UOJ Logo gaolinxiang的博客

博客

NOIP2017提高组题解

2018-01-07 21:40:47 By gaolinxiang

前言

NOIP2017提高组可能是NOIP提高组有史以来考察的知识点最偏僻的一次。

于是本蒟蒻就想在这里讲一讲这些奇葩赛题都怎么做。

D1T1 小凯的疑惑

题目大意就是给定$a$和$b$，$(a,b)=1$，求不能表示为 $(ax+by)$的数的最大值。

经过推导或打表找规律，我们发现答案就是$ab-a-b$。于是就做完了。

注意：开long long！

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll p,q;
int main () {
    scanf ("%lld%lld",&p,&q);
    printf ("%lld\n",p*q-p-q);
    return 0;
}

[加强版]老凯的疑惑

题目大意不变，但要求$x$和$y$都必须是正整数。

经过推导或打表找规律，我们发现答案就是$ab$。于是就做完了。

注意：开long long！

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll p,q;
int main () {
    scanf ("%lld%lld",&p,&q);
    printf ("%lld\n",p*q);
    return 0;
}

D1T2 时间复杂度

题目本质就是一个大模拟，无非就是先判ERR再分析时间复杂度。

这题只要注意细节就好了。

细节1：F循环

F i a b (a>b)      O(0)
F i n b            O(0)
F i a b (a<=b)     O(1)
F i n n            O(1)
F i a n            O(n)

细节2：对于并列的结构取最大值。

#include <bits/stdc++.h>
#define getstr scanf("%s",str+1),len=strlen(str+1)
#define reg register
#define inl inline
#define L 100
using namespace std;
int T,O,N,len,poi,cnt;
int pro[L|1],var[L|1],cen[L|1],lft[L|1],rht[L|1];
bool vis[L|1];
char str[L|1];
inl void init () {
    O=0,poi=0;
    memset (pro,0,sizeof(pro));
    memset (cen,0,sizeof(cen));
    memset (lft,0,sizeof(lft));
    memset (rht,0,sizeof(rht));
    memset (var,0,sizeof(var));
    memset (vis,0,sizeof(vis));
}
inl void scan () {
    scanf ("%d",&N);    getstr;
    for (reg int i=5;i<len;i++)
        O=(O<<1)+(O<<3)+str[i]-'0';
    for (reg int i=1;i<=N;i++) {
        getstr;            pro[i]=str[1]-'E';
        if (pro[i]) {
            getstr;    var[i]=str[1]-'a'+1;
            getstr;    if (str[1]!='n')    for (reg int j=1;j<=len;j++)
                lft[i]=(lft[i]<<1)+(lft[i]<<3)+str[j]-'0';
            getstr;    if (str[1]!='n')    for (reg int j=1;j<=len;j++)
                rht[i]=(rht[i]<<1)+(rht[i]<<3)+str[j]-'0';
        } 
    }
}
inl bool isErr () {
    cnt=0;
    for (reg int i=1;i<=N;i++)
        if (pro[i]) {
            if (vis[var[i]])    return 1;
            vis[var[i]]=1;
            cen[++cnt]=var[i];
        } else {
            vis[cen[cnt--]]=0;
            if (cnt<0)            return 1;
        }
    return cnt!=0;
}
inl int solve () {
    reg int mxo=0,myo=0;
    if (lft[poi]>0&&rht[poi]==0)
        mxo=1;
    if ((lft[poi]==0&&rht[poi]>0)||(lft[poi]>rht[poi]&&rht[poi]>0)) {
        poi++;
        while (poi<=N&&pro[poi])    solve(),poi++;
        return 0;
    }
    poi++;
    while (poi<=N&&pro[poi])        myo=max(myo,solve()),poi++;
    return mxo+myo;
}
int main () {
    for (scanf("%d",&T);T;T--) {
        init ();
        scan ();
        if (isErr())            puts ("ERR");
        else if (solve()==O)    puts ("Yes");
        else                    puts ("No");
    }
    return 0;
}

