NOIp 2016 Senior Solution

Posted On 2018年10月11日

Day 1

Solution

直接模拟即可

#include <cstdio>
#include <iostream>
#include <cstring>
typedef long long ll;
using namespace std;
inline int read()
{
	int f=1,k=0;char c=getchar();
	while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
	while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
	return k*f;
}
const int maxn=1e5+100;
struct mc{int typ;char s[23];}store[maxn];
signed main()
{
	int n=read(),m=read();
	for (int i=0;i<n;i++)
	{
		store[i].typ=read();
		scanf("%s",store[i].s);
	}
	int now=0;
	while (m--)
	{
		int p=store[now].typ^read(),k=read();
		if (!p)now=((now-k)%n+n)%n;
		else now=(now+k)%n;
	}
	puts(store[now].s);
}

#include <cstdio>

#include <iostream>

#include <cstring>

typedef long long ll;

using namespace std;

inline int read()

{

int f=1,k=0;char c=getchar();

while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();

while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();

return k*f;

}

const int maxn=1e5+100;

struct mc{int typ;char s[23];}store[maxn];

signed main()

{

int n=read(),m=read();

for (int i=0;i<n;i++)

{

store[i].typ=read();

scanf("%s",store[i].s);

}

int now=0;

while (m--)

{

int p=store[now].typ^read(),k=read();

if (!p)now=((now-k)%n+n)%n;

else now=(now+k)%n;

}

puts(store[now].s);

}

Solution

题目数据范围提供了起点/终点的特殊数据，~~显然是在提示我们~~考虑将每条路径拆分为两条至\(LCA\)的路径

令一个士兵出发点为\(s\)，终点为\(t\)，到达终点的时间为\(dis\)

考虑出发点对其祖先\(x\)的贡献：\(dep[x]+time[x]==dep[s]\)

考虑结束点对其祖先\(x\)的贡献：\(-dep[x]+time[x]==-dep[t]+dis\)

用DSU On Tree维护桶即可

注意在对于起点与终点分别在\(LCA/fa[LCA]\)打标记清除贡献

复杂度\(O(nlogn)\)

