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

2020.07.18模拟4

admin • • C/C++ • 阅读 129

老姚出题我必糊
话说回来这套题虽然感觉考得不高，但是很有价值，都是那种看完题目有思路，码起来又拿不到满分（还是我tcl），这样的题改起来收获会更大点

A.渔民的烦恼

Descrption

在某个海边小国，大多数居民都是渔民，这个国家的所有城镇都沿直线分布在海边。渔民们捕获大量的海鱼，但就象世界上大多数的渔民一样，他们并不喜欢吃鱼，所以他们决定从邻国收养一些贫困家庭的小孩，让他们来帮着吃鱼，国家规定每个城镇收养的贫困儿童数量必须相等。
一条又长又直的公路贯穿整个海岸将所有的城镇连接了起来，所以每个城镇（除去第一个和最后一个）都直接和相邻的两个城镇相连接。一个小孩一年要吃掉一吨鱼，每个城镇捕获的鱼既可以在本地吃也可以运往其它城市吃，在运输过程中，每公里要上交一吨鱼作为过路费。
已知每个城镇一年的捕鱼产量，并假设运输方案是最佳的，计算最多能收奍多少个贫困儿童。

Input

第一行包含一个整数 N，其中 1≤N≤100,000，表示城镇总数。
接下来的 N行每行包含两个整数 A 和 B，其中 1≤A≤1,000,000,000,0≤B≤1,000,000,000
分别表示城镇的位置(坐标)和该城镇的捕鱼产量，所有城镇按其位置从小到大排序给出，注意问题一定存在正整数解。

Output

输出文件仅一行，包含一个整数表示每个城镇最多能够收养的贫困儿童数量。

Sample Input

4
20 300
40 400
340 700
360 600

Sample Output

415

solution

拿到题目一眼就看出来要二分答案
本来感觉挺简单的，代码也不长，可是码完之后样例没有过
以为问题不大，然后就想简单调一下就过了
于是一个小时过去了，mgl也在调，未果，果断弃掉
等到最后快要考试结束的时候
一不小心调过了，交上去40分
看下之前提交的0分，有点玄
正解
没错就是二分，然而少考虑了情况
只是考虑从别的地方运进来
没有算运出去
能水40还不错。。。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define int long long
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;
int fish[maxn];
int pos[maxn];
int n;

inline bool check(int x){
    int tmp = 0;
    for(int i = 1; i < n; i++){
        int y = tmp + fish[i];
        if(y < x)
            tmp = y - x - (pos[i + 1] - pos[i]);
        else{
            tmp = y - x - (pos[i + 1] - pos[i]);
            if(tmp < 0)
                tmp = 0;
        }
    }
    return fish[n] + tmp >= x;
}

