NOI 2021 day1

• 輕重邊
• • description
  • solution
  • code
• 路徑交點
• • description
  • solution
  • code

輕重邊

description

solution

• case=1~6

  把父親和兒子的邊轉化為儲存在兒子上的點

  建樹，暴力爬$lca$，暴力修改，$O(n^2)$

• case=A

  對于一條鏈的情況，每次修改重邊就是一段區間，輕邊只有兩個端點相連的邊

  同樣的邊化點，線性用線段樹區間/單點修改，區間查詢

• case=B

  第二類操作詢問只有一條邊，考慮這條邊怎么才可能是重邊，顯然就是兩個點最后被經過的時間戳要一樣

  樹鏈剖分打時間戳

• case=1~20

  正解其實就在case=B基礎上，的確一條邊如果是輕邊當且僅當該邊的兩個端點所打時間戳不同

  樹鏈剖分維護數顏色段的個數（輕邊的數量），重邊數量減一下就可以了

  最原始局面全都是輕邊，所以初始化建樹時就要給每個點打一個不同的時間戳

蒟蒻只想到所有到case=B的前$70\%$的部分分，實在沒想到顏色段個數

code

#include <cstdio> #include <vector> #include <iostream> using namespace std; #define maxn 100005 #define lson num << 1 #define rson num << 1 | 1 struct node {int cnt, l, r, tag; }t[maxn << 2]; vector < int > G[maxn]; int T, n, m, cnt; int dep[maxn], son[maxn], top[maxn], dfn[maxn], f[maxn], siz[maxn];void dfs1( int u, int fa ) {dep[u] = dep[fa] + 1, f[u] = fa, siz[u] = 1;for( auto v : G[u] ) {if( v == fa ) continue;else dfs1( v, u );siz[u] += siz[v];if( siz[v] > siz[son[u]] )son[u] = v; } }void dfs2( int u, int tt ) {top[u] = tt, dfn[u] = ++ cnt;if( son[u] ) dfs2( son[u], tt );else return;for( auto v : G[u] ) {if( v == f[u] || v == son[u] ) continue;else dfs2( v, v );} }void pushdown( int num ) {if( ! t[num].tag ) return;t[lson].l = t[lson].r = t[lson].tag = t[num].tag;t[rson].l = t[rson].r = t[rson].tag = t[num].tag;t[lson].cnt = t[rson].cnt = 1;t[num].tag = 0;return; }void build( int num, int l, int r ) {if( l == r ) {t[num].cnt = 1, t[num].l = t[num].r = l;return;}int mid = ( l + r ) >> 1;build( lson, l, mid );build( rson, mid + 1, r );t[num].l = t[lson].l, t[num].r = t[rson].r;t[num].cnt = t[lson].cnt + t[rson].cnt;t[num].tag = 0; }void modify( int num, int l, int r, int L, int R, int id ) {if( R < l || r < L ) return;if( L <= l && r <= R ) {t[num].cnt = 1, t[num].l = t[num].r = t[num].tag = id;return;}pushdown( num );int mid = ( l + r ) >> 1;modify( lson, l, mid, L, R, id );modify( rson, mid + 1, r, L, R, id );t[num].l = t[lson].l, t[num].r = t[rson].r;t[num].cnt = t[lson].cnt + t[rson].cnt - ( t[lson].r == t[rson].l ); }void modify( int x, int y, int id ) {while( top[x] ^ top[y] ) {if( dep[top[x]] < dep[top[y]] ) swap( x, y );modify( 1, 1, n, dfn[top[x]], dfn[x], id );x = f[top[x]];}if( dep[x] > dep[y] ) swap( x, y );modify( 1, 1, n, dfn[x], dfn[y], id ); }node query( int num, int l, int r, int L, int R ) {if( L <= l && r <= R ) return t[num];int mid = ( l + r ) >> 1;pushdown( num );if( R <= mid ) return query( lson, l, mid, L, R );else if( mid < L ) return query( rson, mid + 1, r, L, R );else {node ans1 = query( lson, l, mid, L, R );node ans2 = query( rson, mid + 1, r, L, R );node ans;ans.l = ans1.l, ans.r = ans2.r;ans.cnt = ans1.cnt + ans2.cnt - ( ans1.r == ans2.l );return ans;} }int query( int x, int y ) {node t;int ans = dep[x] + dep[y], tot = 0;int last_x = -1, last_y = -1;while( top[x] ^ top[y] ) {if( dep[top[x]] >= dep[top[y]] ) {t = query( 1, 1, n, dfn[top[x]], dfn[x] );tot += t.cnt;if( last_x == t.r ) tot --;last_x = t.l;x = f[top[x]];}else {t = query( 1, 1, n, dfn[top[y]], dfn[y] );tot += t.cnt;if( last_y == t.r ) tot --;last_y = t.l;y = f[top[y]];}}if( dep[x] > dep[y] ) swap( x, y ), swap( last_x, last_y );ans -= ( dep[x] << 1 );t = query( 1, 1, n, dfn[x], dfn[y] );tot += t.cnt;if( t.l == last_x ) tot --;if( t.r == last_y ) tot --;return ans - tot + 1; }int main() {scanf( "%d", &T );while( T -- ) {scanf( "%d %d", &n, &m );cnt = 0;for( int i = 1;i <= n;i ++ )G[i].clear(), son[i] = 0;for( int i = 1, u, v;i < n;i ++ ) {scanf( "%d %d", &u, &v );G[u].push_back( v );G[v].push_back( u );}dfs1( 1, 0 );dfs2( 1, 1 );build( 1, 1, n );for( int i = 1, opt, a, b;i <= m;i ++ ) {scanf( "%d %d %d", &opt, &a, &b );if( opt & 1 ) modify( a, b, i + n );else printf( "%d\n", query( a, b ) );}}return 0; }

