A. Ternary Decomposition

思维难度其实可以作为第二题

思路

先考虑最优情况下需要多少个数来组成（不够就 No）
在考虑全部为1的情况下是否可行（ N < K 这种情况不行）
剩下的情况，考虑每次把高位的1向下挪变为3 ，所需的数字＋2
那么即三进制拆分后，在[min , max]范围内，且与最优情况差值为2 都是可行方案

完整代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 100005 ; 
inline ll read(){
	ll 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 ; 
}
ll t , n , k ;
ll a[40] ; 
void solve(){
    ll n = read() , k = read() ;
    ll res = n%3 ; 
    if( n < k ){cout<<"No"<<endl ; return ;} 
    // ll h = 1350851717672992089ll ; ll a = 0 ;
    // for( int i = 38 ; i ; --i )
    int now = 0 ; ll tot = 0 ; 
    while( n ){
        a[++now] = n%3 ; 
        n /= 3 ;
        tot += a[now] ; 
    }
    if( k >= tot && (k-tot)%2 == 0 ){cout<<"Yes"<<endl ; return ;}
    cout<<"No"<<endl ; return ;
}
int main(){
    t = read() ; 
    while( t-- )solve() ; 
}

B. Switching Travel

ssw：一个奇妙的思路

思路

比赛的时候，我先是用拓扑删掉了图外面的链（后来发现不删也可以）
然后dfs,按照不同颜色去走，只要发现走过的点，且相邻的，颜色相同，那么必定有一个环可以走回

完整代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 400005 ; 
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 head[MAXN] , to[MAXN] , nex[MAXN] , d[MAXN] , tot = 1 ; 
int n , m , c[MAXN] , sing[MAXN] , v[MAXN] , now , ans = 0 ; 
void add( int x , int y ){
	d[y]++ , to[++tot] = y , nex[tot] = head[x] , head[x] = tot ; 
}
void dfs( int u ){
    v[u] = now ; if( ans )return ;
    for( int i = head[u] ; i ; i = nex[i] ){
        if( d[ to[i] ] <= 1 || sing[ to[i] ]  )continue ;
        if( v[to[i]] == now ){
            if( c[u] == c[ to[i] ] ){ ans = 1 ; return ; }
            continue ; 
        }
        if( c[ to[i] ] != c[u] )dfs( to[i]  ) ;
    }
}
int main(){
	n = read() , m = read() ; 
    for( int i = 1 ; i <= m ; ++i ){
        int a = read() , b = read() ; add( a , b ) ; add( b , a ) ; 
    }
    for( int i = 1 ; i <= n ; ++i )c[i] = read() ; 
    queue<int>q ; 
    for( int i = 1 ; i <= n ; ++i )
        if( d[i] == 0 )sing[i] = 1 ; 
        else if( d[i] == 1 ){
            q.push( i ) ; v[i] = 1 ; 
        }
    while( !q.empty() ){
        int u = q.front() ; q.pop() ;
        for( int i = head[u] ; i ; i = nex[i] ){
            if( v[to[i]] )continue ; 
            d[ to[i] ]-- , d[u]-- ; 
            if( d[ to[i] ] <= 1 && v[ to[i] ] == 0 ){
                v[ to[i] ] = 1 ; q.push( to[i] ) ; 
            }
        }
    }
    memset( v, 0 , sizeof(v) ) ; 
    //for( int i = 1 ; i <= n ; ++i )cout<<sing[i]<<" "; cout<<endl ; 
    for( int i = 1 ; i <= n ; ++i ){
        if( d[i] <= 1 || sing[i] || v[i] )continue ; 
        now = i ; 
        dfs( i  ) ; 
        if( ans ){
            cout<<"Yes"; return 0 ; 
        }
    }
    cout<<"No" ; return 0 ; 
}

C. Reversible Card Game

fxs:这题是个巨复杂的博弈论，你好好想
ssw:????? 这不就是一个优先队列吗？？？？

思路

主要思路

考虑这种博弈：爱丽丝每次翻卡，一定会把差值（a-b）最大的翻走。Bob一定会取走当前差值最大的，不让爱丽丝翻，那就用一个优先队列动态维护这个过程即可

代码

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
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 ; 
}
struct ap{
    int a , b , c , id ; 
    friend bool operator < (ap a, ap b)    {    
        return a.c < b.c;   
    }  
}t[200005] ; 
priority_queue<ap>q ; 
int main(){
    int n = read() ; 
    for( int i = 1 ; i <= n ; ++i ){
        t[i].a = read() , t[i].b = read() ; t[i].c = t[i].a - t[i].b ; t[i].id = i ; 
        q.push( t[i] ) ; 
    }
    ll sum = 0 ;
    for( int i = 1 ; i <= n ; ++i ){
        int u = q.top().id ; q.pop() ;    
        swap( t[u].a , t[u].b ) ; t[u].c = t[u].a - t[u].b ; 
        q.push( t[u] ) ; 
        u = q.top().id ; q.pop() ; 
        sum += t[u].a ; 
    }
    cout<<sum ; 
}