这里给大家推荐几个大模拟题：

提高难度：PASTE

省选难度：杀蚂蚁

D1T3 逛公园

算法一

直接暴力搜索。

期望得分$10$分。

算法二

发现有$3$个测试点$K=0$。

使用“最短路计数”算法即可。

期望得分$30$分。

#include <bits/stdc++.h>
#define I 0x3f3f3f3f
#define N 100000
#define M 50
using namespace std;
int T,n,m,k,p;
int tot[2],ter[2][N<<1|1],val[2][N<<1|1],nxt[2][N<<1|1],lnk[2][N|1];
int vis[N|1],dis[N|1];
int ans,fun[N|1][M|1];
void update(int &x,int y) {    x=(x+y)%p;    }
void adde(int o,int u,int v,int w) {
    ter[o][++tot[o]]=v;
    val[o][tot[o]]=w;
    nxt[o][tot[o]]=lnk[o][u];
    lnk[o][u]=tot[o];
}
int dfs(int poi,int kth) {
    if(~fun[poi][kth])
        return fun[poi][kth];
    fun[poi][kth]=0;
    for(int i=lnk[1][poi];i;i=nxt[1][i]) {
        int t=dis[poi]+kth-val[1][i]-dis[ter[1][i]];
        if(t<0)                    continue;
        update(fun[poi][kth],dfs(ter[1][i],t));
    }
    return fun[poi][kth];
}
void work() {
    tot[0]=0;
    tot[1]=0;
    memset(ter,0,sizeof(ter));
    memset(nxt,0,sizeof(nxt));
    memset(lnk,0,sizeof(lnk));
    scanf("%d%d%d%d",&n,&m,&k,&p);
    for(int u,v,w,i=1;i<=m;i++) {
        scanf("%d%d%d",&u,&v,&w);
        adde(0,u,v,w),adde(1,v,u,w);
    }
    queue <int> que;
    que.push(1);
    memset(dis,0x3f,sizeof(dis));
    memset(vis,true,sizeof(vis));
    dis[1]=0;
    vis[1]=0;
    while(que.size()) {
        int poi=que.front();
        for(int i=lnk[0][poi];i;i=nxt[0][i])
            if(dis[ter[0][i]]>dis[poi]+val[0][i]) {
                dis[ter[0][i]]=dis[poi]+val[0][i];
                if(vis[ter[0][i]]) {
                    vis[ter[0][i]]=0;
                    que.push(ter[0][i]);
                }
            }
        vis[poi]=1;
        que.pop();
    }
    ans=0;
    memset(fun,-1,sizeof(fun));
    fun[1][0]=1;
    update(ans,dfs(n,0));
    printf("%d\n",ans);
}
int main() {
    for(scanf("%d",&T);T;T--)
        work();
    return 0;
}

算法三

在“算法二”基础上进行改进。

将一维状态变为二维状态，第二维表示比最短路长度多$j$的路径条数。

记点$1$到点$i$的最短路长度为$dis[i]$，$v$表示点$i$的前驱，$w$表示边权。

$f[i][j]$就可以通过$f[v][dis[i]+j-w-dis[v]]$转移过来啦！

本人推荐使用记忆化搜索来实现。

但是在有在最短路上的$0$权环时，该算法就会陷入死循环······

发现有$7$个测试点都不包含$0$权边。

期望得分$70$分。

