A. gcd
题目的意思可以转变为是否存在某个b的质因子不在a的质因子集合中？所以我们通过不断将b / gcd(a,b)，把 b中与 a 公因子的部分剥离掉，最后如果b是1，说明b的所有质因子都来自 a，否则直接输出b
void solve() {
int a,b;
cin >> a >> b;
while(__gcd(a,b) != 1) {
b /= gcd(a,b);
}
if(b == 1) {
cout << -1 << endl;
}
else cout << b << endl;
}
C. Shuffle
给你一个长度为 n 的二进制字符串(即由字符 0 和/或 1 组成的字符串) s 。您最多可以对字符串 s 执行一次以下操作：从 s 中选择一个子串(连续的子序列)，其中包含k个字符 1，然后将其洗牌(按您的意愿重新排列子串中的字符)。
计算从 s 最多进行一次此操作可以得到多少个不同的字符串。
题目是对包含k个1的字串进行重排，既然是重排，我们也可以选择只重排其中一部分，这也是一种重排，所以题目可以这样理解——对包含1的数<=k的子串重排，要保证重排后与原来的字符串不同，所以我们可以强制改变首尾的字符，然后对每个子串用组合数计算数目。我感觉这样更好理解，也可以参考另一个大佬的题解
这题发现用 dp 不好处理，于是考虑怎么处理掉本质不同这个限制，就有了一个很妙的办法，我们只关注最终的序列，并不关注在哪个区间操作了，所以可以枚举值发生变化的第一个位置 i 和最后一个位置 j 。发现对于不同的 i,j ，最终的序列是肯定不相同的，因为 i,j 这两个位置的值是一定改变了的。
现在我们处理好了本质不同这个限制，我们还要满足对于 k∈[i,j],ak 中的 1 的个数不能超过 k ，且全局中 1 的个数要大于等于 k ，这使得这一对 i,j 是合法的。i,j 中间的 01 可以随意填，ai,aj 要强制改变，方案数为 (c0*c0+c1) ，c0 , c1 代表可填的 0,1 的个数 原链接
上面还有复杂度为O(n)的做法，但本题O(n2)也可以过。
int C[N][N],a[N];
int n,k;
string s;
void init() {
C[0][0] = 1;
for(int i = 1; i <= n; i++) {
C[i][0] = 1;
for(int j = 1; j <= i; j++) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
}
}//组合数数组
void solve() {
int ans = 1,sum = 0;
cin >> n >> k >> s;
init();
for(int i = 0; i < sz(s); i++) {
sum += s[i] - '0';
}
if(sum < k) {
cout << 1 << endl;
return;
}//没有等于k的子串
for(int i = 0; i < sz(s); i++) {
int cnt = s[i] - '0';
int n0 = 0,n1 = 0;
if(s[i] == '0') {
n0++;
n1--;
}
else {
n1++;
n0--;
}
for(int j = i + 1; j < sz(s); j++) {
if(s[j] == '1') {
n1++;
cnt++;
}
else n0++;
if(cnt > k) break;
int nn0 = n0,nn1 = n1;
if(s[j] == '1') nn0--;
else nn1--;
if(nn0 >= 0 && nn1 >= 0) {
ans = (ans + C[nn0 + nn1][nn0]) % mod;
}
}
}
cout << ans << endl;
}//复杂度O(n^2)
E. Book
这题有依赖关系我们可以用拓扑排序，然后用一个数组存每章节在哪一遍会被读懂。有向边表示依赖关系，用拓扑排序 + dp[i] 表示第 i 章在哪一轮能被理解。代码如下
const int N = 2e5 + 10;
vector<int> g[N];
int rd[N];
void solve() {
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
g[i].clear();
rd[i] = 0;
}
for(int i = 1; i <= n; i++) {
int k; cin >> k;
for(int j = 0; j < k; j++) {
int x; cin >> x;
g[x].push_back(i);
rd[i]++;
}
}
queue<int> q;
vector<int> dp(n + 1, 1);
for(int i = 1; i <= n; i++) {
if(rd[i] == 0) q.push(i);
}
int cnt = 0;
while(!q.empty()) {
int u = q.front(); q.pop();
cnt++;
for(auto v : g[u]) {
rd[v]--;
if(rd[v] == 0) q.push(v);
if (v > u) dp[v] = max(dp[v], dp[u]);
else dp[v] = max(dp[v], dp[u] + 1);
}
}
if(cnt < n) {
cout << -1 << endl;
} else {
int ans = 0;
for(int i = 1; i <= n; i++) {
ans = max(ans,dp[i]);
}
cout << ans << endl;
}
}
F. easy
你的任务是从矩阵中选择一些数字，以便：
- 从每一行中选出2个数字。
- 从每列中选出2个数字。
您需要确定所选数字的最小和。
实际上怎么选答案都一样，我们把每一个数字的贡献，拆成行标(x – 1) * n加上列标 y。 那么无论怎么选，行标和列标的贡献之和是确定的，直接输出解即可，记得开long long.
void solve() {
int ans = 0;
int n; cin >> n;
if(n % 2 == 0) {
for(int i = 1; i <= n; i += 2) {
for(int j = i; j < i + 2; j++) {
for(int k = i; k < i + 2; k++) {
ans += (j - 1) * n + k;
}
}
}
}
else {
for(int i = 1; i <= n; i++) {
ans += (i - 1) * n + i;
}
for(int i = 1; i < n; i++) {
ans += (i - 1) * n + i + 1;
}
ans += (n - 1) * n + 1;
}
cout << ans << endl;
}
G. student
考虑全局最大值，至少得剩一个删不掉，全局最小值，最少得剩一个删不掉；a1,an 一定删不掉。 所以考虑能否删完其他位置。 假设 mx,mn 都不是a1,an ，那么对于一个数字，如果在 mx,mn 中间，则直接删了，如果在他俩左边或者右边，则可以选他们中的一个，搭上a1/an 来 删 所以最后的答案是2+ [全局最大值都在中间] + [全局最小值都在中间] 。还有千万不要忘记特判n = 1的时候😢
int a[N];
void solve() {
int n;
cin >> n;
if(n == 1) {
cout << 1 << endl;
return;
}
for(int i = 1; i <= n; i++) cin >> a[i];
int mx = *max_element(a + 1, a + 1 + n);
int mn = *min_element(a + 1, a + 1 + n);
bool flag1 = true,flag2 = true;
for (int i = 1; i <= n; i++) {
if(a[i] == mx && (i == 1 || i == n)) flag1 = false;
if(a[i] == mn && (i == 1 || i == n)) flag2 = false;
}
int ans = 2;
if (flag1) ans++;
if (flag2) ans++;
cout << ans << endl;
}
I.And
如果有重复元素直接输出0，因为a[i] & x & x & … = a[i] & x，所以我们只考虑最多&两次，否则直接输出-1
int a[N];
int vis[N],vis1[N];
void solve() {
bool flag = false;
int n,x; cin >> n >> x;
for(int i = 1; i <= n; i++) {
cin >> a[i];
if(vis[a[i]] == 1) {
flag = true;
}
vis[a[i]] = 1;
}
if(flag) {
cout << 0 << endl;
return;
}//如果存在重复元素，输出 0 返回
for(int i = 1; i <= n; i++ ){
int t = a[i] & x;
if(t != a[i] && vis[t] == 1) {
flag = true;
break;
}
}//如果 t != a[i] 且 t 在 vis 中出现过,输出 1 返回
if(flag) {
cout << 1 << endl;
return;
}
for(int i = 1; i <= n; i++) {
int t = a[i] & x;
if(vis1[t] == 1) {
cout << 2 << endl;
return;
}
vis1[t] = 1;
}//如果 t 在 vis1 中出现过,输出 2 返回
if(!flag) {
cout << -1 << endl;
}
J. Swords
每种类型的剑被拿走的数量是x – a[i]，所以可以构成一个数组{ x – a[1], x – a[2], …. ,x – a[n] };因为每个人拿走的剑的数目是相同的，所以这个数组的里的每个数都是z的倍数，它们的最大公因数就是 z，人数 y 就是 他们的和 / z，接下来我们考虑x的取值，因为x – a[i] 一定是大于等于0的，所以x >= a[i]max，要使 y 最小就要让个公因数尽可能的大，所以当我们取x为a[i]max时x – a[i]max = 0,此时这个数列的和也是最小的，若取其他更大数，最大公因数只会更小，甚至为1，并且和也会变大，所以x取a[i]max一定是最优解。代码很简单
int a[N];
void solve() {
int n,mx = 0;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
mx = max(mx,a[i]);
}
int z = 0,sum = 0;
for(int i = 1; i <= n; i++) {
int d = mx - a[i];
z = __gcd(d,z);
sum += d;
}
cout << sum / z << ' ' << z << endl;
}
L. Win
题目就是让你插入k个字符使得lose的字串数最多，没什么难点，别忘了插完了以后，多余的可以直接加上lose
int a[5];
string t,s;
int k;
void solve() {
cin >> k >> s;
bool flag = false;
for(int i = 0; i < sz(s); i++) {
if(flag) {
bool f = false;
char last = t.back();
if(last == 'l') {
if(s[i] == 'o' || s[i] == 's' || s[i] == 'e') {
t += s[i];
f = true;
}
}
else if(last == 'o') {
if(s[i] == 's' || s[i] == 'e') {
t += s[i];
f = true;
}
}
else if(last == 's') {
if(s[i] == 'e') {
t += s[i];
f = true;
}
}
if(!f) {
a[sz(t)]++;
t = "";
flag = false;
}
}
if((s[i] =='l' || s[i] == 'o' || s[i] == 's' || s[i] =='e') && flag ==false){
t += s[i];
flag = true;
}
}
if(sz(t) >= 1) {
a[sz(t)]++;
}
int ans = 0;
for(int i = 4; i >= 1; i--) {
if(k >= a[i] * (4 - i)) {
ans += a[i];
k -= a[i] * (4 - i);
}
else {
ans += min(a[i],k / (4 - i));
k = 0;
break;
}
}
if(k > 0) ans += k / 4;
cout << ans << endl;
}
