目录

A. Adjacent Replacements

B. Polycarp's Practice

C. Three Parts of the Array

D. Two Strings Swaps

E. Military Problem

F. Xor-Paths

---

A. Adjacent Replacements

简单思维题

每一个数都变成第一个小于等于自己的的奇数

void solve(){
    
    cin>>n;
    while(n--){
    	int x; cin>>x;
    	cout<<(x&1 ? x : x-1)<<' ';
    }
    cout<<endl;
    return ;
}

B. Polycarp's Practice

简单性质

由题知一定是选出最大的m个数然后对这m个数分配线段即可，最后一个是到n

PII e[N];
void solve(){
    
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	int x; cin>>x;
    	e[i]={x,i};
    }
    sort(e+1,e+1+n,greater<PII>());
    LL ans = 0;
    vector<int> res;
    for(int i=1;i<=m;i++){
    	auto [x,id]=e[i];
    	ans += x;
    	res.push_back(id);
    }
    
    sort(res.begin(),res.end());
    cout << ans << endl;
    int last = 0;
    for(int i=0;i<m;i++){
    	int v=res[i];
    	if(i==m-1) v=n;
    	cout<<v-last<<' ';
    	last=v;
    }
    cout<<endl;
    return ;
}

C. Three Parts of the Array

前后缀相等明显的就是双指针，按照双指针的方式来移动使得相等即可

void solve(){
    
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    LL pre=0,suf=0;
    int l=1,r=n;
    LL ans = 0;
    while(l<=r){
    	if(pre<=suf) pre+=a[l++];
    	else suf+=a[r--];
    	if(pre==suf) ans=max(ans,pre);
    }
    cout << ans << endl;
    return ;
}

D. Two Strings Swaps

题目不难但是有细节注意a的改变只能是在交换前

依次对几种情况仔细的讨论

4  a b c d   2次

3  a  a b  c  2次     b   c  a  a 1次

2  a  a  b  b  0次   a  a  a  b 1次   a  b a a 1 次

1 0 次
 

void solve(){
    cin>>n;
    string a,b; cin>>a>>b;
    a=' '+a,b=' '+b;
    map<char,int> mp;
    int ans = 0;
    for(int i=1;i<=n/2;i++){
    	set<char> s={a[i],a[n-i+1],b[i],b[n-i+1]};
    	mp.clear();
    	mp[a[i]]++;
    	mp[a[n-i+1]]++;
    	mp[b[i]]++;
    	mp[b[n-i+1]]++;
    	if(s.size()==4) ans+=2;
    	if(s.size()==3){
    		if(a[i]==a[n-i+1]) ans += 2;
    		else ans += 1;
    	}
    	if(s.size()==2){
    		if(mp[a[i]]!=2) ans += 1;
    	}
    }
    if(n&1 and a[n+1>>1]!=b[n+1>>1]) ans+=1;
    cout << ans << endl;
    return ;
}

E. Military Problem

简单树形问题，用类似dfs序列标记每一个点即可

int d[N],dmx[N],id[N];
int idx;
vector<int> g[N];
 
void dfs(int u){
	dmx[u]=d[u]=++idx;
	id[idx]=u;
	for(auto&v:g[u]){
		dfs(v);
		dmx[u]=max(dmx[v],dmx[u]);
	}
}
void solve()
{
    cin>>n>>m;
    for(int i=2;i<=n;i++){
    	int x; cin>>x;
    	g[x].push_back(i);
    }
	dfs(1);    
    while(m--){
    	int x,y; cin>>x>>y;
    	if(d[x]+y-1>dmx[x]) cout<<-1<<endl;
    	else cout<<id[d[x]+y-1]<<endl;
    }
    return ;
}

F. Xor-Paths

我们发现如果直接搜索的话是肯定会超时的，时间复杂度是,我们对于这个数就是的两倍

，我们敏锐的发现如果可以变成一半的话就是可以通过的，于是我们想到可以折半搜索，所以可以得到答案，于是我们开map来记录路径即可，同时注意到一半是(n+m)/2的位置即可

LL X;
LL ans;
LL a[25][25];
map<LL,int> mp[25][25];
void dfs1(int x,int y,LL s){
	if(x>n or y>m) return ;
	s^=a[x][y];
	if(x+y==(n+m)/2+1){
		mp[x][y][s]++;
		return ;
	}
	dfs1(x+1,y,s);
	dfs1(x,y+1,s);
}
void dfs2(int x,int y,LL s){
	if(x<1 or y<1) return ;
	
	if(x+y==(n+m)/2+1){
		if(mp[x][y].count(s^X)) ans+=mp[x][y][s^X];
		return ;
	}
	s^=a[x][y];
	dfs2(x-1,y,s);
	dfs2(x,y-1,s);
}
void solve(){
    
    cin>>n>>m>>X;
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=m;j++)
    		cin>>a[i][j];
    
    dfs1(1,1,0);
    dfs2(n,m,0);
    
    cout << ans << endl;
    return ;
}