投稿
  1. 高性能架构探索首页
  2. C/C++

2020.07.16模拟2

admin • • C/C++ • 阅读 125

A. Layout

题目描述

  • 和人类一样，奶牛们在打饭的时候喜欢和朋友站得很近。
  • 约翰的编号为1到n的n只奶牛正打算排队打饭。现在请你来安排她们，让她们在数轴上排好队。奶牛的弹性很好，同一个坐标可以站无限只奶牛，排队的顺序必须和她们编号的顺序一致。有M对奶牛互相爱慕，她们之间的距离不能超过一定的值，有K对奶牛互相敌视，她们的距离不能小于一定的值。
  • 那么，首尾奶牛的最大距离是多少呢？

输入格式

第一行输入 n,m,k, (0<m,k<=5000)
接下来m行每行三个整数xyz，表示编号为x和y的两头奶牛之间的距离最大不超过z
再接下来k行每行三个整数xyz，表示编号为x和y的两头奶牛之间的距离最少为z

输出格式

如果没有合理方案，输出-1
如果首尾两头牛的距离可以无限大，输出-2
否则输出一个整数表示首尾奶牛的最大距离

样例输入

4 2 1
1 3 10
2 4 20
2 3 3

样例输出

27

solution

考场上看出来spfa，但是差分约束是忘的一干二净，嘛也不记得，水了20分有点亏

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

inline int read(){
    int x = 0, w = 1;
    char ch = getchar();
    for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') w = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
    return x * w;
}

const int maxn = 100010;
struct node{
    int to, nxt, w;
}edge[maxn << 1];
int head[maxn], tot;
int n, m, k;

inline void add(int u, int v, int w){
    edge[++tot].to = v;
    edge[tot].nxt = head[u];
    edge[tot].w = w;
    head[u] = tot;
}

int dis[maxn];
int cnt[maxn];
bool vis[maxn];

inline int spfa(int u){
    queue<int> q;
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    q.push(u);
    dis[u] = 0;
    vis[u] = 1;
    while(!q.empty()){
        int v = q.front();
        q.pop();
        vis[v] = 0;
        for(int i = head[v]; i; i = edge[i].nxt){
            int to = edge[i].to;
            if(dis[to] > dis[v] + edge[i].w){
                dis[to] = dis[v] + edge[i].w;
                if(!vis[to]){
                    q.push(to);
                    vis[to] = 1;
                    if(++cnt[to] > n) 
                        return -1;
                }
            }
        }
    }
    if(dis[n] == 0x3f3f3f3f) return -2;
    return dis[n];
}

signed main(){
    n = read(), m = read(), k = read();
    for(int i = 1; i <= m; i++){
        int u = read(), v = read(), w = read();
        if(u > v) swap(u, v);
        add(u, v, w);
    }
    for(int i = 1; i <= k; i++){
        int u = read(), v = read(), w = read();
        if(u > v) swap(u, v);
        add(v, u, -w);
    }
    for(int i = 1; i < n; i++)
        add(i + 1, i, 0);
    for(int i = 1; i <= n; i++)
        add(0, i, 0);
    if(spfa(0) == -1) return cout << "-1n", 0;
    cout << spfa(1) << endl;
    return 0;
}

B.游戏

题目描述

Mirko 和 Slavko 爱玩弹球戏。在一个令人激动的星期五，Mirko 和 Slavko 玩了一把弹球游戏。Mirko 构建一个有向图，所有顶点最多有 1 条出边。弹球从 1
个顶点出发可以沿着一条边移动到它的邻接点，只要它存在，而且它会继续移动到后者的邻接点去，直到最后到达一个找不到出边的顶点才停下来。如果不存在这样的点，弹球可能无限运动下去。
为了确信 Slavko
理解游戏的规则，Mirko 将发起一系列询问，询问的类型如下：1 X：除非弹球陷入循环，弹球从X出发，最终将在哪个点停下来。
2 X：删除 X的出边（保证该边总是存在）

注意：询问是按顺序执行的。

输入格式

第一行包含一个正整数 N(1<=N<=300000),表示图的定点数。
第二行包含由空格隔开 N个正整数，第 i 个数表示从 i 顶点可以通过出边到达的定点编号。0表示该点没有出边。
接下来的一行包含 1个整数 Q(1<=Q<=300000),表示询问的次数。
格式如上所示。

