MaxDYF的随笔Blog

May all the beauty be blessed.

发表于 分类于

题目思路

可以发现，非简单路径意味着可以走环，那么若是有两个相邻的点都是左括号或右括号，那么就可以反复走这两个点来刷左括号或右括号。同时，合法括号序列的长度必然为偶数，也就是说两点有合法路径时，必然有一条经过点数为偶数的路径。不妨假设询问路径为从\(x\)到\(y\)，那么当

  1. \(x\)有与其相连的左括号（称其为\(LL\)点对）
  2. \(y\)也有与其相连的右括号（称其为\(RR\)点对）
  3. 且\(LL\)点对到\(RR\)点对有偶数长度的路径

时，必然存在合法路径。

上面得出的结论是充分非必要条件，我们考虑怎么将其扩充为充分必要条件。我们发现，如果\(x\)与某一\(LL\)点对有路径，且到他们的路径之间构成的括号序列合法时，实际上等同于\(x\)就是\(LL\)点对的情况。对\(y\)点也类似，所以下面只对\(x\)分析。由于只要存在这样的\(LL\)就可以，所以我们只需要对\(x\)找到离他最近的的\(LL\)点对。对于最近的\(LL\)点对，显然只会构成\(()()\ldots()\)这样的括号序列（否则就不是最近了）。

对于这种最简单的括号序列，我们可以对原图的部分边的基础上建立一个二分图，只对相邻的左括号和右括号之间进行连边，显然这个二分图只会存在这种最简单的括号路径。这样只要判断\(x\)点是否和某一\(LL\)点对在这个二分图的同一连通块里就可以了。

现在我们解决了上面的条件1、2，考虑怎么转换原来的条件3并加以解决。原来条件3等效于\(LL\)由于\(x\)到\(LL\)的路径一定是偶数，\(y\)到\(RR\)的路径也是偶数，且\(x\)与\(y\)在同一连通块里，那么只需判断\(x\)到\(y\)是否具有偶数长度的路径。这里可以运用一个小Trick：

我们考虑尝试对原图的边直接构建二分图。在\(x\)与\(y\)在同一连通块的前提下，如果原图就是二分图，那么\(x\)与\(y\)存在偶数路径，当且仅当\(x\)与\(y\)在二分图的同一边；如果原图不是二分图，那么原图必然存在奇环，也就是必然存在偶数路径。

最后考虑一种特殊情况：\(x\)与\(y\)之间只存在\(()()\ldots()\)这样的路径，只要判断一下在上面的部分二分图上\(x\)与\(y\)是否在不同的两边且在这个二分图的同一连通块即可。

下面证明这几种情况的完备性。

阅读全文 »

发表于 更新于 分类于

静电场

基础公式

电通量

\[ \Phi=\oint_S \vec{E}\mathrm{d}\vec S \] #### 电势

\[ u_p=\int \frac{\mathrm{d}q}{4\pi\epsilon_0r} \\ \\ u_p=\sum u_{p, i} \]

高斯定理（真空环境下）

\[ \Phi=\oint_S \vec{E}\mathrm{d}\vec S=\frac Q{\epsilon_0} \]

极化强度、电位移矢量

\[ \vec P=\epsilon_0 \chi \vec E \newline \vec D=\epsilon_0\vec E+\vec P \newline =\epsilon_0(1+\chi)\vec E \]

二级结论

阅读全文 »

发表于 更新于 分类于

题外话

鸽了好久，忙学校的一堆b课和b考试，打了CF也没写题解。打场div2复健一下。

完成情况

A B C D E
赛时 YES YES YES NO NO
补题 YES NO

A. Little Nikita

直觉法可得能凑成的充要条件是\((n>m) \land (n\equiv m \mod 2)\)。

B. Binary Colouring

考虑对于二进制下一段连续的1，设第一位为\(i\)位，最后一位为\(j\)位，给\(j+1\)设为1，再给\(i\)设为-1。

可以发现两个特殊情况会出现两个连续的非0，一是两段连续的1只有一个0隔开。设低位的连续段位\([i, p]\)，高位的为\([p+2, j]\)。我们要将\(p+1\)位置为1，\(p+2\)位置为-1，那么显然可以替换成将\(p+1\)位置为-1。

