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我好菜。
版权归原作者 林梦落 所有， 如有侵权，请联系我们删除。