\(noip模拟29\;solutions\)

这次考试给我最大的伤害，让我意识到了差距

这场考试可以说是非常的简单，就是简单到，看两眼，打个表就有结果了

但是呢？我考得非常的完蛋，只有30pts

据说上一届做这题随便切；

考完之后一看，这第一题第三题都有人切了，我就非常的伤心，但是把题都改过来之后

还是很开心，明天一定要好好考，今天的状态非常不好

明天提起精神A掉至少一道题！！！！

\(T1\; 最长不下降子序列\)

确实，乍一看这题还是挺简单的，我说着我树状数组打的非常的熟练，

就个这玩意不是小case？？我就开始敲，突然发现，这个数据范围好像炸掉了。。

一不做二不休，打完了觉得应该拿到30分，就交上去了

然而因为第一个数不符合规律我特判了一下，忘记统计它的答案了。。。。。。00000

第一题就这样无奈的爆零了。。。

其实正解就是一个小dp，也就是我前面的算法加了点其他的东西，

你会发现这个模数只有150，这样根据抽屉原理就可以得到，这个序列必然有循环节，且长度小于模数

（我考场上也意识到了这个模数不对劲，可惜就是没有找到规律，下次多想想）

我们发现当这个序列有了循环节，那我们就可以直接去统计每个循环节的贡献了

本题要求的是不下降子序列，所以每个循环节都至少有1的贡献，要是上升就不一定了

当这个序列出现了循环节，我们就可以将这个序列分为三部分，整块的循环节和前后散的

那我们就可以分别去统计贡献，注意这里前面散块的贡献不能只统计这一小块的

因为你不知道跨越了n个循环节之后还会出现什么，所以这个长度要弄成\(\mathcal{O(T^2)}\)

后面的直接统计就好了，你会发现这时候中间剩下的循环节就直接加1就行了

AC_code 

#include<bits/stdc++.h>

using namespace std;

#define re register int

#define ll long long

ll n,t,a,b,c,d;

ll zq,s[90005];

ll fro,beh,dp[90005];

ll ans,sum,beg;

ll pos[305];

struct SZSZ{

	ll tr[305];

	int lb(int x){return x&(-x);}

	void ins(int x,ll v){for(re i=x;i<=d+1;i+=lb(i))tr[i]=max(tr[i],v);}

	ll query(int x){ll ret=0;for(re i=x;i;i-=lb(i))ret=max(ret,tr[i]);return ret;}

	void clear(){memset(tr,0,sizeof(tr));}

}sz;

signed main(){

	scanf("%lld%lld%lld%lld%lld%lld",&n,&t,&a,&b,&c,&d);

	int now=1;s[1]=t;

	while(!pos[s[now]]){

		pos[s[now]]=now;now++;

		s[now]=(s[now-1]*s[now-1]*a+s[now-1]*b+c)%d;

		//cout<<s[now]<<" ";

	}

	//cout<<endl;

	zq=now-pos[s[now]];

	beg=now-zq-1;

	fro=min(now-zq-1+zq*zq,n);

	//cout<<n<<" "<<fro<<" "<<zq<<endl;

	for(re i=1;i<=fro;i++){

		if(!s[i])s[i]=(s[i-1]*s[i-1]*a+s[i-1]*b+c)%d;

		ll tmp=sz.query(s[i]+1)+1;

		sz.ins(s[i]+1,tmp);

		dp[i]=max(dp[i],tmp);

		ans=max(ans,tmp);

		//cout<<i<<endl;

		//cout<<s[i]<<" "<<ans<<endl;

	}

	for(re i=1;i<=zq;i++){

		dp[i+beg]=dp[i+beg+zq*(zq-1)];

	}

	//cout<<endl;

	//cout<<ans<<endl;

	if(fro==n){printf("%lld",ans);return 0;}

	sum=(n-fro)/zq;

	beh=n-fro-sum*zq;

	//cout<<sum<<" "<<beh<<endl;

	for(re i=1;i<=zq;i++){

		sz.clear();ll mx=0;

		for(re j=1;j<=beh;j++){

			if(s[i+beg]>s[j+beg])continue;

			ll tmp=sz.query(s[j+beg]+1)+1;

			sz.ins(s[j+beg]+1,tmp);

			mx=max(mx,tmp);

		}

		ans=max(ans,dp[i+beg]+mx+sum);

	}

	printf("%lld",ans);

}


\(T2\; 完全背包问题\)

这个的话，我也是直接打了个最最最普通的背包就溜走了

我其实根本就没看出来是个dp，考完沈队一讲，好像是有点明白，这个题的dp是这样的