输出格式

对于第 1 类询问，输出弹球停止时所在顶点编号,每行 1个，按照查询的顺序输出。如果弹球无法停止，则输出 CIKLUS.

样例输入

3
2 3 1
7
1 1
1 2
2 1
1 2
1 1
2 2
1 2

样例输出

CIKLUS
CIKLUS
1
1
2

solution

考试的时候嘛也没看出来，直接爆搜40分，就不粘代码了
正解是并查集，类似于打击犯罪？？？
所有顶点最多有一条出边，所以我们正好把边的去点当做父亲节点，因为存在删边，我们对原始的父子关系做一个备份，倒序处理的时候再依次把删掉的边还原回来。
这个题必须离线处理，在线只能DFS爆搜，离线的话要存储整个集合的状态以便删边之后还原

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

inline int read(){
    int x = 0, w = 1;
    char ch = getchar();
    for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') w = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
    return x * w;
}

const int maxn = 300010;
int ff[maxn], fa[maxn];
int a[maxn][3];
int n, m;

inline int find(int x, int cnt){
    if(cnt > n) return fa[x] = 0;
    if(x == fa[x]) return x;
    return fa[x] = find(fa[x], cnt + 1);
}

int main(){
    n = read();
//  cout << n << endl;
    for(int i = 1; i <= n; i++)
        fa[i] = i;
    for(int i = 1; i <= n; i++){
        int u = read();
        if(u!=0) fa[i] = ff[i] = u;
    }
    int q = read();
    for(int i = 1; i <= q; i++){
        a[i][0] = read();
        a[i][1] = read();
        if(a[i][0] == 2)
            fa[a[i][1]] = a[i][1];
    }
    for(int i = q; i > 0; --i){
        if(a[i][0] == 1)
            a[i][1] = find(a[i][1], 0);
        else fa[a[i][1]] = ff[a[i][1]];
    }
    for(int i = 1; i <= q; i++)
        if(a[i][0] == 1){
            if(a[i][1]) cout << a[i][1] << 'n';
            else cout << "CIKLUSn";
        }
    return 0;
}

C. 数字

题目描述

一个数字被称为好数字当他满足下列条件：它有 2∗n个数位，n 是正整数（允许有前导 0）。
构成它的每个数字都在给定的数字集合 S中。
它前 n位之和与后 n位之和相等或者它奇数位之和与偶数位之和相等。

例如对于 n=2,S={1,2}，合法的好数字有 1111,1122,1212,1221,2112,2121,2211,2222 这样 8种。
已知 n，求合法的好数字的个数 mod 999983。

Input

第一行一个数 n
接下来一个长度不超过 10的字符串，表示给定的数字集合（不存在重复的数字）。

Output

一行，一个整数表示合法的好数字的个数 mod 999983

Sample Input

2
0987654321

Sample Output

1240

Hint

对于 20%的数据，n≤7
对于 100%的数据，n≤1000,|S|≤10

solution

是个计数DP？？？没有印象，像新知识，直接听老姚的博客过掉，对于这个题已经丧失了思考能力……

（以下摘自@hszxyb）
令：dp[i][j] 表示长度为i且所有数字和为j的方案数。则有：

[dp[i][j]=sum_{j=0}^{i*Max_a_i}sum_{k=1}^{len(s) } dp[i-1][j-a[k]]
]

对于方案数我们分两种情况考虑：

前 n与后 n 和相同：将和相等，且个数为n的两个序列拼在一起即可，方案数为：

[ans+=sum_{i=0}^{n*Max_a_n} (dp[n][i])^2
]

奇数位上的数的和与偶数位上的数的和相等：这种情况也可以通过两个长度为 n
，且和相等的序列拼在一起，所以方案数和1一样。

但是上面的两种方案是有重复的情况的，即存在既符合情况1,也符合情况2的序列。

设左边奇数序列为 s1，偶数序列为 s2 ，那右边构造为奇数序列为 s2，偶数序列为 s1，则把这种情况减去即可。（容斥原理）

[ans-=sum_{i=0}^{frac {n+1}{2}*Max_a_n}(dp[frac{n+1}{2}][i])^2-sum_{j=0}^{frac{n}{2}*Max_a_n}(dp[frac{n}{2}][j])^2
]

