widsnoy's blog

题目

桌面上有\(N\)个数字排成一排，小武要求小林从中选出\(3\)个数字，使得这\(3\)个数字的按位或的结果恰好等于\(x\)，小林很快 就解决了这个问题，小武想了想，决定把问题加强一下，小武会问小林\(Q\)次问题，每次选的\(3\)个数字只能在从左往右 的第\(l\)个数和第\(r\)个数之间选择，并且要小林说出符合要求的方案数，小林顿时不会了，于是把问题交给了你。 第一行两个数\(N\)和\(Q\), 第二行\(N\)个数，按照从左到右的顺序给出桌面上的数字 接下来\(Q\)行，每行\(3\)个数字，分别为\(l,r,x\ Q\)行，每行一个数表示方案数。

分析

首先，如果\(x\)某位等于\(0\)。那么选出的数该为只能等于\(0\)。

排除这种情况，选出的数一定是\(x\)的子集，即\(i\and x=i\)

而没有顺序的选出三个数方案是\(\binom{n}{3}\)

选出的三个数一定属于某个集合，我们直接枚举这个集合\(S\)，\(S\)一定是\(x\)的子集，不然没有意义。如果\(S\)和\(x\)一的个数不同，一定是\(S\)为\(0\)，\(x\)是\(1\)。所以要把\(S\)的所有选择方案减去。但是某个三元组可能被反复减，如果\(1\)的个数差偶数个时又要加上去。

为什么这样是对的？

假如当前有一个三元组或起来等于\(10001101\)，而\(x=10111111\)

我们考虑这个三元组的贡献，也就是在哪些集合会枚举到它。

「NOIP2017」宝藏

不知道为什么，最开始\(70\)的暴力都没有想到。

因为当前在某个最新开发的点，不会再往以前已经开发的点连边。

所以开发顺序是一个排列，所以直接全排列枚举开发顺序。

每个新开发的点，都枚举是从哪个已开发的点过来的，这样做应该是\(\mathjaxcal{O}(n^3n!)\)的，可以拿\(70\)分。

然后这题有一个根据定义的状压\(dp\)，可以把开发顺序看成一棵\(bfs\)树，是一层一层开发的。

设\(f[i][s1][s2]\)表示已经开了前\(i\)层，开发的点集是\(s1\)，最后一层是\(s2\)，枚举\(s1\)补集的子集接上即可。

不知道为什么我写了这个\(\mathjaxcal{O}(n^24^n)\)的\(dp\)没过样例。

可以优化下状态，可以发现不用管第三维，因为最优状态总会被考虑到，只用记录\(g[i][j]\)表示两个集合连边的最小边权和。

转移的时候\(g[i][j]=g[i][j\and -j]+v\)

「HAOI2016」放棋子

这题，一看就很状压\(dp\) 但是\(N\leq 200\)，拿啥压啊...

不会做啊，忍不住去搜题解了。

题目有个很好的性质

任意两个障碍不在同一行，任意两个障碍不在同一列......你放\(N\)个棋子也满足每行只有一枚棋子，每列只有一枚棋子的限制

首先，既然每行每列都只有一个障碍，那么显然障碍放哪里对棋子方案数没有影响。

你想在某行换一个障碍位置，那么必定会把另一个障碍换到这一列。这就相当于换了某两行。

因为棋子也满足这个限制，所以换两行是没有影响的。

所以我们直接钦定第\(i\)行的障碍物就在第\(i\)列，因为要放\(N\)个棋子，每一行都要放一个，给放在\(i\)行的棋子编号为\(i\)。

所以编号为\(i\)的棋子不能放在第\(i\)列。

首先，把所有数二进制拆分一下，然后数位\(dp\)爆搜当前位分别填什么，然后这题就做完了。

做完个锤子。

如果填\(0/1\)，\(1/0\)，\(0/0\)，最后并起来都是一个数，但是\(x,y\)却不相同了。

据可靠消息，发现这三种填法的方案数是包含关系，也就是说你在这一位填什么，最后都不会让某个方案不同于其中一个能最大化答案的那个方案。

因为当前填什么对后面的影响就是会不会碰到上下界，调整一下可以证。

具体可以看看其他大佬的博客。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 99;
ll f[N][2][2][2][2];
int t[N], a[N], b[N], c[N], d[N], mx;
int dx[4] = {1, 0, 0, 1};
int dy[4] = {0, 1, 0, 1};

