都是傻逼题

#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的范围

根据条件∣x−y∣≤∣x∣,∣y∣≤∣x+y∣|x - y| \le |x|, |y| \le |x + y|（实际上这里还需要讨论符号）

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

  • x≤0x\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，所以长度肯定不会超过限制

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

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

可以发现这样做了之后，sumk−1sum_{k-1}会加上2n−ix2^{n-i}x

又因为2n−ix≤Δ2^{n-i}x\le \Delta，且x≤m−1x\le m - 1

所以贪心地考虑，x=min{⌊Δ2n−i⌋,m−1}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使得Ai∩Aj=∅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 连一条xx到yy，颜色为zz的边

  • ? x y询问从xx到yy是否存在一条这样的路径：从经过的第一条边开始，每经过的两条边颜色相同

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

n,m,c,q≤105n,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;
}

```