Codeforces Round #821 (Div. 2)（A~E）

A. Consecutive Sum

最多可以进行k次操作，每次操作可以将两个对k取模相等的下标对应的元素交换位置，问做完这些操作之后每连续的k个数中，最大的和是多少。

思路：数据范围很小，直接对于所有对k取模相等的数进行比较，取最大的即可。

AC Code：

#include 
 
typedef long long ll;
const int N=1e5+5;
int t,n,k;
ll a[N];
 
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>t;
	while(t--){
		std::cin>>n>>k;
		for(int i=1;i<=n;i++){
			std::cin>>a[i];
		}
		ll ans=0;
		for(int i=1;i<=k;i++){
			ll max=-1;
			for(int j=0;i+j*k<=n;j++){
				max=std::max(max,a[i+j*k]);
			}
			ans+=max;
		}
		std::cout<'\n';
	}
	return 0;
}

 B. Rule of League

一列人，从头开始，两两比赛，胜出的人留下，每个人获胜的数量只能是x或y，若存在满足条件的胜负状态则输出任意一种，否则输出-1。

思路：首先如果一共n个人的获胜次数凑不出来n-1，则输出-1；若可以凑出来，则从头开始赋值即可。

AC Code：

#include 
 
typedef long long ll;
const int N=1e5+5;
int t;
ll n,x,y;
 
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>t;
	while(t--){
		std::cin>>n>>x>>y;
		bool flag=false;
		int cntx,cnty;
		for(int i=0;i
			if(x*i+(n-i)*y==n-1){
				flag=true;
				cntx=i,cnty=n-i;
				break;
			}
		}
		if(!flag){
			std::cout<<-1<<'\n';
			continue;
		}
		std::vector<int>ans;
		int pos=1,cnt=0;
		for(int i=1;i<=cntx;i++){
			for(int j=1;j<=x;j++){
				ans.push_back(pos);
				cnt++;
			}
			pos=cnt+2;
		}
		for(int i=1;i<=cnty;i++){
			for(int j=1;j<=y;j++){
				ans.push_back(pos);
				cnt++;
			}
			pos=cnt+2;
		}
		int len=ans.size();
		for(int i=0;i
			std::cout<" \n"[i==len-1];
		}
	}
	return 0;
}

C. Parity Shuffle Sorting

在一个数组中，可以使用最多n次操作，选择两个数字，若两数加起来为奇数，则将位置靠后的数字改为另一个数；若为偶数，则将位置靠前的数改为前一个数，怎样操作使得在最多n次操作之后使数列变为非递减排序的。

思路：一般这种题还有什么交互题，都应该去考虑比较极端的情况。这个题可以这样考虑：将第一个数和最后一个数经过一次操作变成一样的，中间的数，如果加起来是奇数的话选第一个数，如果加起来是偶数的话选最后一个数，这样在n-1次操作后将整个序列变成一样的数字，满足条件。（注意1特判，也可能不用？）

AC Code：

#include 
 
typedef long long ll;
typedef std::pair<int,int>PII;
const int N=1e5+5;
int t,n;
ll a[N];
 
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin>>t;
	while(t--){
		std::cin>>n;
		for(int i=1;i<=n;i++){
			std::cin>>a[i];
		}
		if(n==1){
			std::cout<<0<<'\n';
			continue;
		}
		std::vectorans;
		ans.push_back({1,n});
		int pos;
		if(a[1]+a[n]&1) pos=a[1];
		else pos=a[n];
		for(int i=2;i
			if(a[i]+pos&1) ans.push_back({1,i});
			else ans.push_back({i,n});
		}
		int len=ans.size();
		std::cout<'\n';
		for(int i=0;i
			std::cout<' '<'\n';
		}
	}
	return 0;
}

 D1. Zero-One (Easy Version)

给出a和b两个字符串，现对a进行操作，选择两个位置，翻转这两位的数字， 若两位置相邻，则花费为x，否则花费为y，现在求令两个字符串变为相同时的最少花费，若无法变为相同，则输出-1。

思路：首先当不同的字符是奇数个时，是无法变成相同的字符串，输出-1；因为D1保证了x>=y，所以尽可能不同时修改相邻的位置。当两个相邻且仅有这两个，且x<2*y时，我们必须选择修改相邻的位置；否则，首先修改不相邻的。可以证明除了这种情况外其他的情况都可以使用y解决。

AC Code：

#include 
 
