A:Design Tutorial: Learn from Math
奇数输出9,n-9;偶数输出4,n-4。
B:Design Tutorial: Learn from Life
排个序,ans = 第1大+第K+1大+第2K+1大+...,可以保证这样一定是最优的,因为下一趟的最大时间被尽量减小了。
C:Design Tutorial: Make It Nondeterministic
对所有编号为i的人两个节点i<<1,i<<1|1,分别代表名和姓。
将题目要求的序列读取到num[]数组里。
如果num[i-1]的名字典序小于num[i]的名,则建边(num[i-1]<< 1,num[i]<<1)。
其他边同理。
最后把序列第一个人的名和姓放进队列bfs。
如果bfs完最后一个人的名或者姓被遍历到,则说明存在一种选择方案使得序列合法,输出YES。
否则输出NO。
D:Design Tutorial: Inverse the Problem
这题我考虑的简单了。。。比赛的时候用了n*n*logn+n*n*logn*logn的算法过的。。。
我是这么想的:首先求一次最小生成树(我用的kruskal,但prim效果更好,因为是完全图),然后以最小生成树的树边建图。接下来我是用树链剖分来做的,暴力判断给的矩阵中的值是否和树链剖分得到的值相同。。。。。。然后只需要注意矩阵的对称以及自己到自己应该是0,其他就没什么了。。。过是没问题的。
现在我讲一下这道题的正确姿势,赛后才发现可以这么做。。
首先还是求最小生成树,用prim,这部分复杂度O(n*n)。
用最小生成树得到的树边建树。
然后枚举以每个点作为根,dfs得到这个点到其余所有点的距离,然后和给的矩阵比较看是否相同。
每次dfs复杂度O(n),总复杂度也是O(n*n)。
如果dfs得到的距离和矩阵给的完全符合则输出YES,否则NO。
算法的总复杂度O(n*n)。
由于实在是懒得写第二个算法的程序了,有看明白的可以自己实现下,反正我是不想动了。。
就贴一下我树链剖分的代码吧。。
代码如下:
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std ; typedef long long LL ; #define rep( i , a , b ) for ( int i = a ; i < b ; ++ i ) #define For( i , a , b ) for ( int i = a ; i <= b ; ++ i ) #define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i ) #define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next ) #define clr( a , x ) memset ( a , x , sizeof a ) #define cpy( a , x ) memcpy ( a , x , sizeof a ) #define ls ( o << 1 ) #define rs ( o << 1 | 1 ) #define lson ls , l , m #define rson rs , m + 1 , r #define root 1 , 1 , n #define mid ( ( l + r ) >> 1 ) #define rt o , l , r const int MAXN = 3005 ; const int MAXE = 10005 ; const int MAXM = 2000005 ; struct Line { int u , v , val ; int flag ; Line () {} Line ( int u , int v , int val ) : u ( u ) , v ( v ) , val ( val ) , flag ( 0 ) {} bool operator < ( const Line& a ) const { return val < a.val ; } } line[MAXM] ; struct Edge { int v ; Edge* next ; } E[MAXE] , *H[MAXN] , *edge ; LL sum[MAXN << 2] ; int G[MAXN][MAXN] ; int siz[MAXN] ; int pos[MAXN] ; int pre[MAXN] ; int top[MAXN] ; int son[MAXN] ; int val[MAXN] ; int dep[MAXN] ; int tree_idx ; int p[MAXN] ; int cnt ; int n ; void clear () { cnt = 0 ; edge = E ; clr ( H , 0 ) ; tree_idx = 0 ; siz[0] = 0 ; rep ( i , 0 , MAXN ) p[i] = i ; } void addedge ( int u , int v ) { edge -> v = v ; edge -> next = H[u] ; H[u] = edge ++ ; } int find ( int x ) { return p[x] == x ? x : ( p[x] = find ( p[x] ) ) ; } bool kruskal () { int count = 1 ; sort ( line , line + cnt ) ; rep ( i , 0 , cnt ) { int x = find ( line[i].u ) ; int y = find ( line[i].v ) ; if ( x != y ) { p[x] = y ; line[i].flag = 1 ; addedge ( line[i].u , line[i].v ) ; addedge ( line[i].v , line[i].u ) ; if ( ++ count == n ) return 1 ; } } return 0 ; } void dfs ( int u ) { siz[u] = 1 ; son[u] = 0 ; travel ( e , H , u ) { int v = e -> v ; if ( v != pre[u] ) { pre[v] = u ; dep[v] = dep[u] + 1 ; dfs ( v ) ; siz[u] += siz[v] ; if ( siz[v] > siz[son[u]] ) son[u] = v ; } } } void rewrite ( int u , int top_element ) { top[u] = top_element ; pos[u] = ++ tree_idx ; if ( son[u] ) rewrite ( son[u] , top_element ) ; travel ( e , H , u ) { int v = e -> v ; if ( v != pre[u] && v != son[u] ) rewrite ( v , v ) ; } } void pushup ( int o ) { sum[o] = sum[ls] + sum[rs] ; } void build ( int o , int l , int r ) { if ( l == r ) { sum[o] = val[l] ; return ; } int m = mid ; build ( lson ) ; build ( rson ) ; pushup ( o ) ; } LL sub_query ( int L , int R , int o , int l , int r ) { if ( L <= l && r <= R ) return sum[o] ; int m = mid ; if ( R <= m ) return sub_query ( L , R , lson ) ; if ( m < L ) return sub_query ( L , R , rson ) ; return sub_query ( L , R , lson ) + sub_query ( L , R , rson ) ; } LL query ( int x , int y ) { LL ans = 0 ; while ( top[x] != top[y] ) { if ( dep[top[x]] < dep[top[y]] ) swap ( x , y ) ; ans += sub_query ( pos[top[x]] , pos[x] , root ) ; x = pre[top[x]] ; } if ( x == y ) return ans ; if ( dep[x] > dep[y] ) swap ( x , y ) ; ans += sub_query ( pos[x] + 1 , pos[y] , root ) ; return ans ; } void solve () { clear () ; bool ok = 1 ; For ( i , 1 , n ) { For ( j , 1 , n ) { scanf ( "%d" , &G[i][j] ) ; if ( i == j && G[i][j] ) ok = 0 ; if ( i > j && G[i][j] != G[j][i] ) ok = 0 ; if ( !ok ) continue ; if ( i < j && G[i][j] ) line[cnt ++] = Line ( i , j , G[i][j] ) ; } } if ( !ok ) { printf ( "NO\n" ) ; return ; } if ( n == 1 ) { printf ( "YES\n" ) ; return ; } if ( !kruskal () ) { printf ( "NO\n" ) ; return ; } dfs ( 1 ) ; rewrite ( 1 , 1 ) ; rep ( i , 0 , cnt ) { if ( line[i].flag ) { int x = line[i].u ; int y = line[i].v ; if ( dep[x] > dep[y] ) val[pos[x]] = line[i].val ; else val[pos[y]] = line[i].val ; } } build ( root ) ; For ( i , 1 , n ) For ( j , i + 1 , n ) { if ( G[i][j] != query ( i , j ) ) ok = 0 ; if ( ok == 0 ) break ; } if ( ok ) printf ( "YES\n" ) ; else printf ( "NO\n" ) ; } int main () { while ( ~scanf ( "%d" , &n ) ) solve () ; return 0 ; }