// luogu-judger-enable-o2
#include <cstdio>
#include <iostream>
#include <cstring>
#include <set>
#include <vector>
typedef long long ll;
using namespace std;
inline int read()
{
	int f=1,k=0;char c=getchar();
	while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
	while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
	return k*f;
}
const int maxn=299998+2;
int last[maxn],ti[maxn],pre[maxn];
struct ask{int typ,too,pre,lca;}store[maxn<<1];
struct reduce{int pos,typ,delta;};
inline bool operator <(const reduce&a,const reduce&b){return a.delta<b.delta;}
vector<reduce>red[maxn];
inline bool add_reduce(const int x,const int pos,const int typ,const int delta)
{
	red[x].push_back((reduce){pos,typ,delta});
	return 1;
}
struct mc{int too,nxt;}e[maxn<<1];
int fa[maxn],top[maxn],heavy[maxn],siz[maxn],dep[maxn];
template<typename T>inline void Swap(T&a,T&b){T tmp=a;a=b;b=tmp;}
int ans[maxn];
int skip,c[2][maxn<<2];
void dfs(const int cur)
{
	siz[cur]=1;
	for (int i=last[cur];i;i=e[i].nxt)
		if (e[i].too!=fa[cur])
			fa[e[i].too]=cur,dep[e[i].too]=dep[cur]+1,
			dfs(e[i].too),
			siz[cur]+=siz[e[i].too],siz[heavy[cur]]<siz[e[i].too]&&(heavy[cur]=e[i].too);
}
void _dfs(const int cur,const int ancestor)
{
	top[cur]=ancestor;
	if (heavy[cur])
		_dfs(heavy[cur],ancestor);
	for (int i=last[cur];i;i=e[i].nxt)
		if (e[i].too!=fa[cur]&&e[i].too!=heavy[cur])
			_dfs(e[i].too,e[i].too);
}
inline int LCA(int a,int b)
{
	while (top[a]!=top[b])
	{
		if (dep[top[a]]<dep[top[b]])Swap(a,b);
		a=fa[top[a]];
	}
	return dep[a]<dep[b]?a:b;
}
inline int get(const int a,const int x)
{
	int lca=store[x].lca;
	return dep[a]-dep[lca]+dep[store[x].too]-dep[lca];
}
void calc(const int cur,const int delta)
{
	for (int i=last[cur];i;i=e[i].nxt)
		if (e[i].too!=fa[cur]&&e[i].too!=skip)calc(e[i].too,delta);
	for (int i=pre[cur];i;i=store[i].pre)
	{
		if (!store[i].typ)c[0][dep[cur]]+=delta,add_reduce(store[i].lca,dep[cur],0,-delta);
		else c[1][get(cur,i)-dep[cur]+maxn]+=delta,add_reduce(fa[store[i].lca],get(cur,i)-dep[cur]+maxn,1,-delta);
	}
	for (int i=0;i<red[cur].size();i++)
		c[red[cur][i].typ][red[cur][i].pos]+=red[cur][i].delta;
	red[cur].clear();
}
void dsu(const int cur,const bool H)
{
	for (int i=last[cur];i;i=e[i].nxt)
		if (e[i].too!=fa[cur]&&e[i].too!=heavy[cur])dsu(e[i].too,0);
	if (heavy[cur])dsu(heavy[cur],1);
	skip=heavy[cur];
	calc(cur,1);
	skip=0;
	ans[cur]=c[0][dep[cur]+ti[cur]]+c[1][-dep[cur]+ti[cur]+maxn];
	if (!H)calc(cur,-1);
}
signed main()
{
	int n=read(),m=read();
	for (int i=1,a,b;i<n;i++)
		a=read(),b=read(),e[i<<1].too=b,e[i<<1].nxt=last[a],last[a]=i<<1,
		e[i<<1|1].too=a,e[i<<1|1].nxt=last[b],last[b]=i<<1|1;
	for (int i=1;i<=n;i++)ti[i]=read();
	dep[1]=1;
	dfs(1);
	_dfs(1,1);
	for (int i=1;i<=m;i++)
	{
		int a=read(),b=read(),lca=LCA(a,b);
		store[i<<1]=(ask){0,b,pre[a],lca};
		pre[a]=i<<1;
		store[i<<1|1]=(ask){1,a,pre[b],lca};
		pre[b]=i<<1|1;
	}
	dsu(1,1);
	for (int i=1;i<=n;i++)printf("%d ",ans[i]);
}

100

101

102

103

104

105

106

107

108

// luogu-judger-enable-o2

#include <cstdio>

#include <iostream>

#include <cstring>

#include <set>

#include <vector>

typedef long long ll;

using namespace std;

inline int read()

{

int f=1,k=0;char c=getchar();

while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();

while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();

return k*f;

}

const int maxn=299998+2;

int last[maxn],ti[maxn],pre[maxn];

struct ask{int typ,too,pre,lca;}store[maxn<<1];

struct reduce{int pos,typ,delta;};

inline bool operator <(const reduce&a,const reduce&b){return a.delta<b.delta;}

vector<reduce>red[maxn];

inline bool add_reduce(const int x,const int pos,const int typ,const int delta)

{

red[x].push_back((reduce){pos,typ,delta});

return 1;

}

struct mc{int too,nxt;}e[maxn<<1];

int fa[maxn],top[maxn],heavy[maxn],siz[maxn],dep[maxn];

template<typename T>inline void Swap(T&a,T&b){T tmp=a;a=b;b=tmp;}

int ans[maxn];

int skip,c[2][maxn<<2];

void dfs(const int cur)

{

siz[cur]=1;

for (int i=last[cur];i;i=e[i].nxt)

if (e[i].too!=fa[cur])

fa[e[i].too]=cur,dep[e[i].too]=dep[cur]+1,

dfs(e[i].too),

siz[cur]+=siz[e[i].too],siz[heavy[cur]]<siz[e[i].too]&&(heavy[cur]=e[i].too);

}

void _dfs(const int cur,const int ancestor)

{

top[cur]=ancestor;

if (heavy[cur])

_dfs(heavy[cur],ancestor);

for (int i=last[cur];i;i=e[i].nxt)

if (e[i].too!=fa[cur]&&e[i].too!=heavy[cur])

_dfs(e[i].too,e[i].too);

}