设\(f[k][i][j]\)表示处理玩前k个物品，用了i个大物品，得到的总体积模上最小的体积为j的最小体积

就是说我们维护不了每一个值，但是我们可以让这个背包的体积模 \(V_0\) (就是所有物品体积中最小的那个)

其实也不需要最小的，任何一个小于L的都可以，因为我们找到最小的话，就可以无限曾加，得到背包的体积

那么转移就分为当前物品是大物品还是小物品就行了，dp好设计，

因为这个物品可以随便加，所以我们直接先把状态转移到当前层，然后层内转移

你发现这个如果是大物品的话，就可以直接循环转移，小物品的话，就有后效性了，

所以这个时候就直接跑最短路就好了，也就是同余最短路。。。

AC_code 

#include<bits/stdc++.h>

using namespace std;

#define re register int

#define ll long long

const ll N=55;

const ll M=1e5+5;

const ll K=1e4+5;

const ll inf=0x3f3f3f3f3f3f3f3f;

ll n,m,v[N],w[M],c,l;

ll f[N][40][K],mv=0,mn=inf;

ll s=20001;

struct DIJ{

	ll to[M*2],nxt[M*2],head[M],rp;

	ll val[M*2];

	bool vis[M];

	void clear(){

		memset(head,0,sizeof(head));rp=1;

		memset(vis,false,sizeof(vis));

	}

	void add_edg(ll x,ll y,ll z){

		to[++rp]=y;

		val[rp]=z;

		nxt[rp]=head[x];

		head[x]=rp;

	}

	struct node{

		ll di,id;

		node(){}

		node(ll x,ll y){

			di=x;id=y;

		}

		bool operator < (node x)const{

			return di>x.di;

		}

	};

	ll dis[M];

	priority_queue<node> q;

	void smw(){

		while(!q.empty())q.pop();

		q.push(node(0,s));dis[s]=0;

		while(!q.empty()){

			ll now=q.top().id;

			ll dit=q.top().di;q.pop();

			if(vis[now])continue;

			vis[now]=true;dis[now]=dit;

			for(re i=head[now];i;i=nxt[i]){

				ll y=to[i];

				if(vis[y])continue;

				q.push(node(dit+val[i],y));

			}

		}

	}

}dj;

signed main(){

	scanf("%lld%lld",&n,&m);

	for(re i=1;i<=n;i++){

		scanf("%lld",&v[i]);

		mn=min(mn,v[i]);

		mv=max(mv,v[i]);

	}

	scanf("%lld%lld",&l,&c);

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

	//if(f[0][0][0]>1e18)cout<<"sb"<<endl;

	f[0][0][0]=0;

	for(re k=1;k<=n;k++){

		if(v[k]>=l){

			for(re j=0;j<mn;j++)

				f[k][0][j]=f[k-1][0][j];

			for(re i=1;i<=c;i++)

				for(re j=0;j<mn;j++)

					f[k][i][j]=min(f[k-1][i][j],f[k][i-1][(1ll*j+mn*100-v[k]%mn)%mn]+v[k]);

		}

		else{

			for(re i=0;i<=c;i++){

				dj.clear();

				for(re j=0;j<mn;j++){

					dj.add_edg(s,j,f[k-1][i][j]);

					dj.add_edg(j,((1ll*j+v[k]%mn)%mn),v[k]);

				}

				dj.smw();

				for(re j=0;j<mn;j++)f[k][i][j]=dj.dis[j];

			}

		}

	}

	//cout<<0x3f3f3f3f<<endl;

	for(re i=1;i<=m;i++){

		scanf("%lld",&w[i]);

		bool flag=false;

		ll tmp=w[i]%mn;

		for(re j=0;j<=c;j++){

			if(w[i]>=f[n][j][tmp]){

				flag=true;break;

			}

			//cout<<f[n][j][w[i]%v[0]]<<endl;

		}

		//if(w[i]>=f[n][c][w[i]%v[0]])flag=true;

		if(flag)printf("Yes\n");

		else printf("No\n");

	}

}


\(T3\;最近公共祖先\)

这个题是考场上最水的一道题了

直接将每个点的答案转化成每个黑点的贡献，直接dfs序一下，然后更新过的就不要更新了

考完试10min就切掉了

AC_code 

#include<bits/stdc++.h>

using namespace std;

#define re register int

const int N=1e5+5;

int n,m,w[N];

int to[N*2],nxt[N*2],head[N],rp;

void add_edg(int x,int y){

	to[++rp]=y;

	nxt[rp]=head[x];

	head[x]=rp;

}

bool vis[N];

