A - Shik and Stone
直接模拟判断就好了。
//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, m;
char str[20][20];
int main()
{
gii(n, m);
for (int i = 1; i <= n; ++i) scanf("%s", str[i] + 1);
int x = 1, y = 1;
if (str[x][y] == '.')
{
puts("Impossible");
return 0;
}
int cnt = 0;
for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) cnt += (str[i][j] == '#');
for (int i = 1; i < cnt; ++i)
{
if (str[x + 1][y] == '#') ++x;
else if (str[x][y + 1] == '#') ++y;
else
{
puts("Impossible");
return 0;
}
}
puts("Possible");
return 0;
}
B - Construct Sequences
我们可以让a[p[i]]=20000*p[i]+i，b[i]=20000*(n-p[i]+1)+i，这样子就好了。
//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 = 20010;
int n, p[N], a[N], b[N];
int main()
{
gi(n);
for (int i = 1; i <= n; ++i) gi(p[i]);
for (int i = 1; i <= n; ++i) a[i] = a[i - 1] + 20000;
for (int i = n; i; --i) b[i] = b[i + 1] + 20000;
for (int i = 1; i <= n; ++i) a[p[i]] += i, b[p[i]] += i;
for (int i = 1; i <= n; ++i) printf("%d ", a[i]); puts("");
for (int i = 1; i <= n; ++i) printf("%d ", b[i]); puts("");
return 0;
}
C - Pushing Balls
我们用整体法，发现每做一次操作，递归下去依然是一个等差序列。
//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;
double a, x, ans;
int main()
{
giii(n, a, x);
for(int i = n; i; --i)
{
double m = 2 * i;
double v = (a + (a + (m - 1) *x)) / m * i;
ans += v;
a = ((m + 2) * a + 5 * x) / m;
x = (m + 4) / m * x;
}
printf("%.15lf
", ans);
return 0;
}
D - Shik and Game
列出dp方程，分类讨论max，用线段树优化一下复杂度即可。
//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 MaxN = 1e5 + 10;
int N, E, T, x[MaxN];
long long f[MaxN];
int find(int i)
{
int j = i;
for (int k = 18; ~k; --k)
if ((j - (1 << k)) >= 0 && 2 * (x[i] - x[j - (1 << k) + 1]) <= T)
j -= 1 << k;
return j;
}
struct zkw
{
long long s[MaxN << 2];
int cnt;
void build()
{
cnt = 1;
for (; cnt < N + 3; cnt <<= 1); --cnt;
for (int i = 1; i <= N + 1; ++i) s[cnt + i] = 1e18;
for (int i = cnt; i; --i) s[i] = 1e18;
}
void modify(int pos, long long x)
{
++pos;
pos += cnt;
s[pos] = min(s[pos], x);
for (pos >>= 1; pos; pos >>= 1) s[pos] = min(s[pos << 1], s[pos << 1 | 1]);
}
long long query(int l, int r)
{
long long ans = 1e18;
++l, ++r;
for (l += cnt - 1, r += cnt + 1; l ^ r ^ 1; l >>= 1, r >>= 1)
{
if (~l & 1) ans = min(ans, s[l ^ 1]);
if (r & 1) ans = min(ans, s[r ^ 1]);
}
return ans;
}
} s1, s2;
int main()
{
giii(N, E, T);
for (int i = 1; i <= N; ++i) gi(x[i]), f[i] = 1e18;
s1.build(), s2.build();
s1.modify(0, -2 * x[1]);
s2.modify(0, 0);
for (int i = 1; i <= N; ++i)
{
int k = find(i);
f[i] = min(f[i], s1.query(0, k - 1) + 3LL * x[i]);
/*for (int j = 0; j < k; ++j)
f[i] = min(f[i], 3LL * x[i] + f[j] - x[j] - 2 * x[j + 1]));*/
f[i] = min(f[i], s2.query(k, i - 1) + x[i] + T);
s1.modify(i, f[i] - x[i] - 2 * x[i + 1]);
s2.modify(i, f[i] - x[i]);
/*for (int j = k; j < i; ++j)
f[i] = min(f[i], f[j] + x[i] - x[j] + T);*/
}
//cerr << f[2] << endl;
f[N] += E - x[N];
printf("%lld
", f[N]);
return 0;
}
E - Shik and Travel
二分答案，每个点存很多pair(x,y)表示第一次走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 long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;
typedef pair<int64, int64> PII;
typedef vector<int> VI;
#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 = 1 << 20;
int a[N], v[N], n;
vector<PII> p[N];
int son[N][2];
bool level[N];
vector<PII> A, B;
bool work(int x, int64 lim)
{
p[x].clear();
if (level[x])
{
p[x].pb(mp(0LL, 0LL));
return 1;
}
int ls = son[x][0], rs = son[x][1];
if (!SZ(p[ls]) || !SZ(p[rs])) return 0;
if (p[ls].size() > p[rs].size()) swap(ls, rs);
A.clear(); B.clear();
int64 L = lim - v[ls] - v[rs];
int64 mi = 1LL << 35;
for (int i = 0, j = 0; i < SZ(p[ls]); ++i)
{
while (p[ls][i].se > L - mi && j < SZ(p[rs])) mi = min(mi, p[rs][j].fi), ++j;
if (p[ls][i].se > L - mi) break;
if (j) A.pb(mp(p[ls][i].fi + v[ls], p[rs][j - 1].se + v[rs]));
}
mi = 1LL << 35;
for (int j = 0, i = 0; j < SZ(p[rs]); ++j)
{
while (p[rs][j].se > L - mi && i < SZ(p[ls])) mi = min(mi, p[ls][i].fi), ++i;
if (p[rs][j].se > L - mi) break;
if (i)
{
if (SZ(B))
{
if (B[SZ(B) - 1].se == p[ls][i - 1].se + v[ls])
B[SZ(B) - 1].fi = min(B[SZ(B) - 1].fi, p[rs][j].fi + v[rs]);
else B.pb(mp(p[rs][j].fi + v[rs], p[ls][i - 1].se + v[ls]));
}
else B.pb(mp(p[rs][j].fi + v[rs], p[ls][i - 1].se + v[ls]));
}
}
int i = 0, j = 0;
while (i < SZ(A) || j < SZ(B))
{
if (j >= SZ(B)) p[x].pb(A[i++]);
else if (i >= SZ(A) || A[i].se > B[j].se) p[x].pb(B[j++]);
else p[x].pb(A[i++]);
}
if (!SZ(p[x])) return 0;
return 1;
}
bool check(int64 lim)
{
for (int i = n; i; --i) if (!work(i, lim)) return 0;
return 1;
}
main()
{
gi(n);
for (int i = 1; i <= n; ++i) level[i] = 1;
for (int i = 2; i <= n; ++i)
{
gii(a[i], v[i]);
level[a[i]] = 0;
if (son[a[i]][0]) son[a[i]][1] = i;
else son[a[i]][0] = i;
}
int64 x = -1;
for (int i = 35; ~i; --i)
if (!check(x + (1LL << i)))
x += (1LL << i);
printf("%lld
", x + 1);
return 0;
}
F - Shik and Copying String
贪心取，用个队列维护互相影响的点的最大值，就是答案了。
//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 = 1e6 + 10;
int n;
char s[N], t[N];
int q[N];
int main()
{
int l = 1, r = 0;
gi(n);
scanf("%s", s + 1);
scanf("%s", t + 1);
if (!strcmp(s + 1, t + 1))
{
puts("0");
return 0;
}
int ans = 0, cnt = 0;
for (int i = n, j = n; i; --i)
{
if (t[i] == t[i - 1]);
else
{
j = min(j, i);
while (j && t[i] != s[j]) --j;
if (!j) return puts("-1"), 0;
while (l <= r)
{
if (q[l] - (r - l) > i) ++l;
else break;
}
q[++r] = j;
if (i != j) ans = max(ans, r - l + 1);
}
}
printf("%d
", ++ans);
return 0;
}