竞赛讨论区 > 牛客IOI周赛24提高

牛客IOI周赛24提高

头像
(́安◞౪◟排‵)
发布于 2021-04-03 21:35:36 APP内打开
赞 2 | 收藏 0 | 回复3 | 浏览351

A

大模拟,没什么好说的
为了简化操作,运用c++STL
对于牌堆,明显可以用队列模拟
对于玩家的牌,用vector储存,出牌可直接调用库函数
对牌单独定义结构体吗,方便操作
对于名字,不要打一堆if

尽量所有函数式编程,尽量复用代码,缩短代码长度,减少调试难度

以下给出2个代码

std

#include<bits/stdc++.h>
using namespace std;
struct card{
    string col;
    string pattern;
    card(){};
    card(string a,string b): col(a),pattern(b){};
}consult;
int n,Round,direction=1;
string name[5]={"xiran","sanqiu","shixin"};
queue<card> pai;
vector<card> v[5];
void get_card(int x,int ad)
{
    while(ad--){
        if(pai.size()==0){ 
            puts("There are no cards to take");//无牌可拿 
            for(int i=0;i<3;i++){
                for(int j=0;j<v[i].size();j++)
                    cout<<v[i][j].col<<" "<<v[i][j].pattern<<" ";
                puts("");
            }
            exit(0);
        }
        v[x].push_back(pai.front());
        pai.pop();
    }
}
void next(int x){Round=((Round+x*direction)%3+3)%3;}
void discard(int i)
{
    card k= v[Round][i];
    consult=k;//参考牌替换
    pai.push(k);//加入牌堆
    v[Round].erase(v[Round].begin()+i,v[Round].begin()+i+1);//删除此玩家的手牌
    if(k.pattern=="Skip"){next(2);}
    else if(k.pattern=="Reverse"){direction=-direction;next(1);}
    else if(k.pattern=="Draw_Two"){next(1);get_card(Round,2);next(1);}
    else{next(1);}
}
void work()
{
    for(int i=0;i<v[Round].size();i++)
        if(v[Round][i].col==consult.col||v[Round][i].pattern==consult.pattern){
            discard(i);
            return;
        }
    //无牌可出
    while(1){
        get_card(Round,1);// 获得一张牌 
        int k=v[Round].size()-1;
        if(v[Round][k].col==consult.col||v[Round][k].pattern==consult.pattern){
            discard(k);
            return;
        }
    }
}
int main()
{

    consult=card("g","1");//规定初始参考牌为 绿色的1 
    cin>>n;
    for(int i=1;i<=n;i++){
        string a,b;
        cin>>a>>b;
        pai.push( card(a,b) );//加入牌堆
    }
    for(int i=0;i<3;i++) get_card(i,7);//每人获得7张的初始牌
    while(v[0].size()&&v[1].size()&&v[2].size()){
        work();
    }
    for(int i=0;i<3;i++) if(!v[i].size()) cout<<name[i]<<"\n";
    for(int i=0;i<3;i++){
        for(int j=0;j<v[i].size();j++)
            cout<<v[i][j].col<<" "<<v[i][j].pattern<<" ";
        puts("");
    }
    return 0;
}

