C. C. Blog

Security Research, Algorithm and Data Structure

(更新)西南民族大学第十届校赛(同步赛)

格式坏掉了,可以去

西南民族大学第十届校赛(同步赛)

打了11道,果然AK是这辈子也不可能的么QAQ

A dreamstart的催促

快速幂。。。

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
 1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 #define MOD 10000019
5 #define ll long long
6 ll n,a;
7 ll ANS=0;
8 ll speed(ll a,ll b){
9 ll ans=1,cur=a%MOD;
10 while(b){
11 if(b&1){
12 ans*=cur;
13 ans%=MOD;
14 }
15 cur*=cur;
16 cur%=MOD;
17 b>>=1;
18 }
19 return ans%MOD;
20 }
21 int main(){
22 cin>>n;
23 for(int i=1;i<=n;i++){
24 scanf("%lld",&a);
25 ANS+=speed(a,i);
26 ANS%=MOD;
27 }
28 printf("%lld\n",ANS);
29
30 return 0;
31 }

A

B TRDD got lost again

很麻烦的一道题,我的做法是先把图转成n*m的,然后用二进制记录是否可以通过,再dfs。一开始cin.getline()超时,后来用的gets()。

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
 1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<queue>
5 #include<string>
6 using namespace std;
7 #define MOD 10000019
8 #define ll long long
9 #define MAXN 1000020
10 int a[3004][3004],n,m;
11 char s1[6020],s2[6020],s3[6020];
12 bool k[3004][3004];
13 int f[6][6]={{-1,0},{1,0},{0,1},{0,-1}};//上,下,右,左
14 int sx,sy,ex,ey;
15 struct Point{
16 int x,y,step;
17 };
18 int bfs(){
19 memset(k,true,sizeof(k));
20 queue<Point>q;
21 q.push((Point){sx,sy,1});
22 k[sx][sy]=false;
23 while(!q.empty()){
24 Point cur=q.front();q.pop();
25 if(cur.x==ex&&cur.y==ey) return cur.step;
26 for(int i=0;i<4;i++){
27 int x=cur.x+f[i][0],y=cur.y+f[i][1];
28 if((a[cur.x][cur.y]&(1<<i))&&k[x][y]&&x>=1&&x<=n&&y>=1&&y<=m){
29 q.push((Point){x,y,cur.step+1});
30 k[x][y]=false;
31 }
32 }
33 }
34 return 0;
35 }
36 int main(){
37 scanf("%d%d",&n,&m);
38 getchar();
39 gets(s1);
40 //cout<<s1<<endl;
41 for(int i=1;i<=n;i++){
42 gets(s2);
43 gets(s3);
44 for(int j=1;j<=2*m;j+=2){
45 if(s2[j]=='S'){
46 sx=i;
47 sy=(j+1)/2;
48 }
49 if(s2[j]=='T'){
50 ex=i;
51 ey=(j+1)/2;
52 }
53 int temp=0;
54 if(s1[j]==' ') temp|=1;
55 if(s3[j]==' ') temp|=2;
56 if(s2[j+1]==' ') temp|=4;
57 if(s2[j-1]==' ') temp|=8;
58 a[i][(j+1)/2]=temp;
59 }
60 strcpy(s1,s3);
61 }
62 /*for(int i=1;i<=n;i++){
63 for(int j=1;j<=m;j++){
64 printf("%d ",a[i][j]);
65 }
66 cout<<endl;
67 }*/
68 int ans=bfs();
69 if(!ans){
70 printf("TRDD Got lost...TAT\n");
71 }
72 else{
73 printf("%d\n",ans);
74 }
75 return 0;
76 }

B

C Company

递归,返回下面的值并记录,一开始以为先求深度,后来发现不用。。。

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
 1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 #define MOD 10000019
