Codeforces Round #668 (Div. 2)A-C题解

A. Permutation Forgery

题目：http://codeforces.com/contest/1405/problem/A

题解：这道题初看有点吓人，一开始居然想到要用全排序，没错我真傻，TLE，之后再想后发现，将数组反过来，两两相加的和和正着的是一样的，因此我们只需将数组倒叙即可。

代码：

#include<bits/stdc++.h>    //POJ不支持
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
using namespace std;
const long long inf = 1e12;//无穷大
const int maxn = 1010;//最大值。
typedef long long ll;


ll a[110],t,n;

int main()
{
    IOS;
    int i,j;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(i=0;i<n;i++)
            cin>>a[i];
        reverse(a,a+n);
        for(i=0;i<n;i++)
            cout<<a[i]<<" ";
        cout<<endl;
    }
    return 0;
}

B. Array Cancellation

题目：http://codeforces.com/contest/1405/problem/B

题解：

题意是当i<j，可以执行a[i]--,a[j]++，此操作是不消耗硬币的，而i>j的话需要消耗一个硬币，输出最小的消耗硬币

我们的解法是：从头进行遍历，若为正数则ans相加，统计i之前的正数之和，若为负数，判断ans是否能将其中和为0，若可以则ans+=a[i]，否则ans=0,a[i]+=ans，最后遍历完之后，将不用消耗硬币的操作做完，剩余的所有负数即为需要消耗硬币才能将其置为0的操作，因此可以在第一次遍历是就将剩余的负数统计一下。

代码：

#include<bits/stdc++.h>    //POJ不支持
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
using namespace std;
const long long inf = 1e12;//无穷大
const int maxn = 100100;//最大值。
typedef long long ll;

ll a[maxn],n,ans,ans2;
int main()
{
    IOS;
    int i,j,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&n);
        ans=0,ans2=0;
        for(i=0;i<n;i++)
        {
            scanf("%lld",&a[i]);
        }
        for(i=0;i<n;i++)
        {
            if(a[i]>0)
                ans+=a[i];
            else
            {
                if(ans+a[i]>0)
                    ans+=a[i];
                else
                {
                    a[i]+=ans;
                    ans=0;
                    ans2-=a[i];
                }
            }
        }
        printf("%lld
",ans2);
    }
    return 0;
}

C. Balanced Bitstring

题目：考虑第一段0123和第二段1234，其中123是相同的，即只需要使得0和4相同即可，即为同余位置的字符相同即可
最后检查一下0~k的位置的0和1的数量是否满足我们上面的假设即可

代码：

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e12;//无穷大
const int maxn = 300010;//最大值。
typedef long long ll;
char s[maxn];
int t,n,k;

bool check()
{
    int v0=0,v1=0,i,j;
    for(i=1;i<=k;i++)
    {
        v0=v1=0;
        for(j=i;j<=n;j+=k)
        {
            if(s[j]=='1')
                v1=1;
            if(s[j]=='0')
                v0=1;
        }
        //若同余位置的数字不相等，直接退出
        if(v0&&v1)
            return false;
        for(j=i;j<=n;j+=k)
        {
            //将同余位置为？的替换成应该出现的数字
            if(s[j]=='?')
            {
                if(v0)
                    s[j]='0';
                else if(v1)
                    s[j]='1';
            }
        }
    }
    v0=v1=0;
    //统计前k个字符终0和1的个数，是否过半，过半则no
    for(i=1;i<=k;i++)
    {
        if(s[i]=='1')
            v1++;
        else if(s[i]=='0')
            v0++;
    }
    if(v0>k/2||v1>k/2)
        return false;
    return true;
}

int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        scanf("%s",s+1);
        if(check())
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}