2022 Robocom世界机器人开发者大赛 CAIP编程赛道 本科组-省赛 挨打记录+题解

2022 Robocom CAIP编程赛道 省赛题解

今天刚打完的省赛…马上退役的大三菜狗来摸一发题解，大佬勿喷QAQ。

今年和去年不同，五道题100分，可以说1、2、3的45分完全是白给的，4是真的恶心，5有点思维题的感觉，想出来就简单，想不出来就很难。

由于题目已经不记得了，只有代码能摸摸鱼发一下这样子…

第一题

题目大意是有

n

天，每天存

a[i]

元钱，钱有上限

K

，如果钱要超出上限了就去花了再存，问一共花了多少次钱？

很简单，根据题目模拟即可，维护当前的钱数

now

，如果加上当天存的钱超过了上限就去花一次。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,m;
LL a[1010]; 
int main()
{
    cin>>n>>m;
    LL now=0;
    LL ans=0;
    for (int i=1;i<=n;i++)
    {
        LL x;cin>>x;
        if (now+x>m)
        {
            ans++;
            now=0;
        }
        now+=x;
    }
    cout<<ans;
    return 0;
}

第二题

题目大意是病人要吃

n

种药，吃一共

m

次，每种药要相隔

t[i]

天才能吃第二次。给出

m

次记录，每次给出当前天的时间

t

和当天吃的药的数量

k

，然后是这些药的种类。如果能吃就吃，不能吃则输出

Don't take X at Y!

，其中

X

是药的种类，

Y

是当前的天数。

也是很简单的模拟题，根据题意直接模拟就完事了= =

唯一的坑点是第一次吃药是必定成功的，而如果不处理上次吃药的时间，第一次吃药也有可能会失败，我们只要把last数组初始化成负无穷即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1010;
int n,m;
LL t[N],last[N];
int main()
{
    cin>>n>>m;
    
    for (int i=1;i<=n;i++)    cin>>t[i];
    
    memset(last,-0x3f,sizeof(last));
    
    while(m--)
    {
        int now,k;cin>>now>>k;
        while(k--)
        {
            int x;cin>>x;
            if (now-last[x]<t[x])
            {
                printf("Don't take %d at %d!\n",x,now);
                continue;
            }
            else
            {
                last[x]=now;
            }
        }
    }
    
    return 0;
}

第三题

题目大意是给定一个字符串，字符串由一些项和加减号构成，这些项要么是

X

的数字类型，要么是

XdY

的骰子类型。数字类型代表直接对结果加或减，骰子类型代表投出

X

个

Y

面骰子，骰子的结果可能是1~Y，问表达式最终的最小结果和最大结果是什么，并输出每种骰子需要多少个。

这个题就稍微有点难度了，其实也是模拟题，考验大家对字符串的操作。

我们可以将整个字符串分成由加减号隔断的数个项，这些项如果是数字类型，那么他们对结果的影响是恒定的；如果是骰子类型，那么我们就要看前面的加减号是什么了：如果是加号，那么当投出的都为1的时候可以对应出最小结果，投出的都为Y的时候可以对应出最大结果；反之，如果是减号，那么投出的都为Y的时候可以对应出最小结果，投出的都为1的时候可以对应最大结果。

综上所述，我们只需要分出这些项之后分类讨论即可。由于我们是将这些项用加减号隔开，那么我们可以在读到加减号的时候对结果进行计算，维护一个X一个Y。对于每个项，如果我们读到了字符d，那么他就是骰子类型，我们之前读到的数就应该是X，后面的数就应该是Y，否则我们读到的就只是X。

除此之外，还需要记住最后一次读到的项也需要参与运算。我们可以在字符串后面接一个加号，这样就可以不需要特殊处理最后一项了。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1010;
string str;
LL eps;
LL up,down;
LL cnt[N];    //代表i面色子要用多少个 
int main()
{
    cin>>str;
    
    str="+"+str+"+";
    
    LL num=0,S=0;    
    bool flag=false;    //代表这个是不是色子 
    bool op=true;        //true代表加 false代表减 
    for (int i=0;i<str.size();i++)
    {
        auto t=str[i];
        if (t=='+' || t=='-')
        {
            if (!flag)    
            {
                if (op)    eps+=S;
                else eps-=S;
                S=0;
            }
            else
            {
                cnt[S]+=num;
                
                if (op)    
                {
                    up+=num*S;
                    down+=num;
                }
                else
                {
                    up-=num;
                    down-=num*S;
                }
                
            }
            S=0;num=0;        
            flag=false;    
            
            if (t=='+')    op=true;
            else op=false;
        }
        else if (t=='d')
        {
            if (str[i-1]=='+' || str[i-1]=='-')
                S=1;
            
            num=S;
            S=0;
            flag=true;
        }
        else
        {
            S=S*10+t-'0';
        }
    }
    
    for (int i=1;i<N;i++)
        if (cnt[i])
            cout<<i<<" "<<cnt[i]<<endl;
    
    cout<<down+eps<<" "<<up+eps;
    return 0;
}

