https://ac.nowcoder.com/acm/contest/1114
A. 超越学姐爱字符串
题意：问有多少种长为n的只有’c’和’y’的字符串满足没有两个相邻的’c’。
dp[i][0/1] 表示第i位为’c’或’y’，简单转移即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9+7;
int n;
int dp[N][2];
int main() {
cin >> n;
dp[1][0] = dp[1][1] = 1;
for (int i = 2; i <= n; i++) {
dp[i][0] = dp[i-1][1];
dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
}
cout << (dp[n][0] + dp[n][1]) % mod << endl;
return 0;
}
|
B. 美味果冻
题意：给定n，求 ∑i=1n∑j=1ii⋅⌊ji⌋j，n<=3000000
分块
j在指数上，没法整块计算，所以转换得到 ∑j=1n∑i=jni⋅⌊ji⌋j，这样只要单层循环遍历j，每次循环内再考虑对i分块，把 ⌊ji⌋ 相同的分一块。
同时为了避免每次重新计算幂次，所以要在前一次的基础上乘 ⌊ji⌋，得到 ⌊ji⌋j。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e6 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n;
ll p[N], ans;
void init(int k) {
for (int i = 1; i <= k; i++)
p[i] = p[i] * i%mod;
}
int main() {
cin >> n;
fill(p + 1, p + n + 1, 1);
for (int j = 1; j <= n; j++) {
int l = j, r = 2 * j - 1;
int limit = n / j;
init(limit);
for (int k = 1; k < limit; k++) {
ans = (ans + 1ll*(l + r)*j%mod*inv2%mod*p[k] % mod) % mod;
l += j; r += j;
}
ans = (ans + 1ll*(l + n)*(n - l + 1) % mod*inv2%mod*p[limit] % mod) % mod;
}
cout << ans << endl;
return 0;
}
|
C. 富豪凯匹配串
题意：有n个长度为m的01文本串，Q次询问，每次给定一个串，可能含有通配符’_'，问能和几个文本串完全匹配。1<=n,m<=1000,1<=Q<=3000。
bitset优化
由于只含01，所以用位运算+bitset更合适，但是要考虑处理通配符。
对于每个询问，处理出一个目标串tag，等于原询问串，再把串里的通配符都换成0.
再处理出一个串p，把询问串里除了通配符的位置都置为1，通配符处为0.
询问时，对于一个文本串如果p与文本串的&等于tag，则匹配。
很巧妙地利用了并的性质。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e6 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n, m, q;
bitset<1010>bt[1010], p, tag;
char s[1010], c;
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++){
scanf(" %c", &c);
bt[i][j] = c - '0';
}
}
scanf("%d", &q);
while (q--) {
scanf("%s", s);
for (int i = 0; s[i]; i++) {
if (s[i] == '1')p[i] = 1, tag[i] = 1;
else if (s[i] == '0')p[i] = 1, tag[i] = 0;
else p[i] = 0, tag[i] = 0;
}
int ans = 0;
for (int i = 0; i < n; i++) {
if ((bt[i] & p) == tag)ans++;
}
cout << ans << endl;
}
return 0;
}
|
D. 德育分博弈政治课
题意：有n个6面的骰子，每面数字1到9，且每面的数字都不同，Q次询问，每次问能否用这n个骰子拼出询问串。每个骰子只能用一次。Q 个字符串的总长度不超过 2000000，1<=n<=500000,1<=Q<=100。
最大流
每个骰子只能用一次，容易想到最大流模型，但是看到数据范围又虚了。
但是，一共只有6面，每面1到9，且每面都不同，并且要想到同样的数字，和排列方式不同，那么总的可能不超过 C96，完全可以网络流。
起点和骰子连边，每个骰子和它包含的数字连边，数字再和终点连边。
注意处理一下骰子重复的情况。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e7 + 10;
const int INF = 0x3f3f3f3f;
int n, Q, tot;
int val[1010][10], vis[N], cnt[1010], cc[10];
char s[N];
int cal(char* s) {
int ans = 0;
for (int i = 0; i < 6; i++) {
ans *= 10;
ans += s[i] - '0';
}
return ans;
}
struct mxfl
{
#define maxn 1010
int n = 0;
int m = 0;
int s, t;
struct Edge
{
int from, to, cap, flow;
};
vector<Edge>edges;
vector<int>G[maxn];
void init(int _n, int _s, int _t) {
n = _n;
s = _s;
t = _t;
edges.clear();
for (int i = 0; i < n; i++)G[i].clear();
}
void add_edge(int from, int to, int cap) {
edges.push_back(Edge{ from,to,cap,0 });
edges.push_back(Edge{ to,from,0,0 });
m = (int)edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool vis[maxn];
int d[maxn], cur[maxn];
bool bfs() {
memset(vis, 0, sizeof(vis));
queue<int>Q;
Q.push(s);
d[s] = 0;
vis[s] = 1;
while (!Q.empty()) {
int x = Q.front(); Q.pop();
for (int i = 0; i < (int)G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (!vis[e.to] && e.cap > e.flow) {
vis[e.to] = 1;
d[e.to] = d[x] + 1;
Q.push(e.to);
}
}
}
return vis[t];
}
int dfs(int x, int a) {
if (x == t || a == 0)return a;
int flow = 0, f;
for (int& i = cur[x]; i < (int)G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
e.flow += f;
edges[G[x][i] ^ 1].flow -= f;
flow += f;
a -= f;
if (a == 0)break;
}
}
return flow;
}
int maxflow() {
int flow = 0;
while (bfs()) {
memset(cur, 0, sizeof(cur));
flow += dfs(s, INF);
}
return flow;
}
}MF;
int main() {
scanf("%d%d", &n, &Q);
for (int i = 1; i <= n; i++) {
scanf("%s", s);
sort(s, s + 6);
int v = cal(s);
if (!vis[v]) {
vis[v] = ++tot;
for (int j = 1; j <= 6; j++)
val[tot][j] = s[j - 1] - '0';
}
cnt[vis[v]]++;
}
int S = 0, T = tot + 10;
while (Q--) {
scanf("%s", s);
MF.init(tot + 11, S, T);
for (int i = 1; i <= tot; i++) {
MF.add_edge(S, i, cnt[i]);
for (int j = 1; j <= 6; j++)
MF.add_edge(i, tot + val[i][j], cnt[i]);
}
memset(cc, 0, sizeof(cc));
for (int i = 0; s[i]; i++)
cc[s[i] - '0']++;
for (int i = 1; i <= 9; i++)
MF.add_edge(tot + i, T, cc[i]);
if (MF.maxflow() == (int)strlen(s))puts("dyf");
else puts("zzk");
}
return 0;
}
|
E. 老瞎眼 pk 小鲜肉
题意：给定一个数组，每次询问一个区间里是否有子区间满足异或和为0.
线段树+离线询问
很容易处理出每个位置最近的区间异或和为0的另一端点，但是规定了范围的话，就有可能另一端不在规定范围中。那么就必须要保证每次处理询问时，有值的地方一定合法。
先处理出每个位置左边最近的区间异或和为0的端点，把询问按照右端点从小到大排序，再滑动到达询问范围，每向右扩展一次，就用新加入的数更新左边的点，注意每次只会更新一个点，就是之前预处理出的那个点。
再用线段树维护每个点和它对应的右端点的距离最小值。每次询问时都能保证线段树上的值的右端点都是在范围内的，因为范围外的还没有更新。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e6 + 10;
const int INF = 0x3f3f3f3f;
int n, Q;
int a[N], d[N], vis[N], sum, ans[N];
struct X{
int l, r, id;
}qq[N];
bool cmp(const X& a, const X& b) {
return a.r < b.r;
}
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int tr[N << 2];
void up(int rt) {
tr[rt] = min(tr[rt << 1], tr[rt << 1 | 1]);
}
void update(int l, int r, int rt, int q, int x) {
if (l == r) {
tr[rt] = x;
return;
}
if (q <= mid)update(lson, q, x);
else update(rson, q, x);
up(rt);
}
int query(int ql, int qr, int l, int r, int rt) {
if (ql <= l && qr >= r)return tr[rt];
int ans = INF;
if (ql <= mid)ans = min(ans, query(ql, qr, lson));
if (qr > mid)ans = min(ans, query(ql, qr, rson));
return ans;
}
int main() {
scanf("%d%d", &n, &Q);
for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
memset(vis, -1, sizeof(vis));
vis[0] = 0;
for (int i = 1; i <= n; i++) {
sum ^= a[i];
d[i] = vis[sum] + 1;
vis[sum] = i;
}
for (int i = 1; i <= Q; i++) {
scanf("%d%d", &qq[i].l, &qq[i].r);
qq[i].id = i;
}
sort(qq + 1, qq + Q + 1, cmp);
int c = 1, R = 1;
memset(tr, 0x3f, sizeof(tr));
while (c <= Q) {
while (R <= qq[c].r) {
if (d[R])update(1, n, 1, d[R], R - d[R] + 1);
R++;
}
while (c <= Q && qq[c].r == R - 1) {
ans[qq[c].id] = query(qq[c].l, qq[c].r, 1, n, 1);
c++;
}
}
for (int i = 1; i <= Q; i++)printf("%d\n", ans[i] == INF ? -1 : ans[i]);
return 0;
}
|
