时间戳

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

[机房测试]11.6

ssw02 2019-11-06 15:15 原文

[机房测试]11.6

电子科大的题，整体不错，就是T3水了点。但是分3页PDF是无法接受的

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

三教

为什么叫三教呢 ? ssw02还是个高中生，当然不知道了。

读入

第一行两个非负整数 ，表示表示补给点个数和需要收集的体力数；

第二行 N 个非负整数 ，第 i 个整数表示在不触发 bug 的情况下补给点 提供的体力。

思路

60分的做法嘛，这种搜索小学生都会了。

100分做法： N = 25 , 如果只有一半 N = 13 ,复杂度就在 1e6 级别 ， 所能得到的各种答案最多有 1e6 种。同时考虑到蒋神才讲了折半法 ， 那就简单了。 用map或者hash记录先搜索前一半能的到的结果 。 搜索后一半是统计 T-val 的贡献即可 。 懒人ssw02用了map 。 但把一个 ll 错开为 int - - 100 -> 25 （部分分都没拿全）

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
inline ll read(){
	ll 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 ;
}
ll N , T , a[30] , b[30] , sum[30] , ans , tot = 0 , half , cnt = 0 , preans[600000] ; 
struct ap{
	ll x , y  ;
}t[30];
map<ll,ll>h ;  
inline bool cmp( ap X , ap Y ){
	return  max( X.x , X.y ) > max( Y.x , Y.y )  ;
}
ll work( ll bb ){
	ll anss = 1LL ;
	while(bb){
		if(bb&1)anss*=2LL ; 
		bb>>=1 ; 
	} 
	return anss ; 
}
void  dfs( int now , ll val ){//部分分
	if( now > N ){if( val == T )ans++ ; return ; }
	if( val > T )return ;
	dfs( now+1 , val ) ; 
	dfs( now+1 , val+a[now] ) ;
	dfs( now+1 , val+b[now] ) ;
}
void  dfs2( int now , ll val ){
	if( now > half ){  
	    if( h.find(val) == h.end() ){
	    	cnt++ ; preans[cnt]++ ;
		    h.insert( make_pair(val,cnt) ) ;  
			return ;
	    }
	    int u = (int)h[val] ; preans[u]++ ; return ; 
	}
	if( val > T )return ;
	dfs2( now+1 , val ) ; 
	dfs2( now+1 , val+a[now] ) ;
	dfs2( now+1 , val+b[now] ) ;
}
void  dfs3( int now , ll val ){
	if( now > N ){  
	    if( h.find(T-val) == h.end() )return ;
	    int u = (int)h[T-val] ; ans += preans[u] ; return ; 
	}
	if( val > T )return ;
	dfs3( now+1 , val ) ; 
	dfs3( now+1 , val+a[now] ) ;
	dfs3( now+1 , val+b[now] ) ;
}
void  work2(){
	for( int i = 1 ; i <= N ; ++i )t[i].x = a[i] , t[i].y = b[i] ; 
	//sort( t+1 , t+N+1 , cmp ) ;
	half = N/2LL ;
	dfs2( 1 , 0LL ) ; 
	dfs3( half+1 , 0LL ) ;
	cout<<ans ; 
}
int main(){
	freopen("building.in","r",stdin) ; 
	freopen("building.out","w",stdout) ; 
	N = read() , T = read() ; 
	for( int i = 1 ; i <= N ; ++i ){
		a[i] = read() ; b[i] = work(a[i]) ; 
	} 
	if( N <= 10 ){dfs(1,0LL );cout<<ans;}
	else work2() ; 
	return 0 ;  
}

PESTC

沙河人民公园？电子科技公园？ 我只知道某停电后的 ‘ ’子科技大学

读入一个带边权的有向图

思路

是个人都会想到 topo , 这个思路bfk以前也给我们考过 。

ssw02考场时被重环卡了，最后判重环判到死循环。。。。。

实际上可以想到，题目保证有解（实际上也一定有解），所以如果我们把边权小于等于 x 的边全部翻来翻去，一定可以让这部分没有环 。只要判断边权 > x 的边即可 。 这个过程明显可以二分。。。水题，不过 topo 的思路真的很好。

#include<bits/stdc++.h>
using namespace std ;
const int MAXN = 200005 , MAXM = 300005 ;
#define ll long long 
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 ;
}
struct ap{
	int fro , too , val ; 
}t[MAXM];
int N , M , head[MAXN] , to[MAXM] , nex[MAXM] , w[MAXM] , tot = 1 ;
int du[MAXN] , vis[MAXN] ; 
queue<int>q ;
void  add( int x , int y , int z ){
	to[++tot]=y , nex[tot] = head[x] , head[x] = tot , w[tot] = z ;
} 
inline bool check( int lim ){
	memset( head , 0 , sizeof(head) ) ; for( int i = 1 ; i <= N ; ++i )du[i] = 0 , vis[i] = true ;  
	memset( du , 0 , sizeof(du) ) ; tot = 1 ;  
	for( int i = 1 ; i <= M ; ++i ){
		if( t[i].val <= lim )continue ; du[ t[i].too ]++ ; vis[ t[i].fro ] = vis[t[i].too ] = 0 ; 
		add( t[i].fro , t[i].too , t[i].val ) ;
	}
	for( int i = 1 ; i <= N ; ++i )if( !du[i] && vis[i] == 0 ){
		q.push( i ) ; vis[i] = true ; 
	}
	while( !q.empty() ){
		int u = q.front() ; q.pop() ; 
		for( int i = head[u] ; i ; i = nex[i] ){
			if( vis[ to[i] ] )continue ; 
			du[ to[i] ]-- ; 
			if( du[ to[i] ] == 0 ){
				vis[ to[i] ] = true ; q.push( to[i] ) ; 
			} 
		}
	}
	//for( int i = 1 ; i <= N ; ++i )cout<<vis[i]<<" " ; cout<<endl ;
	for( int i = 1 ; i <= N ; ++i )if( !vis[i] )return false ;
	return true ;
}
void  dx( int l , int r ){
	int ans = 0 ; 
	while( l <= r ){
		int mid = (l+r)>>1 ; 
		if( check(mid) )ans = mid , r = mid-1 ; 
		else l = mid+1 ; 
	}
	cout<<ans ;
}
int main(){
	freopen("pestc.in","r",stdin) ;
	freopen("pestc.out","w",stdout) ; 
	N = read() , M = read() ; int maxx = 0 ;
	for( int i = 1 ; i <= M ; ++i )
		t[i].fro = read() , t[i].too = read() , t[i].val = read() , maxx = max( maxx , t[i].val )  ;
	dx( 0 , maxx ) ;
	return 0 ;  
}

