吴易繁的博客
Simulation
吴易繁 LV5 化神期 LV 4 @ 2024-10-18 20:02:47

U $15$ B $01$ F. Censoring

这道题目我们很容易想到：

while(s.find(t)) s.erase(s.find(t));

但是！会超时！

那我们该怎么办呢？

我们知道，删除后面字符是 $O(1)$ 的！

所以我们可以逐个扫描字符，每次将字符加进 $a$ 里，若 $a$ 里有 $t$ 了，就删除。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int main(){
	freopen("censor.in","r",stdin);
	freopen("censor.out","w",stdout);
	string s,t,a;
	cin>>s>>t;
	for(int i=0;i<s.size();i++){
		a+=s[i];
		if(a.size()>=t.size()&&a.substr(a.size()-t.size(),a.size()-1)==t) a.erase(a.size()-t.size(),t.size());
	}
	cout<<a;
	return 0;
}

U $16$ B $02$ D. Block Game

这道题目我们可以考虑每一组单词用到的最大字母数量，那么要用到的最小字母块即为每一组单词的最大字母数量的和

#include<bits/stdc++.h>
using namespace std;
int a[30],b[30],c[30],d[30];
int main(){
	freopen("blocks.in","r",stdin);
	freopen("blocks.out","w",stdout);
	int n;
	cin>>n;
	while(n--){
		for(int i=1;i<=26;i++) b[i]=0;
		for(int i=1;i<=26;i++) c[i]=0;
		for(int i=1;i<=26;i++) d[i]=0;
		string s1,s2;
		cin>>s1>>s2;
		for(int i=0;i<s1.size();i++) c[s1[i]-'a'+1]++;
		for(int i=0;i<s2.size();i++) d[s2[i]-'a'+1]++;
		for(int i=1;i<=26;i++) b[i]=max(c[i],d[i]);
		for(int i=1;i<=26;i++) a[i]+=b[i];
	}
	for(int i=1;i<=26;i++) cout<<a[i]<<endl;
}

U $16$ B $02$ F. Circular Barn

对于这道题目我们可以模拟从1~n的每个门进去的情况，更新记录最短距离即可。

#include<bits/stdc++.h>
using namespace std;
int a[1010];
int main(){
	freopen("cbarn.in","r",stdin);
	freopen("cbarn.out","w",stdout);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	long long ans=1e9;
	for(int i=1;i<=n;i++){
		long long j=i,cnt=0,sum=0;
		for(int k=1;k<=n-1;k++){
			j++;
			if(j==n+1) j=1;
			cnt++;
			sum+=cnt*a[j];
		}
		ans=min(ans,sum);
	}
	cout<<ans;
	return 0;
}

U $16$ B $03$ J. Mowing the Field

对于这道题目我们可以枚举隔得时间。

然后在每次枚举时开一个二维数组，模拟移动过程即可。

#include<bits/stdc++.h>
using namespace std;
int a[2010][5],st[2010][2010],dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int main(){
	freopen("mowing.in","r",stdin);
	freopen("mowing.out","w",stdout); 
	int n,y;
	cin>>n;
	char x;
	for(int i=1;i<=n;i++){
		cin>>x>>y;
		if(x=='N') a[i][0]=0;
		else if(x=='E') a[i][0]=1;
		else if(x=='S') a[i][0]=2;
		else if(x=='W') a[i][0]=3;
		a[i][1]=y;
	}
	int i1=1000,j1=1000,mn=0x3f3f3f3f,cnt=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=a[i][1];j++){
			cnt++;
			i1+=dx[a[i][0]],j1+=dy[a[i][0]];
			if(st[i1][j1]) mn=min(mn,cnt-st[i1][j1]);
			st[i1][j1]=cnt;
		}
	}
	if(mn==0x3f3f3f3f) cout<<-1;
	else cout<<mn;
	return 0;
}

U $17$ B $01$ D. The Lost Cow

模拟整个行走过程即可。

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("lostcow.in","r",stdin);
	freopen("lostcow.out","w",stdout);
	int x,y;
	cin>>x>>y;
	int nx=1,cnt=1,sum=0;
	while(1){
		if(nx==1&&x<=y&&y-x<=cnt){
			sum+=y-x;
			cout<<sum;
			return 0;
		}
		else if(nx==-1&&x>y&&x-y<=cnt){
			sum+=x-y;
			cout<<sum;
			return 0;
		}
		else{
			cnt*=2;
			sum+=cnt;
			nx*=-1;
		}
	}
	return 0;
}

