20190907爆零记

布满荆棘的人生 2023-10-11 04:52 24阅读 0赞

今天突然\\(\\rm pdf\\)题面了，认真打了打，于是自闭了

\\(\\rm T1\\)是个简单的结论题，给定\\(n,m,q\\)，求\\(\[1,q\]\\)里不能被\\(n\\times x+m\\times y\\)表示的数有多少个

一眼大凯的疑惑既视感

首先设\\(r=(n,m)\\)，能表示的数就一定是\\(r\\)的倍数，于是我们让\\(n=\\frac\{n\}\{r\},m=\\frac\{m\}\{r\}\\)，求一下\\(\[1,\\left \\lfloor \\frac\{q\}\{r\} \\right \\rfloor\]\\)内能被表示的数即可，让\\(q\\)减去这个数就是答案了

注意到现在\\(n\\perp m\\)，考虑小凯的疑惑中的结论，不能被表示的最大数是\\(n\\times m-n-m\\)，即一个数\\(c\\)能被表示，必定唯一存在\\(c=n\\times x+m\\times y\\)，且\\(x<m,y<n\\)

注意到\\(n\\leq 10^5,y<n\\)，于是考虑枚举这个\\(y\\)，于是在\\(\[m\\times y,\\left \\lfloor \\frac\{q\}\{r\} \\right \\rfloor\]\\)范围内所有\\(n\\)的倍数都能被表示出来，这样的数的个数显然有\\(\\left \\lfloor \\frac\{(\\left \\lfloor \\frac\{q\}\{r\} \\right \\rfloor-m\\times y)\}\{n\}\\right \\rfloor +1\\)个

最后注意到\\(0\\)也被视为能表示的数了，减掉即可

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define re register
    #define LL long long
    #define min(a,b) ((a)<(b)?(a):(b))
    inline int gcd(int a,int b) {
        return !b?a:gcd(b,a%b);
    }
    int T,n,m;
    LL q;
    int main() {
        freopen("simple.in","r",stdin);
        freopen("simple.out","w",stdout);
        scanf("%d",&T);
        while(T--) {
            scanf("%d%d%lld",&n,&m,&q);
            if(n>m) std::swap(n,m);
            int r=gcd(n,m);LL ans=q;
            n/=r,m/=r,q/=r;
            for(re int i=0;i<n&&1ll*m*i<=q;++i)
                ans-=(q-1ll*m*i)/n,ans--;
            printf("%lld\n",ans+1);
        }
        return 0;
    }

由于在最后二十分钟才推出结论而过于兴奋，让\\(q\\)对\\(n\\times m-n-m\\)取了一个\\(\\min\\)，而\\(ans\\)的初值设成了\\(\\min\\)之后的\\(q\\)，于是获得了\\(10\\rm pts\\)的好成绩

\\(\\rm T2\\)给定一棵树，边有边权，长度都为\\(1\\)，定义一条路径的架势为这条路径上所有边边权的\\(\\gcd\\)，要求对于任意\\(i\\in\[1,n\]\\)，求长度为\\(i\\)的路径的最大权值

\\(n\\leq 4\\times 10^5,w\\leq 10^6\\)

不难发现长度越小的路径，其最大权值也就越大，因此答案单调不降

考虑一个\\(O(nw)\\)的做法，即枚举\\(\\gcd\\)，求当前\\(gcd\\)下的最长路径；每次只走边权为\\(i\\)的倍数的边，找树上直径即可

这样每次跑一边整棵树太傻了，于是我们把边权为\\(i\\)的倍数的边都拿出来，跑树的直径即可，复杂度是所有边的约数个数和

代码

