以前打的几场都没有及时补题，这几天补起来
这一场期望过6题，实际过4题。还是4个暴力。主要是C题WA了好几发，细节太多了……
A - Diagonal Walking
直接贪心，正确性显然。
#include <bits/stdc++.h>
using namespace std;
int n; char A[200], B[200];
template<typename T>
inline void readint(T& x) {
T f=1, r=0; char c=getchar();
while(!isdigit(c)){ if(c=='-')f=-1; c=getchar(); }
while(isdigit(c)){ r=r*10+c-'0'; c=getchar(); }
x = f*r;
}
inline char readc() {
char c=getchar();
while(!isalnum(c) && !ispunct(c))
c=getchar();
return c;
}
inline void readstr(char *str) {
char c=getchar(); int p=0;
while(!isalnum(c) && !ispunct(c)) c=getchar();
while(isalnum(c) || ispunct(c)) {
str[p++]=c;
c=getchar();
}
str[p]='\0';
}
int main() {
readint(n);
readstr(A+1);
int j = 1;
for(int i = 1; i <= n;) {
if(i <= n-1 && A[i] != A[i+1])
B[j++] = 'D', i+=2;
else
B[j++] = A[i++];
}
cout << j-1 << endl;
return 0;
}
B - String Typing
暴力模拟。
值得注意的是很多人把题意看错了，有的认为可以多次复制，有的认为可以复制任意后缀。
我用这个数据：
8
ababcabc
叉了冬令营文艺汇演在后台打碟的rvalue童鞋=.=
#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline void readint(T& x) {
T f=1, r=0; char c=getchar();
while(!isdigit(c)){ if(c=='-')f=-1; c=getchar(); }
while(isdigit(c)){ r=r*10+c-'0'; c=getchar(); }
x = f*r;
}
inline char readc() {
char c=getchar();
while(!isalnum(c) && !ispunct(c))
c=getchar();
return c;
}
inline void readstr(char *str) {
char c=getchar(); int p=0;
while(!isalnum(c) && !ispunct(c)) c=getchar();
while(isalnum(c) || ispunct(c)) {
str[p++]=c;
c=getchar();
}
str[p]='\0';
}
int n, ans; char str[200], a[200], b[200];
int main() {
readint(n);
readstr(str);
ans = n;
for(int i = 1; i <= n/2; i++) {
memcpy(a, str, sizeof(char) * i);
a[i] = '\0';
memcpy(b, str + i, sizeof(char) * i);
b[i] = '\0';
if(strcmp(a, b) == 0) ans = min(ans, i + 1 + (n - 2*i));
}
cout << ans;
return 0;
}
C - Matrix Walk
最恶心的模拟题。quailty大爷都被hack了。
quailty大爷：我都得想想怎么出一道这么恶心的细节题
出题人还是很良心地加强了Pretest，我最开始一直WA on test 4。
细节如下：
- 不能原地不动！！！
- 在找出 $y$ 之后要模拟一遍实际行走的操作，以确定有没有从某一行第一个跳到上一行最后一个，或是从某一行最后一个走到上一行第一个，或是发生了越界什么的。
#include <bits/stdc++.h>
#define FAIL() do{ puts("NO"); exit(0); }while(0)
using namespace std;
template<typename T>
inline void readint(T& x) {
T f=1, r=0; char c=getchar();
while(!isdigit(c)){ if(c=='-')f=-1; c=getchar(); }
while(isdigit(c)){ r=r*10+c-'0'; c=getchar(); }
x = f*r;
}
const int MAXN = 2e5, MAXNUM = 1e9;
int n, x, y, cx, cy, a[MAXN+10];
void Init() {
readint(n);
for(int i = 1; i <= n; i++)
readint(a[i]);
}
int get_i(int idx) {
return idx % y == 0 ? idx / y: idx / y + 1 ;
}
int get_j(int idx) {
return idx % y == 0 ? y : idx % y;
}
void Work() {
for(int i = 1; i <= n-1; i++) {
if(abs(a[i+1] - a[i]) > 1) {
if(y == 0) y = abs(a[i+1] - a[i]);
else {
if(y != abs(a[i+1] - a[i]))
FAIL();
else
continue;
}
}
}
if(y > MAXNUM) FAIL();
if(y == 0) y = MAXNUM;
x = MAXNUM;
cx = get_i(a[1]), cy = get_j(a[1]);
for(int i = 1; i <= n-1; i++) {
int dx = get_i(a[i+1]) - get_i(a[i]);
int dy = get_j(a[i+1]) - get_j(a[i]);
if(abs(dx) + abs(dy) != 1) FAIL();
if(cy == 1 && dy == -1) FAIL();
if(cy == y && dy == 1) FAIL();
if(cx == 1 && dx == -1) FAIL();
if(cx == x && dx == 1) FAIL();
cx += dx; cy += dy;
}
puts("YES");
cout << x << ' ' << y;
}
int main() {
Init(); Work();
return 0;
}
D - Fight Against Traffic
2次BFS后暴力找要连的边并且更新答案。
qls告诉我，其实可以开到 $n \leq 4 \cdot 10^5$ . 方法是转化为二维数点。
首先BFS，找出每个点 $u$ 到源点的距离 $d_{s, u}$ 和到汇点的距离 $d_{u, t}$ . 然后问题转化为：对于一个点 $u$ 找出同时满足 $d_{s, u} + 1 + d_{v, t} \ge d_{s, t}$ 和 $d_{s, v} + 1 + d_{u, t} \ge d_{s, t}$ 的点 $v$ 的数目。也就是： \(d_{v, t} \ge d_{s, t} - d_{s, u} - 1 \text{ 且 } d_{s, v} \ge d_{s, t} - d_{u, t} - 1\) 以从 $s$ 出发的距离为 $x$ 轴，从 $t$ 出发的距离为 $y$ 轴，就可以二维数点了。扫描线+线段树即可。
评论里面好像还有一种 $O(n+m)$ 的做法？
E - Water Taps
机智的人会想到贪心，只有我在想线性规划转网络流，还有单纯形=。=
最后30min想到贪心，写了出来却死活过不了，真是悲伤。后来发现主要是cin的锅……然而去掉cin之后还是WA on test 8，原因不明。
贪心策略如下：把所有的水龙头都打开，然后每次关掉温度最高的。二分关多少即可。
代码等AC了再贴……
F - Runner’s Problem
递推关系容易发现，但是要应对 $3 ≤ m ≤ 10^{18}$ 的数据范围怎么做？比赛的时候，我一直在想能不能用组合数学的方法 $O(1)$ 地得出答案。其实递推就是个很好的工具啊……有了递推套上矩阵快速幂就可以跑这个数据范围了……
大范围的递推和DP，用矩阵乘法优化！
怎么优化呢？有2个维度啊？没关系，这么做：
当没有障碍的时候： \(\begin{bmatrix} f(1, i-1)& f(2, i-1)& f(3, i-1) \end{bmatrix} \times \begin{bmatrix} 1& 1& 0 \\ 1& 1& 1 \\ 0& 1& 1 \end{bmatrix} = \begin{bmatrix} f(1, i) & f(2, i) & f(3, i) \end{bmatrix}\) 有障碍的时候，相应地修改转移矩阵即可。
注意到障碍数目 $n \le 10^4$ ，于是对于每段障碍把转移矩阵乘起来就可以了。对于某一段障碍用矩阵快速幂算。复杂度为 $O(n \lg m)$ ，可以接受。
注意：离散化后如果需要用到差分，就一定要把 $l, r+1$ 放进离散化数组！！！！
保险的做法是把 $l, r$ 周围的全部丢进去，不过数组就要开够，建议开8倍。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int MAXN = 1e4, WIDTH = 3, MOD = int(1e9+7);
struct Matrix {
int A[WIDTH][WIDTH];
Matrix() {
memset(A, 0, sizeof(int) * WIDTH * WIDTH);
}
int* operator[](const int idx) {
assert(idx >= 0 && idx < WIDTH);
return A[idx];
}
const int* operator[](const int idx) const {
assert(idx >= 0 && idx < WIDTH);
return (const int*)A[idx];
}
static Matrix unit() {
Matrix ret;
for(int i = 0; i < WIDTH; i++)
ret[i][i] = 1;
return ret;
}
Matrix operator*(const Matrix &rhs) const {
Matrix ret;
for(int i = 0; i < WIDTH; i++)
for(int j = 0; j < WIDTH; j++)
for(int k = 0; k < WIDTH; k++)
ret[i][j] = (ret[i][j] + (int64(A[i][k])%MOD) * (rhs[k][j]%MOD) % MOD) % MOD;
return ret;
}
Matrix operator=(const Matrix &rhs) {
memcpy(A, rhs.A, sizeof(int) * WIDTH * WIDTH);
return *this;
}
friend ostream& operator<<(ostream &out, const Matrix &rhs) {
for(int i = 0; i < WIDTH; i++) {
for(int j = 0; j < WIDTH; j++)
out << rhs[i][j] << ' ';
out << '\n';
}
return out;
}
};
struct Interval {
int a; int64 l, r;
};
int64 n, m, nums[(MAXN+10)<<4]; Interval I[(MAXN+10)<<4];
int M[5][(MAXN+10)<<4];
Matrix fastpow(Matrix a, int64 x) {
Matrix ret = Matrix::unit();
while(x > 0) {
if(x & 1) ret = ret * a;
x >>= 1; a = a * a;
}
return ret;
}
template<typename T>
inline void readint(T &x) {
T f=1, r=0; char c=getchar();
while(!isdigit(c)) { if(c=='-')f=-1; c=getchar(); }
while(isdigit(c)) { r=r*10+c-'0'; c=getchar(); }
x = f*r;
}
void init() {
readint(n); readint(m);
for(int i = 1; i <= n; i++) {
readint(I[i].a); I[i].a--; // Line index start from 0, correspond with the matrix
readint(I[i].l); readint(I[i].r);
nums[++nums[0]] = I[i].l, nums[++nums[0]] = I[i].r;
nums[++nums[0]] = I[i].l+1, nums[++nums[0]] = I[i].r+1;
if(I[i].l > 1) nums[++nums[0]] = I[i].l-1;
if(I[i].r > 1) nums[++nums[0]] = I[i].r-1;
}
nums[++nums[0]] = 1; nums[++nums[0]] = m;
sort(nums + 1, nums + nums[0] + 1);
nums[0] = unique(nums + 1, nums + nums[0] + 1) - &nums[1];
for(int i = 1; i <= n; i++) {
I[i].l = lower_bound(nums + 1, nums + nums[0] + 1, I[i].l) - nums;
I[i].r = lower_bound(nums + 1, nums + nums[0] + 1, I[i].r) - nums;
M[I[i].a][I[i].l]++, M[I[i].a][I[i].r+1]--;
}
for(int i = 1; i <= nums[0]; i++) {
M[0][i] += M[0][i-1], M[1][i] += M[1][i-1], M[2][i] += M[2][i-1];
}
}
void work() {
Matrix V, Trans, A;
V[0][1] = 1;
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
Trans[i][j] = 1;
Trans[0][2] = Trans[2][0] = 0;
for(int i = 1; i <= nums[0]; i++) {
A = Trans;
for(int k = 0; k < 3; k++)
if(M[k][i]) {
V[0][k] = 0;
for(int j = 0; j < 3; j++)
A[k][j] = 0;
}
if(i == nums[0]) break;
A = fastpow(A, nums[i+1] - nums[i]);
V = V * A;
}
cout << V[0][1];
}
int main() {
init(); work();
return 0;
}
G - Castle Defense
坑着
