The 3rd Universal CupStage 15: Chengdu, November 2-3, 2024(2024ICPC 成都)

Problem L. Recover Statistics

题目意思：

给定a, b, c三个值，确保构造的数列中包含满足题目的数量

解题思路：

100 中选择a 50个， b45个， c4个。

#include <iostream>using namespace std;using ll = long long;int main(){ios::sync_with_stdio(0);cin.tie(0);int a, b, c;cin >> a >> b >> c;cout << 100 << endl;for(int i = 0; i < 50; i ++)cout << a << " ";for(int i = 0; i < 45; i ++)cout << b << " ";for(int i = 0; i < 4; i ++)cout << c << " "; cout << c + 1;return 0;
}

Problem A. Arrow a Row

题目意思：

n次操作，构造出给定字符串，每次操作可以覆盖之前的操作。

解题思路：

每次把一个字符变为满足题意的字符，n次之内操作就可以完成构造

#include <iostream>
#include <string>
#include <vector>using namespace std;void solve(){string s;cin >> s;int len = s.size();if(len < 5 || s[0] == '-'){cout << "No\n";return ;}for(int i = len - 1; i >= len - 3; i --){if(s[i] == '-'){cout << "No\n";return ;}}int f = 0;for(int i = 0; i < len; i ++){if(s[i] == '-')f = 1;}if(f == 0){cout << "No\n";return ;}vector<pair<int, int>> res;int end = len - 1;for(int i = len - 3; i >= 0; i --){if(s[i] == '>'){res.push_back({1, end + 1});end --;}elsebreak;}end ++;for(int i = 1; i < end - 3; i ++){if(s[i] == '>')res.push_back({i + 1, end - i + 1});}if(res.size() <= len){cout << "Yes ";cout << res.size() << endl;for(auto [x, y] : res)cout << x << " " << y << endl;}elsecout << "No\n"; 
}int main(){ios::sync_with_stdio(0);cin.tie(0);int n;cin >> n;while(n --){solve();}return 0;
}

Problem G. Expanding Array

题目意思：

每次在相邻的两个数之间做运算，再将新构成的数插入到两数之间，再次做一样的运算，可做无限次运算，问最多能构成多少个不同的数。

解题思路：

利用等式 a ^ b = c => b = a ^ c, 通过这条性质可以无线构造出相邻的.

a & ( a ^ b ) ^ a = a & a ^ (a & b ) ^ a = a & b

0 ^ x = x

#include<iostream>
#include<vector>
#include<set>using namespace std;using ll = long long;int main(){ios::sync_with_stdio(0);cin.tie(0);int n;cin >> n;vector<int> a(n);set<int> cnt;for(auto &x : a)    cin >> x;for(int i = 0; i < n - 1; i ++){cnt.insert(a[i]);int t1 = a[i] | a[i + 1];int t2 = a[i] & a[i + 1];int t3 = a[i] ^ a[i + 1];int t4 = t1 ^ a[i];int t5 = t1 ^ a[i + 1];cnt.insert(t1); cnt.insert(t2);cnt.insert(t3);cnt.insert(t4);cnt.insert(t5);}cnt.insert(0);cnt.insert(a[n - 1]);cout << cnt.size() << endl;return 0;
}

Problem B. Athlete Welcome Ceremony

题目意思：

给定一个字符串和a, b, c的数量，问能构成多少种不同的长度为x的序列。

解题思路：

计数dp.

由于题目范围很小，我们很显然可以枚举所有满足cnt个问号，abc的数量，根据题目限制，相邻的两个字符不能相同。状态定义为dp[x][y][z][p]，1 - i 中以p结尾的字符，并且保证当前的和上一层的不重复。我们可以用滚动数组来实现。

