A Alice and Bob
解题思路
#include<bits/stdc++.h> using namespace std; typedef long long ll; bool d[5005][5005]; void init(){ for(int i=0;i<=5000;i++){ for(int j=0;j<=5000;j++){ if(!d[i][j]){ for(int k=1;k+i<=5000;k++) for(int s=0;s*k+j<=5000;s++) d[i+k][j+s*k]=1; for(int k=1;k+j<=5000;k++) for(int s=0;s*k+i<=5000;s++) d[i+s*k][j+k]=1; } } } } int main(){ init(); int t; cin>>t; while(t--){ int n,m; cin>>n>>m; if(d[n][m]) cout<<"Alice"<<endl; else cout<<"Bob"<<endl; } return 0; }
B.Ball Dropping
题目大意：一个球卡在一个直角等腰梯形内部，求卡着的高度。
根据相似三角形，很容易能求出结果。
#include<bits/stdc++.h> using namespace std; double r, a, b, h; int main() { scanf("%lf%lf%lf%lf",&r,&a,&b,&h); if(a<b) { int c=a; a=b; b=c; } if(r*2.0<=b)cout<<"Drop"<<endl; else { cout<<"Stuck"<<endl; double x=b*h/(a-b); double l=2*r/a*sqrt((a/2)*(a/2)+(h+x)*(h+x)); double ll=l-x; printf("%.10lf\n",ll); } }
D Determine the Photo Position
题目大意：给出一个 n* n 的 01 矩阵，要用一个 1* m 的矩阵去覆盖一段 0，问方案数。
代码：
#include<bits/stdc++.h> using namespace std; int n,m,a[5001][5001]; int ans; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { int num=0; for (int j=1;j<=n;j++) { scanf("%1d",&a[i][j]); if (a[i][j]==0) num++; else num=0; if (num>=m) ans++; } } printf("%d\n",ans); return 0; }
F Find 3-friendly Integers
题目大意：定义一个自然数是 3-friendly 的，如果它存在一个子串(允许前导 00 )是 33 的倍数。多组数据，求 L - R 中的 3-friendly3−friendly 的数的个数。
思路：
如果是三位数及以上，一定是 3-friendly3−friendly 的。求一下一百以内的数。
#include<bits/stdc++.h> using namespace std; long long t,l,r; int a[101]; long long _if(long long x) { if(x<=99)return a[x]; return x-99+a[99]; } int main() { cin>>t; a[0]=1; for(int i=1;i<=9;i++) { a[i]=a[i-1]; if(i%3==0) { a[i]++; } } for(int i=10;i<=99;i++) { a[i]=a[i-1]; if(i%3==0||i/10%3==0||i%10%3==0) { a[i]++; } } while(t--) { cin>>l>>r; cout<<_if(r)-_if(l-1)<<endl; } }
G Game of Swapping Numbers
题目大意：给定序列 A,BA,B ，需要交换恰好 kk 次 AA 中两个不同的数，使得 A,BA,B 每个位置的绝对差值和最大。
思路：
A B两个差的绝对值，相当于赋予两个数符号，我们可以先选出，相应位置的大数和小数，然后排序贪心，比较他们的交换贡献值。
代码：
#include<bits/stdc++.h> using namespace std; int a[500010],b[500010]; long long ans; int main() { int n,k; cin>>n>>k; for(int i=1;i<=n;i++) scanf("%d",&a[i]); if(n==2) { while(k--) { int c=a[1]; a[1]=a[2]; a[2]=c; } } for(int i=1;i<=n;i++) { scanf("%d",&b[i]); if(a[i]>b[i]) { int c=a[i]; a[i]=b[i]; b[i]=c; } ans+=b[i]-a[i]; } sort(a+1,a+1+n); sort(b+1,b+1+n); for(int i=1;i<=k;i++) { if(i>n)break; int t; t=2*(a[n+1-i]-b[i]); if(t>0) ans+=t; else break; } cout<<ans<<endl; }
I Increasing Subsequence
题目大意：给出排列P，两个人轮流取数，每次取的数需要在之前该人取数的右边，且比当前取出来的所有的数都要大。所有当前可选的数都将等概率随机的被当前决策人选中。问两个人期望去数的轮数。
代码：
#include<bits/stdc++.h> using namespace std; long long mod=998244353; double eps=1e-7; long long a[5010],inv[5010]; long long n; long long qsm(long long a,long long n) { long long res=1; while(n) { if(n&1) res=res*a%mod; a=a*a%mod; n/=2; } return res; } long long f[5010][5010]; int main() { cin>>n; for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); } for(int i=1;i<=n;i++) inv[i]=qsm(i,mod-2); for(int j=n;j>=0;j--) { long long cnt=0,sum=0; for(int i=n;i>=0;i--) { if(a[i]>j) { cnt++; sum+=f[j][a[i]]; sum%=mod; } else if(a[i]<j) { f[a[i]][j]=1; if(!cnt)continue; f[a[i]][j]+=sum*inv[cnt]%mod; f[a[i]][j]%=mod; } } } long long res=0; for(int i=1;i<=n;i++) res=(res+f[0][i])%mod; res=res*inv[n]%mod; cout<<res<<endl; return 0; }
