这个也是当年的湖南全国邀请赛

I Elevator

电梯里有 n 个人（你是其中一个），这些人想去 m 个楼层， 每个人只想去一个楼层。到达一个楼层，所有想去这个楼层 的人都会下电梯。问在你想去的楼层最多有多少人下电梯。

vp的时候题目根本没读懂，感觉就是输出 n − (m − 1) ， 交了一发就过了……

J Similarity (Easy Version)

给定 n 个串，求两两之间最长公共子串的最大值。
多测T不超过15，字符串长度不超过50，个数也不超过50。并保证n的总和不会超过300。
直接暴力匹配即可。

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
map<string,int>f;
void solve(){
    int n;
    cin>>n;
 
    per(i,1,n){
        string s;
        cin>>s;
        map<string,bool>vis;
        per(j,0,s.length()-1)
            per(len,1,s.length())
                if(j+len<=s.length())
                    if(!vis[s.substr(j,len)]){
                        vis[s.substr(j,len)]=true;
                        f[s.substr(j,len)]++;
                    }
    }
 
    int ans=0;
    for(auto [x,y]:f){
        if(y>=2){
            ans=max(ans,(int)x.length());
        }
    }
 
    cout<<ans<<endl;
    f.clear();
}

H Neil’s Machine

有两个长度为 n, 数值为 0 − 25 的数组 S, T。每次操作可 以选择一个正数 k (1 ≤ k ≤ 25), 并选择 S 的一个后缀加 k 模 26，问至少几次操作可以令 S = T。
直接贪心因为迟早是要变掉的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int n;
string s1,s2;
int main(){
    cin>>n>>s1>>s2;
    int ti=0,sum=0;
    for (int i=0;i<n;++i){
        ti%=26;
        int x=s1[i]-'a',y=s2[i]-'a';
        x+=ti;
        x%=26;
        if(x==y)continue;
        if(y>x)ti+=y-x,sum++;
        else ti+=(26+y-x),sum++;
    }
    cout<<sum;
    return 0;
}

A Today’s Word

你接受了 VortaroEnMano 公司的聘用，这是一家致力于创建最全面的世界语词典的公司。世界语是一种非常难学的语言，所以你非常努力地工作—主要是为了在就业低迷的情况下保住工作。
今天，你的任务是重构名为 “Hodiaŭa Vorto “的函数，即英文中的 “Today’s Word”。这个单词由一个字符串生成，用 $S_k$ 表示。
下面是 $S_k$ 的生成过程：

  1. 生成过程从给定的初始字符串 $S_0$ 开始。该字符串只包含小写英文字母，长度为偶数。
  2. 对于 $n \ge 1$ ， $S_n$ 的生成方式如下： $S_n=S_{n-1}[0\ldots \frac{l}{2}-1]+S_{n-1}+\text{next}(S_{n-1}[\frac{l}{2}\ldots l-1])$ ，其中 $l$ 是 $S_{n-1}$ 的长度， $+$ 用于连接字符串。注意，字符串的索引从 $0$ 开始。

函数 $\text{next}(S)$ 将字符串 $S$ 中的每个字符递增到字母表中的下一个字母，即 $\texttt{a}$ 变为 $\texttt{b}$ ， $\texttt{b}$ 变为 $\texttt{c}$ ，以此类推， $\texttt{z}$ 变为 $\texttt{a}$ 。例如， $\text{next}(\texttt{abz})=\texttt{bca}$ 。
您的任务是确定长度为 $m$ 的 $S_{10^{100}}$ 的后缀。
10的100次这个数字显然是模拟不了的，很容易就发现长度到达2*m之后是按照26次进行一次循环，所以直接预处理出10的100次幂是多少，得在模26下答案是16，所以加上之前变成长度为2m要用到的次数最多进行16次即可，由于有可能超过16次，不妨取大一些的16的倍数，比如224这个就绝对没有问题。

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
 string next(string s){
    per(i,0,s.length()-1){
        if(s[i]=='z')s[i]='a';
        else s[i]++;
    }
    return s;
}
 
