Reincarnation

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

OI复健

发表于 更新于 分类于
本文字数： 11k 阅读时长 ≈ 10 分钟

ABC414

A - Streamer Takahashi

题目简介

输入 ，有 组 ，求 是多少组 的子集。

数据范围：

签到题。

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
// ----- Eternally question-----
// Problem: A - Streamer Takahashi
// Contest: AtCoder -  Mirrativ Programming Contest 2025 (AtCoder Beginner Contest 414)
// URL: https://atcoder.jp/contests/abc414/tasks/abc414_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2025-07-12 20:00:24
// ----- Endless solution-------

#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(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s) putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
int N,ans;
int L,R,l,r;
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N,L,R);
    for(int i=1;i<=N;++i)
    {
    	read(l,r);
    	if(l<=L&&R<=r) ++ans;
    }
    write(ans);
    return 0;
}
/*

*/

B - String Too Long

题目简介

输入 组 表示一个字符串 按顺序出现字母 有 次，若 则违法。

数据范围：，

签到题2。

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
// ----- Eternally question-----
// Problem: B - String Too Long
// Contest: AtCoder -  Mirrativ Programming Contest 2025 (AtCoder Beginner Contest 414)
// URL: https://atcoder.jp/contests/abc414/tasks/abc414_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2025-07-12 20:01:47
// ----- Endless solution-------

#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(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s) putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
const int MAXN=110;
int N;
ll Le[MAXN],Len;
char Ch[MAXN];
bool TL;
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N);
    for(int i=1;i<=N;++i)
    {
    	Ch[i]=getchar();
    	read(Le[i]);
    	Len+=Le[i];
    	if(Len>100) TL=1;
    }
    if(TL) puts("Too Long");
    else
    {
    	for(int i=1;i<=N;++i)
    		for(;Le[i]--;) putchar(Ch[i]);
    }
    return 0;
}
/*

*/

C - Palindromic in Both Bases

题目简介

求出 中数 满足其 进制下和 进制下都是回文数的个数。

数据范围：

我们可以找出所有 进制下的回文数并一一判断其 进制下是否为回文数。

判断回文的复杂度为 ，枚举复杂度为 ，因为对于一个 位数，我们只需要枚举 位即可。

使用了最暴力的写法，需要注意的是在 进制下 的数位达到四十多五十多，所以不能转化为 long long，用数组存即可。

时间复杂度 。

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
// ----- Eternally question-----
// Problem: C - Palindromic in Both Bases
// Contest: AtCoder -  Mirrativ Programming Contest 2025 (AtCoder Beginner Contest 414)
// URL: https://atcoder.jp/contests/abc414/tasks/abc414_c
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// Written by: Eternity
// Time: 2025-07-12 20:06:12
// ----- Endless solution-------

#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(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s) putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
int A;
ll N,ans;
int val[110];
inline bool isPali_trBase(ll s)
{
	int len=0;auto _s=s;
	while(_s)
	{
		val[++len]=_s%A;
		_s/=A;
	}
	for(int i=1;i<=(len>>1);++i) if(val[i]!=val[len-i+1]) return 0;
	return 1;
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(A,N);
    // for(ll i=1;i<=N;++i) if(isPali(i)&&isPali(trBase(i))) ans+=i;
    int _N=N,len=0;
    while(_N) ++len,_N/=10;
    for(int i1=0;i1<=9;++i1)
    	for(int i2=0;i2<=9;++i2)
    		for(int i3=0;i3<=9;++i3)
    			for(int i4=0;i4<=9;++i4)
    				for(int i5=0;i5<=9;++i5)
    					for(int i6=0;i6<=9;++i6)
    					{
    						ll X=	i1+
    								i2*10ll+
    								i3*100ll+
    								i4*1000ll+
    								i5*10000ll+
    								i6*100000ll+
    								i6*1000000ll+
    								i5*10000000ll+
    								i4*100000000ll+
    								i3*1000000000ll+
    								i2*10000000000ll+
    								i1*100000000000ll;
    						if(!i1)
    						{
    							X/=10;
    							if(!i2)
    							{
    								X/=10;
    								if(!i3)
    								{
		    							X/=10;
			    						if(!i4)
			    						{
			    							X/=10;
	    									if(!i5) X/=10;
	    								}
    								}
    							}
    						}
    						if(X>N||X==0) continue;
    						if(isPali_trBase(X)) ans+=X;
    					}
    for(int i1=0;i1<=9;++i1)
    	for(int i2=0;i2<=9;++i2)
    		for(int i3=0;i3<=9;++i3)
    			for(int i4=0;i4<=9;++i4)
    				for(int i5=0;i5<=9;++i5)
    					for(int i6=0;i6<=9;++i6)
    					{
    						ll X=	i1+
    								i2*10ll+
    								i3*100ll+
    								i4*1000ll+
    								i5*10000ll+
    								i6*100000ll+
    								i5*1000000ll+
    								i4*10000000ll+
    								i3*100000000ll+
    								i2*1000000000ll+
    								i1*10000000000ll;
    						if(!i1)
    						{
    							X/=10;
    							if(!i2)
    							{
    								X/=10;
    								if(!i3)
    								{
		    							X/=10;
			    						if(!i4)
			    						{
			    							X/=10;
	    									if(!i5) X/=10;
	    								}
    								}
    							}
    						}
    						if(X>N||X==0) continue;
    						if(isPali_trBase(X)) ans+=X;
    					}
    write(ans);
    return 0;
}
/*

*/

