上蓝了！
A. Consecutive Sum Riddle
题意
给一个$n$，你需要构造一个整数区间$[L,R]$,其和等于$n$
分析
取$[-n+1,n]$即可。
B. Special Numbers
题意
给出一个 $n$ , 另一个数 $m$ 如果可以表示成 $n$ 的不同幂次之和，则称 $m$ 是 special 的。现在给出 $n$， 将所有 special 的数升序排序，问第 $k$ 个数是多少。
分析
假如一个数是 $n^0+n^1+n^4$ ， 我们不妨用二进制表示，转化为 $10011_{(2)}$ ，也就是说现在给了一个二进制的数，但是其每个位的权值要乘以 $n$. 那么第 $k$ 个数表示成二进制自然就是 $k_{(2)}$ 本身了，模拟快速幂求即可。
代码
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
| #include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define pii pair<int, int>
using namespace std;
const int mod = 1e9 + 7;
signed main() {
DDLC_ESCAPE_PLAN_FAILED;
int t;
cin >> t;
while(t--) {
int n, k;
cin >> n >> k;
int ans = 0;
int x = 1;
while(k) {
if(k & 1) {
ans = (ans + x) % mod;
}
x = (x * n) % mod;
k >>= 1;
}
cout << ans << endl;
}
return 0;
}
|
C. Make Them Equal
题意
给一串字符串，你要通过一些操作把它的所有字符全部变成 $c$：
选择一个数字 $x, 1\leq x\leq n$. 字符串中所有下标 $i$ 中 $i\ mod\ x \neq 0$ 的下标都将被替换为 $c$.
分析
首先贪心考虑，如果 $x$ 取 $n$，那么 $[1,n-1]$ 必定全部都可以替换，接下来再取个 $n-1$，把 $n$ 替换即可。故不管怎样，答案最多为2.
所以只需要考虑答案为1的情况了。这里我们可以直接暴力统计所有不等于 $c$ 的下标的因数，如果不同因数的个数小于 $n$ ，说明一定可以找到一个 $x$ 使得所有字符为 $c$.
代码
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
| #include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define pii pair<int, int>
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
using namespace std;
const int maxn = 3e5 + 10;
bool v[maxn];
signed main() {
DDLC_ESCAPE_PLAN_FAILED;
int t;
cin >> t;
while(t--) {
int n;
string s; char c;
cin >> n;
s += '#';
string tmp;
cin >> c;
cin >> tmp;
s += tmp;
bool flag = 1;
vector<int> pos;
for (int i = 1; i <= n; ++i) v[i] = 0;
for (int i = 1; i <= n; ++i) if(s[i] != c) {
flag = 0; pos.pb(i);
}
if(flag) {
cout << 0 << endl;
continue;
}
int cnt = 0;
for (auto &i : pos) {
if(!v[i]) v[i] = 1, cnt++;
for (int j = 1; j * j <= i; ++j) {
if(i % j == 0 && !v[j]) v[j] = 1, cnt++;
if(i % j == 0 && !v[i / j]) v[i / j] = 1, cnt++;
}
}
if (cnt == n) {
cout << 2 << endl;
cout << n << ' ' << n - 1 << endl;
}
else {
cout << 1 << endl;
for (int i = 1; i <= n; ++i) if(!v[i]) {
cout << i << endl;
break;
}
}
}
return 0;
}
|
D. The Number of Imposters
题意
有一张 $n$ 个节点的图，每条边都是单向边 $(i,j,c)$ 表示第 $i$ 个人说第 $j$ 个人是个说谎的人/说实话的人。且如果一个人是说谎的人，那他说的一定是假，否则一定是真。
问这张图最多有几个说实话的人。
分析
单向图其实可以直接转化为无向图，这是等价的。 $a$ 说 $b$ 是假的，其实和 $b$ 说 $a$ 假是一样的，可以列真值表证明。
而且，只要连通图中有一个人的真假确定了，其他人的真假一定也确定了。
所以，转化为无向图之后再记忆化搜索就可以了，对每个连通块进行 dfs ，$dp[i][0]$ 表示第 $i$ 人说谎的情况下他和他的子节点中说实话的人有多少；$dp[i][1]$ 表示 $i$ 说实话的情况下的答案。
注意矛盾的情况，搜索过程中每个节点要保存自己的当前真假情况，这样在子节点指回祖先节点时判断一下矛不矛盾就可以了。
所以对每个连通块搜索的根节点，假设其为实话或者谎话，分别 dfs 两次，取最大值即可。
其实也可以写的更简单的，但是昨天越写越奇怪，有点没稳住，思路太乱了。
不仅思路较为冗杂，代码也特别丑qwq
代码
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
| #include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define pii pair<int, int>
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
using namespace std;
const int maxn = 2e5 + 10;
int n, m;
int dp[maxn][2];
vector<pii> e[maxn];
bool v[maxn];
bool flag = 0;
int fa[maxn];
int st[maxn];
vector<int> tmp;
void dfs(int i, int l) {
tmp.pb(i);
st[i] = l + 1;
for (auto &x : e[i]) {
if(st[x.first]) {
if(l == 1 && x.second == 0 && st[x.first] == 2){
flag = 1;
}
else if(l == 1 && x.second == 1 && st[x.first] == 1) {
flag = 1;
}
else if(l == 0 && x.second == 1 && st[x.first] == 2) {
flag = 1;
}
else if(l == 0 && x.second == 0 && st[x.first] == 1) {
flag = 1;
}
continue;
}
if(l == 1 && x.second == 0) {
dfs(x.first, 0);
dp[i][1] += dp[x.first][0];
}
else if(l == 1 && x.second == 1) {
dfs(x.first, 1);
dp[i][1] += dp[x.first][1];
}
else if(l == 0 && x.second == 0) {
dfs(x.first, 1);
dp[i][0] += dp[x.first][1];
}
else {
dfs(x.first, 0);
dp[i][0] += dp[x.first][0];
}
}
}
signed main() {
DDLC_ESCAPE_PLAN_FAILED;
int t;
cin >> t;
while(t--) {
cin >> n >> m;
flag = 0;
fors(i, 1, n) {
dp[i][0] = 0, dp[i][1] = 1;
fa[i] = i;
v[i] = 0;
st[i] = 0;
}
int l, r; string s;
while(m--) {
cin >> l >> r >> s;
if(s[0] == 'i') {
e[l].pb({r, 0});
e[r].pb({l, 0});
}
else {
e[l].pb({r, 1});
e[r].pb({l, 1});
}
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
if(!st[i]) {
tmp.clear();
dfs(i, 0);
for(auto &x : tmp) st[x] = 0;
dfs(i, 1);
ans += max(dp[i][0], dp[i][1]);
if(flag) break;
}
}
if(flag) cout << -1 << endl;
else cout << ans << endl;
fors(i, 1, n) e[i].clear();
}
return 0;
}
|
E1. Rubik’s Cube Coloring (easy version)
这种E1还是放Div. 3去吧，能当A做了，我不好说。
属于是送经验了（
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
| #include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
#define pii pair<int, int>
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
using namespace std;
const int mod = 1e9 + 7;
int fpow(int x, int y) {
int ans = 1;
while(y) {
if(y & 1) {
ans = (ans * x) % mod;
}
x = (x * x) % mod;
y >>= 1;
}
return ans;
}
signed main() {
DDLC_ESCAPE_PLAN_FAILED;
int t;
t = 1;
while(t--) {
int k;
cin >> k;
int p = (1LL << k) - 1LL;
cout << (fpow(4, p - 1LL) * 6LL) % mod << endl;
}
return 0;
}
|
