A. 极源流体
上和下，左和右是等效的，只考虑下和右。
操作顺序不影响结果，按任意顺序操作x次右，y次下后，一个黑格一定会变成一个长为x，宽为y的矩形。可以用两个队列记录位置，这样可以把每一步单独拿出来，枚举x，找到最小的合法的y更新答案。
TLE 79
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 750;
typedef pair<int, int> pii;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
int cnt, pnt, n, m, ans;
int f[maxn*maxn], pf[maxn*maxn];
queue<pii> q, Q, p, P;
bool pcol[maxn][maxn], col[maxn][maxn];
char c[maxn][maxn];
int dx[4] = {0, -1, -1, -1};
int dy[4] = {-1, -1, 0, 1};
int dw[3] = {-1, 0, 1};
bool check(int x, int y) {return x > 0 && y > 0 && x <= n && y <= m;}
int id(int x, int y) {return (x-1)*m+y;}
int fa(int x) {return f[x] == x ? x : f[x] = fa(f[x]);}
int merge(int x, int y) {x = fa(x), y = fa(y); if(x == y) return false; f[y] = x; return true;}
int pa(int x) {return pf[x] == x ? x : pf[x] = pa(pf[x]);}
int pmerge(int x, int y) {x = pa(x), y = pa(y); if(x == y) return false; pf[y] = x; return true;}
void sol(int down)
{
while(!q.empty()) q.pop(); while(!Q.empty()) Q.pop();
cnt = pnt;
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) col[i][j] = pcol[i][j];
for(int i=1; i<=n*m; i++) f[i] = pf[i];
for(int i=1; i<=n; i++) for(int j=1; j<m; j++) if(col[i][j] && !col[i][j+1]) q.push(pii(i, j));
int nans = down;
for(int i=1; i<=m; i++)
{
if(cnt <= 1) break;
nans++;
while(!q.empty())
{
pii now = q.front(); q.pop();
if(now.second == m - 1) continue;
if(now.second < m - 1)
{
for(int j=0; j<3; j++)
{
int nx = now.first + dw[j], ny = now.second + 2;
if(col[nx][ny] && check(nx, ny) && merge(id(now.first,now.second), id(nx,ny))) cnt--;
}
}
if(col[now.first][now.second+1] == 0)
{
Q.push(pii(now.first, now.second+1));
col[now.first][now.second+1] = 1;
merge(id(now.first, now.second), id(now.first, now.second+1));
}
}
swap(Q, q);
}
if(cnt == 1) ans = min(ans, nans);
}
int main()
{
freopen("fluid.in", "r", stdin);
freopen("fluid.out", "w", stdout);
n = read(); m = read();
for(int i=1; i<=n; i++) scanf("%s", c[i]+1);
for(int i=1; i<=n*m; i++) pf[i] = i;
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) pcol[i][j] = c[i][j]-'0';
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) if(pcol[i][j])
{
pnt++;
for(int k=0; k<4; k++)
{
int nx = i + dx[k], ny = j + dy[k];
if(pcol[nx][ny] && check(nx, ny) && pmerge(id(i,j), id(nx,ny))) pnt--;
}
}
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) if(pcol[i][j]) p.push(pii(i, j));
ans = n + m;
for(int i=0; i<=n && i<ans; i++)
{
sol(i);
while(!p.empty())
{
pii now = p.front(); p.pop();
if(now.first == n) continue;//为什么上面是m-1这里不是n-1？？
if(now.first < n - 1)
{
for(int j=0; j<3; j++)
{
int nx = now.first + 2, ny = now.second + dw[j];
if(pcol[nx][ny] && check(nx, ny) && pmerge(id(now.first, now.second), id(nx, ny))) pnt--;
}
}
//差别是，上面的染色只用于当前，而当前又用不到，所以没有用
//可是这个染色是有用的
if(pcol[now.first+1][now.second] == 0)
{
P.push(pii(now.first+1, now.second));
pcol[now.first+1][now.second] = 1;
pmerge(id(now.first, now.second), id(now.first+1, now.second));
}
}
swap(P, p);
}
printf("%d\n", ans);
return 0;
}题意转化：
对每个黑格子建一个点，两个黑格子之间连一条边(优化就是只连有可能最近的两个)，这条边的两个权值分别是横纵坐标差。求一组(x, y)使得所有a<=x,b<=y的边能把整张图联通且x+y最小。把合法的边按照横坐标差分组，枚举x，y，找到y组的元素中x满足条件的边加上(就是把所有a<=x,b<=y的边加上)，重新枚举的时候还原并查集。(方法是把每个点的father记录下来)
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 750;
typedef pair<int, int> pii;
char c[maxn][maxn];
int n, m, ans, f[maxn*maxn], tot, cnt;
vector<int> H[maxn], L[maxn], le;
int id(int x, int y) {return (x-1)*m+y;}
int fa(int x) {return f[x] == x ? x : f[x] = fa(f[x]);}
void merge(int x, int y) {x = fa(x), y = fa(y); if(x != y) f[y] = x, cnt--;}
struct edge{int a, b, x, y;} d[maxn*maxn*2];
vector<edge> v[maxn];
bool cmp(const edge &x, const edge &y) {return x.x == y.x ? x.y < y.y : x.x < y.x;}
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
int main()
{
freopen("fluid.in", "r", stdin);
freopen("fluid.out", "w", stdout);
n = read(); m = read();
for(int i=1; i<=n; i++) scanf("%s", c[i]+1);
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++)
{
if(c[i][j] == '1') H[i].push_back(j), L[j].push_back(i);
}
for(int i=1; i<=n; i++)
{
for(int x : H[i])
{
for(int j=x; j<=m; j++)
{
if(c[i][j] == '1' && j != x) break;//就因为去掉这个RE了？
int p = upper_bound(L[j].begin(), L[j].end(), i)-L[j].begin();
if(p >= L[j].size()) continue;
p = L[j][p];
d[++tot] = {id(i,x), id(p,j), p-i-1, j-x-1};
}
for(int j=x-1; j>=1; j--)
{
if(c[i][j] == '1') break;
int p = upper_bound(L[j].begin(), L[j].end(), i)-L[j].begin();
if(p >= L[j].size()) continue;
p = L[j][p];
d[++tot] = {id(i,x), id(p,j), p-i-1, x-j-1};
}
}
for(int j=0; j+1<H[i].size(); j++) d[++tot] = {id(i,H[i][j]), id(i,H[i][j+1]), -1, H[i][j+1]-H[i][j]-1};
}
sort(d+1, d+1+tot, cmp);
for(int i=1; i<=n*m; i++) f[i] = i;
//两项都<=0那不就是同一个点的意思吗？
for(int i=1; i<=tot; i++) if(d[i].x<=0 && d[i].y<=0) merge(d[i].a, d[i].b);
for(int i=1; i<=tot; i++)
{
d[i].a = fa(d[i].a), d[i].b = fa(d[i].b);
if(d[i].a != d[i].b) v[d[i].y+2].push_back(d[i]);
}
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++)
{
int d = id(i, j); if(fa(d) == d && c[i][j] == '1') le.push_back(d);
}
int ans = 0x3f3f3f3f;
//对每个点找出不同横坐标差下，纵坐标差最小的点建两个权值的边，然后枚举向下走的距离加边，统计答案
for(int i=0; i<=n; i++)
{
for(int x : le) f[x] = x;//还原初始状态
cnt = le.size();
for(int j=1; j<=m+2; j++)
{
for(edge x : v[j]) if(x.x <= i) merge(x.a, x.b);
if(cnt == 1) {ans = min(ans, i+max(0,j-2)); break;}
if(i+max(0, j-2) > ans) break;
}
}
printf("%d\n", ans);
return 0;
}
B. 等差数列
我连直接枚举公差都没想到……
对于一个公差，每个数都有一个使它不变的首项，不变的个数越多越好，找到出现最多的当首项就是当前公差下的最优解。
细节是及时排除不可能的首项防止数组越界。
code
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 271900;
int n, w, a[maxn], ans, res, d, vis[maxn], mx;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
int main()
{
freopen("sequence.in", "r", stdin);
freopen("sequence.out", "w", stdout);
n = read(); w = read(); bool sp = 1;
for(int i=1; i<=n; i++)
{
a[i] = read();
if(a[i] != 1) sp = 0;
}
if(sp)
{
printf("0\n"); exit(0);
}
ans = n - 1;
d = w / (n-1);
for(int i=0; i<=d; i++)
{
res = 0; mx = 0;
for(int j=1; j<=n; j++)
{
int x = a[j]-i*(j-1);
if(x <= 0 || a[j]+i*(n-j)>w) continue;
vis[x]++;
if(vis[x] > vis[mx]) mx = x;
}
for(int j=1; j<=n; j++)
{
if(a[j] != mx) res++;
mx += i;
int x = a[j]-i*(j-1);
if(x <= 0 || a[j]+i*(n-j)>w) continue;
vis[x] = 0;//忽然发现没清空？？
}
ans = min(ans, res);
}
printf("%d\n", ans);
return 0;
}
C. 送给好友的礼物
枚举二进制数有77分。
dp很神奇， 解释在注释里
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 447;
int n, k, si[maxn], key[maxn], is[maxn], dis[maxn][maxn];
short f[3][maxn][maxn+maxn];
vector<int> g[maxn], v;
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
void dfs(int x, int fa, int root)
{
for(int v : g[x])
{
if(v == fa) continue;
dis[root][v] = dis[root][x] + 1;
dfs(v, x, root);
}
}
void sol(int x, int fa)
{
for(int v : g[x])
{
if(v == fa) continue;
sol(v, x);
si[x] += si[v];
}
if(is[x] && !si[x]) v.push_back(x);
si[x] += is[x];
}
void Ckmi(short &x, short y) {x = x < y ? x : y;}
inline int min(int x, int y) {x = x < y ? x : y; return x;}
//既然加多少强制类型转换都不让我过编译，那我就不用了qwq
int main()
{
freopen("gift.in", "r", stdin);
freopen("gift.out", "w", stdout);
n = read(); k = read();
for(int i=1; i<n; i++)
{
int u = read(), v = read();
g[u].push_back(v); g[v].push_back(u);
}
for(int i=1; i<=k; i++) is[key[i] = read()] = 1;
for(int i=1; i<=n; i++) dfs(i, 0, i);
if(k == 1) {printf("%d\n", dis[1][key[1]]*2); exit(0);}
//1又不是叶子，把1放进来干什么？？
//因为可能所有的叶子都和当前讨论的叶子同组，另一组为空，计算路径时就从起点开始走
//当k!=1时它不会是最终答案，但可以是中间过程
v.push_back(1); sol(1, 0);
memset(f, 0x3f, sizeof(f));
f[1][0][dis[1][v[1]]] = 0;
int s = v.size();
for(int i=1; i<s-1; i++)
{
for(int j=0; j<i; j++)
{
for(int t=0; t<=n+n; t++) if(f[i&1][j][t] != f[0][0][0])
{
//这时加入第1个叶子。第i+1个叶子还不考虑
//第i个叶子变成了2组的最后一个，如果i+1在2组，2组的答案是new f，1组的答案是t
Ckmi(f[(i+1)&1][i][f[i&1][j][t]+dis[v[j]][v[i+1]]], t);
//第i个叶子变成了1组的最后一个，如果i+1在2组，2组的答案是f[i&1][j][t]，1组的答案是new t
Ckmi(f[(i+1)&1][j][t+dis[v[i]][v[i+1]]], f[i&1][j][t]);
//其实1组二组什么的只是在讨论第i+1个叶子到底是不是和i一组，第二维就是不和i+1一组的最后一个
//f的值一直是第一维所属组的答案，1组和2组是相对的
f[i&1][j][t] = f[0][0][0];
}
}
}
short ans = f[0][0][0];
for(short i=0; i<s-1; i++)//s-1(最后一个叶子)所属组外另一个组的最后一个
{
for(short j=0; j<=min((short)n+n, ans); j++)
{
ans = min(ans, (short)max(j+dis[v[s-1]][1], f[(s-1)&1][i][j]+dis[v[i]][1]));
}
}
printf("%d\n", ans);
return 0;
}
D. 非常困难的压轴题
题解是枚举中间的W前后做乘法。
其实对L，W，和S都可以考虑枚举它前面的数，所以每个字母合法的个数都是它上一级的字母个数的和，所以加两个前缀和。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 145000;
int n;
ll res, fis, ans;
char s[maxn];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
{
f = -1;
}
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = (x << 1) + (x << 3) + (ch^48);
ch = getchar();
}
return x * f;
}
int main()
{
freopen("lws.in", "r", stdin);
freopen("lws.out", "w", stdout);
scanf("%s", s+1);
n = strlen(s+1);
for(int i=1; i<=n; i++)
{
if(s[i] == 'L') res++;
else if(s[i] == 'W') fis += res;
else if(s[i] == 'S') ans += fis;
}
printf("%lld\n", ans);
return 0;
}