A.点对最大值

链接：https://ac.nowcoder.com/acm/contest/5758/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<bits/stdc++.h> 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<n;i++) { int a,b;             cin>>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<<ans<<endl; } } 

B.减成一

链接：https://ac.nowcoder.com/acm/contest/5758/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<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int>PII; #define I_int ll inline 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<<res<<endl; } return 0; } 

C.面积

链接：https://ac.nowcoder.com/acm/contest/5758/C
来源：牛客网

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

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

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

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

代码：

#include<iostream> #include<iomanip> 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.扔硬币

链接：https://ac.nowcoder.com/acm/contest/5758/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 <bits/stdc++.h> 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<m; i++) {             y=((y-C(n,i))%mod+mod)%mod; }         cout<<ksm(y,mod-2)*C(n,k)%mod<<"n"; } return 0; } 

E.赛马

链接:https://ac.nowcoder.com/acm/contest/5758/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 <bits/stdc++.h> 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("%dn", ans); } } 

F.三角形

链接：https://ac.nowcoder.com/acm/contest/5758/F
来源：牛客网

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

示例1
输入
2
1
3
输出
1

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

代码：

#include<bits/stdc++.h> 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("%dn", ans); } return 0; } 

G.养花

链接：https://ac.nowcoder.com/acm/contest/5758/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<queue> #include<cstdio> #include<cstring> #include<iostream> 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 %dn",u,v,w);     to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; cap[tot]=w; } bool spfa() {     queue<int>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("%dn",ans); } } 

H.直线

链接：https://ac.nowcoder.com/acm/contest/5758/H
来源：牛客网

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

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

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

代码：

#include <bits/stdc++.h> 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.字典序

链接：https://ac.nowcoder.com/acm/contest/5758/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 <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> 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.最大值

链接：https://ac.nowcoder.com/acm/contest/5758/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<bits/stdc++.h> 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<<ans<<endl; } return 0; } 

如有不足指出，请指正