#include <bits/stdc++.h>
#define I 0x3f3f3f3f
#define N 100000
#define M 50
using namespace std;
int T,n,m,k,p;
int tot[2],ter[2][N<<1|1],val[2][N<<1|1],nxt[2][N<<1|1],lnk[2][N|1];
int vis[N|1],dis[N|1];
int ans,fun[N|1][M|1];
void update(int &x,int y) {    x=(x+y)%p;    }
void adde(int o,int u,int v,int w) {
    ter[o][++tot[o]]=v;
    val[o][tot[o]]=w;
    nxt[o][tot[o]]=lnk[o][u];
    lnk[o][u]=tot[o];
}
int dfs(int poi,int kth) {
    if(~fun[poi][kth])
        return fun[poi][kth];
    fun[poi][kth]=0;
    for(int i=lnk[1][poi];i;i=nxt[1][i]) {
        int t=dis[poi]+kth-val[1][i]-dis[ter[1][i]];
        if(t<0)                    continue;
        update(fun[poi][kth],dfs(ter[1][i],t));
    }
    return fun[poi][kth];
}
void work() {
    tot[0]=0;
    tot[1]=0;
    memset(ter,0,sizeof(ter));
    memset(nxt,0,sizeof(nxt));
    memset(lnk,0,sizeof(lnk));
    scanf("%d%d%d%d",&n,&m,&k,&p);
    for(int u,v,w,i=1;i<=m;i++) {
        scanf("%d%d%d",&u,&v,&w);
        adde(0,u,v,w),adde(1,v,u,w);
    }
    queue <int> que;
    que.push(1);
    memset(dis,0x3f,sizeof(dis));
    memset(vis,true,sizeof(vis));
    dis[1]=0;
    vis[1]=0;
    while(que.size()) {
        int poi=que.front();
        for(int i=lnk[0][poi];i;i=nxt[0][i])
            if(dis[ter[0][i]]>dis[poi]+val[0][i]) {
                dis[ter[0][i]]=dis[poi]+val[0][i];
                if(vis[ter[0][i]]) {
                    vis[ter[0][i]]=0;
                    que.push(ter[0][i]);
                }
            }
        vis[poi]=1;
        que.pop();
    }
    ans=0;
    memset(fun,-1,sizeof(fun));
    fun[1][0]=1;
    for(int i=0;i<=k;i++)
        update(ans,dfs(n,i));
    printf("%d\n",ans);
}
int main() {
    for(scanf("%d",&T);T;T--)
        work();
    return 0;
}

算法四

在“算法三”基础上进行改进。

如何判断在最短路上的$0$权环呢？

如果记忆化搜索的时候重新搜到了自己的状态，就可以判断在最短路上的$0$权环存在了。

期望得分$100$分。

#include <bits/stdc++.h>
#define I 0x3f3f3f3f
#define N 100000
#define M 50
using namespace std;
int T,n,m,k,p;
int tot[2],ter[2][N<<1|1],val[2][N<<1|1],nxt[2][N<<1|1],lnk[2][N|1];
int vis[N|1],dis[N|1];
int ans,cnt[N|1][M|1],fun[N|1][M|1];
bool err;
void update(int &x,int y) {    x=(x+y)%p;    }
void adde(int o,int u,int v,int w) {
    ter[o][++tot[o]]=v;
    val[o][tot[o]]=w;
    nxt[o][tot[o]]=lnk[o][u];
    lnk[o][u]=tot[o];
}
int dfs(int poi,int kth) {
    if(~fun[poi][kth])
        return fun[poi][kth];
    cnt[poi][kth]=1;
    fun[poi][kth]=0;
    for(int i=lnk[1][poi];i;i=nxt[1][i]) {
        int t=dis[poi]+kth-val[1][i]-dis[ter[1][i]];
        if(t<0)                    continue;
        if(cnt[ter[1][i]][t])    err=1;
        update(fun[poi][kth],dfs(ter[1][i],t));
    }
    cnt[poi][kth]=0;
    return fun[poi][kth];
}
void work() {
    tot[0]=0;
    tot[1]=0;
    memset(ter,0,sizeof(ter));
    memset(nxt,0,sizeof(nxt));
    memset(lnk,0,sizeof(lnk));
    scanf("%d%d%d%d",&n,&m,&k,&p);
    for(int u,v,w,i=1;i<=m;i++) {
        scanf("%d%d%d",&u,&v,&w);
        adde(0,u,v,w),adde(1,v,u,w);
    }
    queue <int> que;
    que.push(1);
    memset(dis,0x3f,sizeof(dis));
    memset(vis,true,sizeof(vis));
    dis[1]=0;
    vis[1]=0;
    while(que.size()) {
        int poi=que.front();
        for(int i=lnk[0][poi];i;i=nxt[0][i])
            if(dis[ter[0][i]]>dis[poi]+val[0][i]) {
                dis[ter[0][i]]=dis[poi]+val[0][i];
                if(vis[ter[0][i]]) {
                    vis[ter[0][i]]=0;
                    que.push(ter[0][i]);
                }
            }
        vis[poi]=1;
        que.pop();
    }
    ans=0;
    memset(fun,-1,sizeof(fun));
    fun[1][0]=1;
    for(int i=0;i<=k;i++)
        update(ans,dfs(n,i));
    dfs(n,k+1);
    if(err)    puts("-1");
    else    printf("%d\n",ans);
}
int main() {
    for(scanf("%d",&T);T;T--)
        work();
    return 0;
}