inline int LCA(int a,int b)

{

while (top[a]!=top[b])

{

if (dep[top[a]]<dep[top[b]])Swap(a,b);

a=fa[top[a]];

}

return dep[a]<dep[b]?a:b;

}

inline int get(const int a,const int x)

{

int lca=store[x].lca;

return dep[a]-dep[lca]+dep[store[x].too]-dep[lca];

}

void calc(const int cur,const int delta)

{

for (int i=last[cur];i;i=e[i].nxt)

if (e[i].too!=fa[cur]&&e[i].too!=skip)calc(e[i].too,delta);

for (int i=pre[cur];i;i=store[i].pre)

{

if (!store[i].typ)c[0][dep[cur]]+=delta,add_reduce(store[i].lca,dep[cur],0,-delta);

else c[1][get(cur,i)-dep[cur]+maxn]+=delta,add_reduce(fa[store[i].lca],get(cur,i)-dep[cur]+maxn,1,-delta);

}

for (int i=0;i<red[cur].size();i++)

c[red[cur][i].typ][red[cur][i].pos]+=red[cur][i].delta;

red[cur].clear();

}

void dsu(const int cur,const bool H)

{

for (int i=last[cur];i;i=e[i].nxt)

if (e[i].too!=fa[cur]&&e[i].too!=heavy[cur])dsu(e[i].too,0);

if (heavy[cur])dsu(heavy[cur],1);

skip=heavy[cur];

calc(cur,1);

skip=0;

ans[cur]=c[0][dep[cur]+ti[cur]]+c[1][-dep[cur]+ti[cur]+maxn];

if (!H)calc(cur,-1);

}

signed main()

{

int n=read(),m=read();

for (int i=1,a,b;i<n;i++)

a=read(),b=read(),e[i<<1].too=b,e[i<<1].nxt=last[a],last[a]=i<<1,

e[i<<1|1].too=a,e[i<<1|1].nxt=last[b],last[b]=i<<1|1;

for (int i=1;i<=n;i++)ti[i]=read();

dep[1]=1;

dfs(1);

_dfs(1,1);

for (int i=1;i<=m;i++)

{

int a=read(),b=read(),lca=LCA(a,b);

store[i<<1]=(ask){0,b,pre[a],lca};

pre[a]=i<<1;

store[i<<1|1]=(ask){1,a,pre[b],lca};

pre[b]=i<<1|1;

}

dsu(1,1);

for (int i=1;i<=n;i++)printf("%d ",ans[i]);

}

Solution

令\(f[i][j][1/0]\)表示第\(i\)天已用\(j\)次机会换/不换课的期望

直接转移即可

// luogu-judger-enable-o2
#include <cstdio>
#include <iostream>
#include <cstring>
#include <set>
#include <vector>
typedef long long ll;
using namespace std;
#define min MIN
inline int read()
{
	int f=1,k=0;char c=getchar();
	while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
	while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
	return k*f;
}
template<typename T>inline T min(const T&a,const T&b){return a<b?a:b;}
const int maxn=4007,inf=1e9;
int dist[maxn][maxn],pos[maxn][2];
double f[maxn][maxn][2],k[maxn];
signed main()
{
	memset(dist,63,sizeof(dist));
	int n=read(),m=read(),v=read(),e=read();
	for (int i=1;i<=n;i++)pos[i][0]=read();
	for (int i=1;i<=n;i++)pos[i][1]=read();
	for (int i=1;i<=n;i++)scanf("%lf",&k[i]);
	for (int i=1,a,b;i<=e;i++)
		a=read(),b=read(),dist[a][b]=dist[b][a]=min(dist[a][b],read());
	for (int i=1;i<=v;i++)dist[0][i]=dist[i][0]=dist[i][i]=0;
	for (int k=1;k<=v;k++)
		for (int i=1;i<=v;i++)
			for (int j=1;j<=v;j++)
				dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
	for (int i=0;i<=n;i++)
		for (int j=0;j<=m;j++)f[i][j][1]=f[i][j][0]=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]+dist[pos[i-1][0]][pos[i][0]];
		for (int j=1;j<=min(i,m);j++)
		{
			f[i][j][0]=min(f[i-1][j][1]+k[i-1]*dist[pos[i-1][1]][pos[i][0]]+(1-k[i-1])*dist[pos[i-1][0]][pos[i][0]],
						   f[i-1][j][0]+dist[pos[i-1][0]][pos[i][0]]),
			f[i][j][1]=
			min(f[i-1][j-1][1]+k[i-1]*k[i]*dist[pos[i-1][1]][pos[i][1]]+k[i-1]*(1.0-k[i])*dist[pos[i-1][1]][pos[i][0]]+(1-k[i-1])*k[i]*dist[pos[i-1][0]][pos[i][1]]+(1-k[i])*(1-k[i-1])*dist[pos[i-1][0]][pos[i][0]],
				f[i-1][j-1][0]+k[i]*dist[pos[i-1][0]][pos[i][1]]+(1.0-k[i])*(dist[pos[i-1][0]][pos[i][0]]));
		}
	}
	double ans=1e9;
	for (int i=0;i<=m;i++)ans=min(ans,min(f[n][i][0],f[n][i][1]));
	printf("%.2lf\n",ans);
}

