先给出比赛链接：
https://vjudge.net/contest/667035
下面说一下难度分层：(同一难度下按字典序排序,数字为cf难度分)
800: A B E G
1100: D
1200: C
1400: H
1500: F
原题链接
A : https://codeforces.com/contest/1850/problem/A
B : https://codeforces.com/contest/1991/problem/A
C : https://codeforces.com/problemset/problem/1996/C
D : https://codeforces.com/contest/1991/problem/B
E : https://codeforces.com/contest/2008/problem/C
F : https://codeforces.com/contest/1990/problem/C
G : https://codeforces.com/problemset/problem/1598/A
H : https://codeforces.com/contest/679/problem/A
A To My Critics
把最大的两个加起来判断是否大于10即可
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int tt = 1;
cin >> tt;
while (tt--) {
int n = 3;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++ i) cin >> a[i];
sort(a.rbegin(), a.rend() - 1);
if (a[1] + a[2] >= 10) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
}
B Maximize the Last Element
由于每次删的是两个连续的，所以最后剩下的只可能是原数组奇数位上的数，取一下max即可
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int tt = 1;
cin >> tt;
while (tt--) {
int n, ans = 0;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++ i) cin >> a[i];
for (int i = 1; i <= n; ++ i) {
if (i & 1) {
ans = max(ans , a[i]);
}
}
cout << ans << "\n";
}
}
C Sort
观察可得，对于每个区间的查询，答案就是两个字符串每种字符数量的差值之和的一半，前缀和维护一下即可
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
auto prefix = [&](vector<ll> &a , int lena) {
vector<ll> sa(lena + 1);
for (int i = 1; i <= lena; ++ i) {
sa[i] = sa[i - 1] + a[i];
}
return sa;
};
auto get = [&](vector<ll> &sa , int xb , int xe) {
ll res = sa[xe] - sa[xb - 1];
return res;
};
int tt = 1;
cin >> tt;
while (tt--) {
int n, q;
cin >> n >> q;
string s1, s2;
cin >> s1 >> s2;
vector<vector<ll>> a1(27, vector<ll>(n + 1));
vector<vector<ll>> a2(27, vector<ll>(n + 1));
for (int i = 1; i <= n; ++ i) {
int c1 = s1[i - 1] - 'a';
a1[c1][i]++;
int c2 = s2[i - 1] - 'a';
a2[c2][i]++;
}
vector<vector<ll>> sa1(27, vector<ll>(n + 1));
vector<vector<ll>> sa2(27, vector<ll>(n + 1));
for (int i = 0; i < 26; ++ i) {
sa1[i] = prefix(a1[i], n);
sa2[i] = prefix(a2[i], n);
}
while (q--) {
int l , r;
cin >> l >> r;
int d = 0;
for (int i = 0; i < 26; ++ i) {
d += abs(get(sa1[i], l, r) - get(sa2[i], l, r));
}
int ans = d / 2;
cout << ans << "\n";
}
}
}
D AND Reconstruction
这是一题构造，由于 $ b_{i} = a_{i} & a_{i + 1} $, 所以 $ 当b_{i} 的某一位为1时 a_{i} 和 a_{i + 1} 这一位上肯定是1 $
构造完检查一遍是否符合即可
异或及其性质
异或在C++中的运算符是 ^
异或可以理解为按位不进位加法
1.异或的逆运算就是异或本身 如果 a ^ b = c ，那么 c ^ b = a
2.异或满足交换律 即 a ^ b == b ^ a
3.异或满足结合律 即 (a ^ b) ^ c == a ^ (b ^ c)
4.异或满足分配律 即 a ^ (b & c) == (a ^ b) & (a ^ c)
对于普通加法可以用高斯定律 sn = (1 + n) * n / 2 快速计算1~n的值
对于异或运算来说也有快速计算1~n各数的异或和的方法，即：
s(n)为1到n的数的异或和
s(n) = 1 , n % 4 == 1
s(n) = 0 , n % 4 == 3
s(n) = n , n % 4 == 0
s(n) = n + 1 , n % 4 == 2
代码实现如下：
auto xorprefix = [&](ll n) {
int flag = n % 4;
if (flag == 0) {
return n;
} else if (flag == 1) {
return 1;
} else if (flag == 2) {
return n + 1;
} else if (flag == 3) {
return 0;
}
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int tt = 1;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<ll> a(n + 1);
vector<vector<ll>> ab(n + 1 , vector<ll>(32));
vector<ll> b(n + 1);
for (int i = 1; i < n; ++ i) cin >> b[i];
for (int i = 1; i < n; ++ i) {
ll cur = b[i];
int len = 0;
while (cur) {
if (cur % 2 == 1) {
ab[i][len] = 1;
ab[i + 1][len] = 1;
}
cur /= 2;
len++;
}
}
for (int i = 1; i <= n; ++ i) {
ll cur = 0;
for (int j = 30; j >= 0; -- j) {
cur = cur * 2ll + ab[i][j];
}
a[i] = cur;
}
for (int i = 1; i < n; ++ i) {
if ( (a[i] & a[i + 1]) != b[i]) {
flag = 0;
}
}
bool flag = 1;
if (flag) {
for (int i = 1; i <= n; ++ i) {
cout << a[i] << " \n"[i == n];
}
} else {
cout << -1 << "\n";
}
}
}
E Longest Good Array
贪心一下，公差的公差肯定是1，那么先生成这个数组（初始值为0,公差的公差为1），然后计算出区间的长度d，二分找到数组内第一个小于等于d的值即可
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
vector<ll> dp(100005);
for (int i = 2; i <= 100000; ++ i) {
dp[i] = dp[i - 1] + i - 1;
}
int tt = 1;
cin >> tt;
while (tt--) {
ll l, r;
cin >> l >> r;
ll d = r - l;
int pos = (--upper_bound(dp.begin(), dp.end(), d)) - dp.begin(); // 二分查找，返回数组中第一个小于于等于d的位置
cout << pos << "\n";
}
}
F Mad MAD Sum
经过一次运算后，数组变得不递减。
再经过一次运算后，数组变得往后移动。
设 \(a[k]\) 为 \(a\) 数组经过 \(k\) 次操作以后的数组， \(sa[k]\) 为 \(a\) 数组经过 \(k\) 次操作以后的数组的前缀和数组
所以 $ sum = \sum\limits_{k = 0}^{1} \sum\limits_{i = 1}^{n} a[k][i] + \sum\limits_{i = 1}^{n} sa[2][i] $
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
// 一维前缀和
auto prefix = [&](vector<ll> &a , int lena) {
vector<ll> sa(lena + 1);
for (int i = 1; i <= lena; ++ i) {
sa[i] = sa[i - 1] + a[i];
}
return sa;
};
int tt = 1;
cin >> tt;
while (tt--) {
bool flag = 0;
ll n, sum = 0, cur = 0;
cin >> n;
vector<vector<ll>> a(3, vector<ll>(n + 1));
for (int i = 1; i <= n; ++ i) {
cin >> a[0][i];
sum += a[0][i];
}
auto f = [&](int k) {
cur = 0;
map<ll, ll> mp;
for (int i = 1; i <= n; ++ i) {
mp[a[k - 1][i]] ++;
if (mp[a[k - 1][i]] > 1) cur = max(cur , a[k - 1][i]);
a[k][i] = cur;
if (k == 1) sum += a[k][i];
}
};
f(1);
f(2);
vector<ll> sa2 = prefix(a[2], n);
for (int i = 1; i <= n; ++ i) sum += sa2[i];
cout << sum << "\n";
}
}
G Computer Game
这题可以用DP或者dfs解决
设 \(dp[i][j] = 1\) 表示该点能到达，然后先列再行遍历转移状态，最后判断 \(dp[2][n]\) 是否为 \(1\) 即可
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int tt = 1;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<string> s(3);
vector<vector<int>> dp(4, vector<int>(n + 1));
cin >> s[1] >> s[2];
s[1] = " " + s[1];
s[2] = " " + s[2];
dp[1][1] = 1;
for (int j = 1; j <= n; ++ j) {
for (int i = 1; i <= 2; ++ i) {
if (s[i][j] == '0' && (i != 1 || j != 1)) {
if (dp[i - 1][j] == 1) dp[i][j] = 1;
if (dp[i - 1][j - 1] == 1) dp[i][j] = 1;
if (dp[i][j - 1] == 1) dp[i][j] = 1;
if (dp[i + 1][j - 1] == 1) dp[i][j] = 1;
if (dp[i + 1][j] == 1) dp[i][j] = 1;
}
}
}
if (dp[2][n]) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
}
H Bear and Prime 100
如果一个数是合数，那么它要么能被某个素数p整除，要么能被两个不同的素数p和q整除。
要检查第一个条件，检查所有可能的 \(p^{2}\) 即可(4, 9, 25, 49), 如果至少有一个yes,那么隐藏数为合数
如果有两个不同的素因子p和q，那么它们都不超过50，否则隐藏数将大于100（因为对于p≥ 2和q> 50，我们将得到p·q> 100）。所以，检查最多50个素数（有15个），并检查其中是否至少有两个是除数就足够了。
constexpr int maxn = 1e3;
int pnl[maxn + 10], cnt;//pnl
bool st[maxn + 10]; //索引为质数值就是0
void init_primes() {
st[0]=1;
st[1]=1;
for (int i=2; i <= maxn; ++i) {
if (st[i] == 0) { pnl[cnt++] = i; }
for (int j=0; pnl[j] <= maxn / i; ++j){
st[pnl[j]*i] = 1;
if (i%pnl[j] == 0) { break; }
}
}
}
int main() {
init_primes();
int tt = 1;
// cin >> tt;
while (tt--) {
auto query = [&](int cur) {
cout << cur << endl;
cur ++;
string s;
cin >> s;
return s;
};
bool flag1, flag2;
int cnt = 0;
int n = 4;
for (int i = 0; i < 15; ++ i) {
if (query(pnl[i]) == "yes") {
cnt++;
}
}
if (cnt <= 1) {
flag1 = 1;
} else {
flag1 = 0;
}
cnt = 0;
for (int i = 0; i < 4; ++ i) {
if (query(pnl[i] * pnl[i]) == "yes") {
cnt++;
}
}
if (cnt >= 1) {
flag2 = 0;
} else {
flag2 = 1;
}
if (flag1 & flag2) {
cout << "prime\n";
} else {
cout << "composite\n";
}
}
}
标签：ZZJC,新生训练,int,题解,tt,cin,--,vector,cur From： https://www.cnblogs.com/Proaes/p/18508879