D2T1 奶酪

将每一个奶酪上的洞当作点，两个可以到达的洞之间连一条边。

如果洞通向地面连0号点，如果洞连向上表面连n+1好点。

建图完毕后，判断0号点与n+1好点的连通性即可。

注意：为了避免精度问题，我们不应该开方；小心被卡常数。

#include <bits/stdc++.h>
#define reg register
#define inl inline
#define M 1004004
#define N 1002
using namespace std;
typedef long long ll;
bool vis[N|1];
ll T,n,h,r,a[N|1],b[N|1],c[N|1];
ll tot,ter[M<<1|1],nxt[M<<1|1],lnk[N|1];
inl ll dist (reg ll a,reg ll b,reg ll c,reg ll d,reg ll e,reg ll f) { return (a-d)*(a-d)+(b-e)*(b-e)+(c-f)*(c-f); }
inl bool check (reg ll a,reg ll b,reg ll c,reg ll d,reg ll e,reg ll f) { return dist(a,b,c,d,e,f)<=(2*r)*(2*r); }
inl void adde (reg ll p,reg ll q) {
    ter[++tot]=q;
    nxt[tot]=lnk[p];
    lnk[p]=tot;
}
inl void dfs (reg int p) {
    vis[p]=false;
    for (reg int i=lnk[p];i;i=nxt[i])
        if (vis[ter[i]])
            dfs (ter[i]);
}
int main () {
    for (scanf("%lld",&T);T;T--) {
        tot=0;
        memset (ter,0,sizeof(ter));
        memset (nxt,0,sizeof(nxt));
        memset (lnk,0,sizeof(lnk));
        memset (vis,true,sizeof(vis));
        scanf ("%lld%lld%lld",&n,&h,&r);
        for (reg int i=1;i<=n;i++) {
            scanf ("%lld%lld%lld",&a[i],&b[i],&c[i]);
            if (c[i]<=r) {
                adde (0,i);
                adde (i,0);
            }
            if (c[i]>=h-r) {
                adde (n+1,i);
                adde (i,n+1);
            }
        }
        for (reg int i=1;i<=n;i++)
            for (reg int j=i+1;j<=n;j++)
                if (check(a[i],b[i],c[i],a[j],b[j],c[j])) {
                    adde (i,j);
                    adde (j,i);
                }
        dfs (0);
        if (vis[n+1])    printf ("No\n");
        else            printf ("Yes\n");
    }
    return 0;
}

这题还可以用$BFS$和并查集做，这里就不提及了。

D2T2 宝藏

$f[i][j]$表示状态为i时以j点开始挖地道的最小花费。

$g[i][j][k]$为辅助数组，表示$f[i][j]$时$j$点到$k$点经过点的个数。

若 i==(i&-i) => 特判边界情况。

否则 => 枚举上一个状态，再枚举从上一个状态中的哪个点连边，更新$f[i][j]$