5 #define ll long long
6 #define MAXN 200020*2
7 int n,k;
8 int pe[MAXN];
9 struct Edge{
10 int u,v,next;
11 }e[MAXN];
12 int g[MAXN];
13 int dep[MAXN],f[MAXN],kk[MAXN];
14 int dfs(int cur,int d){
15 dep[cur]=d;
16 f[cur]=1;
17 int ans=0;
18 for(int i=g[cur];i>0;i=e[i].next){
19 int v=e[i].v;
20 if(!f[v]){
21 ans+=dfs(v,d+1);
22 }
23 }
24 if(pe[cur]<=k) return kk[cur]=ans+1;
25 return kk[cur]=ans;
26 }
27 int main(){
28 scanf("%d%d",&n,&k);
29 for(int i=1;i<=n;i++){
30 scanf("%d",&pe[i]);
31 }
32 int xx,yy;
33 for(int i=1;i<=n-1;i++){
34 scanf("%d%d",&xx,&yy);
35 e[i]=(Edge){xx,yy,g[xx]};g[xx]=i;
36 e[i+n-1]=(Edge){yy,xx,g[yy]};g[yy]=i+n-1;
37 }
38 dfs(1,1);
39 for(int i=1;i<=n;i++){
40 printf("%d ",kk[i]);
41 }
42
43 return 0;
44 }
C

D >A->B->C-

从任意一个点能搜3个回来就可以。

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
 1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 #define MOD 10000019
5 #define ll long long
6 #define MAXN 1000020
7 int n,a[5020],f[5020],k=0;
8 void dfs(int rig,int x,int d){
9 if(d==4){
10 if(rig==x){
11 k=1;
12 }
13 return;
14 }
15 dfs(rig,a[x],d+1);
16 }
17 int main(){
18 cin>>n;
19 for(int i=1;i<=n;i++){
20 scanf("%d",&a[i]);
21 }
22 for(int i=1;i<=n;i++){
23 dfs(i,i,1);
24 if(k==1) break;
25 }
26 if(k==1) printf("YES\n");
27 else{
28 printf("NO\n");
29 }
30 return 0;
31 }

D

E PPY的字符串

模拟,数组要开大一点。

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
     1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 #define MOD 10000019
6 #define ll long long
7 #define MAXN 1000020
8 int a[500000],b[500000],l=0;
9 int n,aa;
10 void fun(){
11 int nl=0,cur=a[1],cnt=0;
12 for(int i=1;i<=l;i++){
13 if(a[i]==cur){
14 cnt++;
15 }
16 if((a[i+1]!=cur&&i<l)||i==l){
17 b[++nl]=cnt;
18 b[++nl]=cur;
19 cnt=0;
20 cur=a[i+1];
21 }
22 }
23
24 l=nl;
25 }
26 int main(){
27 cin>>aa>>n;
28
29 for(int i=1;aa;i++){
30 a[i]=aa%10;
31 aa/=10 ;
32 l++;
33 }
34 for(int i=1;i<=l/2;i++){
35 swap(a[i],a[l-i+1]);
36 }
37 /*for(int i=1;i<=l;i++){
38 printf("%d",a[i]);
39 }*/
40 for(int i=1;i<=n-1;i++){
41 memset(b,0,sizeof(b));
42 fun();
43 for(int j=1;j<=l;j++){
44 a[j]=b[j];
45 }
46 }
47 cout<<l<<' ';
48 for(int i=1;i<=l;i++){
49 printf("%d",a[i]);
50 }
51 cout<<endl;
52 return 0;
53 }```

E

F [集训队脱单大法:这是一道只能由学姐我自己出数据的水题](https://ac.nowcoder.com/acm/contest/322/F)

左边找最大值,右边找最大值。

即使分成两半也让单身狗羡慕至极呢

![](http://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)![](http://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif)


1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 #define MOD 10000019 5 #define ll long long 6 #define MAXN 1000020 7 int n,ans; 8 int a[MAXN]; 9 int lm[MAXN],rm[MAXN]; 10 int abss(int a){ 11 return a>0?a:-a; 12 } 13 int main(){ 14 cin>>n; 15 for(int i=1;i<=n;i++){ 16 scanf("%d",&a[i]); 17 } 18 for(int i=1;i<=n-1;i++){ 19 lm[i]=max(lm[i-1],a[i]); 20 } 21 for(int i=n-1;i>=1;i--){ 22 rm[i]=max(a[i+1],rm[i+1]); 23 } 24 for(int i=1;i<=n-1;i++){ 25 ans=max(ans,abss(lm[i]-rm[i])); 26 } 27 cout<<ans<<endl; 28 return 0; 29 }```

