前情提要：

本来这场练习赛没有C题，但小沙觉得太简单了，决定加上C题

原本F题放在C题，是一个不怎么需要脑子的题目，但经过小沙加强，来到了F的位置（甚至应该放G才对）

内测时有人认为，A和B的位置需要调整，但被我否决了，因为感觉B有一个要会贪心的前提条件，加上有点阅读理解，所以最终没有选择调整位置（小锅）。

B题好像卡了一些语言的输入输出，非常抱歉QAQ，似乎系统会把py的TLE判定成RE，导致hls寄了好几发，最后改用了C语言。

感觉这场会被骂，如果大家想骂可以直接骂。

A 嘤嘤的签到

​ 枚举

​ 对每一个位置，向左枚举，只要这一段中1和4至少有一个没有出现过，那么这一段是合法子串。

​ 这样向左枚举的复杂度显然是无法通过的，所以需要优化这个枚举，即从左到右枚举时，维护最后一个1和4的位置，每次枚举计算贡献时，最后一个1和4的位置中靠左的那一个往右都是合法的。

​ 例如，041004080，枚举第8个位置时，最后一个1在第3个位置，最后一个4在第6个位置，最左边的位置是3，因此，00408，0408，408，08，8都是合法子串。

​ 代码如下：

#include<bits/stdc++.h>

using namespace std;

using LL = long long;

int main(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	s = " " + s;
	vector<int> a(200);
	LL ans = 0;
	for(int i=1;i<=n;i++){
		a[s[i]] = i;
		ans += i - min(a['1'] , a['4']);
	}
	cout<<ans<<endl;
	return 0;
}

B 嘤嘤的猫娘

​ 贪心、构造。

​ 一种简单的思路是，按价格从大到小的顺序出售嘉心糖，之后每天的出售数量随意，此时，每天买一颗嘉心糖是一种最优的选择，因为提前买嘉心糖一定不会更便宜。

​ 注意保证数量和等于嘉心糖的总数即可。

​ 代码如下：

#include<bits/stdc++.h>

using namespace std;

int main(){
	int n,m;
	cin>>n>>m;
	vector<int> ve(n);
	vector<pair<int,int>> a(n,{0,1});
	for(auto &i : ve) cin>>i;
	sort(begin(ve),end(ve),greater<int>());
	for(int i=0;i<n;i++) a[i].x=ve[i];
	a[n-1].y=m-n+1;
	for(int i=0;i<n;i++) cout<<a[i].x<<" \n"[i+1==n];
	for(int i=0;i<n;i++) cout<<a[i].y<<" \n"[i+1==n];
	return 0;
}

C 嘤嘤的风车

​ 本题是毒瘤沙烬出的！

​ 他说随便画画就行！嗯，就这样！

​ 小沙的代码如下：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    int o = 2 << n;
    vector<string> ans(o * 2 + 1, string(o * 2 + 1, ' '));
    for (int i = 1; i <= n; i++) {
        const int d = 2 << i;
        for (int j = -d; j <= d; j++)
            ans[o + j][o] = '*', ans[o][o + j] = '*';
        for (int j = -d / 2; j <= d / 2; j++)
            ans[o - j][o - j] = '*', ans[o - j][o + j] = '*';
        for (int j = 0; j <= d; j++) {
            if ((j <= d - j) ^ (i % 2))
                ans[o + j][o - d + j] = '*', ans[o - j][o + d - j] = '*';
            if ((j > d - j) ^ (i % 2))
                ans[o + j][o + d - j] = '*', ans[o - j][o - d + j] = '*';
        }
    }
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << "\n";
}

D 嘤嘤的可爱（easy）

​ DP

​ 这题本来是复杂度 $O(n+k\times lo{g}_{2}10^9+7)O(n+k\; \backslash times\; log\_210^9+7)$ 的期望DP，但是内测时大家都不会，所以把复杂度降为了$O(n\times k\times lo{g}_{2}10^9+7)O(n\; \backslash times\; k\; \backslash times\; log\_210^9+7)$ ，但一时间想不到这种复杂度的做法。

​ 这里介绍原本复杂度的做法，新复杂度做法待补充。

