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;
}
