NOIP 2017 总结

谷雨同学 2017年11月14日-15日
最后更新于2018年1月8日

总述

这是我第一次参加 NOIP 。

总分355。下面是当时估分写的总结

我只不过刚刚学了一年而已，关于算法竞赛只是了解些皮毛而已。今天早些时候我拿到了我的源代码，于是便立即在洛谷上用”民间数据”自测了一下。现汇报如下：

题目	估计分数	实际分数
math	100	100
complexity	100	100
park	0	0
cheese	100	70
treasure	80	55
phalanx	30	30
总分	410	355

math - 小凯的疑惑

上来第一题就是数学让我感到措手不及。我只好一点点列举，然后找规律……比如我看到 $14 = 3 \times 0 + 7 \times 2$ 时，便意识到11之所以被输出，是因为实际上 $11 = 3 \times (-1) + 7 \times 2$ ，但是 -1 不合法。以此为突破口，我首先试着循环 1 .. a，然后对于每一个数不断累加 a 判断那一个最晚被 b 整除，再减去 a 求得答案，此时时间复杂度为 $\Theta(ab)$ 。后来又发现先找到的被整除的数其实就是 $a \times (b - 1)$ ，所以答案就是

a \times b - a - b

源代码

100分， AC 。中间的大部分都注释掉了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long a,b;
int main(){
    ios::sync_with_stdio(false);
    #ifndef LOCAL
    freopen("math.in","r",stdin);
    freopen("math.out","w",stdout);
    #endif
    cin>>a>>b;
    if(a>b)swap(a,b);
    /*
    long long ans=-1;
    for(long long i=1;i<a;i++){
        long long c=i,j=0;
        while(c%b){
            c+=a;
            j++;
        }
        ans=max(ans,i+a*(j-1));
    }
    cout<<ans<<endl;
    */
    long long ans=b*(a-1)-a;
    cout<<ans<<endl;
    return 0;
}

complexity - 时间复杂度

这是一个非常复杂的模拟。我最初没有想到用栈，于是思路就是先读入全部指令，然后逐行执行：设置一个 work 变量，记录当前光标执行到的循环体编号。然后读到” F “行将 work 设为一个新开循环体编号同时记录它的父亲编号。读到” E “行将 work 退回父亲编号。所以每一个循环体就是如下结构：

struct xht{
    int par;//父亲编号
    int v;//时间复杂度对数
};

关于处理时间复杂度：用对数记录即可。输入的处理方式是截取 [2] 处字符，若为 '1' 则返回 $\log_n 1$ ,否则把 [4]..size()-2 区间的字符转为数字，即为 $\log_n \Theta$ 。转换为数字的方法是用 stringstream，输入一个字符串再对一个整型输出即可。（这是我头一次用这种方法）

然后判断循环变量是否使用（已使用输出 ERR）。再判断初值和末值的关系，共有五种情况，我用了一个函数判断：

编号	情况	时间复杂度对数
1	n~n	等于父亲循环体
2	n~常数	不存在
3	常数~n	等于父亲循环体+1
4	常数~常数，且前者小于后者	等于父亲循环体+1
5	常数~常数，且前者大于后者	不存在

这样就可以找到光标经过每一个循环体的时间复杂度，找到其最大值和输入的比较即可。

源代码

100分，AC。其中 xht 结构体中的 no 成员是没有用的，忘记删除了。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<string>
#include<cstdio>
using namespace std;
int t;
bool used[30];
string cmd[102];
struct xht{
    int no;
    int par;
    int v;
};
xht f[52];
int toInt(string x){
    stringstream a;
    int b;
    a<<x;
    a>>b;
    return b;
}
int getO(string x){
    if(x[2]=='1')return 0;
    string y;
    for(int i=4;i<x.size()-1;i++){
        y+=x[i];
    }
    return toInt(y);
}
void getDtl(string src,char& a,string& b,string& c){
    stringstream x;
    x<<src;
    x>>src>>a>>b>>c;
    return;
}
int als(string x,string y){
    if(x=="n"){
        if(y=="n")return 0;
        return 1;
    }
    if(y=="n")return 2;
    if(toInt(x)<=toInt(y))return 3;
    return 4;
}

