"China Dongxin Cup" the fourth programming competition of Guangxi University (synchronous competition)

List of articles

Topic knowledge

• simulation
• gcd and lcm
• thinking
• Completely backpack
• kmp
• Monotonic stack

Title code

A Antinomy And the gold content of the game

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long int ll;
const ll maxn=1e5+10;
ll t;
int main(){
	cin>>t;
	while(t--){
		ll x,y,z;
		cin>>x>>y>>z;
		if(x>90&&y>90&&z>60){
			cout<<"A+\n";
		}else{
			cout<<"E+\n";
		}
	}
	return 0;
}

B Antinomy And take the mold

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long int ll;
const ll maxn=1e5+10;
ll t;
ll gcd(ll a,ll b){
	return b ? gcd(b,a%b) : a;
}
int main(){
	scanf("%lld",&t);
	while(t--){
		ll x,y,l,r;
		scanf("%lld%lld%lld%lld",&x,&y,&l,&r);
		ll val=gcd(x,y);
		val=x*y/val;
		ll q=l/val;
		ll p=r/val;
		ll flag=0;
		for(int i=q;i<=p;i++){
					//cout<<i*val<<endl;
			if((i*val)>=l&&(i*val)<=r){
				printf("%lld\n",i*val);
				flag=1;
				break;
			}
		}
		if(!flag){
			printf("-1\n");
		}
	}
	return 0;
}

C Antinomy And clean up magic

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long int ll;
const ll maxn=1e5+10;
ll n,k;
ll a[maxn];
int main(){
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	sort(a+1,a+1+n);
	ll flag=0;
	for(int i=2;i<=n;i++){
		if((a[i]-a[i-1])>k){
			flag=1;
			break;
		}
	}
	if(flag){
		printf("NO");
	}else{
		printf("YES");
	}
	return 0;
}

E Antinomy Slow down the skill tree

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long int ll;
const ll maxn=1e5+10;
ll n,k;
ll w[maxn];
ll v[maxn];
ll f[maxn];
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		double v1;
		scanf("%lf %lld",&v1,&w[i]);
		v1=(v1+0.00005)*10000;
		v[i]=v1;
		//cout<<v[i]<<" ";
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		for(int j=10000;j>=v[i];j--){
			f[j]=max(f[j],f[j-v[i]]+w[i]);
			ans=max(f[j],ans);
			//cout<<f[j]<<" ";
		} 
		//cout<<endl;
	}
	printf("%lld\n",ans);
	return 0;
}
/*
4
1 5
0.4999 7
0.5001 3
0.9 12
0.1001 15
*/

F Antinomy With the golden finger

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long int ll;
const ll maxn=5e5+10;
ll n;
string s,t;
ll nex[maxn];
void getnex(){
	ll k=-1;
	ll j=0;
	nex[0]=-1;
	ll len=s.size();
	while(j<len){
		if(k==-1||s[j]==s[k]){
			j++;
			k++;
			nex[j]=k;
		}else{
			k=nex[k];
		}
	}
}
ll kmp(){
	ll len1=s.size(),len2=t.size();
	if(len1>len2){
		return 0;
	}
	ll i=0,j=0;
	while(i<len2){
		if(j==-1||t[i]==s[j]){
			i++;
			j++;
		}else{
			j=nex[j];
		}
		if(j==len1){
			return 1;
		}
	}
	return 0;
}
int main(){
	cin>>n;
	cin>>t>>s;
	t+=t;
	getnex();
	if(!kmp()){
		printf("TAT");
	}else{
		printf("wow");
	}
	return 0;
}

H Antinomy And magic power

#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
typedef long long int ll;
const ll maxn=2e5+10;
ll st[maxn];
ll l[maxn];
ll r[maxn];
ll a[maxn];
ll ans[maxn];
ll n;
ll now;
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	now=-1;
	st[++now]=0;
	for(int i=1;i<=n;i++){
		while(now>=0&&a[i]<=a[st[now]])now--;
		l[i]=st[now];
		st[++now]=i;
	}
	now=-1;
	st[++now]=n+1;
	for(int i=n;i>=1;i--){
		while(now>=0&&a[i]<=a[st[now]])now--;
		r[i]=st[now];
		st[++now]=i;
	}
	//a[i] stay r[i]-l[i]-1 Length and below are useful  
	for(int i=1;i<=n;i++){
		ans[r[i]-l[i]-1]=max(a[i],ans[r[i]-l[i]-1]);
		//cout<<l[i]<<" "<<r[i]<<endl;
	}
	for(int i=n;i>=1;i--){
		ans[i]=max(ans[i],ans[i+1]);
	}
	for(int i=1;i<=n;i++){
		printf("%lld ",ans[i]);
	}
	return 0;
}

Answer key pdf Download link

• pdf Answer key

Conclusion

• Never decide Ask the spring breeze
• The spring breeze is silent That is, follow your heart
• If my heart can settle How can you not make up your mind when you are in trouble Spring breeze also has spring breeze sorrow Don't worry about me .
• Since then, the spring breeze has filled my sleeves , Just for the sake of peace