Training for Graph Theory

Posted by JHSN on May 31, 2017

2017 UESTC 图论专题题解



题目链接：2017 UESTC Training for Graph Theory

Content

[CDOJ 1636] A - 梦后楼台高锁，酒醒帘幕低垂
[CDOJ 1633] B - 去年春恨却来时，落花人独立，微雨燕双飞
[CDOJ 1634] C - 记得小苹初见，两重心字罗衣
[CDOJ 1635] D - 琵琶弦上说相思，当时明月在，曾照彩云归
[CDOJ 1638] E - 红藕香残玉簟秋，轻解罗裳，独上兰舟。
[CDOJ 1639] F - 云中谁寄锦书来？雁字回时，月满西楼。
[CDOJ 1640] G - 花自飘零水自流，一种相思，两处闲愁。
[CDOJ 1641] H - 此情无计可消除，才下眉头，却上心头。
[CDOJ 1642] I - 老当益壮， 宁移白首之心？
[CDOJ 1646] J - 穷且益坚， 不坠青云之志。
[CDOJ 1647] K - 酌贪泉而觉爽， 处涸辙以犹欢。



[CDOJ 1636] A - 梦后楼台高锁，酒醒帘幕低垂

Problem

给一个带正边权的无向图，路径的权值为路径上所有边的最大值与最小值之差，问从 1 到 n 的所有路径的最小权值。
1≤n≤200, n−1≤m≤1000, 1≤u,v≤n, 1≤w≤1000000

Solution

想到二分答案，那如果要判断某个答案值可不可行，需要从某条边开始，按边权从小到大依次将比它大的边加入图中，直至 1 和 n 联通或者边权差值超出答案。
那好像不需要二分答案了，直接枚举最小边，寻找可使 1 和 n 联通的最小的最大边就行了，并查集维护。
复杂度 O(mlgm + m^2)

Code

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

struct re {
    int x, y, z;
} a[1010];
inline bool cmp(re a, re b) {return a.z < b.z;}
int i, n, m, j, res, nn, ans, p, q;
int f[210];

int find(int x) {
    if (f[x] == x) return x;
    f[x] = find(f[x]);
    return f[x];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (i = 1; i <= m; i++)
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
    sort(a + 1, a + m + 1, cmp);
    ans = 1000000000;
    for (i = 1; i <= m; i++)
    {
        for (j = 1; j <= n; j++) f[j] = j;
        nn = n - 1;
        res = 1000000000;
        for (j = i; j <= m; j++)
        {
            p = find(a[j].x); q = find(a[j].y);
            if (p == q) continue;
            f[q] = p;
            p = find(1); q = find(n);
            if (p == q)
            {
                res = a[j].z - a[i].z;
                break;
            }
        }
        ans = min(ans, res);
    }
    if (ans == 1000000000) puts("-1");
            else printf("%d\n", ans);
    return 0;
}

Note

[HDU 1598]find the most comfortable road

[CDOJ 1633] B - 去年春恨却来时，落花人独立，微雨燕双飞

Problem

给你一个大小为 n(1≤n≤2000) 的集合 S，集合里有 n 个互不相同正整数 (1≤ai≤50000) 。有 q(1≤q≤10000) 个询问，每次询问是否能选择 S 中的一些数字（同一个数字可以选择多次，也可以任何数字都不选），使它们相加的和为 m(0≤m≤1000000000) 。

Solution

把最小的 ai 挑出来作为模数 r，以 r 建立剩余系，这样就只要找出模 r 为 x 的最小的数是多少（把这个设为 d[x]），那么如果有 ai 的话，那么就可以做 y = (x + ai) % r; d[y] = min(d[y], d[x] + ai) 这样的更新操作，这样其实就是一个最短路模型，共 r 个点，有 n * r 条边。跑一下最短路就行。。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int MAX=1e9+10;
const int R=5010;
int d[R];
bool g[R];
int a[20100];
int i, k, r, Q, j, y, n;

priority_queue <pair<int, int>> q;
void dij(int x)
{
	int tot=0, mi, i;
	q.push(make_pair(-d[x], x));
	while (tot < r && !q.empty())
	{
		mi = q.top().second;
		q.pop();
		if (g[mi]) continue;
		g[mi] = 1;
		tot++;
		for (i = 1; i <= n; i++)
		{
		    y = (mi + a[i]) % r;
			if (!g[y] && d[y] - d[mi] > a[i])
			{
				d[y] = d[mi] + a[i];
				q.push(make_pair(-d[y], y));
			}
		}
	}
	return;
}

