https://ac.nowcoder.com/acm/contest/5758#description
做的迟了+只会水题.jpg 剩下的咕咕咕慢慢补
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>1，n<1e6，a[i]<i，-500<=b[i]<=500，-500<=c[j]<=500）
输出描述:
输出最大的点对价值
首先注意这题输入比较坑，n那一行实际上是第一行，然后从第二行开始输入边…
注意这个题的点对价值的定义：起点终点加上路径上的边权总和。那么可以联想到树的直径，关键在于两个端点怎么处理。其实很简单，只需要把d数组初始化成对应的点权即可。这里我套了蓝书的板子，此处d[x]的含义为：从节点x出发走向x为根的子树，能够到达的最远价值处（包含路径端点的点权以及经过的边的边权之和，不包含x的点权）。对于这个题而言，假设当前处理到的点的度不为1，那么这个初始化了的d[x]肯定会被后续更新掉，假设度为1，联想到求树的直径时，dfs到了叶子时其实啥都没干，叶子节点的d值也没有被更新，那么这个题要加上端点，我就把它初始化成点权，问题完美解决。
#include <bits/stdc++.h> #define N 1000006 using namespace std; int head[N],ver[2*N],edge[2*N],Next[2*N],p[N],tot=0,d[N],n;//d[x]为不包含本点的从x出发能走的最远路径和 （包括最远点的端点值 不包括x bool v[N]; long long ans; void add(int x,int y,int z) { ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot; } void dp(int x) { v[x]=1; int i; for(i=head[x];i;i=Next[i]) { int y=ver[i]; if(v[y])continue; dp(y); if(ans<(long long)d[x]+d[y]+edge[i]) { ans=(long long)d[x]+d[y]+edge[i]; } d[x]=max(d[x],d[y]+edge[i]); } } int main() { int t; cin>>t; while(t--) { tot=0; ans=-1e18; memset(head,0,sizeof(head)); memset(ver,0,sizeof(ver)); memset(edge,0,sizeof(edge)); memset(Next,0,sizeof(Next)); memset(d,0,sizeof(d)); memset(v,0,sizeof(v)); int i; cin>>n; for(i=2;i<=n;i++) { int a,b; cin>>a>>b; add(i,a,b); add(a,i,b); } for(i=1;i<=n;i++) { scanf("%d",&p[i]); d[i]=p[i]; } dp(1); cout<<ans<<endl; } return 0; }
B．
题目描述
存在n个数，每次操作可以任选一个区间使得区间内的所有数字减一。问最少多少次操作，可以让所有数都变成1。
数据保证一定有解。
输入描述:
输入t，代表有t组数据。每组数据输入n，代表有n个数。接下来一行输入n个数，数字大小小于1e6。(t<=1000，n<1e5，∑n < 1e6)
输出描述:
每组数据输出一个整数代表最少需要操作的次数。
差分，是蓝书上那道题的超级弱化版。求出差分数组，对区间减1相当于差分数组左端点l减1，右端点r+1的位置+1，贪心的先把正负中和后再消去剩下的正数或者负数。最后输出差分数组正数之和和负数相反数之和较大的那个数-1（因为最后要构成1 0 0 0这样，所以要减去1）
#include <bits/stdc++.h> using namespace std; int n,a[100005],d[100005]; int main() { int t; cin>>t; a[0]=0; while(t--) { cin>>n; int i; long long pos=0,neg=0; for(i=1;i<=n;i++) { scanf("%d",&a[i]); d[i]=a[i]-a[i-1]; } if(n==1) { cout<<a[1]-1<<endl; continue; } for(i=1;i<=n;i++) { if(d[i]>0)pos+=d[i]; else neg-=d[i]; } cout<<max(pos,neg)-1<<endl; } } //最终要变成1 0 0 0 0...
C．
题目描述
如图所示，正方形周围接4个半圆，求图形的面积
输入描述:
输入t，代表有t组数据。每组数据输入正整数x，代表正方形的边长。(t<100, x<1000)
输出描述:
输出图形面积，并保留2位小数，其中π取3.14。
签到。
#include <bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while(t--) { double l,ans; cin>>l; ans=l*l+0.5*l*l*3.14; printf("%.2lf ",ans); } }
E．
题目描述
一天小明与他同学准备赛马，他们每人有n匹马，每匹马有一个固定的战力值，战力值高的马会战胜战力值低的马并赢得比赛。每匹马只能出场比赛一次。小明偷看到了他对手每匹马的出场顺序，小明在更改自己马出场顺序后最多能赢多少场比赛。
输入描述:
输入t，代表有t组数据。每组数据输入正整数n，每人的马匹数量。下一行输入n个值a[i]，代表小明每匹马的战力值。接下来一行输入n个值b[i]，代表对手按顺序出场的每匹马的战力值。(t<=10, n<1000，1<=i<=n，a[i]<1e6，b[i]<1e6)
输出描述:
小明在更改马匹出场顺序后，最多能赢的场数。
A数组排序后贪心用下等马优先比较即可。数据范围过水懒得写O(n)做法了。
#include <bits/stdc++.h> using namespace std; int n,a[1005],b[1005]; int main() { int t; cin>>t; while(t--) { cin>>n; int i,j,ans=0; for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<=n;i++) scanf("%d",&b[i]); sort(a+1,a+n+1); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(a[j]==-0x3f3f3f3f)continue; if(a[j]>b[i]) { ans++; a[j]=-0x3f3f3f3f; break; } } } cout<<ans<<endl; } }
F．
题目描述
小明有一根长度为a的木棒，现在小明想将木棒分为多段（每段木棒长度必须为整数），
使得分隔后的木棍中，取出的任意三段都不能构成三角形，小明想知道木棒最多被分成几段？
输入描述:
输入数据的第一行是t，表示数据的组数, 接下来每组数据输入一个a
（t<=1000, 1 <= a < 2^64 - 1）
输出描述:
对于每组输入样例，打印木棒最多被分为多少段
最多的情况是按斐波那契数列分配长度（模拟一下更方便理解）。当前i项和大于a时输出i-1即可（宁缺毋滥）。注意斐波那契前k项和是Fib[k+2]-1。
C++这个题用ull好像会稍微爆掉，所以我选择python
t=eval(input()) x=0 fib=[0,1,1]; i=0 j=0 for j in range(3,100): fib.append(0) for j in range(3,100): fib[j]=fib[j-1]+fib[j-2] while x < t: a=eval(input()) for i in range(100): if fib[i+2]-1>a: print(i-1) break x=x+1
H．
题目描述
平面上存在n条直线。请问n条直线在平面上最多存在多少交点。
输入描述:
输入数据的第一行是t，表示数据的组数（t < 100）, 接下来每组数据输入一个n（1<=n <= 1e15）
输出描述:
对于每组输入样例，打印n条直线最多有多少个交点
输出n*(n-1)/2即可。
人生苦短数据范围很大，所以我选择Python(注意整数除法是// 坑了我半天）
t=int(input()) i=0 while i < t: n=eval(input()) print (int(n*(n-1)//2)) i=i+1
J．
题目描述
有一个字符串s，对于字符串中一个非前缀子串恰好为字符串的前缀我们称之为ac串。
请问给出一个字符串他的ac串最大长度为多少
输入描述:
输入数据第一行是t，表示数据的组数，接下来每组数据输入一个字符串s
（t<=10，s<=1e5）
输出描述:
输出最大长度
求出next数组的最大值输出即可。
#include <bits/stdc++.h> using namespace std; long long a; int next[100005]; int main() { int t; cin>>t; while(t--) { string a; cin>>a; a="0"+a; next[1]=0; int i,j; for(i=2,j=0;i<=a.size()-1;i++) { while(j>0&&a[i]!=a[j+1])j=next[j]; if(a[i]==a[j+1])j++; next[i]=j; } int ans=0; for(i=1;i<=a.size()-1;i++) ans=max(ans,next[i]); cout<<ans<<endl; } }