2017/10/7模拟赛总结

题目来自NOIP2016十连测第5场

T1 simple

一眼看上去像是exgcd 但是其实并没有这么麻烦
对于60分可以dp背包转移
看到n比m小很多
首先当 x<m 的时候只有可能是n的倍数除一下即可
然后当 x≥m 时可以枚举m的倍数在模n下相同的最小的一个然后计算贡献
当遇到相同模数的时候就可以结束循环了

#include<bits/stdc++.h>
using namespace std;
#define N 100010
int n,m;
long long q;
struct P1{
    int dp[N];
    void solve(){
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        int i,ans=0;
        for (i=0;i<=q;i++)
            if (dp[i]){
                if (i+n<=q) dp[i+n]=1;
                if (i+m<=q) dp[i+m]=1;
            }else ans++;
        printf("%d\n",ans);
    }
}P60;
struct P2{
    bool b[N];
    void solve(){
        if (n>m) swap(n,m);
        if (m>q){
            printf("%lld\n",q-q/n);
            return;
        }
        long long ans=q/n;
        int i;
        memset(b,0,sizeof(b));
        for (i=1;1LL*i*m<=q;i++){
            int mo=1LL*i*m%n;
            if (b[mo]) break;
            b[mo]=1;
            if (mo) ans+=(q-1LL*i*m)/n+1;
        }
        printf("%lld\n",q-ans);
    }
}P100;
int main(){
    int Case;
    scanf("%d",&Case);
    while (Case--){
        scanf("%d%d%lld",&n,&m,&q);
        if (q<=100000) P60.solve();
        else P100.solve();
    }
    return 0;
}

T2 walk

对于30分直接枚举每个点dfs一遍
注意到P60有 w≤100
枚举权值把所有权值是它倍数的边都找出来
然后做一波树形dp 把可能的路径长度算出来
注意不需要存当前路径长度是否可行对于一个点来说它子树内路径长度的可能值一定是连续的
也就是 [1,maxlen] 都可以取到那么就只存一个 maxlen （也就是直径）即可
收集子树能到达的最大深度即可 O(wn)

这一种做法每次把所有边都遍历了一遍这样当然会很慢
如果每次都把需要的边提出来呢？
事先把所有边存到权值对应的vector里
每枚举一个因子可以找它的倍数然后重新建图
这样会快很多据说时间大约为 O(n1.5) 但是远远不到

