历年题目列表 CSDN
题目大意 • 定义 Sn 的构造方式为:
• 其中 + 表示字符串拼接,next(·) 表示把字符串中每一个字符都换成下一个字符,z 换成 a. • 给定一个长度为偶数且只包含小写字母的字符串S0,按如上方法构造字符串S10100,问这个字符串长为 m 的后缀是什么。
思路 • 考虑当 Sk 长度超过 2m 时,再进行一次操作后,其长度为m 的后缀只会进行 next(·) 变换,把这个长为 m 的后缀的每个字符变成下一个字符。因此考虑暴力将 S0 按构造方式操作,求出一个长度大于 2m 的 Sk,取 Sk 长度为 m 的后缀进行 next(·) 变换即可。
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 <iostream> using namespace std;string next (string s,int t) { for (int i=0 ;i<s.size ();i++) s[i] = ((s[i]-'a' )+t)%26 +'a' ; return s; }string subSum (string s) { int idx = s.size ()/2 ; string res=s.substr (0 ,idx); res += s; res += next (s.substr (idx),1 ); return res; }int main () { int n,m; cin>>n>>m; string s; cin>>s; int cnt = 0 ; while (s.size ()<m*2 ) { cnt ++; s = subSum (s); } s = next (s,((16 -cnt)%26 +26 )%26 ); cout<<s.substr (s.size ()-m)<<endl; return 0 ; }
题目大意 你有 A 个原料,每 B 个合成一个产品。每一次合成你可以选择下列两种 buff 的任意一种: 1 P% 的概率合成双倍产物 2 Q% 的概率返还一个原料求期望最多合成多少产物。
思路 • 设 dp(i) 表示还剩下 i 个原料时的最大期望。根据题意,容易得到如下 dp 方程: dp(i) = max{P × (dp(i − B) + 2) + (1 − P) × (dp(i − B) + 1),Q × (dp(i − B + 1) + 1) + (1 − Q) × (dp(i − B) + 1)} • 注意 B = 1 时需要特判。此时只选择其中一种 buff 是最优的,可以分别算出各自的期望值然后取 max 即可。 • 时间复杂度:O(A)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include <iostream> using namespace std;const int N = 1000010 ;double dp[N];int main () { int a,b; double p,q; cin>>a>>b>>p>>q; p /= 100 ; q /= 100 ; for (int i=b;i<=a;i++) dp[i] = max (p*(dp[i-b]+2 )+(1 -p)*(dp[i-b]+1 ),q*(dp[i-b+1 ]+1 )+(1 -q)*(dp[i-b]+1 )); printf ("%.15f" ,b==1 ?max (a*1.0 /(1 -q),dp[a]):dp[a]); }
题目大意 • 有两个长度为 n, 数值为 0 − 25 的数组 S, T。每次操作可以选择一个正数 k (1 ≤ k ≤ 25), 并选择 S 的一个后缀加 k模 26,问至少几次操作可以令 S = T。
思路 • 设 S0 = T0 = 0, DSi = (Si−Si−1+26) mod 26, DTi = (Ti−Ti−1+26) mod 26(1 ≤ i ≤ n),则 S = T 等价于 DS = DT。每次操作可以将一个 DSi 修改为 0 − 25 的任意数,故统计 DSi ≠ DTi 的数 量即可。时间复杂度 O(n)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include <iostream> #include <math.h> using namespace std;const int N = 200010 ;int f[N];int main () { int n; string s1,s2; cin>>n>>s1>>s2; int last = 0 ,res = 0 ; for (int i=0 ;i<n;i++) f[i] = (s1[i]-s2[i]+26 )%26 ; for (int i=0 ;i<n;i++) { int c = (f[i]-last+26 )%26 ; if (c!=0 ) res ++; last = (last+c)%26 ; } cout<<res<<endl; return 0 ; }
题目大意 • 电梯里有 n 个人(你是其中一个),这些人想去 m 个楼层,每个人只想去一个楼层。到达一个楼层,所有想去这个楼层的人都会下电梯。问在你想去的楼层最多有多少人下电梯。
思路 考虑鸽巢原理,其中人数最多的情况为:在你不想去的楼层每层只下一个人,在你想去的楼层能下的都下。考虑在m − 1 个不想去的楼层每层分配一个人下梯,那么在想去的楼层一起下梯的就有 n − (m − 1) 人。考虑调整法,可以证明这是最多情况。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include <iostream> using namespace std;int main () { int T; cin>>T; while (T--) { int n,m; cin>>n>>m; cout<<n-m+1 <<endl; } return 0 ; }
题目大意 • 给定 n 个串,求两两之间最长公共子串的最大值。
思路 • 直接暴力对 n2 个二元组 (si, sj) 跑最长公共子串即可,或者考虑暴力枚举匹配也可以通过。 • 复杂度 O(T × n4) 或 O(T × n5)
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 #include <iostream> #include <cstring> using namespace std;const int N = 55 ;int dp[N][N];int match (string s1,string s2) { memset (dp,0 ,sizeof dp); int res = 0 ; int n = s1.size (),m = s2.size (); for (int i=1 ;i<=n;i++) for (int j=1 ;j<=m;j++) { if (s1[i-1 ]==s2[j-1 ]) dp[i][j] = dp[i-1 ][j-1 ]+1 ; res = max (dp[i][j],res); } return res; } string f[N];int main () { int T; cin>>T; while (T--) { int n,res = 0 ; cin>>n; for (int i=0 ;i<n;i++) cin>>f[i]; for (int i=0 ;i<n;i++) for (int j=i+1 ;j<n;j++) res = max (match (f[i],f[j]),res); cout<<res<<endl; } return 0 ; }
题目大意 • 构造 n 个不同的长度为 k 的只由小写字符组成的字符串,使得其两两之间最长公共子串的最大值等于 m。
思路 • 首先特判如下情况无解:1 m = 0, n > 26 时无解2 m != 0, m ≥ k 时无解 • 剩下的有解情况可以按如下方式构造: 1 m = 0 时,直接输出长度为 k 的只由第 i 个字母组成的小写字母组成的串即可。 2 m != 0,时,我们考虑构造如下形式的字符串: a1a2a1a2a1a2a1a2 · · · 其中 a1 和 a2 分别表示一种不同的小写字母,且 a1 < a2 < z • 那么对于这种类型的串一共有 25×(25−1)/2= 300 种,两两之间的最长公共子串长度均不超过 1。
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 #include <iostream> #include <cstring> using namespace std; string s1 = "" ,s2 = "" ;string make (int k,char c) { string s = "" ; for (int i=0 ;i<k;i++) s += c; return s; }void print (int len,int n,int m) { if (m==0 ) { string s = make (len,'a' ); for (int i=0 ;i<n+2 ;i++){ cout<<s<<endl; for (int j=0 ;j<len;j++) s[j]++; } } else { string s = make (len,'a' ); for (int j=1 ;j<len;j+=2 ) s[j] = s[j]+1 ; for (int i=0 ;i<800 ;i++) { if (s[1 ]=='z' ) { for (int j=1 ;j<len;j+=2 ) s[j] = s[0 ]+1 ; for (int j=0 ;j<len;j+=2 ) s[j] = s[j]+1 ; } for (int j=1 ;j<len;j+=2 ) s[j] = s[j]+1 ; if (n!=0 && s1!=s && s2!=s) cout<<s<<endl,n--; else if (n==0 ) break ; } } }int main () { int n,m,k; cin>>n>>m>>k; if (m>=k || (n>26 && m==0 )) puts ("No" ); else { puts ("Yes" ); s1 = make (k,'a' ); s2 = s1.substr (0 ,m); for (int i=0 ;i<k-m;i++) s2 += 'b' ; if (m!=0 )cout<<s1<<"\n" <<s2<<"\n" ; print (k,n-2 ,m); } return 0 ; }