2022RoboCom世界机器人开发者大赛-本科组(初赛)_2022 robocom 世界机器人开发者大赛-本科组

1、不要浪费金币

题目分析：

没啥好分析的，从前往后遍历就行

 C++代码如下：

#include<iostream>
using namespace std;
const int N=1010;
int a[N]; 
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    int sum=0,cnt=0;
    for(int i=1;i<=n;i++){
        if(sum+a[i]>m){//如果加上当前的金币数后sum>m，则需要去消费一次
        	cnt++;//消费次数+1
			sum=0;//sum重置为0
		}
        sum+=a[i];//加上当前的金币数
    }
    cout<<cnt<<endl;
    return 0;
}

2、智能服药助手

题目分析 ：

本题保证按照时间递增的顺序给出每个时间的服用药物计划，所以我们从前往后做就可以，不用考虑时间问题

用一个数组last[]，last[i]记录上一次服用药物i的时间

对于每个时间点，对当前时间点服用的药物进行一次时间判断即可

C++代码如下：

#include<iostream>
#include<cstring>
using namespace std;
const int N=1010;
int last[N],b[N];//last[i]表示上一次服用药物i的时间
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>b[i];//第i种药物服用的间隔时间为b[i]
    memset(last,-1,sizeof last);//初始化为-1
    while(m--){
        int t,k;
        cin>>t>>k;//在t时间服用k种药物
        while(k--){
            int x;
            cin>>x;
            //1、间隔时间为0  2、未服用过该药物  3、间隔时间足够了，都可以服用该药物
            if(b[x]==-1||last[x]==-1||t-last[x]>=b[x])last[x]=t;
            //否则不可服用
            else printf("Don't take %d at %d!\n",x,t);
        }
    }
    return 0;
}

 3、跑团机器人

题目分析：

一个字符串模拟题，详情看注释

 C++代码如下：

#include<iostream>
#include<cstring>
#include<map>
using namespace std;
map<int,int> cnt;//cnt[i]存储第i种骰子被掷的总数
int maxx,minn;//存储点数的最大最小值
void solve(string s){
    int i=0,n=s.size();
	int flag=1;//flag为当前指令的正负号,1为正,-1为负
    while(i<n){
        int pre=0,last=0;
        //读取数字字符,存在pre中,isdigit(c)判断c是否是数字字符,是就返回true 
        while(i<n&&isdigit(s[i]))
            pre=pre*10+s[i]-'0',i++;
        //如果数字后面是d,说明是这一个指令
        if(s[i]=='d'){
            if(pre==0)pre=1;//d前面没有数字时,默认为1 
            i++;
            //读取d后面的数字,存在last中
            while(i<n&&isdigit(s[i]))
                last=last*10+s[i]-'0',i++;
            //last面骰子的掷数增加pre
            cnt[last]+=pre;
            if(flag==1){//pre前面符号为正时
            	minn+=pre;//(pre*1最小)
                maxx+=pre*last;//(pre*last最大) 
            }else{//pre前面符号为负
            	minn-=last*pre;
                maxx-=pre;
            }
        }else{//读取完pre后停止在'+'或'-'或越界,说明是一个常量,更新maxx和minn
            maxx+=flag*pre;
            minn+=flag*pre;
        }
        if(i<n-1){//如果i停在'+'或者'-'，则更新flag，flag作为下一个数字前的符号 
            if(s[i]=='+')flag=1;
            else if(s[i]=='-')flag=-1;
            i++;
        }
    }
}
int main(){
    string s;
    cin>>s;
    solve(s);
    for(auto t:cnt)
        cout<<t.first<<" "<<t.second<<endl;
    cout<<minn<<" "<<maxx<<endl;
    return 0;
}

4、攻略分队

题目分析：

将6支队伍（可能不足六只）按要求分成两组，dfs深搜出所有可行的方案，然后用结构体存储起来，写一个cmp函数用于按照题意进行排序，最后输出所有方案种的第一个就可，不存在就输出GG

