NOIp2017真题模拟赛 By cellur925

果然我还是最菜的==不接受反驳

（先考了day2喵喵喵）

Day2

T1：奶酪

期望得分：100分

实际得分：100分

考察：并查集

思路：这题其实之前做过了==。思路还是比较清晰的，读入时预处理出可以“通天下地”的奶酪，之后n²枚举所有的奶酪关系，可以互达的就连到一个并查集中。互达怎么判断？即使是空间也没关系，将两个奶酪的球心距离与二倍半径比较即可。之前的题解

Code

 //15:31
 #include<cstdio>
 #include<algorithm>
 #include<cmath>

 using namespace std;
 typedef long long ll;

 int T,n;
 int qwq[],qaq[],cnt,tot;
 int f[];
 ll h,r;
 struct point{
     ll x,y,z;
 }p[];

 int getf(int x)
 {
     if(x==f[x]) return x;
     else return getf(f[x]);
 }

 double dis(int i,int j)
 {
     return (double)sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)+(p[i].z-p[j].z)*(p[i].z-p[j].z));
 }

 int main()
 {
     freopen("cheese.in","r",stdin);
     freopen("cheese.out","w",stdout);
     scanf("%d",&T);
     while(T--)
     {
         scanf("%d",&n);
         scanf("%lld%lld",&h,&r);
         for(int i=;i<=n;i++)
         {
             scanf("%lld%lld%lld",&p[i].x,&p[i].y,&p[i].z);
             if(p[i].z-r<=) qwq[++cnt]=i;
             if(p[i].z+r>=h)    qaq[++tot]=i;
         }
         /*for(int i=1;i<=cnt;i++) printf("qwq:%d ",qwq[i]);
         printf("\n");
         for(int i=1;i<=tot;i++) printf("qaq:%d ",qaq[i]);
         printf("\n");*/
         for(int i=;i<=n;i++) f[i]=i;
         for(int i=;i<=n;i++)
             for(int j=;j<=n;j++)
             {
                 if(dis(i,j)<=(double)*r)
                 {
                     int pp=getf(i);
                     int qq=getf(j);
                     if(qq!=pp)
                         f[qq]=pp;
                 }
             }
         bool flag=;
         for(int i=;i<=cnt;i++)
         {
             for(int j=;j<=tot;j++)
             {
                 int a=qwq[i];int b=qaq[j];
                 if(getf(a)==getf(b))
                 {
                     flag=;
                     printf("Yes\n");
                     break;
                 }
             }
             if(flag) break;
         }
         if(!flag) printf("No\n");
         cnt=;tot=;
     }
     return ;
 }

cheese

*  注意long long，以及文件名qwq

T2：宝藏

期望得分：40分

实际得分：0分

考察：状压dp+dfs

考场心路历程：

//20 pts树的情况
//一定每条边都被选到

//40pts 所有的边权都相等
//那么根据乘法结合律，我们可以不再考虑边权对结果的影响
//那么答案可以转化为：枚举一个起点 使起点到 各点经过的点之和最小
//哎这样是不是可以重新建一个没有权的图进行一下遍历啊.....
//这样是不是转为一个树形dp了......
//假的。树形dp写爆了 用了spfa苟

