Codeforces Round #626

div2A
给n个数,从中取出任意个数使得和为偶数,给出取出的数量和取出的数的位置。
解 2个奇数或者1个偶数即可。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
int a[105];
void work()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	int cnt=0;
	int k1=0;
	int k2=0;
	for(int i=1;i<=n;i++){
		if(a[i]%2==0){
			printf("1\n%d\n",i);return;
		}else{
			if(cnt==0){
				k1=i;
				cnt++;
			}else{
				printf("2\n%d %d\n",k1,i);return;
			}
		}
	}
	printf("-1\n");
	return;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

div2 B
给2个01序列a,b,矩形的\(c_{ij}=a_i*b_j\),给定面积k,问面积为k的全1矩形有多少个
解 若为全1矩形 那么这一段的a和b就要求为连续的1,那么对a,b求一个前缀和,然后对面积k枚举长宽,利用前缀和判断有多少个连续的1即可。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
int x[40005];
int y[40005];
int sumx[40005];
int sumy[40005];
int n,m,k;
ll cal(int a,int b)
{
	int cnt1=0;
	int cnt2=0;
	for(int i=a;i<=n;i++){
		if(sumx[i]==sumx[i-a]+a)cnt1++;
	}
	for(int i=b;i<=m;i++){
		if(sumy[i]==sumy[i-b]+b)cnt2++;
	}
	return 1ll*cnt1*cnt2;
}
void work()
{
	
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&x[i]);
		sumx[i]=sumx[i-1]+x[i];
	}
	for(int i=1;i<=m;i++){
		scanf("%d",&y[i]);
		sumy[i]=sumy[i-1]+y[i];
	}
	ll ans=0;
	for(int i=1;i*i<=k;i++){
		if(k%i==0){
			ans+=cal(i,k/i);
			if(i*i!=k){
				ans+=cal(k/i,i);
			}
		}
	}
	printf("%lld\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

div2C div1A
给一个括号串,你可以将任意长度的串任意排列,代价为串的长度,问使得括号串正确的最小代价。
解 把(看做1,)看做-1,那么在求前缀和的时候 只要不出现负数,那么就是一个好的串。如果出现了负数,那么意味着从这个点开始出现了错误,那么修改也要从这个点开始。首先如果这个点出现了负数,那么上一个点必定是0,那么当我们再找到下一个0的时候,那么这两个点之间的2种括号数量相同,将这段区间进行排列即可。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
char a[1000005];
void work()
{
    int n;
    scanf("%d",&n);
    scanf("%s",a);
    bool f=false;
    int cnt=0;
    int now;
    int ans=0;
    for(int i=0;i<n;i++){
        if(a[i]=='(')cnt++;
        else cnt--;
        if(!f&&cnt<0){
            f=true;
            now=i;
        }
        if(f&&cnt==0){
            f=false;
            ans+=i-now+1;
        }
    }
    if(cnt!=0){
        printf("-1\n");
        return;
    }
    printf("%d\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

div2D div1B
给一个数列,求任意两个数相加的异或。
枚举答案的每一位,对于直接在这一位上为1,和进位后这一位为1分别计算数量即可。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
int a[400005];
int b[400005];
void work()
{
    int n;
    scanf("%d",&n);
    int ans=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int j=0;j<=24;j++){
        int tmp=1<<j;
        for(int i=1;i<=n;i++){
            b[i]=a[i]&(tmp-1);//b只取比当前这位低的段
        }
        ll sum=0;
        for(int i=1;i<=n;i++){
            if(a[i]&tmp)sum++;
        }
        if(sum&1&&n%2==0)ans+=tmp;//如果要使得这一位上为1,那么sum*(n-sum)要为奇数,那么sum要为奇数,n要为偶数
        sort(b+1,b+n+1);
        int p=n;
        sum=0;
        for(int i=1;i<=n;i++){
            p=max(p,i);
            while(p>i&&b[i]+b[p]>=tmp)p--;//计算有多少个加起来满足这一位为1的,因为b取得都是比当前tmp小的,所以加起来必定不会超过tmp*2,也就是下一位
            sum+=(n-p);
        }
        if(sum%2==1)ans^=tmp;
    }
    printf("%d\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

vis2E div1C
给n个数和二分图,求对于左边任意一个子集,右边与其相邻的点的值的和的gcd。
解 对于右边的点,如果他们连的左边点全部相同,那么他们必定是加在一起的(因为取任意点,这些点要么全被选 要么全不被选),然后对于所有数求gcd。证明等我先看懂了。。。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
ll a[500005];
vector<ll>v[500005];
void work()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        v[i].clear();
    }
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        v[y].emplace_back(x);//使用push_back会T
    }
    map<vector<ll>,ll>mp;
    for(int i=1;i<=n;i++){
        if(v[i].empty())continue;
        sort(v[i].begin(),v[i].end());
        mp[v[i]]+=a[i];
    }
    ll ans=0;
    for(auto x:mp)ans=__gcd(ans,x.second);
    printf("%lld\n",ans);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

div2F div1D
给n个人,每个人有\(l_i\)(上限为m)的攻击力和\(s_i\)的出演费,当攻击力为i的人上台时会获得\(c_i\)的利润,你必须从1-n按顺序雇佣,如果你已经选了的人里面有攻击力严格大于当前这个人的,那么不能选这个人,否则可以选择要或是不要,就是选择的人的攻击力要是一个非递增序列。当2个攻击力相同的人上台上(先获得收益),其中一个会退场,并且使另一个人的攻击力+1,同时获得\(c_{i+1}\)的收益,问最大收益。
解 dp,dp[i][j]   i代表当前最高的攻击力,j代表攻击力为i的人有多少个,所获得的最大收益。由于记录的是最高攻击力,所以将人倒过来存,那么就是要求形成一个非递减序列。每加入一个人将d[l[i]][j]=max(d[l[i][j-1]+c[l[i]]-s[i]),对于最高攻击力每上升一个等级,dp[i+1][j/2]=max(dp[i+1][j/2],dp[i][j]+j/2*c[i+1])

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
const int inf=0x3f3f3f;
int s[2005],l[2005];
int c[4005];
ll dp[4005][2005];
void work()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&l[n-i+1]);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&s[n-i+1]);
	}
	memset(dp,-inf,sizeof(dp));
	for(int i=1;i<=n+m;i++){
		scanf("%d",&c[i]);	
		dp[i][0]=0;
	}
	dp[0][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=n;j>=1;j--){
			dp[l[i]][j]=max(dp[l[i]][j],dp[l[i]][j-1]+c[l[i]]-s[i]);
		}
		for(int j=l[i]+1,k=n;j<=n+m;j++,k>>=1){
			for(int p=0;p<=k;p++){
				dp[j][p/2]=max(dp[j][p/2],dp[j-1][p]+p/2*c[j]);
			}
		}
	}
	printf("%lld\n",dp[n+m][0]);//当攻击力达到n+m时必定为0个人,n个攻击力为m的人,最高攻击力只会升到m+logn
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注