2018 NOIP集训(一)

作者: 影踪派熊猫人武僧 | 来源:发表于2018-10-14 20:24 被阅读34次

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<bits/stdc++.h>
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<<t<<endl;
    while(t--){
        good=0;
        n=read();m=read();q=read();
        if(n==1 || m==1){
            printf("0\n");
            continue;
        }//特判
        if(n<m)swap(n,m);
        //cout<<1<<endl;
        for(register long long i=m;i<=q;i++){
            pd=0; 
            for(register long long j=0;j*n<=i;j++){
                if((i-(j*n)) % m==0){
                    good++;
                    break;
                }
            }
        }
        printf("%lld\n",q-good);
    }
    return 0;
}

因为各种玄学优化可以得到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<bits/stdc++.h>
#define ll long long
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 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<<endl;
    while(t--){
        n=read();m=read();q=read();
        if(n<m)swap(n,m);
        if(n>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<m;i++){
                if(f[i]!=-1&&(q-f[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<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N 800003
#define M 1000006
using 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<n;i++)
     {
        int a,b,c; scanf("%d%d%d",&a,&b,&c);
        add(c,a,b);
     }
    for (int i=1;i<=1000000;i++){
        for (int j=i;j<=1000000;j+=i)
         for (int k=head[j];k;k=nxt1[k])
          add1(x1[k],y2[k]);
        mark=i; ++sz; len=0;
        for (int j=1;j<=top;j++)
         if (vis[st[j]]!=sz) dfs(st[j],0);
        ans[len]=max(ans[len],i);
        for (int j=1;j<=top;j++)
         point[st[j]]=0;
        tot=0; top=0;
    }
    for (int i=n;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<bits/stdc++.h>
using namespace std;
int main(){
    cout<<-1<<endl;
    return 0;
}

足以说明数据有多水。
好的不皮了，我们来讲正解。
首先当 $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 <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <string.h>
#include <vector>
using namespace std;

typedef long long LL;
typedef pair<int,int> mp;
#define pb push_back
const 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) {
        for (int i=s-1;i>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-1;i++) ord[++tot]=mp(x[i+1]-x[i],i+1);
    sort(ord+1,ord+tot+1);
    for (int i=1;i<=tot;i++) pos[ord[i].second]=i;
    LL minv=inf,sum=0;int e,j;
    for (int i=1;i<=l;i++) sum+=ord[i].first;
    minv=sum*2;e=n;j=l;
    
    for (int i=n-1,p=l;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]<minv) {
            minv=sum*2+x[n]-x[i];e=i;j=p;
        }
    }
    
    memset(tag,false,sizeof tag);
    for (int i=s-1;i>=1;i--) ans[++cnt]=i;
    for (int i=s+2;i<e;i++) if (pos[i]<=j) tag[i]=true;
    for (int i=s+1;i<e;i++)
    if (!tag[i+1]) ans[++cnt]=i;
    else {
        int tmp=i+1;while (tag[tmp]) ++tmp;
        for (int j=tmp-1;j>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<cost2) {
        printf("%lld\n",cost1);
        for (int j=1;j<n;j++)
            printf("%d ",ans1[j]);
    }
    else {
        printf("%lld\n",cost2);
        for (int j=1;j<n;j++)
            printf("%d ",n-ans2[j]+1);
    }
    return 0;
}

2018 NOIP集训(一)

A题 Simple

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

问题描述

输入格式

输出格式

数据规模

样例

题解

附上代码

B题 Walk

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

问题描述

输入格式

输出格式

数据规模

样例

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

C题 Travel

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

问题描述

输入格式

输出格式

数据规模

样例

题解

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

动态规划