审题人代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct node{
    char col;
    string act;
}card[4][10005];
node allofcard[10005];
bool aim[4][10005];
int nowcard[4];
int leacard[4];
void print()
{
    for(int j=1;j<=nowcard[1];j++)
    {
        if(aim[1][j]==0)
            cout<<card[1][j].col<<" "<<card[1][j].act<<" ";
    }
    cout<<endl;
    for(int j=1;j<=nowcard[2];j++)
    {
        if(aim[2][j]==0)
            cout<<card[2][j].col<<" "<<card[2][j].act<<" ";    
    } 
    cout<<endl;
    for(int j=1;j<=nowcard[3];j++)
    {
        if(aim[3][j]==0)
            cout<<card[3][j].col<<" "<<card[3][j].act<<" ";
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    int cnt=0;
    int now=1;
    for(int i=1;i<=n;i++)
    {
        if(now==4)
        {
            cin>>allofcard[++cnt].col;
            getchar();
            cin>>allofcard[cnt].act;
        }
        else 
        {
            cin>>card[now][++cnt].col;
            getchar();
            cin>>card[now][cnt].act;
            nowcard[now]++;
            if(cnt==7)
                now++,cnt=0;    
        }
    }
    if(now<=3)
    {
        printf("There are no cards to take\n");
        print();
        return 0;
    }
    for(int i=1;i<=3;i++)
        leacard[i]=nowcard[i];
    int order=1;
    char stacol='g';
    string stact="1";
    int peo=1;
    int pointo=1;
//    cout<<"——————————————————————————————"<<endl;
    while(1)
    {
        bool flag=false;
        for(int i=1;i<=nowcard[peo];i++)
        {
            if(!aim[peo][i]&&(card[peo][i].col==stacol||card[peo][i].act==stact))
            {
                aim[peo][i]=1;
                leacard[peo]--;
                flag=true;
                stacol=card[peo][i].col;
                stact=card[peo][i].act;
//                cout<<stacol<<" "<<stact<<endl;
                allofcard[++cnt].col=stacol;
                allofcard[cnt].act=stact;
                if(leacard[peo]==0)
                {
                    if(stact=="Draw_Two")
                    {
                        int now1=peo;
                        now1+=order;
                        if(now1>3)
                            now1=1;
                        if(now1<1)
                            now1=3;
                        if(pointo>cnt)
                        {
                            printf("There are no cards to take\n");
                            print();
                            return 0;
                        }
                        card[now1][++nowcard[now1]]=allofcard[pointo++];
                        leacard[now1]++;
                        if(pointo>cnt)
                        {
                            printf("There are no cards to take\n");
                            print();
                            return 0;
                        }
                        leacard[now1]++;
                        card[now1][++nowcard[now1]]=allofcard[pointo++];
                    }
                    if(peo==1)
                        cout<<"xiran"<<endl;
                    else if(peo==2)
                        cout<<"sanqiu"<<endl;
                    else 
                        cout<<"shixin"<<endl;
                    print();
                    return 0;
                }
                if(stact=="Skip")
                {
                    peo+=order;
                    if(peo>3)
                        peo=1;
                    if(peo<1)
                        peo=3;
                }
                else if(stact=="Reverse")
                {
                    order*=-1;
                }
                else if(stact=="Draw_Two")
                {
                    peo+=order;
                    if(peo>3)
                        peo=1;
                    if(peo<1)
                        peo=3;
                    if(pointo>cnt)
                    {
                        printf("There are no cards to take\n");
                        print();
                        return 0;
                    }
                    card[peo][++nowcard[peo]]=allofcard[pointo++];
                    leacard[peo]++;
                    if(pointo>cnt)
                    {
                        printf("There are no cards to take\n");
                        print();
                        return 0;
                    }
                    leacard[peo]++;
                    card[peo][++nowcard[peo]]=allofcard[pointo++];
                }
                break;
            }
        }
        if(leacard[peo]==0)
        {
            if(stact=="Draw_Two")
            {
                int now1=peo;
                now1+=order;
                if(now1>3)
                    now1=1;
                if(now1<1)
                    now1=3;
                if(pointo>cnt)
                {
                    printf("There are no cards to take\n");
                    print();
                    return 0;
                }
                card[now1][++nowcard[now1]]=allofcard[pointo++];
                leacard[now1]++;
                if(pointo>cnt)
                {
                    printf("There are no cards to take\n");
                    print();
                    return 0;
                }
                leacard[now1]++;
                card[now1][++nowcard[now1]]=allofcard[pointo++];
            }
            if(peo==1)
                cout<<"xiran"<<endl;
            else if(peo==2)
                cout<<"sanqiu"<<endl;
            else 
                cout<<"shixin"<<endl;
            print();
            return 0;
        }
        if(!flag)
        {
            if(pointo>cnt)
            {
                printf("There are no cards to take\n");
                print();
                return 0;
            }
            while(!(allofcard[pointo].col==stacol||allofcard[pointo].act==stact))
            {
                card[peo][++nowcard[peo]]=allofcard[pointo++];
                leacard[peo]++;
                if(pointo>cnt)
                {
                    printf("There are no cards to take\n");
                    print();
                    return 0;
                }
            }
            stacol=allofcard[pointo].col;
            stact=allofcard[pointo].act;
            pointo++;
            allofcard[++cnt].col=stacol;
            allofcard[cnt].act=stact;
//            cout<<stacol<<" "<<stact<<endl;
            if(stact=="Skip")
            {
                peo+=order;
                if(peo>3)
                    peo=1;
                if(peo<1)
                    peo=3;
            }
            else if(stact=="Reverse")
            {
                order*=-1;
            }
            else if(stact=="Draw_Two")
            {
                peo+=order;
                if(peo>3)
                    peo=1;
                if(peo<1)
                    peo=3;
                if(pointo>cnt)
                {
                    printf("There are no cards to take\n");
                    print();
                    return 0;
                }
                card[peo][++nowcard[peo]]=allofcard[pointo++];
                leacard[peo]++;
                if(pointo>cnt)
                {
                    printf("There are no cards to take\n");
                    print();
                    return 0;
                }
                leacard[peo]++;
                card[peo][++nowcard[peo]]=allofcard[pointo++];
            }
        }
        peo+=order;
        if(peo>3)
            peo=1;
        if(peo<1)
            peo=3; 
    }
}

B

众所周知,这是一道签到题
原式子可以化为: =
可把看作一个整体
判断是否矛盾即得答案

#include<bits/stdc++.h>
using namespace std;
int n;
int a[10005][10005];
int c[10005][10005];
int k[10005];
void work()
{
    cin>>n;
    memset(k,0,sizeof(k));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
            k[i]^=a[i][j];
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&c[i][j]);
    for(int j=1;j<=n;j++){
        int flag=-1,t;
        for(int i=1;i<=n;i++){
            t=c[i][j]^k[i];
            if(flag==-1)    flag=t;
            else if(flag!=t) {
                puts("NO");
                return;
            }
        }
    }
    puts("YES");
    return;
}
int T;
int main()
{
    cin>>T;
    while(T--)
        work();
    return 0;
}