D - Transmission Mission

题目简介

有 个数，你需要将其分为 组，每一组的权值定义为这一组数中的极差，求最优划分下权值和的最小值。

数据范围：

首先进行排序，从差分角度来看，每一组的权值就是其差分和，而组与组之间，即 分组相当于消除了 的贡献，所以我们把最大的 个差值剪去即可。

实现复杂度取决于排序复杂度。非常蠢的题，想了半天被fly秒了。

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
// ----- Eternally question-----
// Problem: D - Transmission Mission
// Contest: AtCoder -  Mirrativ Programming Contest 2025 (AtCoder Beginner Contest 414)
// URL: https://atcoder.jp/contests/abc414/tasks/abc414_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2025-07-12 20:40:31
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
using namespace std;
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(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s) putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
const int MAXN=5e5+10;
int N,M;
ll Dist[MAXN],Diff[MAXN];
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N,M);
    for(int i=1;i<=N;++i) read(Dist[i]);
    sort(Dist+1,Dist+N+1);
    for(int i=1;i<N;++i) Diff[i]=Dist[i+1]-Dist[i];
    sort(Diff+1,Diff+N);
    ll ans=0;
    for(int i=1;i<=N-M;++i) ans+=Diff[i];
    write(ans);
    return 0;
}
/*

*/

E - Count A%B=C

题目简介

求数对 满足 ，且 的个数，模 。

数据范围：

很好想，相当于求对每个式子 求 的个数，移一下 。

所以相当于求：

可以用整数分块优化 的计算，时间复杂度 ，显然过不了。

所以我们不能枚举 。

观察式子，假如我们枚举 ，你会发现 可以取 中 的所有值，而这个值我们可以直接计算。

所以相当于求：

稍微化简：

前者是初中学过的等差数列，后者是整数分块，所以 搞定。

注意取模即可， 是爆 int 级的，直接乘会爆 long long，所以先取模再运算，等差数列求和涉及到除法，用逆元即可。

写法很丑陋。

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
// ----- Eternally question-----
// Problem: E - Count A%B=C
// Contest: AtCoder -  Mirrativ Programming Contest 2025 (AtCoder Beginner Contest 414)
// URL: https://atcoder.jp/contests/abc414/tasks/abc414_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2025-07-12 21:02:03
// ----- Endless solution-------

#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(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s) putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
const ll Mod=998244353;
ll N,ans;
inline ll calc1(ll x)
{
	ll res=0;
	for(ll l=1,r=l;l<=x;l=r+1)
	{
		r=x/(x/l);
		res=(res+x/l*(r-l+1)%Mod)%Mod;
	}
	return (res%Mod+Mod-(N%Mod)-1+Mod)%Mod;
}
inline ll qPow(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%Mod;
		a=a*a%Mod;b>>=1;
	}
	return res;
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N);
    ans=(N-2)%Mod*((N+1)%Mod)%Mod*qPow(2,Mod-2)%Mod+Mod-calc1(N);
    write(ans%Mod);
    return 0;
}
/*

*/

P1281

https://www.luogu.com.cn/problem/P1281

考虑一个很朴素的 ，设 表示前 本书由 个人抄写，转移方程：

