（更新）西南民族大学第十届校赛（同步赛）
打了11道，果然AK是这辈子也不可能的么QAQ
快速幂。。。
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 }
很麻烦的一道题，我的做法是先把图转成n*m的，然后用二进制记录是否可以通过，再dfs。一开始cin.getline()超时，后来用的gets()。
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 }
C Company
递归，返回下面的值并记录，一开始以为先求深度，后来发现不用。。。
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 }
从任意一个点能搜3个回来就可以。
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 }
E PPY的字符串
模拟，数组要开大一点。
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 }
左边找最大值，右边找最大值。
即使分成两半也让单身狗羡慕至极呢
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 }
G 不想再WA了
DFS赋值写一遍，然后愉快地打表咯。。。
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 }
更新，RealDan拥有把偶数变成奇数的神奇能力，所以只要Ricky一次不能赢，就输了。
当只有一堆且为偶数是为Ricky胜
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 }
I 小A的期末作业
C++语言入门题。。。
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 }
二分，这是伟大玄学的胜利。
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 }
K 正方体
第一遍不知道为什么WA，修改了一下1，3行赋值就对了，图形限定这么严格也是入门题了
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 }
L 简单的分数
直接想到了GCD，也算是个模拟吧。
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 }
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 }
查看45道真题和解析