string s;
int used;
 
void solve(){
    int n,m;
    cin>>n>>m;
 
    cin>>s;
    while(s.length()<2*m){//确定了后面m个
        string l=s.substr(0,s.length()/2);
        string r=next(s.substr(s.length()/2));
 
        s=l+s+r;
 
        used++;
    }
 
    s=s.substr(s.length()-m);//后m个,已经变换used次
 
    while(used<224)s=next(s),used++;
 
    cout<<s<<endl;
}

K Similarity (Hard Version)

交给队友自己去写F了结果没调出来，有空补

F Timaeus

蒂迈厄斯是蒙德施塔特的一名初露头角的炼金术士，他的导师阿尔贝多给他布置了一项任务。合成一种特殊的炼金术产品：大甜花。然而，由于他的技能有限，蒂迈厄斯只能通过在一次合成中组合 B 个小甜花来创造一朵大甜花。因此，他得到了两个帮手的帮助：佐藤和莫娜。
佐藤有一种提高生产率的诀窍，在一次合成中有P%可能产生两倍的产量。这意味着通过在单个合成中组合 B 个小甜花来产生两个大的甜花。
另一方面，莫纳有保护资源的诀窍。在该过程中以概率 Q% 取回一朵正常的香花，其意味着通过将 B 规则的香花组合在一起，生产一朵大的香花，同时回收一朵规则的香花单合成。
然而，蒂迈厄斯每次合成只能选择一个助手。从总共 A个常规甜花开始，蒂迈厄斯的目标是最大限度地增加他所能生产的大型甜花的期望数量。
因此，他必须为每个合成在助手佐藤和莫娜之间做出最佳选择。请计算他能生产的大香花的最大预期数量。

一道简单的期望dp。
简化一下题意，其实就是每次选一个助手，助手一有P%的概率在消耗B单位个代价产生的贡献变成2（注意是变成2不是加上2）；助手二可以有Q%的概率在消耗B单位个代价的时候减少1的代价产生1的贡献。
否则就是产生1的贡献。
首先由于每次必须要选一个人作为助手，那么对于这一道题，只有消耗的原料数量是需要保存的状态。
用dp[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));
得到，dp[n]即是答案。
需要注意的是，如果b等于1，那么转移方程就有问题，max中的第二个元素变成了:
Q * (dp[i] + 1) + (1 - Q) * (dp[i - 1] + 1));
由于dp[i]是要求的，这显然是不合法的，那么对这个转移方程移项变形得：
dp[i] = Q * (dp[i] + 1) + (1 - Q) * (dp[i - 1] + 1)); -> dp[i] = dp[i-1] + 1/(1-Q)
如果对第一个式子也进行化简，那么原式可以转化为：
dp[i] = max(dp[i - 1] + P + 1,dp[i-1] + 1/(1-Q));
然后就可以递推了。
实际上观察这个式子可以发现通项是一个过零点的一条直线，那么可以证明最重的答案一定是斜率较大（即max(p+1,1/(1-Q)）的那一条线对应的通项。所以判断一下大小就可以做到O(1)回答。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve() {
	int a, b, p, q;
	cin >> a >> b >> p >> q;
	double P = p / 100.0, Q = q / 100.0;
	if (b == 1) {
		double diff1 = P + 1;
		double diff2 = 1.0 / (1.0 - Q);
//		for (int i = b; i <= a; ++i)
//			dp[i] = max(dp[i - 1] + diff1, dp[i-1]+diff2);
		double maxn = max(diff1, diff2);
		cout << maxn*(a - b + 1.0) << endl;
		return;
	}
	vector<double> dp(a + b + 1, 0);
	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));
	cout << dp[a] << endl;
}

6题全开出来还是有机会银牌的