2020牛客暑期多校第八场 | Moonglade

K.Kabaleo-Lite

难点在于题意读不清楚和爆long long，以及怎么用unsigned long long处理负数。

一开始一直搞不清是优先“人数”还是优先“利润”，后来看了回答才搞清楚是优先人数，然而已经WA飞了。。

然后这道题最大值会到$1e19$，只能用unsigned long long存，问题是怎么处理负数情况呢。可以开两个ull，遇到正数记在第一个变量里，遇到负数，把它取反之后记录在第二个变量里，然后判断这两个变量的大小来决定答案是否有负号。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+5;
const ll INF=0x3f3f3f3f3f3f3f3f;
int T,n;

ll A[N],B[N];
struct status{
    ll a,b;
};
vector<status>Q;
void solve(int caseNum)
{
    scanf("%d",&n);
    A[0]=0;
    for (int i=1;i<=n;i++)
    {
        scanf("%llu",&A[i]);
        A[i]+=A[i-1];
    }
    B[0]=INF;
    for (int i=1;i<=n;i++)
    {
        scanf("%llu",&B[i]);
        B[i]=min(B[i-1],B[i]);
    }
    Q.clear();
    for (int i=n;i>=1;i--)
    {
        while(!Q.empty() && Q.back().a<=A[i]) Q.pop_back();
        Q.push_back({A[i],B[i]});
    }
    ll sum=0;
    unsigned long long ans1=0,ans2=0;
    unsigned long long aa=0;
    for (auto now:Q)
    {
        if (now.a>=0)
            ans1+=1ll*now.a*(now.b-sum);
        else
            ans2+=1ll*(-now.a)*(now.b-sum);
        sum=now.b;
    }
    bool sig=0;
    unsigned long long ans;
    if (ans1>=ans2) ans=ans1-ans2;
    else
    {
        sig=1;
        ans=ans2-ans1;
    }
    printf("Case #%d: %lld ",caseNum,sum);
    if (sig) printf("-");
    printf("%llu\n",ans);
}
int main()
{
    cin>>T;
    for (int i=1;i<=T;i++) solve(i);
    return 0;
}

G.Game-SET

不知道怎么评价的一题。结论是只需要考虑前21个就可以了，那直接暴力肯定没问题。想不通为啥，也懒得证了。

然而直接写$O(T*n^3)$的暴力，找到解就return也一样能过。。

也不深究了，倒是对这种字符串的读入和处理方法可以学一下。

#include<bits/stdc++.h>
using namespace std;

const int N=300;

int A[N][4];

int T,n;

char s[100],o[100],p[100],q[100],r[100];

void Read(int x)
{
    scanf("%s",s);
    int len=strlen(s);
    for (int i=0;i<len;i++) if (s[i]=='[' || s[i]==']') s[i]=' ';
    sscanf(s,"%s%s%s%s",o,p,q,r);
    switch(o[1]){
        case 'n':A[x][0]=1; break;
        case 'w':A[x][0]=2; break;
        case 'h':A[x][0]=3; break;
        default:A[x][0]=0; break;
    }
    switch(p[0]){
        case 'd':A[x][1]=1; break;
        case 's':A[x][1]=2; break;
        case 'o':A[x][1]=3; break;
        default:A[x][1]=0; break;
    }
    switch(q[1]){
        case 'o':A[x][2]=1; break;
        case 't':A[x][2]=2; break;
        case 'p':A[x][2]=3; break;
        default:A[x][2]=0; break;
    }
    switch(r[0]){
        case 'r':A[x][3]=1; break;
        case 'g':A[x][3]=2; break;
        case 'p':A[x][3]=3; break;
        default:A[x][3]=0; break;
    }
}

bool judge(int a,int b,int c)
{
    for (int i=0;i<=3;i++)
    {
        if (A[a][i]==0 || A[b][i]==0 || A[c][i]==0) continue;
        int sum=A[a][i]+A[b][i]+A[c][i];
        if (sum!=6 && sum!=3 && sum!=9) return 0;
    }
    return 1;
}
void solve(int cs)
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) Read(i);
    for (int i=1;i<=min(21,n);i++)
        for (int j=i+1;j<=min(21,n);j++)
            for (int k=j+1;k<=min(21,n);k++)
            {
                if (judge(i,j,k))
                {
                    printf("Case #%d: %d %d %d\n",cs,i,j,k);
                    return;
                }
            }
    printf("Case #%d: -1\n",cs);
}
int main()
{
    cin>>T;
    for (int cs=1;cs<=T;cs++) solve(cs);
    return 0;
}

E.Enigmatic Partiton

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N=1e5+5,up=100;

LL sum[N+5],dp[N+5];

int T,l,r;

int main() {
    for (int l=up;l<=N/3;l++) {
        int m=l+1,r=l+2;
        for (int nl=1;nl*l<=N;nl++)
            for (int nm=3;nm*m+nl*l<=N;nm++)
                sum[nl*l+nm*m]+=(nm-1)/2;
        for (int nr=0;nr*r<=N;nr++)
            for (int nm=3;nm*m+nr*r<=N;nm++)
                sum[nr*r+nm*m]+=(nm-1)/2;
    }
    for (int i=1;i<up;i++) {
        memset(dp,0,sizeof(dp));
        int a[4];
        a[1]=i,a[2]=i+1,a[3]=i+2;
        dp[a[1]+a[2]+a[3]]=1;
        for (int i=1;i<=3;i++) {
            for (int j=a[1]+a[2]+a[3];j+a[i]<=N;j++)
                dp[j+a[i]]+=dp[j];
        }
        for (int i=1;i<=N;i++) sum[i]+=dp[i];
    }
    for (int i=1;i<=N;i++) sum[i]+=sum[i-1];
    cin>>T;
    for (int k=1;k<=T;k++) {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("Case #%d: %lld\n",k,sum[r]-sum[l-1]);
    }
    return 0;
}