U $17$ B $02$ D. The Bovine Shuffle

对于这道题目我们可以反推出答案，答案是 $c[a[a[a[i]]]]$ 。

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int a[N],b[N],c[N],d[N];
int main(){
	freopen("shuffle.in","r",stdin);
	freopen("shuffle.out","w",stdout);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	for(int i=1;i<=n;i++) c[i]=b[a[i]];
	for(int i=1;i<=n;i++) d[i]=c[a[i]];
	for(int i=1;i<=n;i++) cout<<d[a[i]]<<endl;
	return 0;
}

U $18$ B $01$ OC. Team Tic Tac Toe

因为题目中的棋盘是 $3×3$ 的，因此暴力枚举即可。

本题的重点就是给定三个字母，如何判断有没有奶牛或队伍可以通过这三个字母取胜。

判断奶牛能否取胜较为简单，只需判断三个字母是否都相等即可。

如果某支队伍能取胜，那么这三个字母中一定有且仅有两种字母，而且必定是一种字母有两个，另一种字母只有一个。那么反过来，只要有一种字母在这三个字母中出现了（且仅出现了）两次，即三个字符中有且仅有两个相等，那么就有一支队伍可以获胜。

#include<bits/stdc++.h>
using namespace std;
char c[10];
int a[30],b[30][30],ans_1,ans_2;
void f(int x,int y,int z){
	if(c[x]==c[y]&&c[y]==c[z]){
		a[c[x]-64]=1;
		return;
	}
	if(c[x]==c[y]){
		int mn=min(c[x],c[z])-64;
		int mx=max(c[x],c[z])-64;
		b[mn][mx]=1;
		return;
	}
	if(c[z]==c[y]){
		int mn=min(c[x],c[z])-64;
		int mx=max(c[x],c[z])-64;
		b[mn][mx]=1;
		return;
	}
	if(c[x]==c[z]){
		int mn=min(c[y],c[z])-64;
		int mx=max(c[y],c[z])-64;
		b[mn][mx]=1;
		return;
	}
}
int main(){
	freopen("tttt.in","r",stdin);
    freopen("tttt.out","w",stdout);
	for(int i=1;i<=9;i++) cin>>c[i];
	f(1,2,3);
	f(4,5,6);
	f(7,8,9);
	f(1,4,7);
	f(2,5,8);
	f(3,6,9);
	f(1,5,9);
	f(3,5,7);
	for(int i=1;i<=26;i++) ans_1+=a[i];
	for(int i=1;i<=26;i++) for(int j=1;j<=26;j++) ans_2+=b[i][j];
	cout<<ans_1<<endl<<ans_2;
	return 0;
}

U $18$ B $02$ D. The Bucket List

对于这道题目我们可以对每个输入的数据这样操作：

将 $s$ ~ $f$ 的数组 $+=b$ 。

最后求最大值即可。

#include<bits/stdc++.h>
using namespace std;
int st[1010];
int main(){
	freopen("blist.in","r",stdin);
	freopen("blist.out","w",stdout);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int s,f,b;
		cin>>s>>f>>b;
		for(int j=s;j<=f;j++) st[j]+=b;
	}
	int ans=0;
	for(int i=1;i<=1000;i++) ans=max(ans,st[i]);
	cout<<ans;
	return 0;
}

U $19$ B $03$ F. Measuring Traffic

对于每个路段，有三种情况。

上车。此时它的车流区间是前一个区间的最大值加上这里上车的最小值、前一个区间的最小值加上上车的最大值。
下车。此时它的车流区间是前一个区间的最大、最小值减去这里下的最大、最小值。
无操作。此时区间可以被前面的区间限制，最小值取两者中大的，最大值取两者中较小的。

直接按照题意模拟即可。对于开头的流量，我们反向再扫一边即可。

