牛客寒假算法基础集训营3

B.处女座的比赛资格

题目描述：

处女座想出去比赛，但是又不知道学校能不能给到足够的经费。然而处女座是大众粉丝，有着很好的人缘，于是他找了一个在学校管经费的地方勤工俭学偷来了一份报销标准。由于处女座是万人迷，所以他在中间途径的每一条线路上都会发生一些故事，也许是粉丝给他发了一个200元的微信红包，也许是和他的迷妹一起吃饭花了500元。
而经费负责人也实地考察了每一条路线，在每一条路上，也许是天降红包雨，也许是地生劫匪。每一条路上都有属于自己的奇遇。
而经费负责人也只能根据他的故事决定这一路批下来多少经费。他会找出从宁波到比赛地的最小花费，并以此作为标准给处女座打比赛。而处女座也会选择对他来说最小花费的路线，来节省使用。
处女座想知道，最终的经费是否够用，如果够还会剩下来多少钱。如果不够，他自己要自费掏出多少钱。（当然处女座和经费管理人都具有旅途中无限信贷额度，所有收入支出会在旅行结束后一起结算。）

输入描述：

输入文件第一行包含一个整数T，表示处女座要参加的比赛场数。对于每一场比赛，第一行包含两个整数N,M，分别表示旅行中的站点数（其中宁波的编号为1，比赛地的编号为N）和线路数。
接下来M行，每一行包含5个整数 $ u,v,c,cnz,jffzr $，分别表示从u到v有一条单向的线路，这条线路的票价为c。处女座搭乘这条线路的时候，会得到cnz元（如果为负即为失去 $ -cnz $ 元）；经费负责人搭乘这条线路的时候，会得到 $ jffzr $ 元（如果为负即为失去 $ -jffzr $ 元）。行程保证不会形成环，并保证一定能从宁波到达比赛地。

输出描述：

对于每一场比赛，如果经费负责人给出的经费绰绰有余，则先在一行输出”cnznb!!!”，并在下一行输出他可以余下的经费；如果处女座的经费不够用，则先在一行输出”rip!!!”，并在下一行输出他需要自费的金额；如果经费负责人给出的经费正好够处女座用，则输出一行”oof!!!”。（所有输出不含引号）

输入

1
3 3
1 2 300 600 -600
2 3 100 -300 1
1 3 200 0 0

输出

1 2	cnznb!!! 100

说明

处女座先走第一条路再走第二条路到达，总花费100元，经费负责人走第三条路，花费200元，处女座经费剩余100元。

备注:

$ T \leq 10 $
$ 2 \leq N \leq 10^5 $
$ 1 \leq M \leq 2 \cdot 10^5 $
$ 1 \leq u, v \leq N $
$ 0 \leq c \leq 10^9 $
$ −10^9 \leq cnz, jffzr \leq 10^9 $

思路：