int main()
{
    scanf("%d", &n);
    for (i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    r = a[1];
    for (i = 1; i <= r; i++) d[i] = MAX;
    d[r] = 0;
    dij(r);
    
    scanf("%d", &Q);
    while (Q--)
    {
        scanf("%d", &k);
        puts( (k >= d[k % r]) ? "YES" : "NO" );
    }
    return 0;
}

Note

非常智障，想到了要用剩余做，却想不到怎么往图论上靠。。



[CDOJ 1634] C - 记得小苹初见，两重心字罗衣

Problem

平面上有 n 个点，将每个点染成红色或者蓝色，使得每一行和每一列的红点蓝点之差不超过 1。
n≤200000, 1≤x,y≤200000

Solution

因为要将每条横线和竖线上的点尽可能均分成两类。
所以考虑染色，构造连边然后红蓝交替着染路径上的点。
从最终的结果来推想，一条横线上的点的红蓝差 <= 1，那么这条横线上一定可以让红蓝点两两配对，然后连边，而且最后横线上最多多出来一个点。（竖线也是相同的道理）
那么就按顺序染一下试试看？
对于每一条横线，从左到右，按顺序选取未选择的两点，连一条边。
对于每一条竖线，从上到下，按顺序选取未选择的两点，连一条边。

例如：
O   O
       O

  O       O
      
    O  

O   O  O

    O  O

连边后：
O---O
|   |  O
|   |  |
| O-------O  （注意这里并不交叉）
|   |  |
|   O  |
|      |
O---O  O
    |
    O--O

这样的连线方案，一定可以保证最终平面上有一堆链（可能还有孤立的点），因为每个点只能在纵向或者横向两个方向连边，而且在竖直方向上最多只能连出去一条边，横向最多也只能连出去一条边，不可能出现 “+” 或者 “┬” 这种样子的点。
因为对于链，红蓝交替染色必然可行，对于孤立点随便染（注意孤立点在每条横线或者竖线上最多有一个），这样染完后，每条横线或者竖线上红蓝差必然是 <= 1 的，所以这样的染色方案是可行的。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=200010;
const int M=N<<2;
struct re {
    int x, y, z;
} a[N];

int i, tot, n;
int st[N];
int nex[M], v[M];
bool g[N], f[N];

void add(int x, int y)
{
    v[++tot] = y;
    nex[tot] = st[x];
    st[x] = tot; 
}

bool cmp(re a, re b) {return a.x < b.x || (a.x == b.x && a.y < b.y);}

void connect()
{
    sort(a + 1, a + n + 1, cmp);
    int x=1, y, j;
    while (x < n)
    {
        y = x;
        while (a[y + 1].x == a[y].x) y++;
        for (j = x + 1; j <= y; j += 2)
        {
            add(a[j - 1].z, a[j].z);
            add(a[j].z, a[j - 1].z);
        }
        x = y + 1;
    }
}

void color(int x, int w)
{
    f[x] = w;
    g[x] = 1;
    for (int i = st[x]; i; i = nex[i])
        if (!g[v[i]]) color(v[i], w ^ 1);
}

int main()
{
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
    {
        scanf("%d%d", &a[i].x, &a[i].y);
        a[i].z = i;
    }
    
    a[n + 1].x = a[n + 1].y = a[n + 1].z = -1;
    connect();
    for (i = 1; i <= n; i++) swap(a[i].x, a[i].y);
    connect();
    
    for (i = 1; i <= n; i++)
    {
        if (!g[i]) color(i, 1);
        putchar(f[i] ? 'b' : 'r');
    }
    puts("");
    return 0;
}

Note

[Codeforces 547D]Mike and Fish



[CDOJ 1635] D - 琵琶弦上说相思，当时明月在，曾照彩云归

Problem

给你 n 个仅由小写字母组成的字符串，请你找出一种字典序，使得这 n 个字符串在这种字典序下是从小到大排列的
1≤n≤1000, 1≤len(s)≤200

Solution

对于所有的字符串，可以对相邻的字符串进行逐位比较，得出字符间的大小关系，由此应该能得到一张拓扑关系图，如果图存在环，则输出 -1。否则的话，因为字符比较少，所以我直接 dfs 求出所有字母间的先后关系，然后直接从 a 到 z 暴力枚举答案。
有种特殊情况是两个字符串，后者是前者的前缀而且前者比后者长，这种情况一定是不合法的，输出 -1，被坑了很久的一种情况。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;

const int N=40;
const int M=200010;
char s[2][210];
bool g[N], cx[N][N], flag;
int a[100];
int st[N], nex[M], b[M];
int i, n, x, y, j, k, tot, len;

void add(int x, int y)
{
    x -= 96; y -= 96;
    cx[x][y] = 1;
    b[++tot] = y;
    nex[tot] = st[x];
    st[x] = tot;
}

void dfs(int x)
{
    g[x] = 1;
    for (int i = st[x]; i; i = nex[i])
        if (!g[b[i]])
        {
            dfs(b[i]);
            for (int j = 1; j <= 26; j++)
                if (cx[b[i]][j]) cx[x][j] = 1;
        }
}

int main()
{
    scanf("%d", &n);
    scanf("%s", &s[0]);
    for (i = 2; i <= n; i++)
    {
        x = i & 1;
        y = x ^ 1;
        scanf("%s", &s[y]);
        len = min(strlen(s[x]), strlen(s[y]));
        for (j = 0; j < len; j++)
            if (s[x][j] != s[y][j])
            	{ add(s[x][j], s[y][j]); break; }
        if (j == len && strlen(s[x]) > strlen(s[y]))
        	{ puts("-1"); return 0; }
    }
    for (i = 1; i <= 26; i++)
        if (!g[i]) dfs(i);
    for (i = 1; i <= 26; i++)
        for (j = 1; j <= 26; j++)
            if (cx[i][j] && cx[j][i])
            {
                puts("-1");
                return 0;
            }
    
    memset(g, 0, sizeof(g));
    for (i = 1; i <= 26; i++)
    {
        for (j = 1; j <= 26; j++)
            if (!g[j])
            {
                flag = true;
                for (k = 1; k <= 26; k++)
                    if (!g[k] && cx[k][j])
						{ flag = 0; break; }
                if (flag)
                {
                    g[j] = 1;
                    a[i] = j;
                    break;
                }
            }
        if (flag == false)
        	{ puts("-1"); return 0; }
    }
    
    for (i = 1; i <= 26; i++) putchar(a[i] + 96);
    puts("");
    return 0;
}

Note

[POJ 1364]King



[CDOJ 1638] E - 红藕香残玉簟秋，轻解罗裳，独上兰舟。

Problem

n(1≤n≤100000) 个学生，m(1≤m≤100000) 条信息 (u, v, w)，表示 score[v] + w <= score[u] (0≤w≤100)，求 score[i] | i=1..n 可能的最大值和最小值

Solution

差分约束系统
根据不等式 score[v] + w <= score[u] 建图，同时设置一个超级源作为最小值，根据 min - score[x] <= 0 不等式将所有点连接起来，那么只要从这个超级源出发，做一遍 spfa 就能求出下限了
然后将不等式移项 score[u] - w >= score[v]，再次建图（相当于上张图反向），然后设置一个超级源作为最大值，连接所有点，然后做 spfa 可求出上限
因为这道题点数比较多，所以在 spfa 中通过入队列的次数来判负环会 TLE
所以我事先 dfs 判断了是否存在负环，因为还可能存在零环，所以在 dfs 的时候还加了一个深度标记，如果搜索到了一个仍还在栈中且深度不一样的点，则说明存在负环

Code

#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
using namespace std;

const int N=110000;
const int M=2000100;
const int INF=0x3fffffff+100;
int n, m, tot;
int d1[N];//, cnt[N];
int d2[N];
int deep[N];
bool inq[N], ins[N];
int st[N], v[M], nex[M], w[M];
int a[M>>1], b[M>>1], c[M>>1];

void no()
{
    puts("-1");
    exit(0);
}
void init()
{
    tot = 0;
    memset(st, -1, (n + 5) * sizeof(st[0]));
}
void add(int x, int y, int z)
{
    v[tot] = y;
    w[tot] = z;
    nex[tot] = st[x];
    st[x] = tot++;
}

void dfs(int x, int dee)
{
    inq[x] = ins[x] = 1;
    deep[x] = dee;
    for(int i = st[x]; i != -1; i = nex[i])
    {
        if (ins[v[i]] && dee != deep[v[i]]) no();
        if (!inq[v[i]]) dfs(v[i], dee + w[i]);
    }
    ins[x] = 0;
}
void circle()
{
    memset(inq, 0, (n + 5) * sizeof(inq[0]));
    memset(ins, 0, (n + 5) * sizeof(ins[0]));
    dfs(n + 1, 0);
}

void spfa(int* dd, int initial)
{
    queue<int> q;
    int a, b;
    memset(inq, 0, (n + 5) * sizeof(inq[0]));
    //memset(cnt, 0, (n + 5) * sizeof(cnt[0]));
    for(int i = 0; i <= n; i++) dd[i] = INF;
    dd[n + 1] = initial;
    inq[n + 1] = 1;
    q.push(n + 1);
    //cnt[n + 1]++;
    while (!q.empty())
    {
        a = q.front(); q.pop();
        //if (cnt[a] > n + 1) no();
        inq[a] = 0;
        for(int i = st[a]; i != -1; i = nex[i])
        {
            b = v[i];
            if(dd[b] > dd[a] + w[i])
            {
                dd[b] = dd[a] + w[i];
                if(inq[b] == 0)
                {
                    inq[b] = 1;
                    q.push(b);
                    //cnt[b]++;
                }
            }
        }
    }
}

int main()
{
    int i;
    scanf("%d%d", &n, &m);
    
    init();
    for (i = 1; i <= n; i++) add(n + 1, i, 0);  // max - i >= 0
    for (i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &a[i], &b[i], &c[i]);
        if (a[i] == b[i])
        {
             if (c[i] != 0) no();
                    else continue;
        }
        // a[i] - b[i] >= c[i]
        // a[i] - c[i] >= b[i]
        add(a[i], b[i], -c[i]);
    }
    circle();
    spfa(d1, 100);
    
    
    init();
    for (i = 1; i <= n; i++) add(n + 1, i, 0);  // min - i <= 0
    for (i = 1; i <= m; i++)
    {
        if (a[i] == b[i])
        {
             if (c[i] != 0) no();
                    else continue;
        }
        // b[i] - a[i] <= -c[i]
        // b[i] + c[i] <= a[i]
        // (-b[i]) - c[i] >= (-a[i]) 化为最短路 
        add(b[i], a[i], -c[i]);
    }
    circle();
    spfa(d2, 0);
    
    for (i = 1; i <= n; i++)
    {
        d2[i] = -d2[i];
        if (d1[i] < 0 || d1[i] > 100 || d2[i] < 0 || d2[i] > 100) no();
    }
    for (i = 1; i <= n; i++)
        printf("%d %d\n", d2[i], d1[i]);
    return 0;
}



