标签: 状态压缩

[BZOJ3900]交换茸角 题解

[BZOJ3900]交换茸角 题解

题目地址:BZOJ:Problem 3900. — 交换茸角

题目描述

动物园里有 n 头麋鹿。每头麋鹿有两支茸角,每支茸角有一个重量。然而,一旦某头麋鹿上两支茸角的重量之差过大,这头麋鹿就会失去平衡摔倒。为了不然这种悲剧发生,动物园院长决定交换某些茸角,使得任意一头麋鹿的两角重量差不超过 c。然而,交换两支茸角十分麻烦,不仅因为茸角需要多个人来搬运,而且会给麋鹿造成痛苦。因此,你需要计算出最少交换次数,使得任意一头麋鹿的两角重量差不超过 c。
注意,交换两支茸角只能在两头麋鹿之间进行。因为交换同一头麋鹿的两支角是没有意义的。

输入输出格式

输入格式:
第一行为整数 n,c。接下来 n 行,每行两个整数,分别表示一开始每头麋鹿的两角重量。

输出格式:
一个数,即最少交换次数。如果无论如何也不能使每头麋鹿平衡,输出 -1。

输入输出样例

输入样例#1:

3 0
3 3
2 5
2 5

输出样例#1:

1

说明

对于 100% 的数据,n <= 16, c <= 1000000, 每支茸角重量不超过 1000000。

题解

这个n的范围看起来很像状压DP,那我们就往那个方向去想。
我们考虑用状压表示子集,dp[S]表示S集合中的所有鹿换角最少多少次能满足条件。对于初始值,我们把S集合中的鹿的所有角都拿出来排个序分好组,如果发现有一组角的差值大过c,那么这个集合内部就无法自行调整为满足条件的情况,dp值应设置为INF。如果集合内部已经满足条件,dp值应设置为0。如果都不是上面的情况,那么按照最差的换法,应该是每个鹿从待选角中找到配对的角换上,这个次数最差是集合内鹿的数量-1的,dp值应设置为这个最差的值。
对于转移,我们考虑枚举每个状态S的子集T,有下面的方程
dp[S] = \min(dp[S], dp[T] + dp[S \wedge T])
这个的复杂度是O(2^n \cdot n)的。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <vector>
#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 17, INF = 0x3f3f3f3f;

int n, c, a[MAXN], b[MAXN], dp[1 << MAXN];
std::vector<int> tmp;

