NOIP2014 DAY1 题解_综合

NOIP2014 DAY1

文章目录

NOIP2014 DAY1
- 前言
- T1 生活大爆炸版石头剪刀布
- - 题目
  - 思路
  - 正解代码
- T2 联合权值
- - 题目
  - 题外话
  - 思路
  - 正解代码
- T3 飞扬的小鸟
- - 题目
  - 题外话
  - 思路
  - 正解代码

前言

NOIP2018即将来临，教练为了训练我们这些~~初中的~~人，就把这套题发给我们做。。。

然而，第二题我毫无思路，第三题却少打了一句话就爆炸了QAQ。。。

绝望。。。。。。。。。。。。

T1 生活大爆炸版石头剪刀布

题目

题目传送门（洛谷）

思路

很明显的一道模拟题，唯一要注意的是：我们要把给定的表格的下半部分（灰框区域）自己填好。

~~（看不懂的自己去看代码吧）~~

正解代码

#include<cstdio> #include<algorithm> using namespace std;const int Maxn=200; int f[][6]={
     {
     0,-1,1,1,-1},{
     -2,0,-1,1,-1},{
     -2,-2,0,-1,1},{
     -2,-2,-2,0,1},{
     -2,-2,-2,-2,0}}; //1表示小A胜，0表示平，-1表示小B胜，-2表示表格中灰框部分int N,Na,Nb; int a[Maxn+5],b[Maxn+5];int main() {
     #ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d %d %d",&N,&Na,&Nb);for(int i=1;i<=Na;i++)scanf("%d",&a[i]);for(int j=1;j<=Nb;j++)scanf("%d",&b[j]);for(int i=0;i<5;i++)for(int j=0;j<i;j++)f[i][j]=-f[j][i];//注意填充灰框部分！！！int cnta,cntb,i,j;i=j=1,cnta=cntb=0;for(int k=1;k<=N;k++) {
     if(i>Na)i=1;if(j>Nb)j=1;//注意出拳有周期！int now=f[a[i]][b[j]];if(now==-1)cntb++;if(now==1)cnta++;i++,j++;}//模拟printf("%d %d\n",cnta,cntb);return 0; }

T2 联合权值

题目

题目传送门（洛谷）

题外话

我写了一个树形DP，结果发现我无法写出状态转移方程。。。

然后，我想到了暴力做法，结果发现要超时。。。

然后，我就GG了。。。QAQ。。。

考试结束后我去看了一下大佬的博客，发现这道题竟然如此简单。。。

思路

首先题目告诉你这是一棵树。

题目要求是一个有序点对 $(u, v), (v, u)$ 。我们不难发现这两个的值是相同的，所以我们就只计算 $(u, v)$ ，最后将答案乘 $2$ 即可。

接下来想到了什么？树形DP？？LCA？？还是什么乱七八糟的东西？？？

这就是一个普通的DFS。。。~~（我怎么就没有想到呢？？？）~~

首先考虑暴力做法：

对于树上的每个节点 $u$ ，首先枚举它的每条边 $e_1$ ，接着枚举它的儿子 $v$ 的边 $e_2$ ，再将其乘上，累加到答案中去。

明显超时。。。。。。

我们考虑一下优化：

当我们枚举以 $u$ 为中间点的出边时，设这些连着的点为 $v1,v2,v3,…,vmv_1,v_2,v_3,\ldots ,v_m$ ，其中 $m$ 为 $u$ 的邻接点的数量。

不难得到联合权值： $S=v1v2+v1v3+v1v4+?+v1vm+v2v3+v2v4+?+v2vm+?+vm?1vmS=v_1v_2+v_1v_3+v_1v_4+\cdots+v_1v_m+v_2v_3+v_2v_4+\cdots+v_2v_m+\cdots+v_{m-1}v_m$ 。

用分配律合并一下： $S=v2v1+v3(v1+v2)+v4(v1+v2+v3)+?+vm(v1+v2+v3+?+vm?1)S=v_2v_1+v_3(v_1+v_2)+v_4(v_1+v_2+v_3)+\cdots+v_m(v_1+v_2+v_3+\cdots+v_{m-1})$ 。

因此，在枚举 $u$ 的出边 $e_1$ 时，设 $s$ 为已经枚举过的点的权值和，则我们就可以省去枚举 $e_2$ 的时间，时间复杂度则降至 $O (N)$

正解代码

#include<vector> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;const int Maxn=200000; const int Mod=10007;vector<int> G[Maxn+2]; inline void addedge(int u,int v) {
     G[u].push_back(v); }int N,W[Maxn+2]; int maxx=-1,ans=0;void DFS(int u,int fa) {
     int sum=W[fa],maxt=W[fa];for(int i=0;i<G[u].size();i++) {
     int v=G[u][i];if(v==fa)continue;DFS(v,u);ans=(ans+sum*W[v])%Mod;sum=(sum+W[v])%Mod;maxx=max(maxx,maxt*W[v]);maxt=max(maxt,W[v]);} }int main() {
     #ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d",&N);for(int i=1;i<N;i++) {
     int u,v;scanf("%d %d",&u,&v);addedge(u,v);addedge(v,u);}for(int i=1;i<=N;i++)scanf("%d",&W[i]);DFS(1,0);ans=(ans*2)%Mod;//注意取模！printf("%d %d\n",maxx,ans);return 0; }