[CDOJ 1639] F - 云中谁寄锦书来？雁字回时，月满西楼。

Problem

n 个点 m 条边的无向图，节点编号为 0 到 n−1，有 k 个点为安全屋
劫犯们从 0 出发，要到其中一个安全屋（任意一个）
每当劫犯到达一个节点，警察立刻封锁与该点相连的边，对于当前点警察最多能够封锁与其相连的 d 条边
求在最坏情况下，劫犯能到达安全屋的最短时间
1≤n≤100000，1≤m≤1000000，0≤k≤n，0≤d≤m，0≤u,v<n，0≤w≤10000

Solution

看了题解写的，是 dijkstra 的改版
感觉题解已经讲得非常清楚了，题解原文：

该题为dijkstra算法的拓展

由于求最坏情况下的最短路，对于每个点，显然最优的前d条边不能走

对于边u->v，必然要先得到v到出口的最坏情况下的最短路
才能得到u经过该边再到出口的最坏情况下的最短路，也就是该边对于u的价值
所以要从出口往回考虑

令f[i]表示i到出口的最坏情况下的最短路
同dijkstra算法一样，每个点i可以分为f[i]已确定的和f[i]未确定的
初始时自然是对于每个出口x，f[x]=0已确定

对于f[v]已确定的点v，将边权为w的边u->v以f[v]+w为关键字加入小根堆中