其实思路是对的...Chemist dalao和lwz dalao都用的我的思路，40分稳稳拿到手。其实我那个20分并不需要写，因为树的情况时各边权也相等==。

 #include<cstdio>
 #include<algorithm>
 #include<cstring>
 #include<queue>

 using namespace std;
 typedef long long ll;

 int n,m,tot,val;
 ll ans=1e10;
 int head[],d[],f[],dis[];
 bool vis[];
 struct node{
     int to,next,val;
 }edge[];

 void add(int x,int y,int z)
 {
     edge[++tot].to=y;
     edge[tot].next=head[x];
     head[x]=tot;
     edge[tot].val=z;
 }

 void dfs(int x,int fa)
 {
     vis[x]=;
     for(int i=head[x];i;i=edge[i].next)
     {
         int y=edge[i].to;
         if(y==fa) continue;
         if(vis[y]) continue;
         d[y]=d[x]+;
         f[y]=edge[i].val;
         dfs(y,x);
     }
 }
 //-------------------------------------------------------------
 void addqwq(int x,int y,int z)
 {
     edge[++tot].to=y;
     edge[tot].next=head[x];
     head[x]=tot;
     edge[tot].val=z;
 }

 /*void Treedp(int u,int fa)
 {
     vis[u]=1;
     for(int i=head[u];i;i=edge[i].next)
     {
         int v=edge[i].to;
         if(fa==v||v==root) continue;
     //    if(vis[v]) continue;
         dp[v]=min(dp[v],dp[u]+1);
         Treedp(v,u);
     }
 }*/

 void spfa(int s)
 {
     memset(dis,0x3f,sizeof(dis));
     queue<int>q;
     q.push(s);vis[s]=;
     dis[s]=;
     while(!q.empty())
     {
         int u=q.front();q.pop();
         vis[u]=;
         for(int i=head[u];i;i=edge[i].next)
         {
             int v=edge[i].to;
             if(dis[v]>dis[u]+edge[i].val)
             {
                 dis[v]=dis[u]+edge[i].val;
                 if(!vis[v]) q.push(v),vis[v]=;
             }
         }
     }
 }

 int main()
 {
     freopen("treasure.in","r",stdin);
     freopen("treasure.out","w",stdout);
     scanf("%d%d",&n,&m);
     //20 pts树的情况
     //一定每条边都被选到
     if(m==n-)
     {
         for(int i=;i<=m;i++)
         {
             int x=,y=,z=;
             scanf("%d%d%d",&x,&y,&z);
             add(x,y,z);add(y,x,z);
         }
         for(int i=;i<=n;i++)
         {
             ll tmp=;
             dfs(i,);
             for(int j=;j<=n;j++)
                 tmp+=(d[i]+)*f[i];
             ans=min(ans,tmp);
             memset(d,,sizeof(d));
             memset(f,,sizeof(f));
         }
         dfs(,);
         for(int i=;i<=n;i++)
             ans+=(d[i]+)*f[i];
 /*        for(int i=1;i<=n;i++)
             printf("%d ",d[i]);
         printf("\n");
         for(int i=1;i<=n;i++)
             printf("%d ",f[i]);*/
         printf("%lld",ans);
         return ;
     }
     // 40pts 所有的边权都相等
     //那么根据乘法结合律，我们可以不再考虑边权对结果的影响
     //那么答案可以转化为：枚举一个起点 使起点到 各点经过的点之和最小
     //哎这样是不是可以重新建一个没有权的图进行一下遍历啊.....
     //这样是不是转为一个树形dp了......
     //假的。树形dp写爆了 用了spfa苟
     for(int i=;i<=m;i++)
     {
         int x=,y=;
         scanf("%d%d%d",&x,&y,&val);
         addqwq(x,y,);addqwq(y,x,);
     }
     for(int i=;i<=n;i++)
     {
         ll qaq=;
         memset(vis,,sizeof(vis));
         spfa(i);
         for(int j=;j<=n;j++)
             if(j==i) continue;
             else qaq+=dis[j]+;
         ans=min(ans,qaq*val);
     }
     printf("%lld",ans);
     return ;
 }

考场--treasure

所以到底哪里错了呢。查了整整一晚自习，才发现题意理解有些问题qwq。

而且在20分的部分程序中还要一个变量名ij写混了...

新开发一条道路的代价是：L*K

L代表这条道路的长度，K代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的 宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋） 。

当时理解的就是用spfa求出点个数最短路后再+1，临收卷不到5分钟，树p写挂了，开始写spfa，过了样例和自己的数据就草草交了，后来买饭还在想会不会爆int之类的...