但这道题要求我们输出字典序最小的方案。我刚开始用的 $pre$ 记录转移过程，但是似乎限制不了，后来看到题解发现事实上可以重构造，也就是在知道答案的情况下从后往前依次枚举让后面包含的区间最多。

时间复杂度 $\mathcal O(n^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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// ----- Eternally question-----
// Problem: P1281 [CERC1998] 书的复制
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1281
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2025-10-26 17:58:48
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
#define fir first
#define sec second
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 ...Arc>
inline void read(T &x,Arc &...arc){ read(x),read(arc...); }
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){ putchar(x?'1':'0'); }
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=5e2+10;
const int INF=0x3f3f3f3f;
int N,K,val[MAXN];
int Dp[MAXN][MAXN],Lst[MAXN];
int L[MAXN],R[MAXN];
inline int sum(int l,int r){ return l>r?0:Lst[r]-Lst[l-1]; }
inline void Print(int ans)
{
	R[K]=N,L[1]=1;int k=K;
	for(int i=N,sum=0;i;--i)
	{
		if(sum+val[i]>ans)
		{
			L[k]=i+1,R[--k]=i;
			sum=val[i];
		}
		else sum+=val[i];
	}
	for(int i=1;i<=K;++i) write(L[i],' ',R[i],'\n');
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,K);
	for(int i=1;i<=N;++i) read(val[i]),Lst[i]=Lst[i-1]+val[i];
	std::memset(Dp,0x3f,sizeof(Dp));
	Dp[0][0]=0;
	for(int i=1;i<=N;++i)
		for(int j=1;j<=K&&j<=i;++j)
			for(int k=0;k<=i;++k)
				checkMin(Dp[i][j],std::max(Dp[k][j-1],sum(k+1,i)));
	Print(Dp[N][K]);
	return 0;
	return 0;
}

CSP-J 2025

闹麻了，花了 $1.5h$ 才做完。

https://www.luogu.com.cn/contest/288427

T1

读入字符串，开一个桶把数字提出来，从 $9$ 到 $0$ 输出，时间复杂度 $\mathcal O(n)$。

T2

闹麻了的结构体排序，但是神秘题面，输入行和列，输出列和行。

排完序后找排名，然后 $rk=c*n+r$ 即可，判一下 $c$ 的奇偶即可。

T3

设 $pr_{i}$ 表示前缀异或和，然后是众所周知的 $\operatorname{xor}_{i=l}^r a_i=pr_r\operatorname{xor}pr_{l-1}$。

首先区间要多，所以区间要小，我们将 $pr$ 开一个前缀桶，那么如果存在 $pr_r\operatorname{xor} k=pr_{l-1}$，则 $[l,r]$ 为合法区间。

然后考虑选重叠的区间，记 $pv_r$ 表示以 $r$ 为结尾的合法区间的头在哪里，如果 $pv_r=0$ 则说明没有以 $r$ 结尾的合法区间。这里显然 $pv_r$ 记录的是最短区间。

这里我们从 $1$ 开始枚举计算，你会发现找到一个选一个是最优的，因为记录的是区间结尾，所以局部最优推全局最优没有问题，当然你也可以记录 $pv_l$ 然后倒序枚举。时间复杂度 $\mathcal O(n)$。

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
// ----- Eternally question-----
// Problem: P14359 [CSP-J 2025] 异或和 / xor（官方数据）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P14359?contestId=288427
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2025-11-13 19:48:08
// ----- Endless solution-------

#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 ...Arc>
inline void read(T &x,Arc &...arc){ read(x),read(arc...); }
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){ putchar(x?'1':'0'); }
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=5e5+10,MAXV=(1<<20)+10;
int N,K;
int val[MAXN],pre[MAXN],prev[MAXV];
int preid[MAXN],ans,pos;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,K);
	std::memset(prev,-1,sizeof(prev));
	for(int i=1;i<=N;++i) read(val[i]),pre[i]=pre[i-1]^val[i];
	prev[0]=0;
	for(int i=1;i<=N;++i)
	{
		auto x=pre[i]^K;
		if(val[i]==K) preid[i]=i;
		else if(~prev[x]) preid[i]=prev[x]+1;
		prev[pre[i]]=i;
		// write(x,' ',pre[i],'\n');
	}
	// for(int i=1;i<=N;++i) write(preid[i],' ');
	// puts("");
	for(int i=1;i<=N;++i) if(preid[i]>pos) ++ans,pos=i;
	write(ans);
	return 0;
}

