今天突然\(\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
    
     #include
     
      #include
      
       #include
       
        #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
        
         <=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
    
     #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
     
       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
     
    

\(\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}}|\]

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

看了看发现我们好像假的差不多，但是不知道为什么我\(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\)的贪心还看不出来假了，于是兴致盎然的写了好久

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