#include<bits/stdc++.h>
using namespace std;
int a[110],b[110];
int main(){
	freopen("traffic.in","r",stdin);
	freopen("traffic.out","w",stdout);
	int n;
	cin>>n;
	string s[110];
	for(int i=1;i<=n;i++) cin>>s[i]>>a[i]>>b[i];
	int l=0,r=1e9;
	for(int i=n;i>=1;i--){
		if(s[i]=="none") l=max(l,a[i]),r=min(r,b[i]);
		else if(s[i]=="off") l+=a[i],r+=b[i];
		else l-=b[i],r-=a[i],l=max(0,l);
	} 
	cout<<l<<" "<<r<<endl;
	l=0,r=1e9;
	for(int i=1;i<=n;i++){
		if(s[i]=="none") l=max(l,a[i]),r=min(r,b[i]);
		else if(s[i]=="on") l+=a[i],r+=b[i];
		else l-=b[i],r-=a[i],l=max(0,l);
	} 
	cout<<l<<" "<<r;
	return 0;
}

U $20$ B $03$ . Stack in a rut

用a数组来表示往东方向走的牛，用b数组来表示往东方向走的牛，再来排序。

排序后我们就需判断是否无限的情况，若$b[t].x<a[i].x||a[i].y<b[t].y||sl[b[t].idx]!=2e9||b[t].x-a[i].x==a[i].y-b[t].y$，

那么就说明这头牛能吃的草是无限的，反之则说明这头牛能吃的的草是有限的。

#include<bits/stdc++.h>
using namespace std;
int st[60];
struct P{
	int x,y,idx;
};
P a[60],b[60];
bool cmp_a(P a,P b){
	return a.y<b.y;
}
bool cmp_b(P a,P b){
	return a.x<b.x;
}
int main(){
	freopen("stack.in","r",stdin);
	freopen("stack.out","w",stdout);
	int n,j=0,k=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		char f;
		int nx,ny;
		cin>>f;
		cin>>nx>>ny;
		if(f=='E') a[++j].x=nx,a[j].y=ny,a[j].idx=i;
		else b[++k].x=nx,b[k].y=ny,b[k].idx=i;
	}
	sort(a+1,a+1+j,cmp_a);
	sort(b+1,b+1+k,cmp_b);
	for(int i=1;i<=n;i++) st[i]=2e9;
	for(int i=1;i<=j;i++){
		for(int t=1;t<=k;t++){
			if(b[t].x>=a[i].x&&a[i].y>=b[t].y&&st[b[t].idx]==2e9&&b[t].x-a[i].x!=a[i].y-b[t].y){
				if(b[t].x-a[i].x<=a[i].y-b[t].y) st[b[t].idx]=a[i].y-b[t].y;
				else{
					st[a[i].idx]=b[t].x-a[i].x;
					break;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
        if(st[i]!=2e9) cout<<st[i]<<endl;
        else cout<<"Infinity"<<endl;
    }
	return 0;
}

Simulation

U $15$ B $01$ F. Censoring

U $16$ B $02$ D. Block Game

U $16$ B $02$ F. Circular Barn

U $16$ B $03$ J. Mowing the Field

U $17$ B $01$ D. The Lost Cow

U $17$ B $02$ D. The Bovine Shuffle

U $18$ B $01$ OC. Team Tic Tac Toe

U $18$ B $02$ D. The Bucket List

U $19$ B $03$ F. Measuring Traffic

U $20$ B $03$ . Stack in a rut

状态

开发

支持

关于

Simulation

U151515B010101F. Censoring

U161616B020202D. Block Game

U161616B020202F. Circular Barn

U161616B030303J. Mowing the Field

U171717B010101D. The Lost Cow

U171717B020202D. The Bovine Shuffle

U181818B010101OC. Team Tic Tac Toe

U181818B020202D. The Bucket List

U191919B030303F. Measuring Traffic

U202020B030303. Stack in a rut

状态

开发

支持

关于

登录

U $15$ B $01$ F. Censoring

U $16$ B $02$ D. Block Game

U $16$ B $02$ F. Circular Barn

U $16$ B $03$ J. Mowing the Field

U $17$ B $01$ D. The Lost Cow

U $17$ B $02$ D. The Bovine Shuffle

U $18$ B $01$ OC. Team Tic Tac Toe

U $18$ B $02$ D. The Bucket List

U $19$ B $03$ F. Measuring Traffic

U $20$ B $03$ . Stack in a rut