时间复杂度$O(2^nn^3)$

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define reg register
#define M 1000
#define N 12
typedef long long ll;
using namespace std;
ll n,m,mx,res,d[N|1][N|1],f[1<<N][N|1],g[1<<N][N|1][N|1];
int main () {
    scanf ("%lld%lld",&n,&m);
    memset (d,0x3f,sizeof(d));
    memset (f,0x3f,sizeof(f));
    memset (g,0x3f,sizeof(g));
    mx=(1<<n)-1;
    for (reg ll u,v,w,i=1;i<=m;i++) {
        scanf ("%lld%lld%lld",&u,&v,&w);
        d[u][v]=min(d[u][v],w);
        d[v][u]=min(d[v][u],w);
    }
    for (reg ll i=1;i<=mx;i++)
        if (i==(i&-i)) {
            for (reg ll j=1;j<=n;j++)    if (i&(1<<(n-j))) {
                f[i][j]=0;
                g[i][j][j]=1;
            }
        } else {
            for (reg ll j=1;j<=n;j++)    if (i&(1<<(n-j)))
                for (reg ll k=1;k<=n;k++)    if (i&(1<<(n-k))) {
                    reg ll c=0,las=i-(1<<(n-k));
                    for (reg ll l=1;l<=n;l++)
                        if (las&(1<<(n-l))&&d[k][l]<inf&&g[las][j][l]<inf&&f[i][j]>f[las][j]+d[k][l]*g[las][j][l])
                                c=l,f[i][j]=f[las][j]+d[k][l]*g[las][j][l];
                    if (c) {
                        for (reg ll l=1;l<=n;l++)    if (las&(1<<(n-l)))
                            g[i][j][l]=g[las][j][l];
                        g[i][j][k]=g[i][j][c]+1;
                    }
                }
        }
    res=inf;
    for (reg ll i=1;i<=n;i++)
        res=min(res,f[mx][i]);
    printf ("%lld\n",res);
    return 0;
}

其实这个算法有后向性，是错误的。

正解应该是$O(n3^n)$的。

但是这个算法出错率极低，本题也可以通过。

这题还可以用搜索加剪枝通过，这里就不再详细说明了。

D2T3 列队

算法一

直接暴力模拟，即可通过$3$个测试点。

期望得分$30$分。

#include <bits/stdc++.h>
#define reg register
#define N 1000
using namespace std;
int n,m,k,s[N|1][N|1];
int main () {
    scanf ("%d%d%d",&n,&m,&k);
    for (reg int i=1;i<=n;i++)
        for (reg int j=1;j<=m;j++)
            s[i][j]=i*m+j-m;
    for (reg int p,q,t,i=1;i<=k;i++) {
        scanf ("%d%d",&p,&q);
        printf ("%d\n",t=s[p][q]);
        for (reg int j=q;j<m;j++)
            s[p][j]=s[p][j+1];
        for (reg int j=p;j<n;j++)
            s[j][m]=s[j+1][m];
        s[n][m]=t;
    }
    return 0;
}

算法二

当询问个数较小时，我么们可以使用$O(q^2)$的方法倒推。

令$r$表示当前行，$c$表示当前列。

若(r==n&&c==m) => r=x[j],c=y[j];

若(r>=x[j]&&c==m) => r++;

若(r==x[j]&&c>=y[j]) => c++;

观察发现有$5$个测试点$q<=500$。

期望得分$50$分。

#include <bits/stdc++.h>
#define N 500
using namespace std;
typedef long long ll;
ll n,m,q,r,c,x[N|1],y[N|1];
int main() {
    scanf("%lld%lld%lld",&n,&m,&q);
    for(int i=1;i<=q;i++) {
        scanf("%lld%lld",&x[i],&y[i]);
        r=x[i],c=y[i];
        for(int j=i-1;j;j--)
            if(r==n&&c==m) {
                r=x[j],c=y[j];
            } else if(r>=x[j]&&c==m) {
                r++;
            } else if(r==x[j]&&c>=y[j]) {
                c++;
            }
        printf("%lld\n",r*m+c-m);
    } 
    return 0;
}

