Codeforces Round 981 (Div. 3) A-D

昨晚太唐了, 错了一万遍

有一件事需要注意, 我们尽量用 map 而不是 unordered_map, map 查询的时间是稳定O(logn), 但是unordered_map 查询的时间是不稳定的, 可能很快, 也可能很慢, 最慢情况是 O(n)

A

原题

A. Sakurako and Kosuke

思路

容易发现随着n增大, 绝对值增大, 获胜的人交替, 因此就是求奇数偶数

代码

#include <bits/stdc++.h>
#define int long long

#define F(i, a, b) for (int i = (a); i <= (b); i++)
#define dF(i, a, b) for (int i = (a); i >= (b); i--)

using namespace std;

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

const int N = 500005, M = (N << 1), inf = 1e16, mod = 1e9 + 7;

int n, m, k, x, y, z, ans, t;
int w[N], f[N];

void solve()
{
	
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	cin >> T;
	while (T -- )
	{
		solve();
	}
}

B

原题

B. Sakurako and Water

思路

这道题统计每条正对角线的最小负数之和即可

代码

#include <bits/stdc++.h>
#define int long long

#define F(i, a, b) for (int i = (a); i <= (b); i++)
#define dF(i, a, b) for (int i = (a); i >= (b); i--)

using namespace std;

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

const int N = 500005, M = (N << 1), inf = 1e16, mod = 1e9 + 7;

int n, m, k, x, y, z, ans, t;
int w[N], f[N];

int a[510][510];



void solve()
{
	cin >> n;
	
	for (int i = 1 - n + 510; i <= n - 1 + 510; i ++ ) f[i] = 0;
	
	for (int i = 1; i <= n; i ++ )
	{
		for (int j = 1; j <= n; j ++ )
		{
			cin >> a[i][j];
			f[i - j + 510] = min(f[i - j + 510], a[i][j]);
		}
	}
	
	int ans = 0;
	for (int i = 1 - n + 510; i <= n - 1 + 510; i ++ )
	{
		if (f[i] < 0) ans -= f[i];
	}
	
	cout << ans << endl;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	cin >> T;
	while (T -- )
	{
		solve();
	}
}

C

原题

C. Sakurako's Field Trip

思路

从中间往两侧最优化考虑即可, 从两侧往中间最优化考虑也可

代码

#include <bits/stdc++.h>
#define int long long

#define F(i, a, b) for (int i = (a); i <= (b); i++)
#define dF(i, a, b) for (int i = (a); i >= (b); i--)

using namespace std;

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

const int N = 500005, M = (N << 1), inf = 1e16, mod = 1e9 + 7;

int n, m, k, x, y, z, ans, t;
int a[N], f[N];

void swap(int i)
{
	int temp = a[i];
	a[i] = a[n - i + 1];
	a[n - i + 1] = temp;
}

bool check(int i)
{
	int aa = 0, b = 0;
	int x = n - i + 1;
	if (a[i] == a[i + 1])
	{
		aa ++;
	}
	if (a[x] == a[x - 1])
	{
		aa ++;
	}
	
	
	if (a[x] == a[i + 1])
	{
		b ++;
	}
	if (a[i] == a[x - 1])
	{
		b ++;
	}
	
	return aa >= b;
}

void solve()
{
	cin >> n;
	
	for (int i = 1; i <= n; i ++ ) cin >> a[i];
	
	for (int i = n / 2; i >= 1; i --)
	{
		if (check(i))
		{
			swap(i);
		}
	}
	
	int ans = 0;
	
	for (int i = 1; i < n; i ++ )
	{
		
		if (a[i] == a[i + 1])
		{
			ans ++;
		}
	}
	
	cout << ans << endl;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	cin >> T;
	while (T -- )
	{
		solve();
	}
}

D

原题

D. Kousuke's Assignment

思路

创建前缀和数组, 遍历, 如果当前的前缀和在前面出现, 那么答案加1, 同时记录这一位置, 不可以再用此位置前的前缀和判断

用 map 很容易实现这个功能, 但是unordered_map会被卡时间

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n;

void solve()
{
	cin >> n;
	
	vector<int> a(n + 5), pre(n + 5);
	
	for (int i = 1; i <= n; i ++ )
	{
		cin >> a[i];
		pre[i] = pre[i - 1] + a[i];
	}
	
	map<long long, int> m;
	int r = 0;
	m[0] = 0;
	int ans = 0;
	for (int i = 1; i <= n; i ++ )
	{
		if (a[i] == 0 || (m.count(pre[i]) && m[pre[i]] >= r))
		{
			ans ++;
			r = i;
		}
		m[pre[i]] = i;
	}
	cout << ans << endl;
}

int main()
{
	int T;
	cin >> T;
	while (T -- )
	{
		solve();
	}
}