Codeforces Round #626 div.2 题解

A. Even Subset Sum Problem

题意

给你n个数，问你能否选择其中的若干个数使他们的和为偶数，如果不能输出-1，如果能输出一个可行的选数方案

思路

显然不能的情况只有一种就是n==1且这个数是奇数
剩下的情况就是随便找两个奇数或者找一个偶数的位置输出就好了

代码

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=100+10;
int a[maxn];
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n;
		cin>>n;
		int flag=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		if(n==1&&a[1]%2!=0){
			cout<<"-1"<<endl;	
		}
		else{
			int fl=0;
			for(int i=1;i<=n;i++){
				if(a[i]%2==0){
					cout<<"1"<<endl<<i<<endl;
					fl=1;
					break;
				}
			}
			if(!fl){
				cout<<"2"<<endl<<"1 2"<<endl;	
			} 
		}
	}
}

B. Count Subrectangles

题意

这题读了半天才读懂... 意思是给你两个只由1和0构成的序列 An 和 Bn ,可以构造出一个矩阵Cnn
其中Cij=Ai x Bj,然后给你一个k，问这个矩阵中面积为k且只由1构成的子矩阵有几个。

思路

每个子矩阵都是由A序列中的某个区间和B序列中的某个区间构成的，如果子矩阵全为1的话则A、B序列中对应的两个区间也都全为1,所以就把两个序列合并处理(例如:1 1 0 1 0 1转化为 2 1 1)，然后再枚举k的因子，k=xy ,然后在合并后的序列中分别找大于x/y的部分然后相乘再求和就好了，注意要开long long！

代码

#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=40000+10;
int a[maxn],b[maxn];
int aaa[maxn],bbb[maxn];
int main(){
	int n,m,k;
	cin>>n>>m>>k;
	int acnt=1,now=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]) now++;
		else{
			aaa[acnt]=now;
			now=0;acnt++;
		}
	}
	if(now!=0){
		aaa[acnt]=now;	
	}
	int bcnt=1;now=0;
	for(int i=1;i<=m;i++){
		cin>>b[i];
		if(b[i]) now++;
		else{
			bbb[bcnt]=now;
			now=0;bcnt++;	
		}
	}
	if(now!=0){
		bbb[bcnt]=now;	
	}
	long long ans=0;
	for(int i=1;i*i<=k;i++){
		if(k%i==0){
			long long ls1=0,ls2=0;
			for(int j=1;j<=acnt;j++){
				if(aaa[j]<i)continue;
				ls1+=aaa[j]-i+1;
			}
			int pp=k/i;
			for(int j=1;j<=bcnt;j++){
				if(bbb[j]<pp)continue;
				ls2+=bbb[j]-pp+1;
			}
			ans+=ls1*ls2;
			if(pp!=i){
				long long ls3=0,ls4=0;
				for(int j=1;j<=acnt;j++){
					if(aaa[j]<pp)continue;
					ls3+=aaa[j]-pp+1;
				}
				for(int j=1;j<=bcnt;j++){
					if(bbb[j]<i)continue;
					ls4+=bbb[j]-i+1;
				}
				ans+=ls3*ls4;
			}
		}	
	}
	cout<<ans;
	return 0;
}

C. Unusual Competitions

题意

给一串括号序列，每次移动任意调整子串中括号的顺序最少，每次移动花费的代价是子串的长度，问最少代价是多少。

思路

从左往右扫，显然只有前括号和后括号数量相等的时候，才能进行一次结算
结算的时候用栈来判断当前这一段能不能匹配的上，不能匹配就全交换,然后继续往后扫
最后如果括号有剩余说明不能匹配输出-1

代码

#include<cstdio>
#include<iostream>
#include<stack>
using namespace std;
const int maxn=1000000+10;
char a[maxn];
stack<int> s;
int main(){
	int n;
	cin>>n>>a+1;
	int now1=0,now2=0,a1=1,a2=2;
	int ans=0,st=1;
	for(int i=1;i<=n;i++){
		if(a[i]=='('){
			now1++;
		}
		else {
			now2++;
			if(now1==now2){
				for(int j=st;j<=i;j++){
					if(a[j]=='('){
						s.push(a1);	
					}
					else{
						if(s.top()==1){
							s.pop();
						}
						else{
							s.push(a2);	
						}
					}
				}
				if(!s.empty()){
					ans+=i-st+1;
				}
				st=i+1;now1=0;now2=0;
				while(!s.empty()){
					s.pop();
				}
			}
		}
		if(now1==now2&&now1!=0){
			ans+=i-st+1;
			st=i+1;now1=0;now2=0;
		}
	}
	if(now1!=0||now2!=0){
		cout<<"-1"<<endl;	
	}
	else cout<<ans<<endl;
}