佳木斯市第一中学NOIP真题模拟赛（19.8.24—19.8.25）游记
NOIP2013真题测试，先简单总结一下成绩。
Day1 180分
一般般的成绩，T1A掉，T2依靠玄学算法搞到了70分，T3的10分就很惨了，想到了LCA却没有继续往下想最大生成树，还是比较菜的
Day2 210分Day2貌似来手感了
T1，T2A掉，T3还是只有可怜巴巴的10分，暴力广搜真的没有get到，打开一看就跑去写dfs了
总分 390分
个人认为还算可以，毕竟是一年的蒟蒻 ，看了下当年的分数线，发现并不是很高，然而tf告诉我现在考分数线最少300分……emmmmmm心里一凉。
Day 1
T1 转圈游戏
T1瞄一眼，10^9，搞毛啊，仔细一看居然是道快速幂水题，速度十分钟搞完，调试一下，出了几组数据搞一搞，就完事了
代码简洁，相信一看就明白了
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,k,x;
ll qpow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans=(ans*a)%n;
a=(a*a)%n; b>>=1;
}
return ans;
}
int main()
{
scanf("%lld%lld%lld%lld",&n,&m,&k,&x);
int t=qpow(10,k);
int res=(m*t)%n;
printf("%lld",(x+res)%n);
return 0;
}
其实没必要开long long ，考场上比较谨慎还是选择开了long long
T2 火柴排队
考场上的玄学方法,显然我们需要找两组数中相差最小的，每次对于第一组数a[i]中第i个数在第二组数b[i]中寻找与a[i]相差最小的数的位置，记为pos，每次移动时，需要将i到pos中所有的数位置向后移动一位，时间复杂度O（n^2），期望得分60pts，实际得分70pts
代码我忘记存了
满分算法：使a[i]中第k大的数与b[i]中第k大的数放在同一位置，即为最优答案
T3 货车运输
考场上想到了LCA，但发现是一个图就没再继续想，正解是最大生成树+LCA，最大生成树可以用并查集的Kruskal，将边权改为从大到小排序即可，LCA使用倍增LCA即可，在预处理倍增LCA时可预处理出minn[u][i]，表示以u为起点，向上跳2^i次所经过最小的限重，在LCA时可以同时处理出路径上的最优解。
代码如下：
#include <bits/stdc++.h>
using namespace std;
#define maxm 100005
#define maxn 100005
#define INF 0x3f3f3f3f
int head[maxn],f[maxn],ff[maxn][25],deep[maxn],minn[maxn][25],vis[maxn];
int n,m,q,cnt=0;
struct node
{
int x,y,val;
}ee[maxm];
struct Node
{
int to,next,w;
}e[maxn*2];
inline int read()
{
int w=1,s=0; char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')w=-1; ch=getchar();}
while(ch>='0' && ch<='9'){s=s*10+ch-'0'; ch=getchar();}
return w*s;
}
int find(int x)
{
if(x==f[x]) return x;
return f[x]=find(f[x]);
}
bool cmp(node a,node b)
{
return a.val>b.val;
}
void add(int x,int y,int v)
{
cnt++;
e[cnt].to=y;
e[cnt].w=v;
e[cnt].next=head[x];
head[x]=cnt;
}
void kruskal()
{
for(int i=1;i<=n;i++) f[i]=i;
sort(ee+1,ee+m+1,cmp);
for(int i=1;i<=m;i++)
{
int x=ee[i].x,y=ee[i].y,v=ee[i].val;
int rx=find(x),ry=find(y);
if(rx!=ry)
{
f[rx]=ry;
add(x,y,v); add(y,x,v);
}
}
}
void dfs(int u)
{
vis[u]=1;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to,dis=e[i].w;
if(vis[v]) continue;
ff[v][0]=u; deep[v]=deep[u]+1; minn[v][0]=dis;
dfs(v);
}
}
int LCA(int x,int y)
{
if(find(x)!=find(y)) return -1;
int res=INF;
if(deep[x]<deep[y]) swap(x,y);
for(int i=22;i>=0;i--)
{
if(deep[ff[x][i]]>=deep[y])
{
res=min(minn[x][i],res); x=ff[x][i];
}
}
if(x==y) return res;
for(int i=22;i>=0;i--)
{
if(ff[x][i]!=ff[y][i])
{
res=min(res,min(minn[x][i],minn[y][i]));
x=ff[x][i]; y=ff[y][i];
}
}
return min(res,min(minn[x][0],minn[y][0]));
}
int main()
{
n=read(); m=read();
for(int i=1;i<=m;i++)
{
ee[i].x=read(); ee[i].y=read(); ee[i].val=read();
}
kruskal();
for(int i=1;i<=n;i++)
{
if(!vis[i]) {deep[i]=0; dfs(i); ff[i][0]=i; minn[i][0]=INF;}
}
for(int i=1;i<=22;i++)
{
for(int u=1;u<=n;u++)
{
ff[u][i]=ff[ff[u][i-1]][i-1];
minn[u][i]=min(minn[ff[u][i-1]][i-1],minn[u][i-1]);
}
}
q=read();
while(q--)
{
int x=read(),y=read();
printf("%d\n",LCA(x,y));
}
return 0;
}
Day 2
T1 积木大赛
考场上：这题我见过！
作为去年刚学两个月参加NOIP2018的我对第一题印象深刻，唯一得到70分的题，当时暴力找最长区间进行修改，时间复杂度O（n^2），期望得分：70分，实际得分：70分
正解：可以发现每次处理一个位置时，若此位置比前一位置小，那么此位置必定能被前一位置顺带处理，若此位置比前一位置大，那么在处理完前一位置后还需要加上剩余的次数，即（h-now）次（now 前一位置高度，h 当前高度），所以想法很简单了，从头到尾扫一遍，记录前一位置和当前位置，若当前位置大于前一位置，那么ans+=（h-now）
代码如下
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
int w=1,s=0; char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')w=-1; ch=getchar();}
while(ch>='0' && ch<='9'){s=s*10+ch-'0'; ch=getchar();}
return w*s;
}
int main()
{
int n;
n=read();
int ans=0,now=0;
ans=read(); now=ans;
for(int i=1;i<n;i++)
{
int h=read();
if(now<h) ans+=h-now;
now=h;
}
printf("%d",ans);
}
T2 花匠
题目中说的十分复杂，但是我们画图理解后可以发现，人话题目就是从长度为n的数列中取出m个数，使任意除去首尾的其他数要么满足当前数大于左右两边的数，或者满足当前数小于左右两边的数，画图可以知道，这题就是让我们求波峰和波谷的个数，flag记录当前递增或是递减，发现当前数是波峰或波谷时ans++，并改变flag，为了最大化m，首尾数字必区，所以需要加2，当然我在循环中处理了最后的数字，所以只需要+1
代码如下
#include <bits/stdc++.h>
using namespace std;
#define maxn 1000005
int h[maxn],n;
inline int read()
{
int w=1,s=0; char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')w=-1; ch=getchar();}
while(ch>='0' && ch<='9'){s=s*10+ch-'0'; ch=getchar();}
return w*s;
}
int main()
{
n=read();
for(int i=1;i<=n;i++) h[i]=read();
bool flag=0;
int ans=0;
if(h[2]>=h[1]) con=1;
for(int i=2;i<=n;i++)
{
if(flag==0 && i==n) {ans++; break;}
if(flag==1 && h[i+1]<h[i]){ans++; flag=0; continue;}
else if(flag==0 && h[i+1]>h[i]){ans++; flag=1; continue;}
}
printf("%d",ans+1);
}
T3 华容道
考试真是脑子抽了，dfs居然用来求最短路径
暴力分给的很足，然而我还是没拿到 ，广搜即可，因为挪动棋子可以变相看作挪动空格，所以每次广搜空格上、下、左、右的格子，广搜深度即最终答案，期望得分：70分
正解：广搜+最短路
这里的最短路推荐使用SPFA，比较好理解
spfa最短路 起点可能不在图中，再跑bfs连边。最后的目标状态就是指定棋子在tx,ty，然后枚举空格子在tx,ty的上下左右求最小。