第四题

    cout<<"GG";

这到底是什么玩意啊喂！出题组真有你的啊。

第五题

第五题还是蛮有意思的，虽然我读题读了半天才看懂。

题目大意是给定一棵树，然后问你选两个点，这两个点之间没有边相连 且 只选这两个点，然后连上边之后可以形成一个二分图，问你有多少种选法。

这个题一开始真给我看蒙了，原因很简单：这树不是本来就是二分图吗？？？读了半天题又模拟了一遍样例之后我才看懂，是让你选两个点连线之后仍然是二分图。

首先我们要明白什么是二分图。通俗点来说，如果在一个图里任选一个点，这个点染成黑色，然后将与这个点相连的所有点染成白色，再将与这些白色点相邻的所有点染成黑色，如此反复到最后，任意两个有边相邻的点的颜色都不同，这就是一个二分图（这不就是染色法判定二分图嘛）。

那么，我们也不难验证出，树因为不存在回路，那么本身就是一个二分图。如何选两个点后还能保证是二分图呢？我们可以先对树用染色法染色，然后在对于一个点，去找那些和他颜色不同的点连边，就不会破坏二分图的性质。

假如，我们设置根的节点为黑色，深度为1，那么我们不难想象出，由于树是一层一层的，所以深度为奇数的就都是黑色，所有深度为偶数的就都是白色。那么暴力做法很容易想象到，我们n^2枚举所有点，判断是否有边相连，且是否颜色不同即可。

代码已经删了 我只记得这个做法能拿19分。

既然已经想到了暴力做法，那么其实离能AC的写法已经差不远了。我们想一下，所有点其实只会和深度比自己大的异色点相连，而异色也就代表深度的奇偶性不同，同时有些边已经存在了不能重复连，这些边的数量就是当前层所有点的出度之和。

那么，我们先bfs出每一层的出度和每一层有多少个点，然后我们动态地维护深度更深的层有多少个点，每次算完当前层之后就将奇/偶层的点数和减去当前层的即可。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII; 
typedef long long LL;
const int N=1000010;
int n;
int depth[N],root,deepest;
int h[N],e[2*N],ne[2*N],idx;
int cnt[N];
int deg[N],Size[N],Sdeg[N];
//deg[i]为第i个点的出度 Size[i]为第i层有多少个点 Sdeg[i]为第i层点的出度之和
void bfs()
{
    memset(depth,0x3f,sizeof(depth));
    depth[root]=1;
    
    queue<int> q;q.push(root);
    while(q.size())
    {
        int t=q.front();q.pop();
                
        Size[depth[t]]++;
        for (int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if (depth[j]>depth[t]+1)
            {
                depth[j]=depth[t]+1;
                deg[t]++;
                deepest=max(deepest,depth[j]);
                q.push(j);
            }
        }
        Sdeg[depth[t]]+=deg[t];
    }
}
void add(int a,int b)
{
    e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
int main()
{
    cin>>n;
    
    memset(h,-1,sizeof(h));
    for (int i=1;i<=n-1;i++)
    {
        int a,b;cin>>a>>b;
        if (a>b)    swap(a,b);
        add(a,b);add(b,a);
        cnt[a]++;cnt[b]++;
    }
    
    root=-1;
    for (int i=1;i<=n;i++)
        if (cnt[i]==1)
        {
            root=i;break;    
        } 
        
    bfs();
    
    LL sumji=0,sumou=0;
    for (int i=1;i<=deepest;i++)
        if (i%2==1)    
            sumji+=Size[i];
        else 
            sumou+=Size[i];
            
    LL ans=0;
    for (int i=1;i<=deepest;i++)
        if (i%2==1)
        {
            ans=ans+Size[i]*sumou-Sdeg[i];
            sumji-=Size[i];
        }
        else
        {
            ans=ans+Size[i]*sumji-Sdeg[i];
            sumou-=Size[i];
        }        
    
    cout<<ans;    
    return 0;
}

最后摸了76分TAT没有AK我好菜。