H 密码是多少？


注意字符串长度都是7
样例1

1
asdfghj
1
10210310410697115100

样例2

1
qazxcdf
1
1209910010211397122

按题意模拟即可

1
2
3
4
5
6
7
void solve() {
	string s;
	cin>>s;
	string t = s.substr(3) + s.substr(0,3);
	for(auto c : t)
		cout<<(int)c;
}

A 送个分吧


样例

1
2
aba
4
1
b

对于给定的样例，前 4 简单的套题分别为：a、ab、aba、b，故答案为 b。
对于 100%的数据，1≤∣_s_∣≤5000,1≤_k_≤5，保证答案存在。

就是在问你字典序第k小的子串
s的范围决定了这道题最多只能是$O(n^2)$的复杂度。
可以这样考虑，比如对于样例而言，前几个子串一定是a开头的，可以是a,ab,aba。那么猜想前面几个一定是字符串中出现的字典序最小的那个字符的某个后缀，比如最小的是a,第二小的是ab(第一个a后面长度为2的后缀),第三小的是aba（第一个a后面长度为3的后缀）。且是长度越小的后缀就一定字典序越小
那么因为出现的字典序最小的那个字符会有很多个，比如样例就是a出现在了第一个和第三个位置。
那么所有以a为开头的后缀有a,ab,aba(第一个a能得到的后缀),a（第二个a得到的后缀），发现有重复的情况。所以可以开set去重。

比如有一个字符串abcaac.先用平方复杂度求出每个位置的后缀:
1:abcaac
2:bcaac
3:caac
4:aac
5:ac
6:c
然后对这些字符串按字典序排序。
4:aac
1:abcaac
5:ac
2:bcaac
6:c
3:caac
那么字典序第1小的子串就是a,第二小的是aa，第三小的是aac……
排序可以用map自动排序，然后找第k小的时候用set去重

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
#include <bits/stdc++.h>

//#define endl '\n'
//#define int long long
//#define N 1003
#define fi first
#define se second
#define si(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define debug cout<<"*******\n";
using namespace std;

typedef pair<int, int> PII;

void solve() {
	string s;
	int k;
	cin>>s>>k;
	map<string,int> mp;
	set<string> st;
	for(int i = 0;i<si(s);++i){
		mp[s.substr(i)] = 1;
	}
	int cnt = 0;
	for(auto [str,v]:mp){
		for(int i = 1;i<=si(str);++i){
			string t = str.substr(0,i);
			if(st.count(t))continue;
			cnt++;
			st.insert(t);
			if(cnt == k) return cout<<t<<endl,void();
		}
	}
}

E 语言学习中


对于 100%100% 的数据，1≤∣S∣,∣T∣≤10^5,1≤q≤10^6.
样例一

1
2
3
4
H
X
1
1 1 1 1
1
NO

样例二

1
2
3
4
5
6
7
XXXHHHHXH
XXXXH
4
7 9 2 5
7 9 1 4
1 7 2 5
1 7 2 4
1
2
3
4
YES
NO
YES
NO

一开始看这范围还以为要什么数据结构。其实就是一个前缀和问题。
因为一个X能变成两个H，不妨将所有的X都变成H最后只要判断区间内有多少个H就行，如果s和t之间H相差的位数能够被3整除，那么就一定是合法的因为题目说了可以在任意的地方删掉三个H。

令sum1[i]表示s的i位之前有多少个H，sum2[i]表示t的i位之前有多少个H，跑一遍前缀和然后判断即可。

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
void solve() {
	string s, t;
	cin >> s >> t;
	vector<int> sum1(100001), sum2(100001);
	for (int i = 1; i <= s.size(); ++i) {
		sum1[i] = sum1[i - 1];
		if (s[i - 1] == 'H')sum1[i]++;
	}
	for (int i = 1; i <= t.size(); ++i) {
		sum2[i] = sum2[i - 1];
		if (t[i - 1] == 'H')sum2[i]++;
	}
	int q;
	cin >> q;
	while (q--) {
		int l1, r1, l2, r2, len1, len2, h1, h2;
		cin >> l1 >> r1 >> l2 >> r2;
		len1 = r1 - l1 + 1, len2 = r2 - l2 + 1;
		h1 = sum1[r1] - sum2[l1 - 1];
		h2 = sum2[r2] - sum2[l2 - 1];
		len1 -= h1, len2 -= h2;
		h1 += len1 * 2;
		h2 += len2 * 2;
		if (abs(h1 - h2) % 3 == 0) cout << "YES" << endl;
		else cout << "NO" << endl;
	}	
}

G 随机汉堡店


样例一

1
2
3
5 5 2
2 2 5 5 2 
2 1 10 9 9 
1
31

样例二

1
2
3
5 5 2
5 1 2 4 4 
7 9 8 5 6 
1
11

对于所有的数据，$2≤p≤n≤10^6,1≤k≤10^6,1≤t_x≤k,1≤d_x≤10^9$。

一个很简单的dp。不知道为啥B题的博弈论要过的人多感觉B难多了。

dp[i]表示当前第i个食材以及前面所有的食材能够达到的最大值。那么第i号点只能由前面的和i号位置的这个食材种类相同的食材转移过来，也就是
$dp[i] = max(dp[i],dp[j-1] + \sum_{k = j}^id[k])$
其中j是在i之前的所有和i种类相同的食材所在的位置，也就是说在位置是j-1的以及所有在j-1前面的位置能达到的最大值加上j-i都作为一个汉堡的食材能达到的最大值，一步一步dp过去即可。
转移方程里面的求和可以用前缀和优化。
需要注意的是题目有个条件是食材数量不能小于p，所以枚举的j要满足i-j+1>=p。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void solve() {
    int n, k, p;
    cin >> n >> k >> p;
    vector<int> t(n+5),d(n+5),dp(n+5),sum(n+5);
    // num记录t[i]的位置
    vector<vector<int>> num(n+5);
    for (int i = 1; i <= n; ++i)
        cin >> t[i],num[t[i]].push_back(i);
    for (int i = 1; i <= n; ++i)
        cin >> d[i],sum[i] = sum[i - 1] + d[i];
    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1];
        for (auto j: num[t[i]]) {
            if (j == i)break;
            int len = i - j + 1;
            if(len<p)continue;
            dp[i] = max(dp[i], dp[j - 1] + sum[i] - sum[j - 1]);
        }
    }
    cout << dp[n];
}

B 客气小孩哥


样例

1
4 8
1
Alice

为什么不好好出题面呢。

比赛一直以为样例里面Alice是哭的那个，后来评论说是Alice没哭……只能说这个题面不好评价

有空再补吧