最近几周训练量会下降了，因为临近期末，要复习，还有大作业啥的
周一 6.7
昨天打了cf，补一补题
只A了两道，第三道题已经想到正解了，但是犯了一个小错误导致没AC，有点可惜
rank3200，再接再厉吧
A. Omkar and Bad Story
首先可以看出不能有负数
然后我发现0 k 2k 3k这样的等差数列符合题目的条件
于是就可以构造等差数列了
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 110;
int a[N], n;int gcd(int a, int b) { return !b ? a : gcd(b, a %b); }int main()
{int T; scanf("%d", &T);while(T--){scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);sort(a + 1, a + n + 1);if(a[1] < 0){puts("NO");continue;}int g;if(a[1] == 0) g = a[2];else g = a[1];_for(i, 2, n) g = gcd(g, a[i]);int k = a[n] / g + 1;printf("YES\n%d\n", k);_for(i, 0, k - 1) printf("%d ", g * i);puts("");}return 0;
}比赛过后想了想，发现可以直接输出0 1 2……100，这样代码会简洁很多
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;int main()
{int T; scanf("%d", &T);while(T--){int n; scanf("%d", &n);bool ok = true;_for(i, 1, n){int x; scanf("%d", &x);if(x < 0) ok = false;}if(!ok) puts("NO");else{printf("YES\n101\n");_for(i, 0, 100) printf("%d ", i);puts("");}}return 0;
}B. Prinzessin der Verurteilung
这题直接暴力就好，问题是这么写得简洁高效
我比赛时写的比较复杂
看到了rank1的代码，写的非常简洁高效，学习学习
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;void solve()
{int n; string s;cin >> n >> s;vector<string> pre = {""};while(1){vector<string> t;for(auto p: pre){_for(i, 0, 25){string now = p + char('a' + i); //在string中加一个字符直接用加号。注意这里要写chart.push_back(now);if(s.find(now) == string::npos) //string::npos相当于s.end() find函数很方便{cout << now << endl;return;}}}pre = t;}
}int main()
{int T; cin >> T;while(T--) solve();return 0;
}
C. Diluc and Kaeya
比赛时没做出来
关键是一个转化
转化成有多少个前缀是这个比例
也就是说把分成的很多段，求个前缀和，每个前缀和都是这个比例
很秀，还是做题太少，没想到
另外，求gcd时，gcd(a, b)其中一个为0，返回的是另一个。
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 5e5 + 10;
map<pair<int, int>, int> mp;
int n;
char s[N];int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }int main()
{int T; scanf("%d", &T);while(T--){mp.clear();int sd = 0, sk = 0;scanf("%d%s", &n, s + 1);_for(i, 1, n){sd += (s[i] == 'D');sk += (s[i] == 'K');int g = gcd(sd, sk);printf("%d ", ++mp[make_pair(sd / g, sk / g)]);}puts("");}return 0;
}