昨晚太唐了, 错了一万遍
有一件事需要注意, 我们尽量用 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();
}
}