A题 Simple

时间限制：1000ms | 空间限制：256MB

问题描述

对于给定正整数\(n,m\),我们称正整数\(c\)为好的,当且仅当存在非负整数\(x,y\)使得\(n×x+m×y=c\)。

现在给出多组数据，对于每组数据，给定\(n,m,q\),求\([1,q]\)内有 多少个正整数不是好的。

输入格式

第一行,一个整数\(T\)表示数据组数。

接下来每行三个数,分别表示\(n,m,q\),即一组询问。

输出格式

对于输入的每组数据,输出一行表示答案。

数据规模

对于30%的数据，\(n,m,q\le100\);

对于60%的数据，\(n,m,q\le100000\);

对于100%的数据，\(n\le10^5,m\le10^9, q\le10^{18} ,T\le10\);

样例

样例输入

2

78 100 4

70 3 34

样例输出

4

23

题解

先上60分代码代码，当我们选取\(1到q\)中的某一个数\(i\)时，如果\(i\)是好的，则必然满足\(i\)>\(min(n,m)\)。这时我们让\(i\)减去\(max(n,m)\)的\(j\)倍得到一个数\(x\),若\(x\)%$ min(n,m)=0$就可以说明这个数是一个好数。

#include
    
     using namespace std;inline char get(){    static char buf[30],*p1=buf,*p2=buf;    return p1==p2 && (p2=(p1=buf)+fread(buf,1,30,stdin),p1==p2)?EOF:*p1++;}inline long long read(){    register char c=get();long long f=1,_=0;    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();    return _*f;}//利用fread优化的超级快读↑long long n,m,q;long long good;bool pd;long long t;int main(){    //freopen("1.txt","r",stdin);    t=read();    //cout<
     
      <
     
    

因为各种玄学优化可以得到60分。这个时候让我们换一种思路：

首先考虑的是dp,这个时候看下数据范围\(q\le10^{18}\),很显然不行。如果用数位dp的话限制条件又过多，于是pass掉dp的思路。

稍微思考一下公式，\(nx+my=c\)，我们令\(n>m\)，则一定有\(n=m*k+t\)；由于\(m\le100000\),则一定存在\(t<=100000\)。

这时我们用一个数组f[x]记录满足\(n*j\)%\(m=x\)里最小的值\(n*j\)。因为\(x\)的值最大为100000，所以f[x]的值最后总会循环出现。再稍加推导就可以知道：

若一个数\(c\)是好的，那么他的倍数\(c*k\)也一定是好的。

那么我们让\(ans+=(q/c)\)

问题还可以进一步简化。

我们知道一定存在至少一个\(f_i≠0\)

这时我们保证好数\(c\)中一定有至少0个\(n\)

那么我们就让\(c-f_i\),此时即可保证\(c\)一定是\(n\)的倍数。剩余的量全部分配给\(m\)即可。也就是\(ans+=(q-f[i])/m+1\)；

附上代码

#include
    
     #define ll long longusing namespace std;inline char get(){    static char buf[30],*p1=buf,*p2=buf;    return p1==p2 && (p2=(p1=buf)+fread(buf,1,30,stdin),p1==p2)?EOF:*p1++;}inline ll read(){    register char c=get();register ll f=1,_=0;    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();    return _*f;}ll f[100005];ll n,m,q;int main(){    //freopen("1.txt","r",stdin);    ll t;    t=read();    //cout<<1<
     
      q && m>q)printf("%lld\n",q);        else if(n>q && m<=q)printf("%lld\n",q-q/m);        else{            for(register int i=0;i<100005;i++)f[i]=-1;//单纯for循环似乎复杂度比memset低一些?            for(register int i=0;;i++){                ll now=n*i;                if(f[now%m]!=-1)break;                f[now%m]=now;            }             ll ans=0;            for(register int i=0;i
      
       =0))ans+=(q-f[i])/m+1;            }            printf("%lld\n",q-ans+1); //因为c的取值是[1,q],也就是说 n*x+y*m=c => x,y不同为0        }    }    return 0;}
      
     
    

B题 Walk

时间限制：2000ms | 空间限制：256MB

问题描述

给定一棵有\(n\)个节点的树，每条边的长度为1，同时有一个权值\(w\)，定义一条路径的权值为路径上所有边的权值的最大公约数，现在对于任意\(i∈[1,n]\)，求树上所有长度为\(i\)的简单路径中权值最大的值。如果不存在长度为i的路径则输出0。

输入格式