T4

首先排序，考虑 $f_{i}$ 表示前 $i$ 根棍子组成的多边形个数，那么我们强制选择第 $i$ 根，答案就是 $\sum_{i=2a_i+1}^{\infty}f_i$。这样做的时间复杂度是 $\mathcal O(n\sum a_{i})=\mathcal O(n^3)$。

注意到 $a_i\leq 5\times 10^3$，所以事实上如果当前和超过 $1\times 10^4$ 后必合法。

所以我们 $f$ 只记录大小为 $10001$ 的部分，然后将 $>1\times 10^4$ 的部分装在一起，转移变为：

然后 在转移之前翻个倍即可，因为原来已经超过 那么再加一个肯定也超了。

写个循环转移调了半天闹麻了，代码实现能力下降比思维还严重。时间复杂度 。

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
73
74
75
76
77
78
79
80
81
82
83
// ----- Eternally question-----
// Problem: P14360 [CSP-J 2025] 多边形 / polygon（官方数据）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P14360?contestId=288427
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2025-11-13 20:13:23
// ----- Endless solution-------

#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 ...Arc>
inline void read(T &x,Arc &...arc){ read(x),read(arc...); }
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){ putchar(x?'1':'0'); }
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=5e3+10,MAXV=1e4+10;
const int Mod=998244353;
int N,val[MAXN];
int Dp[2][MAXV],ans;
inline void add(int &a,int b){ a=a+b>Mod?a+b-Mod:a+b; }
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i) read(val[i]);
	std::sort(val+1,val+N+1);
	Dp[0][0]=1;
	for(int i=1,op=0;i<=N;++i)
	{
		op^=1;
		for(int j=0;j<=10001;++j) Dp[op][j]=Dp[op^1][j];
		for(int j=val[i]+1;j<=10001;++j)
			add(ans,Dp[op^1][j]);
		for(int j=val[i];j<=10000;++j) add(Dp[op][j],Dp[op^1][j-val[i]]);
		add(Dp[op][10001],Dp[op^1][10001]);
		for(int j=10001-val[i];j<=10000;++j) add(Dp[op][10001],Dp[op^1][j]);
		// for(int i=1;i<=30;++i) write(Dp[op][i],' ');
		// puts(""); 
	}
	write(ans);
	/*Dp[0]=1;
	for(int i=1,sum=0;i<=N;++i)
	{
		sum+=val[i];
		if(i>=3) for(int j=(val[i]<<1)+1;j<=sum;++j) add(ans,Dp[j-val[i]]);
		for(int j=sum;j>=val[i];--j) add(Dp[j],Dp[j-val[i]]);
		// for(int i=1;i<=sum;++i) write(Dp[i],' ');
		// puts("");
	}
	write(ans);
	*/
	return 0;
}

ACM2025 趣味赛

第一场

由于 F 边界忘判导致吃了 3 发罚时痛失 rk1，最后第三拿下（进阶组 rk1）

A. Uestcers need love

容易发现是签到题（抢首杀的方式是将 种方式模拟出来，然后计算在改变前和改变后分别赢了多少次，判断即可。时间复杂度 ，其中 。

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
int Test;
int a1,a2,a3;
inline int abs(int x){ return x>0?x:-x; }
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	while(Test--)
	{
		read(a1,a2,a3);
		int val=a1+a2+a3;
		int ans1=0,ans2=0;
		for(int x=1;x<=42;++x)
			for(int y=1;y<=13;++y)
			{
				if(abs(val-21)<abs(x-21)) ++ans1;
				if(abs(val+y-21)<abs(x-21)) ++ans2;
			}
		puts(ans1>ans2?"No":"Yes");
	}
	return 0;
}

很显然有 的做法，计算当前 后需要最多多少才能到达 或者根本到不到，计算临界值，判断临界值和 的大小关系即可，时间复杂度 。

B. diaoman 的 Gem Mine

显然的贪心思路。我们考虑到升级过程中可能会在一些等级等待一段时间并采矿，那么不妨思考，加入我在 级停留了一会儿， 级停留了一会，假如 那我为什么不把停留在 级的时间也给 级呢？

还要考虑的是，虽然题目要求 级，但假如说在大于 级的某个等级的采矿效率非常高，我们可能会强迫自己升级到那个等级再开始采矿。

