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;
}