[机房测试]10.25

2024-03-16 13:10:46

[机房测试]10.25

T2爆0啦,只有123啦

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

考试的时间点记录

14:32 T1结束开T2

14:35 验证T1

14:53 T2无思路，开T3

15:12 开T3暴力

16:11 T3 50分

16:46 T2 50分有锅

16:54 T2 改完

board

点双联通分量嘛，由于题目特殊，打个特判+记录度数也可以过

change

神仙。。。。

逻辑推理+分类讨论
结论是：如果a=1,10,100,1000并且b != 2a，那么答案是2，否则是1.
考虑为什么，⾸先分析1,2,5,10这⼏个⼩的，如果a = 1,b >= 5，那么⼀定需要⾄少2，否则只需要1（这个⾃⼰可
以枚举⽅案证明）。
然后考虑⼤的的情况，举个例⼦，如果a = 10,b = 50，那么买了1之后，需要找零49，这个9肯定是⽤1,2,5凑出来
的（这⾥的意思是，能拼出49，⼀定能拼出9，然后剩下的部分即使有1,2,5，他们也⼀定能拼出10），减掉他们之
后相当于⽤10,20,去凑40，就回到了上⾯的情况。其他情况类似证明。

#include<bits/stdc++.h>
using namespace std ;
const int MAXN = 100005 ;
const int val[14]={0,1,2,5,10,20,50,100,200,500,1000,2000,5000,10000}; 
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 T , A , B ; 
int main(){
    freopen("change.in","r",stdin);
    freopen("change.out","w",stdout);
    T = read() ;
    while( T-- ){
        A = read() , B = read() ; 
        int flag = 2 ;
        if( B == 1 || B == 100 || B == 10 || B == 1000 )flag-- ;
        if( A != B*2 )flag-- ;
        if( flag )cout<<1<<endl ;
        else cout<<2<<endl ;    
    }
    return 0 ;
}

fill

话说。。。为什么50分比满分还要难写啊！！！！！！！！！

10分，枚举+树上暴跳
+40分，转化为序列贪心右端点排序。

话说，ssw02都想到了贪心，为啥没想到贪lca呢？

按照询问的lca从深到浅贪心即可。

如果左右点在dfn上没有被覆盖，那么把lca的子树全部打标记。

用个数据结构维护下区间加即可。