这道题比赛时没来得及写，赛后补题发现挺简单的。仔细读题，行程一定不会形成环并保证一定能从宁波达到比赛地，这不就是赤裸裸的拓扑排序？！求特殊的有向无环图（DAG）上的最短路，每次更新拓扑点的邻接点到宁波（编号为1）的最小费用，显然题目中编号1的入度肯定为0，然后按照节点拓扑顺序计算最小费用，最终一定能求出达到比赛地的最小费用。两次拓扑排序。时间复杂度为 $ O(|E| + |V|)$。
坑点：①初始建边时，每条边的权值应为 $ z - cnz, z - jffzr $，边权为负数表示赚了，边权为正表示要缴过路费。
②若从宁波到达比赛地的最小花费为负数，说明赚了，即不用交过路费，则需花费的费用应为0，否则就是要交的最小过路费。因此，最终应取 $ max(0, dist[n]) $。

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 2e5+5;
const LL inf = 1e15;
LL T, n, m, x, y, z, cnz, jffzr, indeg1[maxn], indeg2[maxn], tot1, tot2, dist1[maxn], dist2[maxn];
struct EDGE{
    LL to, val;
    EDGE(LL to, LL w) : to(to), val(w) {}
};
vector<EDGE> edge1[maxn], edge2[maxn];
queue<LL> que;
inline LL read(){
    LL 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;
}
LL cnz_topsrot(LL s) {
    while(!que.empty()) que.pop();
    for(LL i = 1; i <= n; ++i)
        if(indeg1[i] == 0) que.push(i);
    dist1[s] = 0LL;
    while(!que.empty()) {
        LL u = que.front(); que.pop();
        for(LL j = 0; j < edge1[u].size(); ++j) {
            LL v = edge1[u][j].to, w = edge1[u][j].val;
            dist1[v] = min(dist1[v], dist1[u] + w);
            if(--indeg1[v] == 0) que.push(v);
        }
    }
    return max(0LL, dist1[n]); //负---赚了<==>0费用
}
LL jffzr_topsrot(LL s) {
    while(!que.empty()) que.pop();
    for(LL i = 1; i <= n; ++i)
        if(indeg2[i] == 0) que.push(i);
    dist2[s] = 0LL;
    while(!que.empty()) {
        LL u = que.front(); que.pop();
        for(LL j = 0; j < edge2[u].size(); ++j) {
            LL v = edge2[u][j].to, w = edge2[u][j].val;
            dist2[v] = min(dist2[v], dist2[u] + w);
            if(--indeg2[v] == 0) que.push(v);
        }
    }
    return max(0LL, dist2[n]);
}
int main(){
    T = read();
    while(T--) {
        n = read(), m = read();
        memset(indeg1, 0, sizeof(indeg1));
        memset(indeg2, 0, sizeof(indeg2));
        for(LL i = 0; i <= n; ++i) edge1[i].clear(), edge2[i].clear(), dist1[i] = dist2[i] = inf;
        while(m--) {
            x = read(), y = read(), z = read(), cnz = read(), jffzr = read();
            edge1[x].push_back(EDGE(y, z - cnz));
            edge2[x].push_back(EDGE(y, z - jffzr));
            indeg1[y]++, indeg2[y]++;
        }
        tot1 = cnz_topsrot(1LL);
        tot2 = jffzr_topsrot(1LL);
        if(tot1 == tot2) printf("oof!!!\n");
        else if(tot1 < tot2) printf("cnznb!!!\n%lld\n", tot2 - tot1);
        else printf("rip!!!\n%lld\n", tot1 - tot2);
    }
    return 0;
}

C.处女座点名

题目描述：

处女座觉得自己手上的经费可能不太够，于是决定给牛逼学生们带家教。一天他去上课用自己的火眼金睛感觉教室里有一个学生没有来，于是他就叫学生们报出自己的学号。
已知这个班上的学号是从1开始连续编号的，处女座告诉你这个班上有多少人，想问问你到底是谁没有来。

输入描述:

输入数据共两行，第一行为一个整数N，表示班上的学生数量。第二行为一行 $ N-1 $ 个整数，表示已经来的学生的学号，按升序给出。

输出描述:

输出一个整数，为没有来的学生的学号。

输入

1
2

3
1 3

输出

备注:

$ 2 \leq N \leq 200000 $.

思路：

签道题！简单标记即可！

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 200005;
int n, x, a[maxn];
int main() {
    while(cin >> n) {
        memset(a, 0, sizeof(a));
        for(int i = 1; i < n; ++i) cin >> x, a[x] = 1;
        for(int i = 1; i <= n; ++i)
            if(!a[i]){cout << i << endl; break;}
    }
    return 0;
}

D.处女座的训练

题目描述：

处女座靠着自己的家教本领赚够了去比赛的钱，于是开启了疯狂训练。在每个夜深人静第二天不收作业的夜晚，他都会开始刷题。”今日又是一个刷题的夜晚。”他挑选了n道题开始刷，而题太多，刷不掉，理还乱（呜呜）、自己没有解决的题目每分钟都会给他带来 $ b_i $ 的疲倦值，而解决每一道题目都需要花费 $ a_i $ 分钟的时间。
当然，处女座一般都是考虑清楚了再写题的，所以他在写题的时候都会精神抖擞，也就是说，当前正在写的那一题并不会给他带来任何疲劳。
为了迎接后天要收的作业和明天要遇到的小姐姐，他想让今晚的刷题尽可能的轻松，那请你帮他找出最小所需要的疲倦值吧。

输入描述:

输入数据共包括 $ n + 1 $ 行，第一行包括一个n表示处女座今晚打算训练的题的数量。
接下来n行，每行包括两个整数 $ a_i, b_i $，分别表示处女座刷掉本题要花费的时间和本题每分钟会带来的疲倦值。

输出描述:

一行包括一个整数，表示处女座今晚训练会产生的最小疲倦值。

输入

输出

说明