#define int long long
int t,n,x,y;
std::string a,b;
 
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>t;
    while(t--){
        std::cin>>n>>x>>y;
        std::cin>>a>>b;
        int cnt=0;
        for(int i=0;i
            if(a[i]!=b[i]) cnt++;
        }
        if(cnt&1){
            std::cout<<-1<<'\n';
            continue;
        }
        bool flag=false;
        for(int i=0;i-1;i++){
            if(a[i]!=b[i]&&a[i+1]!=b[i+1]){
                if(cnt==2){
                    flag=true;
                    break;
                }
            }
        }
        if(flag) std::cout<min(x,2*y)<<'\n';
        else std::cout<2*y<<'\n';
    }
    return 0;
}

os：注意开ll

D2. Zero-One (Hard Version)

与D1题意类似，只是不再保证x>=y，且数据范围变成5e3。

思路：特判的情况与D1差不多，主要就是x

思路是知乎严格鸽的，orzorzCodeforces Round #821 (Div. 2) D(dp) E(思维) - 知乎 (zhihu.com)

AC Code：

#include 
 
#define int long long
const int N=5e3+5;
int t,n,x,y;
int f[N][N];
std::string a,b;
std::vector<int>vec;
 
int getans(int l,int r){
    if(l+1==r) return std::min(2*y,x);
    else return std::min(y,x*(r-l));
}
 
int DFS(int l,int r){
    if(l>r) return 0;
    if(f[l][r]!=-1) return f[l][r];
    int res=1e18;
    res=std::min(res,DFS(l+1,r-1)+getans(vec[l],vec[r]));
    res=std::min(res,DFS(l,r-2)+getans(vec[r-1],vec[r]));
    res=std::min(res,DFS(l+2,r)+getans(vec[l],vec[l+1]));
    return f[l][r]=res;    
}
 
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>t;
    while(t--){
        std::cin>>n>>x>>y;
        std::cin>>a>>b;
        a=' '+a,b=' '+b;
        vec.clear();
        for(int i=0;i<=n;i++){
            for(int j=0;j<=n;j++)
                f[i][j]=-1;
        }
        for(int i=1;i<=n;i++){
            if(a[i]!=b[i])
                vec.push_back(i);
        }
        if(vec.size()%2==1){
            std::cout<<-1<<'\n';
            continue;
        }
        if(vec.size()==0){
            std::cout<<0<<'\n';
            continue;
        }
        if(vec.size()==2){
            if(vec[0]+1==vec[1]) std::cout<min(2*y,x)<<'\n';
            else std::cout<min(y,x*(vec[1]-vec[0]))<<'\n';
            continue;
        }
        if(y<=x) std::cout<size()/2*y<<'\n';
        else std::cout<<DFS(0,vec.size()-1)<<'\n';
    }
    return 0;
}

E. Conveyor

给出一个无限大的网格，初始时每个网格的方向都是向右的，每一秒都会在(0,0)处放一个箱子，这个箱子会向现在所处网格的方向移动一格，然后网格方向变为向下，即向右和向下交替，q组询问，每次给出一个格子和时间t，判断在时间t时该格子是否有箱子。

思路：直接计算ts时每一个位置的格子不容易，但是可以计算ts时某一个格子途径了几个箱子，用两个时间的变化量也可以表示。我们定义a[i][j]在ts时，经过了多少箱子。可以知道，a[0][0]=t+1，又因为初始方向为向右，所以该点向右传送了向下传送了，这样计算在两个时间之间的差值，注意，该位置的点在到达该位置之前也至少有i+j的时间。

AC Code：

#include 
 
#define int long long
typedef long long ll;
const int N=150;
int f[N][N];
 
int getans(int t,int x,int y){
	memset(f,0,sizeof(f));
	f[0][0]=std::max(t-(x+y)+1,0ll);
	for(int i=0;i<=x;i++){
		for(int j=0;j<=y;j++){
			f[i+1][j]+=f[i][j]/2;
			f[i][j+1]+=f[i][j]-f[i][j]/2;
		}
	}
	return f[x][y];
}
 
signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int T;
	std::cin>>T;
	while(T--){
		int t,x,y;
		std::cin>>t>>x>>y;
		if(getans(t,x,y)-getans(t-1,x,y)>0) std::cout<<"YES"<<'\n';
		else std::cout<<"NO"<<'\n';
	}
	return 0;
}

os：思维题，感觉确实还好，但是赛时并做不到这里hhhh