MaxDYF的随笔Blog

May all the beauty be blessed.

发表于 更新于 分类于

A - Square

直接记录最左最右、最上最下即可。

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. Square
// Contest: Codeforces - Codeforces Round 920 (Div. 3)
// URL: https://codeforces.com/contest/1921/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Author: MaxDYF
// 
// 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()
{
	ll x, y;
	ll now1 = llinf, now2 = llinf, len1, len2;
	for (int i = 1; i <= 4; i++)
	{
		cin >> x >> y;
		if (now1 == llinf)
			now1 = x;
		else if (now1 != x)
			len1 = abs(now1 - x);
		if (now2 == llinf)
			now2 = y;
		else if (now2 != y)
			len2 = abs(now2 - y);	
	}
	cout << len1 * len2 <<endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B - Arranging Cats

先算需要转换多少个0/1使得1的数量相等，转化完剩下的不同数对个数除以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
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
// Problem: B. Arranging Cats
// Contest: Codeforces - Codeforces Round 920 (Div. 3)
// URL: https://codeforces.com/contest/1921/problem/B
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// Author: MaxDYF
// 
// 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;
int a[N], b[N];
void work()
{
	cin >> n;
	char ch;
	int cnt1 = 0, cnt2 = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> ch;
		a[i] = ch - '0';
		cnt1 += a[i];
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> ch;
		b[i] = ch - '0';
		cnt2 += b[i];
	}
	int dif1 = 0, dif2 = 0;
	for (int i = 1; i <= n; i++)
	{
		if (a[i] == 0 && b[i] == 1)
			dif1++;
		else if (a[i] == 1 && b[i] == 0)
			dif2++;
	}
	if (cnt1 < cnt2)
		dif1 = max(0, dif1 - (cnt2 - cnt1));
	else
		dif2 = max(0, dif2 - (cnt1 - cnt2));
	cout << (dif1 + dif2) / 2 + (abs(cnt1 - cnt2)) << endl;
	
			
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

C - Sending Messages

简单dp。

设dp[i]表示发出第i条信息后的最小耗电量。容易发现，转移到下一个状态，只有两个状态：

  1. 发完上一条马上关机，下一次再开机；
  2. 发完上一条不关机。
阅读全文 »

发表于 更新于 分类于

A - Satisfying Constraints

每次动态更新上下界，最后二分判断一下界内的被删除数字即可。

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
//#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;
	ll l = 0, r = 1e10, x;
	vector<int> vec;
	for (int i = 1, op; i <= n; i++)
	{
		cin >> op >> x;
		switch (op)
		{
			case 1:
			{
				l = max(x, l);
				break;
			}
			case 2:
			{
				r = min(x, r);
				break;
			}
			case 3:
			{
				vec.push_back(x);
				break;
			}
		}
	}
	if (l > r)
	{
		cout << 0 << endl;
		return;
	}
	sort(vec.begin(), vec.end());
	unique(vec.begin(), vec.end());
	auto it1 = lower_bound(vec.begin(), vec.end(), l);
	auto it2 = --upper_bound(vec.begin(), vec.end(), r);
	if (it2 - it1 < 0 || (*it1) < l || (*it2) > r)
	{
		cout << r - l + 1 << endl;
	}
	else
	{
		cout << r - l + 1ll - (ll)(it2 - it1 + 1) << endl;
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B - Summation Game

对后手而言，显然把最大的\(x\)个数取反了是最优的。所以作为先手，我们枚举去掉最大的\(1\dots 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
//#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;

ll a[N];
void work()
{
	int n, k, x;
	cin >> n >> k >> x;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	sort(a + 1, a + n + 1);
	ll val = -1e10;
	for (int i = 2; i <= n; i++)
		a[i] += a[i - 1];
	if (n == k)
		val = 0;
	for (int i = 0; i <= k; i++)
	{
		if (n - i < 0)
			break;
		val = max(val, 2ll * a[max(0, n - i - x)] - a[n - i]);
	}
	cout << val << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

C - Partitioning the Array

题意可知，对于每个整除n的\(k\)，每一个下标组 \[ \begin{gather} \{1,1+k,1+2k\dots 1+(\frac n k -1)k\}, \\\\ \{2,2+k,2+2k\dots 2+(\frac n k -1)k\}, \\\\ \dots \\\\ \{k,2k\dots n\} \end{gather} \] 组内的元素对某个数\(m\)同余。

观察题目可以发现，我们实际上并不关心\(m\)是多少，只需知道存不存在这样的\(m\)。

对于这样一个式子: \[ \begin{align} a \equiv b\pmod M \\\\ b \equiv c\pmod M \\\\ \end{align} \] 移项得： \[ \begin{align} a-b \equiv 0\pmod M \\\\ b-c \equiv 0\pmod M \\\\ \end{align} \] 等效于： \[ gcd(a -b,b-c) \not= 1 \]

阅读全文 »

发表于 更新于 分类于

A题

A - Least Product

没有0的情况下，更改数字不改变正负性。若是正数，就将其归零；若是负数，则不做处理。注意特判原数有0的情况。

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
//#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;
	ll maxn = 0;
	bool rev = 0, suc = 0;
	for (int i = 1, x; i <= n; i++)
	{
		cin >> x;
		if (x < 0)
			rev = !rev;
		else if (x == 0)
		{
			suc = 1;
		}
	}
	if (suc == 1)
	{
		cout << 0 << endl;
		return;
	}
	if (rev)
	{
		cout << 0 << endl;
	}
	else
	{
		cout << "1\n1 0\n";
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B - Erase First or Second Letter

注意到只删第1、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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//#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;
	string s;
	cin >> s;
	s = ' ' + s;
	ll sum = 0, lst = 0;
	vector<int> but(26);
	for (int i = 1; i <= n; i++)
	{
		if (!but[s[i] - 'a'])
			lst++;
		sum += lst;
		but[s[i] - 'a']++;
	}
	cout << sum << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

C - Watering an Array

显然，对于纯0数列，由于只加前缀，只会创造出一个递减的序列，意味着无论加多少次，答案贡献最多为1。所以，最优操作是每加一次立即清零计算贡献。总贡献即\(\lfloor\frac{总轮数}{2}\rfloor\)。

对于不为0的部分，显然，加的次数不可能超过\(2\times n\)次，直接模拟即可，复杂度\(\Theta(n^2)\)。

阅读全文 »

发表于 更新于 分类于

秩相关

$$ \[\begin{gather} R(AB) \leq min\{R(A), R(B)\} \\ \\ R(A + B) \leq R(A)+R(B) \\ \\ R(A,B) \leq R(A) + R(B) \\ \\ R(A)+R(B)\leq n (AB=O)\\ \\ R(A^*)= \left\{ \begin{array}{l} n, && {R(A) = n} \\ 1, && {R(A) = n - 1} & \\ 0, && {R(A) < n - 1} & \\ \end{array} \right. \\ \\ R(A^TA) = R(AA^T) = R(A) \end{gather}\] $$

合同/相似/等价 关系(实对称矩阵下)

关系图

\[ \begin{gather} \{相似矩阵\}\subset \{等价矩阵\} \\ \{合同矩阵\}\subset \{等价矩阵\} \\ \{合同矩阵\}\cap \{相似矩阵\} \not= \emptyset \end{gather} \]

等价矩阵

  1. 秩相等

合同矩阵

  1. 等价矩阵的性质
  2. 一定对称
  3. 正负惯性系数（即正负定）相等
  4. 特征值不一定相等

相似矩阵

阅读全文 »

发表于 更新于 分类于

题意

给出一个 01 序列，一次操作可以选择连续的三个数，把它们都变成三个数的异或和。

问能否在 \(n\) 次以内全变成 0，输出方案。

思路

显然，把三个数都变为异或和不改变异或和，则若所有数异或和为0，无解。

若\(n\)为奇数，则可以依次操作\(n-2, n-4,n-6,...1\)，则操作后有\(a_1=0, a_{2k}=a_{2k+1}\)，则再依次对\(1,3,5,...n-2\)操作，可使所有数变为0。

若n为偶数，则可将数列拆成两段长度为奇数、异或和为0的子数列，分别操作。若没有为0的奇子数列，则无解。

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
// Problem: Xor of 3
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1572B
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// Auther : MaxDYF
// 
// 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);
typedef pair<int, int> pii;
typedef long long ll;
int n, m, k, q;
void work()
{
	cin >> n;
	vector<int> a(n), sum(n), ans;
	for (int i = 0; i < n; i++)
		cin >> a[i], sum[i] = sum[i - 1 < 0 ? 0 : i - 1] ^ a[i];
	if (sum[n - 1])
	{
		cout << "NO\n";
		return;
	}
	if (n & 1)
	{
		for (int i = n - 2; i >= 1; i -= 2)
			ans.emplace_back(i);
		for (int i = 1; i < n; i += 2)
			ans.emplace_back(i);
	} 
	else
	{
		int stop = -1;
		for (int i = 0; i < n; i += 2)
			if (!sum[i])
			{
				stop = i;
				break;
			}
		if (stop == -1)
		{
			cout << "NO\n";
			return;
		}
		stop++;
		for (int i = stop - 2; i >= 1; i -= 2)
			ans.emplace_back(i);
		for (int i = 1; i < stop; i += 2)
			ans.emplace_back(i);
		stop++;
		for (int i = n - 2; i >= stop; i -= 2)
			ans.emplace_back(i);
		for (int i = stop; i < n; i += 2)
			ans.emplace_back(i);
	}
	cout << "YES\n" << ans.size() << endl;
	for (auto x : ans)
		cout << x << ' ';
	cout << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}
0%