​ 设经过 $ii$ 次魔法后，字符串的可爱值的期望为 $dp[i]dp[i]$ ，那么，第一次操作，修改有贡献的字母的概率是 $\frac{dp[i]}{n}\backslash frac\{dp[i]\}\{n\}$ ，修改无贡献的字母的概率是 $\frac{n-dp[i]}{n}\backslash frac\{n-dp[i]\}\{n\}$ ，修改后字母有贡献的概率是 $\frac{5}{26}\backslash frac\{5\}\{26\}$ ，无贡献的概率是 $\frac{21}{26}\backslash frac\{21\}\{26\}$ ，对期望产生改变的只有将有贡献的字母修改为无贡献的字母、将无贡献的字母修改为有贡献的字母，因此dp表达式为：

dp[i] = dp[i-1]
dp[i] -= dp[i-1]/n * 21/26
dp[i] += (n-dp[i-1])/n * 5/26

​ 代码如下：

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

const LL M = 1e9+7;

int main(){
	LL n,k;
	cin>>n>>k;
	string s;
	cin>>s;
    vector<LL> dp(k+1);
    auto ksm = [&](LL x,LL y){
		LL ans = 1;
		while(y){
			if(y&1) ans = ans * x % M;
			x = x * x % M;
			y >>= 1;
		}
		return ans;
	};
    for(auto &i : s){
    	if(i=='y' || i=='k' || i=='a' || i=='w' || i=='i') dp[0]++;
    }
    for(int i=1;i<=k;i++){
        LL sub = (dp[i-1] * ksm(n , M-2) % M) * (21 * ksm(26 , M-2) % M) % M;
        LL add = ((n - dp[i-1] + M) * ksm(n , M-2) % M) * (5 * ksm(26 , M-2) % M) % M;
        dp[i] = (dp[i-1] - sub + add + M)%M;
    }
	cout<<dp[k];
	return 0;
}

E 嘤嘤的可爱（hard）

​ 数学

​ 对于某个位置的字母，计算出被更改的可能性和不被更改的可能性，以及这两种可能性对可爱值的影响。

​ 某一个位置没有被改变过的概率是 $p_0=(\frac{n-1}{n}{)}^{k}p\_0\; =\; (\backslash frac\{n-1\}\{n\})^k$ ，被改变过的概率是 $p_1=1-p_{0}p\_1\; =\; 1\; -\; p\_0$ 。

​ 若一个位置被多次改变，则只有最后一次改变有意义，改变成命运字母的概率是 $t=\frac{5}{26}t\; =\; \backslash frac\{5\}\{26\}$ 。

​ 因此，一个位置如果本来有贡献，那么这个位置有 $p_{0}p\_0$ 的概率不改变，贡献为 $p_{0}p\_0$ ，若一个位置发生了改变，则有 $tt$ 的概率产生贡献，则贡献为 $p1\times tp1\; \backslash times\; t$ 。

​ 复杂度 $O(n)O(n)$ 。

​ 代码如下：

#include<bits/stdc++.h>

using namespace std;

using LL = long long;

const LL M = 1e9+7;

int main(){
	LL n,k;
	cin>>n>>k;
	string s;
	cin>>s;
	auto ksm = [&](LL x,LL y){
		LL ans = 1;
		while(y){
			if(y&1) ans = ans * x % M;
			x = x * x % M;
			y >>= 1;
		}
		return ans;
	};
	LL ans = 0;
	LL p0 = 1 * ksm(n-1 , k) * ksm(ksm(n,k) , M-2) % M;
	LL t = 5 * ksm(26 , M-2) % M;
	LL p1 = (1 - p0 + M) % M;
	for(auto &i : s){
		if(i=='y' || i=='k' || i=='a' || i=='w' || i=='i') ans += p0;
		ans += p1*t;
		ans %= M;
	}
	cout<<ans<<endl;
	return 0;
}

F 嘤嘤的棒子

​ PS:某嘤姓毒瘤不仅在题面说我，还要我临时给他当写题解，太不是人了（PS：明明是你先毒的）。

​ 首先根据题意可得，回文值指变成回文的操作次数。

​ 假设一个串长度为 $nn$ ，他等价于该串第 $ii$ 个字符与第 $n-i+1n-i+1$ 个字符不同的对数。

​ 由于可以修改 $kk$ 种字符，所以修改字符产生的贡献与修改的字符个数无关，与修改字符的位置也无关。

​ 即将其储存为 $30\times 3030\; \backslash times\; 30$ 对二元字符对并计算个数。

