当前位置：首页 > news >正文

【2025.8.11】模拟赛

news 2025/12/6 11:42:44

T1

solution

先特判买不够 \(a\) 瓶和能买无限瓶的两种情况。

接着一直买 \(a\) 瓶，直到买不够为止。

~~（签到题竟然挂了）~~

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t;
ll n,x,a,b;
ll ans=0;
int main(){freopen("buy.in","r",stdin);freopen("buy.out","w",stdout);cin>>t;while(t--){scanf("%lld%lld%lld%lld",&n,&x,&a,&b);ans=0;if(n/x<a){printf("%lld\n",n/x);continue;}if(a*x<=b){//7 2 3 5printf("-1\n");continue;}ll tmp=(n-a*x)/(a*x-b);ans=tmp*a;n-=tmp*(a*x-b);while(n>=a*x){n-=a*x-b;ans+=a;}ans+=n/x;printf("%lld\n",ans);}fclose(stdin);fclose(stdout);return 0;
}

T2

solution

每次找相邻的三个颜色不同的点进行划分，找到后把中间的点删去，用链表维护。

特别地，如果存在只剩一个的颜色，就拿这个点往其他所有没被删去的点连对角线。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
struct node{int x,y;
}ans[N];
int n,tot=0;
char s[N];
int a[N];
int lst[N],nxt[N];
bool vis[N];
int cnt[5];
queue<int> q;
int ch(char c){if(c=='R')  return 0;if(c=='G')  return 1;if(c=='B')  return 2;
}
bool check(int idx){if(a[lst[idx]]==a[idx])  return 0;if(a[nxt[idx]]==a[idx])  return 0;if(a[lst[idx]]==a[nxt[idx]])  return 0;return 1;
}
int main(){freopen("polygon.in","r",stdin);freopen("polygon.out","w",stdout);cin>>n;cin>>s+1;for(int i=1;i<=n;++i){a[i]=ch(s[i]);cnt[a[i]]++;lst[i]=(i!=1?i-1:n);nxt[i]=(i!=n?i+1:1);}memset(vis,0,sizeof(vis));for(int i=1;i<=n;++i)if(check(i))q.push(i);while(1){if(cnt[0]==1||cnt[1]==1||cnt[2]==1){int pos=0;for(int i=1;i<=n;++i)if(!vis[i]&&cnt[a[i]]==1)pos=i;for(int i=1;i<=n;++i)if(!vis[i]&&i!=pos&&i!=lst[pos]&&i!=nxt[pos]){ans[++tot].x=i;ans[tot].y=pos;}break;}int u=q.front();q.pop();if(vis[u])  continue;if(check(u)){ans[++tot].x=lst[u];ans[tot].y=nxt[u];lst[nxt[u]]=lst[u];nxt[lst[u]]=nxt[u];vis[u]=1;cnt[a[u]]--;if(check(lst[u]))  q.push(lst[u]);if(check(nxt[u]))  q.push(nxt[u]);}}for(int i=1;i<=tot;++i)printf("%d %d\n",ans[i].x,ans[i].y);fclose(stdin);fclose(stdout);return 0;
}