二是单独一个1的连续段。这种情况下直接将\(i\)置为1，然后考虑用上面类似的策略和低位的1进行等效替换即可。

阅读全文 »

发表于 更新于 分类于

喜提2 TON币，好耶

A. Farmer John's Challenge

对于\(n=k\)的情况，显然构造一个全为1的序列是合法的。

对于\(k=1\)的情况，显然构造1至n的序列合法。

对于这之外的情况，我们设想一个有序序列，如果其循环左移\(k(k \not=1且k \not= n)\)次后仍然合法，那么也就是说，原序列最小的数要等于最大的数，也就是所有数相等，显然k不可能为n以外的数。所以直接输出-1。

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
// Problem: A. Farmer John's Challenge
// Contest: Codeforces - CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!)
// URL: https://codeforces.com/contest/1942/problem/0
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;

void work()
{
	cin >> n >> k;
	if (n == k)
	{
		for (int i = 1; i <= n; i++)
			cout << 1 << ' ';
		cout << endl;
	}
	else if (k == 1)
	{
		for (int i = 1; i <= n; i++)
			cout << i << ' ';
		cout << endl;
	}
	else
	{
		cout << -1 << endl;
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B. Bessie and MEX

考虑倒推。对于第n位，有\(a_n\) = \(\texttt{MEX}(p_1, p_2, \ldots, p_n) - p_n\)。而\(\texttt{MEX}(p_1, p_2, \ldots, p_n)\)显然应该等于\(n\)，所以\(p_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
54
55
// Problem: B. Bessie and MEX
// Contest: Codeforces - CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!)
// URL: https://codeforces.com/contest/1942/problem/B
// Memory Limit: 256 MB
// Time Limit: 1500 ms
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
int a[N];
int p[N];
bool vis[N];
// p[n    ] = n - a[n]
// p[n - 1] = p[n] - a[n - 1]
void work()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	int lst = n;
	for (int i = n; i >= 1; i--)
	{
		p[i] = lst - a[i];
		lst = min(lst, p[i]);
	}
	for (int i = 1; i <= n; i++)
		cout << p[i] << ' ';
	cout << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

C. Bessie's Birthday Cake

阅读全文 »

发表于 更新于 分类于

A. Median of an Array

显然，有多少个和中位数相等的数就加多少次。

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
// Problem: A. Median of an Array
// Contest: Codeforces - Codeforces Round 936 (Div. 2)
// URL: https://codeforces.com/contest/1946/problem/0
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;

void work()
{
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	sort(a.begin(), a.end());
	int pos = (n - 1) / 2, cnt = 1;
	while (pos < n - 1 && a[pos] == a[pos + 1])
		pos++, cnt++;
	cout << cnt << endl;
	
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B. Maximum Sum

很显然，如果没有插入操作的话，答案显然就是最大子段和\(sum\)。

如果有插入操作的话，我们只需要把这个最大子段和的值插在最大子段的旁边，答案就变成了\(2\times sum\)。如是，我们重复k次，答案就变成了\((1+2+4+\ldots +2^k)\times sum=(2^{k+1}-1)\times sum\)。

因为k比较小，直接暴力算就好。最后答案还要加上整个数列的和。

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
// Problem: B. Maximum Sum
// Contest: Codeforces - Codeforces Round 936 (Div. 2)
// URL: https://codeforces.com/contest/1946/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
const ll mod = 1e9 + 7;
void work()
{
	cin >> n >> k;
	ll ans = 0;
	ll sum = 0, maxsum = 0, numsum = 0;
	vector<ll> a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		numsum += a[i];
		numsum %= mod;
	}
	for (int i = 0; i < n; i++)
	{
		sum += a[i];
		if (sum < 0)
			sum = 0;
		maxsum = max(maxsum, sum);
	}
	for (int i = 1; i <= k; i++)
	{
		ans += maxsum;
		ans %= mod;
		maxsum += maxsum;
		maxsum %= mod;
	}
	cout << (ans + numsum + 2LL * mod) % mod << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

C. Tree Cutting

看到最小连通块的最大值，很容易想到用二分解决。关键在于设计check(lim)。

阅读全文 »
0%