总的来说思路就是：枚举最高需要升到 级，其中 ，然后除开升级的时间（如果这个时间大于 则无解），所有的时间都用在 级中效率最高的那一级。

时间复杂度 ，

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
const int MAXN=1e5+10;
int Test,N,X,D;
int val[MAXN],cst[MAXN],Mx[MAXN];
ll pre[MAXN];
inline void Init()
{
	read(N,X,D);
	for(int i=1;i<=N;++i) read(val[i]);
	for(int i=1;i<=N;++i) read(cst[i]);
	cst[1]=0;
	for(int i=0;i<=N;++i) Mx[i]=0;
	for(int i=1;i<=N;++i) Mx[i]=std::max(Mx[i-1],val[i]),pre[i]=pre[i-1]+cst[i];
}
inline void Solve()
{
	if(pre[X]>D) return puts("-1"),void();
	ll ans=0;
	for(int i=X;i<=N;++i) checkMax(ans,1ll*(D-pre[i])*Mx[i]);
	write(ans,'\n');
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	while(Test--)
	{
		Init();
		Solve();
	}
	return 0;
}

C. 魔法与螃蟹

交互题。

首先，对于对方给出的数 和我们给出的数 ，如果 ，那么 与 一定互质，这是易证的。

却只给了 次询问，且要求 ，而最容易与其他数互质的数很明显是质数，所以我们可以依次询问质数，如果返回了 ，则说明当前质数与给定数互质，当前质数即我们需要的答案。

但事实上 中有 个质数，超出了询问次数，所以我们考虑将较小的一些质数两两组合进行询问，即用我们最开始得到的那个结论即可。

至于正确性，由于保证了 这个数小于了 以内所有质数的乘积，故 至少与 内一个质数互质。

事实上，前 个质数的乘积已经大于 了，所以你随便找 个质数问也能过。

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
ll Ask[]={0,86,93,77,65,17,19,23,29,37,41,47,53,59,61,67,71,73,79,83,89,97};
//2、3、5、7、11、13、17、19、23、29、31、37、41、
//43、47、53、59、61、67、71、73、79、83、89、97
//2*43,3*31,7*11,5*13
ll x;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	for(int i=1;i<=20;++i)
	{
		std::cout<<"? "<<Ask[i]<<std::endl;
		std::cout.flush();
		std::cin>>x;
		if(x!=Ask[i])
		{
			std::cout<<"! "<<Ask[i]/x<<std::endl;
			std::cout.flush();
			return 0;
		}
	}
	std::cout<<"! "<<Ask[21]<<std::endl;
	std::cout.flush();
	return 0;
}

D. 摆魔法阵

乍一看是一个神秘分讨题，但注意到 ，所以等效于 ，可降维。

结论很简单，但我不会证。具体可查询 ，考场上遇到了直接猜结论就完事了（ 爷如此说道）。

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
int Test;
ll a,b,c,x,y,z;
inline bool Solve(ll p,ll q,ll n,ll m)
{
	ll A=p*q,B=n*m;
	if(B%A!=0) return 0;
	return (n%p==0&&m%q==0)||(m%p==0&&n%q==0);
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	while(Test--)
	{
		read(a,b,c,x,y,z);
		if(x%a!=0||y%a!=0||z%a!=0)
		{
			puts("No");
			continue;
		}
		x/=a,y/=a,z/=a,b/=a,c/=a;a=1;
		int ans=Solve(b,c,x,y)|Solve(b,c,x,z)|Solve(b,c,y,z);
		puts(ans?"Yes":"No");
	}
	return 0;
}

突然好像又会了。

由于有 ，所以我们将 直接化作 填进一维（所以显然 ），然后转化为将 填入 （假设 填了 ，这是可交换的），又有 ，所以我们把 化作 （则有 ），转化为将 填进 ，所以只要 中有一个是 的倍数即可。

总结来说就是三个条件：

  1. 都整除 ；
  2. 中至少两个整除 ；
  3. 中至少一个整除 。

E. diaoman 的 Civilization

还是贪心。

