NOIP2016总结

阅读原文时间：2023年07月15日阅读：1

Day1：

T1：模拟；

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define FILE "toy"
#define up(i,j,n) for(int i=(j);i<=(n);i++) #define pii pair
#define LL long long
namespace IO{
char buf[<<],*fs,*ft; int gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?-:*fs++;} int read(){ int ch=gc(),f=,x=; while(ch<''||ch>''){if(ch=='-')f=;ch=gc();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=gc();}
return f?-x:x;
}
}using namespace IO;
const int maxn=;
int n,m;
int a[maxn];
char s[maxn][];
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
scanf("%d%d",&n,&m);
up(i,,n-)scanf("%d %s",&a[i],s[i]);
int x,y,now=;
up(i,,m){
scanf("%d%d",&x,&y);
if(x==a[now])now=(now-y+n)%n;
else now=(now+y)%n;
}
printf("%s",s[now]);
return ;
}

T2:

这次noip2016最难的题？

考场上只急着打暴力了，没有好好思考；

实际上想了之后还是很简单的；

这题的关键是理清思路，题目上的特点是 若一条路径已走的时间若与当前节点的值相等，这一点的答案加1；

最暴力的思路当然是dfs Q遍，先判断这个点是否在这条路径上，然后判断已走的距离是不是等于当前点的权值，都符合的话ans++；

如何化简条件？

我们可以发现当若有一条从x->y的路径是一条链，且dep[x]<dep[y]，则若dep[i]-dep[x]=v[i]，则该点ans++；

这可以变形成dep[i]-v[i]=dep[x]，左边只与点i自身有关；

经过了这样的转化，我们发现可以这样做，将一个路径拆成从x->lca和lca->y两个链，然后可以仿照上面的方法，用dep与v[i]的关系做。

但做到了这一步仍然没什么卵用；

我们是否可以把目光转移，从看一条路径到看每个点？

对每个点而言，我们需要计算的是，它自身dep[i]±v[i]正好匹配经过它的路径所要求的的值的路径的数目；

这很绕，实际上对路径只有两个要求，第一个是经过它，第二个是路径与这个点可以匹配；

怎么维护？

第一个，维护只经过它的路径的值的集合；

第二个，在集合中快速找到符合要求的值的数目；

满足这两个要求，第一个可以用离线的方法维护，第二个可以在dfs的途中顺便维护一个桶，这个桶里存的就是经过它的路径的值的集合，然后可以O(1)查询；

这里面还有一个地方需要注意，每次桶从一颗子树出来的时候会带着这颗子树的信息，再进入另一个桶的时候会出现问题，解决方案是作差，先记录一下当前的ans值，待遍历完所有子树，再记录一下当前的ans，两个的差值即为所求；