​ 对于修改的字符而言，并没有顺序关系，所以仅需要枚举出选择所有命运字符的组合便一定能得到答案。

​ 对于二元字符组而言，仅需要满足一个字符为命运字符，该二元字符组对回味值产生的贡献便会变成 $00$ 。假设没选择的字符集为 $VV$， 为二元字符组产生的贡献，则最终产生的贡献为 。

​ 由于在字符集为 $3030$ 的情况下，使用状压在进行枚举的时候计算次数为$2^{30}2^\{30\}$，而使用DFS的计算次数为$\left(\genfrac{}{}{0px}{}{k}{30}\right)\backslash binom\{k\}\{30\}$，可以发现不管 $kk$ 的取值为多少，其均计算次数均优于状压枚举。（也有可能是你写丑了写的不是$\left(\genfrac{}{}{0px}{}{k}{30}\right)\backslash binom\{k\}\{30\}$了）。

​ 那么，如何在DFS的过程中辅助计算出上述该式便是其难点，当枚举完所以情况后，在使用双重循环进行计算时，其时间复杂度为$\left(\genfrac{}{}{0px}{}{k}{30}\right)\times k^2\backslash binom\{k\}\{30\}\; \backslash times\; k^2$，而可以讲该步骤融入其DFS的过程中，使其在DFS枚举的同时枚举${\sum }_{j\in V}\backslash sum\_\{j\; \backslash in\; V\}$，同时进行计算，其复杂度为$\left(\genfrac{}{}{0px}{}{k}{30}\right)\times k\backslash binom\{k\}\{30\}\; \backslash times\; k$。对于枚举${\sum }_{j\in V}\backslash sum\_\{j\; \backslash in\; V\}$的时候，很容易发现其顺序无关性，且得到的答案仅与 $VV$ 和 枚举的 $jj$ 相关。由于$VV$ 的种类不超过$2^{30}2^\{30\}$个，$jj$ 的个数不超过 $3030$ 个，所以可以采用状压DP的方式将其预处理出来，假设查询一次集合的时间复杂度为 $cc$ ，则此时我们对于DFS过程中的复杂度便转变成$O(\left(\genfrac{}{}{0px}{}{k}{30}\right)\times c)O(\backslash binom\{k\}\{30\}\; \backslash times\; c)$了。

​ 由于$2^{30}\times 302^\{30\}\; \backslash times\; 30$ 在空间以及时间上均无法被接受，所以可以采用折半搜索的方式，将其分成两个状压集合，由于其集合与另一个集合中的元素均不相互影响，所以其合并复杂度为$O(1)O(1)$，查询复杂度也为 $O(1)O(1)$ ，这样对于DFS过程的 $c=1c\; =\; 1$ ，所以其复杂度为$O(\left(\genfrac{}{}{0px}{}{k}{30}\right))O(\backslash binom\{k\}\{30\})$。

​ 所以整体的时间复杂度为$O(2\times 30\times 2^{15}+\left(\genfrac{}{}{0px}{}{k}{30}\right))O(2\; \backslash times\; 30\; \backslash times2^\{15\}\; +\; \backslash binom\{k\}\{30\})$。

​ PS：当然由于一定会将字符划分为两个集合中的一个（选或不选两个集合），所以可以枚举两种情况，第一种为 $aa$ 一定选的集合，第二种为 $aa$ 一定不选的集合，那么会将复杂度凹到$O(2\times 30\times 2^{15}+\left(\genfrac{}{}{0px}{}{k-1}{29}\right))O(2\; \backslash times\; 30\; \backslash times2^\{15\}\; +\; \backslash binom\{k-1\}\{29\})$。当然并不需要这么变态（也可以通过本题。

​ 代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int M = 15;
const int maxn = (1 << M) - 1;
char s[N];
int ans = 1e9, n, k, sum = 0;
int cnt[M * 2][M * 2], sum1[maxn + 1][M * 2], sum2[maxn + 1][M * 2];
int lowit(int x) {
    return x & -x;
}
void dfs(int u, int res, int S, int lim) {
    for (int a = lim; a + u <= M * 2; a++) {
        int cc = res, S1 = S & maxn, S2 = S >> M;
        cc += sum1[S1][a] + sum2[S2][a] - sum1[maxn][a] - sum2[maxn][a];
        if (u == 1)
            ans = min(ans, cc);
        else
            dfs(u - 1, cc, S + (1 << a), a + 1);
    }
}