先做第6个题，增加 $ (1 + 5 + 3 + 2 + 1) * 2 = 24 $ 点疲倦值，再做第2个题，增加28点疲倦值，随后依次是第 $ 3,4,1,5 $ 道题，增加 $ 16,12,6 $ 点疲倦值。总共的疲倦值是 $ 24 + 28 + 16 + 12 + 6 = 86 $ 点。

备注:

$ 2 \leq N \leq 10^5 $.
$ 2 \leq a_i \leq 4 \cdot 10^6 $.
$ 1 \leq b_i \leq 1000 $.

思路：

猜题+验证！出题人处女座 $ (cnznb!!!) $ 处处暗示着答案，简单计算了样例可知只需按每道题的单位疲劳值所花费的时间降序排+贪心即可！证明略。

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+5;
int n; LL ans, sum;
struct node{LL a, b;} nod[maxn];
bool cmp(node x, node y) { 
    return x.b * y.a > y.b * x.a;
}
int main() {
    while(cin >> n){
        sum = ans = 0;
        for(int i = 0; i < n;++i) cin >> nod[i].a >> nod[i].b, sum += nod[i].b;
        sort(nod, nod + n,cmp);
        for(int i = 0; i < n; ++i) {
            sum -= nod[i].b;
            ans += sum * nod[i].a;
        }
        cout << ans << endl;
    }
    return 0;
}

E.处女座和小姐姐

题目描述:

既然昨天晚上处女座已经训练了，明天才要交作业，那今天就是平淡无奇要上课的一天了。
然而处女座也想自己的小姐姐了，可是这节课是老师安排座位，处女座坐在 $ (1,1) $，而小姐姐坐在 $ (n,m) $。他们之间只能通过传纸条的方式来交流感情。对于处女座而言，他上课不想过度分心，因此并不想传纸条，只在那里趁机折千纸鹤。
老师上课喜欢用”开火车”的方式让大家轮流回答问题，显然处女座作为 $ (1,1) $ 位，会被第一个叫起来回答，之后老师将依次叫起
$ (2,1),(3,1), \cdots (n,1),(n,2),(n−1,2) \cdots (1,2), \cdots $ 的人起来回答问题，每个人回答问题需要1秒。处女座在自己回答完以后会以每秒1个千纸鹤的速度折叠，在小姐姐开始回答问题的时候停止折叠。
处女座想知道，他这节课一共要折多少个千纸鹤？

输入描述:

输入文件包含T+1行，第一行包含一个整数T，表示用例组数。接下来T行，每行包含两个整数n,m表示小姐姐的位置和教室的大小。

输出描述:

对于每一组用例，用一行输出一个整数，表示处女座要折的千纸鹤的个数。

输入

1
2

1
3 3

输出

备注:

$ 2 \leq n, m \leq 1000 $.

思路：

签道题！一开始把行和列看反了，多加了罚时QWQ，以后读题要细心点！！！

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int T, n, m, ans, cnt;
int main() {
    while(cin >> T){
        while(T--){
            cin >> n >> m; //行：m，列：n
            if(m & 1) ans = m - 1 + m * (n - 1) - 1;
            else ans = m - 1 + (m - 1) * (n - 1) - 1 ;
            cout << ans << endl;
        }
    }
    return 0;
}

G.处女座和小姐姐（三）

题目描述：

经过了选号和漫长的等待，处女座终于拿到了给小姐姐定制的手环，小姐姐看到以后直呼666！
处女座其实也挺喜欢6这个数字的，实际上他做手环的时候选取的k=6。所以他对于包含数码6的数字极其敏感。每次看到像4567这样的数字的时候他的心就像触电了一样，想起了小姐姐。
现在你要给处女座展示一系列数字，你想知道他的内心会激动多少次。对于同一个数字，他最多只会激动一次，即如果这个数是66666，他还是只会激动一次。

输入描述:

一行包括两个数字 $ l,r $，表示你给处女座展示的数字范围为 $ [l, r] $。

输出描述:

一行一个整数，表示处女座内心激动的次数。

输入

10 20

输出

备注:

$ 0 \leq l \leq r \leq 10^{18} $.

思路：

裸的数位dp！！！统计不含6的数的个数，改一下模板即可。
公式： $j \neq 6, dp[i][j] += \sum_{k = 0 \land k \neq 6}^9 dp[i-1][k] ; j = 6, dp[i][j] = 0$ 。

