结果
题面
题解
T1
此题数据较弱,一些错误的做法也能通过全部数据。
本题只要记录一个前缀$OR$和$Pre_i$以及后缀$OR$和$Suf_i$,枚举修改的位置即可。
T2
首先对于一个人$i$,显而易见,他所能到达的格子一定是$gcd(a_i,n)$的倍数。
只要枚举$n$的约数,令当前枚举到的数为$d$,若存在一个$i$, 使得$gcd(a_i,n)|d$
说明所有$gcd(i, n) = d$的格子都能被到达,答案加上$φ(\frac{n}{d})$即可。
T3
状压$dp$, 首先把表达式的树形结构建出来, $dp_{i,j}$表示第$i$个表达式中,当$ABCD$的
值分别为$m$个条件中的值的时候, 表达式的结果为$j$的表达式的数目。
通过$\text{AND, OR}$卷积进行转移, 利用$FWT$或分治乘法优化即可。
代码
T1
1 | #include<bits/stdc++.h> |
T2
60分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#include<bits/stdc++.h>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;
inline int read()
{
int data = 0, w = 1;
char ch = getchar();
while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
return data*w;
}
inline int gcd(int x, int y)
{
while(y) y ^= x ^= y ^= x %= y;
return x;
}
const int maxn(60);
int n, m, a[maxn], ans;
int main()
{
file(running); n = read(); m = read(); ans = n - 1;
for(RG int i = 1; i <= m; i++) a[i] = gcd(read(), n);
for(RG int i = 1; i < n; i++) for(RG int j = 1; j <= m; j++) if(!(i % a[j])) { --ans; break; }
printf("%d\n", ans);
return 0;
}
T3
20分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#include<bits/stdc++.h>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;
inline int read()
{
int data = 0, w = 1;
char ch = getchar();
while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
return data*w;
}
char s[1000];
int A[20], B[20], C[20], D[20], E[20], len, q[1000], cnt, ans, m;
int val[300];
int Calc(int beg, int end)
{
if(end - beg == 0) return val[s[beg]];
int pos = end, x = 1;
for(RG int i = beg + 1; i <= end; i++)
{
if(s[i] == ')') x--;
if(s[i] == '(') x++;
if(!x) { pos = i; break; }
}
int a = Calc(beg + 1, pos - 1), b = Calc(pos + 3, end - 1);
if(s[pos + 1] == '|') return a | b;
else return a & b;
}
inline bool check()
{
for(RG int i = 1; i <= m; i++)
{
val['a'] = !(val['A'] = A[i]);
val['b'] = !(val['B'] = B[i]);
val['c'] = !(val['C'] = C[i]);
val['d'] = !(val['D'] = D[i]);
if(Calc(1, len) != E[i]) return false;
}
// printf("%s\n", s + 1);
return true;
}
void dfs(int x)
{
if(x == cnt + 1) { if(check()) ++ans; return; }
if(s[q[x] - 1] == ')' && s[q[x] + 1] == '(')
{
s[q[x]] = '&'; dfs(x + 1);
s[q[x]] = '|'; dfs(x + 1);
}
else
{
s[q[x]] = 'A'; dfs(x + 1);
s[q[x]] = 'B'; dfs(x + 1);
s[q[x]] = 'C'; dfs(x + 1);
s[q[x]] = 'D'; dfs(x + 1);
s[q[x]] = 'a'; dfs(x + 1);
s[q[x]] = 'b'; dfs(x + 1);
s[q[x]] = 'c'; dfs(x + 1);
s[q[x]] = 'd'; dfs(x + 1);
}
}
int main()
{
file(calculate);
scanf("%s", s + 1);
len = strlen(s + 1);
for(RG int i = 1; i <= len; i++) if(s[i] == '?') q[++cnt] = i;
m = read();
for(RG int i = 1; i <= m; i++) A[i] = read(), B[i] = read(), C[i] = read(), D[i] = read(), E[i] = read();
dfs(1);
printf("%d\n", ans);
return 0;
}