这题特别特别好想，特别特别难写，特别特别难调。

$2$ 分钟想了一个玄学思路。

首先，正常人都会发现这题在经过一段时间后变成一个循环不断插入弹出。

然后就会有人发现这个序列就是一堆最小的胜利条件牌，如果不够就拿一些非胜利条件牌补。

然后就去专门找序列去了，最后发现找到序列后啥事都干不了。

我当时就这么想着，一拍脑袋，谁还找那个序列啊！

然后我就选择相信我的直觉：直接硬模拟 $2n$ 次，剩下来的序列加上一个胜利条件牌（没有用其他的补）就是你要的序列。

这个东西就非常容易做前缀和了，但是我二分边界写错了导致调了半小时。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e5+10;
int a[N],v[N],inq[N],b[N],c[N],len,s[N],s1[N];
#define PII pair<int,int>
#define fi first
#define se second
priority_queue<PII,vector<PII>,greater<PII>>q1,q2;deque<PII>q;
signed main()
{
	int n,m,vsum=0;cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	int k;cin>>k;
	for(int i=1,x;i<=k;i++)cin>>x,v[x]=1,vsum++;
	for(int i=1;i<=m;i++)
	{
		if(v[i])q1.push({a[i],1});
		else q2.push({a[i],0});
	}
	for(int i=m+1;i<=n;i++)q.push_back({a[i],v[i]});
	int sum=0,sum1=0;
	for(int i=1;i<=n*2;i++)
	{
		if(q1.empty())
		{
			sum+=q2.top().fi;
			q.push_back(q2.top());q2.pop();
		}
		else
		{
			sum+=q1.top().fi;sum1++;
			q.push_back(q1.top());q1.pop();
		}
		b[++len]=sum;c[len]=sum1;
		if(q.front().se)q1.push(q.front());
		else q2.push(q.front());
		q.pop_front();
	}
	if(q1.empty())q.push_front(q2.top());
	else q.push_front(q1.top());
	int tmp=0,vres=0,len1=q.size();
	for(auto i:q)tmp+=i.fi,vres+=i.se;
	for(int i=1;i<=len1;i++)s[i]=s[i-1]+q[i-1].fi;
	for(int i=1;i<=len1;i++)s1[i]=s1[i-1]+q[i-1].se;
	int Q;cin>>Q;
	while(Q--)
	{
		int x;cin>>x;
		if(x<=b[len])
		{
			int l=0,r=len,res=0;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(x>=b[mid])l=mid+1,res=mid;
				else r=mid-1;
			}
			cout<<c[res]<<'\n';
		}
		else
		{
			int summ=x-b[len],ans=c[len],ssum=summ/tmp;
			ans+=ssum*vres,summ%=tmp;
			int l=0,r=len1,res=0;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(summ>=s[mid])l=mid+1,res=mid;
				else r=mid-1;
			}
			ans+=s1[res];
			cout<<ans<<'\n';
		}
	}
	return 0;
}

本人第一次写题解，请各位大佬多多关照。

题目传送门

P15573 Clash! S 题解

题目分析

FJ 有 $N$ 张牌，初始手牌为 $1\sim H$，剩余的牌在抽牌队列中。

魔力变化：每秒魔力 $+1$。

出牌时的规则：

1．必须优先打胜利牌（非常重要，~由此可看出 FJ 没有自由权~）。

2．每次打出一张手牌后，从队首补牌，打出的牌放入抽排队队尾。

数据范围：$t\le 10^{18}$。

从这我们就可以看出，我们不能死算，要用巧解。

思路

遇到这种大数，我们可以考虑一下周期问题（~不要告诉我你还没学~）。因为在一个时间段内，我们能拿胜利牌的张数都是相同的，所以我们只需算出一个周期需要的时间和可以拿到的胜利牌，问题就迎刃而解。

而一个周期是 $n-h+1$，我来解释一下，因为：

手牌变回来是 $1\sim H$。

抽牌队列变回来是 $H+1\sim N$。

我们需要把抽牌队列里所有牌都抽一遍，变回原来的样子。

而抽牌队列长度为 $N-H$。

所以： 周期长度 $=$ 队列长度 $+1$ $=$ $(N-H)+1$ $=$ $N-H+1$。

没看懂没关系，来看看代码。（注：注释是我和豆包老师一起写的，~不然会把我累死~）：

AC code：

// AC代码 QwQ

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,h,k,a[N],qq,s[N];
bool vis[N];// vis[x]=0表示x是不是胜利条件牌 vis[x]=1表示x是胜利条件牌
inline int read(){
	int x=0,y=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') y=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+(c-'0');
		c=getchar();
	}
	return x*y;
}
signed main(){
	n=read();
	h=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	k=read();
	for(int i=1;i<=k;i++){
		s[i]=read();
		vis[s[i]]=1;
	}
	queue<int>q;
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >hand;
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >handwin;
	bool handvis[N]={0};// 标记某张牌是否在手牌中
	for(int i=1;i<=h;i++){
		handvis[i]=1;
		hand.push(make_pair(a[i],i));
		if(vis[i]) handwin.push(make_pair(a[i],i));
	}
	for(int i=h+1;i<=n;i++){
		q.push(i);
	}
	int cnt=0,ml[N]={0},sum=0;
	for(int i=1;i<=n-h+1;i++){// 模拟一个周期，只要执行n-h+1次，牌组就可以回到初始状态
		if(!handwin.empty()){
		    // 手里有胜利牌 →打胜利牌
			int min_ml=handwin.top().first;
			int card=handwin.top().second;
			handwin.pop();
			sum+=min_ml;
			handvis[card]=0;
			ml[++cnt]=sum;
			q.push(card);
		}else{
		    // 没有胜利牌 →打普通牌
			while(!handvis[hand.top().second]) hand.pop();// 清除堆里已不在的手牌（这一步非常关键，不加必废）
			int min_ml=hand.top().first;
			int card=hand.top().second;
			hand.pop();
			handvis[card]=0;
			sum+=a[card];
			q.push(card);
		}
		// 补手牌
		int tmp=q.front();
		q.pop();
		handvis[tmp]=1;
		hand.push(make_pair(a[tmp],tmp));
		if(vis[tmp]) handwin.push(make_pair(a[tmp],tmp));
	}
	ml[cnt+1]=0x3f;// 防止二分越界
	qq=read();
	int x=0;
	while(qq--){
		x=read();
		int shengyu=upper_bound(ml+1,ml+1+cnt,x%sum)-ml-1;// 二分找剩余部分能打出多少胜利牌
		cout<<x/sum*cnt+shengyu<<"\n";
	}
	return 0;
}

如有问题请指出，请多多关照 QwQ。