ll read() {
	ll w = 0;
	char ch = getchar();
    while (ch > '9' || ch < '0') ch = getchar();
    while (ch >= '0' && ch <= '9') {
    	w = w * 10 + ch - 48;
    	ch = getchar();
    }
    return w;
}
void work(int *a, ll x) {
	int cnt = 0;
	while (x) a[++cnt] = x % 2, x /= 2;
	if (cnt > mx) mx = cnt;
}
ll dfs(int x, bool lx, bool rx, bool ly, bool ry) {
    if (x == 0) return 1;
    if (f[x][lx][rx][ly][ry] != -1) return f[x][lx][rx][ly][ry];
    ll &res = f[x][lx][rx][ly][ry], ans;
    res = 0;
    for (int i = 0; i < 4; i++) {
    	int nx = dx[i], ny = dy[i];
    	if ((nx | ny) != t[x]) continue;
    	if (lx && nx < a[x]) continue;
    	if (rx && nx > b[x]) continue;
    	if (ly && ny < c[x]) continue;
    	if (ry && ny > d[x]) continue;
    	if (nx & ny) res += dfs(x - 1, lx && a[x] == nx, rx && b[x] == nx, ly && c[x] == ny, ry && d[x] == ny);
    	else res = max(ans, dfs(x - 1, lx && a[x] == nx, rx && b[x] == nx, ly && c[x] == ny, ry && d[x] == ny));
    }
    return res;
}

int main() {
    memset(f, -1, sizeof f);
    work(t, read());
    work(a, read());
    work(b, read());
    work(c, read());
    work(d, read());
    printf("%lld\n", dfs(mx, 1, 1, 1, 1));
    return 0;
}

「NOIP2017」 逛公园

题目

策策同学特别喜欢逛公园。公园可以看成一张\(N\)个点\(M\)条边构成的有向图，且没有自环和重边。其中1号点是公园的入口，\(N\)号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。 策策每天都会去逛公园，他总是从1号点进去，从\(N\)号点出来。

策策喜欢新鲜的事物，他不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，他不希望每天在逛公园这件事上花费太多的时间。如果1号点到\(N\)号点的最短路长为\(d\)，那么策策只会喜欢长度不超过\(d+k\)的路线。策策同学想知道总共有多少条满足条件的路线，你能帮帮他吗？为避免输出过大，答案对\(P\)取模。如果有无穷多条合法的路线，请输出-1。

分析

首先需要最短路处理出\(1\)和\(n\)作为起点到每个点的最短路。

有无数解的情况是有零环并且走零环能满足长度不大于\(d+k\)的条件。

\(k\)的范围应该很\(dp\)，就是\(f[i][k]\)表示走到\(i\)点，相对最短路多走了\(k\)的方案数。

而零环和最短路图上的边转移时成环的，需要按照拓扑序来转移。

代码

退役选手114514分钟没写博客了

题目

L 国有 \(n\) 个星球，有 \(n-1\) 条双向航道连通了 L 国的所有星球，每条航道连通两个星球，第 \(i\) 条航道通过的时间为 \(t-i\)。

小 P 掌管的物流公司有 \(m\) 个运输计划，每个运输计划形如：有一艘物流飞船需要从 \(u-i\) 号星球沿最快的路径到 \(v-i\) 号星球去。注意：任意两艘飞船之间不会产生任何干扰。

在运输计划开始前，小 P 可以自由选择一条航道改造成虫洞，飞船驶过虫洞不消耗时间。在虫洞建设完成后，这 \(m\) 个运输计划会同时开始，所有飞船一起出发。当这 \(m\) 个运输计划都完成时，小 P 的物流公司的阶段性工作就完成了。求出小 P 的物流公司完成阶段性工作所需要的最短时间。

数据范围：\(n,m\le 3\times 10^5\)，\(0\le t-i\le 1000\)

分析

一开始没注意到是一棵树，感觉很不可做。

看了下别人题解，才发现这个性质。

所以可以先预处理出每个任务的长度。

马上联赛了，把陈年老题改一下，试图找点自信?

感觉沈睿出的题还是很有技术含量的，只是我不会做就是了。

比赛地址

A 串

感觉直接大力讨论就可以了，因为情况不是很多。

可能是太懒了，这题都不会。

B 数

好像洛谷月赛有一道类似的题。

把数重小到大排序，然后\(f[i]\)表示前\(i\)个数能凑出的最大的数。

即\(f[i]+1\)不能被凑出。

「SCOI2012」滑雪与时间胶囊

因为只能从更高的点到不高于它的点。

我们给边定向后(虽然有些边还是无向的)，看一下从\(1\)能到哪些点就。