int main(){
    ios::sync_with_stdio(false);
    #ifndef LOCAL
    freopen("complexity.in","r",stdin);
    freopen("complexity.out","w",stdout);
    #else
    freopen("out.txt","w",stdout);
    #endif
    cin>>t;
    while(t--){
        int l,o,cnt=0,ans=0;
        memset(used,false,sizeof(used));
        memset(f,0,sizeof(f));
        int work=0;
        string oo;
        cin>>l>>oo;
        o=getO(oo);
        getline(cin,oo);
        for(int i=1;i<=l;i++){
            getline(cin,cmd[i]);
        }
        for(int i=1;i<=l;i++){
            if(cmd[i][0]=='F'){
                char a;
                string b,c;
                getDtl(cmd[i],a,b,c);
                if(used[a-'a']){
                    cout<<"ERR"<<endl;
                    goto out;
                }
                f[++cnt].no=a-'a';
                used[f[cnt].no]=true;
                f[cnt].par=work;
                work=cnt;
                switch(als(b,c)){
                    case 0:{//n,n
                        f[cnt].v=f[f[cnt].par].v;
                        break;
                    }
                    case 1:{//n,_
                        f[cnt].v=-1;
                        break;
                    }
                    case 2:{//_,n
                        f[cnt].v=(f[f[cnt].par].v==-1?-1:f[f[cnt].par].v+1);
                        break;
                    }
                    case 3:{//small.big
                        f[cnt].v=f[f[cnt].par].v;
                        break;
                    }
                    case 4:{//big,small
                        f[cnt].v=-1;
                        break;
                    }
                }
                ans=max(ans,f[work].v);
            }
            else{
                used[f[work].no]=false;
                if(work==0){
                    cout<<"ERR"<<endl;
                    goto out;
                }
                work=f[work].par;
            }
        }
        if(work){
            cout<<"ERR"<<endl;
            continue;
        }
        cout<<(ans==o?"Yes":"No")<<endl;
        out:;
    }
    return 0;
}

park - 逛公园

没做。由于第二题花了我太长的时间，所以第三题几乎没有什么时间了。再者图论我也不熟悉，恐怕做也做不出来。

0分。

cheese - 奶酪

用了一个DFS做出来的。首先在输入的同时用布尔型”邻接矩阵” e[][] 来记录两个洞是否相连，并判断是否通底部或顶部。如果通底部，把这个洞加入数组 btm[] 中，如果同顶部将 top[] 设为 true 。再从 btm[] 中逐个DFS搜索，如果能搜到顶返回 "Yes" ,否则就是 "No" 。

然而这道题还是踩了个坑，因为判断是否连通时会超 long long 范围。坐标极值为 $\pm 10^9$ ,坐标之差最大值为 $2 \times 10^9$ , 带入距离公式则根号下最大值为 $3 \times ( 2 \times 10^9)^2 = 3 \times 4 \times 10^{18} = 1.2 \times 10^{19}$ 。而 long long 的最大值为 $9, 223, 372, 036, 854, 775, 807 = 9.22 \times 10^{18} < 1.2 \times 10^{19}$ 。所以只能说洛谷的数据有点水，真正的得分应该到不了 AC 。

是啊，一个 unsigned 扣了我 30 分…

源代码

70分， AC 。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

int t;
int n,h,r;
bool e[1002][1002];
bool m[1002];
bool top[1002];
int btm[1002];
int lb;
struct hole{
    int x;
    int y;
    int z;
};
hole o[1002];

