【泛做】简单题选做 · 第四弹

因为这个 Typora 有点锅和自己电脑性能问题,文章太长就会很自闭。于是打算尽量精简一下题面,这样一篇文章整理的就会多一点。

预计会有不知道多少题题。慢慢更。

#warning: 本篇难度无限接近普及组,仅供个人娱乐。可以选择性忽略。

[Topcoder SRM 518 Div1] Hard Nim

有 $n$ 堆石子,每堆石子个数都必须是 $\leq m$ 的某个质数。玩 nin 游戏,求有多少种方式先手胜。

$1\leq n\leq 10^9,1\leq m\leq 10^5$ 。

不能算是一眼秒了…但也是最多三眼?考虑因为 nim 游戏只关心每堆石子个数的异或和,如果堆数比较少就可以直接卷几次 FWT。更多的话…观察到 $n\leq 10^9$ 就不难知道要快速幂。然后就做完了

[CF Round#643 Div2] C

给定 $A, B, C, D$,求有多少个三边长度分别为 $x,y,z$ 的三角形满足

要求线性。

就是弱智题?考虑枚举最大的边长,然后发现对于每个 $x\in[A, B]$ ,对应的 $y$ 的数量就是一个等差数列的形式。不过这题边界说实话比较烦人…

[CF Round#643 Div2] F

交互题。

设置一个数 $X\in[1,10^9]\cap \mathbb{Z_{+}}$ 。最多可以询问 $22$ 次,每次询问一个long long 范围内的数 $Y$ 后反馈 $\gcd(X, Y)$ 。最后需要输出 $X$ 的约束个数。

最后答案可以有一定误差,设 $d$ 为标准答案,那么只需要满足:

霉吹联盟

一个比较直接的暴力是考虑对每个 $\leq \sqrt{10^9}$ 的素数的最大幂进行 check,然后二分出指数。但是这样做需要 $3300+$ 次的询问…然后考虑如何把状态压一压。发现只需要最多 $10^9$ ,但是可以询问 $10^{18}$,于是可以把相邻状态压一压。然后发现还是 WA on 5 .

然后又有一个更压的方法,就是考虑每次选取相邻几个质数的最小公倍数,然后这样筛过一遍就可以知道有哪些数要去筛。然后再把这里面的相邻组合…大概就是在上面一个方法外面套一个分组。但这样需要调整分界线。然后…然后就过了 XD

「My-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
#include <cmath>
#include <bitset>
#include <cstdio>
#include <iostream>

using namespace std ;

typedef long long ll ;

const int Mp = 4000 ;

const int Mx = 1000000000 ;

int T, used ;
int pos[Mp], res ;

template <typename T>
void debug(T x, char c = '\n'){ cerr << x << c ; }

template <typename T>
void debug(T *const tp, int minn, int maxn, char v = ' ', char c = '\n'){
for (int i = minn ; i <= maxn ; ++ i) debug(tp[i], v) ; cerr << c ;
}

namespace Euler{
#define MAXN 51000
bitset <MAXN> vis ;
int pr[MAXN], A, i, j, cnt ;
void Ego(){
int N = sqrt(Mx) ;
vis[1] = vis[0] = 1 ;
for (i = 2 ; i <= N ; ++ i){
if (!vis[i]) pr[++ cnt] = i ;
for (j = 1 ; j <= cnt ; ++ j){
if (i * pr[j] > N) break ;
vis[i * pr[j]] = 1 ;
if (!(i % pr[j])) break ;
}
}
}
}

int tp ;
int ng ;
int tot ;
ll gp[Mp] ;
int stk[Mp] ;
int lrg[Mp] ;
int rrg[Mp] ;

int main(){
cin >> T ;
// for (int i = 1 ; i <= 44 ; ++ i)
// cout << num[i] << '\n' ;
Euler :: Ego() ;
lrg[tot = 1] = 1 ;
using namespace Euler ;
int x, y, z, q1, q2 ; ll o = 1 ;
for (int i = 1 ; i <= cnt ; ++ i)
pos[i] = log(Mx) / log(pr[i]) ;
for (int i = 1 ; i <= cnt ; ++ i){
if (1.0 * o * pr[i] > 1e18)
gp[tot] = o, rrg[tot] = i - 1, lrg[++ tot] = i, o = 1 ;
o *= pr[i] ;
}
// debug(gp, 1, tot) ;
// debug(lrg, 1, tot) ;
// debug(rrg, 1, tot) ;
while (T --){
ng = 1 ;
res = 1 ;
used = 0 ;
do {
tp = 0 ; ++ used ;
cout << "? " << gp[ng] << endl, cin >> y ;
for (int i = lrg[ng] ; i <= rrg[ng] ; ++ i)
if (y % pr[i] == 0) stk[++ tp] = i ; //cout << tp << '\n' ;
for (int i = 1 ; i <= tp ; ){
if (used >= 22) break ;
q1 = 0, q2 = 0 ; x = 1, z = 1 ;
x = pow(pr[stk[i]], pos[stk[i]]) ;
if (i < tp)
z = pow(pr[stk[i + 1]], pos[stk[i + 1]]) ;
cout << "? " << 1ll * x * z << '\n' ;
cin >> y ; ++ used ;
while (y % pr[stk[i]] == 0)
++ q1, y /= pr[stk[i]] ;
if (i < tp)
while (y % pr[stk[i + 1]] == 0)
++ q2, y /= pr[stk[i + 1]] ;
res *= (q1 + 1) * (q2 + 1) ; i += 2 ;
// cout << res << '\n' ;
}
++ ng ;
// cout << used << "#\n " ;
} while(used < 22) ;
cout << "! " << max(res * 2, res + 7) << endl ;
}
return 0 ;
}

大概算了 一下,发现这个不是很容易卡掉。证明方式大概可以考虑分类讨论 $\approx 10^3$ 的质数个数。

发现这样最多只能 check 到前 $153$ 个质数。考虑此时质数大小已经是 $900$ ,而 $10^9$ 至多分成 $3$ 个在 $10^3$ 左右的质数之积,考虑如果三个质数都没筛到那么 $res=1$ ,在 $+7$ 之后必然符合误差范围;如果只剩下一个质数没被筛到那么 $\times 2$ 之后必然合法;如果剩两个质数没被筛到,那么除去这两个较大的剩下的最大也只有 $1200$ 左右,而 $\leq 1200$ 的数最多含有 $4$ 个不同的质因子,同时用到超过第一个块(即超过前 $15$ 个质数)的最多会有 $1$ 个,毛估估一下发现 $22$ 次是绰绰有余的。

[CF Round #633(Div2) A]

……题面不搬了。

考虑 $n$ 每次 $+1$,可以拆成两个单独的小菱形加上 $n-1$ 的方案,那么看上去通过分类讨论在左边插入还是右边插入,答案应该为

但是这并不对,因为两种方式会有重复。发现重复就重复在共同使用了中间那个大小为 $n-2$ 的多边形上。于是可以知道正确的递推应该是

归纳可得 $f(n)=n$。

[CF Round #622(Div2) B]

一项奥林匹克竞赛有着与普通竞赛不同的规则,它分成两轮,假如一位参赛者在第一轮中排名第 $x$ 名,在第二轮中排名第 $y$ 名,则他的总分是 $x+y$,他的总排名是总分小于等于 $x+y$ 的参赛者(包括他自己)。需要注意的是,每一轮比赛都不会出现并列的情况,每一个排名 $i$ 都对应了唯一的参赛者。

尼古拉被告知他第一轮排名第 $x$,第二轮排名第 $y$ ,他需要你帮助他算出他可能获得的最好总排名和最差总排名。

首先不难知道最大值是 $\min\{x+y,n\}$ 。考虑如果 $x+y<n$,那么其他人的排名可以让一场比尼古拉小,一场比尼古拉大,这样稍微安排一下就可以使得尼古拉成为第一名。但是如果 $x+y\geq n$ 。嗯,欧神说猜出答案来就算完,不管了不管了(

[CF Round #626(Div1) A]Unusual Competitions

有一个长度为 $n$ 的括号序列。

你可以进行若干次操作:花费 $m$ 的代价,将一个长度为 $m$ 的括号子串任意排列。

若能将括号序列排成合法的括号序,请求出最小花费的代价和。否则请输出 -1

考虑自然是当 () 数量相等但是没能匹配成功的时候才能重排,并且考虑一长段重排和几小段分别重排本质是相同的,因为每次重排相当于选择相等数量的几个左括号和右括号交换位置。

感觉写这个题的时候还是不细心。细节写丢了好几次。

[CF Round #626(Div2) B]Count Subrectangles

给定长为 $n$ 的数组 $a$ 和长为 $m$ 的数组 $b$,数组中的元素均是 $0$ 或 $1$。有 $n\times m$ 的矩阵 $c$,$c_{i,j}=a_i \cdot b_j$。请求出矩阵 $c$ 面积为 $k$ 的全 $1$ 子矩阵数量。

$1\leq n,m\leq 10^6$。

不难知道就是统计含 $1$ 的连续段然后分别贡献一下。当然我用了个并查集就导致实现很臃肿疯狂爆 OJ

[CF Round #399(Combined) B]Code For 1

有一个序列,初始时只有一个数 $n(0\le n\le2^{50})$。

对于序列中每一个 $>1$ 的数,拆分成三个数$ \lfloor\frac n2\rfloor,n\bmod2,\lfloor\frac n2\rfloor$ 并替换原数,直到序列中没有>1的数为止。

查询最终序列中 $ [l,r] (1\le l,r)$ 中有多少 $1$。

同时 $l,r$ 满足 $0\le r - l\le10^5$。

不难发现最后会构成一棵共有 $2^k$ 个节点的分治树,其中 $k=\lceil\log_2 n\rceil$ 。但是这其中有很多部分是重复的。随便画一下图可以发现对于区间内所有的奇数位置都会是一样的结果,取决于最后 $n$ 不断除以 $2$ 下取整是 $0$ 还是 $1$ 。而对于偶数位置则是某些 $n’\mod 2$ 。发现这些偶数位置的深度可能会有不同,同一深度结果相同。于是就可以预处理出每个深度的答案。最终复杂度 $O((r-l)\log n)$ 。

[CF Round #399(Combined) F] Barrels and boxes

有 $w$ 箱酒,$f$箱食物。

现在要把这些箱子摞成相邻的若干堆,要求每一堆都必须是同类型的箱子,且相邻堆类型不同。

堆的高度定义为所有的箱子数。问所有 用酒箱子做成的堆 高度都大于 $h$ 的概率。

一开始觉得是分拆数,后来发现是有序的分拆数,就变成插板法 sb 题了。

考虑本质上「堆」就是对总量的一个有序拆分。而这里不同的是总方案数要求不能存在某些位置放 $0$ 的情况。考虑如果可以放 $0$ 那么就是一个 $n$ 元线性不定方程组非负整数解的个数,这个地方要求 $k$ 个位置都 $\geq 1$ 的话,就只需要将等号右边的 $w/f$ 改成 $w-k$ 和 $f-k$ 即可。考虑合法方案数也是一样的道理,变成了 $w-h\cdot k$ 和 $f-h\cdot k$ 。

然后就可以考虑对每个堆数计数。发现对于一个数量 $n’$ 两者只会放 $\left\lfloor\dfrac{n}{2}\right\rfloor$ 和 $\left\lceil\dfrac{n}{2}\right\rceil$ 的数量,随便算一下即可。

[CF Codefest 18 E] Trips

一共有 $n$ 个人,他们开始互不认识,而每天早上不认识的两个人会变成朋友。一共有 $m$ 天,每天晚上有的人要去旅行,去旅行的人必须满足 ta 有至少 $k$ 个朋友也去旅行

秒掉了…然而还是想了一会儿的。大概是考虑倒着做,每次删边,然后考虑拿个小根 multiset 维护可以去旅行的人的度数集合就好了。

[CF Round#400 (Combined) E] The Holmes Children

定义函数 $f(x)$

定义函数 $g(x)$

定义函数 $F_k(n)$ .

给定 $n,k$,求 $F_k(n)$ 。

$1\leq n,k\leq 10^{12}$ 。

简单题,满满的套路…考虑 $\gcd(a,b-a)=\gcd(a,b)$ ,那么 $f(x)=\varphi(x)$ 。同时根据 $\varphi$ 反演的式子可以得到 $g(x)=x$ 。那么就可以发现 $F_k(n)$ 大概是一个这样的分布:

然后随便打个表可以发现这东西是 $O(\log n)$ 的。暴力求到 $\varphi(n)=1$ 就好了。