对于每个点i还要记录cnt[i]=k，表示到i后，i连出的最优的前k条边已被封锁

每次取出堆顶对应的边u->v（若f[u]已确定直接弹出）
则该边为u连出的（除已被封锁的边外）最优的边
若cnt[u]<d，该边必然会被封锁，那么将cnt[u]加1，弹出堆顶
若cnt[u]=d，那么可以确定f[u]=f[v]+w，再用u更新连向u的边，弹出堆顶

重复这一过程直到确定f[0]的值，该值即为答案

这里的堆通过边来维护最近的点，每次松弛都是挑选当前最近的点，也就是对于每一个点，去松弛它的距离一定是从小到大的，小的先松弛，大的后松弛，这样就能挑出最优的 k 种情况封锁掉。

Code

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=100020;
const int M=1000020<<1;
priority_queue<pair<int, int>> q;

int v[M], w[M], nex[M];
int st[N], d[N], cnt[N];
int tot, i, kk, lim, n, m;

char ch;
void read(int &x)
{
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar());
    for (x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 - 48 + ch;
}

void add(int x, int y, int z)
{
    v[++tot] = y;
    w[tot] = z;
    nex[tot] = st[x];
    st[x] = tot;
}

void add_edge(int x)
{
    for (int i = st[x]; i != -1; i = nex[i])
    {
        int y = v[i];
        if (d[y] == -1)
            q.push(make_pair(- d[x] - w[i], y));
    }
}

