【题解】牛客练习赛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-22 00:39
安徽大学 Java
点赞 评论 收藏
分享
11-23 18:53
合肥工业大学 golang
一字一句，带你读懂“外卖项目”
写在前面&nbsp;起因是这样的，当我准备了很长时间八股文准备找一段实习工作时，我接到了蔚来的面试，面试官的一个问题让我大脑瞬间就宕机了——你这个项目是怎么实现序列化的？我回想起八股文中序列化是什么，在什么地方需要使用序列化，为什么不推荐使用JDK自带的序列化......可我的项目中到底那里使用了，怎么使用的序列化哪？&nbsp;于是便有了今天这篇文章，我相信很多人像我一样，跟着某颜色的马敲了一遍外卖项目，但是到头来对这个项目却是一窍不通，现在如果抛开这个，让你自己设计一个项目，你会怎么做哪？你可能知道个大概，比如什么使用MVC架构、redis做缓存、MyBatis做持久化，可具体的细节你又要怎...
一字一句，带你读懂外卖项... 简历中的项目经历要怎么写 我的成功项目解析
点赞 评论 收藏
分享
10-09 10:06
蚌埠坦克学院 算法工程师
闺蜜公司
一人来一句闺蜜牛逼
尊尼获获：闺蜜在哪？
点赞 评论 收藏
分享
10-28 11:04
已编辑
美团_后端实习生(实习员工)
双非小子现在还没有offer
每天都在阴暗的爬行&nbsp;连面试都没有几个
一个2人：我说几个点吧，你的实习经历写的让人觉得毫无含金量，你没有挖掘你需求里的 亮点， 让人觉得你不仅打杂还摆烂。然后你的简历太长了🤣你这个实习经历看完，估计没几个人愿意接着看下去， sdk， 索引这种东西单拎出来说太顶真了兄弟，好好优化下简历吧
点赞 评论 收藏
分享
11-22 16:37
博尔塔拉职业技术学院 Java
华宇信息 java 一面面经
自我介绍?我是智科的?问我这个专业学了什么?为什么要学java?讲一下索引你项目中redis是怎么用的;除了java自带的集合类&nbsp;，你还用到了那些第三方的集合包?java的日期处理有哪些类&nbsp;;讲一下垃圾回收算法给你一个4GB的文件，算他的md5码，估计一下它的处理速度?秒级/毫秒级?数据库的分组select里有个group&nbsp;by知道吧？那个能举个例子吗？怎么用它？redis缓存预热了解吗？为什么要缓存预热？回答的解决缓存问题?触发器知道是什么吗？MySQl中的触发器也就是那个Trigger,与表有关，当表上的特定事件发生时，触发器会自动执行，可以用于数据复制(向表中插入一条数据然后会自动向另一...
查看13道真题和解析 秋招joker 软件开发笔面经
点赞 评论 收藏
分享
1 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
355335次浏览 3473人参与
# 我的实习求职记录 #
6087889次浏览 83708人参与
# 北方华创开奖 #
50280次浏览 451人参与
# 地方国企笔面经互助 #
5289次浏览 13人参与
# 职场吐槽大会 #
90846次浏览 752人参与
# 选完offer后，你后悔学本专业吗 #
23082次浏览 165人参与
# 百度开奖 #
215252次浏览 1366人参与
# ai智能作图 #
4120次浏览 78人参与
# 运营商笔面经互助 #
92846次浏览 1335人参与
# 实习中的菜狗时刻 #
278973次浏览 2741人参与
# 腾讯求职进展汇总 #
200545次浏览 1666人参与
# 如果有时光机，你最想去到哪个年纪？ #
25039次浏览 515人参与
# 当下环境，你会继续卷互联网，还是看其他行业机会 #
37833次浏览 345人参与
# 风评不好的公司，你会去吗？ #
20760次浏览 94人参与
# 上班苦还是上学苦呢？ #
91504次浏览 796人参与
# 大疆求职进展汇总 #
413823次浏览 2934人参与
# 国企还是互联网，你怎么选？ #
90225次浏览 703人参与
# 硬件兄弟们 甩出你的华为奖状 #
73845次浏览 609人参与
# 远程面试的尴尬瞬间 #
20581次浏览 296人参与
# 软件开发2024笔面经 #
2326132次浏览 48226人参与
# 如果中了500万，你会离职吗？ #
13747次浏览 145人参与
# 如何一边实习一边秋招 #
1000273次浏览 12701人参与
牛客网
牛客企业服务