Reincarnation

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

长沙一中集训 模拟赛2

发表于 分类于 ，
本文字数： 9.8k 阅读时长 ≈ 9 分钟

少见的简单题。

A. 愚者（fool）

题目简介

给定一个数字串 ，要求使用其中的数字重组出两个数 ，不允许包含前导 ，且 分别为第一二关键字最小。若无解则 。

数据范围：

考虑签到。

的位数越少越好，所以我们枚举 的位数 ，特判 ，如果此时 则无解，否则填最小的出现过的数，只有 时 可以 开头，否则开头后从小到大依次填。

然后特判 ，此时只有 成立，所以记录 表示 出现的次数，如果 则有解，否则无解。

然后没有啥需要特判了，帮 拍的时候发现 的时候无解，插点挂掉。

时间复杂度 。

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
#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=40;
char Str[MAXN];
int Cnt[10],Cntsum;
int main()
{
	freopen("fool.in","r",stdin);
	freopen("fool.out","w",stdout);
	scanf("%s",Str+1);
	int N=std::strlen(Str+1);Cntsum=N;
	for(int i=1;i<=N;++i) ++Cnt[Str[i]-'0'];
	if(Cntsum<=1) return puts("-1 -1"),0;
	for(int k=1;k<=18;++k)
	{
		if(Cntsum-k>19) continue;
		if(Cntsum-k==19)
		{
			if(Cnt[0]>=18&&Cnt[1]>=1)
			{
				Cnt[0]-=18,Cnt[1]--;
				for(int i=1;i<=9;++i) if(Cnt[i]){ write(i);--Cnt[i];break; }
				for(int i=0;i<=9;++i) while(Cnt[i]) write(i),--Cnt[i];
				write(' ',(ll)1e18,'\n');
				return 0;
			}
			continue;
		}
		if(k==1)
		{
			for(int i=0;i<=9;++i) if(Cnt[i]){ write(i,' ');--Cnt[i];break; }
			if(Cntsum-k==1)
			{
				for(int i=0;i<=9;++i) if(Cnt[i]){ write(i,'\n');break; }
				return 0;
			}
			else
			{
				for(int i=1;i<=9;++i) if(Cnt[i]){ write(i);--Cnt[i];break; }
				for(int i=0;i<=9;++i) while(Cnt[i]){ write(i);--Cnt[i]; }
				return 0;
			}
		}
		else
		{
			int cnt=1;
			for(int i=1;i<=9;++i) if(Cnt[i]){ write(i);--Cnt[i];break; }
			for(int i=0;i<=9;++i)
			{
				while(Cnt[i])
				{
					write(i);--Cnt[i];
					++cnt;
					if(cnt>=k) break;
				} 
				if(cnt>=k) break;
			}
			putchar(' ');
			for(int i=1;i<=9;++i) if(Cnt[i]){ write(i);--Cnt[i];break; }
			for(int i=0;i<=9;++i) while(Cnt[i]){ write(i);--Cnt[i]; }
			return 0;
		}
	}
	if(Cnt[0]==36&&Cnt[1]==2&&N==38) write((ll)1e18,' ',(ll)1e18,'\n');
	else write("-1 -1");
	return 0;
}
/*

*/

B. 魔术师（magician）

题目简介

维护一个初始为空的序列 ，一共 次操作：

  • 在序列末尾插入 ；
  • 将序列排序；
  • 求序列头元素并删除。

数据范围：

考虑诈骗。

居然和出题人一个脑回路，想了十多分钟才发现被骗了。在任何时刻，整个序列都可以被分为前后半段，前半段有序，后半段无序。每次排序操作相当于将无序段合并进有序段，这个操作很熟悉，我们想到了 std::priority_queue，所以前半段用优先队列，后半段可以用双端队列维护，队头的修改只会在前半段为空时出现。

时间复杂度 。

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=5e5+10;
int Q;
std::priority_queue<int,std::vector<int>,std::greater<int>>Pq;
int a[MAXN],Head=1,Tail;
int main()
{
	freopen("magician.in","r",stdin);
	freopen("magician.out","w",stdout);
	read(Q);
	for(int opt,qx;Q--;)
	{
		read(opt);
		if(opt==1)
		{
			read(qx);
			a[++Tail]=qx;
		}
		else if(opt==2)
		{
			for(int i=Head;i<=Tail;++i) Pq.push(a[i]);
			Tail=0,Head=1;
		}
		else
		{
			if(Pq.empty()) write(a[Head++],'\n');
			else
			{
				write(Pq.top(),'\n');
				Pq.pop();
			}
		}
	}
	return 0;
}
/*

*/

C. 女祭司（highpriestess）

题目简介

