都是傻逼题

#1167

D

直接贪心。如果要填左括号,就看当前剩下没配对的左括号哪种颜色少;右括号同理

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
   for (int i = 1; i <= N; ++i)
{
if (S[i] == '(')
{
if (sum0 < sum1) Ans[i] = 0, ++sum0;
else Ans[i] = 1, ++sum1;
}
else
{
if (sum0 > sum1) Ans[i] = 0, --sum0;
else Ans[i] = 1, --sum1;
}
}

E

固定左端点,假设可行的右端点的范围为[p,m][p, m],显然从大到小枚举左端点后,pp是单调不升的

记录每种数字位置的最大/最小值,前缀最大值,two pointers扫一下即可

two pointers的细节需要注意,务必想清楚再动键盘

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Max[i] 所有为i的数的最右位置
// Min[i] 所有为i的数的最左位置
// sum_max[] Max的前缀最大值
int MIN = 1e7, r = M;
for (int l = p; l >= 1; --l)
{
while (r >= l && Max[r + 1] <= MIN && Min[r + 1] >= sum_max[l - 1])
{
Chkmin (MIN, Min[r + 1]);
--r;
}

ans += (M - r);
}

F

考虑贡献,计算每个数对答案的贡献,即对于每个数考虑所有包含它的区间中小于它的数的个数

显然,对于一个位置,因为往左右分别延伸的区间互不影响,所以可以拆成左边和右边分别计算答案

再拆一次贡献,对于每个小于它的数分别算对它的贡献,搞一左一右两棵树状数组统计答案

Code
1
2
3
4
5
6
7
8
9
10
for (int i = 1; i <= N; ++i) T[1].add (A[i], N - i + 1);
int ans = 0;
for (int i = 1; i <= N; ++i)
{
int sum0 = (LL) T[0].query (A[i]) * (N - i + 1) % Mod;
int sum1 = (LL) T[1].query (A[i]) * i % Mod;
Add (ans, (LL) (sum0 + sum1) % Mod * Hash[A[i]] % Mod);
T[0].add (A[i], i);
T[1].add (A[i], Mod - (N - i + 1));
}

#1166

C

枚举xx,计算可能的yy的范围

根据条件xyx,yx+y|x - y| \le |x|, |y| \le |x + y|(实际上这里还需要讨论符号)

分类讨论一下可以得到合法的yy的区间

  • x0x\le 0时:y[2x,x2][x2,2x]y\in [2x, \frac{x}{2}]\cup [-\frac{x}{2}, -2x]
  • x>0x > 0时:y[x2,2x][2x,x2]y\in [\frac{x}{2}, 2x]\cup [-2x,-\frac{x}{2}]

注意减掉x=yx=y的情况

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
sort (A + 1, A + N + 1);
LL ans = 0;
for (int i = 1; i <= N; ++i)
{
int x = A[i], l, r;
if (x <= 0)
{
l = lower_bound (A + 1, A + N + 1, 2 * x) - A;
r = upper_bound (A + 1, A + N + 1, x / 2.0) - A - 1;
ans += r - l + 1;
l = lower_bound (A + 1, A + N + 1, - x / 2.0) - A;
r = upper_bound (A + 1, A + N + 1, - 2 * x) - A - 1;
ans += r - l + 1;
}
else
{
l = lower_bound (A + 1, A + N + 1, x / 2.0) - A;
r = upper_bound (A + 1, A + N + 1, x * 2) - A - 1;
ans += r - l + 1;
l = lower_bound (A + 1, A + N + 1, - x * 2) - A;
r = upper_bound (A + 1, A + N + 1, - x / 2.0) - A - 1;
ans += r - l + 1;
}
--ans;
}
cout << ans / 2 << endl;

D

贪心构造,先构造一个初始局面,再不断调整这个局面

考虑先构造一个形如 的局面,因为log(1014)<50\log(10^{14}) < 50,所以长度肯定不会超过限制

这样构造出来后,Δ=bsumk1\Delta = b - sum_{k-1}有可能>m> m,于是需要调整,把前面多凑一点

从小到大考虑每个位置ii,假设给它加上xx,那么i+1i+1就需要加上xxi+2i+2加上2x2xi+3i+3加上4x4x,以此类推

可以发现这样做了之后,sumk1sum_{k-1}会加上2nix2^{n-i}x

又因为2nixΔ2^{n-i}x\le \Delta,且xm1x\le m - 1

所以贪心地考虑,x=min{Δ2ni,m1}x = \min\{\lfloor\frac{\Delta}{2^{n-i}}\rfloor, m - 1\}

最后看剩下的Δ\Delta是否m\ge m即可

还有一些小细节,比较恶心

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
if (a == b)
{
cout << 1 << ' ' << a << endl;
return ;
}

memset(A, 0, sizeof A); N = 0;
A[++N] = a;
LL sum = a;
while (1)
{
if (sum <= b && b <= sum * 2 + 1) { A[++N] = b; break; }
A[++N] = sum + 1;
sum = sum * 2 + 1;
}