void dij()
{
    int x;
    pair<int, int> p;
    while (d[0] == -1 && !q.empty())
    {
        p = q.top(); q.pop();
        x = p.second;
        if (d[x] != -1) continue;
        cnt[x]++;
        if (cnt[x] == lim + 1)
        {
            d[x] = - p.first;
            add_edge(x);
        }
    }
}

int main()
{
    read(n); read(m); read(kk); read(lim);
    int xx, yy, ww;
    memset(st, -1, sizeof(st[0]) * (n + 5));
    memset(d, -1, sizeof(d[0]) * (n + 5));
    for (i = 1; i <= m; i++)
    {
        read(xx); read(yy); read(ww);
        add(xx, yy, ww);
        add(yy, xx, ww);
    }
    for (i = 1; i <= kk; i++)
    {
        read(xx);
        d[xx] = 0;
        add_edge(xx);
        cnt[xx] = lim + 1;
    }
    dij();
    printf("%d\n", d[0]);
    return 0;
}



[CDOJ 1640] G - 花自飘零水自流，一种相思，两处闲愁。

Problem

有向图，从 1 出发，回到 1，允许在有向边上逆行一次，最多能遍历多少个点
1≤n,m≤100000，1≤x,y≤n

Solution

我的想法是，先缩点，点权就是分量大小，重新建图，那么 1 所在的这个分量的点都会被遍历，然后对所有从 1 连出去的点 xjb DP，但是 WA 了。。
看了题解，意思是，对于剩下的点，如果存在 u->v 这条边，如果逆着走过它的话，那么额外遍历的点数就是 1->v 能遍历的最多的点加上 u->1 能遍历的最多的点
怎么算这个东西？因为已经缩完了点，所以就不会存在环的问题，这整个就是一个拓扑图，做两次 dp 就能预处理出来，之前想多了，分太多种情况了。
然后就只要枚举边，然后两边加一加算一下，选个最大的就行了。
然而就是 A 不掉。。 数组边界开小了，这个错误隐藏得非常隐蔽。。mdzz

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define fi first
#define se second
const int N=100010;
const int M=100010;
int dfn[N], low[N], s[N], b[N], cnt[N], g[N], deg[N], degr[N];
int st[N], str[N], f[N], fr[N];
int v[M], vr[M], nex[M], nexr[M];
bool ins[N];
int fltot, tot, totr, i, n, m, ind, size, core, flag;

pair <int, int> edge[M];

void add(int x, int y)
{
    v[++tot] = y;
    nex[tot] = st[x];
    st[x] = tot;
}
void addr(int x, int y)
{
    vr[++totr] = y;
    nexr[totr] = str[x];
    str[x] = totr;
}