求出有多少个数对 满足：

  • ；
  • 存在正整数 使得 。

对 取模。

数据范围：，且 为质数。

考虑猜结论。

具体结论不会证，讲讲考场上的思路。

我们枚举 ，发现 的取值个数实际上就是最小的正整数 满足 ，也就是最小循环节。

但这并没有什么性质或者公式，但是给了我们一个暴力思路，所以我们尝试打表，将对应 的贡献打出来，容易发现全部都是 的因子。

然后你发现并没有办法知道每一个因子与 的对应关系，但是我们只需要求和，所以我们统计每个因子出现的次数，发现有些杂乱无章，但并非无迹可寻。

观察：

1
2
3
4
4 2
8 4
16 8
97 96

看前面乍一看猜测与倍数有关，但是第四个给了我们一点启示。

然后我们查表，发现 ，然后我们将 打出来，发现一一对应。

所以我们得到答案：

现在做到了 ，还差 。

然后你发现 是一个积性函数（我没发现， 发现的）。

所以我们分解 的质因数，对 暴力计算，这个好做，然后统一相乘即可。

时间复杂度 ，爆踩标算的 的牛鬼蛇神。

保留了暴力与调试，好让你知道这个结论真的是猜出来的。

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
#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){ 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; }
using Pir=std::pair<int,int>;
#define fir first
#define sec second
#define Mkr std::make_pair	
const int MAXN=4e6+10;
const int S=4e6;
const int Mod=998244353;
template<class T1,class T2>
inline void add(T1 &x,T2 y){ x=x+y>=Mod?x+y-Mod:x+y; }
ll P,ans;
inline ll qPow(ll a,ll b=Mod-2)
{
	ll res=1;
	for(;b;b>>=1,a=a*a%Mod) (b&1)&&(res=res*a%Mod);
	return res;
}
int pri[MAXN],Tot,phi[MAXN];
bool is[MAXN];
inline void sieve(int n)
{
	phi[1]=1;
	for(int i=2;i<=n;++i)
	{
		if(!is[i]) pri[++Tot]=i,phi[i]=i-1;
		for(int j=1;j<=Tot&&i*pri[j]<=n;++j)
		{
			is[i*pri[j]]=1;
			if(i%pri[j]==0)
			{
				phi[i*pri[j]]=pri[j]*phi[i];
				break;
			}
			phi[i*pri[j]]=phi[i]*(pri[j]-1);
		}
	}
}
std::vector<ll>vec;
inline void apart(ll x)
{
	for(ll i=2;i*i<=x;++i) if(x%i==0) vec.push_back(i),vec.push_back(x/i);
	if(x>1) vec.push_back(x);
}
inline ll getPhi(ll x)
{
	ll res=x;
	for(ll i=2;i*i<=x;++i)
		if(x%i==0)
		{
			res=res*(i-1)/i;
			while(x%i==0) x/=i;
		}
	if(x>1) res=res*(x-1)/x;
	return res;
}
inline ll F(ll p,ll k)
{
	ll delta=-1,mul=p,res=0;
	for(int i=1;i<=k*2;++i)
	{
		res=(res+(mul*delta%Mod+Mod)%Mod+Mod)%Mod;
		delta*=-1,mul=mul*p%Mod;
	}
	// write(p,' ',k,' ',res,'\n');
	return (res+1)%Mod;
}
inline void solve(ll x)
{
	ll ans=1;
	for(ll i=2;i*i<=x;++i)
		if(x%i==0)
		{
			ll cnt=0;
			while(x%i==0) ++cnt,x/=i;
			ans=ans*F(i,cnt)%Mod;
		}
	if(x>1) ans=ans*F(x,1)%Mod;
	write((ans+1)%Mod);
}
int main()
{
	freopen("highpriestess.in","r",stdin);
	freopen("highpriestess.out","w",stdout);
	read(P);
	// sieve(MAXN-10);
	// apart(P-1);
	solve(P-1);
	return 0;
	// std::sort(vec.begin(),vec.end());
	// vec.erase(std::unique(vec.begin(),vec.end()),vec.end());
	// // for(int x:vec) write(x,' ');
	// // puts("");
	// // return 0;
	// ll ans=2,Phi=getPhi(P-1);
	// for(int x:vec)
	// {
		// // write(x,' ',phi[x],' ',(ll)qPow(phi[(P-1)/x])*Phi%Mod,'\n');
		// if(x<=S) add(ans,(ll)x*phi[x]%Mod);
		// else add(ans,(ll)x*Phi%Mod*qPow(phi[(P-1)/x])%Mod);
	// }
	// write(ans);
	return 0;
}
/*

*/

D. 女皇（empress）

相关文章