bool isLinked(hole a,hole b,int d){
    long long dl=d*d;
    long long rr=0;
    rr+=(a.x-b.x)*(a.x-b.x);
    rr+=(a.y-b.y)*(a.y-b.y);
    rr+=(a.z-b.z)*(a.z-b.z);
    return rr<=dl;
}
bool find(int x){
    if(m[x])return false;
    m[x]=true;
    if(top[x])return true;
    for(int i=1;i<=n;i++){
        if(e[x][i]){
            if(find(i))return true;
        }
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    #ifndef LOCAL
    freopen("cheese.in","r",stdin);
    freopen("cheese.out","w",stdout);
    #else
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    cin>>t;
    while(t--){
        memset(o,0,sizeof(o));
        memset(e,false,sizeof(e));
        memset(top,false,sizeof(top));
        memset(btm,0,sizeof(btm));
        memset(m,false,sizeof(m));
        cin>>n>>h>>r;
        for(int i=1;i<=n;i++){
            cin>>o[i].x>>o[i].y>>o[i].z;
            if(o[i].z+r>=h)top[i]=true;
            if(o[i].z-r<=0)btm[++lb]=i;
            for(int j=1;j<i;j++){
                bool isL=isLinked(o[i],o[j],2*r);
                e[i][j]=e[j][i]=isL;
            }
        }
        /*
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cout<<e[i][j];
            }
            cout<<endl;
        }
        */
        //cout<<lb<<btm[1]<<endl;
        for(int i=1;i<=lb;i++){
            if(find(btm[i])){
                cout<<"Yes"<<endl;
                goto out;
            }
        }
        cout<<"No"<<endl;
        out:;
    }
    return 0;
}

treasure - 宝藏

呃……这个题，我是没有思路的。经过一段时间的观察发现：我可以建立一个集合 hv[] 表示已遍历的点以及一个集合 work[] 容纳边。先以第一个点为起点，加进 hv[] ，把与它相连的边加入 work[] ，然后选取边长 * 深度最短的一条退出 work[] ，把所指向的点加进集合 hv[] ，将与这个点相连的所有边加入 work[] 。这样往复操作直到所有的点都加入 hv[] 后，再以第二个作为起点执行一遍，直到全部执行完成，输出选中的”边长 * 深度”之和的最小值，就和样例的输出是一样的。

至于为什么是这样的我不知道，所以 WA 了 4 个点也就不足为怪了。不过已经很知足了。

知足了，瞎写一通还能55分。

源代码

代码写的很乱，因为邻接表用的不熟练，导致无向边和有向边不统一，设了一堆乱七八糟的数组……

55分， WA 。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m;
int l[1002];
int s[15];
int em[2004];
bool work[1002];
int hv[15];
int to[1002];
int by[1002];
int ans=0,res=(1<<30);
//-------------LJB------------
int next[2002];
int dot[15];
int edge[2002];
int cnt=0;
void addedge(int x,int y,int i){
    edge[++cnt]=y;
    next[cnt]=dot[x];
    dot[x]=cnt;
    em[cnt]=i;
}

void debug(){
    cout<<"work:";
    for(int i=1;i<=m;i++){
        cout<<work[i]<<" ";
    }
    cout<<endl<<"by:";
    for(int i=1;i<=m;i++){
        cout<<by[i]<<" ";
    }
    cout<<endl<<"to:";
    for(int i=1;i<=m;i++){
        cout<<to[i]<<" ";
    }
    cout<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    #ifndef LOCAL
    freopen("treasure.in","r",stdin);
    freopen("treasure.out","w",stdout);
    #endif
    cin>>n>>m;
    memset(l,0,sizeof(l));
    memset(dot,0,sizeof(dot));
    memset(edge,0,sizeof(edge));
    memset(next,0,sizeof(next));
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        addedge(a,b,i);
        addedge(b,a,i);
        l[i]=c;
    }
    for(int i=1;i<=n;i++){
        ans=0;
        memset(work,false,sizeof(work));
        memset(by,0,sizeof(by));
        memset(to,0,sizeof(to));
        memset(hv,false,sizeof(hv));
        hv[i]=true;
        for(int j=dot[i];j;j=next[j]){
            //cout<<i<<" "<<edge[j]<<" "<<em[j]<<":"<<l[em[j]]<<endl;
            work[em[j]]=true;
            by[em[j]]=1;
            to[em[j]]=edge[j];
        }
        int x=1;
        
        while(x<n){
            //debug();
            int sno=500002,nx,bb;
            for(int j=1;j<=m;j++){
                if(work[j]&&!hv[to[j]]){
                    if(sno>l[j]*by[j]){
                        sno=l[j]*by[j];
                        nx=to[j];
                        bb=by[j];
                    }
                }
            }
            //cout<<sno<<" "<<nx<<" "<<bb<<endl;
            ans+=sno;
            hv[nx]=true;
            x++;
            for(int j=dot[nx];j;j=next[j]){
                if(!hv[edge[j]]){
                    work[em[j]]=true;
                    by[em[j]]=bb+1;
                    to[em[j]]=edge[j];
                }
            }
        }
        res=min(res,ans);
    }
    cout<<res<<endl;
    return 0;
}

phalanx - 方阵

无思路，写了个暴力。用二元数组 a[][] 表示这一点的编号。

源代码

30分， RE 。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int a[10002][10002];
int n,m,q;
void debug(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
}
int main(){
    ios::sync_with_stdio(false);
    #ifndef LOCAL
    freopen("phalanx.in","r",stdin);
    freopen("phalanx.out","w",stdout);
    #else
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=(i-1)*m+j;
        }
    }
    //debug();
    for(int i=1;i<=q;i++){
        int x,y;
        cin>>x>>y;
        int p=a[x][y];
        cout<<p<<endl;
        for(int j=y;j<m;j++){
            a[x][j]=a[x][j+1];
        }
        for(int j=x;j<n;j++){
            a[j][m]=a[j+1][m];
        }
        a[n][m]=p;
    }
    return 0;
}

结语

感觉这次考 NOIP 着实让我第一次亲身体验到算法竞赛。我自己认为我在赛场上还是还是发挥得较为成功。不过确实还有许多要学习的知识点、算法和技巧。未来还是要努力的……

本文由Markdown书写。样式表、解析器来自 GitHub 。编辑器 MarkdownPad 2 。