F

G 不想再WA了

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
     1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 #define MOD 10000019
5 #define ll long long
6 #define MAXN 1000020
7 int ANS[20]={0,3,8,21,55,144,377,987,2584,6765,17711};
8 int T,n;
9 int main(){
10 cin>>T;
11 while(T--){
12 cin>>n;
13 printf("%d\n",ANS[n]);
14 }
15 return 0;
16 }```

G

H [Ricky's RealDan's Ricky](https://ac.nowcoder.com/acm/contest/322/H)

更新,RealDan拥有把偶数变成奇数的神奇能力,所以只要Ricky一次不能赢,就输了。

当只有一堆且为偶数是为Ricky胜

![](http://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)![](http://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif)


1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int T,n; 5 int a[100020]; 6 int main(){ 7 cin>>T; 8 while(T--){ 9 scanf("%d",&n); 10 for(int i=1;i<=n;i++){ 11 scanf("%d",&a[i]); 12 } 13 if(n==1&&a[1]%2==0){ 14 cout<<"Ricky is Winner"<<endl; 15 } 16 else{ 17 cout<<"RealDan is Winner"<<endl; 18 } 19 } 20 return 0; 21 }```

H

I 小A的期末作业

C++语言入门题。。。

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
     1 #include<iostream>
2 #include<cstdio>
3 using namespace std;
4 #define MOD 10000019
5 #define ll long long
6 #define MAXN 1000020
7 int n;
8 int main(){
9 cin>>n;
10 for(int i=1;i<=n-1;i++){
11 for(int j=1;j<=i-1;j++){
12 printf(" ");
13 }
14 for(int j=1;j<=n;j++){
15 printf("*");
16 }
17 cout<<endl;
18 }
19 for(int i=1;i<=n-1;i++){
20 printf(" ");
21 }
22 for(int i=1;i<=n;i++){
23 printf("*");
24 }
25 cout<<endl;
26 for(int i=n-1;i>=1;i--){
27 for(int j=1;j<=i-1;j++){
28 printf(" ");
29 }
30 for(int j=1;j<=n;j++){
31 printf("*");
32 }
33 cout<<endl;
34 }
35 return 0;
36 }```

I

J [怪盗基德 & 月之瞳宝石](https://ac.nowcoder.com/acm/contest/322/J)

二分,这是伟大玄学的胜利。

![](http://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)![](http://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif)


1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #include<string> 6 #include<algorithm> 7 using namespace std; 8 #define MOD 10000019 9 #define ll long long 10 #define MAXN 1000020 11 int n,m; 12 int a[100020],b[100020]; 13 bool fun(ll s){ 14 int cur=1; 15 ll xl=b[1]-s,xr=b[1]+s; 16 for(int i=1;i<=n;i++){ 17 if(a[i]<xl){ 18 return false; 19 } 20 if(a[i]>xr){ 21 while(a[i]>xr||a[i]<xl){ 22 cur++; 23 xl=b[cur]-s; 24 xr=b[cur]+s; 25 if(cur>m){ 26 return false; 27 } 28 } 29 } 30 } 31 return true; 32 } 33 int main(){ 34 cin>>n>>m; 35 for(int i=1;i<=n;i++){ 36 scanf("%d",&a[i]); 37 } 38 for(int j=1;j<=m;j++){ 39 scanf("%d",&b[j]); 40 } 41 sort(a+1,a+1+n); 42 sort(b+1,b+1+m); 43 ll l=0,r=4e9+1; 44 while(l<r){ 45 ll mid=(l+r)/2; 46 if(fun(mid)){ 47 r=mid; 48 } 49 else{ 50 l=mid+1; 51 } 52 } 53 printf("%lld\n",l); 54 // printf("%d",fun(4)); 55 return 0; 56 }```

