因为忘了开long long错失上分机会QWQ
A. Direction Change
可以向上下左右走，每连续的两个走路的步骤不能相同，给出n*m的二维矩阵，从(1,1)到(n,m)是否可以满足条件又能到达。
思路：分情况讨论，若是1*1，输出0；若是对于n*n的二维矩阵，一定可以从(1,1)到达(n,m)且满足条件，剩下的m-n行可以通过下->左->下->右这样的顺序来走；剩下的情况则无法到达，即n==1||m==1且另一个数>2。
AC Code：
#include <bits/stdc++.h>
#pragma GCC optimize(2)
template <typename T>
inline void read(T &x) {
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0', ch = getchar();
}
x *= f;
}
template <typename T>
void write(T x) {
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
#define INF 0x3f3f3f3f
typedef long long ll;
const double PI = acos(-1);
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int N = 105;
ll t, n, m;
int main() {
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> t;
while (t--) {
std::cin >> n >> m;
if (n == 1 && m == 1)
std::cout << 0 << '\n';
else if (abs(n - m) <= 1) {
std::cout << n + m - 2 << '\n';
} else if (n == 1 || m == 1)
std::cout << -1 << '\n';
else {
ll a = std::max(n, m);
ll b = std::min(n, m);
std::cout << b * 2 - 2 + (a - b) / 2 * 4 + (a - b) % 2 << '\n';
}
}
return 0;
}B. Social Distance
每个人选择座位的时候要选择一个左右两侧都至少留有a[i]个座位的位置，所有的座位都是成环摆放的，给出座位数量，问每个人是否能落座。
思路： 按照每个人的要求座位数排序，这样挨着坐是耗费座位最少的方案，计算所有的要求和sum，最后最少的座位答案是sum-a[1]+a[n]+n（升序排列），判断这个结果和座位数的大小关系即可。
AC Code：
#include <bits/stdc++.h>
#pragma GCC optimize(2)
template <typename T>
inline void read(T &x) {
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0', ch = getchar();
}
x *= f;
}
template <typename T>
void write(T x) {
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
#define INF 0x3f3f3f3f
typedef long long ll;
const double PI = acos(-1);
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
ll t, n, m;
ll a[N];
int main() {
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> t;
while (t--) {
std::cin >> n >> m;
ll sum = 0;
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
sum += a[i];
}
if (n > m) {
std::cout << "NO" << '\n';
continue;
}
std::sort(a + 1, a + 1 + n);
if (sum - a[1] + a[n] + n <= m)
std::cout << "YES" << '\n';
else
std::cout << "NO" << '\n';
}
return 0;
}C. Make it Increasing
给出一个数组a，和一个全为0的数组b，每次操作可以选择一个i，使b[i]=b[i]+a[i]或者b[i]=b[i]-a[i]，问使得数组b成为严格递增序列最少需要多少次操作。
思路：对于一个构造的递增序列来说，一定有一个位置是0，因为对于一个递增序列来说，最接近0的那个数如果为0更优，因为给出的数据范围是5000，可以O(n^2)解决，那就枚举为0的位置，取结果的最小值即可。
AC Code：
#include <bits/stdc++.h>
#pragma GCC optimize(2)
template <typename T>
inline void read(T &x) {
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0', ch = getchar();
}
x *= f;
}
template <typename T>
void write(T x) {
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
#define INF 0x3f3f3f3f
typedef long long ll;
const double PI = acos(-1);
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
ll tt, n, m, cnt;
ll a[N];
int main() {
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> n;
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
std::vector<ll>vec;
for (int i = 1; i <= n; i++) {
ll max = 0, min = 0, cnt = 0;
for (int j = i - 1; j >= 1; j--) {
if (a[j] > 0)
a[j] = -a[j];
tt = max / a[j] + 1;
cnt += tt;
max = a[j] * tt;
}
for (int j = i + 1; j <= n; j++) {
if (a[j] < 0)
a[j] = -a[j];
tt = min / a[j] + 1;
cnt += tt;
min = a[j] * tt;
}
vec.push_back(cnt);
}
std::sort(vec.begin(), vec.end());
std::cout << vec[0] << '\n';
return 0;
}os：赛时vector里没开long long，然后寄了（血压++）
?D好像要用线段树维护，线段树。。。滚了滚了
若有错误请指教，谢谢！
orzorz
