A - Range Product
经过0答案肯定是0，都是正数肯定是正数，都是负数的话就奇负偶正。
//waz
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
int F()
{
char ch;
int x, a;
while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
if (ch == '-') ch = getchar(), a = -1;
else a = 1;
x = ch - '0';
while (ch = getchar(), ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + ch - '0';
return a * x;
}
int a, b;
int main()
{
gii(a, b);
if (a <= 0 && b >= 0) puts("Zero");
else
{
if (a > 0) puts("Positive");
else
{
if ((b - a + 1) & 1) puts("Negative");
else puts("Positive");
}
}
}
B - Box and Ball
模拟，顺序模拟判断用一个bool数组存这个点红球可不可能在这里，直接扫过去就好了。
//waz
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
int F()
{
char ch;
int x, a;
while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
if (ch == '-') ch = getchar(), a = -1;
else a = 1;
x = ch - '0';
while (ch = getchar(), ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + ch - '0';
return a * x;
}
const int N = 1e5 + 10;
int n, m, x[N], y[N];
int cnt[N];
bool can[N];
int main()
{
gii(n, m);
for (int i = 1; i <= m; ++i)
gii(x[i], y[i]);
for (int i = 1; i <= n; ++i) cnt[i] = 1;
can[1] = 1;
for (int i = 1; i <= m; ++i)
{
if (can[x[i]])
{
if (cnt[x[i]] == 1)
can[x[i]] = 0;
can[y[i]] = 1;
}
--cnt[x[i]];
++cnt[y[i]];
}
int ans = 0;
for (int i = 1; i <= n; ++i)
if (can[i]) ++ans;
printf("%d
", ans);
return 0;
}
C - Knot Puzzle
找出最长的a[i]+a[i+1]，如果大于等于l，就从两头一直删到这里，否则无解。
//waz
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
int F()
{
char ch;
int x, a;
while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
if (ch == '-') ch = getchar(), a = -1;
else a = 1;
x = ch - '0';
while (ch = getchar(), ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + ch - '0';
return a * x;
}
int a[100010];
int n, l;
int main()
{
gii(n, l);
for (int i = 1; i <= n; ++i) gi(a[i]);
int j = 1;
for (int i = 2; i < n; ++i)
if (a[i] + a[i + 1] > a[j] + a[j + 1])
j = i;
if (a[j] + a[j + 1] < l)
{
puts("Impossible");
return 0;
}
puts("Possible");
for (int i = 1; i < j; ++i)
printf("%d
", i);
for (int i = n - 1; i >= j; --i)
printf("%d
", i);
return 0;
}
D - Stamp Rally
整体二分，用撤销并查集维护即可。
//waz
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
int F()
{
char ch;
int x, a;
while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
if (ch == '-') ch = getchar(), a = -1;
else a = 1;
x = ch - '0';
while (ch = getchar(), ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + ch - '0';
return a * x;
}
const int N = 1e5 + 10;
struct query
{
int x, y, z, id;
};
int ans[N];
int n, m;
int a[N], b[N];
struct info
{
int fa, siz;
} f[N];
struct item
{
int x, y;
info a, b;
} stk[N];
int tp;
int find(int x) { return f[x].fa == x ? x : find(f[x].fa); }
void unit(int x, int y)
{
x = find(x), y = find(y);
if (x == y) return;
if (f[x].siz < f[y].siz) swap(x, y);
stk[++tp] = (item) {x, y, f[x], f[y]};
f[y].fa = x, f[x].siz += f[y].siz;
}
void undo(int beg)
{
while (tp != beg)
{
f[stk[tp].x] = stk[tp].a;
f[stk[tp].y] = stk[tp].b;
--tp;
}
}
void solve(int l, int r, vector<query> v)
{
if (l == r)
{
for (auto x : v)
ans[x.id] = l;
return;
}
int mid = (l + r) >> 1;
int now = tp;
for (int i = l; i <= mid; ++i) unit(a[i], b[i]);
vector<query> L, R;
L.clear(), R.clear();
for (auto x : v)
{
int siz = f[find(x.x)].siz;
if (find(x.x) != find(x.y))
siz += f[find(x.y)].siz;
if (siz >= x.z)
L.pb(x);
else
R.pb(x);
}
solve(mid + 1, r, R);
undo(now);
solve(l, mid, L);
}
int main()
{
gii(n, m);
for (int i = 1; i <= n; ++i) f[i] = (info) {i, 1};
for (int i = 1; i <= m; ++i)
gii(a[i], b[i]);
int Q;
gi(Q);
vector<query> v; v.clear();
for (int i = 1; i <= Q; ++i)
{
int x, y, z;
giii(x, y, z);
v.pb((query){x, y, z, i});
}
solve(1, m, v);
for (int i = 1; i <= Q; ++i)
printf("%d
", ans[i]);
}
E - Candy Piles
把决策表画出来，我们发现一个人选择一种删除方式，另一个就选另一种，也就是沿着x=y的斜线走，最后只要有一个方向能让先手赢，先手肯定会走那一边，否则就是后手必胜。
//waz
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
int F()
{
char ch;
int x, a;
while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
if (ch == '-') ch = getchar(), a = -1;
else a = 1;
x = ch - '0';
while (ch = getchar(), ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + ch - '0';
return a * x;
}
int n, a[100010];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", a + i);
sort(a + 1, a + n + 1);
reverse(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i)
{
if (i + 1 > a[i + 1])
{
int j = i + 1, ans = 0;
for (; a[j] == i; ++j) ans ^= 1;
if ((ans || ((a[i] - i) & 1))) puts("First");
else puts("Second");
break;
}
}
}
F - Leftmost Ball
我们发现令白球的编号是1...n，保证编号小的在前面，只要算出这个方案数乘上n!，我们发现这是个特殊的拓扑图，求拓扑序方案数，一个n^2dp就好了。
//waz
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))
int F()
{
char ch;
int x, a;
while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
if (ch == '-') ch = getchar(), a = -1;
else a = 1;
x = ch - '0';
while (ch = getchar(), ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + ch - '0';
return a * x;
}
const int mod = 1e9 + 7;
int fpow(int a, int x)
{
int ret = 1;
for (; x; x >>= 1)
{
if (x & 1) ret = 1LL * ret * a % mod;
a = 1LL * a * a % mod;
}
return ret;
}
int f[2010][2010], n, k, fac[2010 * 2010], ifac[2010 * 2010];
int C(int n, int m)
{
if (n < m || m < 0) return 0;
return 1LL * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
int get(int x, int y)
{
return C(x + y, y);
}
int main()
{
gii(n, k);
if (k == 1)
{
puts("1");
return 0;
}
f[0][0] = 1;
fac[0] = 1;
for (int i = 1; i <= (n + 2) * (k + 2); ++i) fac[i] = 1LL * fac[i - 1] * i % mod;
ifac[(n + 2) * (k + 2)] = fpow(fac[(n + 2) * (k + 2)], mod - 2);
for (int i = (n + 2) * (k + 2); i; --i) ifac[i - 1] = 1LL * ifac[i] * i % mod;
for (int i = 0; i <= n; ++i)
for (int j = i; j <= n; ++j)
{
if (i) f[i][j] = (f[i][j] + f[i - 1][j]) % mod;
if (j) f[i][j] = (f[i][j] + 1LL * f[i][j - 1] * get((j - 1) * (k - 1) + i, k - 2)) % mod;
//cerr << "get = " << get(j * (k - 1), k - 2) << endl;
}
printf("%d
", int((1LL * f[n][n] * fac[n]) % mod));
return 0;
}