大二下课业真的太重了……机器学习课一周要精读4篇论文，掌握每篇论文的数学原理推导……
光是学校的课程就要花去我所有的时间……
现在好不容易挤点时间训练
周二
昨天vp了一场cfdiv2 然而打到一半被叫去做核酸……
算是做了一些水题吧 先找回打代码的感觉
A. Marin and Photoshoot（观察）
观察发现两个0之间必须有两个1
#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);int ans = 0, pre = 0;_for(i, 1, n){int x; scanf("%1d", &x);if(!x){if(!pre) pre = i;else{int cur = i - pre;if(cur == 1) ans += 2;else if(cur == 2) ans++;pre = i;}}}printf("%d\n", ans);}return 0;
}B. Marin and Anti-coprime Permutation（gcd）
考虑奇偶搭配即可
#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;typedef long long ll;
const int mod = 998244353;int main()
{int T; scanf("%d", &T);while(T--){int n; scanf("%d", &n);if(n % 2 == 1) puts("0");else{ll ans = 1;_for(i, 1, n / 2) ans = ans * i % mod;ans = ans * ans % mod;printf("%lld\n", ans);}}return 0;
}C. Shinju and the Lost Permutation（找规律）
这种题无非就是找规律，看满足什么条件
c的值其实就是以第一个数为起点的最长上升子序列。
可以把数据移动一下，把1放到第一个
然后后面的值与前面的值，如果是增加的话，最多加1，减少的话不能减到1
用最长上升子序列的角度很好理解上面两个条件
我当时只是确定了这是必要条件，但是不清楚是不是充分条件
但没管太多，写了一发就AC了
#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 = 1e5 + 10;
int a[N], b[N], n;int main()
{int T; scanf("%d", &T);while(T--){scanf("%d", &n);int pos = 0;_for(i, 1, n) {scanf("%d", &a[i]);if(a[i] == 1) pos = i;}if(!pos) {puts("NO");continue;}int cnt = 0;_for(i, pos, n) b[++cnt] = a[i];_for(i, 1, pos - 1) b[++cnt] = a[i];bool ok = true;_for(i, 2, n)if(b[i] - b[i - 1] > 1 || b[i] < 2) {ok = false;break;}puts(ok ? "YES" : "NO");}return 0;
}D1. 388535(Easy Version) (异或)
这种位运算的题，尤其是涉及到异或的，常规套路都是按照一位一位考虑
果然挺久没做题了 都不敏感了 当时没有怎么意识到 而是尝试去推公式了
按照一位一位来考虑，在某一位下，0的个数小于等于1的个数
如果x的这一位为1，那么0和1全部颠倒，就变成0的个数大于等于1的个数
所以可以通过统计个数来判断x的这一位是否为1
一位一位判断即可
#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 = 2e5 + 10;
int a[N], l, r;int main()
{int T; scanf("%d", &T);while(T--){scanf("%d%d", &l, &r);_for(i, l, r) scanf("%d", &a[i]);int ans = 0;_for(j, 0, 16){int cnt0 = 0, cnt1 = 0;_for(i, l, r){if(a[i] & (1 << j)) cnt1++;else cnt0++;}if(cnt0 < cnt1) ans |= 1 << j;}printf("%d\n", ans); }return 0;
}D1. 388535(Hard Version) (字典树)
这个想法非常妙啊
我当时想题的时候就想枚举每一个可能的x，然后迅速判断它是否是答案。后一步并没有想出来
正解就是这个思路。
首先怎么枚举可能的x呢
l ^ x = ai
x = l ^ ai
所以枚举每一个ai 然后l^ai就一定是可能的x，x一定是其中的一个
那么怎么迅速判断这个x是否是答案呢 这里很妙
[a1……an] ^ x = [l……r]
因为l到r各不相同，所以a1到an各部相同
如果这个等式成立，必然有x与[a1……an]的异或最小值等于l，最大值等于r
又因为[a1……an]各不相同，异或x后也各不相同，所以异或后的结果必然是[l, r]
所以只需要判断异或最小值和最大值就行了，这就是字典树模板题了
#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 = 3e6 + 10;
int trie[N][2], a[N], l, r, cnt;void insert(int x)
{int p = 0;for(int j = 16; j >= 0; j--){int cur = (x >> j) & 1;if(!trie[p][cur]) trie[p][cur] = ++cnt;p = trie[p][cur];}
}int max_xor(int x)
{int res = 0, p = 0;for(int j = 16; j >= 0; j--){int cur = (x >> j) & 1;if(trie[p][cur ^ 1]){p = trie[p][cur ^ 1];res |= 1 << j;}else p = trie[p][cur];}return res;
}int min_xor(int x)
{int res = 0, p = 0;for(int j = 16; j >= 0; j--){int cur = (x >> j) & 1;if(trie[p][cur]) p = trie[p][cur];else{res |= 1 << j;p = trie[p][cur ^ 1];}}return res;
}int main()
{int T; scanf("%d", &T);while(T--){cnt = 0;scanf("%d%d", &l, &r);_for(i, l, r) scanf("%d", &a[i]), insert(a[i]);_for(i, l, r){int x = a[i] ^ l;if(min_xor(x) == l && max_xor(x) == r){printf("%d\n", x);break;}}_for(i, 0, cnt) trie[i][0] = trie[i][1] = 0;}return 0;
}周三
过几天是蓝桥杯省赛，随便挑了几道题做了做
回文日期（模拟）
模拟即可。
用string的substr函数以及stoi函数string转int会很方便
注意闰年判断条件
#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;string s;
int year, month, day;void add()
{day++;int m[20] = {0};_for(i, 1, 12) m[i] = 31;m[4] = m[6] = m[9] = m[11] = 30;if(year % 4 == 0 && year % 100 != 0 || year % 400 == 0) m[2] = 29;else m[2] = 28;if(day == m[month] + 1){month++;day = 1;if(month == 13){month = 1;year++;}}
}string get(int year, int month, int day)
{string a, b, c;a = to_string(year);if(month < 10) b = "0" + to_string(month);else b = to_string(month);if(day < 10) c = "0" + to_string(day);else c = to_string(day);return " " + a + b + c;
}bool check1()
{string s = get(year, month, day);_for(i, 1, 4)if(s[i] != s[8 - i + 1])return false;return true;
}bool check2()
{if(!check1()) return false;string s = get(year, month, day);return s[1] == s[3] && s[2] == s[4];
}int main()
{cin >> s; s = " " + s;year = stoi(s.substr(1, 4));month = stoi(s.substr(5, 2));day = stoi(s.substr(7, 2));int flag = 1;while(1){add();if(flag && check1()){printf("%d%02d%02d\n", year, month, day);flag = 0;}if(check2()){printf("%d%02d%02d\n", year, month, day);break;}}return 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;typedef long long ll;
vector<int> pos[30];
string s;int main()
{cin >> s;int len = s.size();_for(i, 0, 25) pos[i].push_back(-1);rep(i, 0, len) pos[s[i] - 'a'].push_back(i);_for(i, 0, 25) pos[i].push_back(len);ll ans = 0;rep(i, 0, len){int id = s[i] - 'a';int x = lower_bound(pos[id].begin(), pos[id].end(), i) - pos[id].begin();int l = pos[id][x - 1], r = pos[id][x + 1];ans += 1LL * (i - l) * (r - i); }printf("%lld\n", ans);return 0;
}周四
F. Remainder Problem(分块)
这题妙啊，分块
记录ans[x][y] 表示模x余y的答案
每次增加，就更新ans和a数组
分类讨论，如模数大于700，则暴力遍历a数组
否则直接输出ans[x][y]
#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;
int a[N], ans[705][705], q;int main()
{scanf("%d", &q);while(q--){int op, x, y;scanf("%d%d%d", &op, &x, &y);if(op == 1) {a[x] += y;_for(i, 1, 700) ans[i][x % i] += y;}else{if(x <= 700) printf("%d\n", ans[x][y]);else{int res = 0;for(int i = y; i <= 5e5; i += x)res += a[i];printf("%d\n", res);}}}return 0;
}C. Money Transfers（思维）
这道题妙啊
首先，如果存在一个和为0的区间，那么操作可以少一次
那么就尽可能的找多的和为0的区间
和为0意味着前缀和里面有两个相同的数
因此做前缀和，看有多少个相同的数，就意味着有多少个和为0的区间
注意首尾也是一个区间，因为中间和为0，总和为0，得出首尾和也为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;typedef long long ll;
map<ll, int> mp;
int ans, n;int main()
{scanf("%d", &n);ll sum = 0;_for(i, 1, n){int x; scanf("%d", &x);sum += x;ans = max(ans, ++mp[sum]); } printf("%d\n", n - ans);return 0;
}