算法三

发现另外$3$个测试点$x$永远等于$1$，影响到的位置只有第一行和最后一列。

于是开一个线段树修改查询即可。

期望得分$30$分，结合前面$50$分的程序共计$80$分。

算法四

我们需要在“算法三”的基础上加以改进。

我们需要$n$棵横着的线段树和$1$棵竖着的线段树，每次只需要把将$(x,y)$处的点移到最后一列的最后，把$(x,m)$的点移到第$x$行的最后就可以了。

我么们发现空间复杂度不够，于是想到动态开点。

期望得分$100$分。

代码难度很高，我为大家整理了一份简洁的代码。

#include <bits/stdc++.h>
#define M 3600000
#define N 600000
#define md (l+r>>1)
using namespace std;
typedef long long ll;
struct node {
    int sum,ls,rs;
    node() {    ls=rs=0;    }
}    tr[M|1];
vector <ll> vc[N|1];
int n,m,q,mx,tot,pos,rt[N|1];
void modify(int &o,int l,int r) {
    if(!o)        o=++tot;    tr[o].sum++;
    if(l==r)    return;
    if(pos<=md)    modify(tr[o].ls,l,md);
    else        modify(tr[o].rs,md+1,r);
} 
int query(int o,int l,int r,int k) {
    if(l==r)    return l;
    int sz=md-l+1-tr[tr[o].ls].sum;
    if(k<=sz)    return query(tr[o].ls,l,md,k);
    else        return query(tr[o].rs,md+1,r,k-sz); 
}
ll delcol(int x,ll v) {
    pos=query(rt[0],1,mx,x);    modify(rt[0],1,mx);
    ll ans=pos<=n?1ll*pos*m:vc[0][pos-n-1];
    vc[0].push_back(v?v:ans);
    return ans;
}
ll delrow(int x,int y) {
    pos=query(rt[x],1,mx,y);    modify(rt[x],1,mx);
    ll ans=pos<m?1ll*(x-1)*m+pos:vc[x][pos-m];
    vc[x].push_back(delcol(x,ans));
    return ans;
}
int main() {
    scanf("%d%d%d",&n,&m,&q),mx=max(n,m)+q;
    for(int x,y,i=1;i<=q;i++) {
        scanf("%d%d",&x,&y);
        if(y==m)    printf("%lld\n",delcol(x,0));
        else        printf("%lld\n",delrow(x,y));
    }    return 0;
}

（压行十分严重）

尾声

本蒟蒻写题解写到$0$点，给个好评吧！

下次NOIP我们再见！OvO

评论

gaolinxiang
ZROJ吃换行？
  • 2018-01-07 21:54:06
heqingyu
@gaolinxiang 爸爸。。。
  • 2018-01-08 09:50:21
heqingyu
Mark Down。。。
  • 2018-01-08 09:50:38
oi_loser
能发个D1T1推导过程吗，这题确实发现结论比推导简单…… 我学弟造了一组D2T2的hack数据： [Input] 9 10 1 2 7 1 3 7 1 4 7 1 5 7 2 6 200 3 7 200 4 8 200 5 9 200 2 3 1 4 5 1 [Output] 1628 所以你还是写个 $O(3^nn)$ 吧…… 另外D1T2标题打成D2T2了……
  • 2018-01-08 10:23:40
gaolinxiang
@oi_loser 感谢提醒！
  • 2018-01-08 20:28:20
gaolinxiang
@heqingyu 大佬！
  • 2018-01-08 20:28:40
heqingyu
@gaolinxiang 爸爸啊。。。
  • 2018-01-09 12:18:10
jaker
D2T2不是错误率低，是noip数据太水了，某学军大佬随机数据之后很多100分直接到了0分就是类似的做法 实际上这道题数据水到贪心的搜索都能过
  • 2018-08-07 16:07:46

中文 English

Server time: 2024-05-11 15:05:45   |   浙ICP备17047493号