int main() {
    n = readint();
    c = readint();
    for(int i = 1; i <= n; i++) {
        a[i] = readint();
        b[i] = readint();
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    for(int i = 1; i < (1 << n); i++) {
        bool flag = false;
        tmp.clear();
        for(int j = 1; j <= n; j++) {
            if(i & (1 << (j - 1))) {
                if(std::abs(a[j] - b[j]) > c) flag = true;
                tmp.push_back(a[j]);
                tmp.push_back(b[j]);
            }
        }
        if(!flag) {
            dp[i] = 0;
            continue;
        }
        std::sort(tmp.begin(), tmp.end());
        flag = false;
        for(int j = 0; j < tmp.size(); j += 2) {
            if(tmp[j + 1] - tmp[j] > c) {
                flag = true;
                break;
            }
        }
        if(!flag) dp[i] = tmp.size() / 2 - 1;
    }
    for(int i = 1; i < (1 << n); i++) {
        for(int j = (i - 1) & i; j; j = (j - 1) & i) {
            dp[i] = std::min(dp[i], dp[j] + dp[i ^ j]);
        }
    }
    if(dp[(1 << n) - 1] == INF) {
        printf("-1");
    } else {
        printf("%d", dp[(1 << n) - 1]);
    }
    return 0;
}
NOIP2017提高组题解&总结

NOIP2017提高组题解&总结

本篇题解借鉴和参考了洛谷题解区的同学所写的题解以及部分博文,由于未能记录全面,并没能将这些参考内容全部列出,为此对这些内容的作者感到抱歉。

NOIP2017已经结束啦。在华中科大计科实验室度过的7个小时犯了挺多的错误,现在想想,其实自己能上300。初次考试,题型有少许变化加上自己没有经验,成功爆炸。还好最后D1T2救了一下场。
接下来是题解和感想。

NOIP2017 提高组 Day1

吐槽

T1实在是太太太太太太拉分了orz

个人成绩

30,90,0

题目列表(评测来自洛谷)

赛题 #A: P3951 小凯的疑惑 | 数论,找规律
赛题 #B: P3952 时间复杂度 | 大模拟,耐心
赛题 #C: P3953 逛公园 | 图论,记忆化搜索,k短路计数

小凯的疑惑

一句话题意

求使px+qy=n无自然数范围内的解的最大正整数n。其中,p, q互质。

解法

100% 1 \leq a, b \leq 10^9

只需输出pq - p - q即可。
证明:试使用反证法
假设存在正整数x, y使px + qy = pq - p - q
则有p(x+1)+q(y+1)=pq
易知p|q(y+1)
\because gcd(p, q)=1
\therefore p|y+1
同理q|x+1
y+1=pj, x+1=qk
则有pqk+qpj=pq
也就是pq(j+k)=pq
\because j+k=x+y+2 \geq 2
上式并不成立,得证。
但是考场上推出这个方法应该打表找规律。
还有一种扩欧推出的方法,更多题解可以看洛谷题解 P3951 – 百科 – 洛谷

代码

// Code by KSkun, 2017/11
#include <cstdio>

int main() {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%lld", 1ll * a * b - a - b);
    return 0;
}

总结

千言万语汇成一句话:数论推个屁,打表找规律。铭记在心,终生受用。

时间复杂度

没有概括,自己看洛谷

解法

100% L \leq 100

维护一个管理循环的栈。由于循环从里到外结束,可用栈管理循环的嵌套关系。
细节比较多,如果该循环能够计入这一次的复杂度,则满足以下条件:

  1. 之前不能有不能执行的循环
  2. 循环的终点是n

不计入复杂度但能执行的循环满足以下条件中任意的一条:

  1. 起点和终点都是常数,且起点小于等于终点
  2. 起点和终点都是n

不能被执行的循环满足以下条件中任意的一条:

  1. 起点是n
  2. 起点和终点都是常数,且起点小于终点

语法错误有3类:

  1. 变量名冲突(vis管理一下)
  2. E语句结束了不存在的循环(判断栈是否为空)
  3. 结束指令后仍有未关闭的循环(同2)

对于不能被执行的循环,打标记并使之后的循环对答案无贡献,直到它出栈。逐循环计算它对总复杂度的贡献。只要把以上细节写全了就能A。

代码

// Code by KSkun, 2017/11
#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>

struct Loop {
    char var;
    int beg, end;
    Loop(char var, int beg, int end): var(var), beg(beg), end(end) {}
};

inline int getComp(char *str) {
    if(str[2] == 'n') {
        int res = 0, len = strlen(str);
        for(int i = 4; i < len; i++) {
            if(str[i] == ')') break;
            res = res * 10 + str[i] - '0';
        }
        return res;
    }
    return 0;
}

inline int getNum(char *str) {
    if(str[0] == 'n') return -1;
    int res = 0, len = strlen(str);
    for(int i = 0; i < len; i++) {
        res = res * 10 + str[i] - '0';
    }
    return res;
}

bool vis[50], iserr;
char op[5], var[5], beg[5], end[5], complexity[100], notValid;
int t, l, now, all, exp;
std::stack<Loop> sta;

int main() {
    //freopen("p3952.in", "r", stdin);
    scanf("%d", &t);
    while(t--) {
        memset(vis, 0, sizeof vis);
        while(!sta.empty()) sta.pop();
        iserr = false;
        notValid = '-';
        now = all = 0;
        scanf("%d%s", &l, complexity);
        exp = getComp(complexity);
        while(l--) {
            scanf("%s", op);
            if(op[0] == 'F') {
                scanf("%s%s%s", var, beg, end);
                // ERR proccess
                if(vis[var[0] - 'a']) {
                    iserr = true;
                    continue;
                } 

                // non-ERR process
                if(iserr) continue;
                vis[var[0] - 'a'] = true;
                Loop t = Loop(var[0], getNum(beg), getNum(end));
                sta.push(t);
                if(((t.beg == -1 && t.end != -1) || (t.beg != -1 && t.end != -1 && t.beg > t.end)) && notValid == '-') {
                    // if this is the first loop that any loop after it will not run. 
                    notValid = t.var;
                }
                if(notValid != '-') continue;
                if(t.end == -1 && t.beg != -1) {
                    now++;
                }
            } else if(op[0] == 'E') {
                // ERR proccess
                if(sta.empty()) {
                    // if stack is empty when trying to proccess an 'E' command
                    iserr = true;
                    continue;
                }

                // non-ERR proccess
                if(iserr) continue;
                Loop t = sta.top();
                sta.pop();
                vis[t.var - 'a'] = false;
                if(t.var == notValid) {
                    notValid = '-';
                }
                if(notValid != '-') continue;
                all = std::max(all, now); // always update all complexity value
                if(t.end == -1 && t.beg != -1) {
                    now--;
                }
            }
        }
        if(!sta.empty()) {
            // if stack is still not empty when all commands are inputed
            iserr = true;
        }
        if(iserr) {
            printf("ERR\n");
        } else if(all == exp) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
}

总结

考场上可能是没考虑周全,思路也比较乱,导致写出来代码很乱而且只有90,没能A掉。是一个遗憾。这种大模拟,重要的就是给自己偷懒,把能复用的代码写函数,能包的包起来,并且思路清晰分模块编写就好。本以为再也不会碰到这种大模拟题了,CCF在搞啥啊orz

逛公园

一句话题意

给一个有向图,求从1到N点长度不超过最短路径+K的路径数量。

解法

30% K = 0

最短路计数。(模板题:洛谷P1144洛谷P1608
在SPFA求最短路的时候加一个cnt数据记录到某点最短路的数量。如果一个点的最短路被更新,cnt重置为1,否则如果找到另外一条最短路,对cnt加一。

100% 1 \leq N \leq 100000, 1 \leq M \leq 200000, 0 \leq K \leq 50

很容易设计一个DP状态为dp[u][k]表示u点比最短路长k的路径数量,而初始dp[1][0]为1。规定dis数组为1到每个点的最短路距离,对于u点的所有入边(入边长度为len)的起点v,转移如下
dp[u][k] = \sum dp[v][dis[u]-dis[v]+k-len]
如果用SPFA转移,要考虑转移的状态是否已经计算过。我们规定转移的顺序是优先转移dis小的点,因此我们要保持转移队列的优先级有序。
但如果这个转移可以从N点开始,在反图上转移就不存在上面的问题。这种方案我们可以采用记忆化搜索。这道题时限有3s,能够满足需要。
那么0边如何处理?记忆化搜索不需要管0边,但是如果搜索的过程中遇到了一个0环,那么这个环任意跑多少圈都是一条可取的路径,这种情况是无解的,因此要在搜索过程中记录下搜索状态(u, k)是否已经在搜索栈中,可以用vis数组来处理一下。如果在栈中,就说明存在0环。
另外有一个很玄学的问题,搜索的最后要加一行dfs(N, K + 1);,否则就会有数据跑不过去,例如这一组数据

2 2 0 50
1 2 0
2 1 0

答案应该为-1,但是如果不加那一行答案就是1了。然而洛谷的数据好像不加那一行也能过,我不是很清楚原理是啥。

代码

// Code by KSkun, 2018/1
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

struct io {
    char buf[1 << 26], *s;

    io() {
        fread(s = buf, 1, 1 << 26, stdin);
    }

    inline int read() {
        register int res = 0, neg = 1;
        while(*s < '0' || *s > '9') {
            if(*s == '-') neg = -1;
            s++; 
        } 
        while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
        return res * neg;
    }
};

io ip;

#define read ip.read 

struct Edge {
    int to, w;
    Edge(int to, int w): to(to), w(w) {}
};

std::vector<Edge> vec[100005], rev[100005];

inline void addedge(int u, int v, int w) {
    vec[u].push_back(Edge(v, w));
    rev[v].push_back(Edge(u, w));
} 

int T, N, M, K, P, ut, vt, wt, dis[100005], dp[100005][55], ans;
bool vis[100005][55], zcircle;

std::queue<int> que;
bool inque[100005];

inline void spfa(int st) {
    memset(dis, 0x3f, sizeof dis);
    memset(inque, 0, sizeof inque);
    que.push(st);
    dis[st] = 0;
    inque[st] = true;
    while(!que.empty()) {
        int u = que.front();
        que.pop();
        inque[u] = false;
        for(int i = 0; i < vec[u].size(); i++) {
            int v = vec[u][i].to;
            if(dis[v] > dis[u] + vec[u][i].w) {
                dis[v] = dis[u] + vec[u][i].w;
                if(!inque[v]) {
                    inque[v] = true;
                    que.push(v);
                }
            } 
        } 
    }
}

inline int dfs(int u, int k) {
    //printf("u %d k %d\n", u, k);
    if(vis[u][k]) {
        zcircle = true;
        return -1;
    }
    if(dp[u][k] != -1) return dp[u][k];
    vis[u][k] = true;
    dp[u][k] = 0;
    for(int i = 0; i < rev[u].size(); i++) {
        int v = rev[u][i].to;
        int delta = dis[u] - dis[v] + k - rev[u][i].w;
        //printf("  v %d delta %d\n", v, delta);
        if(delta < 0) continue;
        dp[u][k] = (0ll + dp[u][k] + dfs(v, delta)) % P;
        if(zcircle) return -1;
    }
    vis[u][k] = false;
    return dp[u][k];
}

int main() {
    T = read();
    while(T--) {
        memset(dp, -1, sizeof dp);
        memset(vis, 0, sizeof vis);
        zcircle = false;
        ans = 0;
        N = read();
        M = read();
        K = read();
        P = read();
        for(int i = 1; i <= N; i++) {
            vec[i].clear();
            rev[i].clear();
        }
        for(int i = 0; i < M; i++) {
            ut = read();
            vt = read();
            wt = read();
            addedge(ut, vt, wt);
        }
        spfa(1);
        dp[1][0] = 1;
        for(int i = 0; i <= K; i++) {
            ans = (0ll + ans + dfs(N, i)) % P;
        }
        dfs(N, K + 1);
        if(zcircle) {
            printf("-1\n");
        } else {
            printf("%d\n", ans);
        }
    }
    return 0;
}

总结

图论+DP的写法是第一次碰到,最短路计数的骗分也不会写,NOIP之前的我果然是个鶸。

NOIP2017 提高组 Day2

吐槽

第一次碰到纯粹的数据结构题,第一次碰到这么难的DP。

个人成绩

100,20,30

题目列表(评测来自洛谷)

赛题 #A: P3958 奶酪 | BFS,并查集
赛题 #B: P3959 宝藏 | 状压DP,记忆化搜索
赛题 #C: P3960 列队 | 数据结构,线段树,平衡树

奶酪

一句话题意

给一堆球体,有两个平行于xOy坐标平面的平面作为底面(z=0)和顶面(z=h),两个相交或者相切的球体可以视作联通,求是否能找到一条路径从底面到顶面去。

解法

100% 1 \leq N \leq 1000

建图BFS或者并查集检查是否有底面-顶面球体对在同一集合内都可以解决这个问题。题目本身并不难,而且默认了z坐标为正也不会爆long long。

代码

// Code by KSkun, 2018/1
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>

struct Ball {
    int x, y, z;
    Ball(int x, int y, int z): x(x), y(y), z(z) {}
};

std::vector<Ball> balls;
std::vector<int> vec[1005];
std::queue<int> que;
bool top[1005], success, vis[1005];
int T, n, h, r, x, y, z;

inline long long dis(int a, int b) {
    long long x = 1ll * (balls[a].x - balls[b].x) * (balls[a].x - balls[b].x),
        y = 1ll * (balls[a].y - balls[b].y) * (balls[a].y - balls[b].y),
        z = 1ll * (balls[a].z - balls[b].z) * (balls[a].z - balls[b].z);
    return x + y + z;
}

inline bool can(int a, int b) {
    return dis(a, b) <= 1ll * r * r * 4;
}

int main() {
    scanf("%d", &T);
    while(T--) {
        success = false;
        while(!que.empty()) que.pop();
        memset(top, 0, sizeof top);
        memset(vis, 0, sizeof vis);
        balls.clear();
        scanf("%d%d%d", &n, &h, &r);
        for(int i = 1; i <= n; i++) {
            vec[i].clear();
        }
        for(int i = 1; i <= n; i++) {
            scanf("%d%d%d", &x, &y, &z);
            balls.push_back(Ball(x, y, z));
            if(std::abs(h - z) <= r) top[i] = true;
            if(std::abs(z) <= r) que.push(i);
            for(int j = 0; j < balls.size() - 1; j++) {
                if(can(i - 1, j)) {
                    vec[i].push_back(j + 1);
                    vec[j + 1].push_back(i);
                }
            }
        }
        // BFS
        while(!que.empty()) {
            int u = que.front();
            que.pop();
            if(top[u]) {
                success = true;
                break;
            }
            vis[u] = true;
            for(int i = 0; i < vec[u].size(); i++) {
                int v = vec[u][i];
                if(!vis[v]) {
                    que.push(v);
                }
            }
        } 
        if(success) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
    return 0;
} 

感想

当时写的时候还在纠结是不是要爆ll,然后开了ull。后来发现我多虑了。好多人都栽在这个题上。我当时写的大常数BFS是能在老爷机上A了的,所以并不清楚发生了什么。

宝藏

一句话题意

给一个无向图,让你找一个最小生成树,生成树的每条边产生Z \times W的代价,其中Z是该边起点到指定根的距离(每条边长度为1),W是边本来的权值。

解法

100% 1 \leq n \leq 12, 0 \leq m \leq 1000

考虑使用dis数组记录每个点到指定根的距离,然后设计状压DP,dp[S]表示已经加入生成树的点为S的时候的最佳方案。
转移直接使用搜索即可。对于集合S中的每一个点尝试转移到它们的下层点。如果发现下层点的状态方案不是最优,则更新最优并搜索下去,否则回溯。
然后枚举指定根,每一次都搜一遍。
代码相当短,题目本身也并不是很难,就是一个大暴力。

代码

// Code by KSkun, 2018/1
#include <cstdio>
#include <cstring>
#include <algorithm>

const int INF = 0x3f3f3f3f;

int n, m, gra[15][15], dis[15], dp[1 << 13], ans = INF, ut, vt, wt;

inline int dfs(int s) {
    for(int i = 1; i <= n; i++) {
        // if the point has been chosen
        if(s & (1 << (i - 1))) {
            for(int j = 1; j <= n; j++) {
                // if the goal is reachable and hasn't been chosen
                if(!(s & (1 << (j - 1))) && gra[i][j] != INF) {
                    // if there is a better solution
                    if(dp[s | 1 << (j - 1)] > dp[s] + dis[i] * gra[i][j]) {
                        int lst = dis[j];
                        dis[j] = dis[i] + 1;
                        dp[s | 1 << (j - 1)] = dp[s] + dis[i] * gra[i][j];
                        dfs(s | 1 << (j - 1));
                        dis[j] = lst;
                    }
                }
            }
        }
    }
}

int main() {
    memset(gra, 0x3f, sizeof gra);
    memset(dis, 0x3f, sizeof dis);
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++) {
        scanf("%d%d%d", &ut, &vt, &wt);
        gra[ut][vt] = gra[vt][ut] = std::min(gra[ut][vt], wt);
    }
    // choose who is the root
    for(int i = 1; i <= n; i++) {
        memset(dis, 0x3f, sizeof dis);
        memset(dp, 0x3f, sizeof dp);
        dis[i] = 1;
        dp[1 << (i - 1)] = 0;
        dfs(1 << (i - 1));
        ans = std::min(ans, dp[(1 << n) - 1]);
    }
    printf("%d", ans);
    return 0;
}

感想

考场上在想为什么今天还没出DP题以及这题怎么看怎么像生成树,然后疯狂想办法证贪心,然后GG。考完试一个华一大佬告诉我就是个贪心生成树,然后他也GG了,233。

列队

一句话题意

有一个n \times m的矩阵,每次从(x, y)拿出一个数并且删掉它,然后左对齐、上对齐,再把拿出的这个数插入(n, m)位置。给定很多(x, y),每次求拿出的那个数是什么。

解法

30% n = 1

其实我们发现我们可以用一个长为m+q的线段树来维护这个序列。当每一次删点的时候记录哪些区间的子树里删了这个点,就可以统计出一个该区间内总共删掉的点数,然后每次查找第几个元素的时候以此为参考到它的左子树or右子树查找。至于多出来的那些个可能乱序的元素,就直接扔进vector然后如果要找就算一下下标。

100% 1 \leq n, m, q \leq 3 \times 10^5

对30%的做法进行延伸,我们可以发现,这个题需要n+1棵线段树,对应n行的前m-1个元素和最后一列,每一次在该行中删除一个元素,然后在最后一列中删一个元素加入该行,再往最后一列中加入一个元素。这样一来,思路就很明确了。

代码

// Code by KSkun, 2018/1
#include <cstdio>
#include <algorithm>
#include <vector>

struct io {
    char buf[1 << 26], *s;

    io() {
        //freopen("p3960-13.in", "r", stdin);
        //freopen("p3960-13.out", "w", stdout);
        fread(s = buf, 1, 1 << 26, stdin);
    }

    inline int read() {
        register int res = 0, neg = 1;
        while(*s < '0' || *s > '9') {
            if(*s == '-') neg = -1;
            s++; 
        } 
        while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
        return res * neg;
    }
};

io ip;

#define read ip.read 

int n, m, q, x, y, N;
int lc[10000005], rc[10000005], del[10000005], root[300005], tot = 0;
std::vector<long long> vec[300005];

inline long long query(int o, int l, int r, int rnk) {
    if(l == r) return l;
    // res stands for how many points left subtree has
    int mid = (l + r) >> 1, res = mid - l + 1 - del[lc[o]];
    if(res >= rnk) return query(lc[o], l, mid, rnk);
    else return query(rc[o], mid + 1, r, rnk - res);
}

inline void update(int &o, int l, int r, int rnk) {
    if(!o) o = ++tot;
    del[o]++;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(mid >= rnk) update(lc[o], l, mid, rnk);
    else update(rc[o], mid + 1, r, rnk);
}

inline long long del_line(int x, int y) {
    long long res = query(root[x], 1, N, y);
    update(root[x], 1, N, res);
    return res < m ? 1ll * (x - 1) * m + res : vec[x][res - m];
}

inline long long del_row(int x) {
    long long res = query(root[n + 1], 1, N, x);
    update(root[n + 1], 1, N, res);
    return res <= n ? 1ll * res * m : vec[n + 1][res - n - 1];
}

int main() {
    n = read();
    m = read();
    q = read();
    N = std::max(n, m) + q;
    while(q--) {
        x = read();
        y = read();
        if(y != m) {
            long long res = del_line(x, y);
            vec[n + 1].push_back(res);
            printf("%lld\n", res);
            vec[x].push_back(del_row(x));
        } else {
            long long res = del_row(x);
            vec[n + 1].push_back(res);
            printf("%lld\n", res);
        }
    }
    return 0;
}

感想

从来没写过纯粹的数据结构题的我在考场上就是懵逼的qwq

密码保护:浴谷八连测总结

密码保护:浴谷八连测总结

无法提供摘要。这是一篇受保护的文章。