这不是丁香树

为何ssw02想到了 这货不是乌迪尔 ？

开个桶记录 ， 每次修改用树状数组维护一下 ， 在值域上分3段区间求和 ， 用dsu on tree即可 ， 不会的可以去翻翻ssw02的学习笔记-Dsu ontree。

话说ssw02的学习笔记被盗搬还不带原文地址，还把DSU改成了DUS,迷惑。

代码

#include<bits/stdc++.h>
using namespace std ;
const int MAXN = 200005 ;
#define ll long long 
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 , S , a[MAXN] , b[MAXN] , size[MAXN] , son[MAXN] ;
int to[MAXN*2] , nex[MAXN*2] , head[MAXN] , tot = 1 , tott ;
int A[MAXN] , B[MAXN] , C[MAXN] ; 
//-----------------
ll cnt[MAXN] ; 
void  insert( int x , int y ){
	for( ; x <= N ; x += x&-x )cnt[x] +=(ll)y ; 
}
ll ask_sum( int x ){
	ll sum = 0 ;
	for( ; x ; x -= x&-x )sum += cnt[x] ; 
	return sum ; 
}
//-----------------
void  add( int x , int y ){
	to[++tot] = y , nex[tot] = head[x] , head[x] = tot ; 
}
int  query( int x ){
	return lower_bound( b+1 , b+tott+1 , x ) - b ; 
}
void  dfs( int u , int fa ){
	size[u] = 1 ; 
	for( int i = head[u] ; i ; i = nex[i] ){
		if( to[i] == fa )continue ; 
		dfs( to[i] , u ) ; 
		size[u] += size[ to[i] ] ; 
		if( size[to[i]] > size[son[u]] )son[u] = to[i] ;  
	}
}
void  Updata( int u ){
	int col = query( a[u] ) ;//B减1 是为了刨除自己的贡献 
	A[u] = (int)( ask_sum(col-1) ), B[u] = (int)( ask_sum(col) - ask_sum(col-1) ) - 1, C[u] = (int)(ask_sum(tott)-ask_sum(col) ) ; 
}
void  deal( int u , int fa , int val ){
	int col = query( a[u] ) ; 
	insert( col , val ) ; 
	for( int i = head[u] ; i ; i = nex[i] ){
		if( to[i] == fa )continue ; 
		if( to[i] != S )deal( to[i] , u , val ) ; 
	}
}
void  dfs2( int u , int fa , int opt ){
	for( int i = head[u] ; i ; i = nex[i] ){
		if( to[i] == fa )continue ; 
		if( to[i] != son[u] )dfs2( to[i] , u , 0 ) ; 
	}
	if( son[u] )dfs2( son[u] , u , 1 ) , S = son[u] ; 
	deal( u , fa , 1 ) ;
	S = 0 ; Updata( u ) ; 
	if( !opt )deal( u , fa , -1 )  ;
}
int main(){
	freopen("ginkgo.in","r",stdin) ; 
	freopen("ginkgo.out","w",stdout) ;
    N = read() ; int m1 ; 
	for( register int i = 2 ; i <= N ; ++i ){
		m1 = read() ; add( m1 , i ) , add( i , m1 ) ; 
	}	
	for( register int i = 1 ; i <= N ; ++i )a[i] = b[i] = read() ; 
	dfs( 1 , 1 ) ;
	sort( b+1 , b+N+1 ) ; tott = unique( b+1 , b+N+1 ) - b - 1 ;
	dfs2( 1 , 1 , 0 ) ;
	for( register int i = 1 ; i <= N ; ++i ){
		printf("%d %d %d\n",A[i],B[i],C[i] ) ;
	}
	return 0 ;
}

总结

ssw02蠢了。。

开局写了T1 60分，然后就先把 T3 切了，然后回来写了会T2 , 中途T1有了正解 ， 写了T1，拍了T3 。结果T2最后发现死循环的问题，改了又改，结果。。。。暴毙

T1 : 折半法很依赖数据范围 。 然而 ll 调用时错写了一个 int ，60都没有，艹。。

T2 : 思路还是有一点问题，应该猜一下结论，然后多手推几组数据，不应该丢分啊。

T3 : DSU on tree 裸题啊 。 比模板还裸 ， 虽然可以想天天爱跑步一样做。。。

推荐阅读