第一行,一个整数\(n\)表示树的大小

接下来\(n-1\)行，每行三个整数\(u,v,w\)表示\(u\)和\(v\)之间有一条权值为\(w\)的边。

输出格式

对于每种长度,输出一行,表示答案。

数据规模

对于30%的数据，\(n\le1000\);

对于额外30%的数据，\(w\le100\);

对于100%的数据，\(n\le4*10^5,1\le u,v\le n,w\le10^6\);

样例

样例输入

3

1 2 3

1 3 9

样例输出

3

9

0

题解(转,不会树DP很多年QAQ)

这道题我们可以考虑枚举最大公因数，然后求最大公因数为i的最长链。这个需要怎么办呢？我们考虑将每条边拆成因数条边，要是一次性加入的话数量会炸飞，所以我们每次将是当前公因数倍数的边加入，然后求树上的最长链。然后用当前的公因数更新长度为最长链的长度的答案。求解后将数组清零，重复利用。

有些长度可能不会出现在最长链中，因为他是构成最长链的一部分，所以如果这个长度的答案<长度大于他的答案的话，就要将长度大于他的答案给他，从大到小枚举\(ans[i]=max(ans[i],ans[i+1])\)

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define N 800003#define M 1000006using namespace std;int head[M],nxt1[N],x1[N],y2[N],cnt,sz,ans[N];int point[M],nxt[N],v[N],tot,st[N],top,vis[N],len;int n,m,mark;void add(int k,int x,int y){    cnt++; nxt1[cnt]=head[k]; head[k]=cnt; x1[cnt]=x; y2[cnt]=y;}void add1(int x,int y){    tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;    tot++; nxt[tot]=point[y]; point[y]=tot; v[tot]=x;    st[++top]=x; st[++top]=y;}int dfs(int x,int fa){    vis[x]=sz;    int l=0,r=0;    for (int i=point[x];i;i=nxt[i])     if (vis[v[i]]!=sz&&v[i]!=fa){        int t=dfs(v[i],x);        if (t+1>l) r=l,l=max(l,t+1);        else if (t+1>r) r=max(r,t+1);     }    len=max(len,l+r);    return l;}int main(){    freopen("a.in","r",stdin);    freopen("my.out","w",stdout);    scanf("%d",&n);    for (int i=1;i
         
          =1;i--) ans[i]=max(ans[i],ans[i+1]); for (int i=1;i<=n;i++) printf("%d\n",ans[i]);}
         
        
       
      
     
    

C题 Travel

时间限制：1000ms | 空间限制：256MB

问题描述

给定一个长度为\(n\)的序列\(x_1,x_2,...,x_n\)。每一次 Lyra 可以选择向左跳到任意一个还没到过的位置，也可以向右跳到任意一个还没到过的位置。如果现在Lyra在格子\(i\)，她下一步跳向格子\(j\)，那么这次跳跃的花费为\(|xi−xj|\)。注意，跳意味着格子\(i\)和格子\(j\)中间其他的格子都不会被这次跳跃影响。并且，Lyra不应该跳出边界。

Lyra的初始位置在格子\(s\)。Lyra将会在到访过所有格子恰好一次之后，在某个位置停下来，这样就完成了任务。

Lyra想知道如果她一共向左跳了\(L\)次，那么她要完成任务的最小总花费是多少，并希望你输出任意一种花费最小的方案。特殊的，如果 Lyra 没有办法完成任务，请输出一行 \(−1\)。

输入格式

第一行，三个整数\(n,L,s\)，分别表示序列的大小，向左走的次数，和初始位置。

第二行，\(n\)个数字，表示序列\(x_i\)。

输出格式

第一行，一个数字，表示答案。

如果能完成任务，则第二行，输出\(n-1\)个数字，表示方案。注意，Lyra 初始的位置已经确定了，所以不要输出。

数据规模

对于所有数据，都满足\(x_1<x_2<⋯<x_{n−1}<x_n，1≤s≤n，0≤L≤n_1\)。

样例

样例输入

3 1 2

1 2 3

样例输出

3

1 3

题解

先上15分的代码：