// luogu-judger-enable-o2

#include <cstdio>

#include <iostream>

#include <cstring>

#include <set>

#include <vector>

typedef long long ll;

using namespace std;

#define min MIN

inline int read()

{

int f=1,k=0;char c=getchar();

while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();

while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();

return k*f;

}

template<typename T>inline T min(const T&a,const T&b){return a<b?a:b;}

const int maxn=4007,inf=1e9;

int dist[maxn][maxn],pos[maxn][2];

double f[maxn][maxn][2],k[maxn];

signed main()

{

memset(dist,63,sizeof(dist));

int n=read(),m=read(),v=read(),e=read();

for (int i=1;i<=n;i++)pos[i][0]=read();

for (int i=1;i<=n;i++)pos[i][1]=read();

for (int i=1;i<=n;i++)scanf("%lf",&k[i]);

for (int i=1,a,b;i<=e;i++)

a=read(),b=read(),dist[a][b]=dist[b][a]=min(dist[a][b],read());

for (int i=1;i<=v;i++)dist[0][i]=dist[i][0]=dist[i][i]=0;

for (int k=1;k<=v;k++)

for (int i=1;i<=v;i++)

for (int j=1;j<=v;j++)

dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);

for (int i=0;i<=n;i++)

for (int j=0;j<=m;j++)f[i][j][1]=f[i][j][0]=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]+dist[pos[i-1][0]][pos[i][0]];

for (int j=1;j<=min(i,m);j++)

{

f[i][j][0]=min(f[i-1][j][1]+k[i-1]*dist[pos[i-1][1]][pos[i][0]]+(1-k[i-1])*dist[pos[i-1][0]][pos[i][0]],

f[i-1][j][0]+dist[pos[i-1][0]][pos[i][0]]),

f[i][j][1]=

min(f[i-1][j-1][1]+k[i-1]*k[i]*dist[pos[i-1][1]][pos[i][1]]+k[i-1]*(1.0-k[i])*dist[pos[i-1][1]][pos[i][0]]+(1-k[i-1])*k[i]*dist[pos[i-1][0]][pos[i][1]]+(1-k[i])*(1-k[i-1])*dist[pos[i-1][0]][pos[i][0]],

f[i-1][j-1][0]+k[i]*dist[pos[i-1][0]][pos[i][1]]+(1.0-k[i])*(dist[pos[i-1][0]][pos[i][0]]));

}

double ans=1e9;

for (int i=0;i<=m;i++)ans=min(ans,min(f[n][i][0],f[n][i][1]));

printf("%.2lf\n",ans);

}

Day2

组合数问题

Solution