结果一个晚自习后发现不需要加1，那样会重复算。因为经过的宝藏屋数量计数终止于修建一条道路的起点。所以不需要加1，边权与点权间转化是等效的。

 #include<cstdio>
 #include<algorithm>
 #include<cstring>
 #include<queue>

 using namespace std;
 typedef long long ll;

 int n,m,tot,val;
 ll ans=1e10;
 int head[],d[],f[],dis[];
 bool vis[];
 struct node{
     int to,next,val;
 }edge[];

 void add(int x,int y,int z)
 {
     edge[++tot].to=y;
     edge[tot].next=head[x];
     head[x]=tot;
     edge[tot].val=z;
 }

 void dfs(int x,int fa)
 {
     vis[x]=;
     for(int i=head[x];i;i=edge[i].next)
     {
         int y=edge[i].to;
         if(y==fa) continue;
         if(vis[y]) continue;
         d[y]=d[x]+;
         f[y]=edge[i].val;
         dfs(y,x);
     }
 }
 //-------------------------------------------------------------
 void addqwq(int x,int y,int z)
 {
     edge[++tot].to=y;
     edge[tot].next=head[x];
     head[x]=tot;
     edge[tot].val=z;
 }

 /*void Treedp(int u,int fa)
 {
     vis[u]=1;
     for(int i=head[u];i;i=edge[i].next)
     {
         int v=edge[i].to;
         if(fa==v||v==root) continue;
     //    if(vis[v]) continue;
         dp[v]=min(dp[v],dp[u]+1);
         Treedp(v,u);
     }
 }*/

 void spfa(int s)
 {
     memset(dis,0x3f,sizeof(dis));
     queue<int>q;
     q.push(s);vis[s]=;
     dis[s]=;
     while(!q.empty())
     {
         int u=q.front();q.pop();
         vis[u]=;
         for(int i=head[u];i;i=edge[i].next)
         {
             int v=edge[i].to;
             if(dis[v]>dis[u]+edge[i].val)
             {
                 dis[v]=dis[u]+edge[i].val;
                 if(!vis[v]) q.push(v),vis[v]=;
             }
         }
     }
 }

 int main()
 {

     scanf("%d%d",&n,&m);
     // 40pts 所有的边权都相等
     //那么根据乘法结合律，我们可以不再考虑边权对结果的影响
     //那么答案可以转化为：枚举一个起点 使起点到 各点经过的点之和最小
     //哎这样是不是可以重新建一个没有权的图进行一下遍历啊.....
     //这样是不是转为一个树形dp了......
     //假的。树形dp写爆了 用了spfa苟
     for(int i=;i<=m;i++)
     {
         int x=,y=;
         scanf("%d%d%d",&x,&y,&val);
         addqwq(x,y,);addqwq(y,x,);
     }
     for(int i=;i<=n;i++)
     {
         ll qaq=;
         memset(vis,,sizeof(vis));
         spfa(i);
         for(int j=;j<=n;j++)
             if(j==i) continue;
             else qaq+=dis[j];
         ans=min(ans,qaq*val);
     }
     printf("%lld",ans);
     return ;
 }

40pts--treasure

不过也是万幸能过发现自己审题的错误，Chemist把他的40分程序改动后也不对，模拟赛分低点总比NOIP爆炸强吧==。

正解：状压dp。

其实看数据范围也想到应该是状压了，就是首先dp不太会写，其次没想到怎么压，而且之前做的为数不多的状压题目都是在棋盘背景那种很显然的dp,状态设计比较显然。

所以还要做一些普适性的状压=w=。

在本题中的状态：0代表当前的宝藏屋没有被挖到（没与选定的起点联通），1代表挖到了。

设f[j]表示在状态j下，从起点到当前状态的最小花费，那么最后就是枚举所有起点取min{f[2^n-1]}。

转移过程：枚举已经挖过的所有点，再枚举这次要挖的点，记录dis[j]表示从jj到起点经过的点的数量。每次转移的时候特判一下是否属于当前状况，

转移：dp[s|(1<<(j-1))]=min(dp[s]+dis[i]*v[i][j],dp[s|(1<<(j-1))]);