#include<bits/stdc++.h>
using namespace std ;
const int MAXN = 100005 ; 
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 T , N , M , ans , fa[MAXN] , dep[MAXN] , d[MAXN] , rev[MAXN] , cnt ;
int head[MAXN] , to[MAXN*2] , nex[MAXN*2] , tot = 1 ;
bool vis[MAXN] ; 
struct ap{
    int  a, b  ;
}t[MAXN];
inline bool cmp( ap x , ap y ){
    return ( x.b == y.b )?(x.a<y.a):(x.b<y.b) ;
}
void  add( int x , int y ){
    to[ ++tot ] = y , nex[tot] = head[x] , head[x] = tot ; 
}
bool lis( int x , int y ){
    if( vis[x] || vis[y] )return true ;
    if( x==y && vis[x]==0 )return false ; 
    while( x!=y ){
        if( dep[x] < dep[y] )swap( x,y ) ;
         if( vis[ fa[x] ] )return true ;
         x=fa[x] ;
    }
    return false ;
}
int check(){
    int flag = (1<<30) ; 
    for( int i=1 ; i<=M ; ++i ){
        if( !lis( t[i].a , t[i].b ) )return flag ;
    }
    flag=0 ;
    for( int i=1 ; i<=N ; ++i )if( vis[i] )flag++ ;
    return flag ;
}
void  find( int stp ){
    if( stp > N )return ;
    vis[stp] = true ; ans = min( check() , ans ) ; 
    find( stp+1 ) ;
    vis[stp] = false ; ans = min( check() , ans ) ; 
    find( stp+1 ) ;
}
void  dfs( int u , int father ){
    fa[u] = father ;
    for( int i = head[u] ; i ; i = nex[i] ){
        if( to[i] == father )continue ;
        dep[ to[i] ] = dep[u] + 1 ;
        dfs( to[i] , u ) ;  
    }
}
void  dfs2( int u , int father ){
    fa[u] = father ; rev[u] = ++cnt ; 
    for( int i = head[u] ; i ; i = nex[i] ){
        if( to[i] == father )continue ;
        dfs2( to[i] , u ) ;
    }
}
void  work1(){
    int m1 , m2 ; ans = (1<<30) ; 
    for( int i = 1 ;  i < N ; ++i ){
        m1 = read() , m2 = read() ;
        add( m1 , m2 ) , add( m2 , m1 ) ; 
    } 
    dfs( 1 , 1 ) ;
    for( int i = 1 ; i <= M ; ++i )t[i].a = read() , t[i].b = read() ;
    find( 1 ) ; 
    cout<<min( ans , N )<<endl ;
}
void  work2(){
    int m1 , m2 ; ans = (1<<30) ;
    for( int i = 1 ; i < N ; ++i ){
        m1 = read() , m2 = read() ; d[m1]++ , d[m2]++ ;
        add( m1 , m2 ) , add( m2 , m1 ) ;
    }
    for( int i = 1 ; i <= N ; ++i )
        if( d[i] == 1 ){dfs2( d[i] , d[i] ) ; break ; }//扫出新的序列 
    for( int i = 1 ; i <= M ; ++i ){
        m1 = read() , m2 = read() ;
        if( rev[m1] > rev[m2] )swap( m1 , m2 ) ;
        t[i].a=rev[m1] , t[i].b = rev[m2] ;
    }
    sort( t+1 , t+M+1 , cmp ) ; 
    ans = 1 ; int now = t[1].b ;
    for( register int i = 2 ; i <= M ; ++i ){
        if( t[i].a <= now )continue ;
        now = t[i].b , ans++ ;
    }
    cout<<min(ans,N)<<endl ;
}
void  clear(){
    for( register int i = 1 ; i <= N ; ++i )
    rev[i] = d[i] = t[i].a = t[i].b = head[i] = dep[i] = fa[i] = vis[i] = 0 ;
    tot = 1 , ans = (1<<30) , cnt = 0 ;
}
int main(){
    freopen("fill.in","r",stdin) ;
    freopen("fill.out","w",stdout) ;
    T = read() ;
    while( T-- ){
        N = read() , M = read() ;
        if( M==0 ){puts("0");continue;} 
        if( N <= 12 && M <= 30 )work1() ;
        else work2() ; 
        clear() ;
    }
    return 0 ;
}

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const int MAXN = 100005 ; 
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 T , N , M , tot = 1 , cnt ;
int  head[MAXN] , to[MAXN*2] , nex[MAXN*2] , dep[MAXN] , dfn[MAXN] , rev[MAXN] , anc[MAXN][20] , out[MAXN] ;
int  c[MAXN] ;
struct ap{
    int l , r , tp ; 
}t[MAXN];
//-------------
void  updata( int x , int y ){
    for( ; x <= N ; x += x&-x )c[x] += y ; 
}
ll sum( int x ){
    ll anss = 0 ;
    for( ; x ; x-= x&-x )anss += (ll)c[x] ;
    return anss ; 
}
//-------------
inline bool cmp( ap x , ap y ){
    return ( dep[ rev[x.tp] ] == dep[ rev[y.tp] ] )?( x.tp > y.tp ):(dep[ rev[x.tp] ]>dep[ rev[y.tp] ]) ;
    //return dep[ rev[x.tp] ]>dep[ rev[y.tp] ] ;
}
void add( int x , int y ){
    to[ ++tot ] = y , nex[tot] = head[x] , head[x] = tot ;
}
int lca( int x , int y ){
    if( dep[x] < dep[y] )swap( x , y ) ; 
    int t = dep[x] - dep[y] ;
    for( int p=0 ; t ; t >>=1 , ++p )
        if( t&1 )x = anc[x][p] ;
    if( x==y )return x ;
    for( int p=17 ; anc[x][0] != anc[y][0] ; p-- )
        if( anc[x][p] != anc[y][p] )x=anc[x][p] , y=anc[y][p] ;
    return anc[x][0] ;  
}
void  dfs( int u , int fa ){
    anc[u][0] = fa , dfn[u] = ++cnt , rev[cnt] = u ; 
    for( int i = 1 ; i <= 17 ; ++i )anc[u][i] = anc[ anc[u][i-1] ][i-1] ;
    for( int i = head[u] ; i ; i = nex[i] ){
        if( to[i] == fa )continue ;
        dep[ to[i] ] = dep[u] + 1 ;
        dfs( to[i] , u ) ;
    }
    out[u] = cnt ;
}
void  work(){
    int m1 , m2 ; 
    for( int i = 1 ; i < N ; ++i ){
        m1 = read() , m2 = read() ; 
        add( m1 , m2 ) , add( m2 , m1 ) ;
    }
    dfs( 1 , 1 ) ; 
    for( int i = 1 ; i <= M ; ++i ){
        m1 = read() , m2 = read() ;
        int tp = lca( m1 , m2 ) ;  
        if( dfn[m1] > dfn[m2] )swap( m1 , m2 ) ; 
        t[i].l = dfn[m1] , t[i].r = dfn[m2] , t[i].tp = dfn[tp] ; 
    }   
    sort( t+1 , t+M+1 , cmp ) ; int ans = 0 ;
    for( int i = 1 ; i <= M ; ++i ){
        //if( sum( t[i].tp )  )continue ;
        if( sum( t[i].l ) || sum( t[i].r ) )continue ;
        updata( t[i].tp , 1 ) , updata( out[ rev[ t[i].tp ] ]+1 , -1 ) ;ans++ ;
    }
    cout<<ans<<endl ;
} 
void  clear(){
    for( register int i = 1 ; i <= max( N , M ) ; ++i )out[i] = t[i].tp = t[i].l = t[i].r = c[i] = head[i] = dep[i] = dfn[i] = rev[i] = 0 ;
    tot = 1 , cnt = 0 ;
}
int main(){
    freopen("fill.in","r",stdin) ;
    freopen("fill.out","w",stdout) ;
    T = read() ;
    while( T-- ){
        N = read() , M = read() ; 
        work() ; 
        clear() ; 
    }
    return 0 ;
}

码农公寓

[机房测试]10.25

考试的时间点记录

board

change

fill

相关文章