2018.10.31 练习赛

T1 【NOIP2018模拟】草地排水

题解：

\(O(N^2)\)的暴力非常好拿,一种方便的方法是直接按要求连边然后\(SPFA\)飞快;

正解考虑动态规划:设状态为\(F[R]\),右端点为R的最大权值,转移为\(F[R]=max{F[close(L)]+W[i]}\),按右端点排序后直接二分出\(L\)的位置,同时可以用线段树维护前驱;

\(code\):

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#define reint register int 
#define ll long long 
#define ld double 
#define l(x) (x<<1) 
#define r(x) (x<<1|1) 
#define rell register ll 
using namespace std; 

char buf[1<<20],*p1,*p2; 
inline char gc() 
{ 
//    return getchar(); 
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++; 
} 

template 
inline void read(T &x) 
{ 
    char tt; 
    bool flag=0; 
    while(!isdigit(tt=gc())&&tt!='-'); 
    tt=='-'?(flag=1,x=0):(x=tt-'0'); 
    while(isdigit(tt=gc())) x=(x<<1)+(x<<3)+(tt^'0'); 
    if(flag) x=-x; 
} 

const int maxn=1e5+2;
struct point{
	int x,y;
	ll len;
	inline point(int a=0,int b=0,int c=0)
	{x=a,y=b,len=c;}
	inline bool operator<(point a)const
	{return y>1;
        	if(a[mid].y

【NOIP2018模拟】化学

题解：

\(meet-in-the-middle\)搜索将指数折半时间复杂度\(O(2^{\frac{N}{2}}logN)\)；

\(code:\)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#define reint register int 
#define ll long long 
#define ld double 
#define l(x) (x<<1) 
#define r(x) (x<<1|1) 
#define rell register ll 
using namespace std; 

char buf[1<<20],*p1,*p2; 
inline char gc() 
{ 
//    return getchar(); 
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++; 
} 

template 
inline void read(T &x) 
{ 
    char tt; 
    bool flag=0; 
    while(!isdigit(tt=gc())&&tt!='-'); 
    tt=='-'?(flag=1,x=0):(x=tt-'0'); 
    while(isdigit(tt=gc())) x=(x<<1)+(x<<3)+(tt^'0'); 
    if(flag) x=-x; 
} 

const int maxn=42;
int n;
ll m,a[maxn];
int lowbit(int x){return x&-x;}
ll f[1<<20];
int cnt[1<<20];
void solve1()
{
	for(int i=1;i<=n;i++) read(a[i]),cnt[1<=a[i];j--)
	g[j]=g[j]+g[j-a[i]];
	for(int i=0;i<=m;i++)ans+=g[i];
	printf("%lld",ans);
}

ll sum,ans,mid;
ll mx[1<<21],tot;

void dfs1(int x)
{
	if(x==mid+1)
	{
		mx[++tot]=sum;
		return;
	}
	dfs1(x+1);
	if(sum+a[x]<=m)
	{
		sum+=a[x];
		dfs1(x+1);
		sum-=a[x];
	}
}

void dfs2(int x)
{
	if(x==n+1)
	{
		ans+=upper_bound(mx+1,mx+1+tot,m-sum)-mx-1;
		return;
	}
	dfs2(x+1);
	if(sum+a[x]<=m)
	{
		sum+=a[x];
		dfs2(x+1);
		sum-=a[x];
	}
}

void solve()
{
	for(int i=1;i<=n;i++) read(a[i]);
	mid=n>>1;
	dfs1(1);
	sort(mx+1,mx+1+tot);
	dfs2(mid+1);
	printf("%lld",ans);
}

int main()
{
	read(n),read(m);
	if(n<=20) solve1();
	else if(m<=1000) solve2();
	else solve();
}

T3 【NOIP2018模拟】读书

题解：

贪心,尽量限制对手的走法,统计\(2-(N-1)\)到\(1\)号\(N\)号点的距离,哪边近哪边先手;

\(code:\)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#define reint register int 
#define ll long long 
#define ld double 
#define l(x) (x<<1) 
#define r(x) (x<<1|1)
#define rell register ll 
using namespace std; 

char buf[1<<20],*p1,*p2; 
inline char gc() 
{ 
//    return getchar(); 
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++; 
} 

template 
inline void read(T &x) 
{ 
    char tt; 
    bool flag=0; 
    while(!isdigit(tt=gc())&&tt!='-'); 
    tt=='-'?(flag=1,x=0):(x=tt-'0'); 
    while(isdigit(tt=gc())) x=(x<<1)+(x<<3)+(tt^'0'); 
    if(flag) x=-x; 
} 

const int maxn=1e5+2;
int n,t,fa[maxn][20],log_[maxn],dep[maxn];
vectorG[maxn];

void dfs(int x,int pre)
{
	fa[x][0]=pre;dep[x]=dep[pre]+1;
	for(int i=1;i<=log_[n];i++)
	if(fa[x][i-1]) fa[x][i]=fa[fa[x][i-1]][i-1];
	else break;
	for(auto it:G[x])
	{
		if(it==pre) continue;
		dfs(it,x);
	}
}

int getlca(int x,int y)
{
	if(x==y) return x;
	if(dep[x]=0;i--)
	if(del>>i&1) x=fa[x][i];
	if(x==y) return x;
	for(int i=log_[n];i>=0;i--)
	if(fa[x][i]!=fa[y][i])
	x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}

int cal(int x,int y)
{return dep[x]+dep[y]-(dep[getlca(x,y)]<<1);}

int main()
{
	read(t);
	log_[0]=-1;
	for(int i=1;i<=maxn-1;i++) log_[i]=log_[i>>1]+1;
	while(t--)
	{
		read(n);
		memset(dep,0,sizeof(dep));
		memset(fa,0,sizeof(fa));
		for(int i=1;i<=n;i++) G[i].clear();
		for(int i=1;ians1) puts("^_^");
		else puts("T_T");
	}
}
比赛杂项题解练习赛DP线段树二分搜索贪心

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

Ubuntu 断网问题解决

DP决策优化小结

dp专题练习

牛客练习赛91（并查集+二维偏序+二分）

[SQL] SQL Server 2019 中LocalDB 报错的问题解决

题解 Count on a tree II/【模板】树分块

力扣530题（二叉搜索树的最小绝对差）

腾讯云搭建个人博客wordpress

HttpURLConnection发送中文乱码问题解决

dp多维状态的优化

CS5265完全替代兼容龙迅LT8711|Type-C/DP1.2 to HDMI2.0方案芯片|CS5265兼容TYPEC手机

标签