Day1.THUSC2017 Day1
T1 chocolate
给一个 $n imes m$ 的矩形，每个格子有颜色和权值，有些格子是坏的，不能选，求一个最小的连通块，满足至少有 $k$ 种颜色，且权值中位数最小
如果连通块最小但权值中位数不是最小可以拿到部分分
$n imes m leq 233,k leq 5$
subtask 有：爆搜，总颜色数不超过 8，总颜色数不超过 14
sol：
当时做的时候脑子有点不清楚...做了颜色数很少的 subtask 的第一问，然后还挂了
第一问颜色少的情况可以对每种颜色新开一个节点，然后对所有新节点做一遍斯坦纳树，这样可以过不超过 8 种颜色的点
然后就没多想，可能离正解就差一步吧
第一问正解是这样的：
把所有颜色随机映射到 $[1,k]$ 里，多做几遍斯坦纳树，因为这样正确的概率是 $frac{k!}{k^k}$，大概做 40 次就过了
甚至有 tm 这么一道题 bzoj5232 就是单纯把斯坦纳树换成树形 dp
怪自己刷题太少吧...
第二问的话，发现之前做斯坦纳树每个点权值都是 1，然后分析一下发现中位数关于斯坦纳树的大小是有单调性的，所以一个带权二分就做完了
曾经吐槽 wxj 出题是三个板子套起来，如今三个板子套起来的题我都不会做了呢
#include <cstdio> #include <cstdlib> #include <queue> #include <ctime> #include <algorithm> #define N 235 #define K 6 #define M 1111111 #define INF 1111111111 using namespace std; int dis[N][N][1 << K], col[N][N], a[N][N], c[N][N], w[N][N], rand_c[N * N]; bool inq[N][N][1 << K]; int n, m, min_col, ans; int queue_x[M], queue_y[M], queue_t[M]; void Spfa(int state) { int ch[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int l = 1, r = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (dis[i][j][state] != INF) { queue_x[++r] = i; queue_y[r] = j; queue_t[r] = state; inq[i][j][state] = true; } while (l <= r) { int x = queue_x[l], y = queue_y[l], t = queue_t[l]; inq[x][y][t] = false; for (int i = 0; i < 4; i++) { int xx = x + ch[i][0], yy = y + ch[i][1], tt; if (!(xx >= 1 && xx <= n && yy >= 1 && yy <= m) || c[xx][yy] == -1) continue; tt = t | (1 << (c[xx][yy] - 1)); if (dis[xx][yy][tt] > dis[x][y][t] + w[xx][yy]) { dis[xx][yy][tt] = dis[x][y][t] + w[xx][yy]; if (!inq[xx][yy][tt]) { inq[xx][yy][tt] = true; queue_x[++r] = xx; queue_y[r] = yy; queue_t[r] = tt; } } } l++; } return ; } void Steiner() { for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { for (int k = 1; k < 1 << min_col; k++) dis[i][j][k] = INF; if (c[i][j] != -1) dis[i][j][1 << (c[i][j] - 1)] = w[i][j]; } for (int i = 1; i < 1 << min_col; i++) { for (int x = 1; x <= n; x++) for (int y = 1; y <= m; y++) if (c[x][y] != -1) { if (!(i & (1 << (c[x][y] - 1)))) continue; for (int j = (i - 1) & i; j; j = (j - 1) & i) if (dis[x][y][j] != INF && j & (1 << (c[x][y] - 1))) { int tmp = dis[x][y][j] + dis[x][y][(i ^ j) | (1 << (c[x][y] - 1))] - w[x][y]; dis[x][y][i] = min(dis[x][y][i], tmp); } } Spfa(i); for (int x = 1; x <= n; x++) for (int y = 1; y <= m; y++) if (dis[x][y][i] > ans) dis[x][y][i] = INF; else for (int j = (i - 1) & i; j; j = (j - 1) & i) dis[x][y][j] = min(dis[x][y][j], dis[x][y][i]); } for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) ans = min(ans, dis[i][j][(1 << min_col) - 1]); return ; } void solve() { int sorted_a[N * N]; int cnt = 0; scanf("%d%d%d", &n, &m, &min_col); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d", &col[i][j]); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { scanf("%d", &a[i][j]); sorted_a[++cnt] = a[i][j]; } sort(&sorted_a[1], &sorted_a[cnt + 1]); int l = 1, r = cnt, min_cnt = INF, min_med = INF; while (l <= r) { ans = INF; int mid = (l + r) >> 1; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) w[i][j] = a[i][j] > sorted_a[mid] ? 1000 + 1 : 1000 - 1; for (int t = 1; t <= 200; t++) { for (int j = 1; j <= n * m; j++) rand_c[j] = rand() % min_col + 1; for (int x = 1; x <= n; x++) for (int y = 1; y <= m; y++) { if (col[x][y] == -1) c[x][y] = -1; else c[x][y] = rand_c[col[x][y]]; } //printf("%d ", ans); Steiner(); } if (ans == INF) { printf("-1 -1 "); return ; } min_cnt = (ans + 500) / 1000; if (ans <= min_cnt * 1000) { min_med = sorted_a[mid]; r = mid - 1; } else l = mid + 1; } printf("%d %d ",min_cnt, min_med); return ; } int main(int argc, char *argv[]) { /*char input_file[20], output_file[20]; sprintf(input_file, "chocolate%d.in", atoi(argv[1])); sprintf(output_file, "chocolate%d.out", atoi(argv[1])); freopen(input_file, "r", stdin); freopen(output_file, "w", stdout);*/ srand(time(0)); int test_case; scanf("%d", &test_case); for (int i = 1; i <= test_case; i++) solve(); return 0; }
T2 dls
询问 $[L,R]$ 中的数有多少个子集乘积是完全平方数，空集算一个子集
$L,R leq 5 imes 10^7$
subtask : $L,R leq 1000$
sol：
列一个方程组，$(i,j)$ ，表示 $i$ 这个数中第 $j$ 个质数的次数是奇数还是偶数
完全平方数每个质因子的次数都是偶数，也就是模 2 意义下每个质因子都是 0 ，也就是有一排全是 0，也就是有一个自由元，这个自由元可以在子集里面也可以不在，所以答案就是 $2^{n-自由元个数}$
于是可以做 $L,R$ 很小的 subtask
当 $R-L$ 很大的时候有一个很扯的结论：自由元个数 $=[L,R]$ 中质数个数，题解 ppt 也没看懂，于是正解就是 $R-L$ 小的时候消元，大的时候结论，我没推出来结论，镘推出来了，但镘没消元，所以我 50 他 10 （
#include <bits/stdc++.h> typedef std::bitset<500> array; const int p = 998244353; const int N = 10000010; int pt, primeid[N], n, k, size, prime[N], factor[N]; char vis[N]; array a[500], now, pre; int power2(int k) { int t = 2, f = 1; for (; k; k >>= 1, t = 1ll * t * t % p) if (k & 1) f = 1ll * f * t % p; return f; } struct D { int x, y; friend bool operator<(const D &a, const D &b) { return a.y < b.y; } } max_fac[N]; int getfac(int i, array &now) { int flag = 0; now.reset(); while (factor[i] > k) i /= factor[i]; for (int j, cnt, tmp; i > 1; i = tmp) { j = factor[i], tmp = i, cnt = 0; while (tmp % j == 0)tmp /= j, cnt++; if (cnt & 1) { now[primeid[j]] = 1; flag = 1; } } return flag; } int add(array &now) { for (int i = 0; i < size; ++i) if (now[i]) if (a[i][i]) now ^= a[i]; else { a[i] = now; return 1; } return 0; } void solve(int L, int R) { //TODO: L==1 int cnt = 0, tot = 0, tot2 = 0; for (int i = std::max(2, L); i <= R; ++i) max_fac[++cnt] = (D) { i, factor[i] }; std::sort(max_fac + 1, max_fac + 1 + cnt); for (int i = 0; i < size; ++i)a[i].reset(); for (int i = 1; i <= cnt; ++i) if (max_fac[i].y <= k) { if (tot < size) if (getfac(max_fac[i].x, now)) tot += add(now); } else if (max_fac[i].y != max_fac[i - 1].y) { tot2++; if (tot < size) getfac(max_fac[i].x, pre); } else { if (tot < size) { getfac(max_fac[i].x, now); now ^= pre; tot += add(now); } } printf("%d ", power2(R - L + 1 - tot - tot2)); } void solve2(int L,int R) { int ans=0; for (int i = 2; i <= R; ++i) if(factor[i]==i && (L - 1) / i < R / i) ans++; printf("%d ",power2(R - L + 1 - ans)); } int T, L[110], R[110]; int main(int argc, char const *argv[]) { scanf("%d", &T); for (int i = 1; i <= T; ++i) { scanf("%d%d", &L[i], &R[i]); if (n < R[i])n = R[i]; } k = sqrt(n) + 1; factor[1] = 1; for (int i = 2; i <= n; i++) { if (!vis[i]) { prime[pt] = i; primeid[i] = pt++; factor[i] = i; if (i <= k)size++; } for (int j = 0; j < pt && i * prime[j] <= n; j++) { vis[i * prime[j]] = 1; factor[i * prime[j]] = std::max(factor[i], prime[j]); if (i % prime[j] == 0)break; } // printf("%d: %d ", i, factor[i]); } for (int i = 1; i <= T; ++i) if(R[i] - L[i] < 6000) solve(L[i], R[i]); else solve2(L[i],R[i]); return 0; }
T3 seat
有 $n$ 个桌子，每个桌子有 $m$ 个位置，现在第 $i$ 张桌子的第 $j$ 个人想要坐到 $L_{(i,j)}$ 到 $R_{(i,j)}$ 的一张桌子上，从第 $a$ 个桌子的 $b$ 位置走到第 $c$ 个桌子的 $d$ 位置需要花
$$|c-a| imes 2 + min(|d-b|,m-|d-b|)$$ 的体力，求完成交换的最小体力
$n leq 400,m leq 10$
保证 $L,R$ 随机生成
sol：
考场上打了个暴力费用流
正解就是线段树优化一下，虽然没看懂
#include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <queue> #include <assert.h> using namespace std; template<typename T, T INF, int MAXN, int MAXM> struct MaxFlowMinCost { int s, t, n; int head[MAXN], head2[MAXN], next[MAXM*2], to[MAXM*2], c[MAXM*2], op; T w[MAXM*2]; T dis[MAXN]; int used[MAXN], way[MAXN], stop; T ans; int maxflow; void init(int s, int t, int n) { this->s = s; this->t = t; this->n = n; memset(head, 0, sizeof(head)); op = 1; stop = 0; } void build(int u, int v, int c, T w) { next[++op] = head[u]; head[u] = op; to[op] = v; this->w[op] = w; this->c[op] = c; next[++op] = head[v]; head[v] = op; to[op] = u; this->w[op] = -w; this->c[op] = 0; assert(op < MAXM*2); } bool spfa() { memset(used, 0, sizeof(used)); memset(dis, 0, sizeof(dis)); dis[t] = INF; queue<int> que; que.push(t); while(!que.empty()) { int u = que.front(); que.pop(); used[u] = 0; for(int pos = head[u]; pos; pos = next[pos]) { if(c[pos^1] && dis[to[pos]]<dis[u]-w[pos^1]) { dis[to[pos]] = dis[u]-w[pos^1]; if (!used[to[pos]]) { used[to[pos]] = 1; que.push(to[pos]); } } } } memcpy(head2, head, sizeof(head)); return dis[s] > 0; } bool dfs(int u, int top) { if (u == t) { int minflow = 0x7fffffff/2; for(int i = top-1; i >= 1; i --) if (minflow >= c[way[i]]) { stop = i; minflow = c[way[i]]; } maxflow += minflow; for(int i = 1; i < top; i ++) { ans += minflow*w[way[i]]; c[way[i]] -= minflow; c[way[i]^1] += minflow; } return true; } used[u] = 1; for(int&pos = head2[u]; pos; pos = next[pos]) if(c[pos] && !used[to[pos]] && dis[to[pos]] == dis[u] + w[pos]) { way[top] = pos; if (dfs(to[pos], top+1) && top != stop) { used[u] = 0; return true; } } used[u] = 0; return false; } T solve() { ans = 0; maxflow = 0; while(spfa()) { memset(used, 0, sizeof(used)); dfs(s, 1); } return ans; } }; namespace Solve { const int MAXN = 300 + 10, LOGN = 10; const int MAXM = 10 + 1; const int INF = 0x7fffffff/4; MaxFlowMinCost<int, INF, MAXN*MAXM*6, MAXN*MAXM*4+MAXN*MAXM*LOGN*2+MAXN*MAXM*6> flow; int n, m; int L[MAXN][MAXM], R[MAXN][MAXM]; int L2RIndex[MAXN][MAXN][MAXM], R2LIndex[MAXN][MAXN][MAXM], cnt; inline int DOWN(int x, int y) { return cnt+x*m+y; } inline int TOP(int x, int y) { return n*m+DOWN(x,y); } void buildSegIndex(int l, int r) { for(int c=0;c<m;c++) { L2RIndex[l][r][c] = cnt++; R2LIndex[l][r][c] = cnt++; } if (l == r) return; int mid = (l+r)/2; buildSegIndex(l, mid); buildSegIndex(mid+1, r); } void buildSegFlow(int *fL2R, int *fR2L, int l, int r) { if (fL2R) { for(int c=0;c<m;c++) flow.build(fL2R[c], L2RIndex[l][r][c], INF, 0); } if (fR2L) { for(int c=0;c<m;c++) flow.build(fR2L[c], R2LIndex[l][r][c], INF, 0); } if (l == r) { for(int c=0;c<m;c++) { flow.build(L2RIndex[l][r][c], TOP(l, c), INF, l*2); } for(int c=0;c<m;c++) { flow.build(R2LIndex[l][r][c], TOP(l, c), INF, (n-l-1)*2); } return; } int mid = (l+r)/2; buildSegFlow(L2RIndex[l][r], R2LIndex[l][r], l, mid); buildSegFlow(L2RIndex[l][r], R2LIndex[l][r], mid+1, r); } enum EdgeType { L2R = 0, R2L = 1 }; void buildEdge(int snode, int sw, int L, int R, int l, int r, int c, EdgeType type) { if (L <= l && r <= R) { if (type == L2R) { flow.build(snode, L2RIndex[l][r][c], 1, sw); } else { flow.build(snode, R2LIndex[l][r][c], 1, sw); } return; } int mid = (l+r)/2; if (L <= mid) buildEdge(snode, sw, L, R, l, mid, c, type); if (R > mid) buildEdge(snode, sw, L, R, mid+1, r, c, type); } void solve() { scanf("%d%d", &n, &m); for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d", &L[i][j]); for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%d", &R[i][j]); cnt = 0; buildSegIndex(0, n-1); const int S = TOP(n-1, m-1)+1; const int T = S + 1; flow.init(S, T, T); buildSegFlow(NULL, NULL, 0, n-1); for(int i=0;i<n;i++) for(int j=0;j<m;j++) { flow.build(S, DOWN(i,j), 1, 0); flow.build(TOP(i,j), T, 1, 0); flow.build(TOP(i,j), TOP(i, (j+1)%m), INF, 1); flow.build(TOP(i,j), TOP(i, (j-1+m)%m), INF, 1); if (R[i][j] <= i) { buildEdge(DOWN(i, j), -(n-i-1)*2, L[i][j], R[i][j], 0, n-1, j, R2L); } else if (L[i][j] >= i) { buildEdge(DOWN(i, j), -i*2, L[i][j], R[i][j], 0, n-1, j, L2R); } else { buildEdge(DOWN(i, j), -(n-i-1)*2, L[i][j], i, 0, n-1, j, R2L); buildEdge(DOWN(i, j), -i*2, i, R[i][j], 0, n-1, j, L2R); } } int ans = flow.solve(); if (flow.maxflow != n*m) puts("no solution"); else printf("%d ", ans); } } int main() { #ifdef __TEST__ freopen("seat.in", "r", stdin); freopen("seat.out", "w", stdout); #endif Solve::solve(); return 0; }
Day2 自选题
T1 bzoj2151 tree
一个环，每个点有权值，选 m 个互不相邻的点，最大化权值和
$n,m leq 10^5$
sol：
模拟赛出板题是不是有点不厚道啊
有一个思想叫做可撤销贪心，就先贪一波，然后发现情况不对，就把前面贪心撤了选后面的，“撤”这一步也是贪心
怎么维护呢？考虑一次操作的代价
如果我们放弃选这个点，一定是把它的两边一起选，于是每选一个数 $x$ ，就把 $pre_x$ 和 $next_x$ 打上删除标记，然后把 $v[pre_x]+v[next_x] - v[x]$ 加入堆里
upd：是我 sb 。。。可能不需要知道可撤销贪心就能做
如果 $n leq 300$ 这是不是一道很裸的费用流？
然后发现增广的时候是有规律的，规律就是上面说的可撤销贪心
事实上这种题可以用所谓“可撤销贪心”做本质上是因为它是一个费用流， “撤”本质上相当于退流
感觉要被 xm 大哥 D 到死...
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<map> #include<cmath> #define inf 1000000000 #define pa pair<int,int> #define ll long long using namespace std; 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*10+ch-'0';ch=getchar();} return x*f; } int ans; int n,m,cnt; int a[200005],pre[200005],nxt[200005]; bool mark[200005]; priority_queue<pa,vector<pa> >q; void del(int x) { mark[x]=1; int l=pre[x],r=nxt[x]; nxt[x]=pre[x]=0; nxt[l]=r;pre[r]=l; } void get() { while(mark[q.top().second])q.pop(); int x=q.top().second;ans+=a[x]; q.pop(); a[x]=a[pre[x]]+a[nxt[x]]-a[x]; del(pre[x]);del(nxt[x]); q.push(make_pair(a[x],x)); } int main() { n=read();m=read(); for(int i=1;i<=n;i++)a[i]=read(); if(m>n/2){puts("Error!");return 0;} for(int i=1;i<=n;i++)pre[i]=i-1;pre[1]=n; for(int i=1;i<=n;i++)nxt[i]=i+1;nxt[n]=1; for(int i=1;i<=n;i++) q.push(make_pair(a[i],i)); for(int i=1;i<=m;i++) get(); printf("%d",ans); return 0; }
T2 singledog
一个序列，求有多少区间满足该区间众数出现了超过 $lceil frac{r-l+1}{2} ceil$ 次
$n leq 5 imes 10^5$
sol：
cp 的题就搬上来了？记得我们都看过题解啊（虽然我忘了
对每个权值记录一下前缀和，$f_v[i]$ 表示前 $i$ 项有几个 $v$ ，枚举 $v$，则一个区间有贡献当且仅当 $2 imes f_v[r] - r > 2 imes f_v[l] - l$
这样直接做是 $O(n^2logn)$ 的，考虑优化
假设我们枚举了 $v$，则当前 $v$ 将序列分成了很多段，每段的 $2 imes f_v[r] - r$ 是一个等差数列，我们要求的是等差数列前缀和
这个东西线段树就可以了，但因为我 sb 的把时限看成了 $1s$ ，线段树跑了 $1s$ 多，我就差分之后用 $3$ 个树状数组维护常数项，一次项和二次项。。。
倒不是很难写，但是很亏
#include<bits/stdc++.h> #define LL long long #define int long long using namespace std; inline int read() { int x = 0,f = 1;char ch = getchar(); for(;!isdigit(ch);ch = getchar())if(ch == '-')f = -f; for(;isdigit(ch);ch = getchar())x = 10 * x + ch - '0'; return x * f; } const int maxn = 1e6 + 50,_m = 1e6; int n,type,a[maxn],r[maxn],ToT; //vector<int> ps[maxn]; int pos[maxn],first[maxn],nx[maxn]; int cp[maxn]; inline int lowbit(int x){return x & (-x);} struct Fenwick { LL v[maxn]; inline void add(int pos,LL val){for(;pos <= _m;pos += lowbit(pos))v[pos] += val;} inline LL query(int pos){LL res = 0;for(;pos;pos -= lowbit(pos))res += v[pos];return res;} }tr1,tr2,tr3; LL ans; LL opt(int pos,LL val) { LL ta = val,tb = pos * val,tc = (pos - 1) * (pos - 2) * val; tr1.add(pos,ta); tr2.add(pos,tb); tr3.add(pos,tc); } LL check(int pos) { LL ta = tr1.query(pos),tb = tr2.query(pos),tc = tr3.query(pos); return ta * pos * (pos + 3) - tb * pos * 2 + tc; } void update(int l,int r,int v) { int len = r - l - 1; l = v - len + n + 1; r = v + n + 1; opt(l,-1);opt(r+1,1); } void query(int l,int r,int v) { int len = r - l - 1; l = v - len + n + 1; r = v + n + 1; ans += (check(r - 1) - check(l - 2)); opt(l,1); opt(r+1,-1); } signed main() { //freopen("singledog4.in","r",stdin); n = read();type = read(); for(int i=1;i<=n;i++)a[i] = r[i] = read(); sort(r + 1,r + n + 1); ToT = unique(r + 1,r + n + 1) - r - 1; for(int i=1;i<=ToT;i++)pos[r[i]] = i; for(int i=1;i<=n;i++) { a[i] = pos[a[i]]; nx[i] = first[a[i]]; first[a[i]] = i; //ps[a[i]].push_back(i); //cout<<a[i]<<" "<<i<<endl; } cp[0] = n + 1; // return 0; for(int i=1;i<=ToT;i++) { int top = 0; //reverse(ps[i].begin(),ps[i].end()); //for(int j=0;j<ps[i].size();j++)cp[++top] = ps[i][j]; for(int j=first[i];j;j=nx[j])cp[++top] = j; cp[top + 1] = 0; //reverse(cp + 1,cp + top + 1); //for(int j=1;j<=top;j++)cout<<cp[j]; //cout<<endl; for(int j=top+1;j;j--)query(cp[j],cp[j-1],(top-j+1)*2-cp[j]); for(int j=top+1;j;j--)update(cp[j],cp[j-1],(top-j+1)*2-cp[j]); } ans >>= 1; cout<<ans<<endl; }
T3 不知道在哪，先咕