526互联

10-16 NOIP模拟赛

发布时间 2023-10-17 14:24:52作者: alloverzyt

10-16 NOIP模拟赛

这周末就要去考 CSP-S 啦！！！

所以改变答题策略，放弃之前死磕第一题正解的做题方法，以暴力为主，得分为主，思考出正解认为能得分后才写。

然后发现把第一题暴力打了以后，正解也浮出水面了。

明天继续尝试，然后注意休息，一定要保持良好睡眠。

T1 购买饮料(buy)

题目描述

你要买饮料。你初始有 \(n\) 块钱，一瓶饮料 \(x\) 块钱。每集齐 \(a\) 个空瓶子可以再获得 \(b\) 块钱。问最多能喝到几瓶饮料。

输入格式

第一行一个正整数 \(T\) ，表示数据组数。

每组数据一行四个整数 \(n,x,a,b\) 。

首先看到这道题暴力模拟很简单，特判如果换来的钱大于买饮料的钱，那就可以陷入循环（也就是无限喝）输出 -1，其次判断一次都换不了，直接输出 \(n/x\) 即可。

剩下的部分如果模拟 while 的话可以得40分；

int ans=0,na=0;
while(n/x){
	ans+=n/x;
	na+=n/x;
	n-=(n/x)*x;
	n+=(na/a)*b;
	na-=(na/a)*a;
}
printf("%d\n",ans);

思考正解，如何加快程序，发现我们每次循环其实各项参数都是不变的，每次 n 的变化都是相同的。

所以我直接判断换 a 个瓶子要亏多少钱，看我能亏多少次，但是要判断我能亏的前提是 \(n \ge a\)。

AC 代码：

int main(){
	freopen("buy.in","r",stdin);	
	freopen("buy.out","w",stdout);
	int T;
	T=read();
	while(T--){
		int n,x,a,b;
		n=read();x=read();a=read();b=read();
		if(n<x){printf("0\n");continue;}
		if(b/a>=x&&(n/x)>=a){
			printf("-1\n");continue;
		}
		if((n/x)<a){
			printf("%d\n",(int)n/x);continue;
		}
		long long ans=0,m=a*x-b;
		long long kn=(n-a*x)/m;
		ans+=a*kn;
		n=n-(kn*m);
		while((n/x)>=a) n-=m,ans+=a;
		ans+=n/x;
		printf("%lld\n",ans);
	}
	return 0;
}

T2 多边形(polygon)

题目描述

有一个正 n 边形，每个点的颜色为红色，蓝色，绿色中的其中一种。保证每种颜色至少出现一次且 n 边形上相邻的两个点颜色不同。你想要连接 n-3 条对角线，使得对角线把整个图形分成了 n-2 个三角形（即三角剖分），并且每个三角形三个顶点颜色两两不同。

输出格式

如果无解，输出 Impossible! 。

否则输出 n-3 行，每行两个正整数 x,y ，表示一条对角线（按顺时针顺序标号）。

你需要保证这构成一个合法的方案，如果有多个答案，输出任意一个即可。

注意此题输出量很大，请尽量使用速度较快的输出方式。

思路出来以后还是比较明了，但是不太好写

首先如果有一个颜色只出现了一次，那么直接把这个点和所有其他点相连即可。

否则一定会出现相邻的三个点颜色两两不同，直接将这三个点划分成一个三角形，并删除掉中间那个点递归即可。容易发现所有限制条件始终满足。但要用链表来维护。

时间复杂度 \(O(n)\)。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define N 1000005
int n;
int a[N],lst[N],nxt[N],cnt[3];
bool vis[N];
char s[N];

int getc(char c){
	if(c=='R') return 0;
	else if(c=='G') return 1;
	else return 2;
}

bool check(int x){
	return a[x]!=a[nxt[x]] && a[x]!=a[lst[x]] 
	&& a[lst[x]]!=a[nxt[x]];
}//判断左右三点都不相同 

int main(){
	freopen("polygon.in","r",stdin);
	freopen("polygon.out","w",stdout);
	scanf("%d",&n);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++) a[i]=getc(s[i]);//a存储字符类型012 
	for(int i=1;i<=n;i++) cnt[a[i]]++;//cnt存储每种个数 
	for(int i=1;i<=n;i++) nxt[i]=i+1,lst[i]=i-1;//链表 
	lst[1]=n,nxt[n]=1;
	queue<int>q;//存储可以被删掉的点 
	for(int i=1;i<=n;i++){
		if(check(i)) q.push(i);
	}
	vector<pair<int,int> >ans;//存储答案 
	while(1){
		if(cnt[0]==1||cnt[1]==1||cnt[2]==1){
			int pl=0;
			for(int i=1;i<=n;i++) if(!vis[i]&&cnt[a[i]]==1) pl=i;
			for(int i=1;i<=n;i++){
				if(!vis[i]&&i!=pl&&i!=nxt[pl]&&i!=lst[pl])
					ans.emplace_back(pl,i);
			}
			break;
		}
		int t=q.front();q.pop();
		if(vis[t]) continue;
		if(check(t)){
			vis[t]=1;
			cnt[a[t]]--;
			ans.emplace_back(lst[t],nxt[t]);
			lst[nxt[t]]=lst[t];
			nxt[lst[t]]=nxt[t];
			if(check(lst[t])) q.push(lst[t]);
			if(check(nxt[t])) q.push(nxt[t]);
		}
	}
	for(auto r:ans) printf("%d %d\n",r.x,r.y);
	return 0;
}