时间复杂度：O（n^3*2^n）

 #include<cstdio>
 #include<algorithm>
 #include<cstring>

 using namespace std;

 int n,m,ans=,fake;
 int v[][],dp[],dis[];

 void dfs(int s)
 {
     for(int i=;i<=n;i++)
     {
         if(!(s&(<<(i-)))) continue;//现在找的是已经挖过的点
         for(int j=;j<=n;j++)
         {
             if(s&(<<(j-))) continue;//现在找的是没挖过的点
             if(v[i][j]==fake) continue;//要找可有边直接连通的
             if(dp[s]+dis[i]*v[i][j]<dp[s|(<<(j-))])
             {//更新
                 int odd=dis[j];//记录原来值，以便日后回溯
                 dp[s|(<<(j-))]=dp[s]+dis[i]*v[i][j];//更新 因为修i到j这条边 所以点的个数到dis[i]即可
                 dis[j]=dis[i]+;//更新
                 dfs(s|(<<(j-)));//向下搜
                 dis[j]=odd;//返回原来值
             }
         }
     }
 }

 int main()
 {
     scanf("%d%d",&n,&m);
     memset(v,0x3f,sizeof(v));
     for(int i=;i<=m;i++)
     {
         int x=,y=,z=;
         scanf("%d%d%d",&x,&y,&z);
         v[x][y]=v[y][x]=min(v[y][x],z);
     }//邻接矩阵存图
     for(int i=;i<=n;i++)
     {
         memset(dp,0x3f,sizeof(dp));
         fake=dp[];//每次的更新
         memset(dis,0x3f,sizeof(dis));
         dis[i]=;
         dp[(<<(i-))]=;//赋初值
         dfs(<<(i-));
         ans=min(ans,dp[(<<n)-]);//更新答案
     }
     printf("%d\n",ans);
     return ;
 }

AC--treasure

状压中的技巧

求最后完备状态（假设都是1），有n个待枚举状态，结果是（1<<n）-1

要只取i这一位是1，其他都是0，那么（1<<(i-1)）

T3：列队

期望得分：30分

实际得分：30分

考场心路历程：题意还是比较亲民的，管他呢30分暴力先打上再说。后来详见这张图...

正解：动态开点线段树（名字都没听说过.......）

从上面那张图中，我们可以看出，我考场的心路历程十分混乱==想到链表是因为基础知识不牢，忘记了链表的适用范围与优点，结果在这块浪费了不少时间。感觉考2015时还有这次，都反而在T3，难度较大的题目上用的时间比T2多，结果给得分率可能更高的T2思考少了空间。这是需要改正的==。

Day2小结：暴露出的问题是基础知识不牢，一直想自己捋一捋了，不过搞不动就很难受==听说听课以后有时间让我们自己整理一下，就很好；还有问题是时间用的不太紧，这几次都是这样，前松后紧了，导致交卷前5分钟还在码代码感觉就会很不好，容易出锅，以及刚才说的T2与T3时间分配的问题；还有问题是暴力的分拿不准，审题出现不准的问题。

Day1

T1：小凯的诱惑

期望得分：100分

实际得分：100分

考察：数论数学&结论

小学奥数题目，可能是去年在noip考场上最认真做的一道题（当时其他题看都看不懂），敲了无数if语句，NOIP2017抱了5分回家==。

注意开longlong！

 #include<cstdio>
 #include<algorithm>

 using namespace std;
 typedef long long ll;

 ll a,b,c;

 int main()
 {
     freopen("math.in","r",stdin);
     freopen("math.out","w",stdout);
     scanf("%lld%lld",&a,&b);
     c=a*b-(a+b);
     printf("%lld",c);
     return ;
 }

math

T2：时间复杂度

期望得分：100分

实际得分：60分

考察：字符串处理&模拟

思路：之前没做过啊...今天的考试又名只做第二题（逃）。第三题看上去十分不可做的样子，草草打了30分开始专心致志写第二题。写的时候思路还是比较清楚的，还是有一些细节没写好以及最后时间紧张心态几乎爆炸，所以丢了40分==。

　　    首先是读入。注意到每个循环语句都由四个部分组成，我便用了一个结构体来储存各条语句。里面包含几个字符数组。

