【题解】牛客练习赛61

迟到1h，险些掉分，呼~

A

数据范围很小，模拟签到题。

/*
* @Author: wxyww
* @Date: 2020-04-10 19:52:33
* @Last Modified time: 2020-04-10 20:02:50
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;

ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int h,a,H,A;
void solve() {
    int ans = 0;
    int HH = H;
    while(h > 0) {
        H = HH;
        while(h > 0 && H > 0) {
            H -= a;
            if(H <= 0) break;
            h -= A;
        }
        if(H <= 0) ans++;
    }
    printf("%d\n",ans);
}
int main() {
    int T = read();
    while(T--) {
        h = read(),a = read(),H = read(),A = read();
        if(a >= H) {puts("-1");continue;}
        solve();
    }

    return 0;
}

B

每当较少的数量*2<=较多的数量，就将较少的数量乘以2。算一下步数即可。

/*
* @Author: wxyww
* @Date: 2020-04-10 20:03:07
* @Last Modified time: 2020-04-10 20:05:18
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;

ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

int main() {
    int T = read();
    while(T--) {
        int n = read(),m = read();
        if(n > m) swap(n,m);
        int ans = 0;
        while(n && m) {
            ++ans;
            if(n + n <= m) n += n;
            else --n,--m;
        }
        printf("%d\n",ans);
    }
    return 0;
}

C

答案相同的题看做一个整体，统计出每个整体的大小。然后爆搜即可。
复杂度上限(k为整体的数量)

/*
* @Author: wxyww
* @Date: 2020-04-10 20:10:48
* @Last Modified time: 2020-04-10 20:15:24
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 100;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int v,nxt;
}e[N * N];
int head[N],ejs;
void add(int u,int v) {
    e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;
}

int vis[N],tot,a[N];

void dfs(int u) {
    a[tot]++;
    vis[u] = 1;
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(vis[v]) continue;
        dfs(v);
    }
}
int ans;
void solve(int pos,int na,int nb,int nc,int nd) {
    if(pos == tot + 1) {
        ans++;return;
    }
    if(a[pos] <= na)
        solve(pos + 1,na - a[pos],nb,nc,nd);
    if(a[pos] <= nb)
        solve(pos + 1,na,nb - a[pos],nc,nd);
    if(a[pos] <= nc)
        solve(pos + 1,na,nb,nc - a[pos],nd);
    if(a[pos] <= nd)
        solve(pos + 1,na,nb,nc,nd - a[pos]);
}
int main() {
    int na = read(),nb = read(),nc = read(),nd = read(),m = read();
    while(m--) {
        int x = read(),y = read();
        add(x,y);add(y,x);
    }
    for(int i = 1;i <= 12;++i) {
        if(!vis[i]) {
            ++tot;
            dfs(i);
        }
    }

    solve(1,na,nb,nc,nd);
    cout<<ans;
    return 0;
}

D

比较经典的一个思路就是。统计出号点到每个点的距离，统计出每个点到号点的距离。
当一条边反向时，直接用计算出必须经过这条边的最短路。
然后有一个问题，如果在计算的时候经过的这条边的正向边，现在反过来这条正向边不存在了，那不就错了吗？

这样可能确实会影响我们计算出的新最短路，但是题目问的是最短路是否会变短，我们只要上述情况不会导致最短路变短即可。

对于一条边，如果经过了此边，也就是，反向之后计算出的新路径长度为，所以这样路径长度显然比不经过此边的时候多了。所以并不会影响最终答案。

/*
* @Author: wxyww
* @Date: 2020-04-10 20:33:31
* @Last Modified time: 2020-04-10 20:46:10
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 200010;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int v,nxt,w,u;
}e[N];
int head[N],ejs;
void add(int u,int v,int w) {
    e[++ejs].v = v;e[ejs].u = u;e[ejs].nxt = head[u];head[u] = ejs;e[ejs].w = w;
}
ll dis1[N],dis2[N];
int vis[N];
queue<int>q;
void spfa(ll *dis,int S) {

    dis[S] = 0;
    q.push(S);
    while(!q.empty()) {
        int u = q.front();q.pop();vis[u] = 0;
        for(int i = head[u];i;i = e[i].nxt) {
            int v = e[i].v;
            if(dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                if(!vis[v]) vis[v] = 1,q.push(v);
            }
        }
    }
}

int main() {
    int n = read(),m = read();
    for(int i = 1;i <= m;++i) {
        int u = read(),v = read(),w = read();
        add(u,v,w);
    }

    memset(dis1,0x3f,sizeof(dis1));
    spfa(dis1,1);

    memset(head,0,sizeof(head));
    ejs = 0;
    memset(dis2,0x3f,sizeof(dis2));
    for(int i = 1;i <= m;++i)
        add(e[i].v,e[i].u,e[i].w);
    spfa(dis2,n);

    int Q = read();
    ll ans = dis1[n];

    while(Q--) {
        int x = read();
        if(dis1[e[x].u] + dis2[e[x].v] + e[x].w < ans) puts("YES");
        else puts("NO");
    }

    return 0;
}

E

首先想到二分答案。先二分一个。然后判断是否能找出至少个长度为的不相交的相同子串。

用表示前i个位置哈希值为j的不想交子串个数最多为多少。转移就是。显然爆炸。

考虑一个延时加入，用表示哈希值为的答案。当枚举到时才用更新。这样每次判断复杂度就成了

在加上外层套的二分答案复杂度。总的复杂度就是，理论上讲是可以在牛客上跑过去的。我没跑过去，只好用了

/*
* @Author: wxyww
* @Date: 2020-04-10 20:50:36
* @Last Modified time: 2020-04-10 21:07:19
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<unordered_map>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 200010;

ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
char s[N];

unordered_map<ull,int>ma;
ull hs[N],base[N],B = 27;
ull get(int l,int r) {
    return hs[r] - hs[l - 1] * base[r - l + 1];
}

int n,K,f[N];
bool check(int x) {
    ma.clear();
    memset(f,0,sizeof(f));
    for(int i = x;i <= n;++i) {

        if(i - x >= x) {
            ma[get(i - x - x + 1,i - x)] = max(f[i - x],ma[get(i - x - x + 1,i - x)]);
        }

        ull t = get(i - x + 1,i);
        f[i] = ma[t] + 1;
        if(f[i] >= K) return true;

    }
    return false;
}
int main() {
    n = read(),K = read();
    scanf("%s",s + 1);
    base[0] = 1;
    for(int i = 1;i <= n;++i) {
        hs[i] = hs[i - 1] * B + s[i] - 'a' + 1;
        base[i] = base[i - 1] * B; 
    }

    int l = 1,r = n,ans = 0;

    while(l <= r) {
        int mid = (l + r) >> 1;
        if(check(mid)) ans = mid,l = mid + 1;
        else r = mid - 1;
    }
    cout<<ans<<endl;

    return 0;
}

F

不会点分树，看完官方题解临时学了一发。

点分树其实就是将点分治过程中每个重心向下一层的重心连边。因为点分治最多递归层，所以点分树的树高不超过

然后对于点分树上每个店开一个动态开点线段树。维护子树中每种成熟度到当前点的最近距离。

修改和查询就从当前点暴力向上跳即可。

真的调了好久~

文末赋上一份自己写的数据生成器（纯随机），希望能帮助大家调题。(๑•ᴗ•๑)

/*
* @Author: wxyww
* @Date: 2020-04-11 08:19:33
* @Last Modified time: 2020-04-11 10:25:52
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 1000010,logN = 20,INF = 1e9 + 8;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int w,v,nxt;
}e[N << 1];
int head[N],ejs;
void add(int u,int v,int w) {
    e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;e[ejs].w = w;
}
//利用LCA求dist
int w[N],lca[N][logN + 1],dis[N],dep[N];
void dfs(int u,int fa) {
    dep[u] = dep[fa] + 1;
    for(int i = 1;i <= logN;++i)
        lca[u][i] = lca[lca[u][i - 1]][i - 1];

    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(v == fa) continue;
        dis[v] = dis[u] + e[i].w;
        lca[v][0] = u;
        dfs(v,u);
    }
}
int LCA(int x,int y) {
    if(dep[x] < dep[y]) swap(x,y);
    for(int i = logN;i >= 0;--i)
        if(dep[lca[x][i]] >= dep[y]) x = lca[x][i];
    for(int i = logN;i >= 0;--i)
        if(lca[x][i] != lca[y][i]) x = lca[x][i],y = lca[y][i];
    if(x != y) x = lca[x][0];
    return x;
}
int dist(int x,int y) {
    return dis[x] + dis[y] - 2 * dis[LCA(x,y)];
}
//点分树
int mx[N],siz[N],fa[N],vis[N];
vector<int>tmp;
void get(int u,int father) {
    siz[u] = 1;
    mx[u] = 0;
    tmp.push_back(u);
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(vis[v] || v == father) continue;
        get(v,u);
        siz[u] += siz[v];
        mx[u] = max(mx[u],siz[v]);
    }
}
int build(int u) {
    tmp.clear();
    get(u,0);
    int rt = 0;
    int k = tmp.size();
    for(int i = 0;i < k;++i) {
        if(mx[tmp[i]] <= k / 2 && (k - siz[tmp[i]]) <= k / 2) {
            rt = tmp[i];break;
        }
    }
    vis[rt] = 1;
    for(int i = head[rt];i;i = e[i].nxt) {
        int v = e[i].v;
        if(vis[v]) continue;
        fa[build(v)] = rt;
    }
    return rt;
}
//动态开点线段树
struct TREE {
    int ls,rs,val;
}tree[10000010];
int root[N],tot;
void update(int &rt,int l,int r,int pos,int w) {
    if(!rt) {
        rt = ++tot;
        tree[rt].val = INF;
    }
    if(l == r) {
        tree[rt].val = min(tree[rt].val,w);
        return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) update(tree[rt].ls,l,mid,pos,w);
    else update(tree[rt].rs,mid + 1,r,pos,w);
    tree[rt].val = min(tree[tree[rt].ls].val,tree[tree[rt].rs].val);
}
int query(int rt,int l,int r,int L,int R) {
    if(!rt) return INF;
    if(L <= l && R >= r) return tree[rt].val;
    int ans = INF;
    int mid = (l + r) >> 1;
    if(L <= mid) ans = min(ans,query(tree[rt].ls,l,mid,L,R));
    if(R > mid) ans = min(ans,query(tree[rt].rs,mid + 1,r,L,R));
    return ans;
}
int main() {
    int n = read(),m = read();
    for(int i = 1;i <= n;++i) w[i] = read();
    for(int i = 1;i < n;++i) {
        int u = read(),v = read(),w = read();
        add(u,v,w);add(v,u,w);
    }
    dfs(1,0);
    build(1);
    tree[0].val = INF;
    for(int i = 1;i <= n;++i) {
        int t = i;
        while(t) {
            update(root[t],1,10000,w[i],dist(t,i));
            t = fa[t];
        }
    }
    while(m--) {
        int opt = read();
        if(opt == 1) {
            int u = read(),x = read();
            int t = u;
            while(t) {
                update(root[t],1,10000,x,dist(t,u));
                t = fa[t];
            }
        }
        else {
            int u = read(),l = read(),r = read();
            int ans = INF,t = u;        
            while(t) {
                ans = min(ans,dist(u,t) + query(root[t],1,10000,l,r));
                t = fa[t];
            }
            if(ans > 1e9) puts("-1");
            else printf("%d\n",ans + ans);
        }
    }
    return 0;
}

F题数据生成器

/*
* @Author: wxyww
* @Date: 2020-04-11 09:55:37
* @Last Modified time: 2020-04-11 09:58:44
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;

ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int Rand(int l,int r) {
    return rand() % (r - l + 1) + l;
}
int main() {
    srand(time(0));
    int n = Rand(5,10),m = Rand(10,20);
    printf("%d %d\n",n,m);
    for(int i = 1;i <= n;++i) printf("%d ",Rand(1,10));
    puts("");
    for(int i = 2;i <= n;++i) {
        printf("%d %d %d\n",Rand(1,i - 1),i,Rand(1,10));
    }
    while(m--) {
        int opt = Rand(1,2);
        printf("%d ",opt);
        if(opt == 1) {
            printf("%d %d\n",Rand(1,n),Rand(1,10));
        }
        else {
            int l = Rand(1,10);
            printf("%d %d %d\n",Rand(1,n),l,Rand(l,10));
        }
    }

    return 0;
}
全部评论
F 动态开点线段树空间没有问题吗？
点赞 回复 分享
发布于 2020-04-11 14:01

相关推荐

11-12 10:23
合合信息_Agent数据工程师(准入职员工)
海康威视内推，海康威视内推码
岗位：武汉&nbsp;嵌入式开发timeline：8.30&nbsp;测评，10.9&nbsp;一面，10.11&nbsp;二面一面技术：自我介绍讲下实习经历平常怎么debug项目中有没有遇到什么问题，怎么解决的介绍一下学校经历了解数据结构吗？基本的数据结构？查找搜索效率？有什么方法可以提高效率？具体围绕数据结构问了很多RTOS，多任务操作反问：做存储固件的，具体的进来再分二面HR：北京线下，地点在北京研发中心，具体内容就是唠家常，一些HR面的基本问题销售工程师工作体验，总结累但成长很多。1.大家最先关注的就是HIK的工作压力，只能说体面厂没有辜负盛名！名不虚传！我来这边是销售岗，基本上每天都要差不多11点下班。因为销售不仅需要对接...
点赞 评论 收藏
分享
11-14 14:51
同济大学 前端工程师
点赞 评论 收藏
分享
09-19 13:59
门头沟学院 Java
刷到的还是让我遇上了
bro搁这写需求呢😅
用微笑面对困难：Trae一下，如果真成了，他用了直接发字节起诉代码版权，，这个代码不商用是没问题的如果没成也是情理之中的。
点赞 评论 收藏
分享
10-14 15:17
门头沟学院 运营
反秋招实习化
又不是啥大公司还搞这套，文字游戏真是玩明白了
少年郎as：这不把公司名贴出来那我可要喷你了哦
点赞 评论 收藏
分享
11-13 16:30
已编辑
腾讯云智研发_后台开发(实习员工)
点赞 评论 收藏
分享
评论
1
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 第一次找实习，我建议__ #
21983次浏览 292人参与
# 韶音科技求职进展汇总 #
60610次浏览 505人参与
# 从mentor身上学到了__ #
19333次浏览 303人参与
# 你怎么评价今年的春招？ #
142386次浏览 1388人参与
# 什么样的公司千万别去 #
16900次浏览 115人参与
# 上班摸鱼，你都在干些什么？ #
31415次浏览 227人参与
# 外出实习被同学举报 #
4192次浏览 32人参与
# 你投递的公司有几家约面了？ #
149816次浏览 982人参与
# 秋招的嫡长offer #
312754次浏览 1881人参与
# 秋招暂停，我将对以下公司做出处罚__ #
29821次浏览 137人参与
# 秋招结束之后的日子 #
106248次浏览 1017人参与
# 你认为工作的意义是什么 #
203582次浏览 1289人参与
# 秋招我要惩罚这些公司 #
3138次浏览 22人参与
# 打工人的至爽时刻or至暗时刻 #
42045次浏览 221人参与
# 你听到的“最没用”的秋招建议 #
21043次浏览 234人参与
# 如果今天是你的last day，你会怎么度过？ #
48245次浏览 299人参与
# 面试被问期望薪资时该如何回答 #
311889次浏览 1789人参与
# 2025秋招体验点评 #
47722次浏览 483人参与
# 除了主业以外，你还有哪些其他收入？ #
35347次浏览 302人参与
# 在国企工作的人，躺平了吗？ #
375594次浏览 3930人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务