【LGR-149-Div.3】洛谷基础赛 #2 & qw Round -1

T1

签到。

T2

送分题。

T3

大模拟，但是TLE两个点。

#include <bits/stdc++.h>
#define ll long long
#define int long long
#define re register
using namespace std;
const int N=1e5+5, INF=0x3f3f3f3f;
int n;
queue<string>Q;
map<string,int> zt;//0 不在；1 排队；2 游玩； 
string last1,last2;
inline void START(int i){
	if(i!=1){
		if(last1!="")
		Q.push(last1),zt[last1]=1;
		if(last2!="")
		Q.push(last2),zt[last2]=1;
		if(!Q.size()){
			printf("Error\n");return ;
		}
		string player1=Q.front();Q.pop();
		if(!Q.size()){
			last1=player1;last2="";
			zt[player1]=2;
			cout<<player1<<"\n";
		}else{
			string player2=Q.front();Q.pop();
			last1=player1;last2=player2;
			zt[player1]=2;zt[player2]=2;
			cout<<player1<<' '<<player2<<"\n";
		}
	}else printf("Error\n");
}
inline void ARRIVE(string x){
	if(zt[x]==1||zt[x]==2)printf("Error\n");
	else{
		Q.push(x);zt[x]=1;
		printf("OK\n");
	}
}
inline void LEAVE(string x){
	if(zt[x]==1){
		zt[x]=0;
		queue<string>Q2;
		while(Q.size()){
			if(Q.front()!=x)Q2.push(Q.front());
			Q.pop();
		}
		Q=Q2;
		printf("OK\n");
	}else printf("Error\n");
}
signed main(){//scanf & printf: "%lld"
	/*freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);*/
	ios::sync_with_stdio();
	cin>>n;
	for(re int i=1;i<=n;i++){
		string s;cin>>s;
		if(s=="start")START(i);
		else if(s=="arrive"){
			string k;cin>>k;
			ARRIVE(k);
		}else{
			string k;cin>>k;
			LEAVE(k);
		}
	}
	return 0;
}

很大概率是LEAVE操作中删除元素太慢了。等个正解。

T4

直接暴力结果超时，不会优化，发呆两个小时。捡漏40分。（似乎用二分查找答案能70分了）

#include <bits/stdc++.h>
#define ll long long
#define int long long
#define re register
using namespace std;
const int N=1e6+5, INF=0x3f3f3f3f;
int n,m,a[N],b[N];
int now[N];
bool check(int k){
	memset(now,0,sizeof(now));
	for(re int i=1;i<=m;i++){
		int l=b[i]-k,r=b[i]+k;
		if(l<1)l=1;if(r>n)r=n;
		for(re int j=l;j<=r;j++){
			int d=abs(j-b[i]);
			if(k-d>0)
			now[j]+=(k-d);
		}
	}
	for(int i=1;i<=n;i++)
		if(now[i]<a[i])return 0;
	return 1;
}

signed main(){//scanf & printf: "%lld"
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(int i=1;i<=m;i++)scanf("%lld",&b[i]);
	if(n==1){
		cout<<a[1]<<endl;return 0;
	}
	if(m==1){
		int maxn=-1;
		for(int i=1;i<=n;i++){
			maxn=max(abs(b[1]-i)+a[i],maxn);
		}
		cout<<maxn<<endl;
		return 0;
	}
	for(int i=0;;i++){
		if(check(i)){
			printf("%lld\n",i);
			return 0;
		}
	}
	return 0;
}

得分：100+100+80+40=320
排名：rk518 /3926
用时：2.22h
弱（
传送门