本场a,b,c秒的较快，a2mins，b11mins，c8mins。b题在实现过程中有些偏慢，c题wa了一发，差点写出了一个hack点，如果是现场打可能会被fst。d题想错了一个地方，认为题读错了卡了40mins，e题20mins写完，f题场后看题解会，最后10mins理解了d题，写出了一个bug场后才发现。
总结：
- 卡题应当考虑换题。
- 简单题先在脑中想好如何去写，再动手。
- 分类讨论要模拟
题解：
A.
题意：给了1000个数，按顺序变换先数组中向1变为2，再将新数组2变为1，3变4，4变3…
思路：把偶数-1即可。
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int main(){
//IO;
int n;cin>>n;
vector<int>a(n);
forn(i,n){
cin>>a[i];
if(a[i]%2==0) a[i]--;
}
forn(i,n) cout<<a[i]<<' ';
return 0;
}
B.
题意：n个数，一个k，将其分为k个段，使得每一段的最大值累加和最大。
思路：排序找位置，构造，输出。
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 2005;
bool vis[maxn];
int main(){
//IO;
int n,k;cin>>n>>k;vector<pair<int,int> >a(n);
vector<int>b(n);
forn(i,n){
cin>>a[i].first;
b[i] = a[i].first;
a[i].second = i;
}
sort(a.begin(),a.end());
forn(i,k){
vis[a.back().second] = 1;
a.pop_back();
}
vector<int>ans;
int cnt = 0,kk = k;
ll sum = 0;
forn(i,n){
cnt++;
if(vis[i]){
k--;
sum+=b[i];
if(k) ans.push_back(cnt);
else ans.push_back(cnt+n-1-i);
cnt = 0;
}
}
cout << sum<<'
';
for(auto x:ans){
cout <<x<<' ';
}
return 0;
}
C.
题意：给n个数（1e5)，分成3段，使得第一段和最后一段sum相等且最大。
思路：双指针
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int main(){
//IO;
int n;cin>>n;
vector<int>a(n);
forn(i,n) cin>>a[i];
int l = 0,r = n-1;
ll sum1 = 0,sum2 = 0,ans = 0;
while(l<=r){
if(r!=l&&sum1==sum2)sum1+=a[l++],sum2+=a[r--];
else if(sum1<sum2) sum1+=a[l++];
else sum2+=a[r--];
if(sum1==sum2) ans = sum1;
}
cout << ans <<'
';
return 0;
}
D.
题意：给两个字符串s,t。可以任意调换si sn-i-1,ti tn-i-1,si ti。问最少更换s中几个字符后，使得任意次数调换后s==t
思路：分类讨论
四种字符+=2；
三种字符如果s串两位置相同+=2，此外+=1；
两种字符如果是3：1这样+=1，此外+=0
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
string s,t;int n;
int judge(int pos){
int a = pos,b = n-pos-1,cnt = 2;
map<int,int>mp;
mp[s[a]-'a']++,mp[s[b]-'a']++,mp[t[a]-'a']++,mp[t[b]-'a']++;
if(mp.size()==4) cnt = 2;
else if(mp.size()==3){
if(s[a]==s[b])cnt=2;
else cnt=1;
}else if(mp.size()==2){
if(mp.begin()->second==1||mp.begin()->second==3)cnt = 1;
else cnt = 0;
}else cnt = 0;
return cnt;
}
int main(){
IO;
cin>>n;
cin>>s>>t;
int x = n>>1,cnt = 0;
forn(i,x){
cnt+=judge(i);
//cerr<<i<<' '<<judge(i)<<'
';
}
if(n&1){
if(s[n/2]!=t[n/2]) cnt++;
}
cout <<cnt<<'
';
return 0;
}
E.
题意：一棵树有n个点（1e5），q个询问(1e5). 每次问一个点的dfs序中第x是多少，没有输出-1。
思路：dfs序预处理，并且统计儿子数。
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 2e5+5;
vector<int>e[maxn];
int id,num[maxn],num2[maxn],a[maxn];
int dfs(int u,int pre){
num[u] = ++id;
num2[id] = u;
int cnt = 1;
for(auto v:e[u]){
if(v==pre)continue;
cnt+=dfs(v,u);
}
a[u] = cnt;
return cnt;
}
int main(){
IO;
int n,q;cin>>n>>q;
for(int i = 2;i<=n;i++){
int x;cin>>x;
e[i].push_back(x);
e[x].push_back(i);
}
dfs(1,1);
forn(i,q){
int x,y;cin>>x>>y;
if(y>a[x])cout <<-1<<'
';
else cout <<num2[num[x]+y-1]<<'
';
}
return 0;
}
F.
题意：给你一个n*m(n,m<=20)的矩阵和一个k，问从(1,1)到(n,m)的最短路径中，路径上每个点的异或值的总和的为k的路径数目为多少。
思路：第一次做这种meet-in-the-middle
暴力的复杂度是O(2^n+m）
可以去中间交接点双向dfs或bfs
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll a[25][25];int n,m,lim;ll k,ans;
map<ll,int>num[25][25];
void dfs(int x,int y,int cnt,ll v){
num[x][y][v]++;
if(cnt==lim){
return;
}
if(x+1<n){
ll vv=a[x+1][y]^v;
dfs(x+1,y,cnt+1,vv);
}
if(y+1<m){
ll vv=a[x][y+1]^v;
dfs(x,y+1,cnt+1,vv);
}
}
void dfs2(int x,int y,int cnt,ll v){
if(cnt==n+m-2-lim){
ans+=num[x][y][v^k];
return;
}
if(x>0){
ll vv=a[x][y]^v;
dfs2(x-1,y,cnt+1,vv);
}
if(y>0){
ll vv=a[x][y]^v;
dfs2(x,y-1,cnt+1,vv);
}
}
int main(){
IO;
cin>>n>>m>>k;
forn(i,n)forn(j,m) cin>>a[i][j];
lim = n+m-2;lim>>=1;
dfs(0,0,0,a[0][0]);
dfs2(n-1,m-1,0,0);
cout << ans <<'
';
return 0;
}