LL delta = A[N] - sum - 1;
for (int i = 2; i < N; ++i)
{
LL now = min (M - 1, (LL) (delta / pow(2ll, N - i - 1)));
delta -= Calc (now, i);

LL res = now;
A[i] += now;
for (int j = i + 1; j < N; ++j)
{
A[j] += res;
res += res;
}
}
if (delta >= M) puts("-1");
else
{
cout << N << ' ' ;
for (int i = 1; i <= N; ++i) cout << A[i] << ' '; puts("");
}

E

Ai,BiA_i, B_i表示第ii天的两个集合,其中AiA_i是题目给出的那个

不难发现存在合法方案的必要条件是所有AA集合之间两两有交

如果存在i,ji, j使得AiAj=A_i \cap A_j = \emptyset,则lcm{Bj}lcm{Ai}>lcm{Bi}>lcm{Aj}\mathrm{lcm}\{B_j\} \ge \mathrm{lcm}\{A_i\} > \mathrm{lcm}\{B_i\} > \mathrm{lcm}\{A_j\},矛盾

然后考虑它的充分性,即只利用这个限制去构造合法解

考虑如下构造:选取mm个互不相同的质数 ,对于第ii天的集合AiA_i,把其中所有商店的权值乘上pip_i

显然,因为AiA_i两两有交,所以i,lcm{Ai}=j=1mpj\displaystyle \forall i, \mathrm{lcm}\{A_i\} = \prod_{j=1}^{m} p_j

那么lcm{Bi}j=1mpjpi<lcm{Ai}\displaystyle \mathrm{lcm}\{B_i\} \le \frac{\prod_{j=1}^{m}p_j}{p_i} < \mathrm{lcm}\{A_i\}

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (int i = 1; i <= M; ++i)
{
int k = read<int>();
while (k--) A[i][read<int>()] = 1;
for (int j = 1; j < i; ++j)
{
if (!(A[i] & A[j]).any())
{
puts("impossible");
return ;
}
}
}
puts("possible");

F

Description

给你一张nn个点mm条边的无向图,每条边有一个[1,c]\in[1, c]的颜色,另外有qq次操作:

  • + x y z 连一条xxyy,颜色为zz的边

  • ? x y询问从xxyy是否存在一条这样的路径:从经过的第一条边开始,每经过的两条边颜色相同

    比如,有一条经过了55条边的路径,那么就需要满足第 条边颜色相同, 条边颜色相同,而第55条边颜色任意

n,m,c,q105n,m, c, q\le 10^5

Solution

一个暴力的想法是,建一个新图,如果(u,w)(u, w)(w,v)(w, v)颜色相同,则在新图中连(u,v)(u, v),但是最后一条边不需要走颜色相同的边,不太好处理

考虑用并查集来维护连通性,且每个连通块用一个set来维护这个连通块能到达的点的集合,显然set可以启发式合并

这里能到达点的集合并不就是这个连通块

因为每个点还能再多往后走一步,即还要加上这些点在原图中的邻居

最后还需要考虑一个经典的问题,因为新图中的边可能很多,所以我们不能把它们直接建出来。于是可以对于每个点,每种颜色只保留一条边。如果再加一条这种颜色的边的话,直接把它与之前保留边的信息合并即可

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e5 + 100;

int N, M, C, Q;
set <int> S[Maxn];
map <pii, int> Map;

namespace DSU
{
int fa[Maxn];

inline void init (int maxn) { for (int i = 1; i <= maxn; ++i) fa[i] = i, S[i].insert (i); }
inline int get_fa (int x) { return x == fa[x] ? x : fa[x] = get_fa (fa[x]); }
inline void link (int x, int y)
{
x = get_fa (x), y = get_fa (y);
if (x == y) return ;
if (S[x].size() > S[y].size()) swap (x, y);
fa[x] = y;
S[y].insert (S[x].begin(), S[x].end());
S[x].clear ();
}
inline int query (int x, int y)
{
x = get_fa (x);
if (*S[x].lower_bound (y) != y) return 0;
return 1;
}
}

inline void add_edge (int x, int y, int z)
{
if (Map[mp (x, z)]) DSU :: link (Map[mp (x, z)], y);
else Map[mp (x, z)] = y;
S[DSU :: get_fa (y)].insert (x);
}

inline void Solve ()
{
DSU :: init (N);
for (int i = 1; i <= M; ++i)
{
int x = read<int>(), y = read<int>(), z = read<int>();
add_edge (x, y, z), add_edge (y, x, z);
}

while (Q--)
{
char S[10]; scanf("%s", S);
if (S[0] == '?')
{
int x = read<int>(), y = read<int>();
printf("%s\n", DSU :: query (x, y) ? "Yes" : "No");
}
else
{
int x = read<int>(), y = read<int>(), z = read<int>();
add_edge (x, y, z);
add_edge (y, x, z);
}
}
}

inline void Input ()
{
N = read<int>(), M = read<int>(), C = read<int>(), Q = read<int>();
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("F.in", "r", stdin);
freopen("F.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}