A - T-shirt
题意：
输入四个整数a,b,c,x，已知自己的排名为x，当你排名在a之前一定会获得奖励，在a+1到b名之间有c/(b+1-a）的概率会获得奖励
思路：
看图说话
#include<bits/stdc++.h> using namespace std; int main() { int a,b,c,x; cin>>a>>b>>c>>x; if(x<=a){ cout<<"1.000000000000"<<endl; } else if(x>=a+1&&x<=b){ double d1=0; d1=c*1.0/(b-a); cout<<fixed<<setprecision(13)<<d1<<endl; } else{ cout<<0<<endl; } return 0; }
B - Minimize Ordering
题意：
给你一个字符串，字符串中的字符不变，重新排序，输出最小的字符串。
思路：
sort一下即可
#include<bits/stdc++.h> using namespace std; int main() { string s1; cin>>s1; sort(s1.begin(),s1.end()); cout<<s1<<endl; }
C - 1111gal password
题意：
已知一串数字的长度为n，且这串数字每一位得是1-9，并且相邻的两个数字相差不超过1，求有多少种可能
思路：
裸dp，dp[i][j]表示当前字符串中第i字符为j结尾的数量。
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+1000; const int mod=998244353; long long dp[maxn][10]; int main() { long long n,i,j; cin>>n; for(i=1;i<=9;i++) dp[1][i]=1; for(i=2;i<=n;i++){ for(j=1;j<=9;j++) { dp[i][j]=(dp[i][j]+dp[i-1][j])%mod; if(j>1) dp[i][j]=(dp[i-1][j-1]+(dp[i][j]))%mod; if(j<9) dp[i][j]=(dp[i-1][j+1]+(dp[i][j]))%mod; } } long long ans=0; for(i=1;i<=9;i++) ans=(ans+dp[n][i])%mod; cout<<ans<<endl; return 0; }
D - ABC Transform
题意：
给你一个字符串S，字符串仅有三种字符构成，且会经历t次变化，求变换后第x位的字符串是什么，变化规则是，原串中的A,B,C：A → BC, B → CA, C → AB
思路：
要发现变化t次时的第k位，其实是由t-1次的第k/2位得来的，那么可以递归搜收上去，就有：S(i,k)=S(i-1,k/2),记忆化搜索是可行的，但是k和t都很大，会到1e18，那么要注意观察第一个字符，因为首字母是三个一循环的。那么接下来递归就行了
#include<bits/stdc++.h> using namespace std; string s1; int getc(long long t1,long long k1) { if(t1==0){ return (s1[k1]-'A'); } else if(k1==0){ return (s1[0]-'A'+t1)%3; } else{ return (getc(t1-1,k1/2)+k1%2+1)%3;//如果第k个是奇数是+2,偶数+1 } //比如A-->B(0),C(1) } int main() { int q,n,i,j,t; cin>>s1>>q; for(i=0;i<q;i++){ long long d1,d2; cin>>d1>>d2; cout<<(char)(getc(d1,d2-1)+'A')<<endl; } return 0; }
E - (∀x∀)
题意：
给你一个字符串，求比它字典序小的回文串有多少个
思路：
可以把题目转换成26进制，先看成十进制吧，比如给你一个数字7879，那么比他小的回文数有哪些呢？首先是7887明显凑不成，但是7777,7667这些肯定是能凑成的，所以有77个，那么如果是6567的话，就有65个了，那么同理把原串转换成26进制，再计算即可。
#include<bits/stdc++.h> using namespace std; const long long mod=998244353; int main() { long long n,i,j,t; cin>>t; while(t--) { string s1,s3; cin>>n>>s1; string s2=s1.substr(0,(n+1)/2);//6543 s3=s2; reverse(s3.begin(),s3.end());//6556==>65 if(s1.length()%2==1) //3456 { //3443 s3.erase(s3.begin()); } long long ans=0; for(i=0;i<s2.length();i++) { ans=(ans*26+s2[i]-'A')%mod; } if((s2+s3)<=s1) ans=(ans+1)%mod; cout<<ans<<endl; } return 0; }