#include<bits/stdc++.h>
    #define re register
    #define max(a,b) ((a)>(b)?(a):(b))
    inline int read() {
        char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
        while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
    }
    std::vector<int> v[1000001];
    const int maxn=4e5+5;
    struct E{int v,nxt;}e[maxn<<1];
    int head[maxn],st[maxn],vis[maxn],top,num,cnt,n,T,tot;
    int rx[maxn],ry[maxn],ans[maxn],f[maxn],tax[maxn],dep[maxn];
    inline void add(int x,int y) {
        e[++num].v=y;e[num].nxt=head[x];head[x]=num;
        if(!vis[x]) st[++top]=x,vis[x]=1;
    }
    void dfs(int x,int fa,int o) {
        if(o) f[x]=1,tax[++cnt]=x;
        for(re int i=head[x];i;i=e[i].nxt) {
            if(e[i].v==fa) continue;
            dep[e[i].v]=dep[x]+1;
            dfs(e[i].v,x,o);
        } 
    }
    inline void getdis(int x) {
        cnt=0;dep[x]=0;dfs(x,0,1);int rt=tax[1];
        for(re int i=2;i<=cnt;++i) if(dep[tax[i]]>dep[rt]) rt=tax[i];
        dep[rt]=0;dfs(rt,0,0);
        for(re int i=1;i<=cnt;i++) tot=max(tot,dep[tax[i]]);
    }
    int main() {
        n=read();
        for(re int w,i=1;i<n;i++) {
            rx[i]=read(),ry[i]=read();
            w=read(),T=max(T,w);
            v[w].push_back(i);
        }
        for(re int i=1;i<=T;++i,tot=0,num=0) {
            for(re int j=i;j<=T;j+=i)
                for(re int k=0;k<v[j].size();k++)
                    add(rx[v[j][k]],ry[v[j][k]]),add(ry[v[j][k]],rx[v[j][k]]);
            for(re int j=1;j<=top;++j) {
                if(f[st[j]]) continue;
                getdis(st[j]);
            }
            ans[tot]=i;
            while(top) f[st[top]]=vis[st[top]]=head[st[top]]=0,top--;
        }
        for(re int i=n-1;i;--i) ans[i]=max(ans[i],ans[i+1]);
        for(re int i=1;i<=n;i++) printf("%d\n",ans[i]);
        return 0;
    }

\\(\\rm T3\\)给定\\(n,L,s\\)和一个严格上升的数组\\(\\\{x\_1,x\_2,...,x\_n\\\}\\)，需要求一个排列\\(p\\)，满足\\(p\_1=s\\)，且\\(p\_i<p\_\{i+1\}\\)恰有\\(L\\)项，最小化

\\\[\\sum\_\{i=2\}^n|x\_\{p\_i\}-x\_\{p\_\{i-1\}\}|\\\]

写了个假贪心之后果真假了，之后发现全场都假了

看了看[成爷的假贪心][Link 1]发现我们好像假的差不多，但是不知道为什么我\\(20\\rm pts\\)他\\(35\\rm pts\\)

正解非常巧妙

不妨考虑\\(s=1\\)的情况，如果我们要从\\(s\\)走到\\(n\\)，如果没有\\(L\\)的限制，最优的方案就是直接从\\(1\\)走过去，但是有了\\(L\\)的限制，就要求我们必须走一些回头路

首先\\(1\\)到\\(n\\)之间的所有线段都至少被经过了一次，由于我们必须走\\(L\\)次回头路，所有至少有\\(L\\)个\\(x\_i-x\_\{i-1\}\\)额外经过了两次，即从前面走回来再走回去，所以**从\\(1\\)走到\\(n\\)中间需要走\\(L\\)次回头路的最小花费就是\\(x\_n-x\_1\\)，加上前\\(L\\)小的\\(x\_i-x\_\{i-1\}\\)，显然\\(L\\)越小这个花费也就越小**

再来考虑终点不在\\(n\\)的情况，考虑枚举一个终点\\(e\\)，那么在\\(\[1,s\]\\)和\\(\[e,n\]\\)这两段里要花费的\\(L\\)次数就是\\(s-1+n-e\\)，同时里面的这些线段也会被经过两次

这样在两边的花费都尽量小，同时还能减小在\\(\[s,e\]\\)之间需要花费的\\(L\\)的次数；这个时候我们发现\\(\[s,e\]\\)的情况和\\(\[1,n\]\\)的情况是等价的，也就是也就是说我们需要维护\\(\[s,e\]\\)之间前\\(L-s+1-n+e\\)小的\\(x\_i-x\_\{i-1\}\\)

随着\\(e\\)的增大，我们发现影响的只有\\(x\_\{e\}-x\_\{e-1\}\\)这一条线段，于是我们用一个堆就能维护了

代码就不写了

从这次考试还是能看出自己非常垃圾了，首先就是在没有大样例的情况下挂题的概率趋近于1，还懒得去写暴力和搭拍，于是往往搞出来的题也挂的非常惨

时间分配上也非常弟弟，\\(\\rm T3\\)的假贪心写了一个多小时，\\(\\rm T1\\)推到最后才写出来，留给\\(\\rm T2\\)的时间就只够写个暴力了

之后还是智商太低了，\\(\\rm T1\\)这样的结论题，成爷\\(10\\rm min\\)就切了，我这种睿智选手搞到最后半个小时才搞出来，之后还写挂了；\\(\\rm T3\\)的贪心还看不出来假了，于是兴致盎然的写了好久

看来下次得对着成爷的屏幕白嫖了

转载于:https://www.cnblogs.com/asuldb/p/11484665.html

[Link 1]: http://39.100.60.248/2019/09/08/lolioi-2019-09-07-notes/