#include<bits/stdc++.h>
using namespace std;
#define N 400010
#define M 1000010
void rd(int &x){
    char c;x=0;
    while (c=getchar(),c<48);
    do x=(x<<1)+(x<<3)+(c^48);
    while (c=getchar(),c>=48);
}
struct road{
    int x,y;
};
vector<road>V[M];
struct edge{
    int nxt,t;
}e[N<<1];
int head[N],tot,Mx,sum,dep[N],ans[N],tar,tim[N],vis[N],rec[N<<1];
void add_edge(int x,int y){
    if (tim[x]<tar) head[x]=-1,tim[x]=tar;
    e[tot]=(edge){head[x],y};
    head[x]=tot++; 
}
int dfs(int x,int f){
    vis[x]=tar;
    dep[x]=dep[f]+1;
    int i;
    int Mx1=dep[x],Mx2=dep[x];
    for (i=head[x];~i;i=e[i].nxt){
        int to=e[i].t;
        if (to==f) continue;
        int t=dfs(to,x);
        if (t>=Mx1) Mx2=Mx1,Mx1=t;
        else if (t>Mx2) Mx2=t;
    }
    sum=max(sum,Mx1+Mx2-dep[x]*2);
    return Mx1;
}
int main(){
    int i,j,k,n;
    rd(n);
    for (i=1;i<n;i++){
        int x,y,z;
        rd(x),rd(y),rd(z);
        V[z].push_back((road){x,y});
        Mx=max(Mx,z);
    }
    for (i=1;i<=Mx;i++){
        sum=tot=0; tar=i;
        int h=0;
        for (j=i;j<=Mx;j+=i)
            for (k=0;k<V[j].size();k++){
                add_edge(V[j][k].x,V[j][k].y);
                add_edge(V[j][k].y,V[j][k].x);
                rec[++h]=V[j][k].x;
                rec[++h]=V[j][k].y;
            }
        for (j=1;j<=h;j++){
            int x=rec[j];
            if (tim[x]==tar && vis[x]<tar) dfs(x,x);
        }
        ans[sum]=i;
    }
    for (i=n-1;i;i--) ans[i]=max(ans[i],ans[i+1]);
    for (i=1;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
}

T3 travel

贪心
首先处理-1 S!=1 且 L=0 或 S!=n 且 L=n−1 这两种情况
切成n-1条 [i,i+1] 的线段
如果起点 S =1 终点 T =n
那么所有线段都至少走一次且至少有L条走了至少3次

不在两端的时候，不妨假设 S 在 T 的前面。显然 S 前面的线段和 T 后面的线段一定都至少经过两次，而且存在方案能让 S 前和 T 后一共用掉 n−T+S−1 个 L ，并且每条线段只经过两次。这样不仅能减少 [S,T] 中间走 L 的次数，而且也让 S 和 T 两侧的花费尽量小。
S 在 T 后面的情况只要全部翻一下就好了

为了让花费最少贪心地取长度小的线段
枚举i的时候每次只有一条线段发生变化直接一开始sort一遍中间维护sum即可
O(n∗log2n)

#include<bits/stdc++.h>
using namespace std;
#define N 200010
#define INF (0x3f3f3f3f3f3f3f3f)
int n,a[N],ord[N];
bool mark[N];
struct node{
    int x,y;
}Q[N];
bool cmp(node _,node __){return _.x<__.x;}
void solve(int S,int L,long long &ans,int *A){
    int h=0,i,j,k;
    if (S-1>=L){
        ans=1LL*a[n]-a[1]+a[S]-a[1];
        for (i=S-1;i>S-L;i--) A[++h]=i;
        for (i=1;i<=S-max(L,1);i++) A[++h]=i;
        for (i=S+1;i<=n;i++) A[++h]=i;
        return;
    }
    L-=S-1;
    if (n-S-1==L){
        ans=1LL*a[n]-a[1]+a[S]-a[1]+a[n]-a[S+1];
        for (i=S-1;i;i--) A[++h]=i;
        for (i=n;i>S;i--) A[++h]=i;
        return;
    }
    int h1=0;
    for (i=S+1;i<n-1;i++) Q[++h1]=(node){a[i+1]-a[i],i+1};
    sort(Q+1,Q+1+h1,cmp);
    for (i=1;i<=h1;i++) ord[Q[i].y]=i;
    long long Mn,sum=0;
    int pos=n,rec=L,t=L;
    for (i=1;i<=L;i++) sum+=Q[i].x;
    Mn=sum*2;
    for (i=n-1;i>=n-L;i--){
        sum-=ord[i]<=t?Q[ord[i]].x:Q[t--].x;
        while (t && Q[t].y>=i) t--;
        if (sum*2+a[n]-a[i]<Mn){
            Mn=sum*2+a[n]-a[pos=i];
            rec=t;
        }
    }
    ans=1LL*a[n]-a[1]+a[S]-a[1]+Mn;
    memset(mark,0,sizeof(mark));
    for (i=S-1;i;i--) A[++h]=i;
    for (i=S+2;i<pos;i++)
        if (ord[i]<=rec) mark[i]=1;
    for (i=S+1;i<pos;i=j){
        for (j=i+1;j<pos && mark[j];j++);
        for (k=j-1;k>=i;k--) A[++h]=k;
    }
    for (i=n;i>=pos;i--) A[++h]=i;
}
long long ans1,ans2;
int ANS1[N],ANS2[N];
int main(){
    int k,S,i;
    scanf("%d%d%d",&n,&k,&S);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    if (k==n-1 && S!=n){
        printf("-1\n");
        return 0;
    }
    if (!k && S!=1){
        printf("-1\n");
        return 0;
    }
    solve(S,k,ans1,ANS1);
    for (i=1;i<=n/2;i++) swap(a[i],a[n-i+1]);
    for (i=1;i<=n;i++) a[i]=-a[i];
    solve(n-S+1,n-1-k,ans2,ANS2);
    if (ans1<=ans2){
        printf("%lld\n",ans1);
        for (i=1;i<n;i++) printf("%d ",ANS1[i]);
    }else{
        printf("%lld\n",ans2);
        for (i=1;i<n;i++) printf("%d ",n-ANS2[i]+1);
    }
    return 0;
}

Date:2017/10/9
By CalvinJin

秒客网

2017/10/7模拟赛总结

相关文章