void tarjan(int x)
{
	int i, j;
	dfn[x] = low[x] = ++ind;
	ins[x] = 1;
	s[++size] = x;	//É趨xµÄʱ¼ä´ÁºÍlow³õÖµ 
	for (i = st[x]; i; i = nex[i])
	{
		j = v[i];
		if (!dfn[j])
		{
			tarjan(j);
			low[x] = min(low[x], low[j]);
		}
		else if (ins[j] && dfn[j] < low[x]) low[x] = dfn[j];
	}
	if (dfn[x] == low[x])
	{
		fltot++;
		do {
			j = s[size--];
			ins[j] = false;
			b[j] = fltot;
			cnt[fltot]++;
		} while (j != x);
	}
}

void dfs(int x)
{
    int y;
    g[x] = 1;
    for (int i = str[x]; i; i = nexr[i])
    {
        y = vr[i];
        if (!g[y]) dfs(y);
        if (f[y] > 0)
            f[x] = max(f[x], f[y] + cnt[x]);
    }
}

void dfs2(int x)
{
    int y;
    g[x] = 1;
    for (int i = st[x]; i; i = nex[i])
    {
        y = v[i];
        if (!g[y]) dfs2(y);
        if (fr[y] > 0)
            fr[x] = max(fr[x], fr[y] + cnt[x]);
    }
}

