时间戳

首页 > 技术文章 > [机房测试]11.4

[机房测试]11.4

ssw02 2019-11-04 19:38 原文

[机房测试]11.4

ssw02咕了几天

欢迎转载ssw02的博客:https://www.cnblogs.com/ssw02/p/11794181.html

algebra

神仙T1， 有意者可以去看下HEOI-动动的博客。

decoration

话说Deco他，应该切了这道题吧。

输入输出：

第一行一个正整数n。
接下来一行n 1 个正整数，第i 个数为fi+1。
接下来一行n 个数，若第i 个数为0 则表示林先森希望i 号点的彩灯是关闭状态，若第i
个数为1 则表示林先森希望i 号点的彩灯是开启状态。
输出一行一个整数，表示林先森最少需要几秒才能看到他期望看到的树。

思路：

由于N很小，所以考虑到状压。由于什么想法都没有，所以考虑DP。（lwq:状压DP不分家，不分N^TM呢）

考虑到一件事，林先生可以在激活一个点（不是MC）后，在下一秒关掉它，所以时间不会超过 N 。（你可以输出N+-rand()骗分 ）。

我们预处理出change[i][j]表示在第 i 个点激活后 j 秒对整棵树的影响 。考虑到贡献时将 sta |= change 即可。

由于影响连续的，如果顺序枚举，必须同时消除一个点1秒前的影响，在加入影响，我的做法会是复杂度多一个乘N。

但是如果倒叙枚举，时间不定。所以设DP[i][j]为状态为j,i秒后可以变为目标态。这样只用异或一个change[i][j-1]即可。

得到状态转移方程： dp[i+1][j^change[k][i]] = dp[i][j]?true:false ; ( k : 1~(1<<N)-1 )

代码

#include<bits/stdc++.h>
using namespace std ;
inline int read(){
	int s=0 ; char g=getchar() ; while(g>'9'||g<'0')g=getchar() ; 
	while( g>='0'&&g<='9' )s=s*10+g-'0',g=getchar() ; return  s ;
}
int N , sta , fa[20] , change[20][20] , dp[20][(1<<17)] ; 
void  prepare(){
	for( int i = 0 ; i <= N ; ++i )change[1][i] = 1 ;
	for( int i = 2 ; i <= N ; ++i ){
		int now = i ; 
		change[i][0] = ( 1<<(i-1) ) ; 
		for( int j = 1 ; j <= N ; ++j ){
			now = fa[now] ; 
			if(now) change[i][j] = (change[i][j-1]|(1<<(now-1))) ;
			else change[i][j] = change[i][j-1] ;//到顶了 
		}
	}
}
int main(){
	freopen("decoration.in","r",stdin) ; 
	freopen("decoration.out","w",stdout) ;
	N = read() ;  int m1 ; fa[1] = fa[0] = 0 ;
	for( int i = 1 ; i < N ; ++i )fa[i+1] = read() ; 
	for( int i = 1 ; i <= N ; ++i ){
		m1 = read() ;if(m1)sta |= (1<<(i-1) ) ;
	}
	prepare() ;
	dp[0][sta] = 1 ; // 状态为sta,0秒后状态为sta 
	for( int i = 0 ; i <=  N ; ++i ){
		if( dp[i][0] ){
			cout<<i ; return 0 ; 
		}
		for( int k = 1 ; k <= (1<<N)-1 ; ++k )
		    if( dp[i][k] ){//状态为k，i秒后可以到达sta 
		    	dp[i+1][k] = true ; 
		    	for( int j = 1 ; j <= N ; ++j )dp[i+1][k^change[j][i]] = true ; 
		    }
	}
	return 0;
}

lunch

说实话，这道题还挺毒瘤的。。。。（思维清奇）

我们考虑到各种人之间的冲突关系：

如果一个人为 0 ， 那我们可以不用特别管他 ， 适应局势即可。。

考虑到一个人为 -1 ,但是他又和一个为 1 的人吃饭，那么在吃饭之前为 1 的人一定没有学会毒瘤算法。

注意读题：开启了SPJ,所以我们只要让方案尽可能合法即可。

如果一个人可以在 i 时刻学会毒瘤算法，那么他一定不会再 j(j>i)时才学会毒瘤算法。把整个过程尽量往前推。

具体而言：令分 h[] 为一个人最早学会毒瘤算法的时间 。 那么他会受吃饭中-1的人影响。为了让时间尽量提前，那么选择L时吃饭，h[u] = L+1 。

然后考虑到更多人之间的关系。 令（u,v）一起吃饭。如果已知 f[u] > R ，那么 v 和 u 吃饭及之前也肯定没有学会，否则无解。这种情况也会导致 h[u] - max( h[u] , L+1 )。

考虑到 h[u] 必须满足所有限制，所以取最大值 。 这个东西可以用最长路维护，跑一次dijkstar。

现在维护出了h[]数组，在考虑吃饭的问题： 每个人吃饭的时间满足：1.合法（可以吃饭）2.满足dis[i] >= h[i] 。让上述关系全部合法，可以得到（ u学会毒瘤算法，传授给v , 最短时间用dis数组表示 ）

lim = max( h[to[i]] , max( L[i] , dis[u] ) ) 。 dis[to[i]] = min( dis[to[i]] , lim ) 。

然后，这又是一次dijkstra ......