T3 飞扬的小鸟

题目

题目传送门（洛谷）

题外话

这道题坑掉了我两个小时。。。

因为我用了一个小时来调。。。

就是因为这句话：
当我发现这一切的时候，考试已经结束了QAQ。。。

思路

不难看出，这道题向上跳跃是一个完全背包，向下掉是一个01背包。

所以我们定义状态 $f [i] [j]$ 为当前在第 $i$ 列（换句话说，也就是第 $i$ 单位时间）第 $j$ 行所需要的点击次数。

记 $u [i]$ 为上面的水管所达到的高度， $d [i]$ 为下面水管所达到的高度。

向下的状态转移方程非常好写： $f[i][j]=\min\{f[i-1][j+Y[i]]\}$ 。

其中， $d [i] < j < u [i]$ 且 $j+Y[i]≤Mj+Y[i]\le M$ ~~（我就是少写了这句话。。。）~~

再来考虑向上的：

我们不难列出状态转移方程： $f[i][j]=\min\{f[i-1][j-k*X[i]]+k\}$

其中， $1≤j<M1\le j<M$ 且 $k<?jX[i]?k<\lfloor\frac{j}{X[i]}\rfloor$ 。

注意在计算结束后将不合法状态值全部赋为INF（即有水管的地方）

但是我们不难看出，这是一个要超时的算法，所以我们必须对它进行优化：

对于状态 $f [i] [j]$ ，我们可以发现，这个状态可以由两个状态转移而来：

$f [i ? 1] [j ? X [i]] + 1$ ，即上一单位时间点击一次，然后到达 $f [i] [j]$ ；
$f [i] [j ? X [i]] + 1$ ，即这个单位时间再点一次，然后到达 $f [i] [j]$ 。

所以，这种转移的时间复杂度就优化为了 $O (M)$ 。

注意，由于在玩的时候是可以顶到天花板的，所以我们还需要一次转移，即再点一次顶到天花板上。

综上所述，我们不难列出状态转移方程： $f[i][j]={min?{f[i?1][j?X[i]]+1,f[i][j?X[i]]+1}0≤i<N,X[i]≤j<Mmin?{f[i?1][j]+1,f[i][j]+1}0≤i<N,M?X[i]≤j<Mmin?{f[i?1][j+Y[i]]}0≤i<N,d[i]<j<u[i],j+Y[i]<Mf[i][j]=\begin{cases}\min\{f[i-1][j-X[i]]+1,f[i][j-X[i]]+1\}&0\le i<N,X[i]\le j<M\\ \min\{f[i-1][j]+1,f[i][j]+1\}&0\le i<N,M-X[i]\le j<M\\\min\{f[i-1][j+Y[i]]\}&0\le i<N,d[i]<j<u[i],j+Y[i]<M\end{cases}$

注意一定要将不合法状态赋为INF！！！

正解代码

注意由于C++中没有负下标，所以我将 $f$ 数组平移了一格，其它不变。

#include<cstdio> #include<cstring> #include<algorithm> using namespace std;const int Maxn=10000; const int Maxm=1000; const int INF=0x3f3f3f3f;int N,M,K; int X[Maxn+1],Y[Maxn+1]; int d[Maxn+1],u[Maxn+1]; int f[Maxn+1][Maxm+1];int main() {
     #ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d %d %d",&N,&M,&K);for(int i=1;i<=N;i++)d[i]=0,u[i]=M+1;//预处理，将没有水管的位置的u[i]设为M+1for(int i=0;i<N;i++)scanf("%d %d",&X[i],&Y[i]);for(int i=1;i<=K;i++) {
     int p,l,h;scanf("%d %d %d",&p,&l,&h);d[p]=l,u[p]=h;}for(int i=1;i<=N;i++)for(int j=0;j<=M;j++)f[i][j]=INF;f[0][0]=INF;for(int i=1;i<=N;i++) {
     for(int j=X[i-1];j<=M;j++) {
     //点了一下f[i][j]=min(f[i][j],f[i-1][j-X[i-1]]+1);f[i][j]=min(f[i][j],f[i][j-X[i-1]]+1);}for(int j=M-X[i-1];j<=M;j++) {
     //到顶f[i][M]=min(f[i][M],f[i-1][j]+1);f[i][M]=min(f[i][M],f[i][j]+1);}for(int j=d[i]+1;j<u[i];j++)//不点if(j+Y[i-1]<=M) f[i][j]=min(f[i][j],f[i-1][j+Y[i-1]]);for(int j=1;j<=d[i];j++)f[i][j]=INF;for(int j=u[i];j<=M;j++)f[i][j]=INF;}int cnt=K;//记录越过多少根水管int ans=INF;//记录点击的最少次数for(int i=N;i>=1;i--) {
     for(int j=d[i]+1;j<u[i];j++)ans=min(ans,f[i][j]);if(ans<INF)break;//注意找到答案即输出！if(u[i]!=M+1)cnt--;//当未到达终点且有一根水管没有过时计数器应减1}//找答案if(cnt==K)printf("1\n%d\n",ans);else printf("0\n%d\n",cnt);#ifdef DEBUGfor(int i=1;i<=N;i++) {
     for(int j=1;j<=M;j++)if(f[i][j]==INF)printf("INF ");else printf("%3d ",f[i][j]);puts("");}#endifreturn 0; }