题解 | #Link with Checksum#
The Game of Eating
https://ac.nowcoder.com/acm/contest/57356/D
嘤嘤菜菜，大佬带带，呜呜。
这场只会三个题，随便写写。是摸鱼的嘤嘤捏，今天代码行数似乎不到三位数呢~~~
D The Game of Eating
心机题！建议不要跟出题人一起吃饭！（除非他请我吃饭）
贪心，博弈。
首先，令 ，也就是最后一个人可以选择的菜的数量。
最后一个人一定会在 个菜中选他最喜欢的菜，那么，倒数第二个人在 个菜中，可以把最后一个人最喜欢的菜留给最后一个人点，然后他点剩下 个菜中最喜欢的菜。那么，倒数第三个人也可以这样做………………
以此类推，最后一个人一定会点到他最喜欢的菜，因为所有人都会把这道菜让给他来点，倒二个人一定会点到其他菜中他最喜欢的菜，因为他前面的人都会把这道菜让给他来点………………
那么，从后往前，每次选择这个人最喜欢的菜，然后去掉这道菜，就是答案。由于一个人对所有菜的喜爱值都不同，所以答案唯一。
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
int T;
cin>>T;
while(T--){
int n,m,k;
cin>>n>>m>>k;
vector a(n+1,vector<int>(m+1));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
vector<int> v;
for(;k>0;k--){
int t = k % n;
if(!t) t = n;
auto j = max_element(a[t].begin(), a[t].end()) - a[t].begin();
v.push_back(j);
for(int i=1;i<=n;i++){
a[i][j] = 0;
}
}
sort(v.begin(),v.end());
for(auto &i : v){
cout<<i<<" ";
}
cout<<endl;
}
}
//30行
G Link with Centrally Symmetric Strings
马拉车、贪心
队友：马拉车！
嘤嘤：让我康康！
板子随便改了改，写了个equal函数，然后贪心一下，再debug半天，就过了。可惜debug慢了点，只拿了个二血，好气哦，东大能不能学学jiangly单挑啊，哼。
要注意，长度为奇数的串中间那个字母必须中心对称，然后如果初始字符串有其他字母，直接寄。之后每次询问区间 到 是否是中心对称， 初始都是1， 每次都加一，然后找到中心对称后， 就变成 ，否则 不变，若最后 大于字符串长度，则yes，否则no。
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
struct Manacher{
string s; //原串
int n; //str的size
string str; //补充后的字符串
vector<int> len; //回文半径
Manacher(string s) : s(s),n(s.size()*2+3){
init(str);
build(len);
}
void init(string &str){
str="$#";
for(auto &i : s){
str+=i;
str+='#';
}
str+='@';
}
void build(vector<int> &len){
// 写12行 + 改3行 = 15行
auto equ = [&](char l,char r){
if(l=='#' && r=='#') return 1;
if(l=='o' || l=='s' || l=='x' || l=='z'){
if(l==r) return 1;
else return 0;
}
if(l>r) swap(l,r);
if(l=='b' && r=='q') return 1;
if(l=='d' && r=='p') return 1;
if(l=='n' && r=='u') return 1;
return 0;
};
len=vector<int>(n,0);
int l=1 , r=1 , p=1;
for(int i=2;i<=n-3;i++){
if(!equ(str[i],str[i])) continue;
if(i>r){
l = r = p = i;
while(equ(str[l-1],str[r+1]))
l--,r++;
len[i] = r - p;
}
else{
len[i] = len[2*p-i];
if(i+len[i]>=r){
p = i;
l = 2 * p - r;
while(equ(str[l-1],str[r+1]))
l--,r++;
len[i] = r - p;
}
}
}
}
};
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T;
cin>>T;
map<int,int> mp;
mp['o']++;
mp['s']++;
mp['x']++;
mp['z']++;
mp['b']++;
mp['q']++;
mp['d']++;
mp['p']++;
mp['n']++;
mp['u']++;
while(T--){
string s;
cin>>s;
Manacher ma(s);
int n = s.size();
int j = 1;
for(auto &i : s){
if(!mp.count(i)){
goto no;
}
}
for(int i=1;i<=n;i++){
int t = i - j + 1;
if(ma.len[i+j]>=t) j = i + 1;
}
if(j>n) cout<<"Yes"<<endl;
else goto no;
if(0) no: cout<<"No"<<endl;
}
return 0;
}
//30（包括mp[]++） + 15 = 45
H 0 and 1 in BIT
线段树
其实可以不用线段树，前缀和乱搞一下就可以了，但是把线段树丢给队友写，就可以不用脑子了呢~~（诶嘿）
观察样例可得，字符串为0011，ABAB操作后不变，分解一下操作，只看ABA，答案是0010，会发现，其实就是原本减一。再试试ABBA，答案是0001，会发现，就是原本减二。而A操作会让字符串取反，那么A的个数已经不重要了，只需要考虑有奇数个还是偶数个A。那么，接下来是化简，以ABBABBBABB为例，转化一下，也就是【-2，+3，-2】，因此，只需要 -1 即可，共有三个A，是奇数，需要将字符串翻转，答案为1101。尝试验证一下，答案正确。
接下来是进位和退位，字符串长度为50，那么long long完全可以存的下，转化成整数后，1111进位时会变成000...10000，只考虑最后四位，答案是正确的。如果是负数，0000退位时，也会变成111....11111（补码），若是不会补码，或者担心出现问题，那么只要加上2的60次方，就可以保证操作永远在正数范围内。（000...001000...001111）
此时，我们只需要查出操作的大小，以及是否要翻转，剩余的就是字符串与数字之间的转换了，难度骤降。
好，本题到此结束。
什么？你说你不会查询？让队友写个线段树不就好了？
什么？队友也不会？那我也不会啊，我也妹写线段树啊，我就写了个大暴力啊~
口胡一下前缀和：维护一个从头到这里的操作次数是多少，再维护一个从头到这里有几个A，然后查询的时候前乱搞一下，再看看符号就好了。
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using LL = long long;
using PII = pair<int, int>;
#define lson (k << 1)
#define rson (k << 1 | 1)
const int N = 3 + 2e5;
struct TreeNode {
int l, r;
int a, b;
} tr[N << 2];
char s[N];
int n, q;
void up(TreeNode &rt, TreeNode l, TreeNode r) {
rt.a = l.a + r.a;
rt.b = l.b;
if (l.a % 2) {
rt.b -= r.b;
} else {
rt.b += r.b;
}
}
void build(int k, int l, int r) {
tr[k].l = l;
tr[k].r = r;
if (l == r) {
if (s[r] == 'A') {
++tr[k].a;
} else {
++tr[k].b;
}
return;
}
int mid = l + r >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
up(tr[k], tr[lson], tr[rson]);
}
TreeNode query(int k, int l, int r) {
// cout << k << ' ' << l << ' ' << r << endl;
if (l <= tr[k].l && tr[k].r <= r) {
return tr[k];
}
int mid = tr[k].l + tr[k].r >> 1;
if (l <= mid && mid < r) {
TreeNode ans;
up(ans, query(lson, l, r), query(rson, l, r));
return ans;
}
if (l <= mid) {
return query(lson, l, r);
} else {
return query(rson, l, r);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
cin >> s + 1;
build(1, 1, n);
LL ans = 0;
while (q--) {
int l, r;
string x;
cin >> l >> r >> x;
int reall = min((ans ^ l) % n + 1, (ans ^ r) % n + 1);
int realr = max((ans ^ l) % n + 1, (ans ^ r) % n + 1);
l = reall;
r = realr;
auto tno = query(1, l, r);
auto a = tno.a;
auto b = tno.b;
ans = 1ll<<60;
int n = x.size();
for(int i=0;i<n;i++){
if(x[i]=='1') ans += 1ll<<(n-i-1);
}
ans += b;
string s;
for(int i=0;i<n;i++){
s += ((ans>>i)&1) + '0';
}
if(a&1){
for(auto &i : s){
i ^= 1;
}
}
ans = 0;
reverse(s.begin(),s.end());
for(auto &i : s){
ans *= 2;
ans += i&1;
}
cout<<s<<endl;
}
return 0;
}
//25行
30+45+25，好像差不多刚好100捏，还生产了一堆废物代码捏~~ 下一场也要继续开摆呢
