NOIP2016

发表于 | 分类于 | 阅读次数:
天天爱跑步,换教室,蚯蚓,愤怒的小鸟,组合数问题

天天爱跑步

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/**************************************************************
    Problem: 4719
    User: zhangche0526
    Language: C++
    Result: Accepted
    Time:9936 ms
    Memory:52772 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
 
const int MAXN=3e5+5;
 
int N,M;
 
struct E{int next,to;} e[MAXN<<1];int ecnt,G[MAXN];
void addEdge(int u,int v){e[++ecnt]=(E){G[u],v};G[u]=ecnt;}
void addEdge2(int u,int v){addEdge(u,v);addEdge(v,u);}
 
struct C{int s,t,lca,len;} chn[MAXN];
 
int w[MAXN],dpt[MAXN];
 
int fa[MAXN];
inline void initUFS(){for(int i=1;i<=N;i++) fa[i]=i;}
int findAnc(int x){return fa[x]==x?x:fa[x]=findAnc(fa[x]);}
 
struct A{int next,to,id;} lcaAsk[MAXN<<1];int acnt,hd[MAXN];
void addAsk(int u,int v,int id){lcaAsk[++acnt]=(A){hd[u],v,id};hd[u]=acnt;}
void addAsk2(int u,int v,int id){addAsk(u,v,id);addAsk(v,u,id);}
 
bool vis[MAXN];
void dfsPre(int u)
{
    int i;
    vis[u]=true;
    for(i=G[u];i;i=e[i].next)
    {
        int v=e[i].to;if(vis[v]) continue;
        dpt[v]=dpt[u]+1;dfsPre(v);fa[v]=u;
    }
    for(i=hd[u];i;i=lcaAsk[i].next) if(vis[lcaAsk[i].to])
            chn[lcaAsk[i].id].lca=findAnc(lcaAsk[i].to);
}

int chnCnt[MAXN],Cnt[MAXN*3];
std::vector<int> vec1[MAXN],vec2[MAXN];

int ans[MAXN];

void dfsU(int u,int la)
{
    int i,k=w[u]+dpt[u];int tmp=Cnt[k];
    for(i=G[u];i;i=e[i].next)
    {
        int v=e[i].to;if(v==la) continue;
        dfsU(v,u);
    }
    Cnt[dpt[u]]+=chnCnt[u];
    ans[u]=Cnt[k]-tmp;
    for(i=0;i<vec1[u].size();i++) Cnt[vec1[u][i]]--;
}
 
void dfsD(int u,int la)
{
    int i,k=dpt[u]-w[u];int tmp=Cnt[MAXN+k];
    for(i=G[u];i;i=e[i].next)
    {
        int v=e[i].to;if(v==la) continue;
        dfsD(v,u);
    }
    for(i=0;i<vec1[u].size();i++) Cnt[MAXN+vec1[u][i]]++;
    ans[u]+=Cnt[MAXN+k]-tmp;
    for(i=0;i<vec2[u].size();i++) Cnt[MAXN+vec2[u][i]]--;
}

int main()
{
    int i;
    scanf("%d%d",&N,&M);
    for(i=1;i<N;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        addEdge2(u,v);
    }
    for(i=1;i<=N;i++) scanf("%d",w+i);
    for(i=1;i<=M;i++)
    {
        scanf("%d%d",&chn[i].s,&chn[i].t);
        addAsk2(chn[i].s,chn[i].t,i);
    }
    initUFS();dpt[1]=1;dfsPre(1);
    for(i=1;i<=M;i++) chn[i].len=dpt[chn[i].s]+dpt[chn[i].t]-2*dpt[chn[i].lca];
     
    for(i=1;i<=M;i++) chnCnt[chn[i].s]++;
    for(i=1;i<=M;i++) vec1[chn[i].lca].push_back(dpt[chn[i].s]);
    dfsU(1,0);
 
    memset(Cnt,0,sizeof(Cnt));
    for(i=1;i<=N;i++) vec1[i].clear();
    for(i=1;i<=M;i++) 
        vec1[chn[i].t].push_back(dpt[chn[i].t]-chn[i].len),
        vec2[chn[i].lca].push_back(dpt[chn[i].t]-chn[i].len);
    dfsD(1,0);
 
    for(i=1;i<=M;i++) 
        if(dpt[chn[i].s]-dpt[chn[i].lca]==w[chn[i].lca])
            ans[chn[i].lca]--;
    for(i=1;i<N;i++) printf("%d ",ans[i]);printf("%d",ans[N]);
    return 0;
}

换教室

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**************************************************************
    Problem: 4720
    User: zhangche0526
    Language: C++
    Result: Accepted
    Time:2096 ms
    Memory:64496 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<cstring>
 
const int MAXN=2e3+5,MAXM=2e3+5,MAXV=305,MAXE=9e4+5,INF=1e9;
 
int N,M,V,E;
int C[MAXN],D[MAXN];double K[MAXN];
 
int dis[MAXV][MAXV];
inline void floyd()
{
    int i,j,k;
    for(k=1;k<=V;k++)
        for(i=1;i<=V;i++)
            for(j=1;j<=V;j++)
                if(dis[i][k]+dis[k][j]<dis[i][j])
                    dis[i][j]=dis[i][k]+dis[k][j];
}
 
double f[MAXN][MAXM][2];
inline void calc()
{
    int i,j;
    for(i=2;i<=N;i++)
        for(j=0;j<=std::min(i,M);j++)
        {
            f[i][j][0]=std::min(f[i-1][j][0]+dis[C[i-1]][C[i]],
                                f[i-1][j][1]+dis[D[i-1]][C[i]]*K[i-1]+dis[C[i-1]][C[i]]*(1.0-K[i-1]));
            if(j) f[i][j][1]=std::min(f[i-1][j-1][0]+dis[C[i-1]][D[i]]*K[i]+dis[C[i-1]][C[i]]*(1.0-K[i]), 
                                      f[i-1][j-1][1]+dis[D[i-1]][D[i]]*K[i-1]*K[i]+dis[D[i-1]][C[i]]*K[i-1]*(1.0-K[i])+
                                                     dis[C[i-1]][D[i]]*(1.0-K[i-1])*K[i]+dis[C[i-1]][C[i]]*(1.0-K[i-1])*(1.0-K[i]));
        }
}
 
int main()
{
    int i,j;
    scanf("%d%d%d%d",&N,&M,&V,&E);  
    for(i=1;i<=N;i++) scanf("%d",C+i);
    for(i=1;i<=N;i++) scanf("%d",D+i);
    for(i=1;i<=N;i++) scanf("%lf",K+i);
    for(i=1;i<=V;i++) for(j=1;j<=V;j++)
            if(i!=j) dis[i][j]=INF;
    for(i=1;i<=E;i++)
    {
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        if(w<dis[u][v]) dis[u][v]=dis[v][u]=w;
    }
    floyd();
    for(i=1;i<=N;i++) for(j=0;j<=M;j++)
        f[i][j][0]=f[i][j][1]=INF;
    f[1][0][0]=f[1][1][1]=0;
    calc();
    double ans=INF;
    for(i=0;i<=M;i++) ans=std::min(ans,std::min(f[N][i][0],f[N][i][1]));
    printf("%.2f\n",ans);
    return 0;
}

蚯蚓

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
typedef long long ll;
const int MAXN=1e5+5,INF=1e9;
int n,m,q,u,v,t,a[MAXN];
std::queue<int> que[3];
int main()
{
	int i,j;
	scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
	for(i=1;i<=n;i++) scanf("%d",a+i);
	std::sort(a+1,a+n+1);
	for(i=n;i;i--) que[0].push(a[i]);
	int tag=0,rk=0;
	for(i=1;i<=m;i++)
	{
		int maxv=-INF,fr;
		for(j=0;j<3;j++) if(!que[j].empty()) 
			if(que[j].front()>maxv) maxv=que[j].front(),fr=j;
		que[fr].pop();
		maxv+=tag;rk++;if(rk%t==0) printf("%d ",maxv);
		int new1=(ll)maxv*u/v,new2=maxv-new1;
		tag+=q;new1-=tag,new2-=tag;
		que[1].push(new1);que[2].push(new2);
	}
	putchar('\n');rk=0;
	int tmp=que[0].size()+que[1].size()+que[2].size();
	for(i=1;i<=n+m;i++)
	{
		int maxv=-INF,fr;
		for(j=0;j<3;j++) if(!que[j].empty()) 
			if(que[j].front()>maxv) maxv=que[j].front(),fr=j;
		que[fr].pop();
		maxv+=tag;rk++;if(rk%t==0) printf("%d ",maxv);
	}
	putchar('\n');
	return 0;
}

愤怒的小鸟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

const int MAXN=20;

int n,m;
double X[MAXN],Y[MAXN];
int f[1<<20],g[MAXN][MAXN];

bool equ(double x,double y){return std::fabs(x-y)<1e-6;}

int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		int i,j,t; 
		scanf("%d%d",&n,&m);
		for(i=1;i<=n;i++) scanf("%lf%lf",X+i,Y+i);
		memset(g,0,sizeof(g));
		for(i=1;i<=n;i++)
			for(j=i+1;j<=n;j++)
			{
				if(equ(X[i],X[j])) continue;
				double a=(Y[j]/X[j]-Y[i]/X[i])/(X[j]-X[i]);
				if(a>=0) continue;
				double b=Y[i]/X[i]-a*X[i];
				for(t=1;t<=n;t++) if(equ(a*X[t]+b,Y[t]/X[t]))
					g[i][j]|=(1<<t-1);
			}
		memset(f,127,sizeof(f));f[0]=0;
		for(i=0;i<(1<<n);i++)
			for(j=1;j<=n;j++)
			{
				if(i&(1<<j-1)) continue;
				for(t=j+1;t<=n;t++) f[i|g[j][t]]=std::min(f[i|g[j][t]],f[i]+1);
				f[i|(1<<j-1)]=std::min(f[i|(1<<j-1)],f[i]+1);
			}
		printf("%d\n",f[(1<<n)-1]);
	}
	return 0;
}

##组合数问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<cstdio>

const int MAXN=2e3;

int K;
int C[MAXN+5][MAXN+5],sum[MAXN+5][MAXN+5];
inline void preTab()
{
    int i,j;C[0][0]=1;
    for(i=1;i<=MAXN;i++)
    {
        C[i][0]=1;
        int isum=0;
        for(j=1;j<i;j++)
        {
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%K;
            if(!C[i][j]) isum++;
            sum[i][j]=sum[i-1][j]+isum;
        }
        C[i][i]=1,sum[i][i]=sum[i-1][j-1]+isum;
    }
}

int main()
{
    int T;scanf("%d%d",&T,&K);
    preTab();
    while(T--)
    {
        int n,m;scanf("%d%d",&n,&m);
        if(n<m) m=n;
        printf("%d\n",sum[n][m]);
    }
}