比赛时我们队一个小时不到切了5个水题，最后AC的只有六个题（B D E F I M）K题思路完全正确，但是队友用int 输入，最后一组样例死活过不去，还以为是自己思路不对，赛后改成ull直接过掉也醉了。L题线段树全程卡bug，WA到死，涵哥给的题解说是平衡树裸题，完全不会平衡树。H题裸的搜索为什么没人做啊，全程跟榜读都没有读。赛后补题 A C G 目前不会，只能先把涵哥的题解贴上去
时间限制：C/C++ 1秒，其他语言2秒
64bit IO Format: %lld
题目描述
给你三组数列，分别为
现在给你一个式子：
然后我们可以将这个函数画在一个xoy直角坐标系下，x的范围为[0,100]，当然我们可以得到一条曲线，现在你们涵哥让你们求出这个曲线的长度，结果保留两位小数
输入描述:
单组输入：
每组测试数据第一行输入一个整数n。
接下来n行，每行3个数代表
Data limit：
输出描述:
对于每组测试数据，输出对应答案，结果保留两位小数
输入
3 1 2 3 4 5 6 7 8 9
输出
215.56
完全不知道怎么积分，学完再补一下
1 #include<bits/stdc++.h> 2 using namespace std; 3 double a[55],b[55],k[55]; 4 double fs(double x,int s) 5 { 6 if(k[s]*(x-a[s])*(x-a[s])+b[s]>100) 7 return 0; 8 return k[s]*(2*x-2*a[s]); 9 } 10 int n; 11 double ges(double x) 12 { 13 double ans=100,res=0; 14 for(register int s=1; s<=n; s++) 15 if(k[s]*(x-a[s])*(x-a[s])+b[s]<ans) 16 res=fs(x,s),ans=k[s]*(x-a[s])*(x-a[s])+b[s]; 17 return res; 18 } 19 double fun(double x) 20 { 21 return sqrt(1+ges(x)*ges(x)); 22 } 23 double Simpson(double l,double r) 24 { 25 return (fun(l)+fun(r)+4*fun((l+r)/2))/6*(r-l); 26 } 27 double asr(double l,double r,double last,int deep,double eps) 28 { 29 double m=(l+r)/2,a,b,ans; 30 a=Simpson(l,m); 31 b=Simpson(m,r); 32 ans=a+b; 33 if(deep<10||fabs(ans-last)>eps) 34 ans=asr(l,m,a,deep+1,eps/2)+asr(m,r,b,deep+1,eps/2); 35 return ans; 36 } 37 int main() 38 { 39 int t; 40 double ans=1e9; 41 scanf("%d",&n); 42 for(int s=1; s<=n; s++) 43 scanf("%lf%lf%lf",k+s,a+s,b+s); 44 ans=asr(0,100,Simpson(0,100),0,1e-4); 45 printf("%.2f\n",ans); 46 }
B wyh的矩阵
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
给你一个n*n矩阵，按照顺序填入1到n*n的数，例如n=5，该矩阵如下
|
1 |
2 |
3 |
4 |
5 |
|
6 |
7 |
8 |
9 |
10 |
|
11 |
12 |
13 |
14 |
15 |
|
16 |
17 |
18 |
19 |
20 |
|
21 |
22 |
23 |
24 |
25 |
现在让你连接相邻两条边的中点，然后只保留他们围成封闭图形区域的数字，那么这个矩阵变为
|
|
|
3 |
|
|
|
|
7 |
8 |
9 |
|
|
11 |
12 |
13 |
14 |
15 |
|
|
17 |
18 |
19 |
|
|
|
|
23 |
|
|
现在你们涵哥让你求变化后的矩阵的所有元素的和为多少
输入描述:
输入第一行一个整数T(1<=T<=100)
接下来有T组测试数据，每组测试数据输入一个整数n(3<=n<=10000)
保证输入的n为奇数
输出描述:
对于每组测试数据，输出对应答案
输入
2 3 5
输出
25 169
语法题没什么可说的，直接上代码
1 #include <bits/stdc++.h> 2 using namespace std; 3 int main() { 4 ios::sync_with_stdio(false); 5 cin.tie(NULL); 6 int t, n, i, j, k; 7 unsigned long long int ans; 8 scanf("%d", &t); 9 while (t--) { 10 scanf("%d", &n); 11 ans = 0; 12 for (i = 0; i <= n / 2; i++) 13 for (j = n / 2 - i; j <= n / 2 + i; j++) 14 ans += i * n + j + 1; 15 for (k = 1; i < n; i++, k++) 16 for (j = k; j < n - k; j++) { 17 //cout << i * n + j + 1 << endl; 18 ans += i * n + j + 1; 19 } 20 cout << ans << endl; 21 } 22 return 0; 23 }
C wyh的商机
时间限制：C/C++ 3秒，其他语言6秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
一天，你们wyh学长和你们zhl学长玩一个游戏，这个游戏规则是这样的
给你n个城市，保证这n个城市之间都只有一条道路可以到达。
有一件物品，在所有城市中都是一样的，但是由于各个城市的经济发展不同，导致每个城市对于这件物品销售的价格不同。
游戏一共进行Q轮。
每轮给你2个点s和t，其中s代表起点，t代表终点。
对于每一个城市都可以选择买这个物品，如果手里有这个物品的话，也可以选择卖掉这个物品，对于同一个城市来说，买和卖的价格是一样的，每一个城市只能买一件物品
现在，你们wyh学长和zhl学长都需要找到一个方案，使得从起点走到终点的时候盈利最多，请你帮助帮助他们吧
输入描述:
每个测试文件中都只有一组测试数据
输入第一行一个整数n(1<=n<=50000)，代表有n个城市
第二行输入n个数，代表每个城市对于这件物品的价格wi(1<=wi<=50000)
接下来有n-1行，每行2个数a和b，代表a到b之间有一条路
接下来输入一个数Q(1<=Q<=50000)
接下来Q行，每行2个数s和t
输出描述:
对于每组测试数据，输出对应答案，如果从起点到终点不能盈利的话，输出0
输入
4 1 5 3 2 1 3 3 2 3 4 9 1 2 1 3 1 4 2 3 2 1 2 4 3 1 3 2 3 4
输出
4 2 2 0 0 0 0 2 0
LCA 并不会。
D wyh的迷宫
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
给你一个n*m的迷宫，这个迷宫中有以下几个标识：
s代表起点
t代表终点
x代表障碍物
.代表空地
现在你们涵哥想知道能不能从起点走到终点不碰到障碍物（只能上下左右进行移动，并且不能移动到已经移动过的点）。
输入描述:
输入第一行一个整数T(1<=T<=10)
接下来有T组测试数据，对于每一组测试数据，第一行输入2个数n和m(1<=n,m<=500)
接下来n行，每行m个字符代表这个迷宫，每个字符都是上面4个中的一种
数据保证只有一个起点和一个终点
输出描述:
对于每一组测试数据，如果可以的话输出YES，不可以的话输出NO
输入
1 3 5 s...x x...x ...tx
输出
YES
裸 BFS 详细解题可以参照 《挑战程序设计》34页
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 int t, n, m; 6 char maze[500][502]; 7 bool vis[500][500]; 8 9 struct Point 10 { 11 int x; 12 int y; 13 }; 14 15 bool BFS(int x, int y) { 16 queue<Point> que; 17 Point p; 18 vis[x][y] = true; 19 que.push({x, y}); 20 while (!que.empty()) { 21 p = que.front(); 22 que.pop(); 23 if (maze[p.x][p.y] == 't') 24 return true; 25 if (p.x + 1 < n && vis[p.x + 1][p.y] == false && maze[p.x + 1][p.y] != 'x') { 26 que.push({p.x + 1, p.y}); 27 vis[p.x + 1][p.y] = true; 28 } 29 if (p.y + 1 < m && vis[p.x][p.y + 1] == false && maze[p.x][p.y + 1] != 'x') { 30 que.push({p.x, p.y + 1}); 31 vis[p.x][p.y + 1] = true; 32 } 33 if (p.x - 1 >= 0 && vis[p.x - 1][p.y] == false && maze[p.x - 1][p.y] != 'x') { 34 que.push({p.x - 1, p.y}); 35 vis[p.x - 1][p.y] = true; 36 } 37 if (p.y - 1 >= 0 && vis[p.x][p.y - 1] == false && maze[p.x][p.y - 1] != 'x') { 38 que.push({p.x, p.y - 1}); 39 vis[p.x][p.y - 1] = true; 40 } 41 } 42 return false; 43 } 44 45 int main(void) { 46 ios::sync_with_stdio(false); 47 cin.tie(NULL); 48 int i, j; 49 scanf("%d", &t); 50 while (t--) { 51 scanf("%d %d", &n, &m); 52 memset(vis, 0, sizeof(vis)); 53 getchar(); 54 for (i = 0; i < n; i++) 55 gets(maze[i]); 56 for (i = 0; i < n; i++) 57 for (j = 0; j < m; j++) 58 if (maze[i][j] == 's') { 59 if (BFS(i, j) == true) 60 printf("YES\n"); 61 else 62 printf("NO\n"); 63 goto BREAKOUT; 64 } 65 BREAKOUT:; 66 } 67 return 0; 68 }
E wyh的阶乘
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
这个问题很简单，就是问你n的阶乘末尾有几个0？
输入描述:
输入第一行一个整数T(1<=T<=100)，代表测试组数
接下来T行，每行一个数n(1<=n<=10^9)
输出描述:
对于每组测试数据，输出对应答案
输入
5 1 2 3 4 5
输出
0 0 0 0 1
比赛时用c++打标到20以为是5个一组依次增加，交上去WA了，用Python打到100发现是循环除以5加商。
题解：
这个题实际上就是求有多少个5的因子，因为要想末尾出现0，必须要有2*5，那么对于阶乘来说，5的个数肯定会比2的个数少，所以直接找有多少个5的根数就可以了
1 #include <iostream> 2 using namespace std; 3 int slove(int n){ 4 int tot= 0; 5 while(n > 0){ 6 tot += n / 5; 7 n = n / 5; 8 } 9 return tot; 10 } 11 int main(){ 12 int tot; 13 cin>>tot; 14 while(tot--){ 15 int n; 16 cin>>n; 17 int ans; 18 ans=slove(n); 19 cout<<ans<<endl; 20 } 21 return 0; 22 }
F wyh的集合
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
你们wyh学长给你n个点，让你分成2个集合，然后让你将这n个点进行两两连接在一起，连接规则是这样的
1. 连接的两个点必须在不同的两个集合
2. 一个集合内部任意两个点之间不能相连
现在，wyh学长需要让你将这n个点任意分成2个集合之后，最多能连接多少条边？
输入描述:
输入第一行一个整数T(1<=T<=100000)
接下来T组测试数据，每组测试数据输入一个整数n(1<=n<=100000)
输出描述:
对于每组测试数据，输出对应答案
输入
4 0 1 2 4
输出
0 0 1 4
说明
对于4的情况，设4个点为A,B,C,D
第一个集合元素为 A,B
第二个集合元素为C,D
连接的边为AC,AD,BC,BD
此时为最大情况，所以答案为4
题面说的挺高大上的，其实就是求平均数相乘一下因为尽量保证两个集合边数尽可能接近，如果一个集合有n/2条边，另外一个集合就是n-n/2条边，相乘就是结果
1 #include <bits/stdc++.h> 2 using namespace std; 3 int main(void) { 4 ios::sync_with_stdio(false); 5 cin.tie(NULL); 6 unsigned long long int ans; 7 int t, n; 8 scanf("%d", &t); 9 while (t--) { 10 scanf("%d", &n); 11 if (n < 2) { 12 cout << 0 << endl; 13 continue; 14 } 15 else if (n % 2 == 0) 16 ans = (n / 2) * (n / 2); 17 else 18 ans = (n / 2 + 1) * (n / 2); 19 cout << ans << endl; 20 } 21 return 0; 22 }
G wyh的考核
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
wyh非常喜欢lol游戏，一天，他听说学校要选拔lol队员，他非常高兴的就去了，选拔规则是，一共有N个评委，每个评委根据线上对线能力和打团能力给出一个[0,M]之间的一个整数作为分数，然后取平均值，wyh学长非常好奇，他想知道有多少种这样的情况：
平均分等于其中某一位评委给的分数
例如2个评委，给打的分数都是1分，那么此时平均分是1分，即等于第一个评委的分数，又等于第二个评委的分数，这样答案是2
但是由于每个评委打的分都是在[0,M]之间，所以会有很多种情况。
现在请你帮助你们wyh学长数一下有多少种这样的情况，由于结果会很大，请你对1000000007取余
输入描述:
输入第一行一个整数T（1<=T<=110）
接下来有T组测试数据，对于每组测试数据输入2个数n和M(2<=n<=60,1<=M<=200)，代表有n个评委，每个评委的分数都在[0,M]之间的一个整数
输出描述:
对于每组测试数据，输出对应答案
输入
1 3 1
输出
6
说明
样例解释：
对于样例有以下几种打分情况是符合要求的
容斥法
其中每种情况相等的可能性都是三个，比如0分的时候，平均分和第一位、第二位、第三位都相等，所以是3中情况，1的时候也同理，所以答案为6
我们首先枚举均分是多少，然后就知道剩下n-1个人的总分了
然后我们首先考虑剩下的n-1个人里面都选（0-没有上限）的方案数，即隔板法可求
然后再减去一个是（m+1到上限），（n-2）个（0-没有上限）
然后再加上两个个是（m+1到上限），（n-3）个（0-没有上限）
然后再减去三个个是（m+1到上限），（n-4）个（0-没有上限）
……
即容斥一下即可求得答案
效率n*m
H wyh的吃鸡
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
最近吃鸡游戏非常火，你们wyh学长也在玩这款游戏，这款游戏有一个非常重要的过程，就是要跑到安全区内，否则就会中毒持续消耗血量，我们这个问题简化如下
假设地图为n*n的一个图，图中有且仅有一块X的联通快代表安全区域，有一个起点S代表缩圈的时候的起点，图中C代表的是车（保证车的数量小于等于100），标记为.的代表空地，可以任意通过，O代表障碍物不能通过。每次没有车的时候2s可以走一个格（只能走自己的上下左右4个方向），有车的话时间为1s走一个格
现在告诉你最多能坚持的时间为t秒，问你在t秒内（含t秒）能否从s点到达安全区域，能的话输出YES，并且输出最短时间，不能的话输出NO
输入描述:
输入第一行一个整数T(1<=T<=10)
接下来有T组测试数据，每组测试数据输入2个数n和k(1<=n<=100,1<=k<=10^9)
接下来n行，每行n个字符，代表对应的n*n的地图，每个字符都是上面的一种，并且保证只有一个起点，只有一块安全区域。
输出描述:
对于每组测试数据，先输出能否到达，能的话输出YES，然后换行输出最短时间，如果不能的话直接输出NO
输入
3 2 3 .X S. 2 3 .X SC 2 4 .X S.
输出
NO YES 3 YES 4
两次 BFS 第一次不考虑车求最短路，第二次从终点向起点BFS 两次vis的和为坐车的结果
1 #include <bits/stdc++.h> 2 #define LL long long 3 using namespace std; 4 #define maxn 107 5 char a[maxn][maxn]; 6 int vis1[maxn][maxn],vis2[maxn][maxn]; 7 int mx[]={0,0,1,-1}; 8 int my[]={1,-1,0,0}; 9 int n; 10 struct node 11 { 12 int x,y,t; 13 }f,ne; 14 int t0; 15 void bfs1(int x,int y) 16 { 17 int i,j; 18 for(i=1;i<=n;i++) 19 for(j=1;j<=n;j++) 20 vis1[i][j]=-1; 21 f.x=x; 22 f.y=y; 23 f.t=0; 24 vis1[x][y]=f.t; 25 queue <node> q; 26 q.push(f); 27 while(!q.empty()) 28 { 29 f=q.front(); 30 q.pop(); 31 for(i=0;i<4;i++) 32 { 33 ne=f; 34 ne.x+=mx[i]; 35 ne.y+=my[i]; 36 ne.t+=2; 37 if(ne.x>=1&&ne.x<=n&&ne.y>=1&&ne.y<=n&&a[ne.x][ne.y]!='O'&&vis1[ne.x][ne.y]==-1) 38 { 39 vis1[ne.x][ne.y]=ne.t; 40 if(a[ne.x][ne.y]=='X') 41 t0=min(t0,ne.t); 42 else 43 q.push(ne); 44 } 45 } 46 } 47 } 48 void bfs2() 49 { 50 int i,j; 51 for(i=1;i<=n;i++) 52 for(j=1;j<=n;j++) 53 vis2[i][j]=-1; 54 queue <node> q; 55 for(i=1;i<=n;i++) 56 { 57 for(j=1;j<=n;j++) 58 { 59 if(a[i][j]=='X') 60 { 61 f.x=i; 62 f.y=j; 63 f.t=0; 64 vis2[i][j]=f.t; 65 q.push(f); 66 } 67 } 68 } 69 while(!q.empty()) 70 { 71 f=q.front(); 72 //printf("(%d,%d,%d) ",f.x,f.y,f.t); 73 q.pop(); 74 for(i=0;i<4;i++) 75 { 76 ne=f; 77 ne.x+=mx[i]; 78 ne.y+=my[i]; 79 ne.t++; 80 if(ne.x>=1&&ne.x<=n&&ne.y>=1&&ne.y<=n&&a[ne.x][ne.y]!='O'&&vis2[ne.x][ne.y]==-1) 81 { 82 vis2[ne.x][ne.y]=ne.t; 83 if(a[ne.x][ne.y]=='C') 84 { 85 if(vis1[ne.x][ne.y]!=-1) 86 t0=min(t0,ne.t+vis1[ne.x][ne.y]); 87 } 88 q.push(ne); 89 } 90 } 91 } 92 } 93 int main() 94 { 95 int t; 96 scanf("%d",&t); 97 while(t--) 98 { 99 int k,i,j,x,y; 100 scanf("%d%d",&n,&k); 101 for(i=1;i<=n;i++) 102 { 103 scanf("%s",a[i]+1); 104 for(j=1;j<=n;j++) 105 { 106 if(a[i][j]=='S') 107 x=i,y=j; 108 } 109 } 110 t0=1e9+7; 111 bfs1(x,y); 112 if(t0==1e9+7) 113 { 114 printf("NO\n"); 115 continue; 116 } 117 bfs2(); 118 if(t0>k) 119 { 120 printf("NO\n"); 121 } 122 else 123 { 124 printf("YES\n%d\n",t0); 125 } 126 } 127 return 0; 128 }
I wyh的物品
时间限制：C/C++ 5秒，其他语言10秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
wyh学长现在手里有n个物品，这n个物品的重量和价值都告诉你，然后现在让你从中选取k个，问你在所有可能选取的方案中，最大的单位价值为多少（单位价值为选取的k个物品的总价值和总重量的比值）
输入描述:
输入第一行一个整数T(1<=T<=10)
接下来有T组测试数据，对于每组测试数据，第一行输入两个数n和k(1<=k<=n<=100000)
接下来有n行，每行两个是a和b，代表这个物品的重量和价值
输出描述:
对于每组测试数据，输出对应答案，结果保留两位小数
输入
1 3 2 2 2 5 3 2 1
输出
0.75
说明
对于样例来说，我们选择第一个物品和第三个物品，达到最优目的
这道题目是一道0-1分数规划求最优值。
方法是一个二分搜索+贪心的题目。
出这道题目就是告诉大家二分不仅可以查找，还可以搜索一个更优值。
要使得单位重量的价值最大，则其最大不超过单个中最大的单位重量的价值，最小当然不小于0.
那么我们就这一在0--最大单位重量的价值中间找一个值ans，使得ans为满足题目条件的最大值。如果满足条件，则可以找更大的。设置一个条件。既二分搜索、
从n个物品中找k个使得k个的价值和/质量和>=ans
为了使得ans尽可能的大，那么这里就要贪心选择。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define INF 1000010 4 #define eps 1e-4 5 double w[100005],v[100005]; 6 double y[100005];//v-x*w 7 double max_ave; 8 int n,k; 9 bool get(double x) 10 { 11 int i; 12 double sum=0; 13 for(i=0;i<n;i++) 14 { 15 y[i]=v[i]-x*w[i]; 16 } 17 sort(y,y+n); 18 for(i=0;i<k;i++) 19 { 20 sum+=y[n-i-1]; 21 } 22 return sum>=0; 23 } 24 void bin() 25 { 26 double low,high,mid; 27 low=0.0; 28 high=INF; 29 for(int i=0;i<100;i++) 30 { 31 mid=(low+high)/2; 32 if(get(mid)) 33 low=mid; 34 else high=mid; 35 } 36 printf("%.2lf\n",high); 37 } 38 int main() 39 { 40 int i; 41 int tot; 42 cin>>tot; 43 while(tot--) 44 { 45 scanf("%d%d",&n,&k); 46 for(i=0;i<n;i++) 47 { 48 scanf("%lf%lf",&w[i],&v[i]); 49 } 50 bin(); 51 } 52 return 0; 53 }
J wyh的问题
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
我国现在能源消耗非常严重，现在*有这样一个工作，每天早上都需要把一些路灯关掉，但是他们想让在关闭的过程中所消耗的能源是最少的，负责路灯关闭的工作人员以1m/s的速度进行行走，假设关闭路灯的时候不需要花费任何的时间，请你编写一个程序，计算在给定路灯位置和每个路灯的消耗能源的多少，求出当所有路灯关闭的时候所需要的最少能量
输入描述:
多组测试数据循环输入
每组测试数据第一行：N表示路灯的数量 （2<=N <=1000）
第二行：V表示开始关灯的路灯号码。 （1<=V<=N）
接下来的N行中，每行包含两个用空格隔开的整数D和W，用来描述每盏灯的参数
D表示该路灯到原点的距离 (用米为单位来表示)，
W表示灯泡的功率，即每秒该灯泡所消耗的能量数。（0<=D<=1000，0<=W<=1000）
路灯按照顺序给出，起始位置的那盏灯不算消耗的电能里面
输出描述:
输出一个整数，即消耗能量之和的最小值。
输入
4 3 2 2 5 8 6 1 8 7
输出
56
说明
对于样例，我一开始在第三个路灯的位置，即在6位置
第1s的时候去5把第二盏灯关闭，消耗电能8
然后去第四盏灯，第四盏灯亮的时间是4s 所以消耗电能28
最后去关第一盏灯第一盏灯亮的时间是10s 所以消耗电能20
最后总和为8+28+20=56
关灯的人要么是去左边关灯，或者是去右边关灯，也即要关闭的下一个路灯要么是从已关闭路段的左端过去的，要么是从已关闭的路段的右端过去的，定义：
DP[i][j][0]表示i到j的路灯都已经关闭，人在路灯i的位置，此时已经消耗的最小电能
DP[i][j][1]表示i到j的路灯都已经关闭，人在路灯j的位置，此时已经消耗的最小电能
则状态转移式：
DP[i][j][0] = min(DP[i+1][j][0]+[i+1,j]路段以外未关闭路灯在人从i+1走的i期间消耗的电能，DP[i+1][j][1]+[i+1,j]路段以外未关闭路灯在人从j走到i期间消耗的电能)
DP[i][j][1] = min(DP[i][j-1][0]+[i,j-1]路段以外未关闭路灯在人从i走到j期间消耗的电能，DP[i][j-1][1]+[i,j-1]路段以外未关闭路灯在人从j-1走到j期间消耗的电能)
1 #include <bits/stdc++.h> 2 #define LEN 1001 3 #define min(a,b) ((a<b)?(a):(b)) 4 5 int DP[LEN][LEN][2]; 6 int bw[LEN][LEN]; 7 int D[LEN]; 8 int W[LEN]; 9 10 int main() 11 { 12 int N,V,tw=0; 13 int i,j,t; 14 while(scanf("%d %d",&N,&V)!=EOF) 15 { 16 tw = 0; 17 memset(bw, 0, sizeof(bw)); 18 for(i=1; i<=N; ++i) 19 { 20 scanf("%d %d",&D[i],&W[i]); 21 tw += W[i]; 22 } 23 for(i=1; i<=N; ++i) 24 { 25 for(j=i; j<=N; ++j) 26 { 27 bw[i][j] = bw[i][j-1] + W[j]; 28 } 29 } 30 31 //初始化 32 for(i=V-1; i>0; --i) 33 { 34 DP[i][V][0] = DP[i+1][V][0]+(tw-bw[i+1][V])*(D[i+1]-D[i]); 35 DP[i][V][1] = DP[i][V][0] + (tw-bw[i][V])*(D[V]-D[i]); 36 } 37 for(j=V+1; j<=N; ++j) 38 { 39 DP[V][j][1] = DP[V][j-1][1] + (tw-bw[V][j-1])*(D[j]-D[j-1]); 40 DP[V][j][0] = DP[V][j][1] + (tw-bw[V][j])*(D[j]-D[V]); 41 } 42 43 //DP 44 for(i=V-1; i>0; i--) 45 { 46 for(j=V+1; j<=N; ++j) 47 { 48 DP[i][j][0] = min(DP[i+1][j][0]+(tw-bw[i+1][j])*(D[i+1]-D[i]), 49 DP[i+1][j][1]+(tw-bw[i+1][j])*(D[j]-D[i])); 50 DP[i][j][1] = min(DP[i][j-1][0]+(tw-bw[i][j-1])*(D[j]-D[i]), 51 DP[i][j-1][1]+(tw-bw[i][j-1])*(D[j]-D[j-1])); 52 } 53 } 54 printf("%d\n", min(DP[1][N][0], DP[1][N][1])); 55 } 56 return 0; 57 }
K wyh的数列
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
wyh学长特别喜欢斐波那契数列，F（0）=0，F（1）=1，F（n)=F(n-1)+F(n-2)(n>=2)
一天他突发奇想，想求F（a^b）%c
输入描述:
输入第一行一个整数T(1<=T<=100)，代表测试组数
接下来T行，每行三个数 a,b,c (a,b<=2^64) (1<c<1000)
输出描述:
输出第a^b项斐波那契数对c取余的结果
输入
3 1 1 2 2 3 1000 32122142412412142 124124124412124 123
输出
1 21 3
暴力打表会有循环节，比赛是想循环节的规律想到死，后来直接模拟求循环节。数据范围太大必须用 unsigned long long
1 #include <bits/stdc++.h> 2 using namespace std; 3 unsigned long long arr[10000]; 4 5 unsigned long long int pm(unsigned long long int a, unsigned long long int b, unsigned long long int c) { 6 unsigned long long int tmp = 1; 7 a = a % c; 8 while (b > 0) { 9 if (b % 2 == 1) 10 tmp = (tmp * a) % c; 11 b /= 2; 12 a = (a * a) % c; 13 } 14 return tmp; 15 } 16 17 int main(void) { 18 unsigned long long int t, a, b, c, cnt; 19 int i; 20 scanf("%llu", &t); 21 while (t--) { 22 scanf("%llu %llu %llu", &a, &b, &c); 23 arr[0] = 0; 24 arr[1] = 1; 25 for (i = 2;; i++) { 26 arr[i] = (arr[i - 1] + arr[i - 2]) % c; 27 if (arr[i] == 1 && arr[i - 1] == 0) { 28 cnt = i - 1; 29 break; 30 } 31 } 32 unsigned long long int dd = pm(a, b, cnt); 33 cout << arr[dd] << endl; 34 } 35 return 0; 36 }
L wyh的天鹅
时间限制：C/C++ 3秒，其他语言6秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
你们wyh学长小时候住在河边，因为周围的生态环境非常好，所以经常会有天鹅浮在湖面上，每只天鹅都长得不一样，它们偶尔排成一排，偶尔分散开，偶尔也会去其他河畔，wyh学长为了统计它们的个数，编了一个程序赋予它们一个“萌”值，但是这些天鹅很不听话，一会儿会从别的地方游过来一两只，一会儿又会在统计过程中游走一两只，现在请你帮他完成统计任务。
输入描述:
共有T(T<=10)组数据，每组数据第一行为两个数 N, M (N，M <= 500000)，代表有N只天鹅和M次操作，接下来一行是N个数字，下面M行首先会输入一个字符串S，接着会有三类操作，如果S是“insert”，接着输入一个正整数a，代表插入一只“萌”值为a的天鹅，如果S是“delete”，接着输入一个正整数a，代表删除一只“萌”值为a的天鹅，如果S是“query”，接着输入一个正整数k，代表查询“萌”值第k大的天鹅。
萌值为[1,1000000000]，并且保证一定存在第k大
输出描述:
对应每次询问，输出询问结果。
输入
1 5 4 6 4 2 9 1 query 2 insert 7 delete 6 query 2
输出
6 7
线段树维护数字个数，查询一下，比赛是全程卡bug，题解说是裸的平衡树
AC代码（线段树）
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int MAX=1e6+10; 4 int tree[4*MAX]; 5 int ans; 6 void build(int l,int r,int rt){ 7 tree[rt]=0; 8 if(l==r) 9 return ; 10 int mid=(l+r)/2; 11 build(l,mid,2*rt); 12 build(mid+1, r, 2*rt+1); 13 } 14 15 void update(int pos,int val,int l,int r,int rt){ 16 if(l==r){ 17 tree[rt]+=val; 18 return ; 19 } 20 int mid; 21 mid=(l+r)/2; 22 if(pos<=mid) 23 update(pos, val, l, mid, 2*rt); 24 else 25 update(pos, val, mid+1, r, 2*rt+1); 26 tree[rt]=tree[2*rt]+tree[2*rt+1]; 27 } 28 29 void query(int k,int l,int r,int rt){ 30 if(l==r){ 31 ans=l; 32 return ; 33 } 34 int mid; 35 mid=(l+r)/2; 36 if(tree[2*rt+1]>=k) 37 query(k, mid+1, r, 2*rt+1); 38 else 39 query(k-tree[2*rt+1], l, mid, 2*rt); 40 } 41 int main(){ 42 int tot; 43 scanf("%d",&tot); 44 while(tot--){ 45 build(0,MAX,1); 46 int num1,num2; 47 int x; 48 scanf("%d%d",&num1,&num2); 49 for(int i=1;i<=num1;i++){ 50 scanf("%d",&x); 51 update(x, 1, 0, MAX, 1); 52 } 53 while(num2--){ 54 string s; 55 cin>>s; 56 int n; 57 scanf("%d",&n); 58 if(s=="query"){ 59 query(n, 0, MAX, 1); 60 cout<<ans<<endl; 61 }else if(s=="insert"){ 62 update(n, 1, 0, MAX, 1); 63 }else { 64 update(n, -1, 0, MAX, 1); 65 } 66 } 67 } 68 return 0; 69 }
M wyh的数字
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld
题目描述
wyh学长十分钟爱数字‘7’，他想知道每一个数字中有多少个数字‘7’
输入描述:
输入第一行一个整数T(1<=T<=10)
接下来有T组测试数据，对于每组测试数据，输入一个整数n(1<=n<=10000000000)
输出描述:
对于每组测试数据，输出对应答案
输入
2 1234567 123456
输出
1 0
裸字符串查找
1 #include <bits/stdc++.h> 2 using namespace std; 3 int main(){ 4 int tt; 5 cin>>tt; 6 while(tt--){ 7 string s; 8 cin>>s; 9 int len; 10 len=(int )s.size(); 11 int tot; 12 tot=0; 13 for(int i=0;i<len;i++){ 14 if(s[i]-'0'==7){ 15 tot++; 16 } 17 } 18 cout<<tot<<endl; 19 } 20 return 0; 21 }