C

考点:可持久化01树,LCA,贪心
对整个图建可持久化01树,其父版本是图上的父亲
对于每次询问,LCA得出其最近公共祖先
利用01树找到表演风格相差最大的城市
利用差分求出其他城市的异或和
最后通过贪心计算答案

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int tot;
int cnt;
int x[N];
int n,m,w;
int head[N];
int tr[N<<6][2];
int f[N][20],dep[N];
int siz[N<<6],Xor[N],rt[N];
struct Edge{
    int u,v;
}edge[N<<1];
void add(int x,int y){
    edge[++tot].u=head[x];
    edge[tot].v=y;
    head[x]=tot;
    return ;
}
void insert(int now,int pre,int val){
    for(int i=1<<30; i; i>>=1){
        bool k=val&i;
        tr[now][k^1]=tr[pre][k^1];
        tr[now][k]=cnt++;
        siz[tr[now][k]]=siz[tr[pre][k]]+1;
        now=tr[now][k];
        pre=tr[pre][k];
    }
}
void dfs(int now,int fa){
    f[now][0]=fa;
    dep[now]=dep[fa]+1;
    Xor[now]=Xor[fa]^x[now];
    for(int i=1; i<20; ++i) f[now][i]=f[f[now][i-1]][i-1];
    for(int i=head[now]; i; i=edge[i].u){
        int to=edge[i].v;
        if(to==fa) continue;
        rt[to]=cnt++;
        insert(rt[to],rt[now],x[to]);
        dfs(to,now);
    }
}
int query(int now,int pre,int val){
    int res=0;
    for(int i=1<<30; i; i>>=1){
        bool k=val&i;
        if(siz[tr[pre][k^1]]>siz[tr[now][k^1]]){
            res+=i;
            now=tr[now][k^1];
            pre=tr[pre][k^1];
        }else{
            now=tr[now][k];
            pre=tr[pre][k];
        }
    }
    return res;
}
int LCA(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=19; i>=0; --i){
        if(dep[f[x][i]]>=dep[y]) x=f[x][i];
        if(x==y) return x;
    }
    for(int i=19; i>=0; --i)
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    return f[x][0];
}
int solve(int u,int v,int p){
    int lca=LCA(u,v);
    int maxx=0,ans=0;
    int res=Xor[u]^Xor[v];
    maxx=max(maxx,query(rt[lca],rt[u],p));
    maxx=max(maxx,query(rt[lca],rt[v],p));
    maxx=max(maxx,x[lca]^p);
    res=res^x[lca]^maxx^p;
    for(int i=30; i>=0; --i){
        if((ans|(1<<i))>w) continue;
        if(res&(1<<i)) continue;
        ans|=(1<<i);
    }
    return ans|res;
}
int main(){
    scanf("%d%d%d",&n,&m,&w);
    for(int i=1,p,q; i<n; ++i){
        scanf("%d%d",&p,&q);
        add(p,q);
        add(q,p);
    }
    for(int i=1; i<=n; ++i) scanf("%d",&x[i]);
    cnt=1;
    rt[1]=cnt++;
    insert(rt[1],0,x[1]);
    dfs(1,0);
    for(int i=1,u,v,s; i<=m; ++i){
        scanf("%d%d%d",&u,&v,&s);
        printf("%d\n",solve(u,v,s));
    }
    return 0;
}