前 n位数里，奇数位个数有 n+12 个，偶数位个数有 n2 个，(Max_{a_n})表示给出的集合的最大数，其实这里可以直接由9代替。

#include <bits/stdc++.h>
const int maxn=1e3+5,Mod=999983;
typedef long long LL;
LL dp[maxn][9*maxn];
int n,a[11];
int main() {
    char s[11];scanf("%d%s",&n,s+1);
    a[0]=strlen(s+1);
    for(int i=1;i<=a[0];++i)
        a[i]=s[i]-48;
    dp[0][0]=1;
    for(int i=1;i<=n;++i)//i个数
        for(int j=0;j<=i*9;++j)//i个数和为j，最大为i个9
            for(int k=1;k<=a[0];++k)
                if(j>=a[k])
                    dp[i][j]=(dp[i][j]+dp[i-1][j-a[k]])%Mod;
    LL ans=0;
    for(int i=0;i<=n*9;++i)//方案1,2之和
        ans=(ans+2*dp[n][i]*dp[n][i])%Mod;
    int len1=(n+1)/2,len2=n/2;
    LL ans1=0,ans2=0;
    for(int i=0;i<=len1 * 9;++i)//长度为(n+1)/2的奇数位序列的组合数
        ans1=(ans1+dp[len1][i]*dp[len1][i]%Mod)%Mod;
    for(int i=0;i<=len2 * 9;++i)//长度为n/2偶数位序列组合数
        ans2=(ans2+dp[len2][i]*dp[len2][i]%Mod)%Mod;
    ans=(ans-ans1*ans2%Mod+Mod)%Mod;
    printf("%lldn",ans);
    return 0;
}

D.水站

题目描述

已知有一个n层的水站:表示未操作之前第层的已有水量；
wi表示第i个水站能够维持或者储存的水的重量；
li表示在第i层进行减压放水操作所需的费用.
pi被压减放水层所储存的所有水都将流向下一层。
如果第i层的水量比li大,则这一层也会（自动）减压(不需要任何费用)。
现在想要使最后一层减压(第级)，求最少的花费。这个任务现在交给了你。

输入格式

每个输入的第一行包含一个自然数 n
接下来n行每行包含3个数w,l,p

输出格式

第一行输出所需的最小费用
第二行若干个整数，从小到大输出必须减压的层的编号。

样例输入

3
1000 1000 1
0 1000 2
2 10 100

样例输出

3
1 2

solution

可以说这个题付出了最大的代价拿到了最低的分数，拿出将近两个小时陪它玩
结果直接爆零，考试的时候完完全全记录下了心路历程
2020.07.16模拟2
可以看到，上来就把最正确能A的解法自己否掉了，然后xjb想了各种奇奇怪怪的算法，然后一个也没写出来。。。
正解
这道题的考试数据比较水，(O(n^2))能卡过
下午学长讲了之后，最优复杂度是(O(log_n))
所以数据该到了15万（好像说百万可过？？？）
前缀和优化+差分数组+二分答案
50行码力硬是憋不出来，自闭了



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

inline int read(){
    int x = 0,w = 1;
    char ch = getchar();
    for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') w = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
    return x * w;
}

const int maxn = 500010;
int w[maxn], p[maxn], l[maxn];
int n, ans = 0x7fffffff;
int s[maxn], c[maxn];

signed main(){
    n = read();
    for(int i = 1; i <= n; i++){
        w[i] = read();
        l[i] = read();
        p[i] = read();
        s[i] = s[i - 1] + w[i];
    }
    for(int i = 1; i <= n ;i++){
        int le = 1, r = i;
        while(le < r){
            int mid = (le + r) >> 1;
            if(s[i] - s[mid - 1] <= l[i]) r = mid;
            else le = mid + 1;
        }
        c[r] += p[i];
        c[i + 1] -= p[i];
    }
    int num=0;
    for(int i = 1; i <= n; i++){
        c[i] += c[i - 1];
        if(ans > c[i]) ans = c[i], num = i;
    }
    cout << ans << endl;
    for(int i = num; i <= n; i++){
        if(s[i]- s[num - 1] <= l[i])
            cout << i << " ";
    }
    return 0;
}

原文链接: https://www.cnblogs.com/rui-4825/p/13323703.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

    2020.07.16模拟2

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/367354

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年3月2日 下午5:43
下一篇 2023年3月2日 下午5:44

相关推荐