AC代码1：递归版本

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n, m, dp[20][2], d[20];
LL dfs(int pos, bool if6, bool limit){ //第pos位、当前数字是否含6：if6、当前数位的上一位是否为上界：limit。
    if(!pos) return 1;
    if(!limit && dp[pos][if6] != -1) return dp[pos][if6];
    LL up = limit ? d[pos] : 9, ans = 0;
    for(LL i = 0; i <= up; ++i) {
        if(i == 6) continue;
        ans += dfs(pos-1, false, limit && i == up);
    }
    return limit ? ans : (dp[pos][if6] = ans);
}
LL solve(LL x){
    memset(d, 0, sizeof(d));
    int len = 0;
    while(x) d[++len] = x % 10, x /= 10;
    return dfs(len, false, true);
}
int main(){
    memset(dp,-1,sizeof(dp));
    while(~scanf("%lld%lld", &n, &m)){
        printf("%lld\n", (m - solve(m)) - (n - 1 - solve(n-1)));
    }
    return 0;
}

AC代码2：递推版本

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n, m, dp[20][10], dit[20];
void init() {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1LL;
    for(int i = 1; i < 20; ++i) {
        for(int j = 0; j < 10; ++ j) {
            if(j == 6) continue;
            for(int k = 0; k < 10; ++k) {
                if(k == 6) continue;
                dp[i][j] += dp[i - 1][k];
            }
        }
    }
}
LL solve(LL x) {
    memset(dit, 0, sizeof(dit));
    int len = 0; LL ans = 0;
    while(x) {
        dit[++len] = x % 10;
        x /= 10;
    }
    for(int i = len; i >= 1; --i) {
        for(int j = 0; j < dit[i]; ++j) {
            if(j == 6) continue;
            ans += dp[i][j];
        }
        if(dit[i] == 6) break;
    }
    return ans;
}
int main(){
    init();
    while(cin >> n >> m) {
        cout << (m + 1) - solve(m + 1) - (n - solve(n)) <<endl;
    }
    return 0;
}

I.处女座的约会

题目描述:

处女座放完了”高利贷”，拿到了不少的资金，又可以和小姐姐约会啦！（之前不还是攒钱打比赛的吗）现在处女座拿到了一份宁波市旅游地图决定和小姐姐一起去玩耍。他们来到了动物园，去参观里面的动物。但是很不幸的是，他们在游玩的途中遇到了一只恶龙。恶龙长有n个头，但经过了处女座的调教，恶龙变得善良了一些。它的n个头每个头要么仍是邪恶的头，用“1”表示，要么已经变得善良，用“0”表示，因而恶龙的n个头就可以用n位01串来表示。而此时处女座要发挥自己的勇士形象，要把所有的龙头都变成 $ 0000 \cdots 00 $ 完全善良的龙头。每一次，他可以砍掉龙最右侧的一个头，同时龙会在最左侧长出新的一个头，以保证龙头数量不变。如果他砍掉的是一个1，即邪恶的头，他可以决定龙在最左侧会长出什么样的头；但如果他砍掉了一个善良的头，那么玻璃心的恶龙将会在左侧不受控制的长出一个随机的头，既可能是善良的头，也可能是邪恶的头，而且它总会与处女座作对，尽力的破坏他的计划。
现在给你一个恶龙头的初始状态，即一个01串，请帮助处女座判断一下，能否在有限步之内让全部的龙头都变成善良的龙头。

输入描述:

输入第一行T，表示用例组数。
之后T行，每行一个01串S表示龙头的初始状态，“0”表示善良的头，“1”表示邪恶的头。

输出描述:

对于每组数据，处女座能否将全部的龙头变成善良的头，可以的话输出“cnznb”，不可以则输出“ljcnz”（不含引号）。

输入

1
2

1
1111

输出

cnznb

备注:

$ T \leq 1000,|S| \leq 100 $。
注意，这个问题可能没有你想的那么简单。显然，处女座必须把一些1变成0，这样才能让1的数量减少并消失。但是如果只是简单的每次把1变成0，最终不见得能取胜。比如，如果龙头的状态是101，那么去掉最右边的1并选择在左边长出一个0，则龙头会变成010；再把010右边的0去掉后，如果左边仍长出一个1，则龙头又变回了101的状态，如此反复，将永远不能得到000。

思路：

博弈+大胆猜想！比赛时模拟了很多样例后，发现都是处女座牛逼，大胆交一发，显然是“cnznb”，怎么会是“ljcnz”。（滑稽）相关证明：趣题：由0和1构成的虫子

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int T; string str;
int main() {
    while(cin >> T){
        while(T--) {
            cin >> str;
            cout << "cnznb" << endl;
        }
    }
    return 0;
}