D

简单矩阵乘法
可以矩阵套矩阵,也可以只建一个矩阵
std写得是矩阵套矩阵的写法

第一个矩阵(最大的矩阵)

矩阵大小:
矩阵意义:对于代表从i走到j需要的最少体力
矩阵嵌套:对于是一个小矩阵,小矩阵定义参见下方

第二个矩阵(小矩阵)

矩阵大小:
矩阵意义:对于代表走过新路的第i条到第j条的最少体力

矩阵转移

见代码

std

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,a,b;
struct ppp {
    long long f[12][12];
    ppp operator*(const ppp x) {
        ppp y;
        memset(y.f,10,sizeof(y.f));
        for(long long i=0; i<=b; i++)
            for(long long j=i; j<=b; j++)
                for(long long k=i; k<=j; k++)
                    y.f[i][j]=min(y.f[i][j],f[i][k]+x.f[k][j]);
        return y;
    }
};
ppp Min(ppp x,ppp y) {
    for(long long i=0; i<=b; i++)
        for(long long j=0; j<=b; j++)
            x.f[i][j]=std::min(x.f[i][j],y.f[i][j]);
    return x;
}
struct oppo {
    ppp f[30][30];
    oppo operator*(const oppo x) {
        oppo y;
        memset(y.f,10,sizeof(y.f));
        for(long long k=1; k<=n; k++)
            for(long long i=1; i<=n; i++)
                for(long long j=1; j<=n; j++)
                    y.f[i][j]=Min(f[i][k]*x.f[k][j],y.f[i][j]);
        return y;
    }
} cs,ans;
void ksm(long long g) {
    memset(ans.f,10,sizeof(ans.f));
    for(long long i=1; i<=n; i++)
        ans.f[i][i].f[0][0]=0;
    while(g) {
        if(g&1) ans=ans*cs;
        g>>=1;
        cs=cs*cs;
    }
    long long st=LONG_LONG_MAX;
    for(long long j=1; j<=n; j++)
        st=min(st,ans.f[1][j].f[0][b]);
    if(st!=ans.f[0][0].f[0][0]) cout<<st<<"\n";
    else puts("-1");
}
int main() {
    cin>>n>>m>>k>>a>>b;
    memset(cs.f,10,sizeof(cs.f));
    for(long long i=1; i<=m; i++) {
        long long s,t,u;
        scanf("%lld%lld%lld",&s,&t,&u);
        for(long long j=0; j<=b; j++)
            cs.f[s][t].f[j][j]=u;
    }
    for(long long i=1; i<=a; i++) {
        long long s,t,u;
        scanf("%lld%lld",&s,&t);
        for(long long j=1; j<=b; j++) {
            scanf("%lld",&u);
            cs.f[s][t].f[j-1][j]=u;
        }
    }
    ksm(k+b);
    return 0;
}

后记

菜鸡出题人选择了一个不好的时间,好多小伙伴都来不了QWQ
想了很久还是决定添上A题(大模拟)
到现在没有发现什么锅,我很开心QWQ
希望大家享受这次的比赛吧

3条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