前言

600分的题果然不是那么适合萌新...萌新都快哭了.

A - Blackjack

按题意输入输出即可.

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int ans=0,res=22;
    for(int i=0;i<3;i++)
    {
        int x;cin>>x;
        ans+=x;
    }ans>=res?puts("bust"):puts("win");
    return 0;
}

B - Palindrome-philia

哪个字母不是回文串 ${Ans++}$ .

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;cin>>s;
    int len=s.size(),ans=0;
    for(int i=0;i<(len+1)/2;i++)
    {
        if(s[i]!=s[len-i-1])    ans++;
    }cout<<ans<<'\n';
    return 0;
}

C - HonestOrUnkind2

二进制枚举哪个点是不是说的正确,然后检测即可啦.

代码

#include <bits/stdc++.h>
using namespace std;
const int N=20;
bool md[N][N];
int a[N];
struct limit{
    int x,y;
};
vector<limit>ask[N];
bool use[N];//n个数是否使用.

int main()
{
    int n;cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        for(int j=1;j<=a[i];j++)
        {
            int x,y;cin>>x>>y;x--;
            ask[i].push_back({x,y});
        }
    }int m=(1<<n);int ans=0;
    for(int i=0;i<m;i++)
    {
        int res=0;memset(use,false,sizeof use);
        for(int j=0;j<n;j++)
        {
            if(i>>j&1)    use[j]=true,res++;
        }bool flag=true;
        for(int j=0;j<n;j++)
        {
            if(use[j])
            {
                for(auto u:ask[j])
                {
                    if(u.y==0)
                    {
                        if(use[u.x])    flag=false;
                    }
                    else
                    {
                        if(!use[u.x])    flag=false;
                    }
                }
            }
        }if(flag)    ans=max(ans,res);
    }cout<<ans<<'\n';
    return 0;
}

D - Xor Sum 4

前缀一下每一位的 ${0/1}$ 的数量,然后按位算贡献即可啦~

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5,M=61;
const int mod=1e9+7;
ll a[N],num[N][M];
int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        for(int j=0;j<60;j++)
        {
            if(a[i]&(1ll<<j))    num[i][j]+=num[i-1][j]+1;
            else                num[i][j]+=num[i-1][j];    
        }
    }ll ans=0;
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<60;j++)
        {
            ll tot=i-1;
            if(a[i]>>j&1)    ans+=(1ll<<j)%mod*(tot-num[i-1][j])%mod;
            else            ans+=(1ll<<j)%mod*num[i-1][j]%mod;
            ans%=mod;
        }
    }cout<<ans<<'\n';
    return 0;
}

E - Balanced Path

令 ${f_{i,j,k}}$ 为到了 ${i,j}$ 差值为 ${k}$ 的方案是否存在.
然后因为有负数,你用 ${map/unorderedmap}$ 都会 ${TLE}$ 的,那么我们不妨不偷懒,直接 ${+base}$ 即可.
转移十分简单.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=85,M=6450;
bool f[N][N][M<<2];//到了i,j差值为k的方案是否存在.
int a[N][N],b[N][N]; 
int main()
{
    int h,w;cin>>h>>w;int m=12800;
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
            cin>>a[i][j];
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
            cin>>b[i][j];
    f[1][0][m]=true;
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
            for(int k=0;k<=2*m;k++)
            {
                f[i][j][k]|=f[i-1][j][k-(a[i][j]-b[i][j])];
                f[i][j][k]|=f[i-1][j][k-(b[i][j]-a[i][j])];
                f[i][j][k]|=f[i][j-1][k-(a[i][j]-b[i][j])];
                f[i][j][k]|=f[i][j-1][k-(b[i][j]-a[i][j])];
            }
    int ans=1e9;
    for(int i=0;i<=2*m;i++)    
        if(f[h][w][i])
            ans=min(ans,abs(i-m));
    cout<<ans<<'\n';
    return 0;
}

F - Sum Difference

首先要你找 ${S,T}$ 两个集合的差不同的数,其实就是让你找 ${U-2*S}$ 的差不同的数. ${U}$ 是确定的,其实就是问你有多少种 ${S}$ 的取值.
对于 ${d==0~and~x==0}$ 输出 ${1}$ ,对于 ${d==0~and~x!=0}$ 输出 ${n+1}$ .
其次对于 ${S}$ ,你可以假设取了 ${k}$ 项,那么它的值 ${S=k*x+I*d}$ 其中 ${S,I}$ 为变量,简单的可以看成一个一次函数.

${I}$ 的取值范围为 ${[0+1+2+...+k-1,n-k+n-k+1+...+n-2+n-1]}$ .这个区间内所有值都可以取.我们不妨把这条直线的点映射成数轴上的点.具体操作就是记录原本的偏移量 ${t=k*x}$ ,以及在这个偏移量下可以取值的范围 ${[L,R]}$ . ${[L,R]}$ 里面都是 ${d}$ 的倍数,而 ${t}$ 成了一个确定但不一定是 ${d}$ 倍数的常量,我们不妨把 ${L+t/d}$ , ${R+t/d}$ .这样 ${L,R}$ 都映射到了数轴上了,记录偏移量为 ${t~mod~d}$ .然后按偏移量就行线段合并即可.
别看题解就这么多,懂了发现并没有那么难,但是也没那么好懂.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+50;
ll sum[N];
struct node{
    ll l,r;
};
map<int,vector<node> >s;
bool cmp(node a,node b)
{
    if(a.l==b.l)    return a.r<b.r;
    else            return a.l<b.l;
}

int main()
{
    ll n,x,d;
    cin>>n>>x>>d;
    for(int i=1;i<=n;i++)    sum[i]+=sum[i-1]+i;
    if(d==0)
    {
        if(x==0)    cout<<1<<'\n';
        else        cout<<n+1<<'\n';
    }
    else
    {
        if(d<0)        x*=-1,d*=-1;
        for(int k=0;k<=n;k++)
        {
            ll t=1ll*k*x;
            ll l=sum[max(0,k-1)];
            ll r=sum[n-1]-sum[max(0ll,n-k-1)];
            l+=t/d,r+=t/d;t%=d;
            s[t].push_back({l,r});
        }ll ans=0;
        for(auto it:s)
        {
            sort(it.second.begin(),it.second.end(),cmp);
            ll l=it.second[0].l,r=it.second[0].r;
            for(auto v:it.second)
            {
                if(v.l>r)    ans+=r-l+1,l=v.l,r=v.r;
                else        r=max(v.r,r);
            }ans+=r-l+1;
        }cout<<ans<<'\n';
    }
    return 0;
}

AtCoder Beginner Contest 147

前言