Codeforces Round #657 (Div. 2)
/ / 阅读耗时 11 分钟 Codeforces Round #657 (Div. 2)。E题待补。
A. Acacius and String
$div2$上来1500评分的题？
由于$n$很小，暴力枚举哪里匹配，然后判别的地方不要匹配即可。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
using namespace std;
const int N = 10000 + 5;
typedef long long ll;
int n;
char op[N], tmp[N];
const char* P = "abacaba";
inline int check3(int l, int r)
{
for (int i = l, z = 0; i <= r; i++, z++) {
if (tmp[i] != P[z]) return 0;
}
return 1;
}
inline int check(int x)
{
for (int i = 7; i <= n; i++) {
if (i != x && check3(i - 6, i)) return 0;
}
// cout << 1 << endl;
return 1;
}
inline int check2(int l, int r)
{
for (int i = l, j = 0; i <= r; i++, j++) {
if (op[i] != P[j] && op[i] != '?') return 0;
}
return 1;
}
int main()
{
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%s", &n, op + 1);
for (int i = 7; i <= n; i++) {
if (check2(i - 6, i)) {
for (int j = 1; j <= n; j++) tmp[j] = op[j];
for (int j = i - 6, z = 0; j <= i; j++, z++) tmp[j] = P[z];
if (check(i)) {
for (int j = 1; j <= n; j++) tmp[j] = tmp[j] == '?' ? 'z' : tmp[j];
printf("Yes\n");
for (int j = 1; j <= n; j++) printf("%c", tmp[j]);
printf("\n");
goto to;
}
}
}
printf("No\n");
to:;
}
return 0;
}
B. Dubious Cyrpto
移项，得到：
然后暴力枚举$a$，判$n$的存在性。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
using namespace std;
const int N = 10000 + 5;
typedef long long ll;
int main()
{
int T;
scanf("%d", &T);
while (T--) {
long long l, r, m, a, b, c, cha;
scanf("%lld%lld%lld", &l, &r, &m);
for (long long i = l; i <= r; i++) {
long long up = (m + r - l) / i;
long long down = (m + l - r) % i == 0 ? (m + l - r) / i : (m + l - r) / i + 1;
down = max(down, 1ll);
if (up >= down) {
a = i, cha = up * a - m;
break;
}
}
if (cha < 0) {
b = r, c = r + cha;
} else {
b = l, c = l + cha;
}
printf("%lld %lld %lld\n", a, b, c);
}
return 0;
}
C. Choosing flowers
经过证明（或者根据合理的猜想），最多只有一种花会买一支以上。
枚举那一个种类的花会买一支以上（设为$s$），然后别的花买一支，只买一支的花的$a_i$必然需要大于$b_s$才会使答案更优。于是我们根据$a_i$排序，然后二分出可行的区间，更新答案。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
using namespace std;
const int N = 100000 + 5;
typedef long long ll;
int n, m;
struct Node
{
int a, b;
bool operator<(Node s)
{
return a < s.a;
}
} nd[N];
long long sum[N];
int main()
{
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) scanf("%d%d", &nd[i].a, &nd[i].b);
sort(nd + 1, nd + m + 1);
sum[m] = nd[m].a, sum[m + 1] = 0;
for (int i = m - 1; i >= 1; i--) sum[i] = sum[i + 1] + nd[i].a;
long long ans = 0;
for (int i = 1; i <= m; i++) {
int l = 0, r = m, mid;
while (l < r) {
if (r == l + 1) break;
mid = (l + r) >> 1;
if (nd[mid].a >= nd[i].b)
r = mid;
else
l = mid;
}
ans = max(ans, nd[i].a + 1ll * (n - 1) * nd[i].b);
if (n <= m - r + 1) {
ans = max(ans, sum[m - n + 1]);
} else {
long long tmp = 0, num = n;
tmp += sum[r], num -= m - r + 1;
// cout << "x" << tmp << " " << num << " " << m - r + 1 << " " << i << endl;
if (r > i)
tmp += nd[i].a + 1ll * (num - 1) * nd[i].b;
else
tmp += 1ll * num * nd[i].b;
ans = max(ans, tmp);
}
}
printf("%lld\n", ans);
}
return 0;
}
D. New Passenger Trams
容易发现，一个货运列车与电车是否冲突（$t=0$），只与它的出现时间对$\frac {m}{2}$的模有关。具体来说，如果这个模在区间$[0,\frac{m}{2}-k]$中，则是可行的。
改变$t$会导致所有货运列车的模数同时增加或减少一个固定的值。我们为了最大化位于$[0,\frac{m}{2}-k]$中的值，可以$O(n)$地（尺取法）枚举左端点，得到右端点，然后更新答案。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
using namespace std;
const int N = 100000 + 5;
typedef long long ll;
ll n, h, m, k, hh[N], mm[N];
vector<pair<ll, int>> vec;
int main()
{
scanf("%lld%lld%lld%lld", &n, &h, &m, &k);
for (int i = 1; i <= n; i++) {
scanf("%lld%lld", hh + i, mm + i);
mm[i] = mm[i] % (m / 2);
vec.push_back({mm[i], i});
}
sort(vec.begin(), vec.end());
int len = vec.size();
for (int i = 0; i < len; i++) vec.push_back({vec[i].first + m / 2, vec[i].second});
int ans = 0, r = 0, who = 0, at;
for (int i = 0; i < len; i++) {
while (r + 1 < vec.size() && vec[r + 1].first - vec[i].first < m / 2 - k + 1) ++r;
if (r - i + 1 > ans) {
ans = r - i + 1;
who = vec[i].first;
at = i;
}
}
printf("%lld %d\n", n - ans, who);
for (int i = at; i < at + n; i++) {
if (vec[i].first - vec[at].first >= m / 2 - k + 1) printf("%d ", vec[i].second);
}
return 0;
}
F. Chess Strikes Back
我们将棋盘划分为若干个$2\times 2$的块，每一个块的左上角和右下角都是白块。这样每一个块里有且仅有一个$king$。每一个块用其左上角坐标表示。
有一个结论：当一个块$(x_1,y_1)$的左上角被堵上，另一个块（可以相同）$(x_2,y_2)$的右下角被堵上，且$x_1\leq x_2,y_1\leq y_2$时，答案为$NO$，否则为$YES$。
这样我们建立线段树维护这两种块的坐标，进而在$O(nlogn)$复杂度下求解。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
using namespace std;
const int N = 400000 + 5;
typedef long long ll;
int n, m, tr[N << 2][3], q;
set<int> ssp[N][2];
void modify(int x, int who, int v, int l = 1, int r = n, int k = 1)
{
if (l == r) {
if (ssp[l][who].count(v))
ssp[l][who].erase(v);
else
ssp[l][who].insert(v);
tr[k][0] = ssp[l][0].empty() ? 0x3f3f3f3f : *ssp[l][0].begin();
tr[k][1] = ssp[l][1].empty() ? 0 : *ssp[l][1].rbegin();
tr[k][2] = tr[k][1] >= tr[k][0];
return;
}
int mid = (l + r) >> 1;
if (x <= mid)
modify(x, who, v, l, mid, k << 1);
else
modify(x, who, v, mid + 1, r, k << 1 | 1);
tr[k][1] = max(tr[k << 1][1], tr[k << 1 | 1][1]);
tr[k][0] = min(tr[k << 1][0], tr[k << 1 | 1][0]);
tr[k][2] = (tr[k << 1 | 1][1] >= tr[k << 1][0]) | tr[k << 1][2] | tr[k << 1 | 1][2];
}
void build(int l = 1, int r = n, int k = 1)
{
tr[k][0] = 0x3f3f3f3f, tr[k][1] = tr[k][2] = 0;
if (l == r) return;
int mid = (l + r) >> 1;
build(l, mid, k << 1), build(mid + 1, r, k << 1 | 1);
}
int main()
{
scanf("%d%d%d", &n, &m, &q);
n <<= 1, m <<= 1, build();
while (q--) {
int x, y;
scanf("%d%d", &x, &y);
if (x & 1) {
modify(x, 0, y);
} else {
--x, --y;
modify(x, 1, y);
}
printf("%s\n", !tr[1][2] ? "YES" : "NO");
}
return 0;
}