inline int judge(int l, int r){
    while(l < r){
        int mid = (l + r + 1) >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

signed main(){
    n = read();
    int maxx = 0;
    for(int i = 1; i <= n; i++){
        pos[i] = read();
        fish[i] = read();
        maxx = max(maxx, fish[i]);
    }
    cout << judge(0, maxx) << endl;
    return 0;

}

B.乘车路线

Descrption

编号为 1∼N的 N 座城镇用若干仅供单向行驶的道路相连，每条道路上均有两个参数：道路长度(length)和在该条道路上行驶的费用（cost）。
BOB准备从城镇 1 出发到达城镇 N，但他目前只有 W 的钱，为此，你需要帮助他寻找一条从城镇 1 到城镇 N
在他能支付的前提下的一条最短路线。

Input

W N M
（N为城镇数目，2<=N<=100，M 为道路条数，1<=M<=10000,W 为钱的数目，0<=W<=1000）
随后的 M行每行为一条道路的信息，包含 4 个数值（u,v,w,cost），表示从城镇 u 到 v 有一条长度为 w 的单向道路，经过这条道路需要花费 cost 。(1<=u,v<=N,1<=w<=100,0<=cost<=100)

Output

输出最短长度，若无解，则输出“NO”；

Sample Input

5 6 7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2

Sample Output

11

solution

这个……挺玄学的，拿着一个无法证明正确性的算法
可以说是完全不对的算法水到了高达80分
一定是数据太水了，要加强数据迫害下一届
这个不正确的算法是，分别给dis和cost跑SPFA
分别限制然后就卡了80分～
正解
二维SPFA
加一维限制费用
\(dis[i][j]\) 表示\(i\)到源点花费了\(j\)的最短距离。

这个是错解



/*
记得删调试
读入顺序写错了调了20分钟
淦
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
//#define int long long
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 = 52000;

struct node{
    int to, nxt, w, c;
}edge[maxn << 1];
int head[maxn], tot;

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

int dis[maxn];
bool vis[maxn];
int cost[maxn];
int n, m, k;

inline void spfa1(int x){
    queue<int> q;
    memset(dis, 0x3f, sizeof dis);
//  memset(vis, 0, sizeof vis);
    q.push(x);
    dis[x] = 0;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int i = head[u]; i; i = edge[i].nxt){
            int v = edge[i].to;
            if(dis[v] > dis[u] + edge[i].w && cost[u] + edge[i].c <= k){
                dis[v] = dis[u] + edge[i].w;
                cost[v] = cost[u] + edge[i].c;
                if(!vis[v])
                    q.push(v), vis[v] = 1;
            }
        }
    }
}

int dis1[maxn];
int ans[maxn];
inline void spfa2(int x){
    queue<int> q1;
    memset(cost, 0x3f, sizeof cost);
    memset(vis, 0, sizeof vis);
    q1.push(x);
    cost[x] = 0;
    dis1[x] = 0;
    while(!q1.empty()){
        int u = q1.front();
        q1.pop();
        vis[u] = 0;
        for(int i = head[u]; i; i = edge[i].nxt){
            int v = edge[i].to;
            if(cost[v] > cost[u] + edge[i].c){
                cost[v] = cost[u] + edge[i].c;
                dis1[v] = dis1[u] + edge[i].w;
                ans[v] = min(dis[v], dis1[v]);
                if(!vis[v])
                    q1.push(v), vis[v] = 1;
            }
        }
    }
}

signed main(){
    k = read(), n = read(), m = read();
    for(int i = 1; i <= m; i++){
        int u = read(), v = read(), w = read(), c = read();
        add(u, v, w, c);
    }
    int minn = 0x7fffffff - 1;
    spfa1(1);
    spfa2(1);
    for(int i = 1; i <= n ;i++)
        minn = min(minn, cost[i]);
    if(minn > k) return cout << "NO\n", 0;
    cout << ans[n] << endl;
    return 0;
}

AC代码

#include <iostream>
#include <cstring>
#include <cstdio>
#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 = 52000;

struct node{
    int to, nxt, w, c;
}edge[maxn << 1];
int head[maxn], tot;

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

int dis[1005][10005];
bool vis[1005][10005];
int cost[maxn];
int n, m, k;
int ans = 0x7fffffff - 1;

inline void spfa(int x){
    memset(dis,0x3f,sizeof(dis));
    queue<pair<int,int> > q;
    dis[x][0] = 0;
    q.push(std::make_pair(x,0));
    while(!q.empty()){
        pair<int,int> t = q.front();
        q.pop();
        int u = t.first, money = t.second;
        vis[u][money] = 0;
        for(int i = head[u]; i; i = edge[i].nxt){
            int v = edge[i].to, w = edge[i].w, c = edge[i].c, y;
            if(money + c > k)continue;
            if(dis[v][money + c] > (y = dis[u][money] + w)){
                dis[v][money + c] = y;
                if(!vis[v][money + c]){
                    vis[v][money + c] = 1;
                    q.push(make_pair(v, money + c));
                }
            }
        }
    }
    int ans = 0x7fffffff - 1;
    for(int i = 0; i <= k; ++i)
        ans = min(ans, dis[n][i]);
    if(ans == 0x7fffffff - 1)
        printf("NO\n");
    else
        printf("%d\n",ans);
}

signed main(){
    k = read(), n = read(), m = read();
    for(int i = 1; i <= m; i++){
        int u = read(), v = read(), w = read(), c = read();
        add(u, v, w, c);
    }
    spfa(1);
    return 0;
}

C.Cloakroom

Descrption

有n件物品，每件物品有三个属性 a[i],b[i],ci
q个询问，每个询问由非负整数 m,k,s 组成，问是否能够选出某些物品使得：
对于每个选的物品i，满足 a[i]<=m 且 b[i]>m+s
所有选出物品的c[i]的和正好是 k

Input

第一行一个正整数 n(n<=1,000)，接下来 n 行每行三个正整数，分别表示 c[i],a[i],b[i] (c[i]<=1,000,1<=a[i]<b[i]<=109)
下面一行一个正整数 q(q<=1,000,000)，接下来 q 行每行三个非负整数 m,k,s(1<=m<=109,1<=k<=100,000,0<=s<=109)

Output

输出q行，每行为 "\(TAK "(yes)或"NIE"(no\))，第 i 行对应第 i 此询问的答案。

Sample Input

5
6 2 7
5 4 9
1 2 4
2 5 8
1 3 9
5
2 7 1
2 7 2
3 2 0
5 7 2
4 1 5

Sample Output

TAK
NIE
TAK
TAK
NIE

solution

考场没的思路，直接就输出其中一个骗了6分？？？

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

const int maxn=1e6+50,maxe=1e3+50,INF=0x3f3f3f3f;

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;
}


int n,q;
struct Node1{
    int a,b,c;
    inline bool operator < (const Node1 &A)const{
        return a<A.a;
    }
}a[maxn];

struct Node2{
    int m,k,s,ci;
    inline bool operator < (const Node2 &A)const{
        return m<A.m;
    }
}b[maxn];

int f[maxn],ans[maxn];

signed main(){
    n = read();
    for(int i = 1; i <= n; i++){
        a[i].c = read();
        a[i].a = read();
        a[i].b = read();
    }
    q = read();
    for(int i = 1; i <= q; i++){
        b[i].m = read();
        b[i].k = read();
        b[i].s = read();
        b[i].ci = i;
    }
    sort(a + 1, a + n + 1);
    sort(b + 1, b + q + 1);
    f[0] = INF;
    int j = 1;
    for(int i = 1; i <= q; i++){
        while(j <= n && a[j].a <= b[i].m){
            for(int k = 100000; k >= a[j].c; k--)
                f[k] = max(f[k], min(f[k - a[j].c], a[j].b));
            j++;
        }
        if(f[b[i].k] > b[i].m + b[i].s)
            ans[b[i].ci] = 1;
    }
    for(int i = 1; i <= q; i++){
        if(ans[i])  cout << "TAK\n";
        else cout << "NIE\n";
    }
    return 0;
}

D.星际网络

Descrption

LY星系有很多个星球。它们之间通过一个巨大的互联网进行通讯。随着信息时代的发展，旧的网络已经不能满足需求
于是 LY星系决定建设一个新的网络。
LY星系有很多个星球，有些星球一天有几十个小时，有些星球一天只有几个小时。但每个星球的一个小时都是一样长的。因此每个星球一天的长短都不一样，这就导致了一个问题：星球上的生物都是在白天工作夜晚 休息，因此每个星球每天都有上网高峰期和低峰期，当很多星球同时达到高峰期时，网络便会变得异常拥堵，进而带来延迟。所以 LY星系需要建设一个有足够大带宽的网络来避免这一问题。现在他们想知道，网络在一个小时内的最大流量是多少。

Input

输入数据的第一行为一个正整数N，表示 LY 星系共有 N个星球。
接下来N行，每行描述一个星球。对于每个星球的描述，开头为两个正整数 D,T，表示这个星球一天有 D 个小时，当前位于 T 时刻（即某一天已经过去了 T
小时）.接下来是D个正整数 q0,q1……qD−1，其中 qi 表示第 i 小时到第 i+1小时的流量。

Output

输出共一行，为一个整数 Ans，表示一个小时内的最大流量。

Sample Input

2
4 0 1 2 3 4
2 0 3 1

Sample Output

6

solution

考场直接数组模拟暴力，妥妥爆零
正解
首先观察到算法时间复杂度与n无关，因为一天的长度相同的星球都可以合并，至多24个。
若A,B星球的小时数互质，则 A 星球每个时刻与 B 星球每个时刻均有机会重合。
也就是说，若 A 星球的小时数与 1∼24 其他数都互质，则无论其他数字如何选择，这个星球都可以取到它的最大流量。
13,17,19,23 满足这个条件。其他数字暴力枚举到它们的最小公倍数即可。

#include <bits/stdc++.h>
typedef long long LL;
const int MAX = 55440;
int n,tmp[30];
LL ans,psum,sum[30][30];

void Calc(int D){
    LL Max = 0;
    for(int i = 1; i <= D; ++i)Max = std::max(Max,sum[D][i]);
    psum += Max;
}

int main(){
    scanf("%d",&n);
    for(int i = 1; i <= n; ++i){
        int D,T;scanf("%d%d",&D,&T);
        for(int j = 1; j <= D; ++j)scanf("%d",&tmp[j]);
        for(int st = T + 1,t = 1; t <= D; ++st,++t){
            if(st > D)st -= D;
            sum[D][t] += tmp[st];
        }
    }
    Calc(13);Calc(17);Calc(19);Calc(23);
    for(int i = 1; i <= MAX; ++i){
        LL cursum = 0;
        for(int j = 1; j <= 24; ++j){
            if(j == 13 || j == 17 || j == 19 || j == 23)continue;
            int cur = (i - 1) % j + 1;
            cursum += sum[j][cur];
        }
        ans = std::max(ans,cursum);
    }
    printf("%lld\n",ans + psum);
    return 0;
}

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

欢迎关注

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

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

    2020.07.18模拟4

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

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

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

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

赞 (0)
adminadmin
0 0
上一篇 2023年3月2日 下午6:18
下一篇 2023年3月2日 下午6:18

相关推荐