2020牛客暑期多校训练营(第八场)
in 牛客多校多校训练 with 0 comment

2020牛客暑期多校训练营(第八场)

in 牛客多校多校训练 with 0 comment

摘要

/ABCDEFGHIJK
场上
zyj
wrf
lmj

题目

A.All-Star Game

zyj (赛后) +3

题意

题解

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
#define pii pair<int,int>
#define fr first
#define se second
typedef long long ll;
const int maxn=(int)2e6+100;
const int mod=(int)1e9+7;
int fa[maxn],sz[maxn],tot;
int n,m,q,ans,num;
vector<pii> v[maxn];map<pii,int> st;
struct node{int l,r,x,y;}p[maxn];
int find(int x){return fa[x]==x?x:find(fa[x]);}
void join(int x,int y,int cnt){
    x=find(x);y=find(y);
    if(x==y) return;
    if(sz[x]<sz[y]) swap(x,y);
    if(x>n) num-=(sz[x]==1);
    if(y>n) num-=(sz[y]==1),ans--;
    fa[y]=x;sz[x]+=sz[y];v[cnt].pb({x,y});
}
void rejoin(int cnt){
    while(!v[cnt].empty()){
        pii o=v[cnt].back();v[cnt].pop_back();
        int x=o.fr,y=o.se;
        fa[y]=y;sz[x]-=sz[y];
        if(x>n) num+=(sz[x]==1);
        if(y>n) num+=(sz[y]==1),ans++;
    }
}
void solve(int l,int r,int L,int R,int op){
    rep(i,l,r){
        if(p[i].l<=L&&R<=p[i].r)
            join(p[i].x,p[i].y,op),swap(p[i],p[l++]);
    }
    if(L==R){
        printf("%d\n",num?-1:ans);rejoin(op);return;
    }int M=(L+R)>>1,m=l-1;
    rep(i,l,r) if(p[i].l<=M) swap(p[i],p[++m]);
    solve(l,m,L,M,op+1);m=l-1;
    rep(i,l,r) if(p[i].r>M) swap(p[i],p[++m]);
    solve(l,m,M+1,R,op+1);rejoin(op);
}
int main(){
    scanf("%d%d%d",&n,&m,&q);
    rep(i,1,n){
        int k;scanf("%d",&k);
        while(k--){
            int x;scanf("%d",&x);st[{x,i}]=1;
        }
    }
    rep(i,1,q){
        int x,y;scanf("%d%d",&x,&y);
        if(st[{x,y}]) p[++tot]={st[{x,y}],i-1,x+n,y},st[{x,y}]=0;
        else st[{x,y}]=i;
    }
    for(auto u:st) if(u.se) p[++tot]={u.se,q,u.fr.fr+n,u.fr.se};
    rep(i,1,n+m) fa[i]=i,sz[i]=1;
    ans=num=m;solve(1,tot,1,q,0);
}

B.Bon Voyage

题意

题解

代码


C.Cinema

题意

题解

代码


D.Disgusting Relationship

题意

题解

代码


E.Enigmatic Partition

zyj (赛后)

题意

数$n$的拆分,需要满足最大和最小差2,相邻两个数的差值不能超过1。
$f(n)$表示这种拆分的个数。给定$l, r$, 求区间和。
$T \leq 10,000 . \quad 1 \leq l \leq r \leq 100,000$

题解

首先可以确定的是最终的拆分必定形如$(l,l+1,l+2)$这样的形式。
容易想到可以通过枚举拆分后数的个数和$l$来更新答案,但是这样显然会$TLE$。
通过观察暴力的代码可以发现,我们在枚举第三层的时候其实很微妙,尝试通过差分解决。

假定$n$为拆分得到的数的个数,$m$为拆分序列的和(也即题中的$n$)。
当$l=2,m=6$时,可以得到:

m15161718192021222324
4个4 234444
3个4 223444233444
2个4 222344223344233344
1个4222234222334223334233334
num1122211000
差分10100-10-100
隔项差分1000-1-10001
表达式$l*n+3$000$(l+1)*n+1$$(l+1)*n+2$000$(l+2)*n$

于是我们预处理出来所有的差分和隔项差分即可还原$num$数组。

代码

暴力:

void precal(){
    rep(l,1,maxn/3){
        int m=l+1,r=l+2;
        for(int nl=1;nl*l<=maxn;++nl)
            for(int nm=3;nm*m+nl*l<=maxn;++nm) f[nm*m+l*nl]+=(nm-1)/2;
        for(int nr=0;nr*(l+2)<=maxn;++nr)
            for(int nm=3;nm*m+nr*l+2*nr<=maxn;++nm) f[nm*m+l*nr+2*nr]+=(nm-1)/2;
    }
    rep(i,1,maxn) f[i]+=f[i-1];
}

差分:

void precal(){
    rep(m,3,maxn)for(int am=m;am<=maxn;am+=m)
        c[am+3]++,c[am+m+1]--,c[am+2*m]++,c[am+m+2]--;
    rep(i,3,maxn) c[i]+=c[i-2];
    rep(i,1,maxn) c[i]+=c[i-1],f[i]=f[i-1]+c[i];
}

F.Factorio

题意

题解

代码


G.Game SET

wrf (03:07:19) +0

题意

题解

代码

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int inf=0x3f3f3f3f;
const ll mint=0x7fffffff;
const ll linf=1000000000000000000LL;
const ll mod=998244353LL;
const double eps=1e-3;
const int N=100020;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
map<int,vector<pair<int,int> > > q;
char ch[4][N];
char t[4][4][10]=
{
    {"*","one","two","three"},
    {"*","diamond","squiggle","oval"},
    {"*","solid","striped","open"},
    {"*","red","green","purple"}
};
 
