Educational Codeforces Round 177 (Rated for Div. 2)

A. Cloudberry Jam

思路：

1千克果子能生產2/3千克果醬，生產3千克果醬則需要2千克果醬，所以*2即可

code:

void solve() {   int x; cin >> x;cout << 2 * x << endl;
} 

B. Large Array and Segments

題意：

當前給出一個長度為n的數組a，數組b為數組a頭尾相接k次而成，長度為n*k，現在求b數組中存在多少個左邊界l，存在一個右邊界r，使得l到r區間的元素和大于等于x

思路：

將數組b視為k段a，求出a數組的前綴和和sum，然后判斷出在第幾段時，會開始出現大于等于x的后綴即可，注意最多k段；

Code:

void solve() {int n, k,  x; cin >> n >> k >> x;vector<int> a(n), sum(n+1, 0);for(int i = 0;i < n;i ++){cin >> a[i];sum[i+1]=sum[i]+a[i];}int s = sum[n], ans = 0;for(int i = 0;i < n;i ++){int ca  = s - sum[i];int ttt;if (ca >= x) {ttt = 0;} else {ttt = (x - ca + s - 1) / s;}if (k <= ttt) continue;ans += (k - ttt);}cout << ans << endl;
}

C. Disappearing Permutation

題意：

當前有一個長度為n的排列p，以及一個操作序列d，第i次操作會使得$p_{d_i}=0$；

在第i次操作后，需要最少多少次操作可以使得數組恢復成一個任意順序的排列，操作如下：

• 將第i個位置的數替換為i

思路：

若$p_i!=i$ ，我們需要進行向上回溯類似并查集的方式尋找i的位置，回溯過程中的元素都需要進行單獨的操作

首先記錄每個元素所需要向上回溯的次數，即操作次數，回溯最終的位置即為祖宗結點

最后從第一個位置開始遞增操作次數即可

Code：

void solve() {int n; cin >> n;for (int i = 1; i <= n; i ++) cin >> p[i];for (int i = 1; i <= n; i ++) cin >> d[i];vector<int> pos(n + 1, 0), find(n + 1, 0), sum(n + 1, 0);int now = 0;for (int i = 1; i <= n; i ++) {if (pos[i]) continue;now ++;int idx = i;while (pos[idx] == 0) {pos[idx] = 1;find[idx] = now;idx = p[idx];}int cnt = 0, st = i;idx = i;idx = p[idx];cnt ++;while (idx != st) {cnt ++;idx = p[idx];}sum[now] = cnt;}vector<int> ans;for (int i = 1; i <= n; i ++) pos[i] = 0;int ca = 0;for (int i = 1; i <= n; i ++) {int t = d[i];int id = find[t];if (!pos[id]) {ca += sum[id];pos[id] = 1;}cout << ca << ' ';} cout << endl;
}

D. Even String

題意：

給出26個字母的每個字母的數量，需要按照要求進行字符串的構造：

相同字符串直接的間隔必須是偶數

有多少種構造方案

思路：

思路原鏈接：https://zhuanlan.zhihu.com/p/1891280211527590056

首先明確一個多重排列數的計算公式，即n個序列中有ci個重復的數有多少種排列的方式：
$$\frac{n!}{c_1!?c_2!?c_k!}$$
而n!需要跟每個ci!進行逆元操作

就本題來說，同一字母只能全部放在奇數位或者偶數位

特判：顯然，如果一個字母的數量單獨在奇數位或者偶數位都不能容納，則不可能完成

這里用一個背包來預處理一下字符的分組問題：

• 我們需要將字母分成兩組，奇數組和偶數組
• 分配其中一個就可以，這里以奇數位為例，從后向前進行一個狀態轉移

然后就是每組的排列組合的問題：

• 奇數位有odd個字符，那么就有odd!種排列方式，偶數同理
• 代入多重排列的公式即可 $n!=odd!?even!$

最后將排列數*分組數即為最終答案
(被創思了。。。。。。)

AC code:

int fact[N], invfact[N];int qmi(int a, int k, int p) {int res = 1;while (k) {if (k & 1) res = res * a % p;a = a * a % p;k >>= 1;}return res;
} //多重排列數預處理，階乘+逆元
void init_fact(int n) {fact[0] = invfact[0] = 1;for (int i = 1; i <= n; i ++) fact[i] = fact[i - 1] * i % MOD;invfact[n] = qmi(fact[n], MOD - 2, MOD);for (int i = n - 1; i >= 1; i --) invfact[i] = invfact[i + 1] * (i + 1) % MOD;
}void solve() {vector<int> c(26);int sum = 0;for (int i = 0; i < 26; i ++) {cin >> c[i];sum += c[i];}int odd = (sum + 1) / 2, even = sum / 2;for (int i = 0; i < 26; i ++) {if (c[i] > odd && c[i] > even) {cout << 0 << endl;return;}}vector<int> dp(odd + 1, 0);dp[0] = 1;for (int i = 0; i < 26; i ++) {if (c[i] == 0) continue;for (int j = odd; j >= c[i]; j --) {dp[j] = (dp[j] + dp[j - c[i]]) % MOD;}}int ans = dp[odd];int ca = 1;for (int i = 0; i < 26; i ++) {ca = ca * invfact[c[i]] % MOD;}ans = ((ans * fact[odd] % MOD) * fact[even] % MOD) * ca % MOD;cout << ans << endl;
}