.
A. Adjacent Replacements
执行1e9次命令，输出的最后数组的样子
一个奇数执行两次命令 会变回原来的数字
一个偶数只会执行一次命令 变成比自身小1的数
#include<bits/stdc++.h> #define int long long #define MAX(a,b,c) max(a,max(b,c)) #define MIN(a,b,c) min(a,min(b,c)) #define pb push_back #define fi first #define se second typedef long long ll; typedef long long LL; typedef unsigned long long ull; typedef unsigned long long uLL; using namespace std; const int maxn=1e6+10; const int INF=1e15; int a[maxn]; int32_t main() { int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { if(a[i]%2==1) cout<<a[i]<<" "; else cout<<a[i]-1<<" "; } }
B. Polycarp's Practice
给出 数组n k 将数组分成k段（每段至少1） 求k段每段中最大数的和的最大值
排序一下 最大的n个数就是数字最大的
将k个最大数标记 我用的map 标记
然后扫一遍输出 第一个标记前的非标记的个数和自身 标记和标记间的个数 最后一个标记和标记间还有标记后的个数
例子
1 2 3 2 1 4 1 5 1 3
mp[3]=1; mp[2]=1; mp[5]=1; 这是被标记的
分成的为 1 2 3 2 1 4 1 5 1 3 三段
#include<bits/stdc++.h> #define int long long #define MAX(a,b,c) max(a,max(b,c)) #define MIN(a,b,c) min(a,min(b,c)) #define pb push_back #define fi first #define se second typedef long long ll; typedef long long LL; typedef unsigned long long ull; typedef unsigned long long uLL; using namespace std; const int maxn=1e6+10; const int INF=1e15; int a[maxn]; int b[maxn]; map<int,int> mp; int32_t main() { int n,k; cin>>n>>k; for(int i=1;i<=n;i++) {cin>>a[i]; b[i]=a[i];} sort(a+1,a+1+n); int ans=0; int num=k; for(int i=n;i>=1;i--) { if(num) {ans+=a[i]; num--; mp[a[i]]++; } } cout<<ans<<endl; int t=0; for(int i=1;i<=n;i++) { if(mp[b[i]]&&k!=1) { cout<<t+1<<" "; t=0; mp[b[i]]--; k--; } else { t++; } } cout<<t<<" "; }
C. Three Parts of the Array
给你一个数组 你分成3段（长度可以为0） 是第一段和最后一段的和相等 求怎么样分让第一段和最大
定义 num1=num3=0;
一个从前往后找 一个从后往前找 谁少谁加 一样就记录答案 都加一个数
#include<bits/stdc++.h> #define int long long #define MAX(a,b,c) max(a,max(b,c)) #define MIN(a,b,c) min(a,min(b,c)) #define pb push_back #define fi first #define se second typedef long long ll; typedef long long LL; typedef unsigned long long ull; typedef unsigned long long uLL; using namespace std; const int maxn=1e6+10; const int INF=1e15; int a[maxn]; int32_t main() { int n; cin>>n; for(int i=1;i<=n;i++) scanf("%d",&a[i]); int num1=0; int num3=0; int ans=0; int i=0; int j=n+1; while(i+1!=j) { if(num1==num3) { ans=max(num1,num3); if(i+2==j) break; i++;j--; num1+=a[i]; num3+=a[j]; } else if(num1<num3) { i++; num1+=a[i]; } else if(num1>num3) { j--; num3+=a[j]; } } if(num1==num3) ans=num1; cout<<ans<<endl; }
D. Two Strings Swaps
给你两个字符串 长度一样 修改第一个字符串 再通过变换 让两个字符串一样
变换规则
- Choose any index ii (1≤i≤n1≤i≤n) and swap characters aiai and bibi;
- Choose any index ii (1≤i≤n1≤i≤n) and swap characters aiai and an−i+1an−i+1;
- Choose any index ii (1≤i≤n1≤i≤n) and swap characters bibi and bn−i+1bn−i+1；
找 ai a(n-i) bi ,b(n-i) 中最大有多少对字符一样
当ai=a(n-i) 时特判 bi！=b(n-1) 要修改两个
#include<bits/stdc++.h> #define int long long #define MAX(a,b,c) max(a,max(b,c)) #define MIN(a,b,c) min(a,min(b,c)) #define pb push_back #define fi first #define se second typedef long long ll; typedef long long LL; typedef unsigned long long ull; typedef unsigned long long uLL; using namespace std; const int maxn=1e6+10; const int INF=1e15; int32_t main() { int n; cin>>n; string ss;cin>>ss; string tt;cin>>tt; int ans=0; for(int i=0;i<n/2;i++) { int t=0; if(ss[i]==ss[n-1-i]) t++; if(tt[i]==tt[n-1-i]) t++; else t--; int w=0; if(ss[i]==tt[i]) w++; if(ss[n-1-i]==tt[n-1-i]) w++; int k=0; if(ss[i]==tt[n-1-i]) k++; if(ss[n-i-1]==tt[i]) k++; int num=MAX(t,w,k); if(num==0) ans+=2; if(num==1) ans+=1; } if(n%2==1) { if(ss[n/2]!=tt[n/2]) ans++; } cout<<ans<<endl; }
E. Military Problem
树不会很会 表述（大家多多见谅）
有一个树
q次询问 问节点 x 是否有 y 个子节点 没有输出 -1 有输出第y个字节点上的书
#include<bits/stdc++.h> #define int long long #define MAX(a,b,c) max(a,max(b,c)) #define MIN(a,b,c) min(a,min(b,c)) #define pb push_back #define fi first #define se second typedef long long ll; typedef long long LL; typedef unsigned long long ull; typedef unsigned long long uLL; using namespace std; const int maxn=1e6+10; const int INF=1e15; vector<int> tree[maxn]; int vis[maxn]; int sum[maxn]; int s[maxn]; int cnt=1; int dfs(int id) { int ans=1; vis[id]=cnt; s[cnt]=id; cnt++; for(int i=0;i<tree[id].size();i++) ans+=dfs(tree[id][i]); return sum[id]+=ans; } int32_t main() { int n,p; cin>>n>>p; for(int i=2;i<=n;i++) { int a; cin>>a; tree[a].pb(i); } dfs(1); while(p--) { int x,y; cin>>x>>y; if(sum[x]<y) cout<<"-1"<<endl; else cout<<s[vis[x]+y-1]<<endl; } }
F. Xor-Paths
从（1，1）到 （n, m） 找路径中所有数的异或为k的道路条数 （只能下 右）
直接dfs会超时 用两端dfs
#include<bits/stdc++.h> #define int long long #define MAX(a,b,c) max(a,max(b,c)) #define MIN(a,b,c) min(a,min(b,c)) #define pb push_back #define fi first #define se second typedef long long ll; typedef long long LL; typedef unsigned long long ull; typedef unsigned long long uLL; using namespace std; const int maxn=5000+10; const int INF=0x3f3f3f3f; int a[25][25]; map<int,int> mp[25][25]; int n,m,k; int MAX; int ans; void dfs1(int x,int y,int num) { num=num^a[x][y]; if(x+y==MAX) { mp[x][y][num]++; } else { int x1=x+1; int y1=y; if(x1>=1 && x1<=n && x1>=1 && y1<=m) { dfs1(x1,y1,num); } int x2=x; int y2=y+1; if(x2>=1 && x2<=n && x2>=1 && y2<=m) { dfs1(x2,y2,num); } } } void dfs2(int x,int y,int num) { if(x+y==MAX) { ans+= mp[x][y][num]; } else { num=num^a[x][y]; int x1=x-1; int y1=y; if(x1>=1 && x1<=n && x1>=1 && y1<=m) { dfs2(x1,y1,num); } int x2=x; int y2=y-1; if(x2>=1 && x2<=n && x2>=1 && y2<=m) { dfs2(x2,y2,num); } } } int32_t main() { cin>>n>>m>>k; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; } } if(n==1&&m==1) { if(k==a[1][1]) cout<<1<<endl; else cout<<0<<endl; return 0; } MAX=max(n,m); dfs1(1,1,0); dfs2(n,m,k); cout<<ans<<endl; }