好久没写博，最近做的题有点杂，先是在上周五夜里做了场CF，然后在完全没休息好的周六下午做了场队内比赛，战况惨烈啊，接下来的这个星期就一直在整理这两场比赛的题。
先说说CF上的比赛吧。
一如既往的水题，就不说了。
求由0~9中的任意一个或两个组成且小于等于N的数的个数。
读完题后没想法，又想到以往B题都是数论题，于是放弃B题转攻C题，最后的时候又看了一遍题觉得应该是组合数学，但是各种情况需要处理，有点繁琐，所以就没做。不过赛后看别人的代码貌似都是有DFS暴力搜的，的确这种做法很巧妙，但我却没想到，唉，还是不能真正理解DFS的用法啊。
参考代码：
View Code
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <algorithm> #include <set> #include <math.h> using namespace std ; typedef long long ll ; set<ll>ans; //ll ans ; ll n ; void cal( int x , int y , ll num , int len ) { if( num > n ) return ; if( len > 10 ) return ; ans.insert( num ) ; //ans++ ; cal ( x , y , num * 10 + x , len + 1 ) ; cal ( x , y , num * 10 + y , len + 1 ) ; } int main() { int i , j ; while ( cin>>n ) { ans.clear(); //ans = 0 ; for ( i = 0 ; i <= 9 ; i++ ) for ( j = i + 1 ; j <= 9 ; j++) cal( i , j , 0 , 0 ); cout<<ans.size()-1<<endl ; //cout<<ans<<endl ; } return 0 ; }
这题做了很久，最后感觉逻辑都乱了，不过觉得这题理清了题意，就很好做了，就是考逻辑的，注意以下几点：
（1、图为无向图，首先要找两个点分别大于h和t，是大于不是大于等于，因为u,v这两个点中分别含有对方这个点，而这个点不能算在内。
（2、u、v这两个点可能含有相同的点，所以最后要求一下不含重复点的总数是否大于h+t+2。
（3、在输出的时候，先输出u、v各自的点，即不重复的点，如果点不够在考虑用重复点输出。
注意到这三点大概就OK了。
参考代码：
View Code
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <algorithm> #include <queue> #include <vector> #include <math.h> #define N 100004 using namespace std ; vector<int>p[N] ; int vist[N] , comm[N] ; bool mark[N]; int n , m , h , t , id ; bool jud( int u , int v ) { if ( p[u].size() <= h || p[v].size() <= t ) return false ; id++ ; for ( int i = 0 ; i < p[u].size() ; i++ ) { if ( p[u][i] != v ) vist[p[u][i]] = id ; } int s = 0 ; for ( int i = 0 ; i < p[v].size() ; i++ ) if ( p[v][i] != u && vist[p[v][i]] == id ) { s++ ; } if ( p[u].size() + p[v].size() - s < h + t + 2 ) return false ; return true ; } void output( int u , int v ) { int i , j , s ; id++ ; for ( i = 0 ; i < p[v].size() ; i++ ) { if ( p[v][i] != u ) { vist[p[v][i]] = id ; } } j = 0 ; memset( mark , false , sizeof( mark )) ; for ( i = 0 , j = 0 ; i < p[u].size() ; i++ ) { if ( p[u][i] != v && vist[p[u][i]] == id ) { mark[p[u][i]] = true ; comm[j++] = p[u][i] ; } } printf ( "YES\n%d %d\n" , u , v ) ; for ( i = 0 , s = 0 ; i < p[u].size() ; i++ ) if ( p[u][i] != v && mark[p[u][i]] == false ) { printf ( "%d" , p[u][i] ); s++ ; if ( s == h ) { printf ( "\n" ) ;break ; } else printf ( " " ); } j = 0 ; while ( s < h ) { printf ( "%d" , comm[j++] ); s++ ; if ( s == h ) { printf ( "\n" ) ;break; } else printf ( " " ); } s = 0 ; for ( i = 0 ; i < p[v].size() ; i++ ) { if ( p[v][i] != u && mark[p[v][i]] == false ) { printf ( "%d" , p[v][i] ); s++ ; if ( s == t ) { printf ( "\n" ) ;break; } else printf ( " " ); } } while ( s < t ) { printf ( "%d" , comm[j++] ); s++ ; if ( s == t ) { printf ( "\n" ) ;break; } else printf ( " " ); } } int main() { int i , j , x , y ; while ( scanf ( "%d%d%d%d" , &n , &m , &h , &t ) != EOF ) { for ( i = 0 ; i <= n ; i++ ) { p[i].clear(); } for ( i = 1 ; i <= m ; i++ ) { scanf ( "%d%d" , &x , &y ) ; p[x].push_back( y ); p[y].push_back( x ) ; } id = 0 ; int flag = 0 ; for ( i = 1 ; i <= n && !flag ; i++ ) { for ( j = p[i].size() - 1 ; j >= 0 ; j-- ) if ( jud ( i , p[i][j] )) { output( i , p[i][j] ); flag = 1 ; break ; } } if ( !flag ) { printf ( "NO\n" ) ; } } return 0 ; }