Codeforces Round #626 (Div. 2, based on Moscow Open Olympiad in Informatics)

A. Even Subset Sum Problem

题意

给出一串数，找到其中的一些数使得他们的和为偶数

题解

水题，找到一个偶数或者两个奇数就好了

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#define def 110

using namespace std;

long a[def];

int main()

{	long _,ans0,ans1,ans2,n,i;

	for(scanf("%ld",&_);_;_--){

		scanf("%ld",&n);

		ans0=ans1=ans2=-1;

		for(i=1;i<=n;i++){

			scanf("%ld",&a[i]);

			if(a[i]%2==0)

				ans0=i;

			else if(ans1==-1)

				ans1=i;

			else ans2=i;

		}

		if(ans0==-1&&(ans1==-1||ans2==-1))

			printf("-1\n");

		else if(ans0!=-1)

			printf("1\n%ld\n",ans0);

		else

			printf("2\n%ld %ld\n",ans1,ans2);

	}

	return 0;

}

B. Count Subrectangles

题意

给出\(a\)和\(b\)两个数列，构造一个矩阵\(c\)，使得\(c_{i,j}=a_i*b_j\)，求矩阵\(c\)中有多少个面积为\(k\)的小矩阵里的值全为1

题解

根据矩阵\(c\)的构造原理可知，每一行相邻元素的连续性由\(b\)决定，每一列的连续性由\(a\)决定，所以可以分别记录下到每个位置到上一个0的长度\(lena\)和\(lenb\)，那么当前点为顶点能构成的最大矩阵就是\(lena*lenb\)，最后枚举一下小矩阵的边长就好了

代码

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<set>

#define ll long long

#define lowbit(i) ((i)&-(i))

#define def 40010

using namespace std;

ll sum[def],a[def],b[def];

set<ll>st;

void add(long x,long y)//用树状数组加速在b中的查询

{

    for(;x<def;x+=lowbit(x))

        sum[x]+=y;

}

ll query(long x)

{    long ans=0;

    for(;x;x-=lowbit(x))

        ans+=sum[x];

    return ans;

}

int main()

{    ll n,m,i,j;

    ll ans=0,k;

    scanf("%lld%lld%lld",&n,&m,&k);

    for(i=1;i<=sqrt(k);i++)

        if(k%i==0){

            st.insert(i);

            st.insert(k/i);

        }

    for(i=1;i<=n;i++){

        scanf("%lld",&a[i]);

        if(a[i])

            a[i]+=a[i-1];

    }

    for(i=1;i<=m;i++){

        scanf("%lld",&b[i]);

        if(b[i]){

            b[i]+=b[i-1];

            add(b[i],1);

        }

    }

    for(i=1;i<=n;i++)

        if(a[i]){

            for(auto q:st)

                if(a[i]>=k/q&&q<=m)

                    ans+=query(m)-query(q-1);

        }

    printf("%lld\n",ans);

    return 0;

}

C. Unusual Competitions

题意

给定一个括号序列，每次可以选择一个区间\([l,r]\)来重排，耗时\(r-l+1\)，求最少需要多少时间使其变得正常（左右括号完全匹配）

题解

因为时间只跟区间长度有关，跟内容无关，故只要找到不正常的区间来重排就好了

对于一个\(num['(']==num[')']\)的区间，如果其中存在一个点，在这个点上\(num['(']<num[')']\)，那么这个区间就是一个不正常的区间

枚举一遍，O(n)解决

代码

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int main()

{    long long n,i,num=0,ans=0,l=0;

    bool t=false;

    string s;

    cin>>n>>s;

    for(i=0;i<n;i++){

        if(s[i]=='(')

            num++;

        else

            num--;

        if(num<0)t=true;

        if(!num){

            if(t)

                ans+=i-l+1;

            l=i+1;

            t=false;

        }

    }

    if(num)

        printf("-1\n");

    else

        printf("%lld\n",ans);

    return 0;

}

巴特西

Codeforces Round #626 (Div. 2, based on Moscow Open Olympiad in Informatics)

Codeforces Round #626 (Div. 2, based on Moscow Open Olympiad in Informatics)

A. Even Subset Sum Problem

题意

题解

代码

B. Count Subrectangles

题意

题解

代码

C. Unusual Competitions

题意

题解

代码

最新文章

热门文章