int fa[N],dep[N];

int siz[N],son[N],top[N];

int dfn[N],dfm[N],idf[N],cnt;

void dfs1(int x){

	siz[x]=1;son[x]=0;

	dfn[x]=++cnt;

	for(re i=head[x];i;i=nxt[i]){

		int y=to[i];

		if(y==fa[x])continue;

		fa[y]=x;dep[y]=dep[x]+1;

		dfs1(y);

	}

	dfm[x]=cnt;

}

struct XDS{

	#define ls x<<1

	#define rs x<<1|1

	int tr[N*4],laz[N*4];

	void build(int x,int l,int r){

		tr[x]=-1;

		if(l==r)return ;

		int mid=l+r>>1;

		build(ls,l,mid);

		build(rs,mid+1,r);

	}

	void pushdown(int x){

		if(!laz[x])return ;

		laz[ls]=max(laz[ls],laz[x]);

		tr[ls]=laz[ls];

		laz[rs]=max(laz[rs],laz[x]);

		tr[rs]=laz[rs];

		laz[x]=0;

	}

	void update(int x,int l,int r,int ql,int qr,int v){

		if(ql>qr)return ;

		if(ql<=l&&r<=qr){

			laz[x]=max(laz[x],v);

			tr[x]=laz[x];

			return ;

		}

		pushdown(x);

		int mid=l+r>>1;

		if(ql<=mid)update(ls,l,mid,ql,qr,v);

		if(qr>mid)update(rs,mid+1,r,ql,qr,v);

		return ;

	}

	int query(int x,int l,int r,int pos){

		if(l==r)return tr[x];

		pushdown(x);

		int mid=l+r>>1;

		if(pos<=mid)return query(ls,l,mid,pos);

		else return query(rs,mid+1,r,pos);

	}

	#undef ls

	#undef rs

}xds;

signed main(){

	scanf("%d%d",&n,&m);

	for(re i=1;i<=n;i++)scanf("%d",&w[i]);

	for(re i=1,x,y;i<n;i++){

		scanf("%d%d",&x,&y);

		add_edg(x,y);add_edg(y,x);

	}

	xds.build(1,1,n);

	dfs1(1);vis[1]=true;

	for(re i=1;i<=m;i++){

		char ch[10];int x;

		scanf("%s%d",ch,&x);

		if(ch[0]=='M'){

			int u=x;

			xds.update(1,1,n,dfn[u],dfm[u],w[u]);

			while(!vis[u]){

				vis[u]=true;

				xds.update(1,1,n,dfn[fa[u]],dfn[u]-1,w[fa[u]]);

				xds.update(1,1,n,dfm[u]+1,dfm[fa[u]],w[fa[u]]);

				u=fa[u];

			}

		}

		else{

			printf("%d\n",xds.query(1,1,n,dfn[x]));

		}

	}

}


最新文章

  1. C#在函数内部获取函数的参数
  2. js的一些实用的小技巧
  3. javascript --- 设计模式之构造函数模式
  4. Windows上使用clang编译
  5. 简述Docker镜像、容器、仓库概念
  6. （翻译）Google Guava Cache
  7. 预处理命令#define #undef #if #endif 的基本用法
  8. Ubuntu vim+ ctags(包含系统函数) + taglist 配置 分类： vim ubuntu 2015-06-09 18:19 195人阅读 评论(0) 收藏
  9. CodeForces 816B Karen and Coffee（前缀和，大量查询）
  10. 数据库——MongoDB——&gt;Java篇
  11. Kafka（二）CentOS7.5搭建Kafka2.11-1.1.0集群与简单测试
  12. Linux ，Ubuntu 分区建议大小
  13. DES对称加密算法详解和c++代码实现（带样例和详细的中间数据）
  14. Tomb Raider
  15. C#与Java AES 加密解密
  16. 一个数学不好的菜鸡的快速沃尔什变换(FWT)学习笔记
  17. pop3设置
  18. Python初学手记----在window系统中安装环境
  19. Bettercap的安装和使用嗅探WIFI
  20. Cstring, TCHAR*, char*的转换

热门文章

  1. mybatis入“坑”第一步
  2. Redis的事务不是原子性的
  3. 关于asp.net中Repeater控件的一些应用
  4. java list 分页
  5. ctf实验吧逻辑问题
  6. npm run start失败&amp;Node.js 查询指定端口运行情况及终止占用端口办法
  7. NOIP 模拟赛 day5 T2 水 故事题解
  8. LOJ528 「LibreOJ β Round #4」求和
  9. 基于Ryu的流量采集代码实现
  10. C语言：读写TXT