最优的方案在题面上已经给你了，那就是全部点科技值。然后我们考虑将其中 个选择换成文化值，假若我们换第 个选择，那么科文差就会减少 ，所以很显然了，我们按照 排序选前 个就可以了，时间复杂度 。

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
const int MAXN=2e5+10;
int Test;
int N,Q;
ll val[MAXN],vbl[MAXN],dif[MAXN],pred[MAXN],sum;
inline void Init()
{
	read(N,Q);sum=0;
	for(int i=1;i<=N;++i) read(val[i]),sum+=val[i];
	for(int i=1;i<=N;++i) read(vbl[i]),dif[i]=val[i]+vbl[i];
	std::sort(dif+1,dif+N+1);
	for(int i=1;i<=N;++i) pred[i]=pred[i-1]+dif[i];
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	while(Test--)
	{
		Init();
		for(int x;Q--;)
		{
			read(x);
			write(sum-pred[x],'\n');
		}
	}
	return 0;
}

F. 捞一捞

讲讲我场上写的爽吃 1h 罚时的神秘暴力写法。

很显然区间越小越好，所以我们对于每一个起点找到他满足条件的最短区间，把题目改写为：给定若干区间，求最多能选择多少个不相交区间的问题，这个问题就非常简单，直接排序贪心即可。

所以现在讲讲怎么求最短区间。这类问题首先想到二分，但因为要 ，这里左式分子分母都在变不满足单调，所以我们改写为：，然后设：，你会发现我们二分的判定条件就会变成 ，很明显的差分条件，所以我们只需要处理区间 最大值即可，主播只会线段树了，所以就写了二分套线段树的神秘双 写法，没想到居然真的能过 ，现在电脑确实很厉害了。

需要注意的是当二分找不到答案的时候 会变成 （而如果当前起点靠后则会使 ）所以需要判最后得到的 和 的大小关系（主播在这里挂了三次），时间复杂度 。

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
const int MAXN=5e5+10;
const ll INF=0x3f3f3f3f3f3f3f3f;
int N,C;
ll P,Q;
char Str[MAXN];
int Rp[MAXN],Prev[MAXN],ans,Cnt;
ll Fc[MAXN];
struct SegmentTree
{
	#define ls (p<<1)
	#define rs (p<<1|1)
	struct Segment{ int l,r;ll mx; }Tr[MAXN<<2];
	inline void pushUp(int p){ Tr[p].mx=std::max(Tr[ls].mx,Tr[rs].mx); }
	void build(int p,int l,int r)
	{
		Tr[p].l=l,Tr[p].r=r;
		if(l==r) return Tr[p].mx=Fc[l],void();
		int mid=(l+r)>>1;
		build(ls,l,mid),build(rs,mid+1,r);
		pushUp(p);
	}
	ll queryMax(int p,int l,int r)
	{
		if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].mx;
		int mid=(Tr[p].l+Tr[p].r)>>1;ll ans=-INF;
		if(l<=mid) checkMax(ans,queryMax(ls,l,r));
		if(mid<r) checkMax(ans,queryMax(rs,l,r));
		return ans;
	}
	#undef ls
	#undef rs
}Tr;
struct Node
{
	int l,r;
	bool operator<(const Node &x) const 
	{ return r==x.r?l<x.l:r<x.r; }
}Seg[MAXN];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,C,P,Q);scanf("%s",Str+1);
	for(int i=1;i<=N;++i) Prev[i]=Prev[i-1]+Str[i]-'0';
	for(int i=1;i<=N;++i) Fc[i]=Q*Prev[i]-P*i;
	Tr.build(1,1,N);
	Fc[N+1]=-INF;
	for(int i=1;i<=N;++i)
	{
		int l=i+C-1,r=N;
		while(l<r)
		{
			int mid=(l+r)>>1;
			if(Tr.queryMax(1,i+C-1,mid)<Fc[i-1]) l=mid+1;
			else r=mid;
		}
		if(l<=N&&Fc[l]-Fc[i-1]>=0) Rp[i]=l;
		else Rp[i]=-1;
	}
	for(int i=1;i<=N;++i) if(Rp[i]>0) Seg[++Cnt]={i,Rp[i]};
	std::sort(Seg+1,Seg+Cnt+1);
	int edpos=-1;
	for(int i=1;i<=Cnt;++i) if(edpos<Seg[i].l) ++ans,edpos=Seg[i].r;
	write(ans);
	return 0;
}

事实上，区间最值问题用 表维护是最合适的，时间复杂度可以优化到 （查询时调用 表时是 的，明显优于线段树）。

相关文章