int main()
{
    freopen("in.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    for (i = 1; i <= m; i++)
    {
        scanf("%d%d", &edge[i].fi, &edge[i].se);
        if (edge[i].fi != edge[i].se)
            add(edge[i].fi, edge[i].se);
    }
    
    for (i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i);
    
    tot = totr = 0;
    core = b[1];
    memset(st, 0, sizeof(st[0]) * (fltot + 5));
    for (i = 1; i <= m; i++)
    {
        int x = b[edge[i].fi];
        int y = b[edge[i].se];
        if (x != y)
            { add(x, y); deg[y]++;
              addr(y, x); degr[x]++; }
    }
    
    f[core] = 1;
    g[core] = 1;
    for (i = 1; i <= fltot; i++)
        if (degr[i] == 0) dfs(i);  // core->x
    
    memset(g, 0, sizeof(g[0]) * (fltot + 5));
    
    fr[core] = 1;
    g[core] = 1;
    for (i = 1; i <= fltot; i++)
        if (deg[i] == 0) dfs2(i);  // x->core
    
    int ans = cnt[core];
    for (i = 1; i <= m; i++)
    {
        int y = b[edge[i].fi];
        int x = b[edge[i].se];  // core <- y->x <- core
        if (x != y)
        {
            if (f[x] > 0) x = f[x] - 1;  // core->x
                    else x = -10000000;
            if (fr[y] > 0) y = fr[y] - 1;  //y->core
                    else y = -10000000;
            ans = max(ans, x + y + cnt[core]);
        }
    }
    printf("%d\n", ans);
    return 0;
}



[CDOJ 1641] H - 此情无计可消除，才下眉头，却上心头。

Problem

n 项的数列 A1~An，每一项的值为 0 / 1
可以花 Cij 的费用询问数列中第 i 项到第 j 项的异或和
至少要花多少费用才能知道数列中每一项的具体值
1≤n≤1000，1≤Cij≤1000000

Solution

因为这个异或和满足区间加减法：
[a, b] ^ [b + 1, c] = [a, c]
[a, b] ^ [c + 1, b] = [a, c]
这样区间之间的=就有了某种传递性，这个传递性和图上的连通性是类似的，就好比 a 和 b 连通，b 和 c 连通，那么 a 和 c 就连通了。
因为上述式子无法直接转成图那样子，所以就考虑分隔线

+-+-+-+-+-+-+-----+-+
|1|2|3|4|5|6|.....|n|
+-+-+-+-+-+-+-----+-+
0 1 2 3 4 5 6   n-1 n

这样的话分隔线之间的连通性就相当于对应区间异或和是否可求
Cij 可以计算出分隔线 i 和分隔线 j+1 之间的异或和，相当于给 (i, j+1) 连一条边
最终目标呢，要使得每一项都可求，那就相当于是 (i, i+1) 连通，等价于所有点连通， 那就太简单啦，裸的最小生成树！

Code

#include<cstdio>
#include<algorithm>
using namespace std;

struct re {
    int x, y, z;
} a[1000010];
int tot, x, i, j, n, f[1010], rest, p, q, ans;

char ch;
void read(int &x)
{
    for (ch = getchar(); ch < '0' || ch > '9'; ch = getchar());
    for (x = 0; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 - 48 + ch;
}

bool cmp(re a, re b) { return a.z < b.z; }

int find(int x)
{
    if (f[x] == x) return x;
    return f[x] = find(f[x]);
}

int main()
{
    read(n);
    for (i = 1; i <= n; i++)
        for (j = i; j <= n; j++)
        {
            read(x);
            a[++tot].x = i - 1;
            a[tot].y = j;
            a[tot].z = x;
        }
    sort(a + 1, a + tot + 1, cmp);
    for (i = 0; i <= n; i++) f[i] = i;
    rest = n;
    for (i = 1; i <= tot && rest > 0; i++)
    {
        p = find(a[i].x);
        q = find(a[i].y);
        if (p == q) continue;
        f[q] = p;
        ans += a[i].z;
        rest--;
    }
    printf("%d\n", ans);
    return 0;
}



[CDOJ 1642] I - 老当益壮， 宁移白首之心？

Problem

请构造一个 01 串，使其满足以下条件：
环状（即首尾相连），每一位取值为 0 或 1，长度是 2n，对于每个（2n 个）位置，从其开始沿逆时针方向的连续的 n 位 01 串（包括自己）构成的数均不相同，即 0 到 2n−1 中的数各出现一次

Solution

打一发暴力，找了找一个规律，发现每次把满足条件的最小的 01 串展开成 2n 个数之后，最后几个数的二进制形式都是这样的：
11110..0 11100..0 11000..0 10000..0
前面一堆 1 后面一堆 0，1 逐渐减少，0 逐渐增多。。并不会证，然后我就用这个性质 dfs 了一波，搜索根本就没有回溯，直接秒出，check 了一下是对的，就 AC 了。。时间复杂度大概只有 O(2^n)，后面就改了一个非递归版的。

Code

#include<cstdio>
#include<cstdlib>
using namespace std;

const int T=100010;
bool g[T];
int a[T], n, tot, mask, lim, left, x, y;

// tot  100000000
// mask 011111111

int main()
{
    scanf("%d", &n);
    tot = 1 << n;
    left = 1 << (n - 1);
    mask = left - 1;
    a[0] = 0; a[1] = 1;
    g[0] = g[1] = 1;
    int base = 0;
    for (int i = 1; i <= n; i++)
    {
        base = (base >> 1) | left;
        a[tot - i] = base;
        g[base] = 1;
    }
    lim = tot - n - 1;
    for (int i = 2; i <= lim; i++)
    {
        x = (a[i - 1] & mask) << 1;
        if (g[x]) x |= 1;
        a[i] = x;
        g[x] = 1;
    }
    for (int i = 0; i < tot; i++)
        putchar((a[i] & left) ? '1' : '0');
    puts("");
    return 0;
}

Note

De Bruijn sequence 德布鲁因序列

[CDOJ 1646] J - 穷且益坚， 不坠青云之志。

Problem

求一个有 n 个元素的数列，满足任意连续 p 个数的和不小于 s，任意连续 q 个数的和不大于 t
1≤n,p,q≤500, 1≤s,t≤100000

Solution

转化为前缀和，就有一堆不等式啦，然后和 E 一样搞一个差分约束，不过不用求两次，求一次就行了，但还是要搞一个超级源

Code

#include<cstdio>
#include<cstring>
using namespace std;
const int N=2010;
const int M=20010;
const int INF=1000000010;
int q[1000010], cnt[N];
int st[N], nex[M], b[M], c[M];
int d[N];
bool g[N];
int n, P, Q, S, T, tot;

void add(int x, int y, int z)
{  // x + z <= y
    b[++tot] = y;
    c[tot] = z;
    nex[tot] = st[x];
    st[x] = tot;
}

bool spfa(int x)
{
    int i, j, h, t=0;
	for (i = 1; i <= n + 2; i++) d[i] = -INF;
	q[++t] = x;
    h = d[x] = 0;
    cnt[x] = 1;
    g[x] = 1;
	while (h != t)
	{
        x = q[++h];
        g[x] = 0;
		for (j = st[x]; j; j = nex[j])
			if (d[x] + c[j] > d[b[j]])
			{
				d[b[j]] = d[x] + c[j];
				if (!g[b[j]])
                {
                    cnt[b[j]]++;
                    if (cnt[b[j]] > n + 2) return 0;
                    q[++t] = b[j];
                    g[b[j]] = 1;
                }
			}
	}
	return 1;
}

int main()  
{
    scanf("%d%d%d%d%d", &n, &P, &Q, &S, &T);
    
    for (int i = 1; i <= n + 1; i++) add(n + 2, i, 0);
    // x + z <= y
    // s[p + i] - s[i] >= s
    // s[i] + s <= s[p + i]
    // s[q + i] - s[i] <= t
    // s[q + i] - t <= s[i]
    T = -T;
    add(n + 1, P, S);  // s[0] + s <= s[p]
    add(Q, n + 1, T);
    for (int i = 1; i <= n - P; i++)
        add(i, i + P, S);
    for (int i = 1; i <= n - Q; i++)
        add(i + Q, i, T);
    
    if (spfa(n + 2))
    {
        puts("Yes");
        printf("%d ", d[1]);
        for (int i = 2; i <= n; i++) printf("%d ", d[i] - d[i - 1]);
        puts("");
    }
    else puts("No");
    return 0;
}



[CDOJ 1647] K - 穷且益坚， 不坠青云之志。

Problem

首行两个整数 n,m(1≤n≤20,1≤m≤100000). ​接下来 m 行，每行包括两个01串（长度为 n）和一个整数si,wi,ti,(1≤ti≤1000000000)，表示 si 变为 wi 需要 ti 的时间
现在给你初始的 01 串，其长度为 n，并且元素全为 0（即 00…000…0），问你至少需要多长的时间变成全为 1（即11…111…1）

Solution

把 01 串按照其十进制大小映射到整数集上，就转化成最短路模型。。然后就是一道水题。。

Code

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

typedef long long ll;
const int M=100010;
const int N=M<<1;
const long long INF=((ll)1<<62)-10;

int st[N], nex[M], v[M];
ll w[M], dd[N];
int a2b[N], b2a[2100000];
bool g[N];
int i, x, y, z, vn, n, m, tot; 
char s1[100], s2[100];
priority_queue <pair<ll, int>> q;

void add(int x, int y, int z)
{
    v[++tot] = y;
    w[tot] = z;
    nex[tot] = st[x];
    st[x] = tot;
}

int dec(char* s)
{
    int len=strlen(s), res=0;
    for (int i = 0; i < len; i++)
        res = (res << 1) | (s[i] - 48);
    return res;
}
int lsh(int x)
{
    if (b2a[x] == 0)
    {
        b2a[x] = ++vn;
        a2b[vn] = x;
    }
    return b2a[x];
}

void dij(int x)
{
	int tot=0, i, j, y;
	q.push(make_pair(0, x));
	// memset(g, false, sizeof(g));
	for (i = 1; i <= vn; i++) dd[i] = INF;
	dd[x] = 0;
	while (tot < vn && !q.empty())
	{
		x = q.top().second;
		q.pop();
		if (g[x]) continue;
		g[x] = 1;
		tot++;
		for (j = st[x]; j; j = nex[j])
		{
		    y = v[j];
			if (!g[y] && dd[y] - dd[x] > w[j])
			{
				dd[y] = dd[x] + w[j];
				q.push(make_pair(-dd[y], v[j]));
			}
		}
	}
	return;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (i = 1; i <= m; i++)
    {
        scanf("%s%s%d", s1, s2, &z);
        x = dec(s1); y = dec(s2);
        if (x == y) continue;
        x = lsh(x);  y = lsh(y);
        add(x, y, z);
    }
    int eend = (1 << n) - 1;
    if (b2a[eend] != 0 && b2a[0] != 0)
    {
        dij(b2a[0]);
        if (dd[b2a[eend]] == INF) puts("-1");
                    else printf("%lld\n", dd[b2a[eend]]);
    } else puts("-1");
    return 0;
}





评论区加载中