对于每次询问，我们直接找出f[x][y][z]即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
#define pb push_back
#define  vi vector<int>
#define  vii vector<pair<int, int>>
#define ff first 
#define ss second 
// ++   ~!    */+-    <<>>    <>  ==   &^|   &&|| =int dp[310][310][310][3]; // ijkz  对前i个字符，使用了j个a字符，k个b字符，第i个字符是 z + 'a'的方案数
int f[310][310][310]; // 有i个a，j个b，k个c的方案数void solve()
{int n, m;cin >> n >> m;string s;cin >> s;s = ' ' + s;vector<int> cnt(n + 1);for (int i = 1; i <= n; i++)cnt[i] = cnt[i - 1] + (s[i] == '?');// 先初始化一下方案数if (s[1] == '?')dp[1][1][0][0] = dp[1][0][1][1] = dp[1][0][0][2] = 1;elsedp[1][0][0][s[1] - 'a'] = 1;for (int i = 2; i <= n; i++){for (int ca = 0; ca <= cnt[i]; ca++){for (int cb = 0; cb + ca <= cnt[i]; cb++){if (s[i] != '?'){int num = dp[i - 1][ca][cb][0] + dp[i - 1][ca][cb][1] + dp[i - 1][ca][cb][2]; //上一层总方案数dp[i][ca][cb][s[i] - 'a'] = (num - dp[i - 1][ca][cb][s[i] - 'a']) % mod; // 去掉上一层一样的,其他结尾字母为0continue;}if (ca){int num = dp[i - 1][ca - 1][cb][1] + dp[i - 1][ca - 1][cb][2]; dp[i][ca][cb][0] = num % mod;}if (cb){int num = dp[i - 1][ca][cb - 1][0] + dp[i - 1][ca][cb - 1][2];dp[i][ca][cb][1] = num % mod;}if (cnt[i] - ca - cb){int num = dp[i - 1][ca][cb][0] + dp[i - 1][ca][cb][1];dp[i][ca][cb][2] = num % mod;}}}}// 先获得特定i j k对应的方案数for(int i = 0; i <= cnt[n]; i ++) for (int j = 0; i + j <= cnt[n]; j++){int num = dp[n][i][j][0] + dp[n][i][j][1] + dp[n][i][j][2];f[i][j][cnt[n] - i - j] = num % mod; }// 获得i j k有富余的情况对应的方案数 三维前缀和for (int i = 0; i <= 300; i++) {for (int j = 0; j <= 300; j++) {for (int k = 0; k <= 300; k++) {if (i > 0) f[i][j][k] += f[i - 1][j][k];if (j > 0) f[i][j][k] += f[i][j - 1][k]; if (k > 0) f[i][j][k] += f[i][j][k - 1]; if (i && j)f[i][j][k] += mod - f[i - 1][j - 1][k];if (k && j)f[i][j][k] += mod - f[i][j - 1][k - 1];if (i && k)f[i][j][k] += mod - f[i - 1][j][k - 1];if (i && j && k)f[i][j][k] += f[i - 1][j - 1][k - 1];f[i][j][k] %= mod;}}}while (m --) {int x, y, z; cin >> x >> y >> z;cout << f[x][y][z] << '\n';}
}signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;//cin >> t;while (t--) solve();return 0;
}
/*   /\_/\
*   (= ._.)
*   / >  \>
*/

Problem I. Good Partitions

题目意思：

给定一个数组，平均分割k段，每一段保证相邻的两个元素不是递增的，求满足条件的k。

同时可以单点修改，再p位置修改为v。

解题思路：

1.满足条件的分割点就是if(a[i] > a[i + 1]）那么i就是分割点。

2.求出分割点的gcd，找出他因子的个数，就是分割方法的总数。

3.为了支持单点修改，每次修改完会有4种结果，并且只会对位置p之后的结果会有影响，我们用线段树来维护即可。

#include<bits/stdc++.h>using namespace std;using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using ull = unsigned long long;struct node{int l, r;ll val;
};
const int N = 2e5 + 10;
int cnt[N];
int gcd(ll a, ll b)
{return b ? gcd(b, a % b) : a;
}class SegmentTree {public:int n;vector<node> c;vector<int> a;
public:SegmentTree (int x){n = x << 2;c.resize(n);a.resize(x + 1);}void build(int k, int l, int r){c[k] = {l, r, 0};if(l != r){int mid = (l + r) / 2;build(k << 1, l, mid);build(k << 1 | 1, mid + 1, r);}}void pushup(int k){c[k].val = gcd(c[k << 1].val, c[k << 1 | 1].val);}void modify(int k, int x, int v){if(c[k].l == c[k].r) c[k].val = v;else{int mid = c[k].l + c[k].r >> 1;if(x <= mid ) modify(k << 1, x, v);else modify(k << 1 | 1, x, v);pushup(k);}}
};void solve(){int n, m;cin >> n >> m;SegmentTree s(n);s.build(1, 1, n);for(int i = 1; i <= n; i ++){cin >> s.a[i];}for (int i = 1; i < n; i++){if (s.a[i] > s.a[i + 1]) s.modify(1, i, i);else s.modify(1, i, 0);}int ans = s.c[1].val;if(ans == 0) cout << n << endl;else cout << cnt[ans] << endl;int p, v;while(m --){cin >> p >> v;s.a[p] = v;if(s.a[p - 1] > s.a[p]) s.modify(1, p - 1, p - 1);else s.modify(1, p - 1, 0);if(p < n){if(s.a[p] > s.a[p + 1]) s.modify(1, p, p);else s.modify(1, p, 0);}int ans = s.c[1].val;if(ans == 0) cout << n << endl;else cout << cnt[ans] << endl;}
}int main(){ios::sync_with_stdio(0);cin.tie(0);for (int i = 1; i <= 200001; i++)for (int j = 1; j * i <= 200001; j++)cnt[i * j] ++;int t = 1;cin >> t;while(t --)solve();return 0;
}