short v[256];
 
bool solve()
{
    int n=read();
    for(int i=0;i<n;i++)
    {
        char c='\0';
        int j=-1,s=0;
        while((c=getchar()) && c!='\n')
        {
            if(c=='[') j++;
            else if(c!=']')
            {
                ch[j][s]=c;
                s++;
            }
            else {ch[j][s]='\0';s=0;}
        }
        v[i]=0;
 
        for(int j=0;j<4;j++)
        {
            v[i]*=8;
            for(int k=0;k<4;k++)
            {
                if(0==strcmp(ch[j],t[j][k])) v[i]+=(k==0?7:(1<<(k-1)));
            }
        }
    }
 
    for(int i=0;i<n-2;i++)
    {
        for(int j=i+1;j<n-1;j++)
        {
            for(int k=j+1;k<n;k++)
            {
                int t=v[i]|v[j]|v[k];
                bool f=true;
                 
                for(int l=0;l<4;l++) {if(t%8!=1 && t%8!=2 && t%8!=4 && t%8!=7) {f=false;break;} t>>=3;}
                if(f)
                {
                    printf("%d %d %d\n",i+1,j+1,k+1);
                    return true;
                }
            }
        }
    }
    return false;
}
 
int main(void)
{
    int _=read();
    for(int i=1;i<=_;i++)
    {
        printf("Case #%d: ",i);
        if(!solve()) printf("-1\n");
    }
}

H.Hard String Problem

题意

题解

代码


I.Interesting Computer Game

lmj (04:03:42) +8

题意

从n对里选数,每对只能选一个,不能选已经选过的点,求选的最多数量。

题解

多显然的二分图匹配,网络流即可
可以发现如果形成了一个环,那么这个环所包含的数可以全选并且不会影响到其他数的选取,然后可以发现对于链来说有一个数无法选择,所以求有多少个链即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n;
inline int read(){
    int x=0;int flag=0;char c=getchar();
    while(!isdigit(c)){
        if(c=='-') flag=1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    } return flag?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int Case=0;
pair<int,int> p[maxn];
int ls[maxn*2],vis[maxn];
int ans[maxn];
int fa[maxn];
vector<int> v[maxn];
void dfs(int past,int now)
{
    //printf("%d %d\n",past,now);
    vis[now]=1;
    fa[now]=past;
    for(int i=0;i<v[now].size();i++){
        int u=v[now][i];
        if(u==past)continue;
        if(vis[u]==1){
            if(ans[u]){
                ans[now]=1;
                continue;
            }
            int tmp=now;
            ans[tmp]=1;
            //printf("%d %d\n",now,u);
            while(tmp!=u){
                tmp=fa[tmp];
                ans[tmp]=1;
            }
        }else{
            dfs(now,u);
            if(!ans[u]){
                ans[u]=1;
            }else{
                ans[now]=1;
            }
        }
    }
}
 
void solve(){
    n=read();
    int cnt=0;
    rep(i,0,2*n) vis[i]=0,fa[i]=i,ans[i]=0;;
    rep(i,1,2*n) v[i].clear();
    rep(i,1,n){
        int a=read(),b=read();
        p[i]={a,b};
        ls[++cnt]=a;ls[++cnt]=b;
    }
    sort(ls+1,ls+1+cnt);int tot=unique(ls+1,ls+1+cnt)-ls-1;
    rep(i,1,n){
        int &a=p[i].first,&b=p[i].second;
        a=lower_bound(ls+1,ls+1+tot,a)-ls;
        b=lower_bound(ls+1,ls+1+tot,b)-ls;
        //printf("---%d %d\n",a,b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=1;i<=tot;i++){
        if(!vis[i]){
            dfs(0,i);
        }
    }
     
    int sum=0;
    for(int i=1;i<=tot;i++){
        sum+=ans[i];
    }
    printf("Case #%d: %d\n",++Case,sum);
}
int main(){
    int T;cin>>T;
    while(T--) solve();
}

J.Jumping Points

题意

题解

代码


K.Kabaleo Lite

lmj (01:34:50) +2

题意

有n种食物,每种有$a_i$的收益,有$b_i$的数量,每个顾客至少吃一种食物,并且只能从第一种开始连续吃,求在满足最多顾客数量的情况下的最大收益

题解

显然最多顾客为$b[1]$,那么显然$a[1]*b[1]$的收益是有的,然后就是判断哪些人往后吃获得更大收益。从2开始遍历,求得从上一次吃到这次之间的收益和,以及能吃到这个位置的人数,如果收益超过0,那么就选这么多人吃到这里即可。
卡longlong,然后write还写错了,忘记负数情况

代码

#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=2e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
ll a[N],b[N];
void write(__int128 x)
{
    if (x < 0) x = ~x + 1, putchar('-');
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&b[i]);
    }
    __int128 ans=a[1]*b[1];
    __int128 now=0;
    __int128 sum=b[1];
    __int128 minn=b[1];
    for(int i=2;i<=n;i++){
        now+=a[i];
        if(b[i]<minn){
              minn=b[i];
        }
        if(now>=0){
            ans+=now*minn;
            now=0;
        }
    }
    write(sum);
    printf(" ");
    write(ans);
    printf("\n");
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    int cas=0;
    while(T--){
        printf("Case #%d: ",++cas);
        work();
    }
}
Responses