　　　之后是判错，觉得判错应该是先处理好的，如果有错就不应再检查复杂度了。注意到题面里写着只可能有两种错误 ：F与E不匹配--这个可以用一个栈来维护。新建的变量与已经存在但未被销毁的变量重复两种情况--可以用bool数组来维护这个变量是否曾经存在但未被销毁。打这一部分用了大概几乎一小时，时间有点浪费了。先后出现了多组数据清空结构体有些麻烦的问题和数组开小了的问题（大样例真香）。不过打完觉得判错这部分应该是稳了。这时已经是17:13。

　　　 再之后是查错了。查错分为两部分：先把小明认为的复杂度处理出来（因为是用字符串读进来的，而且可能不是一位数），以及计算正确的复杂度。而我计算的基本思想是，如果循环嵌套，就在答案上加1，如果是常数类的，就加零。也就是把乘法巧妙的转化为加法。当时我对自己的想法还是有些怀疑的，但是时间真的不够了，今天还要早收卷==写完大致后就开始调调调调大样例，没有再瞪眼检查样例可能涉及不到的细节了。然后处理小明认为的复杂度时还是出锅了...虽然有之前做另一道恶心的模拟题相对分子质量的转化数字经验==。具体的锅是：字符数组的下标和循环的下标搞混了，还有用ksm进位的时候乘方乘多了...这个时候大家已经都跑饭去惹==，还好坚持下来苟了60分，要不60分都得不了==。

　　　 所以到底是哪里错了呢？开始下载洛谷数据检查。首先发现：用来记录循环是否不能再记录（无法进入的循环）的flag在每一次后没有更新。交一发后多了10分。继续检查，发现一种循环的特殊情况：就是多个循环嵌套以后结束了几个循环，之后又开始了一系列循环。这样我们更新答案的时候就可能会少记录或者多记录一些东西。最后改变策略，将更新答案的条件放宽，一边更新一边减去结束的循环，这样就A了。

 // 17:13 err解决 感动！
 // 17:56 算出正确复杂度
 #include<cstdio>
 #include<algorithm>
 #include<stack>
 #include<cstring>
 #include<cctype>

 using namespace std;

 int T,lin;
 bool vis[];
 char sta[];

 // tmp
 struct node{
     char l[],r[];
     char fir[],cha[];
 }word[]; 

 int ksm(int a,int b)
 {
     int ans=;
     while(b)
     {
         if(b&) ans=ans*a;
         b>>=;
         a=a*a;
     }
     return ans;
 }

 void read()
 {
     for(int i=;i<=lin;i++)
     {
         scanf("%s",word[i].fir+);
         if(word[i].fir[]=='F')
         {
             scanf("%s",word[i].cha+);
             scanf("%s%s",word[i].l+,word[i].r+);
         }
     }
 }

 bool checkerr()
 {
     stack<int>sf;
     for(int i=;i<=lin;i++)
     {
         if(word[i].fir[]=='F')
         {
             sf.push(i);
             if(vis[(int)word[i].cha[]]==) return ;
             vis[(int)word[i].cha[]]=;
         }
         else if(word[i].fir[]=='E')
         {
             if(sf.empty()) return ;
             int u=sf.top();
             sf.pop();
             vis[(int)word[u].cha[]]=;
         }
     }
     if(!sf.empty()) return ;
     return ;
 }

 bool illegal(int pos)
 {
     int len1=strlen(word[pos].l+);
     int len2=strlen(word[pos].r+);
     int rl=,rr=;
     for(int i=;i<=len1;i++)
         rl+=ksm(,len1-i)*((int)word[pos].l[i]);
     for(int i=;i<=len2;i++)
         rr+=ksm(,len2-i)*((int)word[pos].r[i]);
     if(rl>rr) return ;
     return ;
 }

 int getsta()
 {
     int pos=,ans=;
     while(isdigit(sta[pos])) pos++;
     pos--;
     int len=pos-+;
     int nowpos=;
     for(int i=;i<=len;i++)
     {
         ans+=ksm(,len-i)*((int)sta[nowpos]-'');
         nowpos++;
     }
     return ans;
 }

 int checktim()
 {
     stack<int>se;
     int ans=,tmp1=,tmp2=;
     bool flag=;
     for(int i=;i<=lin;i++)
     {
         if(word[i].fir[]=='F')
         {
             se.push(i);
             if(word[i].l[]=='n'&&word[i].r[]!='n') flag=;
             if(word[i].l[]!='n'&&word[i].r[]!='n'&&illegal(i))
                 flag=;
             if(!flag)
             {
                 if(word[i].r[]=='n'&&word[i].l[]!='n') tmp1++;
                 else tmp2++;
             }
         }
         else if(word[i].fir[]=='E')
         {
             se.pop();
             ans=max(ans,tmp1);
             tmp1--;
             if(se.empty())
             {
                 if(tmp1) ans=max(ans,tmp1);
                 else ans=max(ans,);
                 tmp1=,tmp2=;flag=;
             }
         }
     }
 //    return ans;
     if(sta[]==''&&ans==) return ;
     if(sta[]==''&&ans!=) return ;
     int qwq=getsta();
 //    printf("%d ",qwq);
 //    printf("%d ",ans);
     if(qwq==ans) return ;
     else return ;
 }

 void init()
 {
     for(int i=;i<=lin;i++)
     {
         if(word[i].fir[]=='E') memset(word[i].fir+,,sizeof(word[i].fir+));
         else
         {
             memset(word[i].fir+,,sizeof(word[i].fir+));
             memset(word[i].cha+,,sizeof(word[i].cha+));
             memset(word[i].l+,,sizeof(word[i].l+));
             memset(word[i].r+,,sizeof(word[i].r+));
         }
     }
     memset(vis,,sizeof(vis));
 }

 int main()
 {
     scanf("%d",&T);
     while(T--)
     {
         scanf("%d",&lin);
         scanf("%s",sta+);
         read();
         if(checkerr())
         {
             printf("ERR\n");
             init();
             continue;
         }
     //    printf("%d\n",checktim());
         if(checktim()) printf("Yes\n");
            else printf("No\n");
         init();
     }
     return ;
 }