在大佬眼里就是道水题…

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define FILE "dealing"
#define up(i,j,n) for(int i=(j);i<=(n);i++) #define pii pair
#define LL long long
namespace IO{
char buf[<<],*fs,*ft; int gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?-:*fs++;} int read(){ int ch=gc(),f=,x=; while(ch<''||ch>''){if(ch=='-')f=;ch=gc();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=gc();}
return f?-x:x;
}
}using namespace IO;
const int maxn=;
int n,m;
struct node{
int y,next,v;
}e[maxn],u[maxn],v[maxn],q[maxn];
int headu[maxn],headv[maxn],headq[maxn],lenu,lenv,lenq;
int linkk[maxn],len=;
int s[maxn],t[maxn],w[maxn];
inline void insert(int x,int y,node* e,int* linkk,int& len,int v){e[++len].y=y;e[len].v=v;e[len].next=linkk[x];linkk[x]=len;}
int top[maxn],siz[maxn],son[maxn],fa[maxn],dep[maxn],Lca[maxn],dfs_clock=;
int f[maxn],flag[maxn];
int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}
int pre[maxn],low[maxn],id[maxn];
void tarjan(int x){
siz[x]=;
pre[x]=++dfs_clock;
id[dfs_clock]=x;
flag[x]=;
for(int i=linkk[x];i;i=e[i].next){
if(e[i].y==fa[x])continue;
fa[e[i].y]=x;
dep[e[i].y]=dep[x]+;
tarjan(e[i].y);
}
for(int i=headq[x];i;i=q[i].next){
if(Lca[q[i].v])continue;
if(flag[q[i].y]==)Lca[q[i].v]=q[i].y;
else if(flag[q[i].y]==)Lca[q[i].v]=getf(q[i].y);
}
f[x]=fa[x];
flag[x]=;
low[x]=++dfs_clock;
id[dfs_clock]=x;
}
void init(){
n=read(),m=read();
int x,y;
up(i,,n-){x=read(),y=read();insert(x,y,e,linkk,len,);insert(y,x,e,linkk,len,);}
up(i,,n)w[i]=read();
up(i,,m){
s[i]=read(),t[i]=read();
insert(s[i],t[i],q,headq,lenq,i);
insert(t[i],s[i],q,headq,lenq,i);
}
up(i,,n)f[i]=i;
tarjan();
}
inline void make_tag(int s,int t,int st,bool flag){
if(flag){
insert(s,st,u,headu,lenu,);
insert(t,st,u,headu,lenu,-);
}
else {
insert(s,st,v,headv,lenv,);
insert(t,st,v,headv,lenv,-);
}
}
int ans[maxn];
int cnt1[maxn<<],cnt2[maxn<<];
int l[maxn];
void slove(){
up(i,,m){
if(Lca[i]==s[i])make_tag(fa[s[i]],t[i],dep[s[i]],);
else if(Lca[i]==t[i])make_tag(s[i],fa[t[i]],dep[s[i]],);
else {
make_tag(s[i],fa[Lca[i]],dep[s[i]],);
make_tag(Lca[i],t[i],*dep[Lca[i]]-dep[s[i]],);
}
}
memset(flag,,sizeof(flag));
int x;
for(int i=;i<=dfs_clock;i++){
x=id[i];
if(flag[x]){
for(int i=headu[x];i;i=u[i].next){
if(u[i].v==-)cnt1[u[i].y+maxn]--;
else cnt1[u[i].y+maxn]++;
}
for(int i=headv[x];i;i=v[i].next){
if(v[i].v==)cnt2[v[i].y+maxn]--;
else cnt2[v[i].y+maxn]++;
}
ans[x]=cnt1[dep[x]+w[x]+maxn]+cnt2[dep[x]-w[x]+maxn]-l[x];
}
else {
l[x]=cnt1[dep[x]+w[x]+maxn]+cnt2[dep[x]-w[x]+maxn];
flag[x]=;
}
}
up(i,,n)printf("%d%c",ans[i],i==n?'\n':' ');
}
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
init();
slove();
return ;
}

顺便进行了一下求lca的速度测试：

只求LCA的话，树链剖分最快，tarjan次之，倍增最慢（经常被卡）；

还需要一些附加信息的话，tarjan无法处理，树链剖分效率很好，倍增效率太低；

代码长度上，树链剖分最长，lca次之，tarjan最短；

如果考场上只求lca的话，建议tarjan，很好写；

T3：

无力吐槽，这题让一心一意备考noip的人怎么受得了；

概率dp；

把概率扒下来其实就是一背包动规；

具体的还是自己去体会(看代码)……

Day2:

T1:

组合数，考场脑子一抽写了二维树状数组，但实际也没什么问题（实际这题的二维动规是有一定的风险的，有人因此挂了）；

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define FILE "problem"
#define up(i,j,n) for(int i=(j);i<=(n);i++) #define pii pair
#define LL long long
namespace IO{
char buf[<<],*fs,*ft; int gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?-:*fs++;} int read(){ int ch=gc(),f=,x=; while(ch<''||ch>''){if(ch=='-')f=;ch=gc();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=gc();} return f?-x:x; } }using namespace IO; const int maxn=,N=; int c[maxn][maxn]; int sum[maxn][maxn]; int T,k,n,m; int main(){ //freopen(FILE".in","r",stdin); //freopen(FILE".out","w",stdout); T=read(),k=read(); c[][]=; up(i,,N){ c[i][]=; up(j,,i){ c[i][j]=(c[i-][j-]+c[i-][j])%k; sum[i][j]=sum[i-][j]+sum[i][j-]-sum[i-][j-]+(c[i][j]==?:); } up(j,i+,N)sum[i][j]=sum[i-][j]+sum[i][j-]-sum[i-][j-]; } while(T--){ n=read(),m=read(); if(m>n)m=n;
printf("%d\n",sum[n][m]);
}
return ;
}

