Reincarnation

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

暑假2025OI复健

发表于 分类于
本文字数： 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;
}
/*

*/
相关文章