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 ;
}
- AtCoder Regular Contest 164 A-Catcoder regular contest 164 atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest sliding atcoder regular contest 167 atcoder regular contest builder subsegments atcoder regular contest inversion atcoder regular contest