complexity

小结：这道题虽然做的还是不尽如人意==，但是也有进步（了吧？）。毕竟最后时间压的很紧的情况下还是比较稳的改错，然后开始写判断err的代码的时候也比较稳。不足的地方是时间把握的还是比较松散，或者说是码力不足打不动，以及细节没考虑完备，面向大样例编程而不是完备整个思维qwq。

留下几个大模拟的坑题（高爸推荐：杀蚂蚁、PASTE）。

T3：逛公园

期望得分：30分

实际得分：0分

考场心路历程：观察到k=0有三个点，可以直接使用最短路计数算法，一顿敲敲敲。等等，无解的 情况怎么判断？等填坑。还要去做第二题啊qwq。

结果发现自己原来掌握的最短路计数算法其实是有问题的，趁这个机会学（改正）了一下，真的是裸的最短路计数算法。改后（学后）就是30分了。

正解是记忆化搜索+dp，自己本来搜索和dp就很弱，两个一起来，更不知所措了qwq。

Day1小结：今天的时间利用应该是比昨天高效了许多，不过，现实中，T1你会在一分钟内保证AC地切掉，然后再心态稳地去打T2T3？时间用的不好还是码力不高，思维欠提升，思考问题的能力有待改善。T2也告诉我们要先肉眼查错，不断给自己设计反例，确保全面正确。

两天期望得分：100+100+30+100+40+30=400

实际得分：100+60+0+100+0+30=290，挂了两道题......

期望和实际差的太多，就是说自己写出的程序不能保证正确，也就是说平时做题的正确率低。

自己的一些知识点还是太弱了，只掌握在皮毛的水平，比如：线段树，状压dp等。水平在300分上下徘徊，暴力的分反而没正解的分稳。

希望把基础知识砸牢后，思维水平也会有一个新的提升吧。