Reincarnation

正因为梦易碎，才格外美好。

NOIP2023未来共同体 模拟十二

发表于 更新于 分类于 ，
本文字数： 4.7k 阅读时长 ≈ 4 分钟

锅最多的一集。 电王原神模拟赛！

A. 星穹铁道（star）

题目简介

给定一个长度为 的序列 ，以及 次操作，每次操作如下：

  • 当前第 次操作，如果 ，那么执行 。

求出最后满足 的编号。

数据范围：

注意到 ，这意味着结点间最多会重合之后一起移动，而不会出现当前 在某次操作之后 的情况，这意味着所有结点在任意时刻满足相对顺序不变。

所以我们只需要找到 当前对应区间，将操作反过来做，找到初始区间之后，就可以的得到最终答案区间了。

时间复杂度 。

大家好我是大懒人不分讨，所以我写了二分。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e6+10;
int N,T,L,R;
int main()
{
	freopen("star.in","r",stdin);
	freopen("star.out","w",stdout);
	read(N,T);
	for(int i=1;i<=N;++i) read(a[i].pos),a[i].id=i;
	for(int i=1;i<=T;++i) read(Ai[i].x,Ai[i].y,Ai[i].z);
	std::sort(a+1,a+N+1);
	read(L,R);
	int l=1,r=N,res=1;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid)>=L) res=mid,r=mid-1;
		else l=mid+1;
	}
	int ansl=res;
	l=1,r=N,res=N;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid)<=R) res=mid,l=mid+1;
		else r=mid-1;
	}
	l=ansl,r=res;
	// write(l,' ',r,'\n');
	write(std::max(0,r-l+1),'\n');
	for(int i=l;i<=r;++i) ans.push_back(a[i].id);
	std::sort(ans.begin(),ans.end());
	for(int x:ans) write(x,' ');
	return 0;
}
/*

*/

B. 电王的烦恼（power）

题目简介

定义 表示最短的序列长度，满足在这个序列中标记任意多的点，分成 两个子序列，一定存在一个长度为 的子序列满足 或者存在一个长度为 的子序列满足 。

给定 ，求出 ，序列 从 到 。多测。

数据范围：

答案的反命题：一个满足 而且 的 序列，最长有多长，其中 为 的个数。最后需要加一。

考虑正解应该是怎么样的。打表、手模可以发现，大部分情况下前一段都相同，后一段都相同，很容易看出这种做法较优。但是也有一些情况答案会分为 3 段。

考虑求出哪些情况下会变成 段、第一段有多长以及为何 段式更优。事实上这些都是一个问题。

我们从两段出发（假设前 后 ，否则同理），这已经是一个很优的情况了，考虑调整使得更优。由于题目的限制很特殊，所以我们考虑这么调整：每次抽出一个 ，插入前面某个位置，然后按照限制的变动，调整前一段 的长度，这样又改变了 的限制，再调整 的长度。任意一种局面都可以从两段式开始由这种方法构造得到。

我们计算一下已经插了 个 后再拿一个 出来放在第 个 的前面的贡献。首先，放在第 个之后一定不优，不能放宽 的限制，还会缩紧 的限制。

所以当我们插入之后， 都会加 ，而 就会加 。则 也都会 。 的上限增加 。

但 的上限会因为 的前移而减小。对答案的贡献和 有关且随 减小而增大。所以最优情况下 。所以 每次必放最前面。所以三段式最优，其他的情况都可以通过把中间的 移到最前面或者放回最后面来使得答案不劣。

事实上，答案可以表示为关于第一段的长度为 的二次函数：

其中 ，而答案就是这个函数的极值。可以直接三分求解。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef vector<int> vi;
typedef pair<int,int> pi;

void solve(){
	int n,m;cin>>n>>m;
	int ans=0;
	
	auto calc=[&](int i)->int{
		int r=n-i;
		int s0=i*(i+1)/2;
		int s1=(i+1+i+m)*m/2;
		return s0+(s1+1+s1+r)*r/2;
	};
	int l=0,r=n-1;
	while(l<r){
		int mid=(l+r)/2;
		if(calc(mid)<calc(mid+1)){
			l=mid+1;
		}
		else{
			r=mid;
		}
	}
	ans=calc(l);
	swap(n,m);
	l=0,r=n-1;
	while(l<r){
		int mid=(l+r)/2;
		if(calc(mid)<calc(mid+1)){
			l=mid+1;
		}
		else{
			r=mid;
		}
	}
	ans=max(ans,calc(l));
	cout<<ans+1<<'\n';
}
signed main(){
	freopen("power.in","r",stdin);
	freopen("power.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t;cin>>t;
	while(t--){
		solve();
	}
}

C. 圣遗物（genshin）

题目简介

说实话没怎么看懂题面。

D. 芙蓉王（lotus）

题目简介

相关文章