C
题目大意
有 \(N\) 个编号分别为 \(1, 2, \dots, N\) 的钥匙。
其中一些是真钥匙，其他的都是假钥匙。
有一扇门，你可以插入任意数量的钥匙。
只有插入至少 \(K\)
把真钥匙，门才会打开。
已经对这些钥匙进行了 \(M\)
次测试。
其中，第 \(i\) 次测试过程如下：
- 将 \(C_i\) 把钥匙，分别是 \(A_{i,1}, A_{i,2}, \dots, A_{i,C_i}\)
插入门。
- 测试结果用一个英文字母 \(R_i\)
表示。
- \(R_i=\)
o 表示在第
\(i\) 次测试中门打开了。
- \(R_i=\)
x 表示在第
\(i\) 次测试中门没有打开。
有 \(2^N\)
种可能的钥匙组合，在这些组合中，你需要找出与任何测试结果都不矛盾的组合数。
给定的测试结果有可能是错误的，没有任何组合满足条件。在这种情况下，输出
\(0\)。
思路
就是暴力，但赛时时间复杂度分析错误（我以为是 \(2^n\times n\times m\times k\)，实际应是
\(2^n\times n\times
m\)），导致没做出来。
实际极限情况运算次数约为 \(2^{15}\times
15\times 100=49152000\approx 5\times 10^7\)，可以通过。
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
| #include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
i128 f=1;
x=0;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
x*=f;
}
void writing(i128 x)
{
if(x>=10)writing(x/10);
putchar(x%10+'0');
}
void write(i128 x)
{
if(x<0)
{
cout<<'-';
x=-x;
}
writing(x);
}
LL n,m,k,c[110],a[110][20],s;
LL f[20];
char r[110];
void dfs(LL x)
{
if(x==n+1)
{
rep(i,1,m,1)
{
LL sum=0;
rep(j,1,c[i],1)
{
sum+=f[a[i][j]];
}
if(!((sum>=k&&r[i]=='o')||(sum<k&&r[i]=='x')))return;
}
s++;
return;
}
dfs(x+1);
f[x]=1;
dfs(x+1);
f[x]=0;
}
int main()
{
cin>>n>>m>>k;
rep(i,1,m,1)
{
cin>>c[i];
rep(j,1,c[i],1)
{
cin>>a[i][j];
}
cin>>r[i];
}
dfs(1);
cout<<s<<endl;
return 0;
}
|
D
题目大意
给定整数 \(N\) 和 \(M\) ，计算 \(\displaystyle \sum_{k=0}^{N}\) \(\rm{popcount}\) \((k \mathbin{\&} M)\) 模 \(998244353\) 的结果。
思路
赛时没有一点思路，反映出我位运算练的少。
建议大家阅读官方题解，比较清晰，而且可以提升英语阅读能力。
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
| #include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
i128 f=1;
x=0;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
x*=f;
}
void writing(i128 x)
{
if(x>=10)writing(x/10);
putchar(x%10+'0');
}
void write(i128 x)
{
if(x<0)
{
cout<<'-';
x=-x;
}
writing(x);
}
LL n,m,sum;
void f(LL j,LL n)
{
sum+=((n>>(j+1))<<j);
sum%=MOD;
if(n&(1LL<<j))
{
sum+=((n&((1LL<<j)-1))+1);
sum%=MOD;
}
}
int main()
{
cin>>n>>m;
repn(i,0,60,1)
{
if(m&(1LL<<i))
{
f(i,n);
}
}
cout<<sum<<endl;
return 0;
}
|
E
题目大意
给你一个长度为 \(N\) 的序列 \(A=(A_1,\ldots,A_N)\) 。
求 \(\displaystyle
\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}\left\lfloor\frac{\max(A_i,A_j)}{\min(A_i,A_j)}\right\rfloor\)
.
这里， \(\lfloor x \rfloor\)
表示不大于 \(x\) 的最大整数。例如，
\(\lfloor 3.14 \rfloor=3\) 和 \(\lfloor 2 \rfloor=2\) 。
思路
好像和官方想一块去了，但觉得自己写的不够好，于是参考了官方题解。
设 \(A\) 中最大的元素是 \(M\) .
我们要对所有满足 \(i<j\) 的 \((i,j)\)
进行求和，又因为可以看出我们改变顺序并不会影响答案，于是乎我们可以重新排列序列
\(A\)。
那么，我们把 \(A\) 按升序排序。
此时，如果 \(i<j\) ，就有 \(A_i \leq A_j\) ，所以 \(\displaystyle
\left\lfloor\frac{\max(A_i,A_j)}{\min(A_i,A_j)}\right\rfloor =
\left\lfloor\frac{A_j}{A_i}\right\rfloor\) 。
于是，原式可以变形为： \[
\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^{N}\displaystyle
\left\lfloor\frac{A_j}{A_i}\right\rfloor =
\sum_{i=1}^{N-1}\sum_{n}n*g(A_i,n)
\]
其中 \(g(d,n)\) 是满足 \(\displaystyle
\left\lfloor\frac{A_j}{d}\right\rfloor=n\) 的 \(j\) 的个数。
设 \(C_x\) 是满足 \(A_i=x\) 的 \(i\) 的个数（此处原文可能笔误，题解上写的是
with，我觉得应该是 wich）。
通过预处理 \(C\) 的前缀和，可以
\(O(1)\) 算出 \(f(d,n)\)，具体见代码。
时间复杂度不证了，是 \(O(m\log
n)\)，可以通过。
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
| #include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
i128 f=1;
x=0;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
x*=f;
}
void writing(i128 x)
{
if(x>=10)writing(x/10);
putchar(x%10+'0');
}
void write(i128 x)
{
if(x<0)
{
cout<<'-';
x=-x;
}
writing(x);
}
LL n,sum,f[1000010],x;
int main()
{
cin>>n;
rep(i,1,n,1)
{
cin>>x;
f[x]++;
}
rep(i,1,1000001,1)f[i]+=f[i-1];
rep(i,1,1000000,1)
{
LL vitamin_D=f[i]-f[i-1];
rep(k,1,1000000/i,1)
{
sum+=k*(f[min(1000001LL,(k+1)*i-1)]-f[k*i-1])*vitamin_D;
}
sum-=vitamin_D*(vitamin_D+1)/2;
}
cout<<sum<<endl;
return 0;
}
|
总结&致谢
还是练得少，手比较生。
另外反映出我的两个问题：
- 位运算掌握不牢
- 分析时间复杂度方面掌握不牢
感谢 AtCoder 官方，提供了好题以及题解供我参考。