【题目记录】——2021牛客暑期多校训练营10

亦凉 2022-09-05 06:00 175阅读 0赞

### 文章目录 ###

*  F Train Wreck 思维+树
 *  H War of Inazuma (Easy Version) 思维

题目集地址 [2021牛客暑期多校训练营10][2021_10]

# F Train Wreck 思维+树 #

题目地址[F Train Wreck][]  
题意：有一个类似于栈的火车通道，即按照后进先出的规则。给出颜色不全相同的火车车厢，管理员要将这些车厢按照给定的规则推入和推出通道。要求每次形成的火车排列要与之前出现过的每种情况不同。输出一种符合条件的解决方案。  
思路：栈操作其实可以看做树。每一次推出前形成的火车序列可以看做树的链。只需要每个树的结点的子节点各不相同，就可以保证有符合条件的解决方案。用数组储存每种颜色对应的车厢个数，用vector储存每个结点对应的子节点，并给子节点赋不同的颜色即可。

#include <bits/stdc++.h>
    using namespace std;
    const int N=2e6+5;
    char s[N];
    int a[N],cnt[N],last[N],ans[N];
    vector<int> G[N];
    int n;
    priority_queue<pair<int, int> > q;
    
    int main(){ 
        cin>>n;
        cin>>s+1;
        int dep=0,tot=0;
        //创建一棵括号序列树
        for(int i=1;i<=2*n;i++){ 
            if(s[i]=='('){ 
                dep++;//层数增加
                G[last[dep-1]].push_back(++tot);
                last[dep]=i;//从上一层回到下一层，开了一个新的子树，所以用i开一个新的G[i]储存它子结点 
            }
            else dep--;
        }
        for(int i=1;i<=n;i++){ 
            int x;
            cin>>x;
            cnt[x]++;
        }//记录车的颜色及对应的量数 
        for(int i=1;i<=n;i++) if(cnt[i]) q.push({ cnt[i],i});
        for (int i=0;i<=2*n;i++){ 
            if(G[i].size()>0){ 
                if(q.size()<G[i].size()){ 
                    cout<<"NO"<<endl;
                    return 0;
                }
                    vector<int> v;//用以减少循环次数 
                    for(int it=0;it<G[i].size();it++){ 
                    int id=q.top().second;//颜色 
                      ans[G[i][it]]=id;//it是推进的第it辆车 
                    cnt[id]--;//个数 
                       v.push_back(id);
                    q.pop();
                   }
                for(int it=0;it<v.size();it++) if(cnt[v[it]]) q.push({ cnt[v[it]],v[it]});
            }
        }
        cout<<"YES"<<endl;
        for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
        return 0;
    }

# H War of Inazuma (Easy Version) 思维 #

题目地址[H War of Inazuma (Easy Version)][H War of Inazuma _Easy Version]  
题意：A方和B方打仗，共有 2 n 2^n 2n个据点，标号为0~ 2 n − 1 2^n-1 2n−1，给出一个定义，如果两个据点标号的二进制表示只有1位对应位的值不同，则两个据点是相邻的。给出一个n，输出一个长度为 2 n 2^n 2n的01字符串，0表示该据点被A方占据，1该表示被B方占据，要求输出的字符串中每一个据点都满足以下条件，与该据点相邻且被占据该据点的势力占据的据点的数量不超过 ( n ) \\sqrt(n) (n)向上取整。  
思路：分析n==1，n==2，n==3，n==4的情况，合理推测，在n维空间的超立方体顶点有n个相邻的点，由于题目要求相邻的友军不超过根号n向上取整的个数，本人的思路是让相邻的全为敌军。分析发现，和一个点相邻的各点都不会相邻，而且n维空间的01字符串是n-1维的01字符串本身接上取反得到的字符串。取反操作可用^1实现。  
AC代码:

#include <bits/stdc++.h>
    using namespace std;
    int main(){ 
        vector<int> vt;
        int n;
        cin>>n;
        vt.clear();
        vt.push_back(0);
        vt.push_back(1);
        for(int j=1;j<=n;j++)
            for(int i=0;i<pow(2,j);i++)
                vt.push_back(vt[i]^1);
        for(int i=0;i<pow(2,n);i++) cout<<vt[i];
        return 0;
    }

[2021_10]: https://ac.nowcoder.com/acm/contest/11261
[F Train Wreck]: https://ac.nowcoder.com/acm/contest/11261/F
[H War of Inazuma _Easy Version]: https://ac.nowcoder.com/acm/contest/11261/H