本文共 13516 字，大约阅读时间需要 45 分钟。

A.点对最大值

链接：

来源：牛客网

题目描述 :

这里有一棵树，每个点和每条边都存在一个价值。对于树上点对的价值，包括点对的起点和终点以及路径上边权值之和，不包括路径上其他点值。 求这颗树上最大的点对价值为多少。

输入描述:

输入t，代表有t组样例。每组样例第一行输入n，代表有n个点。接下来有n-1行，第i行有a[i]和b[i]，代表a[i]节点与i节点存在一条边，且边的值为b[i]，2<=i<=n。接下来一行有n个值c[j]，代表每个节点j的价值，1<=j<=n。 （t<=10，n<1e6，a[i]<i，-500<=b[i]<=500，-500<=c[j]<=500）

输出描述:

输出最大的点对价值

示例1

输入 1 4 1 -2 1 2 1 3 2 -2 3 4

输出

12 思路：

• 对于每个点求出向下延伸最大的两条仅带一个端点的链，并通过两条链之和更新最大值。
• 因为每个节点也有值，因此节点的值也算该节点向下延伸且只有一个端点的链。
• 初始每个节点向下最大链为本节点，并通过子节
  点的最大链不断更新自己向下链的最大值。

代码：

#include
   
    using namespace std;const int maxn=1000010;const int inf=-0x3f;int head[maxn],cnt,val[maxn],ans,f[maxn];struct edge{       int nx,to,w;}edge[maxn*2];void add(int u,int v,int w){       edge[++cnt].to=v;    edge[cnt].nx=head[u];    edge[cnt].w=w;    head[u]=cnt;}void dfs(int u,int fa){       f[u]=val[u];    for(int i=head[u];i;i=edge[i].nx)    {           int v=edge[i].to;        if(v!=fa)        {               dfs(v,u);             ans=max(ans,f[u]+f[v]+edge[i].w);            f[u]=max(f[u],f[v]+edge[i].w);        }    }}int main(){       int n,t;    cin>>t;    while(t--)    {           cin>>n;        ans=-1000;        memset(f,inf,sizeof(f));        memset(head,0,sizeof(head));        cnt=0;        memset(edge,0,sizeof(edge));        for(int i=1;i
    
     >a>>b;            add(a,i+1,b),add(i+1,a,b);        }        for(int i=1;i<=n;i++) cin>>val[i];        dfs(1,0);        cout<
     
      <
     
    
   

B.减成一

链接：

来源：牛客网

题目描述

存在n个数，每次操作可以任选一个区间使得区间内的所有数字减一。问最少多少次操作，可以让所有数都变成1。 数据保证一定有解。 输入描述: 输入t，代表有t组数据。每组数据输入n，代表有n个数。接下来一行输入n个数，数字大小小于1e6。(t<=1000，n<1e5，∑n < 1e6)

输出描述:

每组数据输出一个整数代表最少需要操作的次数。

示例1

输入 1 6 1 3 5 2 7 1 输出 9

思路：

• 每次操作可以将一个区间内的数减一。
• 如图，通过计算出差分数组，操作可以转为先选取一个数减一再选取一个数加一。目标的差分数组也就变成了第一个数为1，其余为0的数组。
• 最快操作方式就是将差分数组第一个数减为1，其余减为0。即操作数为差分数组的正数之和减一。
  

代码：

#include
   
    using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair
    
     PII;#define I_int llinline ll read(){       ll x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){   if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){   x=x*10+ch-'0';ch=getchar();}    return x*f;}char F[200];inline void out(I_int x) {       if (x == 0) return (void) (putchar('0'));    I_int tmp = x > 0 ? x : -x;    if (x < 0) putchar('-');    int cnt = 0;    while (tmp > 0) {           F[cnt++] = tmp % 10 + '0';        tmp /= 10;    }    while (cnt > 0) putchar(F[--cnt]);}  const int maxn=1e5+100;  int a[maxn],b[maxn],n;  bool cmp(int a,int b){       return a>b;}  int main(){         int T=read();      while(T--){                         n=read();        for(int i=1;i<=n;i++){               a[i]=read();            a[i]--;        }                  int res=0;        for(int i=1;i<=n;i++)            if(a[i]>=a[i-1]) res+=a[i]-a[i-1];        cout<
     
      <
     
    
   

C.面积

链接：

来源：牛客网

题目描述

如图所示，正方形周围接4个半圆，求图形的面积

输入描述:

输入t，代表有t组数据。每组数据输入正整数x，代表正方形的边长。(t<100, x<1000)

输出描述:

输出图形面积，并保留2位小数，其中π取3.14。

示例1

输入 1 1 输出 2.57 思路： 签到题，就是求正方形面积和两个圆的面积

代码：

#include
   
    #include
    
     using namespace std;int main(){       int t;    double x;    cin >> t;    double s;    while (t--)    {           cin >> x;        s = x * x + 2 * (x / 2) * (x / 2) * 3.14;        cout << fixed << setprecision(2) << s << endl;    }    return 0;}
    
   

D.扔硬币

链接：

来源：牛客网

题目描述

有n枚硬币，每枚硬币扔出来是正面和反面的概率各占50%。小明同时扔下了n枚硬币后，已知至少有m枚硬币是反面。请问恰好有k枚硬币是正面的概率是多少。

输入描述:

输入t，代表有t组数据。每组数据输入一个数n，m，k，代表有n枚硬币，抛出以后至少有m枚是反面的情况下，恰好有k个正面的概率。 (t<=1000，n<1e5，m<=1000，k<=n)

输出描述:

对于结果是p/q，输出分数取模1e9+7后的结果。

示例1

输入 1 10 3 5 输出 797520667 思路：

• 由于已知部分硬币的方向。因此，扔n个硬币的情况要在2的n次幂的中去掉少于m个硬币是反面的情况。
• 对于k+m>n是不可能的，直接输出0. • 其余情况：C(n,k)/[ 2^n - ∑(C(n,i)) ] (i<m)
• 由于数据量较大，需要进行预处理等。

代码：

#include 
   
    typedef long long ll;using namespace std;const int N=1e5+10;const int mod=1e9+7;ll f[N],inv[N];ll ksm(ll a,ll b){       if(a==0)        return 0;    if(b==1)        return a%mod;    if(b==0)        return 1%mod;    ll ans=ksm(a,b/2);    ans=ans*ans%mod;    if(b%2)        ans=ans*a%mod;    return ans;}void init(){       inv[0]=1;    f[0]=1;    for(int i=1; i<=1e5; i++)    {           f[i]=f[i-1]*i%mod;        inv[i]=ksm(f[i],mod-2);    }}ll C(int n,int m){       return f[n]*inv[n-m]%mod*inv[m]%mod;}int main(){       init();    int t;    cin>>t;    while(t--)    {           int n,m,k;        cin>>n>>m>>k;        if(m+k>n)        {               cout<<0<<"\n";            continue;        }        ll y=ksm(2,n);        for(int i=0; i
   

E.赛马

链接:

来源：牛客网

题目描述

一天小明与他同学准备赛马，他们每人有n匹马，每匹马有一个固定的战力值，战力值高的马会战胜战力值低的马并赢得比赛。每匹马只能出场比赛一次。小明偷看到了他对手每匹马的出场顺序，小明在更改自己马出场顺序后最多能赢多少场比赛。

输入描述:

输入t，代表有t组数据。每组数据输入正整数n，每人的马匹数量。下一行输入n个值a[i]，代表小明每匹马的战力值。接下来一行输入n个值b[i]，代表对手按顺序出场的每匹马的战力值。(t<=10, n<1000，1<=i<=n，a[i]<1e6，b[i]<1e6)

输出描述:

小明在更改马匹出场顺序后，最多能赢的场数。

示例1

输入 1 3 5 8 8 4 7 10 输出 2 思路：

• 做法一：每次暴力寻找比b[i]大且没参赛过的最小a[j]值
  （1<=i<=n1<=j<=n）。时间复杂度O(n^2)。
• 做法二：将a[i]和b[i]数组放到一起排序，每次按照最大括号匹配的方式计算。时间复杂度O(nlogn)。

代码：

#include 
   
    using namespace std;int _, n;int a[1005], b[1005];int main() {       scanf("%d", &_);    while (_--)     {           scanf("%d", &n);        for (int i = 1; i <= n; i++)             scanf("%d", &a[i]);        for (int i = 1; i <= n; i++)             scanf("%d", &b[i]);        sort(a + 1, a + 1 + n); sort(b + 1, b + 1 + n);        int ans = 0, sta = 1;        for (int i = 1; i <= n; i++)         {               for (int j = sta; j <= n; j++)             {                   if (b[i] < a[j])                 {                       ans++;                    sta = j + 1;                    break;                }                sta = j + 1;            }        }        printf("%d\n", ans);    }}
   

F.三角形

链接：

来源：牛客网

题目描述

小明有一根长度为a的木棒，现在小明想将木棒分为多段（每段木棒长度必须为整数）， 使得分隔后的木棍中，取出的任意三段都不能构成三角形，小明想知道木棒最多被分成几段？ 输入描述: 输入数据的第一行是t，表示数据的组数, 接下来每组数据输入一个a （t<=1000, 1 <= a < 2^64 - 1） 输出描述: 对于每组输入样例，打印木棒最多被分为多少段

示例1

输入 2 1 3 输出 1

思路：

三角形两边之和大于第三边，因此不构成三角形的条件就是存在两边之和不超过另一边。所以按照斐波那契数列的方法切割可以使得切割的段数最大，1，1，2，3，5这样可以使得任意三根木棒不能组成三角形，最后无法切割的部分组成一根长的木棒。

代码：

#include
   
    using namespace std;typedef unsigned long long ll;const int N = 1e5 + 5;#define mst(a) memset(a,0,sizeof a)ll a[93] = {    0,1,1 };int main() {       int t;    for (int i = 3; i <= 92; i++)         a[i] = a[i - 1] + a[i - 2];    scanf("%d", &t);    while (t--)     {           ll x;        scanf("%llu", &x);        int ans = 0;        for (int i = 1; a[i] <= x; i++)            x -= a[i], ans++;        printf("%d\n", ans);    }    return 0;}
   

G.养花

链接：

来源：牛客网

题目描述

小明是一个魔法师，他有n棵植物，所有植物排成一排，植物的初始高度为数组h，小明有一些强迫症，他想 让植物的高度都恰好达到k，小明有m瓶药水，但药水分为4种： 1.选择一棵高度为a0的植物变为b0高度的植物 2.选择一棵高度在[a1,a2]区间内的植物变为b1高度的植物 3.选择一棵高度为a1的植物变为[b1, b2]区间内某一高度的植物 4.选择一棵高度在[a1,a2]区间内的植物变为[b1,b2]区间内某一高度的植物 由于每瓶药水有C瓶库存，小明想知道他最多让多少棵植物高度达到k 输入描述: 输入数据第一行是t，表示数据的组数，接下来每组数据输入n，m，k， 接下来一行输入n个数，分别是每棵植物的高度h[i]（1 <= h[i] < k）, 接下来m行开头的两个数字为op和c表示药水是哪一种和该种药水有几瓶，输入如下 若 op=1，则接下来两个整数 a0，b0，意义如上文所述。 若 op=2，则接下来三个整数 a1,a2,b1，意义如上文所述。 若 op=3，则接下来三个整数 a1,b1,b2，意义如上文所述。 若 op=4，则接下来四个整数 a1,a2,b1,b2，意义如上文所述。 数据保证，所有 1 <= a0,b0,a1,b1,a2,b2 <= k （t <= 10，n <= 1e4，m <= 300，k <= 100，c <=1e6） 输出描述: 输出一个整数，表示最多有多少颗植物能生涨到k。 示例1 输入 1 5 4 5 1 1 1 1 1 1 3 1 3 1 3 3 2 1 3 2 5 4 1 1 1 4 5 输出 4

思路：

• 采用网络流直接进行建图，对于四种操作每次都新建两个点from和to，题面中的[a1,a2]区间每个节点连接到from节点，to连接[b1,b2]区间的每个节点。然后跑最大流即可。
• 但对于区间的最大流还可采用线段树建图的方式，建立两棵线段树，每种操作新建节点时直接在两棵线段树上所对应的区间即可。

代码：

#include
   
    #include
    
     #include
     
      #include
      
        using namespace std; #define N 702#define M 70001 int n,num; int sum[N]; int src,decc;int tot,front[N],to[M<<1],nxt[M<<1],cap[M<<1]; int lev[N],cur[N]; void add(int u,int v,int w){   //  printf("%d %d %d\n",u,v,w);    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; cap[tot]=w;} bool spfa(){       queue
       
        q;    memset(lev,-1,sizeof(lev));    for(int i=0;i<=num;++i) cur[i]=front[i];    q.push(src);    lev[src]=0;    int now,nt;    while(!q.empty())    {           now=q.front();        q.pop();        for(int i=front[now];i;i=nxt[i])        {               nt=to[i];            if(lev[nt]!=-1 || cap[i]<=0) continue;            lev[nt]=lev[now]+1;            if(nt==decc) return true;            q.push(nt);        }    }    return false;} int dinic(int now,int flow){       if(now==decc) return flow;    int nt,rest=0,delta;    for(int & i=cur[now];i;i=nxt[i])    {           nt=to[i];        if(lev[nt]!=lev[now]+1 || cap[i]<=0) continue;        delta=dinic(nt,min(flow-rest,cap[i]));        if(delta)        {               cap[i]-=delta;            cap[i^1]+=delta;            rest+=delta;            if(rest==flow) break;        }    }    if(rest!=flow) lev[now]=-1;    return rest;}  int main(){       int T,m,k,op,c,a1,a2,b1,b2;    int ans;    scanf("%d",&T);    while(T--)    {           scanf("%d%d%d",&n,&m,&k);        memset(sum,0,sizeof(sum));        for(int i=1;i<=n;++i)        {               scanf("%d",&c);            sum[c]++;        }        src=0;        num=decc=k+1;        memset(front,0,sizeof(front));        tot=1;        for(int i=1;i<=k;++i)        {               add(src,i,sum[i]);            add(i,src,0);        }        add(k,decc,n);        for(int i=1;i<=m;++i)        {               scanf("%d%d",&op,&c);            if(op==1)            {                   scanf("%d%d",&a1,&b1);                add(a1,b1,c);                add(b1,a1,0);            }            else if(op==2)            {                   scanf("%d%d%d",&a1,&a2,&b1);                num++;                for(int j=a1;j<=a2;++j)                {                       add(j,num,n);                    add(num,j,0);                }                add(num,b1,c);                add(b1,num,0);            }            else if(op==3)            {                   scanf("%d%d%d",&a1,&b1,&b2);                num++;                add(a1,num,c);                add(num,a1,0);                for(int j=b1;j<=b2;++j)                {                       add(num,j,n);                    add(j,num,0);                }            }            else if(op==4)            {                   scanf("%d%d%d%d",&a1,&a2,&b1,&b2);                num++;                for(int j=a1;j<=a2;++j)                {                       add(j,num,n);                    add(num,j,0);                }                num++;                add(num-1,num,c);                add(num,num-1,0);                for(int j=b1;j<=b2;++j)                {                       add(num,j,n);                    add(j,num,0);                }                             }        }        ans=0;        while(spfa())            ans+=dinic(src,n);        printf("%d\n",ans);    }}
       
      
     
    
   

H.直线

链接：

来源：牛客网

题目描述

平面上存在n条直线。请问n条直线在平面上最多存在多少交点。

输入描述:

输入数据的第一行是t，表示数据的组数（t < 100）, 接下来每组数据输入一个n（1<=n <= 1e15）

输出描述:

对于每组输入样例，打印n条直线最多有多少个交点 示例1 输入 复制 2 1 2 输出 复制 0 1 思路： 平面中直线交点最多n*(n-1)/2个，大数运算

代码：

#include 
   
    using namespace std;inline void print(__int128 x){       if(x>9)        print(x/10);    putchar(x%10+'0');}int main(){       int t;    scanf("%d",&t);    while(t--)    {           __int128  n;        scanf("%lld",&n);        print(n*(n-1)/2);puts(" ");    }    return 0;}
   

I.字典序

链接：

来源：牛客网

小明遇到了一个问题希望你能帮他解决

现在有n个数字排成一列构成数组A，数组A中存在n个数a[i], 其中1<=i<=n。 数组sj为删除数组A中的第j个数后，剩余n-1个数构成的数组，其中1<=j<=n。 小明希望你把s1~sn的数组按照字典序大小排列起来， 若两个数组相等，则认为删除元素编号小的数组字典序更小

输入描述:

输入数据第一行是t，表示数据的组数，接下来每组数据输入n，接下来一行 一共n个数，a[i]表示数组的第i个数 （t<=10，n <= 1e5，a[i] <= 1e9）

输出描述:

输出一行n个整数，b1,b2…bn，表示Sb1 < Sb2 < … < Sbn 示例1 输入 复制 1 7 1 1 2 1 1 1 2 输出 复制 3 7 4 5 6 1 2

思路：

对于a[i]位置的数据分一下三种情况进行讨论

1. 若a[i] == a[i+1]，那么删除a[i]后与删除a[i + 1]的结果一样，那么a[i]出处的字典序会比a[i+1]出小
2. 若a[i] < a[i+1]，那么删除a[i]后的数组在第i位上比删除a[i+1]所得到的更大，所以第i个位置的字典序比后面位置的字典序都小
3. 若a[i] > a[i+1]，那么删除a[i]后的数组在第i位上比删除a[i+1]所得到的更小，所以第i个位置的字典序比后面位置的字典序都大。

代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;int t, n, tot;int a[110000], b[110000], ans[110000];int main() {       scanf("%d", &t);    while(t--) {           scanf("%d", &n);        tot = 0;        for(int i = 1; i <= n; i++) {               scanf("%d", &a[i]);            b[i] = 0;        }        for(int i = 1; i < n; i++) {               if(a[i] > a[i + 1]) {                   int temp = i;                while(a[temp - 1] == a[temp] && temp > 1) temp--;                for(int j = temp; j <= i; j++) {                       ans[++tot] = j;                    b[j] = 1;                }            }        }                     for(int i = n; i >= 1; i--) {               if(!b[i]) {                   int temp = i;                while(a[temp - 1] == a[temp] && temp > 1) temp--;                for(int j = temp; j <= i; j++) {                       ans[++tot] = j;                    b[j] = 1;                }            }        }                 for(int i = 1; i <= n; i++) printf("%d ", ans[i]);        printf("\n");             }    return 0;}
       
      
     
    
   

J.最大值

链接：

来源：牛客网

有一个字符串s，对于字符串中一个非前缀子串恰好为字符串的前缀我们称之为ac串。

请问给出一个字符串他的ac串最大长度为多少

输入描述:

输入数据第一行是t，表示数据的组数，接下来每组数据输入一个字符串s （t<=10，s<=1e5） 输出描述: 输出最大长度 示例1 输入 复制 2 aaaaa abacc 输出 复制 4 1 说明 aaaab的ac串是aaa(2:4) acac的ac串是ac(3:4)

思路：

ac串其实是kmp中next数组的含义，所以求出字符串的next数组即可得到答案

代码：

#include
   
    using namespace std;typedef long long ll;const int N = 100005;char p[N];int ne[N];void solve(int m) {       for (int i = 2, j = 0; i <= m; i ++ ){       while (j && p[i] != p[j + 1]) j = ne[j];    if (p[i] == p[j + 1]) j ++ ;    ne[i] = j;}}int main() {       ll t;    cin>>t;    while(t--) {           scanf("%s",p+1);        int len = strlen(p+1);        solve(len);        int ans = 0 ;        for(int i=1;i<=len;i++) {           ans = max(ans,ne[i]);        }        cout<
    
     <
    
   

如有不足指出，请指正

转载地址：http://mhbiz.baihongyu.com/