路徑交點

description

solution

• 圖中的每個頂點至多出現在一條路徑中是對本題正解算法的條件限制/保證

• $(P_j?Q_j)\times (P_{j+1}?Q_{j+1})<0$

  當固定第$j$層的枚舉順序時，發現這個條件限制的本質是逆序對

• 詢問有偶數個交點的路徑方案數比有奇數個交點的路徑方案數多多少個

  一種方案的貢獻顯然是$(?1{)}^{cnt},cnt$表示這種方案下的逆序對個數

• 相鄰層給出的若干條有向邊，可以構建一個鄰接矩陣

• 綜上所有的信息都在暗示/匹配矩陣的行列式

  $|P|={\sum }_{j_1,j_2,...,j_n}(?1{)}^{\tau (j_1,j_2...j_n)}{a}_{1,j_1}...a_{n,j_n}$

  ${\sum }_{j_1,j_2,...,j_n}:j$的$n$級全排列求和，$\tau (j_1,j_2,...,j_n)$表示排列$j_1,...,j_n$的逆序對個數

• 知道二分圖的解決方法了，接下來要擴展成$k$層圖的計算

  binet-cauchy公式 $|AB|=|A||B|$

  所以只需要算出相鄰兩層的矩陣，然后矩陣乘法得到最后為$n_1\times n_1$的總矩陣

  最后通過高斯消元（上三角矩陣）計算主對角線的乘積就是矩陣的行列式，也是詢問的答案

code

#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define mod 998244353 #define int long long #define maxn 205 struct matrix {int n, m;int c[maxn][maxn];matrix() {n = m = 0;memset( c, 0, sizeof( c ) );}void clear() {for( int i = 1;i <= n;i ++ )for( int j = 1;j <= m;j ++ )c[i][j] = 0;}matrix operator * ( matrix &t ) const {matrix ans;ans.n = n, ans.m = t.m;for( int i = 1;i <= n;i ++ )for( int k = 1;k <= m;k ++ )if( c[i][k] )for( int j = 1;j <= t.m;j ++ )ans.c[i][j] = ( ans.c[i][j] + c[i][k] * t.c[k][j] ) % mod;return ans;} }last, now;int qkpow( int x, int y ) {int ans = 1;while( y ) {if( y & 1 ) ans = ans * x % mod;x = x * x % mod;y >>= 1;}return ans; }void gauss( int a[][maxn], int n ) {int ans = 1;for( int i = 1;i <= n;i ++ ) {int k = i;for( int j = i + 1;j <= n;j ++ )if( a[j][i] > a[k][i] ) k = j;if( i ^ k ) swap( a[i], a[k] ), ans *= -1;for( int j = i + 1;j <= n;j ++ ) {int t = a[j][i] * qkpow( a[i][i], mod - 2 ) % mod;for( int k = i;k <= n;k ++ )a[j][k] = ( a[j][k] - t * a[i][k] % mod + mod ) % mod;}}for( int i = 1;i <= n;i ++ )ans = ans * a[i][i] % mod;printf( "%lld\n", ( ans + mod ) % mod ); }int T, n; int vec[maxn], edge[maxn]; signed main() {scanf( "%lld", &T );while( T -- ) {scanf( "%lld", &n );for( int i = 1;i <= n;i ++ )scanf( "%lld", &vec[i] );for( int i = 1;i < n;i ++ )scanf( "%lld", &edge[i] );last.n = vec[1], last.m = vec[2], last.clear();for( int i = 1, u, v;i <= edge[1];i ++ ) {scanf( "%lld %lld", &u, &v );last.c[u][v] = 1;}for( int i = 2;i < n;i ++ ) {now.n = vec[i], now.m = vec[i + 1], now.clear();for( int j = 1, u, v;j <= edge[i];j ++ ) {scanf( "%lld %lld", &u, &v );now.c[u][v] = 1;}last = last * now;}gauss( last.c, vec[1] );}return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[NOI2021 day1]轻重边（树链剖分），路径交点（矩阵行列式）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。