#include
    
     using namespace std;int main(){    cout<<-1<
    

足以说明数据有多水。

好的不皮了，我们来讲正解。

首先当\(x_i=i\)时，数列是等差的递增数列，每个的间距相同，所以我们肯定是考虑尽量的不走回头路，但是因为必须要向左走\(L\)步，所以至少有\(L\)段要被经过三次，那么我们从起点一直向左跳，跳到不能再跳为止，如果此时还是不够的话，我们就再跳到起点的右边正好多出剩下\(L\)步的为止，然后再向左跳，最后在向右跳即可。如果连续向左跳会多，那就考虑间隔的跳最终跳到头再转弯即可。-1的情况非常好处理，当\(l=0\)但是\(s≠1\)的时候，是没有合法路径的。同理\(l=n-1\)，\(s≠n\)也是没有合法路径的。

常规情况比较难考虑，让我们先来考虑特殊情况。当\(s=1\)的时候，显然答案的下界是 \(x_n-x_1\)，就是从最左边按次序一直跳到最右边，不过L>0的时候就不能这么做了。答案要求最小也就是说要尽量少走回头路。假如我们在\(n\)这个位置停下，那么中间就需要走一些回头的路类来用掉\(L\)，我们把所有\(i\)到\(i+1\)之间的区间看成一个线段。跳的路径相当于对线段进行覆盖。显然所有的线段都必须覆盖至少1次，而至少有\(L\)个线段至少覆盖3次。

但是实际情况中，起点不一定是1，终点也不一定是\(n\)。我们假设终点\(t\)再起点\(s\)的左边，那么\([1,s-1][t+1,n]\)中的点至少都需要经过两次，如果能在这两段中用掉较多的\(L\)，那我们中间剩下的L就会少，这样在好不过。以为中间\([s,t]\)这一段的处理就相当于是上面[1,n]的处理，中间的线段都会被覆盖三次。那么两边最多会向左走\(n-t+s-1\)步，如果\(n-t+s-1>=L\)，那么中间的不需要向左走，直接一步一步的跳就好了。如果不够\(L\)步的话就考虑从中选取差值小的线段让其长度*3即可。然后根据对称原则，在计算终点在起点左边的情况，这时候其实就是向右跳\(n-L-1\)步，向上面一样处理即可。

然后我们就可以通过枚举终点，来更新答案。对于上面中起点相对位置的两种情况，我们单独看。每次就是在上一起点的基础上中间加入\([i,i+1]\)，然后\([t+1,n]\)的长度减小\([i,i+1]\)，我们用小根堆维护，每次都尽可能利用小的。注意有可能存在无法满足答案的情况，就是堆中不够。

还需要注意的是中的段的头尾两条线段不能使用，因为无论怎么跳都没法满足，会影响两边的跳法。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long LL;typedef pair
          
            mp;#define pb push_backconst LL inf = 1ll<<50;const int maxn = 200005;int n,l,s,pos[maxn];int x[maxn],ans1[maxn];int y[maxn],ans2[maxn];mp ord[maxn];bool tag[maxn];LL solve(int n,int l,int s,int x[],int ans[]) { int cnt=0,tot=0; if (l
           
            s-l;i--) ans[++cnt]=i; for (int i=1;i<=s-l;i++) if (i!=s) ans[++cnt]=i; for (int i=s+1;i<=n;i++) ans[++cnt]=i; return (LL)x[n]-x[1]+x[s]-x[1]; } l-=s-1; if (l==n-s-1) { for (int i=s-1;i>=1;i--) ans[++cnt]=i; for (int i=n;i>s;i--) ans[++cnt]=i; return (LL)x[n]-x[1]+x[s]-x[1]+x[n]-x[s+1]; } for (int i=s+1;i
            
             =n-l;i--) { if (pos[i]<=p) sum-=ord[pos[i]].first; else sum-=ord[p--].first; while (p&&ord[p].second>=i) --p; if (sum*2+x[n]-x[i]
             
              =1;i--) ans[++cnt]=i; for (int i=s+2;i
              
               i;j--) ans[++cnt]=j; ans[++cnt]=i;i=tmp-1; } for (int i=n;i>=e;i--) ans[++cnt]=i; return (LL)x[n]-x[1]+x[s]-x[1]+minv;}int main(){ #ifndef ONLINE_JUDGE freopen("travel.in","r",stdin); freopen("travel.out","w",stdout); #endif scanf("%d %d %d",&n,&l,&s); for (int i=1;i<=n;i++) scanf("%d",&x[i]); for (int i=1;i<=n;i++) y[i]=-x[n-i+1]; if (s!=1&&l==0) {puts("-1");return 0;} if (s!=n&&l==n-1) {puts("-1");return 0;} LL cost1=solve(n,l,s,x,ans1); LL cost2=solve(n,n-1-l,n-s+1,y,ans2); if (cost1