用组合数递推式取模，二维前缀和预处理即可

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<bitset>
#include<cstring>
#include<cstdlib>
#include<cmath>
typedef long long ll;
using namespace std;
inline int read()
{
    int f=1,k=0;char c=getchar();
    while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
    while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
const int maxn=2007,up=2000;
ll sum[maxn][maxn],c[maxn][maxn];
int n,k;
signed main()
{
    int q=read();k=read();
    for (int i=0;i<=up;i++)c[i][0]=1;c[1][1]=1;
    for (int i=2;i<=up;i++)
    {
        for (int j=1;j<=i;j++)
        {
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
            sum[i][j]=(c[i][j]==0)+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
        }
        sum[i][i+1]=sum[i][i];
    }
    for (int T=1;T<=q;T++)
    {
        int n=read(),m=read();
        printf("%lld\n",m>n?sum[n][n]:sum[n][m]);
    }
}

// luogu-judger-enable-o2

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<set>

#include<bitset>

#include<cstring>

#include<cstdlib>

#include<cmath>

typedef long long ll;

using namespace std;

inline int read()

{

int f=1,k=0;char c=getchar();

while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();

while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();

return k*f;

}

const int maxn=2007,up=2000;

ll sum[maxn][maxn],c[maxn][maxn];

int n,k;

signed main()

{

int q=read();k=read();

for (int i=0;i<=up;i++)c[i][0]=1;c[1][1]=1;

for (int i=2;i<=up;i++)

{

for (int j=1;j<=i;j++)

{

c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;

sum[i][j]=(c[i][j]==0)+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];

}

sum[i][i+1]=sum[i][i];

}

for (int T=1;T<=q;T++)

{

int n=read(),m=read();

printf("%lld\n",m>n?sum[n][n]:sum[n][m]);

}

蚯蚓

Solution

85%：直接用堆模拟

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<bitset>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<cmath>
typedef long long ll;
using namespace std;
inline int read()
{
    int f=1,k=0;char c=getchar();
    while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
    while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
priority_queue<int>Q;
signed main()
{
    int n=read(),m=read(),q=read(),u=read(),v=read(),t=read(),delta=0;
    double p=1.0*u/v;
    for (int i=1;i<=n;i++)Q.push(read());
    for (int i=1;i<=m;i++)
    {
        int tmp=Q.top()+delta;Q.pop();
        int a=tmp*p,b=tmp-a;
        if (i%t==0)printf("%d ",tmp);
        delta+=q;
        Q.push(a-delta);Q.push(b-delta);
    }
    puts("");
    int cnt=0;
    while (!Q.empty())++cnt,cnt%t==0&&(printf("%d ",Q.top()+delta)),Q.pop();puts("");
}

// luogu-judger-enable-o2

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<set>

#include<bitset>

#include<queue>

#include<cstring>

#include<cstdlib>

#include<cmath>

typedef long long ll;

using namespace std;

inline int read()

{

int f=1,k=0;char c=getchar();

while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();

while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();

return k*f;

}

priority_queue<int>Q;

signed main()

{

int n=read(),m=read(),q=read(),u=read(),v=read(),t=read(),delta=0;

double p=1.0*u/v;

for (int i=1;i<=n;i++)Q.push(read());

for (int i=1;i<=m;i++)

{

int tmp=Q.top()+delta;Q.pop();

int a=tmp*p,b=tmp-a;

if (i%t==0)printf("%d ",tmp);

delta+=q;

Q.push(a-delta);Q.push(b-delta);

}

puts("");

int cnt=0;

while (!Q.empty())++cnt,cnt%t==0&&(printf("%d ",Q.top()+delta)),Q.pop();puts("");

}

100%：显然先切的蚯蚓切完后一定仍比后切的切完大，再开两个单调队列维护切完后的两半蚯蚓即可

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<bitset>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<cmath>
typedef long long ll;
const int inf=2e9;
using namespace std;
inline int read()
{
    int k=0,f=1;char c=getchar();
    while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
    while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
const int maxn=2e5+100,maxm=2e7;
int ans[maxm+maxn];
struct mc{int Q[maxm];int front=1,rear;}Q[3];
inline bool cmp(const int&a,const int&b){return a>b;}
signed main()
{
    int n=read(),m=read(),delta=read(),u=read(),v=read(),t=read();
    double p=1.0*u/v;
    for (int i=1;i<=n;i++)Q[0].Q[i]=read();
    sort(Q[0].Q+1,Q[0].Q+1+n,cmp);
    Q[0].rear=n;
    for (int i=1;i<=m;i++)
    {
        int pos=0,mx=-inf;
        if (Q[0].front<=Q[0].rear)pos=0,mx=delta*(i-1)+Q[0].Q[Q[0].front];
        if (Q[1].front<=Q[1].rear&&mx<delta*(i-2)+Q[1].Q[Q[1].front])pos=1,mx=delta*(i-2)+Q[1].Q[Q[1].front];
        if (Q[2].front<=Q[2].rear&&mx<delta*(i-2)+Q[2].Q[Q[2].front])pos=2,mx=delta*(i-2)+Q[2].Q[Q[2].front];
        ++Q[pos].front;
        int DELTA=delta*(i-1);
        int a=mx*p,b=mx-a;
        if (i%t==0)printf("%d ",mx);
        Q[1].Q[++Q[1].rear]=a-DELTA;
        Q[2].Q[++Q[2].rear]=b-DELTA;
    }
    puts("");
    int tot=0;
    for (int i=Q[0].front;i<=Q[0].rear;i++)ans[++tot]=Q[0].Q[i]+m*delta;
    for (int i=Q[1].front;i<=Q[1].rear;i++)ans[++tot]=Q[1].Q[i]+(m-1)*delta;
    for (int i=Q[2].front;i<=Q[2].rear;i++)ans[++tot]=Q[2].Q[i]+(m-1)*delta;
    sort(ans+1,ans+1+tot,cmp);
    for (int i=1;i<=tot;i++)
        if (i%t==0)printf("%d ",ans[i]);
}

// luogu-judger-enable-o2

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<set>

#include<bitset>

#include<queue>

#include<cstring>

#include<cstdlib>

#include<cmath>

typedef long long ll;

const int inf=2e9;

using namespace std;

inline int read()

{

int k=0,f=1;char c=getchar();

while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();

while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();

return k*f;

}

const int maxn=2e5+100,maxm=2e7;

int ans[maxm+maxn];

struct mc{int Q[maxm];int front=1,rear;}Q[3];

inline bool cmp(const int&a,const int&b){return a>b;}

signed main()

{

int n=read(),m=read(),delta=read(),u=read(),v=read(),t=read();

double p=1.0*u/v;

for (int i=1;i<=n;i++)Q[0].Q[i]=read();

sort(Q[0].Q+1,Q[0].Q+1+n,cmp);

Q[0].rear=n;

for (int i=1;i<=m;i++)

{

int pos=0,mx=-inf;

if (Q[0].front<=Q[0].rear)pos=0,mx=delta*(i-1)+Q[0].Q[Q[0].front];

if (Q[1].front<=Q[1].rear&&mx<delta*(i-2)+Q[1].Q[Q[1].front])pos=1,mx=delta*(i-2)+Q[1].Q[Q[1].front];

if (Q[2].front<=Q[2].rear&&mx<delta*(i-2)+Q[2].Q[Q[2].front])pos=2,mx=delta*(i-2)+Q[2].Q[Q[2].front];

++Q[pos].front;

int DELTA=delta*(i-1);

int a=mx*p,b=mx-a;

if (i%t==0)printf("%d ",mx);

Q[1].Q[++Q[1].rear]=a-DELTA;

Q[2].Q[++Q[2].rear]=b-DELTA;

}

puts("");

int tot=0;

for (int i=Q[0].front;i<=Q[0].rear;i++)ans[++tot]=Q[0].Q[i]+m*delta;

for (int i=Q[1].front;i<=Q[1].rear;i++)ans[++tot]=Q[1].Q[i]+(m-1)*delta;

for (int i=Q[2].front;i<=Q[2].rear;i++)ans[++tot]=Q[2].Q[i]+(m-1)*delta;

sort(ans+1,ans+1+tot,cmp);

for (int i=1;i<=tot;i++)

if (i%t==0)printf("%d ",ans[i]);

}

愤怒的小鸟

Solution

预处理每两只小鸟组成的抛物线能打掉多少小鸟

再状压即可

注意抛物线\(a\)必须小于0

复杂度\(O(2^n*n^2)\)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<bitset>
#include<queue>
#include<cstring>
#include<cstdlib>
#include<cmath>
typedef long long ll;
using namespace std;
inline int read()
{
	int k=0,f=1;char c=getchar();
	while (c<'0'||c>'9') c=='-'&&(f=-1),c=getchar();
	while (c>='0'&&c<='9') k=k*10+c-'0',c=getchar();
	return k*f;
}
const int maxn=23;
const double eps=1e-6;
struct mc{double x,y;}store[maxn];
int f[1<<20],pre[maxn][maxn];
inline double sqr(const double x){return x*x;}
inline int min(const int a,const int b){return a<b?a:b;}
inline void work()
{
	int n=read(),m=read();
	memset(f,0x3f,sizeof(f));
	memset(pre,0,sizeof(pre));
	for (int i=1;i<=n;i++)scanf("%lf%lf",&store[i].x,&store[i].y);
	for (int i=0;i<n;i++)
		for (int j=i+1;j<n;j++)
			if (abs(store[i+1].x-store[j+1].x)>eps)
			{
				int ST=(1<<i)|(1<<j);
				double x1=store[i+1].x,y1=store[i+1].y,x2=store[j+1].x,y2=store[j+1].y,
				a=(y1*x2/x1-y2)/(x1*x2-x2*x2),b=(y1-a*x1*x1)/x1;
				if (a>0||abs(a)<eps)continue;
				for (int k=0;k<n;k++)
					if (abs(a*sqr(store[k+1].x)+b*store[k+1].x-store[k+1].y)<eps)ST|=(1<<k);
				pre[i][j]=ST;
			}
	f[0]=0;
	for (int st=0;st<(1<<n);st++)
	{
		for (int i=0;i<n;i++)f[st|(1<<i)]=min(f[st|(1<<i)],f[st]+1);
		for (int i=0;i<n;i++)
			for (int j=i+1;j<n;j++)
				f[st|pre[i][j]]=min(f[st|pre[i][j]],f[st]+1);
	}
	printf("%d\n",f[(1<<n)-1]);
}
signed main()
{
	for (int T=read();T;T--)work();
}

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<set>

#include<bitset>

#include<queue>

#include<cstring>

#include<cstdlib>

#include<cmath>

typedef long long ll;

using namespace std;

inline int read()

{

int k=0,f=1;char c=getchar();

while (c<'0'||c>'9') c=='-'&&(f=-1),c=getchar();

while (c>='0'&&c<='9') k=k*10+c-'0',c=getchar();

return k*f;

}

const int maxn=23;

const double eps=1e-6;

struct mc{double x,y;}store[maxn];

int f[1<<20],pre[maxn][maxn];

inline double sqr(const double x){return x*x;}

inline int min(const int a,const int b){return a<b?a:b;}

inline void work()

{

int n=read(),m=read();

memset(f,0x3f,sizeof(f));

memset(pre,0,sizeof(pre));

for (int i=1;i<=n;i++)scanf("%lf%lf",&store[i].x,&store[i].y);

for (int i=0;i<n;i++)

for (int j=i+1;j<n;j++)

if (abs(store[i+1].x-store[j+1].x)>eps)

{

int ST=(1<<i)|(1<<j);

double x1=store[i+1].x,y1=store[i+1].y,x2=store[j+1].x,y2=store[j+1].y,

a=(y1*x2/x1-y2)/(x1*x2-x2*x2),b=(y1-a*x1*x1)/x1;

if (a>0||abs(a)<eps)continue;

for (int k=0;k<n;k++)

if (abs(a*sqr(store[k+1].x)+b*store[k+1].x-store[k+1].y)<eps)ST|=(1<<k);

pre[i][j]=ST;

}

f[0]=0;

for (int st=0;st<(1<<n);st++)

{

for (int i=0;i<n;i++)f[st|(1<<i)]=min(f[st|(1<<i)],f[st]+1);

for (int i=0;i<n;i++)

for (int j=i+1;j<n;j++)

f[st|pre[i][j]]=min(f[st|pre[i][j]],f[st]+1);

}

printf("%d\n",f[(1<<n)-1]);

}

signed main()

{

for (int T=read();T;T--)work();

}

NOIp 2017 Senior Solution

0 0 vote

Article Rating

0 评论

Inline Feedbacks

View all comments

NOIp 2016 Senior Solution

Day 1

玩具谜题

Solution

天天爱跑步

Solution

换教室

Solution

Day2

组合数问题

Solution

蚯蚓

Solution

愤怒的小鸟

Solution

NOIp 2017 Senior Solution