T2:

数学题目，需要证一下单调性（求个导如何？）

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define FILE "earthworm"
#define up(i,j,n) for(int i=(j);i<=(n);i++) #define pii pair
#define LL long long
namespace IO{
char buf[<<],*fs,*ft; int gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?-:*fs++;} int read(){ int ch=gc(),f=,x=; while(ch<''||ch>''){if(ch=='-')f=;ch=gc();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=gc();} return f?-x:x; } }using namespace IO; const int maxn=; const double E=0.0000001; int a[maxn],b[maxn],c[maxn]; int ha,hb,hc,tb=,tc=; int n,m,u,v,t,q,d; LL pop(){ int L; if(ha&&(a[ha]>=b[tb]||tb>hb)&&(a[ha]>=c[tc]||tc>hc))L=a[ha],ha--;
else if(tb<=hb&&(b[tb]>=a[ha]||!ha)&&(b[tb]>=c[tc]||tc>hc))L=b[tb],tb++;
else L=c[tc],tc++;
return L;
}
int main(){
n=read(),m=read(),q=read(),u=read(),v=read(),t=read();
up(i,,n)a[i]=read();
sort(a+,a+n+);
ha=n;
LL L,top=;
up(i,,m){
L=pop()+d;
d+=q;
if(top*t==i){printf("%lld ",L);top++;}
b[++hb]=(int)(L*u/v)-d;
c[++hc]=L-b[hb]-*d;
}
cout<<endl;
top=;
up(i,,m+n){
L=pop();
if(t*top==i){printf("%lld ",L+d);top++;}
}
return ;
}

T3：

惭愧惭愧，考场不假思索，先打暴力……

后改记忆化，本质上都是状压dp；

吐槽的是，我同学写正解都被卡了一个n，而我写dfs，没有被卡掉……

实质上dfs会避免访问很多不可能出现的状态，所以效率比较高；

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define FILE "angrybirds"
#define up(i,j,n) for(int i=(j);i<=(n);i++) #define pii pair
#define LL long long
#define pdd pair
namespace IO{
char buf[<<],*fs,*ft; int gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,,<<,stdin),fs==ft))?-:*fs++;} int read(){ int ch=gc(),f=,x=; while(ch<''||ch>''){if(ch=='-')f=;ch=gc();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=gc();} return f?-x:x; } }using namespace IO; inline bool chkmin(int &a,int b){return a>b?a=b,true:false;}
inline bool chkmax(int &a,int b){return a=)return make_pair(,);
dui.second=(w*e-dui.first*q*q*e)/(q*e);
return dui;
}
int f[];
int dfs(int top,int vis){
if(f[vis]!=-)return f[vis];
if(top==n+)return f[vis]=;
if((<<top-)&vis)return f[vis]=dfs(top+,vis);
pdd p;
f[vis]=n;
int q=vis;
up(i,top+,n){
vis=q;
if(!((<<i-)&vis)){
p=slove(x[top],y[top],x[i],y[i]);
if(!p.first)continue;
vis=vis^(<<top-);
vis=vis^(<<i-);
up(j,top+,n){
if(vis&(<<j-))continue;
if(c(p.first*x[j]*x[j]+p.second*x[j],y[j]))vis=vis^(<<j-);
}
chkmin(f[q],dfs(top+,vis)+);
}
}
vis=q;
chkmin(f[vis],dfs(top+,vis^(<<top-))+);
return f[vis];
}
int main(){
//freopen(FILE".in","r",stdin);
//freopen(FILE".out","w",stdout);
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
up(i,,n)scanf("%lf%lf",&x[i],&y[i]);
if(!m||m==)ans=n;
if(m==)ans=(n%)?(n/+):(n/+);
memset(f,-,sizeof(f));
cout<<dfs(,)<<endl;
}
return ;
}

手机扫一扫

移动阅读更方便

你可能感兴趣的文章

2015长春 HDU 5534 Partial Tree

Codeforces Round #470 (rated, Div. 2, based on VK Cup 2018 Round 1) C.Producing Snow

洛谷P3235 [HNOI2014]江南乐(Multi-SG)

HDU 6203 2017沈阳网络赛 LCA，DFS+树状数组

【bzoj3576】 Hnoi2014—江南乐

BZOJ 3576: [Hnoi2014]江南乐 (SG函数)