codeforces round984 div3
A Quintomania
思路：枚举每一个位置
代码：
#include <bits/stdc++.h>
using namespace std;void solve() {int n;cin >> n;vector<int> a(n + 1);for(int i = 1; i <= n; i ++ ) cin >> a[i];bool flag = true;for(int i = 2; i <= n; i ++ ) {if(abs(a[i] - a[i - 1]) != 5 && abs(a[i] - a[i - 1]) != 7) flag = false;}if(!flag) cout << "NO\n";else cout << "YES\n";
}int main() {int t;cin >> t;while(t -- ) solve();return 0;
}B startup
题目：
思路：
将同种商品相加之后，取前n大值相加
#include <bits/stdc++.h>
using namespace std;void solve() {int n, k;cin >> n >> k;map<int, int> ma;priority_queue<int> q;for(int i = 1; i <= k; i ++ ) {int b, c;cin >> b >> c;ma[b] += c;}for(auto t: ma) {q.push(t.second);}int ans = 0;while(!q.empty() && n -- ) {ans += q.top();q.pop();}cout << ans << "\n";
}int main() {int t;cin >> t;while(t -- ) solve();return 0;
}C Anya and 1100
问题：
思路：
考虑每个位置对答案的贡献。对于目标串1100而言，可以看出，如果某个位置上的点已经对答案做出了贡献，那么这个点一定不会做出第二个贡献，即：某一个点要么不会对答案做出贡献，要么只属于一个1100中。在做出修改之前从前向后扫字符串，维护一个cnt表示所有的贡献
那么每次修改，考虑修改前后是否会对cnt产生影响，如果修改位置在修改之前属于1100串的一部分，那么使cnt --若修改后产生了新的1100那么cnt ++。如果cnt > 0输出yes反之输出no
代码：
#include <bits/stdc++.h>
using namespace std;void solve() {string s;cin >> s;s = '#' + s + '#';int n = s.length() - 2;auto check = [&](int idx) {return (s[idx] == '1' && s[min(n + 1, idx + 1)] == '1' && s[min(n + 1, idx + 2)] == '0' && s[min(n + 1, idx + 3)] == '0');};int q;cin >> q;int cnt = 0;for(int i = 1; i <= n - 4 + 1; i ++ ) {if(check(i)) {cnt ++;i += 3;}}
//cout << cnt << " ";while(q -- ) {int i, v;cin >> i >> v;if((v + '0') == s[i]) {if(cnt) cout << "YES\n";else cout << "NO\n";} else {for(int j = max(0, i - 4 + 1); j <= i; j ++ ) {if(check(j)) cnt --;}s[i] ^= 1;for(int j = max(0, i - 4 + 1); j <= i; j ++ ) {if(check(j)) cnt ++;}if(cnt) cout << "YES\n";else cout << "NO\n";}//cout << cnt << " ";}
}int main() {int t;cin >> t;while(t -- ) solve();return 0;
}D I love 1543
问题：
思路：模拟，先把所有的layers放一个一维数组中，再扩展成两倍以解决循环问题
对于一个的矩阵，该矩阵最多有
个layer，首先对这些layer进行遍历(从外向内遍历)，用idx表示每层layer。
对于最上面那一层，满足所有元素属于区间
对于最右边那一层，满足所有元素属于区间
算了看代码吧...
代码：
#include <bits/stdc++.h>
using namespace std;typedef long long ll;void solve() {int n, m;cin >> n >> m;vector<vector<int>> a((n + 1), vector<int>(m + 1));for(int i = 1; i <= n; i ++ ) {for(int j = 1; j <= m; j ++ ) {char c;cin >> c;a[i][j] = c - '0';}}int cnt = 0;int cir = (min(n, m) + 1) / 2;//cout << cir << " ";for(int id = 1; id <= cir; id ++ ) {vector<int> b;for(int i = id; i <= m - id; i ++ ) {b.push_back(a[id][i]);}for(int i = id; i <= n - id; i ++ ) {b.push_back(a[i][m - id + 1]);//cout << i << " " << m - id + 1 << endl;}for(int i = m - id + 1; i >= id + 1; i -- ) {b.push_back(a[n - id + 1][i]);//cout << n - id + 1 <<" " << i<< endl;}for(int i = n - id + 1; i >= id + 1; i -- ) {b.push_back(a[i][id]);//cout << i << " " << id << endl;}int len = b.size();vector<int> c;for(auto t: b) c.push_back(t);for(auto t: b) c.push_back(t);int start;for(start = 0; start < len; start ++ ) {if(b[start] == 1) break;}auto check = [&](int idx) {return ((c[idx] == 1) && (c[idx + 1] == 5) && (c[idx + 2] == 4) && (c[idx + 3] == 3)); };if(start < len) {bool flag = true;for(int i = start; (i % len != start) || flag; i ++ ) {flag = false;if(check(i)) cnt ++;}}}cout << cnt << "\n";
}int main() {int t;cin >> t;while(t -- ) solve();return 0;
}E reverse the rivers
问题：
思路：
首先翻译一下题目，有一个n * k的矩阵，现在对矩阵的每一列进行前缀or操作（就是说操作过后，矩阵的每一列就变成了从上向下的递增序列）然后给你查询，每个查询对矩阵中的数的大小进行限制，问查询到最后是否有一行满足所有的查询
就是一个二分...
代码：
#include <bits/stdc++.h>
using namespace std;typedef long long LL;int main() {LL n, k, q;cin >> n >> k >> q;vector<vector<LL>> a(n + 1, vector<LL>(k + 1));for(int i = 1; i <= n; i ++ ) {for(int j = 1; j <= k; j ++ ) {cin >> a[i][j];}}for(int j = 1; j <= k; j ++ ) {for(int i = 1; i <= n; i ++ ) {a[i][j] |= a[i - 1][j];}}while(q -- ) {int m;cin >> m;int ll = 1, rr = n;bool flag = true;for(int i = 1; i <= m; i ++ ) {LL ri, c;char o;cin >> ri >> o >> c;int l = ll, r = rr;while(l < r) {if(o == '<') {int mid = l + r + 1 >> 1;if(a[mid][ri] < c) l = mid;// > find the first pos that value upper than celse r = mid - 1;} else if(o == '>') {int mid = l + r >> 1;if(a[mid][ri] > c) r = mid;/**/else l = mid + 1;}}//cout << "LL " << l << " LL" << endl;if(o == '<') {if(a[l][ri] < c) {rr = l;} else {flag = false;}} else if(o == '>') {if(a[l][ri] > c) {ll = l;} else {//cout << a[l][ri] << " " << c << endl;flag = false;}}}if(flag) cout << ll << "\n";else cout << "-1\n";}return 0;
}F XORificator 3000
问题：
思路：
翻译一下题目就是求出前x个数的异或和后再去掉某些固定的数
我们可以先封装一个函数表示求出前x个数的异或和，这道题的数据范围很大，考虑这件事情要怎么做
首先列出前10个数的二进制表示
000000000000000000
000000000000000001
000000000000000010
000000000000000011
000000000000000100
000000000000000101
000000000000000110
000000000000000111
000000000000001000
000000000000001001
以列为单位找规律，注意到每一列01的出现都是循环的
从右向左第i位中每个循环节中总是有个数
并且0与1对半分，先0后1，那么只要求出x中包含几个循环节，再求出剩余数的个数，就可以知道每一列中01的数量，实际上，0并不会对xor操作的结果产生影响，因此考虑1的数量为奇数还是偶数...
现在考虑被去掉的数有什么性质 注意到 k < 并且被去掉的数是x以内的
由于k <
并且
的二进制表示是1后跟上i个0，因此这些数中k的二进制表示位一定不会被改变，因此只要求出含有奇数个或偶数个k，奇数则答案 ^k。对于
实际上就是前y个数的异或和再乘上
,让最后答案xor上这个值就好
现在我们可以求出满足题意的xor值，接下来就是简单的前缀xor操作即可求出答案
代码：
#include <bits/stdc++.h>
using namespace std;typedef unsigned long long ll;
ll l, r, I, K;ll qmi(ll a, ll b) {ll res = 1;while(b) {if(b & 1) res *= a;a *= a;b >>= 1;}return res;
}ll get(ll x) {x ++;ll ans = 0;for(int i = 59; i >= 0; i -- ) {ll numOf1 = qmi(2, i);ll cir = 2 * numOf1;ll numOfCir = x / cir;ll last = x % cir;if(last > numOf1) last -= numOf1;else last = 0;ll num = numOf1 * numOfCir + last;ans += (1ull << i) * (num & 1);}return ans;
}void solve() {cin >> l >> r >> I >> K;ll yl = qmi(2, I);ll ansl = get(l - 1);ll numOfK = 1;if(K > l - 1) numOfK = 0;ll tmp = 0;if(l > K + 1) tmp = l - 1 - K;ll allsNum = tmp;ll cir = allsNum / yl;numOfK += cir;if(numOfK & 1) ansl ^= K;ll ansll = get(cir);ansll <<= I;ll ans1 = ansl ^ ansll;ll yr = qmi(2, I);ll ansr = get(r);numOfK = 1;if(K > r) numOfK = 0;tmp = 0;if(r > K) tmp = r - K;allsNum = tmp;cir = allsNum / yr;numOfK += cir;if(numOfK & 1) ansr ^= K;ll ansrr = get(cir);ansrr <<= I;ll ans = ansr ^ ansrr ^ ans1;cout << ans << "\n";
}int main() {int t;cin >> t;while(t -- ) solve();return 0;
}