判断Impossible 的ssw02写代码里了。

代码：

#include<bits/stdc++.h>
using namespace std ;
const int MAXN = 200005 ;
inline int read(){
	int s=0,w=1 ; char g=getchar() ; while(g>'9'||g<'0'){if(g=='-')w=-1,g=getchar() ;} 
	while(g>='0'&&g<='9')s=s*10+g-'0',g=getchar() ; return s*w ;
}
int N , M , sta[MAXN] , h[MAXN] , L[MAXN*2] , R[MAXN*2] ;
int head[MAXN] , to[MAXN*2] , nex[MAXN*2] , tot = 1 ;
bool vis[MAXN] ; 
struct ap{
	int u , v , l , r ; 
}t[MAXN] ;
priority_queue<pair<int,int> >q ; 
void  add( int x , int y , int l , int r ){
	to[++tot] = y , nex[tot] = head[x] , L[tot] = l , R[tot] = r , head[x] = tot ; 
}
void  dijkstra(){//维护每个人学会的时间的下限 
	while( !q.empty() ){
		int  u = q.top().second ; q.pop() ; 
		if( vis[u] )continue ; 
		vis[u] = true ; 
		for( int i = head[u] ; i ; i = nex[i] ){//u,v在 L R 吃饭  , u 学会的时间 > R ，说明 u,v吃饭时v还没有学会,贪心在L吃饭，v在L+1学会 
			if( R[i] < h[u] )//出现限制情况 
			    if( h[to[i]] < L[i]+1 ){//更新限制 
				    h[to[i]] = L[i]+1 ;
				    q.push( make_pair( h[to[i]],to[i] ) ) ; 
			    }
		}
	}
}
int dis[MAXN] ; 
void  dijkstra2(){//维护每个人学会的时间 (贪心最早)
	while( !q.empty() )q.pop() ; 
	memset( vis , 0 , sizeof(vis) ) ;
	for( int i = 1 ; i <= N ; ++i )dis[i] = (1<<30) ; 
	q.push( make_pair(0,1) ) ; dis[1] = 0 ;
	while( !q.empty() ){
		int u = q.top().second ; q.pop() ;
		if( vis[u] )continue ; 
		vis[u] = true ; 
		for( int i = head[u] ; i ; i = nex[i] ){
			int  lim = max( h[to[i]] , max( L[i] , dis[u] ) ) ;//由 u 传授给 v : 满足条件 u会 ， 能吃饭 
			if( lim <= R[i] )//合法 
				if( dis[ to[i] ] > lim ){
					dis[ to[i] ] = lim ;
					q.push( make_pair( -dis[to[i]] , to[i] ) ) ;
				}
		}
	}
}
void  print(){
	for( int i = 1 ; i <= M ; ++i ){
		if( sta[t[i].u] == -1 || sta[t[i].v] == -1 || ( t[i].r < max(dis[t[i].u] , dis[t[i].v]) ) )printf("%d\n",t[i].l ) ; 
		//有任意一个人不会，贪心最早吃饭 || 两个人吃饭时都不会 (任意时间吃)
		else printf("%d\n",max( max(dis[t[i].u],dis[t[i].v]) , t[i].l ) ) ;
	}
}
int main(){
	freopen("lunch.in","r",stdin) ;
	freopen("lunch.out","w",stdout) ; 
	N = read() , M = read() ; 
	for( int i = 1 ; i <= M ; ++i ){
		t[i].u = read() , t[i].v = read() , t[i].l = read() , t[i].r = read() ;
		add( t[i].u , t[i].v , t[i].l , t[i].r ) ; 
		add( t[i].v , t[i].u , t[i].l , t[i].r ) ;  
	}
	for( int i = 1 ; i <= N ; ++i ){
		sta[i] = read() ; 
		if( sta[i] == -1 ){
			h[i] = (1<<30) ; q.push( make_pair( h[i] , i ) ) ;
		}
	}
	dijkstra() ; dijkstra2() ; bool flag = 1 ; 
	for( int i = 1 ; i <= N ; ++i )//最后会但限制不会，冲突 
	    if( sta[i] == 1 && dis[i] == (1<<30) )flag = 0 ; 
	for( int i = 1 ; i <= M ; ++i ){
		if( sta[ t[i].u ]==-1 && dis[ t[i].v ] <= t[i].l )flag = 0 ;//明明不会有还在和会的吃饭 
		if( sta[ t[i].v ]==-1 && dis[ t[i].u ] <= t[i].l )flag = 0 ;
	}
	if( flag )print() ; 
	else cout<<"Impossible" ;
	return 0 ;
}

总结

T1,zhen ^TM 毒瘤（我差点写成了华容道加强版。。。。）

T2的状态转移方程设计很经典，在未知目标时，考虑到change数组是固定到目标态的时间，为了方便，就倒叙设计状态转移。

T3属于思路非常好的带限制问题转化为最短路问题。满足多个带限制条件，（和差分约束的思想比较相似）。

今天考试时判题还是有问题，在T1发现更优做法时明显慌张了，影响了整个考试的心态。T2和T3又是思路+套路问题，一时没有突破口导致ssw02死的很惨。。。（考到后面都去复习PPT了。。。）T1上真的花掉了太多时间，而且每个打包数据都被卡了（subtask杀人了！！！），明天一定要先验证算法，不要依赖做过的题。。。。

推荐阅读