void dfs(int u, int res, int res2, int S, int lim) {
    for (int a = lim; a + u <= M * 2; a++) {
        int cc = res, dd = res2, S1 = S & maxn, S2 = S >> M;
        cc += sum1[S1][a] + sum2[S2][a] - sum1[maxn][a] - sum2[maxn][a];
        dd += sum1[S1][a] + sum2[S2][a];
        if (u == 1)
            ans = min({ans, cc, dd});
        else
            dfs(u - 1, cc, dd, S + (1 << a), a + 1);
    }
}
int mp[130];
int main() {
    scanf("%d %d", &n, &k);
    scanf("%s", s + 1);
    if (k >= M * 2 - 1) {
        cout << "0\n";
        return 0;
    }
    string str(26, '0');
    iota(str.begin(), str.end(), 'a');
    str += ",.!?";
    for (int i = 0; i < 30; i++) {
        mp[str[i]] = i;
    }
    for (int i = 1, j = n; i < j; i++, j--) {
        if (s[i] != s[j]) {
            int a = mp[s[i]], b = mp[s[j]];
            cnt[a][b] = ++cnt[b][a];
            sum++;
        }
    }
    for (int i = 1; i <= maxn; i++) {
        int x = __lg(lowit(i));
        for (int j = 0; j < M * 2; j++) {
            sum1[i][j] = sum1[i - (1 << x)][j] + cnt[x][j];
        }
    }
    for (int i = 1; i <= maxn; i++) {
        int x = __lg(lowit(i));
        for (int j = 0; j < M * 2; j++) {
            sum2[i][j] = sum2[i - (1 << x)][j] + cnt[x + M][j];
        }
    }
    if (k != M) {
        dfs(k, sum, 0, 0);
    } else {
        dfs(k - 1, sum - sum1[maxn][0] - sum2[maxn][0], 0, 1, 1);
    }
    cout << ans << "\n";
    return 0;
}

G 嘤嘤的闺蜜

​ 根号分治

​ std复杂度是 $O(n\sqrt{n})O(n\; \backslash sqrt\; n)$ ，但比较长，hls写了一份短的代码，并且复杂度相同，也更容易理解。

​ 思路是计算每一种颜色的喜欢值之和，然后暴力统计两种颜色喜欢值的冲突，并记录每对颜色防止重复询问。

​ 首先用哈希表存储每种颜色被哪些闺蜜喜欢，计算冲突时，枚举喜欢的人数少的颜色中的每个人，在另一个颜色中寻找是否冲突（即此人是否同时喜欢两种颜色），若冲突则减去小的喜欢值。

​ 考虑极限数据：令n，m，q相等并都取最大值，至多有根号个颜色被根号个人喜欢，那么这根号个颜色两两组合，正好可以构成n个不同的询问，每一次询问枚举少的颜色，也就是根号个，因此复杂度依然是 $O(n\sqrt{n})O(n\; \backslash sqrt\; n)$ 。若增加每次询问枚举的次数，则会导致不同的询问数量减少，导致复杂度更优。

​ hls代码如下：

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<LL> sum(m + 1);
    vector<unordered_map<int, LL>> mp(m + 1);
    for (int i = 0; i < m; i += 1) {
        int r, c, l;
        cin >> r >> c >> l;
        sum[c] += l;
        mp[c][r] = l;
    }
    map<pair<int, int>, LL> query;
    for (int i = 0; i < q; i += 1) {
        int t;
        cin >> t;
        if (t == 1) {
            int u;
            cin >> u;
            cout << sum[u] << "\n";
        } else {
            int u, v;
            cin >> u >> v;
            if (u == v) {
                cout << sum[u] << "\n";
            } else {
                if (u > v) {
                    swap(u, v);
                }
                if (query.count({u, v})) {
                    cout << query[{u, v}] << "\n";
                } else {
                    LL &res = query[{u, v}];
                    res = sum[u] + sum[v];
                    if (mp[u].size() > mp[v].size()) {
                        swap(u, v);
                    }
                    for (auto [k, x] : mp[u]) {
                        if (mp[v].count(k)) {
                            res -= min(x, mp[v][k]);
                        }
                    }
                    cout << res << "\n";
                }
            }
        }
    }
}