C++代码如下：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10;
int a[N][3],b[N];
int cnt;
struct node{
    int mt[2],zh[2],gb[2];//主坦克，指挥，工兵
    //mt[0],zh[0],gb[0]表示第1组的信息，mt[1],zh[1],gb[1]表示第2组的信息，
    int sum[2];//sum[0]：讨伐欧文的人数  sum[1]:讨伐亚特的人数
    string ch[2];//每一组的队伍编号用字符串记录,方便排序和输出
}ans[1200],s;
bool cmp(node x,node y){
    int t1=(x.zh[0]&&x.zh[1]&&x.gb[1]&&x.gb[0]);//方案x是否满足条件1
    int t2=(y.zh[0]&&y.zh[1]&&y.gb[1]&&y.gb[0]);//方案y是否满足条件1
    if(t1!=t2)return t1>t2;
    if(!t1){//条件1无法满足
        t1=(x.zh[0]&&x.zh[1]);//方案x是否满足条件2
        t2=(y.zh[0]&&y.zh[1]);//方案y是否满足条件2
        if(t1!=t2)return t1>t2;
    }
    //二者都满足条件1或两者都满足条件2或两者都不满足条件2，然后判断条件3
    if(abs(x.sum[0]-x.sum[1])!=abs(y.sum[0]-y.sum[1]))
        return abs(x.sum[0]-x.sum[1])<abs(y.sum[0]-y.sum[1]);
    //满足条件3的方案不唯一，然后判断条件4
    t1=(x.sum[0]>x.sum[1]);
    t2=(y.sum[0]>y.sum[1]);
    if(t1!=t2)return t1>t2;
    //满足条件4的方案不唯一，然后判断条件5
    return x.ch[0]<y.ch[0];
}
void dfs(int x,node y){
    if(x==7){//六支队伍都搜完了
        if(y.mt[0]>0&&y.mt[1]>0)//判断一下是否每组都有一个mt(主坦克)
            ans[cnt]=y,cnt++;//n记录满足条件的方案数
        return;
    }
    if(!b[x]){//如果第x支队伍不存在，则直接看下一个队伍
        dfs(x+1,y);
        return;
    }
    for(int i=0;i<=1;i++){//考虑将第x支队伍给第1组还是第2组
        node t=y;
        t.sum[i]+=b[x];//人数加上第x支队伍的人数
        t.mt[i]+=a[x][0];//mt数量加上第x支队伍的mt数
        t.gb[i]+=a[x][1];//gb数量加上第x支队伍的gb数
        t.zh[i]+=a[x][2];//zh数量加上第x支队伍的zh数
        t.ch[i]+=char(x+'0');//记录队伍编号
        t.ch[i]+=" ";//加上空格，方便输出
        dfs(x+1,t);
    }
}
int main(){
    for(int i=1;i<=6;i++)scanf("%d",&b[i]);
    for(int i=1;i<=6;i++){
        string ch;
        cin>>ch;
        //a[i][0],a[i][1],a[i][2]分别记录第i支队伍的mt数,gb数,zh数
        for(int j=0;j<3;j++)
            a[i][j]=(ch[j]-'0');
    }
    dfs(1,s);
    if(cnt){
        sort(ans,ans+cnt,cmp);//给所有方案排序
        string res1,res2;
        res1=ans[0].ch[0],res2=ans[0].ch[1];
        //不能有多余的空格，所以都要删除最后一个空格，然后再输出
        res1.erase(res1.end()-1),res2.erase(res2.end()-1);
        cout<<res1<<"\n"<<res2;
    }else printf("GG\n");
    return 0;
}

5、树与二分图

题目分析：

 给定一颗n个点n-1条边的树，问选择本没有边相连的两个点，使得将这两个点相连能够构成二分图，一共有多少种选择方案

判断一个图是否是二分图可以用染色法：一共有两种颜色，每个点和它的相邻节点颜色不相同，看是否可以染色成功，如果可以，则是二分图，否则不是

1、暴力做法可以骗到19分

枚举每两个点，如果这两个点之间没有边，则尝试往这两条边之间连一条边，如果连边之后是一个二分图的话，答案就加一

 暴力C++代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
vector<int> s[N];
typedef pair<int,int> PII;
map<PII,int> mp;
int color[N];
int dfs(int u,int c){//染色法判定二分图，颜色编号为1和2
    color[u]=c;
    for(int i=0;i<s[u].size();i++){//遍历u的所有邻点
        int j=s[u][i];
        if(!color[j]){//如果未被染色且染色失败，则返回false
            if(!dfs(j,3-c))return false;
        }else if(color[j]==c)//如果已经被染色但是颜色和u相同，也返回false
            return false;
    }
    return true;//染色成功，返回true
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        s[a].push_back(b);
        s[b].push_back(a);
        mp[{a,b}]++;
        mp[{b,a}]++;
    }
    int sum=0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(!mp[{i,j}]){//如果树中没有这条边，则加上这条边判断是否是二分图
                memset(color,0,sizeof color);
                s[i].push_back(j);
                s[j].push_back(i);
                if(dfs(i,1))sum++;
                s[i].pop_back();
                s[j].pop_back();
            }
    cout<<sum<<endl;
    return 0;
}

二分图：图中不含有奇数环

正解：由于给定的树是一颗n个点n-1条边的树，所以一定是一个二分图，因为没有环

所以可以先给树中所有节点染色，然后算出两种颜色各含有多少节点

颜色编号为1的节点个数为x

颜色编号为2的节点个数为y，y=n-x

如果让所有颜色不同的点之间都有边也不会影响该二分图，所以一共有x*y种情况，但由于树中一开始就有n-1条边，所以二者之差就是答案，即x*y-(n-1)

 C++代码如下：

#include<iostream>
#include<vector>
using namespace std;
const int N=1000010;
typedef long long LL;
vector<int> s[N];
int color[N];//颜色编号为1和2 
void dfs(int u,int c){
    color[u]=c;
    for(int i=0;i<s[u].size();i++){
        int j=s[u][i];
        if(!color[j])//如果未被染色就染色 
            dfs(j,3-c);
    }
}
int main(){
    int n,x=0,y=0;//x存储颜色为1的节点数,y存储颜色为2的节点数 
    cin>>n;
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        //添加一条无向边 
        s[a].push_back(b);
        s[b].push_back(a);
    }
    dfs(1,1);//染色，该题一定会染色成功 
    for(int i=1;i<=n;i++)
    	if(color[i]==1)x++;
    y=n-x;
    cout<<(LL)x*y-(n-1)<<endl;
    return 0;
}