本次比赛共8题，本文附AC代码和题目链接。
这次先写H题和G题，因为比赛的时候这两题我没写出来…
———————————————————————————————————————————————
H题 nefu 1818 库特的字符串
这题要想清楚字符变换的要求，设第一个字符串为a，第二个字符串为b，我们先列一个表格研究一下字符合成的规律：
| 情况编号 | ① | ② | ③ | ④ |
|---|---|---|---|---|
| a中某个字符 | A | B | A | B |
| b中某个字符 | B | B | A | A |
| 合成后的字符 | A | B | A | A |
| 如果要改变合成后的字符串，只能改变a字符串，如何变换？ | 将a字符串的’A’与其之前没有互相交换过的’B’交换 | 将a字符串的’B’与其之前没有互相交换过的’A’交换 | 无论如何变换a字符串都无法改变合成后的字符 | 无论如何变换a字符串都无法改变合成后的字符 |
我们发现，只有情况1和情况2才有可能改变合成后的字符。
那么可以先同时遍历字符串a和b，如果满足a[i]=='A'&&b[i]=='B'||a[i]=='B'&&b[i]=='B'，则用vis数组标记，
同时统计字符串a中的A字符个数(记为suma)和B字符个数(记为sumb)。
为了避免重复计数，再遍历一次字符串a和b，
用visa记录遍历到i位置之前字符串a中有多少个已经被标记了的A字符，若出现情况①，则需要将a字符串的"A"与其之前没有互相交换过的"B"交换，共sumb-visb种交换方法，更新答案为ans+sumb-visb，
用visb记录遍历到i位置之前字符串a中有多少个已经被标记了的B字符，若出现情况②，则需要将a字符串的"B"与其之前没有互相交换过的"A"交换，共suma-visa种交换方法，更新答案为ans+suma-visa。
想清楚这些，AC就很简单了，以下代码16ms稳过。
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#include <bits/stdc++.h> using namespace std; string a,b; long long ans; int n,suma,sumb,visa,visb,vis[1000010];//vis数组标记满足情况一或者情况二 int main() { ios::sync_with_stdio(false); while(cin>>n) { cin>>a>>b; memset(vis,0,sizeof(vis)); suma=sumb=0; for(int i=0;i<n;i++) { if(a[i]=='A'&&b[i]=='B'||a[i]=='B'&&b[i]=='B')vis[i]=1; if(a[i]=='A')suma++; if(a[i]=='B')sumb++; } visa=visb=ans=0;//visa记录[1,i]被标记的A的个数，visb记录[1,i]被标记的B的个数 for(int i=0;i<n;i++) { if(a[i]=='A'&&vis[i])visa++; if(a[i]=='B'&&vis[i])visb++; if(a[i]=='A'&&b[i]=='B')ans=ans+sumb-visb; if(a[i]=='B'&&b[i]=='B')ans=ans+suma-visa; } printf("%lldn",ans); } return 0; }
G题 nefu 1819 库特分糖果
这题的递归函数很不好写啊，因为递归是一个不易可视化的过程，类似于栈的先进后出，一层一层深入，然后不符合条件时又返回到上一层，返回之前注意清除标记(回溯)，回到上一层又深入到另外的下一层寻找其他的可能性，如果所有节点都已经搜索过了，最终还是返回到了第一层，则说明不存在这样的分配方式，如果搜索到了最后一个人也有了糖果，那么就直接return，一层层返回直到退出第一层。
注意dfs函数中，从第一个人开始，确定他的糖果，如果第一个人到最后都不行，说明无法分配，如果是从第二个人开始的其他人不行，就退回上一个人并把那个人之前分的糖果标记去掉。
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#include <bits/stdc++.h> using namespace std; int n,flag,a[20][20],vis[20],ans[20]; void dfs(int x,int y) { int i; for(i=1;i<=n;i++)//第i列 { if(a[x][i]==1&&vis[i]==0) { ans[x]=i; vis[i]=1; dfs(x+1,i); } }//退出循环时i=n+1 if(ans[n]!=0)return;//最后一个人也有了糖果，结束 if(i==n+1&&x==1){flag=0;return;}//第一次搜索第一行或者回溯搜索到第一行时找不到未被标记的1 if(i==n+1&&x>1){vis[y]=0;return;}//清除标记，回溯 } int main() { while(cin>>n) { memset(ans,0,sizeof(ans));//注意初始化 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j]; flag=1; memset(vis,0,sizeof(vis)); dfs(1,1); if(flag==0){printf("库特大失败！n");continue;} for(int i=1;i<=n;i++) i==n?printf("%dn",ans[i]):printf("%d ",ans[i]); } return 0; }
———————————————————————————————————————————————
剩下的题基本上都是水题了…
———————————————————————————————————————————————
A题 nefu 1822 按钮
1
2
3
4
5
6
7
8
9
10#include <bits/stdc++.h> using namespace std; int main() { int x,y; cin>>x>>y; printf("%dn",max(max(x*2-1,y*2-1),x+y)); return 0; }
B题 nefu 1823 看海
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22#include <bits/stdc++.h> using namespace std; int n,flag,ans,a[110]; int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { flag=0; for(int j=1;j<=i-1;j++) { if(a[j]>a[i]) {flag=1;break;} } if(flag==0)ans++; } printf("%dn",ans); return 0; }
C题 nefu 1824 0-1字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19#include <bits/stdc++.h> using namespace std; int tmp1,tmp2,ans; int main() { string a; cin>>a; for(int i=0;i<a.length();i++) { if(i%2==0&&a[i]!='0')tmp1++; else if(i%2!=0&&a[i]!='1')tmp1++; if(i%2!=0&&a[i]!='0')tmp2++; else if(i%2==0&&a[i]!='1')tmp2++; } ans=min(tmp1,tmp2); printf("%dn",ans); return 0; }
D题 nefu 1825 逃出迷宫
BFS基础题，不多说。
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#include <bits/stdc++.h> using namespace std; int n,m,newx,newy,a[110][110],vis[110][110]; int dir[8][2]={{1,0},{-1,0},{0,-1},{0,1},{1,1},{1,-1},{-1,1},{-1,-1}}; struct node { int x,y,cnt; }; queue<node>q; int main() { cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; q.push({1,1,0}); int flag=0; while(!q.empty()) { node tmp=q.front();q.pop(); if(tmp.x==n&&tmp.y==m){printf("%dn",tmp.cnt);flag=1;break;} vis[tmp.x][tmp.y]=1; for(int i=0;i<8;i++) { newx=tmp.x+dir[i][0]*a[tmp.x][tmp.y]; newy=tmp.y+dir[i][1]*a[tmp.x][tmp.y]; if(newx>=1&&newx<=n&&newy>=1&&newy<=m&&vis[newx][newy]==0) q.push({newx,newy,tmp.cnt+1}); } } if(flag==0)printf("BOMBn"); return 0; }
E题 nefu 1821 库特的飞船
先用素数筛的模板打表素数，之后打表pre数组，pre[i]表示[1,i]区间内的素数和。
如果不先打表pre数组记录区间内素数和就会TLE，注意在询问区间前要先打表。
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#include <bits/stdc++.h> using namespace std; const int N=1e6+10; int l,r,t,tmp,cnt,prime[N],pre[N];//pre数组记录[1,i]区间内的素数和 bool flag[N];//flag标记合数为0，素数为1 void get_prime()//素数筛，打表素数 { memset(flag,1,sizeof(flag)); flag[1]=cnt=0; for(int i=2;i<=N;i++) { prime[++cnt]=i; for(int j=1;j<=cnt&&prime[j]*i<=N;j++) { flag[prime[j]*i]=0; if(i%prime[j]==0)break; } } } void get_pre()//打表pre数组 { for(int i=1;i<=N;i++) { if(flag[i])tmp=tmp+i%2; pre[i]=tmp; } } int main() { get_prime();get_pre(); ios::sync_with_stdio(false); cin>>t; while(t--) { cin>>l>>r; printf("%dn",pre[r]-pre[l-1]); } return 0; }
F题 nefu 1820 库特大危机
这题注意分类讨论。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22#include <bits/stdc++.h> using namespace std; int t,x,y,z,tmp,ans; int main() { cin>>t; while(t--) { cin>>x>>y>>z; if(x>=z) {printf("1n");continue;} if(x<=y&&x<z){printf("库特大危机！n");continue;} if(x>y&&x<z) { tmp=z-x; if(tmp%(x-y)==0)ans=tmp/(x-y)+1; else ans=tmp/(x-y)+2; printf("%dn",ans); } } return 0; }
最后
以上就是丰富小甜瓜最近收集整理的关于大一省赛选拔赛（2019.4.20）的全部内容，更多相关大一省赛选拔赛（2019内容请搜索靠谱客的其他文章。
发表评论 取消回复