Living-Dream 系列笔记 第17期

Problem

T1

/*
思路：分类讨论：
若k=0，则输出x+1；
若k>tot（x的位数），则输出1+k-tot个0+x；
否则输出10^k+x。
*/
#include<bits/stdc++.h>
using namespace std;

long long k,x,tot,ans=1; //开long long

int main(){
	cin>>k>>x;
	if(k==0){ cout<<x+1; return 0; } //情况1
	long long tmp=x;
	while(tmp) tot++,tmp/=10; //计算tot
	if(x==0) tot=1; //特判x=0
	//cout<<x<<'\n';
	if(k>tot){ //情况2
		cout<<1;
		for(int i=1;i<=k-tot;i++) cout<<0;
		cout<<x;
		return 0;
	}
	for(int i=1;i<=k;i++) ans*=10;
	cout<<ans+x; //情况3
	return 0;
}

T2

/*
思路：
循环模拟n次猜拳过程，
若AB出的拳不同，则对于A赢和B赢两种情况进行讨论，并更新得分；
然后将AB出拳周期下标+1即可。
*/
#include<bits/stdc++.h>
using namespace std;

int n,la,lb,pa,pb,sa,sb; //n，A/B周期长，A/B周期下标，A/B得分
int a[231],b[231]; //A/B周期

int main(){
	cin>>n>>la>>lb;
	for(int i=1;i<=la;i++) cin>>a[i];
	for(int i=1;i<=lb;i++) cin>>b[i];
	
	int pa=1,pb=1;
	for(int i=1;i<=n;i++){
		if(a[pa]!=b[pb]){ //若出拳不同
			if(a[pa]==0&&b[pb]==1||a[pa]==0&&b[pb]==4||a[pa]==1&&b[pb]==2||a[pa]==1&&b[pb]==4||a[pa]==2&&b[pb]==0||a[pa]==2&&b[pb]==3||a[pa]==3&&b[pb]==0||a[pa]==3&&b[pb]==1||a[pa]==4&&b[pb]==2||a[pa]==4&&b[pb]==3) sb++; //B赢
			else sa++; //A赢
		}
		pa++; if(pa>la) pa=1; //更新A下标
		pb++; if(pb>lb) pb=1; //更新B下标
		//cout<<pa<<' '<<pb<<'\n';
	}
	cout<<sa<<' '<<sb;
	return 0;
}

T3

/*
思路：
首先观察样例可知朝内则左减右加，朝外则左加右减；
于是对于第z条指令，先令s=s%n；
若情况1：该指令朝内且向右或朝外且向左，则令下标p=(p+s)%n；
否则情况2：令p=(p-s)%n+n；
为了方便处理，我们可以从0下标开始。
*/
#include<bits/stdc++.h>
using namespace std;

int n,m,p=0;
struct node{ //存储小人的名字和朝向
	string name;
	int dir;
}a[100031];

int main(){
	//freopen("P1563_4.in","r",stdin);
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>a[i].dir>>a[i].name; //0下标
	//cout<<mod(2,1);
	for(int i=1,d,x;i<=m;i++){
		cin>>d>>x;
		x%=n;
		//cout<<d<<' '<<x<<'\n'; 
		if(a[p].dir==0&&d==0){ //情况2
			p=(p-x<0?p-x+n:p-x);
			//if(p<0) p+=(abs(p)/n+1)*n;
		}
		else if(a[p].dir==0&&d==1) p=(p+x>=n?p+x-n:p+x); //情况1
		else if(a[p].dir==1&&d==0) p=(p+x>=n?p+x-n:p+x); //情况1
		else{ //情况2
			p=(p-x<0?p-x+n:p-x);
			//if(p<0) p+=(abs(p)/n+1)*n;
		}
		//cout<<p<<'\n';
	}
	cout<<a[p].name;
	return 0;
}

T4

/*
思路：考虑贪心，为了使等待时间更短，我们应当将接水时间更短的人排在靠前位置；
因此，仅需对接水时间排序，并计算等待时间总和即可。
*/
#include<bits/stdc++.h>
using namespace std;

int n;
struct node{ //需要使用结构体排序
	int x,id;
}t[1031];
double avg; //要用double

bool cmp(node a,node b){
	return a.x<b.x;
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>t[i].x,t[i].id=i;
	sort(t+1,t+n+1,cmp);
	for(int i=1;i<=n;i++) cout<<t[i].id<<' ';
	cout<<'\n';
	for(int i=1;i<=n;i++) avg+=(double)t[i].x*(double)(n-i); //注意对于第i个人他的等待时间为t{i-1}*(n-i)
	//cout<<avg<<'\n';
	cout<<setprecision(2)<<fixed<<avg/(double)n; //保留两位小数
	return 0;
}

T5

/*
思路：
遍历n个彩票号码，
对于第i个号码，
遍历中奖号码，
记录相等的个数，
将对应的奖项获得数目更新即可。
*/
#include<bits/stdc++.h>
using namespace std;

int n;
int num[7]; //中奖号码
int p[1031][7]; //n个彩票号码
int tot[7]; //每个奖项的获得数目

int main(){
	cin>>n;
	for(int i=0;i<7;i++) cin>>num[i];
	for(int i=1;i<=n;i++){
		for(int j=0;j<7;j++) cin>>p[i][j];
		int cnt=0;
		for(int j=0;j<7;j++) //遍历中奖号码
			for(int k=0;k<7;k++) //遍历当前彩票号码
				if(p[i][k]==num[j]) cnt++; //记录相等个数
		tot[7-cnt]++; //更新获得奖项数目
	}
	for(int i=0;i<7;i++) cout<<tot[i]<<' ';
	return 0;
}

T6

/*
思路：
我们知道，一个满足第一个条件的首领，一定是所有这个品种牛中的第一个，同时它名单的右端点一定包含了这个品种的最后一头牛；
因此我们可以先找出字符序列中两种牛的第一个和最后一个。
同时我们又知道，一个满足第二个条件的首领，它的名单一定包含了另一个品种牛的首领；
因此我们遍历字符序列，若有一头牛满足他的名单包含另一品种牛的首领，则令答案累加。
同时需要注意可能漏掉两个品种的首领都满足第一个条件的情况，需要单独特判。
*/
#include<bits/stdc++.h>
using namespace std;

int n,ans,len;
char cow[200031];
int ed[200031];
int g,h,G,H;
bool gg,hh;

int main(){
	cin>>n>>(cow+1);
	len=strlen(cow+1);
	for(int i=1;i<=n;i++) cin>>ed[i];
	
	for(int i=1;i<=len;i++){ //找第一个
		if(cow[i]=='G'&&!g) g=i;
		if(cow[i]=='H'&&!h) h=i;	
	}
	for(int i=len;i>=1;i--){ //找最后一个
		if(cow[i]=='G'&&!G) G=i;
		if(cow[i]=='H'&&!H) H=i;
	}
	
	for(int i=1;i<=n;i++){
		if(cow[i]=='H'){ 
			if(ed[i]>=g&&i<=g&&ed[g]>=G){ //若它包含另一品种的首领
				ans++;
				if(i==h) hh=1; //标记
			}
		}
		else{
			if(ed[i]>=h&&i<=h&&ed[h]>=H){
				ans++;
				if(i==g) gg=1;
			}
		}
	}
	if(ed[h]>=H&&ed[g]>=G&&!gg&&!hh) ans++; //若两个品种的首领都满足第一个条件
	cout<<ans;
	return 0;
}