J

K 正方体

第一遍不知道为什么WA,修改了一下1,3行赋值就对了,图形限定这么严格也是入门题了

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
     1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 using namespace std;
5 #define MOD 10000019
6 #define ll long long
7 #define MAXN 1000020
8 ll a[10][10];
9 int T;
10 int main(){
11 cin>>T;
12 for(int i=1;i<=T;i++){
13 memset(a,0,sizeof(a));
14 ll x=0,y=0;
15 for(int j=1;j<=3;j++){
16 for(int k=1;k<=4;k++){
17 scanf("%lld",&a[j][k]);
18 if(j==1&&a[j][k]){
19 x=a[j][k];
20 }
21 if(j==3&&a[j][k]){
22 y=a[j][k];
23 }
24 }
25 }
26 if(x==y&&a[2][1]==a[2][3]&&a[2][2]==a[2][4]){
27 printf("Yes!\n");
28 }
29 else{
30 printf("No!\n");
31 }
32 if(i%50==0)cout<<endl;
33 }
34 return 0;
35 }```

K

L [简单的分数](https://ac.nowcoder.com/acm/contest/322/L)

直接想到了GCD,也算是个模拟吧。

![](http://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)![](http://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif)


1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 #define MOD 10000019 5 #define ll long long 6 #define MAXN 1000020 7 int T,op,a,b,c,d,e,f; 8 int gcd(int a,int b){ 9 return b==0?a:gcd(b,a%b); 10 } 11 int main(){ 12 cin>>T; 13 while(T--){ 14 cin>>op>>a>>b>>c>>d; 15 if(op==1){ 16 e=a*d+b*c; 17 f=b*d; 18 int k=gcd(e,f); 19 e/=k; 20 f/=k; 21 cout<<e<<'/'<<f<<endl; 22 } 23 else{ 24 e=a*d-b*c; 25 f=b*d; 26 int kkkkk=0; 27 if(e<0){ 28 e=-e; 29 kkkkk=1; 30 } 31 int k=gcd(e,f); 32 e/=k; 33 f/=k; 34 if(kkkkk==0) cout<<e<<'/'<<f<<endl; 35 else{ 36 cout<<'-'<<e<<'/'<<f<<endl; 37 } 38 } 39 } 40 return 0; 41 }```

L

M HJ浇花

/*带的树状数组板子发现是坏的->_->

然后从左到右算改了N发还是不对。。。*/

emmmm没有啥树状数组,从左到右扫一遍看成爬山,用一个数组cnt[i]来统计在i位置向上还是向下,对于每组l,r,cnt[l]++,cnt[r+1]--,从0扫到max(r)+1,对于每个cnt[i]不为0的i,用i和上一个cnt不为0的位置和当前层数更新ans数组,然后更新当前层数。

```
 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int n,cnt[1000020],last,now,rmx,ans[1000020]; 
 5 int main(){
 6     cin>>n;
 7     int l,r;
 8     for(int i=1;i<=n;i++){
 9         scanf("%d%d",&l,&r);
10         rmx=max(rmx,r);
11         cnt[l]++;
12         cnt[r+1]--;
13     }
14     for(int i=0;i<=rmx+1;i++){
15         if(cnt[i]!=0){
16             ans[now]+=(i-last);
17             last=i;
18             now+=cnt[i];
19         }
20     } 
21     cout<<ans[1];
22     for(int i=2;i<=n;i++){
23         printf(" %d",ans[i]);
24     }
25     return 0;
26 }```

M

  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/35804/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!