NOIP 2016 题解
D1 T1
玩具谜题 大意：
有 nn个玩具小人围成一圈, 已知它们的职业和朝向。现在第11个玩具小人告诉小南一个包含mm条指令的谜題, 其中第 zz条指令形如“左数/右数第 ss,个玩具小人”。 你需要输出依次数完这些指令后,到达的玩具小人的职业。
Solution:
模拟即可
#include<bits/stdc++.h>
using namespace std;
int ans=1,n,m;
struct ii{
int face;
string job;
}a[100005];
struct jj{
int dt,num;
}b[100005];
void check(int x,int y){
if((a[ans].face==0&&x==0)||(a[ans].face==1&&x==1)){
ans-=y;
}
else{
ans+=y;
}
while(ans<=0){
ans+=n;
}
while(ans>n){
ans-=n;
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i].face>>a[i].job;
}
for(int j=1;j<=m;j++){
cin>>b[j].dt>>b[j].num;
}
for(int l=1;l<=m;l++){
check(b[l].dt,b[l].num);
}
cout<<a[ans].job;
}D1 T2
天天爱跑步：
2016最难一题，卡死无数神仙
给出n条树上的路径，询问对于每一个点，到这一个点的距离为定值的起点，并经过这个点的路径条数。
Solution: 解法很多，这里给出两种
解法1：
LCA+桶+差分（也不能说是差分但又和差分类似）
先对全部玩家进行一些预处理，然后用两个类似的dfs函数对整棵树处理。
最后再做一些微调，就输出答案。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#define N 300009
#define M 600009
using namespace std;
int en,n,m;
int w[N],spn[M],bucket[N+M],ans[N];
vector<int> v1[M],v2[M],v3[M];
struct nod{
int u,v,dis,lca;
}p[N];
struct edge{
int e;
edge *next;
}*v[N],ed[M];
inline void add_edge(int s,int e){
en++;
ed[en].next = v[s],v[s] = ed+en,v[s]->e =e;
}
int read(){
int x = 0;
char ch = getchar();
while(ch < '0' || ch > '9')ch = getchar();
while(ch >= '0' && ch <= '9'){
x = x * 10 + ch - '0';
ch = getchar();
}
return x;
}
int deep[N],f[N][25],dist[N];
bool use[N];
void dfs(int now,int dep){
use[now] = true;
deep[now] = dep;
for(int k = 1;k <= 22; k++){
int j = f[now][k-1];
f[now][k] = f[j][k-1];
}
for(edge *e = v[now];e;e=e->next)
if(!use[e->e]){
f[e->e][0] = now;
dist[e->e] = dist[now]+1;
dfs(e->e,dep+1);
}
use[now] = false;
}
inline int jump(int u,int step){
for(int k = 0; k <= 22; k++)
if((step & (1<<k)))u = f[u][k];
return u;
}
inline int qlca(int u,int v){
if(deep[u] < deep[v])swap(u,v);
u = jump(u,deep[u]-deep[v]);
for(int k = 22; k >= 0; k--)
if(f[u][k] != f[v][k])u = f[u][k],v = f[v][k];
return u == v ? u : f[u][0];
}
void LCA(){ //关于LCA的组件
f[1][0] = 1;
dfs(1,0);
}
inline void dfs1(int now){
use[now] = true;
int prev = bucket[deep[now]+w[now]+N];
for(edge *e = v[now];e;e=e->next)
if(!use[e->e])dfs1(e->e);
bucket[deep[now]+N] += spn[now];
ans[now] += bucket[deep[now]+w[now]+N]-prev;
int len = v1[now].size();
for(int k = 0; k < len;k++)
--bucket[deep[v1[now][k]]+N];
use[now] = false;
}
inline void dfs2(int now){
use[now] = true;
int prev = bucket[w[now]-deep[now]+N];
for(edge *e = v[now];e;e=e->next)
if(!use[e->e])dfs2(e->e);
int len = v2[now].size();
for(int k = 0; k < len; k++)
++bucket[v2[now][k]+N];
ans[now] += bucket[w[now]-deep[now]+N] - prev;
len = v3[now].size();
for(int k = 0; k < len; k++)
--bucket[v3[now][k]+N];
use[now] = false;
}
int main(){
n = read(),m = read();
for(int i = 1; i <= n-1; i++){
int u = read(), v = read();
add_edge(u,v);
add_edge(v,u);
}
for(int i = 1; i <= n; i++)w[i] = read();
LCA();
for(int i = 1; i <= m; i++){ //预处理
int u = read(),v = read();
p[i].u = u;
p[i].v = v;
p[i].lca = qlca(u,v);
p[i].dis = dist[u]+dist[v]-dist[p[i].lca]*2;
spn[u]++;
v1[p[i].lca].push_back(u);
v2[v].push_back(p[i].dis-deep[p[i].v]);
v3[p[i].lca].push_back(p[i].dis-deep[p[i].v]);
}
dfs1(1); //从下至上
dfs2(1); //从上至下
for(int i = 1; i <= m; i++)
if(deep[p[i].u] == deep[p[i].lca]+w[p[i].lca]) ans[p[i].lca]--;
for(int i = 1; i <= n; i++)
printf("%d ",ans[i]);
printf("\n");
return 0;
}解法2：
树链剖分，对于每一个叶子开一棵线段树，动态开点（类似主席树），深度相同放在一棵线段树里，时间：o（nlog^2n），有点类似sdoi2014旅行的做法
#include"algorithm"
#include"iostream"
#include"string.h"
#include"stdlib.h"
#include"stdio.h"
#include"math.h"
#include"vector"
#include"queue"
#include"set"
using namespace std;
template<class MyInt>
void readi(MyInt&x){
x=0;int 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-'0',ch=0,ch=getchar();
x*=f;
}
const int N=300005,LG=20;
int s[N],t[N],h[N],nxt[N*2],to[N*2],tmp,w[N],n,m;
void addedge(int u,int v){nxt[++tmp]=h[u],h[u]=tmp,to[tmp]=v;}
int dfn[N],rel[N],fa[N][LG],sz[N],dep[N],son[N],tot;
void dfs1(int x){
sz[x]=1;for(int i=0;fa[x][i];fa[x][i+1]=fa[fa[x][i]][i],i++);
for(int i=h[x];i;i=nxt[i])if(to[i]!=fa[x][0]){
dep[to[i]]=dep[x]+1,fa[to[i]][0]=x;dfs1(to[i]);
sz[x]+=sz[to[i]];if(sz[son[x]]<sz[to[i]])son[x]=to[i];
}
}
int r1[N*2],r2[N*2],ls[2*N*LG],rs[2*N*LG],tag[2*N*LG],c;
void add(int&x,int l,int r,int pos){
if(!x)x=++c;if(l==r)return;int mid=(l+r)>>1;
if(pos<=mid)add(ls[x],l,mid,pos);else add(rs[x],mid+1,r,pos);
}
void update(int x,int l,int r,int L,int R,int W){
if(!x)return;if(L==l&&R==r){tag[x]+=W;return;}int mid=(l+r)>>1;
if(R<=mid)update(ls[x],l,mid,L,R,W);else if(L>mid)update(rs[x],mid+1,r,L,R,W);
else update(ls[x],l,mid,L,mid,W),update(rs[x],mid+1,r,mid+1,R,W);
}
int qry(int x,int l,int r,int pos){
if(!x||l==r)return tag[x];
if(tag[x]){
if(ls[x])tag[ls[x]]+=tag[x];
if(rs[x])tag[rs[x]]+=tag[x];
tag[x]=0;
}
int mid=(l+r)>>1;
if(pos<=mid)return qry(ls[x],l,mid,pos);
return qry(rs[x],mid+1,r,pos);
}
void dfs2(int x,int r){
dfn[x]=++tot,rel[x]=r;if(son[x])dfs2(son[x],r);
for(int i=h[x];i;i=nxt[i])if(to[i]!=fa[x][0]&&to[i]!=son[x])dfs2(to[i],to[i]);
add(r1[dep[x]+w[x]],1,n,dfn[x]);add(r2[w[x]-dep[x]+N],1,n,dfn[x]);
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);int l=dep[x]-dep[y];
for(int i=0;l;i++)if(l&(1<<i))x=fa[x][i],l^=1<<i;
for(int i=LG-2;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return x==y?x:fa[x][0];
}
void work(int u,int v){
int f=lca(u,v);int x=u;
while(rel[u]!=rel[f]){
update(r1[dep[x]],1,n,dfn[rel[u]],dfn[u],1);
u=fa[rel[u]][0];
}
update(r1[dep[x]],1,n,dfn[f],dfn[u],1);
while(rel[v]!=rel[f]){
update(r2[dep[x]-2*dep[f]+N],1,n,dfn[rel[v]],dfn[v],1);
v=fa[rel[v]][0];
}
update(r2[dep[x]-2*dep[f]+N],1,n,dfn[f],dfn[v],1);
update(r1[dep[x]],1,n,dfn[f],dfn[f],-1);
}
int main(){
// freopen("running.in","r",stdin);
// freopen("running.out","w",stdout);
tmp=0;int x,y;readi(n),readi(m);
for(int i=1;i<n;i++){
readi(x),readi(y);
addedge(x,y),addedge(y,x);
}
for(int i=1;i<=n;i++)readi(w[i]);
dfs1(1);dfs2(1,1);
for(int i=1;i<=m;i++){
readi(s[i]),readi(t[i]);
work(s[i],t[i]);
}
for(int i=1;i<=n;i++){
int ansx=qry(r1[dep[i]+w[i]],1,n,dfn[i]);
int ansy=qry(r2[w[i]-dep[i]+N],1,n,dfn[i]);
printf("%d ",ansx+ansy);
}
return 0;
}D1 T3
换教室：
对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。
在可以选择的课程中，有 2n 节课程安排在 n 个时间段上。在第 i（1≤i≤n）个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室ci上课，而另一节课程在教室di进行。
在不提交任何申请的情况下，学生们需要按时间段的顺序依次完成所有的n节安排好的课程。如果学生想更换第i节课程的教室，则需要提出申请。若申请通过，学生就可以在第i个时间段去教室di上课，否则仍然在教室ci上课。
由于更换教室的需求太多，申请不一定能获得通过。通过计算，牛牛发现申请更换第i节课程的教室时，申请被通过的概率是一个已知的实数ki ，并且对于不同课程的申请，被通过的概率是互相独立的。
学校规定，所有的申请只能在学期开始前一次性提交，并且每个人只能选择至多m节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室，而不能根据某些课程的申请结果来决定其他课程是否申请；牛牛可以申请自己最希望更换教室的m门课程，也可以不用完这m个申请的机会，甚至可以一门课程都不申请。
因为不同的课程可能会被安排在不同的教室进行，所以牛牛需要利用课间时间从一间教室赶到另一间教室。
牛牛所在的大学有v个教室，有e条道路。每条道路连接两间教室，并且是可以双向通行的。由于道路的长度和拥堵程度不同，通过不同的道路耗费的体力可能会有所不同。 当第i（1≤i≤n−1）节课结束后，牛牛就会从这节课的教室出发，选择一条耗费体力最少的路径前往下一节课的教室。
现在牛牛想知道，申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的期望值最小，请你帮他求出这个最小值。
Solution：
很明显的一道期望DP
我们dp[i][j][k]， 表示走到第i个教室，换了j次，这次换/不换的最优解
Floyd处理最短路即可
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=350;
double k[2500];
int n,m,v,e,c[2500],d[2500];
double dis[N][N];
int head[N],cnt;
double dp[2500][2500][3];
void floyd(){
for (int k=1;k<=v;k++)
for (int i=1;i<=v;i++)
for (int j=1;j<i;j++)
if (dis[i][j]>dis[i][k]+dis[k][j])
dis[j][i]=dis[i][j]=dis[i][k]+dis[k][j];
}
double minn(double a,double b){
if(a<b) return a;
return b;
}
double ans=9999999999.0;
int main(){
// freopen("A.in","r",stdin);
scanf("%d%d%d%d",&n,&m,&v,&e);
for(int i=1;i<=n;i++){
scanf("%d",&c[i]);
}
for(int i=1;i<=n;i++){
scanf("%d",&d[i]);
}
for(int i=1;i<=n;i++){
scanf("%lf",&k[i]);
}
for(int i=1;i<=v;i++)
for(int j=1;j<=v;j++){
if(i==j) continue;
dis[i][j]=999999999;
}
for(int i=1;i<=e;i++){
int p,q,w;
scanf("%d%d%d",&p,&q,&w);
dis[p][q]=dis[q][p]=minn(1.0*w,dis[p][q]);
}
floyd();
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
// if(i==1&&j==0) continue;
// if(i==1&&j==1) continue;
dp[i][j][0]=dp[i][j][1]=999999999.0;
}
}
dp[1][0][0]=0;
dp[1][1][1]=0;
for(int i=2;i<=n;i++){
for(int j=0;j<=min(i,m);j++){
dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][0]+1.0*dis[c[i]][c[i-1]]);
dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][1]+1.0*dis[d[i-1]][c[i]]*k[i-1] + 1.0*dis[c[i-1]][c[i]]*(1-k[i-1]) );
if(j!=0) {
dp[i][j][1]=min(dp[i][j][1], dp[i-1][j-1][0]+1.0*dis[c[i]][c[i-1]]*(1-k[i]) + 1.0*dis[c[i-1]][d[i]]*k[i]);
dp[i][j][1]=min(dp[i][j][1], dp[i-1][j-1][1] + 1.0*dis[c[i-1]][c[i]]*(1-k[i])*(1-k[i-1]) + 1.0*dis[c[i-1]][d[i]]*k[i]*(1-k[i-1]) + 1.0*dis[d[i-1]][c[i]]*(1-k[i])*k[i-1] + 1.0*dis[d[i-1]][d[i]]*k[i]*k[i-1] ) ;
}
}
}
for(int j=0;j<=m;j++){
ans=minn(ans,dp[n][j][0]);
ans=minn(ans,dp[n][j][1]);
}
printf("%.2lf",ans);
}D2 T1
组合数问题
Solution
我们考虑动态规划，设题意中的答案为dp[n][m],那么dp[n][m]又与谁有关呢？我们可以发现
dp[n][m]=dp[n-1][m]+dp[n][m-1]-dp[m-1][m-1] dp[n-1][m-1]用来去重。
换句话说，dp[n][m]=dp[n-1][m-1]+C(n,m-1)新增量+C（n-1,m）新增量。
另外，为了之后的调用，需在j=i结束循环后使 dp[i][i+1]=dp[i][i]。（这里不理解可以先看代码在进行体会）
代码参上：
#include <iostream>
#define maxn 2005
using namespace std;
int c[maxn][maxn];
int s[maxn][maxn];
int t,k,n,m;
int main(){
cin >> t >> k;
for (int i=1;i<maxn;i++){
c[i][0] = 1;
c[i][i] = 1;
for (int j=1;j<i;j++)
c[i][j] = (c[i-1][j] + c[i-1][j-1]) % k;
}
for (int i=1;i<maxn;i++)
for (int j=1;j<=i;j++){
s[i][j] = s[i][j-1];
if (c[i][j] == 0)
s[i][j]++;
}
for (int time=1;time<=t;time++){
cin >> n >> m;
int ans = 0;
for (int i=1;i<=n;i++){
int j = min(i,m);
ans += s[i][j];
}
cout << ans << endl;
}
return 0;
}D2 T2
蚯蚓
Solution:
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#define N 7000005
using namespace std;
bool cmp(const int &a,const int &b){
return a>b;
}
priority_queue<int>ans;
int cut1[N],now[N],cut2[N];
int n,m,q,u,v,t;
int sigma;
double p;
int h,h1,h2;
int t0,t1,t2;
int main(){
scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
p=(double)u/v;int tmp;
for(t0=1;t0<=n;++t0)
scanf("%d",&now[t0]);
--t0;t1=t2=0;h=h1=h2=1;
sort(now+1,now+t0+1,cmp);//对所有蚯蚓从大到小排序
int top;
for(int i=1;i<=m;++i){
if(h>t0){if(cut1[h1]>cut2[h2])top=cut1[h1++];else top=cut2[h2++];}
else if(now[h]>=cut1[h1]&&now[h]>=cut2[h2])top=now[h],++h;
else if(cut1[h1]>=cut2[h2]&&now[h]<=cut1[h1])top=cut1[h1],++h1;
else top=cut2[h2],++h2;
;;;//上述四行都是为了找到应该被切的蚯蚓,写的麻烦细节很多
top+=sigma;
int a1=floor(p*(double)top),a2=top-a1;
sigma+=q;
a1-=sigma,a2-=sigma;
cut1[++t1]=a1,cut2[++t2]=a2;
if(i%t==0)printf("%d ",top);
}
putchar('\n');
for(int i=h;i<=t0;++i)ans.push(now[i]);
for(int i=h1;i<=t1;++i)ans.push(cut1[i]);
for(int i=h2;i<=t2;++i)ans.push(cut2[i]);
for(int i=1;ans.size();++i){
if(i%t==0)printf("%d ",ans.top()+sigma);
ans.pop();
}
return 0;
}D2 T3
愤怒的小鸟
Solution:：
代码：
#include <bits/stdc++.h>
#define eps 1e-6
using namespace std;
int t, n, m, top;//top代表当前找到多少抛物线
int f[524300], st[400];//f的大小是一个略大于(1<<18)的数，注意数组大小不要开到2的整数次幂否则会慢 st[i]表示第i条抛物线能打的猪的状态
double x[20], y[20];//猪的坐标
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
int maxn = (1 << n) - 1;
memset(f, 0x3f, sizeof(f));
memset(st, 0, sizeof(st));
top = 0;
f[0] = 0;
for (int i = 1; i <= n; i++)
scanf("%lf%lf", &x[i], &y[i]);
//寻找所有抛物线
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
{
if (x[i] != x[j])
{
double ta = (y[i] - y[j] * x[i] / x[j]) / x[i] / (x[i] - x[j]);
double tb = (y[i] * x[j] * x[j] / x[i] / x[i] - y[j]) / (x[j] * x[j] / x[i] - x[j]);
if (ta < 0)
{
top++;
//枚举哪些猪能被抛物覅打掉
for(int k = 1; k <= n; k++)
if(fabs(ta * x[k] * x[k] + tb * x[k] - y[k]) <= eps)
st[top] |= (1 << (k - 1));
}
}
}
//从小到大枚举所有状态
for (int k = 0; k <= maxn; k++)
{
for (int i = 1; i <= top; i++)
f[k | st[i]] = min(f[k | st[i]], f[k] + 1);
for (int i = 1; i <= n; i++)
f[k | (1 << (i - 1))] = min(f[k | (1 << (i - 1))], f[k] + 1);
}
printf("%d\n", f[maxn]);
}
return 0;
}