第二问，因为有些边是有向的，为了走完所有点，一点要从更高的点开始走。

如果形成了树的结构，显然是可以走完所有点的。

但是为了保证从高点走到低点，我们需要指向更高点的边被优先选出。

不然有可能没有走向它的边，肯定是不对的。

话说这图好像可以叉掉\(prime\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e6 + 6;
struct node {
	int nxt, v, w;
} e[N << 1];
struct Edge {
	int u, v, w;
} E[N << 1];
int n, m, h[N], head[N], ecnt, cnt, tot, fa[N];

int find(int x) {return fa[x] ? fa[x] = find(fa[x]) : x;}
void add-edge(int u, int v, int w) {
    e[++ecnt] = {head[u], v, w}; head[u] = ecnt;
    e[++ecnt] = {head[v], u, w}; head[v] = ecnt;
}

bool vis[N];
void dfs(int u) {
	if (vis[u]) return;
	tot++;
	vis[u] = 1;
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v, w = e[i].w;
		if (h[u] < h[v]) continue;
        E[++cnt] = {u, v, w};
		dfs(v);
	}
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= m; i++) {
    	int u, v , w;
    	cin >> u >> v >> w;
    	add-edge(u, v, w);
    }
    dfs(1);
    sort(E + 1, E + cnt + 1, [&](Edge a, Edge b) {return (h[a.v] == h[b.v]) ? a.w < b.w : h[a.v] > h[b.v];});
    int c = 0, w = 0;
    for (int i = 1; i <= cnt; i++) {
        int u = find(E[i].u), v = find(E[i].v);
        if (u == v) continue;
        c++;
        w += E[i].w;
        fa[u] = v;
        if (c == n - 1) break;
    }
    cout << tot << " " << w << endl;
    return 0;
}

DFS 序 3，树上差分 1

给一棵有根树，这棵树由编号为\(1...N\)的 \(N\)个结点组成。根结点的编号为\(R\) 。每个结点都有一个权值，结点\(i\) 的权值为\(V-i\) 。 接下来有\(M\)组操作，操作分为三类：

• 1 a b x，表示将「结点\(a\)到结点\(b\)的简单路径」上所有结点的权值都增加\(x\) ；
• 2 a，表示求结点\(a\) 的权值。
• 3 a，表示求 \(a\)的子树上所有结点的权值之和。

上来就写了树剖，交上去\(TLE\)了一个点。

诶，我被卡常数了？

卡常数卡到怀疑人生，点开最优解，树上差分啊，那没事了。

分析

先说前两个操作，考虑更改的链两个端点\(u,v\)祖先关系的情况。

把\(v\)增加\(x\)，\(fa[u]\)减去\(x\)即可。单点查询时查询该点的子树差分数组和。

更一般的情况是，\(u\)，\(v\)增加\(x\)，\(lca\)和\(fa[lca]\)减去\(x\)。

意会一下这样修改显然是对的。

贴一下对拍的脚本

bash

1
2
3
4
5
6
7
8
9
10
11

while true; do
    ./make > data.in
    ./a < data.in > a.out
    ./b < data.in > b.out
    if diff a.out b.out; then 
        printf "Accept\n"
    else
        printf "Wrong answer\n"
        exit 0
    fi 
done

bat

参考自这里

1
2
3
4
5
6
7
8
9

@echo off  
:loop  
    make.exe %random% > data.in
    a.exe < data.in > a.out
    b.exe < data.in > b.out
    fc a.out b.out 
if not errorlevel 1 goto loop  
pause
goto loop

首先@echo off 是关掉输入显示，不然你的所有命令都会显示出来的，防止刷屏。 ：loop是定位标记点，和c语言里的goto很像。 中间是主体程序。 if not errorlevel 1 goto loop ，errorlevel 是上一个命令的返回值，fc在文件不同时返回1，相同时返回\(0\)，这一行的意思就是，如果fc返回的不是\(1\)，就跳到:loop，使劲循环。 pause，暂停，一旦fc返回\(1\)，就会执行到这一行，停住程序，给你时间看数据。 goto loop，看完数据，按下任意键结束暂停，继续循环。

\(\text{windows}\)下可以用系统的随机数种子，这样生成数据更快些，不知道\(\text{linux}\)上有没有类似的东西。

写数据生成程序时这样：

1
2
3
4
5
6
7
8
9
10

stringstream ss;
int main(int argc, char *argv[]) {
    int seed;
    if (argc > 1) {
        ss.clear();
        ss << argv[1];
        ss >> seed;
    }
    srand(seed);
}