【解题报告】 NOIP2016
Day1
T1 玩具谜题
思路
快乐暴力模拟
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
int n,m;
using namespace std;
struct people
{
int dir;
char job[150];
}a[100005];
int b[100005],s[100005];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i].dir;
scanf("%s",a[i].job);
}
for(int i=1;i<=m;i++)
{
cin>>b[i]>>s[i];
}
int ans=1;
for(int i=1;i<=m;i++)
{
if(a[ans].dir==0)
{
if(b[i]==0)
ans=(ans-s[i]+n)%n;
if(b[i]==1)
ans=(ans+s[i])%n;
if(ans==0)
ans=n;
}
else if(a[ans].dir==1)
{
if(b[i]==0)
ans=(ans+s[i])%n;
if(b[i]==1)
ans=(ans-s[i]+n)%n;
if(ans==0)
ans=n;
}
}
printf("%s\n",a[ans].job);
return 0;
}
T2 天天爱跑步
思路
Day1T2就这个难度了？ 恐慌
首先这是一棵树
我们可以按照顺序模拟，也就是一堆人在走路
如果是树的话，平均下来深度是 \(log n\) 的，那么有 \(m\) 个人，时间复杂度就是 \(O(mlog n)\) ，但是数据范围中提到了，这棵树可能会退化成一条链，这样时间复杂度就变成了 \(O(nm)\) ，显然时间复杂度会爆炸
所以我们想，正解肯定不是直接模拟（这还用说
然后我们发现，实际上我们可以转换一个角度，从观察员的角度进行思考
我们要看的就是对于每个观察员结点，有多少个结点在第 \(w_j\) 秒可以到达观察员结点
我们枚举观察员就是 dfs 一整棵树的过程，时间复杂度 \(O(n)\)
然后我们想，对于一个观察员有哪些结点会为他做贡献呢？
我们分类讨论对于一个观察员结点P在一条路径上的情况，其中起点为 \(s\) ，终点为 \(t\)
- \(P\) 在 \(s\) 到 \(lca\) 的路上
可以画一下，如果起点 \(s\) 满足 \(dep[s]=w[P]+dep[P]\) ，这样这个起点这个结点就会为 \(P\) 产生一个贡献
- \(P\) 在 \(lca\) 到 \(t\) 的路上
同样可以画一下
我们可以定义 \(dis(i,j)\) 表示 从 \(i\) 出发到 \(j\) 的路径长度
所以我们可以得到
\(dis(s,t)-w[P]=dep[t]-dep[P]\)
\(=dis(s,t)-dep[t]=w[P]-dep[P]\)
当终点满足上式的时候，终点会为 \(P\) 做一个贡献
我们发现，不管怎么样，为 \(P\) 能做贡献的结点一定在 \(P\) 的子树上
递归以 \(P\) 为根的子树的时候，可以统计出来子树中所有起点和终点对他的贡献
但是我们发现，子树中有些起点和终点对 \(P\) 产生了贡献，有些没贡献
桶的用法我是真不懂草
然后就寄了
然后如果 \(P\) 和起点或者终点重合的话，这个贡献会重复计数一次，所以要减一
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
const int maxn=300000;
int n,m;
int dep[maxn],fa[maxn][20];
int w[maxn];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
//边表
struct edge{
int e,next;
}ed[maxn<<1],ed1[maxn<<1],ed2[maxn<<1];
int en,en1,en2;
int first[maxn],first1[maxn],first2[maxn];
void add_edge(int s,int e)
{
en++;
ed[en].next=first[s];
first[s]=en;
ed[en].e=e;
}
void add_edge1(int s,int e)
{
en1++;
ed1[en1].next=first1[s];
first1[s]=en1;
ed1[en1].e=e;
}
void add_edge2(int s,int e)
{
en2++;
ed2[en2].next=first2[s];
first2[s]=en2;
ed2[en2].e=e;
}
//lca部分
void dfs1(int x)
{
for(int i=1;(1<<i)<=dep[x];i++)
fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=first[x];i;i=ed[i].next)
{
int e=ed[i].e;
if(e==fa[x][0]) continue;
fa[e][0]=x;
dep[e]=dep[x]+1;
dfs1(e);
}
}
int get_lca(int x,int y)
{
if(x==y) return x;
if(dep[x]<dep[y]) swap(x,y);
int t=log(dep[x]-dep[y])/log(2);
for(int i=t;i>=0;i--)
{
if(dep[fa[x][i]]>=dep[y])
x=fa[x][i];
if(x==y)
return x;
}
t=log(dep[x])/log(2);
for(int i=t;i>=0;i--)
{
if(fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
}
return fa[x][0];
}
int b1[maxn<<1],b2[maxn<<1];
int path_cnt[maxn];
int dis[maxn],s[maxn],t[maxn];
int l[maxn],ans[maxn];
void dfs2(int x)
{
int t1=b1[w[x]+dep[x]];
int t2=b2[w[x]-dep[x]+maxn];
for(int i=first[x];i;i=ed[i].next)
{
int e=ed[i].e;
if(e==fa[x][0]) continue;
dfs2(e);
}
b1[dep[x]]+=path_cnt[x];
for(int i=first1[x];i;i=ed1[i].next)
{
int e=ed1[i].e;
b2[dis[e]-dep[t[e]]+maxn]++;
}
ans[x]+=b1[w[x]+dep[x]]-t1+b2[w[x]-dep[x]+maxn]-t2;
for(int i=first2[x];i;i=ed2[i].next)
{
int e=ed2[i].e;
b1[dep[s[e]]]--;
b2[dis[e]-dep[t[e]]+maxn]--;
}
}
int main()
{
dep[1]=1; fa[1][0]=1;
n=read(),m=read();
for(int i=1;i<=n-1;i++)
{
int x=read(),y=read();
add_edge(x,y);
add_edge(y,x);
}
dfs1(1);
for(int i=1;i<=n;i++)
w[i]=read();
for(int i=1;i<=m;i++)
{
s[i]=read(),t[i]=read();
int lca=get_lca(s[i],t[i]);
dis[i]=dep[s[i]]+dep[t[i]]-2*dep[lca];
path_cnt[s[i]]++;
add_edge1(t[i],i);
add_edge2(lca,i);
if(dep[lca]+w[lca]==dep[s[i]])
ans[lca]--;
}
dfs2(1);
for(int i=1;i<=n;i++)
cout<<ans[i]<<" ";
return 0;
}
T3 换教室
思路
一道期望DP，应该也是NOIP历史上第一次出现的期望DP的题目
首先了解一下期望的概念
然后按照普通的动态规划做
这个思路很简单，就是设置一个状态的问题
设 \(f[i][j][0/1]\) 表示选到了第 \(i\) 个教室，已经选择调换 \(j\) 个教室，我们是否调换 \(i\) ，这样我们可以得到的最小的期望
这个状态转移方程很好理解，主要是方程太沃泰默长了
\[f[i][j][0]=\\min(f[i][j][0],\\min(f[i-1][j][0]+a[c[i-1]][c[i]],\\f[i-1][j][1]\\+a[c[i-1]][c[i]]*(1-k[i-1])\\+a[d[i-1]][c[i]]*k[i-1]));
\]
\[f[i][j][1]=\\min(f[i][j][1],\\min(f[i-1][j-1][0]\\+a[c[i-1]][c[i]]*(1-k[i])\\+a[c[i-1]][d[i]]*k[i],\\f[i-1][j-1][1]+a[d[i-1]][d[i]]*k[i]*k[i-1]\\+a[d[i-1]][c[i]]*k[i-1]*(1-k[i])\\+a[c[i-1]][d[i]]*(1-k[i-1])*k[i]\\+a[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i])));
\]
都弄成这样了才能看草
然后就直接码就好了，对于最短路径的话，因为点很少，边很多，直接 \(Floyd\) 预处理就好了
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn=2005;
const double INF=1e17+5;
int n,m,v,e;
int c[maxn],d[maxn],a[305][305];
double k[maxn],f[maxn][maxn][2];
double ans;
int main()
{
memset(a,0x3f3f3f,sizeof(a));
cin>>n>>m>>v>>e;
for(int i=1;i<=n;i++)
cin>>c[i];
for(int i=1;i<=n;i++)
cin>>d[i];
for(int i=1;i<=n;i++)
cin>>k[i];
for(int i=1;i<=e;i++)
{
int x,y,w;
cin>>x>>y>>w;
a[x][y]=a[y][x]=min(a[x][y],w);
}
for(int k=1;k<=v;k++)
{
for(int i=1;i<=v;i++)
{
for(int j=1;j<=v;j++)
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
}
}
for(int i=1;i<=v;i++)
a[i][i]=a[i][0]=a[0][i]=0;
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
f[i][j][0]=f[i][j][1]=INF;
f[1][0][0]=f[1][1][1]=0;
for(int i=2;i<=n;i++)
{
f[i][0][0]=f[i-1][0][0]+a[c[i-1]][c[i]];
for(int j=1;j<=min(i,m);j++)
{
f[i][j][0]=min(f[i][j][0],min(f[i-1][j][0]+a[c[i-1]][c[i]],f[i-1][j][1]+a[c[i-1]][c[i]]*(1-k[i-1])+a[d[i-1]][c[i]]*k[i-1]));
f[i][j][1]=min(f[i][j][1],min(f[i-1][j-1][0]+a[c[i-1]][c[i]]*(1-k[i])+a[c[i-1]][d[i]]*k[i],f[i-1][j-1][1]+a[d[i-1]][d[i]]*k[i]*k[i-1]+a[d[i-1]][c[i]]*k[i-1]*(1-k[i])+a[c[i-1]][d[i]]*(1-k[i-1])*k[i]+a[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i])));
}
}
ans=INF;
for(int i=0;i<=m;i++)
ans=min(ans,min(f[n][i][0],f[n][i][1]));
printf("%.2lf",ans);
return 0;
}
Day2
T1 组合数问题
思路
zhx题！！！！
NOIP中第一次出现组合数
小葱！
好了，回归正题
这个题目的话，就是用组合数直接计算 \(C_n^m\)
主要是因为 \(n,m \le 2000\) ，比较小
然后可以 \(O(n^2)\) 预处理组合数
然后 \(O(n^2)\) 二位前缀和统计答案的数量
然后对于每个询问就能 \(O(1)\) 回答了
注意在计算组合数的时候边弄边模 \(k\) 就好了
总的时间复杂度就是 \(O(t+n^2)\)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int n,m,t,k;
int c[2005][2005],s[2005][2005];
void init()
{
c[1][1]=1;
for(int i=0;i<=2000;i++)
c[i][0]=1;
for(int i=2;i<=2000;i++)
{
for(int j=1;j<=i;j++)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;
}
for(int i=2;i<=2000;i++)
{
for(int j=1;j<=i;j++)
{
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
if(!c[i][j])
s[i][j]+=1;
}
s[i][i+1]=s[i][i];
}
}
int main()
{
cin>>t>>k;
init();
while(t--)
{
cin>>n>>m;
if(m>n)
m=n;
cout<<s[n][m]<<endl;
}
return 0;
}
T2 蚯蚓
思路
首先，看到这道题目，我想到了大根堆
每次取出堆顶，按照题意进行模拟，然后把得到的蚯蚓放回来，然后其他的蚯蚓都加 \(q\)
但是用优先队列模拟大根堆时间复杂度直接弄会炸，所以怎么办呢？
我们观察发现，对于一个先切的蚯蚓分成的两个蚯蚓一定比后切的蚯蚓分成的两个蚯蚓更大一些
所以我们直接找最大的不就得了
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#define int long long
using namespace std;
const int maxn=1000005;
const int INF=1e9;
int n,m,q,u,v,t;
int a[maxn];
int add,mx,pos;
queue <int> heap[5];
bool cmp(int x,int y)
{
return x>y;
}
signed main()
{
std::ios::sync_with_stdio(false);
cin>>n>>m>>q>>u>>v>>t;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
heap[1].push(a[i]);
for(int i=1;i<=m;i++)
{
mx=-INF;
for(int j=1;j<=3;j++)
{
if(heap[j].empty())
continue;;
if(heap[j].front()>mx)
{
mx=heap[j].front();
pos=j;
}
}
heap[pos].pop();
int now=mx+add;
if(!(i%t))
cout<<now<<" ";
int jie1=now*u/v;
int jie2=now-jie1;
add+=q;
heap[2].push(jie1-add);
heap[3].push(jie2-add);
}
cout<<'\n';
for(int i=1;i<=m+n;i++)
{
mx=-INF;
pos=0;
for(int j=1;j<=3;j++)
{
if(heap[j].empty())
continue;
if(heap[j].front()>mx)
{
mx=heap[j].front();
pos=j;
}
}
if(!(i%t))
cout<<mx+add<<" ";
heap[pos].pop();
}
return 0;
}
T3 愤怒的小鸟
思路
搜索，或者状压
如果是我这种蒟蒻的话
搜索更好理解一些
我们可以对于当前小鸟，尝试搜索这只小鸟是否在已有的抛物线上
如果在的话，说明这个小鸟不用再多占一个抛物线，所以直接退出
如果不在的话，我们就要考虑这个小鸟和当前其他还没有匹配的小鸟是不是可以组成一个抛物线
如果横坐标相同，显然不行，因为函数是一一对应的映射
然后用公式算一个函数 \(y=ax^2+bx\) 的 \(a,b\)
推导一下：
设函数上两点 \((x_1,y_1),(x_x,y_2)\)
则
\[\begin{cases}
ax_1^2+bx_1=y_1 ①
\\
ax_2^2+bx_2=y_2②
\end{cases}
\]
\(①\times x_2-② \times x_1\) 得
\[a(x_1^2x_2-x_2^2x_1)=y_1x_2-y_2x_1
\]
移项
\[a= \dfrac {y_1x_2-y_2x_1} {x_1^2x_2+x_2^2x_1}③
\]
\(③\) 带入 \(①\) 或者 \(②\)
\[b= \dfrac {y_1-ax_1^2} {x_1}④
\]
然后我们就可以求出来这个函数的 \(a,b\)
如果 \(a<0\) 说明可以构成抛物线，所以我们将这个抛物线加入，把这个猪删除，然后搜索，然后回溯
反之，我们就把这头猪加入单独成为抛物线的行列
然后搜索的时候，如果结果已经大于当前答案了，那么剪个枝直接回去，及时止损
这样就做完了
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn=20;
const double eps=1e-7;
int n,m,ans;
double x[maxn],y[maxn];
double pa[maxn],pb[maxn];
double dx[maxn],dy[maxn];
bool check(double x,double y)
{
return fabs(x-y)<eps;
}
void dfs(int dep,int cnt,int re)
{
if(cnt+re>=ans) return ;
if(dep>n)
{
ans=cnt+re;
return ;
}
bool flag=false;
for(int i=1;i<=cnt;i++)
{
if(check(pa[i]*x[dep]*x[dep]+pb[i]*x[dep],y[dep]))
{
dfs(dep+1,cnt,re);
flag=true;
break;
}
}
if(!flag)
{
for(int i=1;i<=re;i++)
{
if(check(x[dep],dx[i])) continue;
double a=(y[dep]*dx[i]-dy[i]*x[dep])/(x[dep]*x[dep]*dx[i]-dx[i]*dx[i]*x[dep]);
double b=(y[dep]-x[dep]*x[dep]*a)/x[dep];
if(a<0)
{
pa[cnt+1]=a;
pb[cnt+1]=b;
double p=dx[i],q=dy[i];
for(int j=i;j<re;j++)
{
dx[j]=dx[j+1];
dy[j]=dy[j+1];
}
dfs(dep+1,cnt+1,re-1);
for(int j=re;j>i;j--)
{
dx[j]=dx[j-1];
dy[j]=dy[j-1];
}
dx[i]=p,dy[i]=q;
}
}
dx[re+1]=x[dep],dy[re+1]=y[dep];
dfs(dep+1,cnt,re+1);
}
}
int T;
int main()
{
cin>>T;
while(T--)
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>x[i]>>y[i];
ans=10000;
dfs(1,0,0);
cout<<ans<<'\n';
}
return 0;
}