2018年安徽省程序设计大赛题解_安徽省大学生程序设计竞赛 a植被保护
赞
踩
2018年安徽省程序设计大赛参考题解
水平有限错误难免。
A: 数7
时间限制：1 s
题目描述：
求整数序列A 中位置L 到R中间一共有多少个7，（每一个位上的7和能被7整除的次数）
输入
第一行是T(T<=50)
然后是T行 L R (L<R<1 e 5)
输出
输出7的个数
样例输入
2
1 10
47 50
- 1
- 2
- 3
样例输出
2
3
- 1
- 2
提示
第二组数据解释 47 中含有一个7 49含有2个7 所以输出3
题解
暴力搜索
#include<bits/stdc++.h> using namespace std; int t; int l,r,ans; int slove(int x){ int ans1=0,tmp=x; while(x!=0){ int k=x%10; if(k==7)ans1++; x/=10; } while(tmp%7==0){ ans1++; tmp/=7; } return ans1; } int main(){ scanf("%d",&t); while(t--){ ans=0; scanf("%d%d",&l,&r); for(int i=l;i<=r;i++){ ans+=slove(i); } printf("%d\n",ans); } return 0; }
- 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
- 26
- 27
- 28
- 29
- 30
B: 编译错误
时间限制：3 s
题目描述：
在程序员编写程序的时候，通常会引用其他文件，而引用的文件也会引用其它的头文件。但是出现循环引用的现象编译时便会报错。例如A引用了B，B引用了C，C引用了A，那么就产生了循环引用（Circular reference）。考虑另外一个情况，A引用了B和C，B引用D，C引用D，虽然D被引用了两次，但是没有出现循环引用 。
输入
第一行是一个整数T，代表测试数据的组数。每组数据中第一行是一个整数n，代表有多少个引用关系。接下来n行每行有2个字符串a,b，用空格分隔，代表a引用了b。其中T<=50, n<=10^5，每个字符串的长度不超过100。
输出
共T行。若不会产生编译错误则输出Passed，否则输出Failed。
样例输入
2
8
client.cpp client.h
client.h server.h
server.cpp server.h
server.h common.h
client.h common.h
common.cpp common.h
common.h gtest.h
common.h glog.h
4
work.cpp client.cpp
client.cpp server.cpp
server.cpp adhoc.cpp
adhoc.cpp work.cpp
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
样例输出
Passed
Failed
- 1
- 2
题解：
如果能够拓扑排序说明不会产生编译错误，如果不能拓扑排序说明出现了循环引用。
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+5; struct edge{ int next,to; }; edge e[maxn]; int t,n,cnt,ind[maxn],head[maxn]; string a,b; map<string,int> mp; void add_edge(int u,int v){ cnt++; e[cnt].to=v; e[cnt].next=head[u]; head[u]=cnt; } bool topsort(){ int num=0; queue<int>q; for(int i=1;i<=n;i++){ if(ind[i]==0){ q.push(i); } } while(!q.empty()){ int u=q.front(); q.pop(); for(int i=head[u];i;i=e[i].next){ int v=e[i].to; ind[v]--; if(ind[v]==0){ q.push(v); } } num++; } if(num==n)return true; else return false; } int main(){ scanf("%d",&t); while(t--){ int tot=0,u,v; cnt=0; memset(head,0,sizeof(head)); memset(ind,0,sizeof(ind)); memset(e,0,sizeof(struct edge)*maxn); mp.clear(); scanf("%d",&n); for(int i=1;i<=n;i++){ cin>>a>>b; if(mp.find(a)==mp.end()){ mp.insert(pair<string,int>(a,++tot)); u=tot; } else u=mp[a]; if(mp.find(b)==mp.end()){ mp.insert(pair<string,int>(b,++tot)); v=tot; } else v=mp[b]; add_edge(v,u); ind[u]++; } if(topsort())printf("Passed\n"); else printf("Failed\n"); } return 0; }
- 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
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
C: 做操的时候要排好队
时间限制：3 s
题目描述：
同学们在做早操时，应该按照身高从低到高排好队。但是总是有人不好好排队，老师在审查时会对没有排好的队伍扣除一定的分数。扣的分数被定义为，找到三个人Ai,Aj,Ak，其中i<j<k，分数为max(0,(Ai-Aj))+max(0,(Aj-Ak))。找到一组i,j,k使这个分数最大即是扣除的分数。
输入
第一行是一个整数T，代表测试数据的组数。每组数据中第一行是一个整数n，代表有一共有多少个人。第二行共有n个整数，代表n个人的身高。其中1<=T<=50,3<=n<=10^6 每个数的大小不超过1000。
输出
共T行。扣除的分数。
样例输入
2
4
150 160 170 180
4
160 150 170 180
- 1
- 2
- 3
- 4
- 5
样例输出
0
10
- 1
- 2
题解：
该题是寻找一个i,j,k,满足（i<j<k）但i,j,k并不一定连续,如果我们枚举中间数j,从2到n-2,对于每一次枚举，我们都需要对i，k分别枚举，时间复杂度为O(n2),肯定不能通过。我们其实在枚举过程中重复了很多计算，对于每一个j,我们的目的是寻找i<j的a[i]最大值，k>j的a[k]最小值。
我们可以预先处理，用两个数组mx[i],mn[i],mx[i]表示i之前a[i]的最大值（不包括a[i]）,mn[i]表示以i之后a[i]的最小值。然后我们直接枚举max（mx [i]-a[i],0）+ max（a[i]-mn[i]）,时间复杂度为O(n);
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+5; int mx[maxn],mn[maxn]; int t,n; int a[maxn]; int main(){ scanf("%d",&t); while(t--){ int ans=0; memset(mx,0,sizeof(mx)); memset(mn,0,sizeof(mn)); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } mx[1]=a[1],mn[n]=a[n]; for(int i=2;i<=n-1;i++){ mx[i]=max(mx[i-1],a[i-1]); } for(int i=n-1;i>=2;i--){ mn[i]=min(mn[i+1],a[i+1]); } for(int i=2;i<=n-1;i++){ ans=max(max(mx[i]-a[i],0)+max(a[i]-mn[i],0),ans); } printf("%d\n",ans); } return 0; }
- 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
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
D: 判重
时间限制：3 s
题目描述：
小七初始有n个数的样本集。现在又新加了m个数，他想知道这m个数是否已经在这n个数之中了。但是他判断是否有重复的方式和常人有些不同。对于样本集内的任意一个数x，他先将x二进制的第2, 5, 7, 10, 13, 14, 17, 18位取反，生成新的8个数。例如x是7（00111），那么第一个数就是5（00101），第二个数是23（10111）…依次类推。然后将他表格上这8个数的位置全部变为1（初始整个表格全部为0）。判断重复时，若一个数x产生的8个数，在表格内全部为1，就认为这个数x和样本集内的数有重复，否则认为没有重复
输入
输入T，代表T组数据。每组数据初始输入n, m。代表n个样本以及m个需要判断的数。接下来两行，第一行是n个样本，第二行m个需要判断的数，样本在前。对于这m个数，每个数输出yes 或者 no。m组数据相互独立，即这m个数都不会新加入到样本集内。其中T<=50 ,n,m<1e5 。
输出
输出一行，共m个字符串，重复输出yes，否则输出no，空格隔开
样例输入
1
2 2
2 1
3 2
- 1
- 2
- 3
- 4
样例输出
no yes
- 1
题解：
按位取异或加入集合s,再判重。
#include<bits/stdc++.h> using namespace std; int a[8]={2,5,7,10,13,14,17,18}; int t,n,m; set<int>s; int main(){ scanf("%d",&t); while(t--){ s.clear(); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ int x; scanf("%d",&x); for(int j=0;j<=7;j++){ int y=x^(1<<(a[j]-1)); s.insert(y); } } for(int i=1;i<=m;i++){ int x; scanf("%d",&x); int flag=1; for(int j=0;j<=7;j++){ int y=x^(1<<(a[j]-1)); if(s.find(y)==s.end()){ flag=0; break; } } if(flag){ printf("yes "); } else printf("no "); } } return 0; }
- 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
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
E: 最长上升字串
时间限制：3 s
题目描述：
给定n个整数，对其进行m次查询。每次查询是一个范围l到r，求出l到r的最长上升连续子串。上升连续子串的定义为一个连续的子串且严格递增。
输入
第一行是一个整数T，代表测试数据的组数。每组数据中第一行是一个整数n,m，代表有一共有n个人，m个查询。第二行共有n个整数，接下来m行是m次查询，每行两个整数l,r。
输出
共T行，每行m个整数，代表最长上升连续字串。其中T<=50,n,m<1e5,每个数的大小不超过1e9。
样例输入
1
4 2
3 2 4 5
1 3
1 4
- 1
- 2
- 3
- 4
- 5
样例输出
2
3
- 1
- 2
题解：
最长连续上升子串，很容易想到动态规划求解。但本题数据量很大，用动态规划无论是时间还是空间可能都过不去。区间最大值，可以用线段树求解，而且不用更新操作。
线段树维护三个值，lv是区间左端点开始的最长上升连续值，rv是以区间右端点结束的最长上升连续值，mv是该区间的最长上升连续值，pushup时分类讨论，当a[mid]<a[mid+1]时，我们可以知道该区间中间两个点是递增的。这是线段树的区间合并操作，如果你有兴趣的话，可以试一试
hdu-3308
本题就是这题的简化版。
#include<bits/stdc++.h> using namespace std; const int maxn=100005; using namespace std; struct node{ int l,r; int lv,rv,mv; }; node tree[maxn*4+5]; int t,n,m,a[maxn]; void pushup(int i,int l,int r){ int mid=(l+r)>>1; if(tree[i<<1].lv==mid-l+1&&a[mid]<a[mid+1]){ tree[i].lv=tree[i<<1].lv+tree[i<<1|1].lv; } else tree[i].lv=tree[i<<1].lv; if(tree[i<<1|1].rv==r-mid&&a[mid]<a[mid+1]){ tree[i].rv=tree[i<<1].rv+tree[i<<1|1].rv; } else tree[i].rv=tree[i<<1|1].rv; tree[i].mv=max(tree[i<<1].mv,tree[i<<1|1].mv); if(a[mid]<a[mid+1]){ tree[i].mv=max(tree[i].mv,tree[i<<1].rv+tree[i<<1|1].lv); } } void build(int i,int l,int r){ tree[i].l=l; tree[i].r=r; if(l==r){ tree[i].lv=tree[i].rv=tree[i].mv=1; return ; } int mid=(l+r)>>1; build(i<<1,l,mid); build(i<<1|1,mid+1,r); pushup(i,l,r); } int query(int i,int x,int y){ if(tree[i].l>=x&&tree[i].r<=y){ return tree[i].mv; } int mid=(tree[i].l+tree[i].r)>>1; int mx=0; if(x<=mid){ mx=max(mx,query(i<<1,x,y)); } if(y>mid){ mx=max(mx,query(i<<1|1,x,y)); } if(a[mid]<a[mid+1]){ mx=max(mx,min(tree[i<<1].rv,mid-x+1)+min(tree[i<<1|1].lv,y-mid)); } return mx; } int main(){ scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); memset(a,0,sizeof(a)); memset(tree,0,sizeof(struct node)*4*maxn); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } build(1,1,n); while(m--){ int x,y; scanf("%d%d",&x,&y); printf("%d\n",query(1,x,y)); } } return 0; }
- 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
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
F: 雄伟的城堡
时间：3 s
题目描述： 在一个群岛上，有一个富可敌国的大富翁。他打算在这个群岛上建造一个最大城堡，也就是群岛上最大的岛屿。
输入 ：
第一行是一个整数T，代表测试数据的组数。每组数据中第一行是两个整数n,m，代表地图的大小。接下来n行每行共m个整数。0代表海洋，1代表陆地。其中T<=50,n,m<=200 。
输出：
共T行，最大的面积。
样例输入
1
5 5
0 1 1 0 0
1 1 0 0 0
0 0 1 1 0
0 1 1 1 1
0 0 1 1 0
- 1
- 2
- 3
- 4
- 5
- 6
- 7
样例输出
8
- 1
题解：f
dfs或bfs求最大连通块
#include<bits/stdc++.h> using namespace std; const int maxn=205; int t,n,m,ans,area; int g[maxn][maxn]; bool vis[maxn][maxn]; void dfs(int x,int y){ if(x<1||x>n||y<1||y>m)return ; if(vis[x][y]||!g[x][y])return ; vis[x][y]=true; area++; dfs(x-1,y); dfs(x+1,y); dfs(x,y-1); dfs(x,y+1); } int main(){ scanf("%d",&t); while(t--){ memset(vis,false,sizeof(vis)); memset(g,0,sizeof(g)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&g[i][j]); } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(!vis[i][j]&&g[i][j]){ area=0; dfs(i,j); ans=max(area,ans); } } } printf("%d\n",ans); } return 0; }
- 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
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
G: 然后打5
时间:5s
题目描述：
《炉石传说》是一款考验技(shen)术(chou)的电子游戏，即使你没有玩过这个游戏也没有关系。《炉石传说》里有一张萨满卡牌叫做连环爆裂，它的效果是等概率的造成3-6点伤害。而游戏获胜的条件是将对方英雄的血量全部打掉。例如对方英雄还有5点生命值，你有1张连环爆裂，那么你获胜的概率为0.5。在本题中你无需考虑法力值消耗。
输入
第一行是一个整数T，代表测试数据的组数。接下来的T行每行有2个整数n,h，n代表你一共可以释放的连环爆裂的个数，h代表敌方英雄的血量。其中T<=50,n<=5000,h<=30000。
输出
共T行，每行是一个小数，保留到小数点后6位。
样例输入
1
1 5
- 1
- 2
样例输出
0.500000
- 1
题解
由于是等概率造成伤害，每次打出卡牌造成的伤害p(3)=1/4,p(4)=1/4,p(5)=(1/4),p(6)=1/4;dp[ i ] [ j]表示i张牌时血量为j的答案。对于每次一的(n,h)都等于(n-1,h-3)+(n-1,h-4)+(n-1,h-5)+(n-1,h-6)，递归求解可行，但n达到5000，h达到30000，所以可以使用递推。递推一定要处理好边界。
时间复杂度小于O(t+4 * 3000 * 50000)。
#include<bits/stdc++.h> using namespace std; const int maxn=5000; const int maxh=30000; int t,n,h; double dp[maxn+5][maxh+5]; int main(){ scanf("%d",&t); for(int i=1;i<=maxn;i++){ for(int j=0;j<=3*i&&j<=maxh;j++){ dp[i][j]=1.000000; } } dp[1][4]=0.750000,dp[1][5]=0.5000000,dp[1][6]=0.25000000; for(int i=2;i<=maxn;i++){ for(int j=3*i+1;j<=maxh;j++){ for(int k=3;k<=6;k++){ if(j-k>=0)dp[i][j]+=dp[i-1][j-k]*0.25; } } } while(t--){ scanf("%d%d",&n,&h); printf("%.6lf\n",dp[n][h]); } return 0; }
- 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
- 26
- 27
- 28
- 29
H: 运货卡车
时间：5 s
题目描述：
在一个运输公司中有很多型号完全一样的卡车，每个卡车都可以装载重量为w的货物。有若干个需要运输的货物an，每个货物ai都有一个质量mi。这个运输公司对于这些货物的装载方式策略是，每一次尽可能装更多质量的货物，在有多种可以装载最多质量的货物的方式时，会选择货物下标字典序最小的一组。例如货物的质量为4 3 2 1，卡车能够装载的质量为5时，第一次会选择4 1而不是2 3 。
输入
第一行是一个整数T，代表测试数据的组数。每组样例中，第一行有两个整数n,w，代表有n个货物，每个卡车可以装载质量w的货物。接下来一行有n个数字，代表每个货物的质量。其中T≤20,n,w≤1000。每个货物的质量不会超过w。
输出
共T行，输出所需要的卡车数量。
样例输入
2
4 4
3 3 3 3
4 4
2 2 2 2
- 1
- 2
- 3
- 4
- 5
样例输出
4
2
- 1
- 2
题解：
多重01背包，价值与容量相等，每次计算以后将字典序最小的物品进行标记。
这样时间复杂度最差有O(n3),可能还需要加bitset优化背包。
#include<bits/stdc++.h> using namespace std; const int maxn=1005; const int inf =0x3f3f3f3f; int n,w,t; int dp[maxn][maxn],a[maxn],ans,num; bool vis[maxn]; int main(){ scanf("%d",&t); while(t--){ ans=0,num=0; memset(vis,true,sizeof(vis)); scanf("%d%d",&n,&w); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } while(num<n){ ans++; memset(dp,0,sizeof(dp)); for(int i=n;i>=1;i--){ for(int j=0;j<=w;j++){ dp[i][j]=dp[i+1][j]; if(j>=a[i]&&vis[i]){ dp[i][j]=max(dp[i][j],dp[i+1][j-a[i]]+a[i]); } } } int cur_v=w; for(int i=1;i<=n;i++){ if(i==n&&cur_v>=a[i]&&vis[i]){ vis[i]=false; num++; break; } if(cur_v<=0)break; if(cur_v-a[i]>=0&&dp[i][cur_v]==dp[i+1][cur_v-a[i]]+a[i]&&vis[i]){ vis[i]=false; num++; cur_v=cur_v-a[i]; } } } printf("%d\n",ans); } return 0; }
- 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
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
I: 最大矩形框
时间：5 s
题目描述：
有一个01的大矩阵，找到一个最大由1围城的矩形框的面积。
输入
第一行是一个整数T，代表测试数据的组数。每组样例中，第一行有两个整数n,m，代表有大矩阵的大小，接下来是一个由01组成的大矩阵。其中T<=10,n,m<=200。
输出
最大由1围成的矩形框的面积。
样例输入
1
5 5
0 1 0 1 0
1 1 1 1 0
1 1 0 1 1
1 1 1 1 1
0 1 1 1 1
- 1
- 2
- 3
- 4
- 5
- 6
- 7
样例输出
12
- 1
题解
枚举矩形框的上下界，在从左往右扫描。我们可以用数组sum[i] [j].x存储第i行j列的数前面连续多少1，
sum[i] [j].y上面连续多少个1，计算时直接使用。
#include<bits/stdc++.h> using namespace std; const int maxn=205; struct node{ int x,y; }; int t; int a[maxn][maxn]; node sum[maxn][maxn]; int n,m,ans; int main(){ scanf("%d",&t); while(t--){ ans=0; scanf("%d%d",&n,&m); memset(sum,0,sizeof(struct node)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); if(a[i][j]){ sum[i][j].x=sum[i][j-1].x+1; sum[i][j].y=sum[i-1][j].y+1; } } } for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ for(int k=1;k<=m;k++){ int h,w; h=j-i+1; w=min(sum[i][k].x,sum[j][k].x); if(sum[j][k].y>=h)for(int l=w;l>=1;l--){ if(sum[j][k-l+1].y>=h){ int area=l*h; ans=max(area,ans); break; } } } } } printf("%d\n",ans); } return 0; }
- 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
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
J: 数列分段
时间：3 s
题目描述： 有n个整数，分成m段。使每一段的和的最小值尽可能的大。
输入
第一行是一个整数T，代表测试数据的组数。每组样例中，第一行有两个整数n，m，接下来一行是n个整数。其中T<=50,n,m<1e5 。
输出
尽可能的大的每一段的和的最小值。
样例输入
1
5 3
4 5 4 5 1
- 1
- 2
- 3
样例输出
4
- 1
题解
最小化最大值，二分+贪心。
我们check时对于，sum如果大于等于k立即划分为一段，num++，如果num大于等于m的，说明该k值一定满足。
#include<bits/stdc++.h> using namespace std; int n,m; int a[100005]; int t,r,l,ans; bool check(int k){ int sum=0,num=0; for(int i=1;i<=n;i++){ if(a[i]+sum>=k){ num++; sum=0; }else{ sum+=a[i]; } } if(num>=m)return true; else return false; } int main(){ scanf("%d",&t); while(t--){ r=0,l=0x3f3f3f3f; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); r+=a[i]; l=min(l,a[i]); } while(l<=r){ int mid=(l+r)/2; if(check(mid))ans=mid,l=mid+1; else r=mid-1; } printf("%d\n",ans); } return 0; }
- 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
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
K: 数数字
时间：3 s
题目描述：
Alice和Bob进行一款质数游戏，Alice先说一个质数或者1，Bob再加上一个质数或者1。不能超过目标数字，谁先喊道目标数字就获胜。Alice和Bob都足够聪明，都会采用最优策略。
输入
第一行是一个整数T，代表测试数据的组数。每组样例中，第一行有一个整数n，代表目标数字。
T<=20,n<1e18
输出
共T行，输出Alice win或者Bob win。
样例输入
2
4
6
- 1
- 2
- 3
样例输出
Bob win
Alice win
- 1
- 2
题解
首先，我们需要知道一个定理：一切大于2的质数，一定是形如4n+1或4n-1的数。
由于我们每次给的数可以是1，2，3+（大于2的）质数。那么无论谁先讲，后手的一定可以加成4n。所以说，只要给的数能够被4整除，Bob必胜。反之，Alice必胜。当然你可以找规律，也能写出来。
#include<bits/stdc++.h> using namespace std; typedef long long ll; int t; ll n; int main(){ scanf("%d",&t); while(t--){ cin>>n; if(n%4==0){ printf("Bob win\n"); } else printf("Alice win\n"); } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
