题解汇总
A. Chery 的魔法药水与 lrc 的韭菜
这个题目是我们前面的月考卷子改编后的 idea，去年就出了，今年翻出来经过加强得到了这道入门
题目。
首先，不要畏惧输入格式……仔细阅读应该是可以理解使用方式的。
Subtask 1
\(\Theta(Tk)\)，模拟即可。
Subtask 2
令 \(f(k) = l\)，则：
\[\begin{aligned} \sum_{i = 1}^l\geq\dfrac{k + 1}{2}\\ \dfrac{l(l + 1)}{2}\geq\dfrac{k + 1}{2}\\ l(l + 1)\geq k + 1\\ l(l + 1) - 1\geq k\\ \end{aligned} \]容易观察到，\(l\) 是 \(\sqrt k\) 级别的，因此可以 \(\Theta(\sqrt k)\) 枚举到 \(f(k)\) 的值。
由于 \(m^3\) 被表示为 \(m\) 个连续奇数的和，那么有 \(1\) 个数答案为 \(1\)，\(2\) 个数答案为 \(2\)，\(3\) 个数答案为 \(3\)。所以算出 \(l\) 之后，答案就是先把前 \(l - 1\) 行的和累计，再单独计算第 \(l\) 行的和。
\(ans = \sum\limits_{i = 1}^{l - 1} {i^2} + l\times (\dfrac{k + 1}{2} - \dfrac{l(l - 1)}{2})\)。
计算 \(ans\) 也是 \(\Theta(\sqrt k)\) 的。
总复杂度 \(\Theta(T\sqrt k)\)。
Subtask 3
考虑优化 Subtask 2 的做法。
主体有两个部分，一个是计算 \(l\)，一个是累加平方和。我们分别优化。
- 计算 \(l\)，显然可以二分，\(\Theta(\log k)\)。
- 计算 \(\sum\limits_{i = 1}^l {i^2}\)。可以 \(\Theta(\sqrt k)\) 预处理前缀和 \(s_i = \sum\limits_{k = 1}^i{k^2}\)，每一次 \(\Theta(1)\) 查询。
时间复杂度 \(\Theta(\sqrt k+T\log n)\)。其中空间复杂度较高，需要 \(O(\sqrt k)\)。注意不要盲目开 long long，否则你会被卡空间。
Subtask 4
略有些毒瘤，意料之外。
为了题解的简洁，证明均写在最后。
首先可以证明 \(l = \operatorname{round}(\sqrt{k + 1})\)，其中 \(\operatorname{round}(x)\) 表示将 \(x\) 四舍五入到整数的值。虽然这和二分的时间复杂度相同，但是由于 \(k\) 的大小已经在 unsigned long long 的临界值，需要仔细思考，否则容易乘炸；若使用 __int128，需要注意写法的常数，若写法不优，会被我卡常。
然而 \(k + 1\) 仍然会爆 unsigned long long。你可以通过特判过题，也可以证明：\(\forall k = 2p + 1(p\in\mathbb{N}),\operatorname{round(\sqrt{k})}=\operatorname{round(\sqrt{k + 1})}\)。
至此，我们求出了 \(l\)。
对于平方和，有公式 \(\sum\limits_{i = 1}^{p}{i^2} = \dfrac{p(p + 1)(2p + 1)}{6}\)，则 \(ans = \dfrac{l(l - 1)(2l - 1)}{6} + l\times (\dfrac{k + 1}{2} - \dfrac{l(l - 1)}{2})\)。
然而 \(l(l - 1)(2l - 1)\) 爆 unsigned long long 了，所以你需要把三个数分别存下来，然后枚举哪个数含有因数 \(2\)，哪个数含有因数 \(3\)，手动除掉后再取模相乘。显然 \(l(l - 1)\) 是 \(2\) 的倍数且不会爆 unsigned long long，所以可以先除掉 \(2\)。
如果你会计算逆元，也可以使用逆元避免上面略显冗余的操作。
此外，还是因为 \(k + 1\) 爆 unsigned long long 了，所以显然可以转换成 \(\dfrac{k + 1}{2} = \dfrac{k - 1}{2} + 1\)。
此外，由于 \(k\) 太大，C++ 中的 sqrt 函数精度会被我卡，所以你需要使用 sqrtl 函数。
注意不要乱取模，否则可能减出负数导致挂大分。
\(ans = \dfrac{l(l - 1)(2l - 1)}{6} + l\times (\dfrac{k - 1}{2} + 1 - \dfrac{l(l - 1)}{2})\)
时间复杂度 \(\Theta(T\log n)\)。
证明：\(l = \operatorname{round}(\sqrt {k + 1})\)。
即证明此时 \(l(l + 1) - 1\geq k\)。
设整数 \(p\)。
- \(l < p + 0.5\)
由于都是整数，所以 \(p(p + 1 ) - 1\geq k\)，则 \(l\) 取 \(p\)，即“四舍”的值。
- \(l \geq p + 0.5\)
由于都是整数，所以 \(p(p + 1 ) - 1\leq k - 1\)，则 \(l\) 不能取 \(p\)，而应取 \(p + 1\)，即“五入”的值。
证明：\(\forall k = 2p + 1(p\in\mathbb{N}),\operatorname{round(\sqrt{k})}=\operatorname{round(\sqrt{k + 1})}\)。
考虑反证法。
若要不同，只有一种情况：\(\operatorname{round(\sqrt{k + 1})}\) “五入”，\(\operatorname{round(\sqrt{k})}\)“四舍”。
设整数 \(x\)，因为 \((x + 0.5)^2 = x^2 + x + 0.25\)，若要四舍，则 \(k = x^2 + x = x(x + 1)\)，必定是偶数，不符合题意。
B. 伤天害理的蚊子
Subtask 1
先通过时间复杂度为 \(n^2\) 以内的筛质数方法筛出 \(1\sim 5000\) 以内的质数，前缀和统计 \(s_i\) 表示 \(1\sim i\) 中的质数数量。再枚举区间左右端点，前缀和判断是否合法，统计一下即可。
Subtask 2
先通过时间复杂度为 \(n \times \sqrt n\) 以内的筛质数方法筛出 \(1\sim 3 \times 10^5\) 以内的质数，前缀和统计 \(s_i\) 表示 \(1\sim i\) 中的质数数量。定义一个数组 \(cnt\)，\(cnt_k\) 表示对于所有 \(s_i(i\ge l-1)\)，\(s_i=k\)的数量。对于一个满足条件的区间 \([l,r]\) 有 \(s_r-s_{l-1}=k\)。考虑枚举区间右端点 \(R\)，符合的左端点 \(L\) 只需要满足两个条件：\(L \ge l\) 且 \(s_{L-1}=s_R-k\)。即为 \(cnt_{s_R-k}\)。对于每个 \(R\) 累加答案即可。
Subtask 3
只需要将 Subtask 2 的筛质数方法时间复杂度优化到 \(n \log n\) 及以内即可。有欧拉筛与埃氏筛两种方法选择。
代码实现如下：
const int N = 5e6 + 5;
int l, r, k, sum[N], ans, cnt[N];
bool p[N];
signed main() {
p[1] = 1;
read(l, r, k);
for (int i = 2; i <= r; ++i) {
if (p[i]) continue;
for (int j = i + i; j <= r; j += i) {
p[j] = 1;
}
}
if (l == 1) ++cnt[0];
for (int i = 1; i <= r; ++i) {
sum[i] = sum[i - 1] + !p[i];
if (i >= l - 1) ++cnt[sum[i]];
}
for (int i = l; i <= r; ++i) {
if (sum[i] < k) continue;
ans += cnt[sum[i] - k];
}
write(ans);
return 0;
}
C. 回答
Solution
显然是模拟，但是要考虑巨多的细节。
首先对于每种单词我先同时存下来它的加 s 形式和不加形式（除了形容词）：
no["I"]=no["you"]=1;
fr1(i,1,n){
cin>>x;
no[x]=1;
no[x+'s']=1;
}
fr1(i,1,m){
cin>>x;
ad[x]=1;
}
fr1(i,1,p){
cin>>x;
vt[x]=1;
vt[x+'s']=1;
}
fr1(i,1,q){
cin>>x;
vi[x]=1;
vi[x+'s']=1;
}
接下来对于每一组询问进行处理就行了。
0.1 读入
使用 getline 读入，但是有一个很麻烦的事情是行末空格和换行，所以我们不妨这么写：
getline(cin,ask);
tnt=1;
cutter[1]="";
fr1(i,0,ask.length()-1){
if(!ok(ask[i])){
tnt++;
cutter[tnt]="";
continue;
}
cutter[tnt]+=ask[i];
r=i;
}
while(cutter[tnt].length()==0){
tnt--;
}
\(ok\) 函数的作用是判断这个字符是不是字母，反正遇到了不是字母的就新开一个单词。行末的换行和空格将会催生一堆空单词，因此最后要回退指针 \(tnt\)。我们用 \(r\) 记下来这个字符串实际有效的部分的最右侧。
0.2 计数拼写错误
主要要计数拼写错误，还要判断加了复数的专有名词、Is 和 yous。
fr1(i,1,tnt){
if(!vt.count(cutter[i])&&!vi.count(cutter[i])&&!no.count(cutter[i])&&!ad.count(cutter[i])){
if(cutter[i]=="Is"||cutter[i]=="yous"){
if(cutter[i]=="Is"){
cutter[i]="I";
}
else{
cutter[i]="you";
}
gmw++;
continue;
}
if('A'<=cutter[i][0]&&cutter[i][0]<='Z'){
if(cutter[i][cutter[i].length()-1]=='s'){
gmw++;
}
continue;
}
spw++;
}
}
每一个步骤都是显然的，这里不再说了，可以通过代码理解。
0.3 找出动词
直接在 map 里面查即可。
int verb=-1;
fr1(i,1,tnt){
if(vt.count(cutter[i])||vi.count(cutter[i])){
verb=i;
break;
}
}
0.4 找出左右名词
直接用谓语动词把整个句子劈成两半，左右各找一下就行了。我们保证过整个句子左右最多各一个名词。
int nounl=-1,nounr=-1;
fr1(i,1,verb-1){
if(isitn(cutter[i])||no.count(cutter[i])){//isitn的作用是判断是否是一个名词，也就是是否出现在名词表或者首字母大写
nounl=i;
break;
}
}
fr1(i,verb+1,tnt){
if(isitn(cutter[i])||no.count(cutter[i])){
nounr=i;
break;
}
}
0.5 各种情况判断
if(vt.count(cutter[verb])){//及物动词
if(nounr==-1){//但是后面没有名词
gmw++;
}
}
else{//不及物动词
if(verb!=tnt){//但是后面有东西
gmw++;
}
}
if(nounl!=-1){//左边有名词
if(cutter[verb][cutter[verb].length()-1]=='s'){//三单了
if(cutter[nounl][cutter[nounl].length()-1]=='s'||cutter[nounl]=="I"||cutter[nounl]=="you"){//但左边名词不太对
gmw++;
}
}
else{//没三单
if(cutter[nounl][cutter[nounl].length()-1]!='s'&&cutter[nounl]!="I"&&cutter[nounl]!="you"){//但左边名词不太对
gmw++;
}
}
}
else{//左边没有名词
if(cutter[verb][cutter[verb].length()-1]=='s'){//但是是三单
gmw++;
}
}
注释里面写的很完整。
0.6 输出组合
直接组合在一起并且输出计数器 \(gmw\) 和 \(spw\) 就行了。
if(spw==0&&gmw==0){
cout<<"Correct!"<<endl;
if('a'<=ask[0]&&ask[0]<='z'){
ask[0]='A'+ask[0]-'a';//记得大写首字母
}
fr1(i,0,r){//只加入有效部分
ans+=ask[i];
}
ans+='.';
ans+=' ';//接上去
continue;
}
cout<<"Spell Wrong: "<<spw<<", Grammer Wrong: "<<gmw<<"\n";
cout<<"--------------"<<endl;
cout<<ans<<endl;
0.7 部分分给法
\(\rm Subtask\ 1\) 给了 \(O(nkT)\)，也就是先分段字符串，然后一个一个去匹配词性。
\(\rm Subtask\ 2\) 给了 \(O(nT)\)，可能是因为你每次都把大写首字母的单词放进了 \(\texttt{map}\)，然后每次都要重新赋值或者清空。
\(\rm Subtask\ 3\) 给了不愿意打及物动词的，这部分很简单。\(\rm Subtask\ 4\) 给的更离谱，只有动词直接判单复数就行了。
\(\rm Subtask\ 5\) 需要写上面的正解，复杂度 \(O(k\log n)\)，带了一个巨大常数。记得读入优化否则会很卡常。
D. 最大公约数问题
Subtask 1
可以观察到， \(n\) 的值域非常的小，只有 \(20\)，又由于取数方案是任意选择，所以我们可以考虑 dfs 枚举每一个 \(a_i\) 是否取出。
时间复杂度 \(O(2^n)\) 。
代码实现如下
#include<bits/stdc++.h>
const int N = 1e5 + 10, mod = 998244353;
using namespace std;
int n, k, a[N], now[N], cnt, ans;
int gcd(int x, int y) {return !y ? x : gcd(y, x % y);}
void dfs(int x) {
if(x > n) {
int g = now[1];
for(int i = 1; i <= cnt; ++i) g = gcd(g, now[i]);
if(g == k && cnt > 1) ++ans, ans %= mod; return ;
}
dfs(x + 1); now[++cnt] = a[x];
dfs(x + 1); --cnt;
}
int main() {
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++i) scanf("%d", a + i);
dfs(1); printf("%d\n", ans);
return 0;
}
Subtask 2
观察到前三个个 Subtask 的 \(a\) 的值域都十分的小，而答案又与值域相关，所以从值域下手，就可以考虑 dp 。
设状态 \(dp_{i,x}\) 表示从前 \(i\) 个数中取数并取出 \(a_i\)， 且\(\gcd(b_1,b_2,b_3\cdots b_p)=x\) 的方案数。因为取出了 \(a_i\)，所以考虑之前取出的数。设之前取出的数的 \(\gcd=q\)，那么答案只需要统计 \(\gcd(q,a_i)=x\) 时的情况，还有一点就是我之前统计的 \(dp\) 值都至少是取了两个数的情况，所以我们还要考虑在前面只取一个数的情况，所以还要计数一下前 \(i-1\) 个数有多少个数 \(a_j\) 满足 \(\gcd(a_i,a_j)=x\)即可。状态转移方程如下
\[dp_{i,x}=\sum_{j=1 \land \gcd(q,a_i)=x}^{i-1} dp_{j,q}+\sum_{j=1}^{i-1}[\gcd(a_j,a_i)=x] \]时间复杂度 \(O(nv^2)\) ，\(v\) 表示 \(a_i\) 的值域。
代码实现如下
#include<bits/stdc++.h>
const int N = 1e3 + 10, mod = 998244353;
using namespace std;
int n, k, num[N], sum[N], a[N], ans, dp[N][N], mx;
int gcd(int x, int y) {return !y ? x : gcd(y, x % y);}
signed main() {
cin >> n >> k;
for(int i = 1; i <= n; ++i) cin >> a[i], mx = max(mx, a[i]);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= mx; ++j) {
for(int p = 1; p <= mx; ++p) {
if(gcd(a[i], p) != j) continue;
dp[i][j] += (sum[p] + num[p]) % mod;
dp[i][j] %= mod;
} sum[j] += dp[i][j]; sum[j] %= mod;
} ++num[a[i]]; ans += dp[i][k]; ans %= mod;
} cout << ans << endl;
return 0;
}
Subtask 3
考虑将 Subtask 2 的做法优化到 \(O(nv)\) 或者乘上 \(\log\) 的复杂度。
很容易发现如果一个 \(q\) 满足 \(\gcd(a_i,q)=x\) 时， \(q\) 和 \(a_i\) 一定是 \(x\) 的倍数且 \(\gcd(\dfrac{a_i}{x},\dfrac{q}{x})=1\)。那么我们对于每一个 \(dp_{i,x}\) 可以枚举 \(q'=\dfrac{q}{x}\) 的值去转移，那么转移方程如下
\[dp_{i,x}=\sum_{j=1\land \gcd(\dfrac{a_i}{x},q')=1}^{i-1}dp_{j,x\times q'}+\sum_{j=1}^{i-1}[\gcd(a_j,a_i)=x] \]不难发现枚举 \(q'\) 的复杂度是 \(\dfrac{v}{1}+\dfrac{v}{2}+\dfrac{v}{3}+\cdots +\dfrac{v}{v}\) 的，这个数由调和集数可得复杂度为 \(O(v\log v)\)。
最终时间复杂度 \(O(nv\log v)\)。
代码实现如下
#include<bits/stdc++.h>
const int N = 1e5 + 10, M = 1e2 + 10, mod = 998244353;
using namespace std;
int n, m, a[N], cnt, sum[M], num[M], mx, dp[N][M], ans;
int gcd(int x, int y) {return !y ? x : gcd(y, x % y);}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) scanf("%d", a + i);
for(int i = 1; i <= n; ++i) {
if(a[i] % m) continue;
a[++cnt] = a[i] / m;
mx = max(a[cnt], mx);
} n = cnt; cnt = 0;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= mx; ++j) {
if(a[i] % j) continue;
for(int k = 1; k <= mx / j; ++k) {
if(gcd(a[i] / j, k) != 1) continue;
dp[i][j] += sum[j * k]; dp[i][j] %= mod;
dp[i][j] += num[j * k]; dp[i][j] %= mod;
} sum[j] += dp[i][j]; sum[j] %= mod;
} num[a[i]]++; ans += dp[i][1]; ans %= mod;
} printf("%d\n", ans);
return 0;
}
Subtask 4
由于答案肯定只能选出为 \(k\) 的倍数的数，所以把这些数都拿出来。但是可以发现如果在这些数中任意选的话，会出现一些不合法的情况，比如说：当 \(k=4\) 时，选出来的数为 \(4,8,16\)，那么像 \(8,16\) 这种方案的 \(\gcd=8\) 并非等于四。但是我们可以发现这些另外不合法的情况的 \(\gcd\) 都是 \(k\) 的倍数，所以我们可以在所有的挑选方案中去除这些 \(\gcd > k\) 的情况，此时拿一个数组 \(ans_i\) 记录当 \(k=i\) 时的答案。
那么在求 \(ans_i\) 时需要用到 \(i\) 的倍数的答案，总复杂度为 \(O(v\log v)\)。
代码实现如下
#include<bits/stdc++.h>
#define int long long
const int N = 1e5 + 10, mod = 998244353;
using namespace std;
int n, k, cy[N], cnt[N], mx, a[N], ans[N];
int qpow(int x, int b) {
if(!b) return 1;
int num = qpow(x, b >> 1);
num *= num; num %= mod;
if(b & 1) num *= x, num %= mod;
return num < 0 ? num + mod : num;
}
signed main() {
cin >> n >> k;
for(int i = 1; i <= n; ++i) {
cin >> a[i], cy[a[i]]++;
mx = max(a[i], mx);
}
for(int i = 1; i <= mx; ++i) {
for(int j = 1; j <= mx / i; ++j) {
cnt[i] += cy[i * j];
}
}
for(int i = mx; i; --i) {
ans[i] = qpow(2, cnt[i]);
for(int j = 2; j <= mx / i; ++j) {
ans[i] -= ans[i * j];
} ans[i] -= cnt[i] + 1;
ans[i] %= mod, ans[i] += mod; ans[i] %= mod;
} cout << ans[k] << endl;
return 0;
}