文章目錄

• T1：[GXOI/GZOI2019]舊詞
• • solution
  • code
• T2：GRE Words Once More!
• • solution
  • code
• T3：Problem B. Harvest of Apples
• • solution
  • code

T1：[GXOI/GZOI2019]舊詞

點擊查看

solution

考慮$k=1$的情況
由于$dep[lca(x,y)]=|\{z,z$是$x$和$y$的祖先$\}|$
按$x$從小到大離線處理詢問，每當$x$向右一個時，將$x$的祖先權值都$+1$
然后詢問就相當于求$y$的所有祖先的權值之和
非常簡單的板樹鏈剖分$+$線段樹

如果$k>1$，那么權值不是加$1$，而是對于深度為$i$的點，權值加上$i^k?(i?1{)}^k$
本質是樹上差分，發現這樣后從根到$x$的距離剛好是$dep[x{]}^k$
同樣用線段樹維護

code

#include <cstdio> #include <vector> #include <algorithm> using namespace std; #define int long long #define maxn 50005 #define mod 998244353 struct node {int x, y, id; }q[maxn]; vector < int > G[maxn]; int n, Q, k, cnt; int ans[maxn], mi[maxn]; int son[maxn], siz[maxn], top[maxn], dep[maxn], id[maxn], f[maxn], rnk[maxn]; int val[maxn << 2], t[maxn << 2], flag[maxn << 2];bool cmp( node s, node t ) {return s.x < t.x; }int qkpow( int x, int y ) {int res = 1;while( y ) {if( y & 1 ) res = res * x % mod;x = x * x % mod;y >>= 1;}return res; }void dfs1( int u ) {siz[u] = 1, dep[u] = dep[f[u]] + 1;for( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i];dfs1( v );siz[u] += siz[v];if( ! son[u] || siz[v] > siz[son[u]] )son[u] = v;} }void dfs2( int u, int t ) {top[u] = t, id[u] = ++ cnt, rnk[cnt] = u;if( ! son[u] ) return;dfs2( son[u], t );for( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i];if( v == son[u] ) continue;dfs2( v, v );} }void pushdown( int num ) {if( ! flag[num] ) return;t[num << 1] = ( t[num << 1] + flag[num] * val[num << 1] % mod ) % mod;t[num << 1 | 1] = ( t[num << 1 | 1] + flag[num] * val[num << 1 | 1] % mod ) % mod; flag[num << 1] += flag[num];flag[num << 1 | 1] += flag[num];flag[num] = 0; }void modify( int num, int l, int r, int L, int R ) {if( L <= l && r <= R ) {t[num] = ( t[num] + val[num] ) % mod;flag[num] ++;return;}pushdown( num );int mid = ( l + r ) >> 1;if( L <= mid ) modify( num << 1, l, mid, L, R );if( mid < R ) modify( num << 1 | 1, mid + 1, r, L, R );t[num] = ( t[num << 1] + t[num << 1 | 1] ) % mod; }void change( int x ) {while( top[x] ) {modify( 1, 1, cnt, id[top[x]], id[x] );x = f[top[x]];} }int query( int num, int l, int r, int L, int R ) {if( R < l || r < L ) return 0;if( L <= l && r <= R ) return t[num];pushdown( num );int mid = ( l + r ) >> 1;return ( query( num << 1, l, mid, L, R ) + query( num << 1 | 1, mid + 1, r, L, R ) ) % mod; }int solve( int x ) {int sum = 0;while( top[x] ) {sum = ( sum + query( 1, 1, cnt, id[top[x]], id[x] ) ) % mod;x = f[top[x]];}return sum; }void build( int num, int l, int r ) {if( l == r ) {val[num] = ( mi[dep[rnk[l]]] - mi[dep[rnk[l]] - 1] + mod ) % mod;return;}int mid = ( l + r ) >> 1;build( num << 1, l, mid ), build( num << 1 | 1, mid + 1, r );val[num] = ( val[num << 1] + val[num << 1 | 1] ) % mod; }signed main() {scanf( "%lld %lld %lld", &n, &Q, &k );for( int i = 1;i <= n;i ++ ) mi[i] = qkpow( i, k );for( int i = 2;i <= n;i ++ ) {scanf( "%lld", &f[i] );G[f[i]].push_back( i );}dfs1( 1 );dfs2( 1, 1 );build( 1, 1, cnt ); for( int i = 1;i <= Q;i ++ ) {scanf( "%lld %lld", &q[i].x, &q[i].y );q[i].id = i;}sort( q + 1, q + Q + 1, cmp );int last = 1;for( int i = 1;i <= Q;i ++ ) {while( last <= q[i].x )change( last ++ );ans[q[i].id] = solve( q[i].y );}for( int i = 1;i <= Q;i ++ )printf( "%lld\n", ans[i] );return 0; }

T2：GRE Words Once More!

點擊查看

solution

但這都不是我的做法，因為上面的口胡題解著實不是很會
所以我學習了網上的奇技淫巧
講解很詳細，不想重復了

code

#include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; #define maxn 100005 #define MAX 100000000 struct node {int v, c;node() {}node( int V, int C ) {v = V, c = C;}bool operator < ( node &t ) const {return c < t.c;} }; vector < node > G[maxn]; int T, n, m, Q, tot; int s[maxn], ans[MAX + 5], dep[maxn], pre[maxn], word[maxn];void dfs( int u, int depth ) {if( tot >= MAX ) return;if( ~ word[u] ) {for( int i = 1;i <= word[u];i ++ ) {if( tot >= MAX ) return;ans[++ tot] = ans[pre[u] + i] - dep[u] + depth;}return;}else {pre[u] = tot;dep[u] = depth;if( s[u] ) ans[++ tot] = depth;for( int i = 0;i < G[u].size();i ++ ) {int v = G[u][i].v;dfs( v, depth + 1 );}word[u] = tot - pre[u];} }int main() {scanf( "%d", &T );for( int Case = 1;Case <= T;Case ++ ) {scanf( "%d %d %d", &n, &m, &Q );for( int i = 1;i <= n;i ++ ) G[i].clear();memset( word, -1, sizeof( word ) );tot = 0;for( int i = 2;i <= n;i ++ )scanf( "%d", &s[i] );for( int i = 1, u, v, c;i <= m;i ++ ) {scanf( "%d %d %d", &u, &v, &c );G[u].push_back( node( v, c ) );}for( int i = 1;i <= n;i ++ )sort( G[i].begin(), G[i].end() );dfs( 1, 0 ); printf( "Case #%d:\n", Case );int k;while( Q -- ) {scanf( "%d", &k );if( k > tot ) printf( "-1\n" );else printf( "%d\n", ans[k] );}}return 0; }

T3：Problem B. Harvest of Apples

點擊查看

solution

一看就知道跟組合數掛鉤，考慮莫隊
$$ans=\sum _{i=0}^m{C}_n^i$$
只需要處理四種操作即可
$m++:ans+C_n^{m+1}$
$m??:ans?C_n^m$
$n++:ans=(ans<<1)?C_n^m$
$$\sum _{i=0}^m{C}_{n+1}^i=\sum _{i=0}^m(C_n^i+C_n^{i?1})=2?\sum _{i=0}^m{C}_n^i?C_n^m$$
$n??:ans=(ans+C_{n?1}^m)/2$

code

#include <cmath> #include <cstdio> #include <iostream> #include <algorithm> using namespace std; #define maxn 100000 #define int long long #define mod 1000000007 struct node {int n, m, id; }query[maxn + 5]; int T, sqt, result; int ans[maxn + 5], fac[maxn + 5], inv[maxn + 5];int qkpow( int x, int y ) {int res = 1;while( y ) {if( y & 1 ) res = res * x % mod;x = x * x % mod;y >>= 1;}return res; }bool cmp( node x, node y ) {return ( x.n / sqt == y.n / sqt ) ? x.m < y.m : x.n < y.n; }int C( int n, int m ) {return fac[n] * inv[m] % mod * inv[n - m] % mod; }signed main() {fac[0] = inv[0] = 1;for( int i = 1;i <= maxn;i ++ )fac[i] = fac[i - 1] * i % mod;inv[maxn] = qkpow( fac[maxn], mod - 2 ) % mod;for( int i = maxn - 1;i;i -- )inv[i] = inv[i + 1] * ( i + 1 ) % mod;scanf( "%lld", &T );for( int i = 1;i <= T;i ++ ) {scanf( "%lld %lld", &query[i].n, &query[i].m );query[i].id = i;sqt = max( sqt, ( int ) sqrt( query[i].n ) );}sort( query + 1, query + T + 1, cmp );int curn = 0, curm = -1;for( int i = 1;i <= T;i ++ ) {int n = query[i].n, m = query[i].m;while( n < curn ) result = ( result + C( -- curn, curm ) ) % mod * inv[2] % mod;while( curn < n )result = ( ( result << 1 ) - C( curn ++, curm ) + mod ) % mod;while( curm < m )result = ( result + C( curn, ++ curm ) ) % mod;while( m < curm )result = ( result - C( curn, curm -- ) + mod ) % mod;ans[query[i].id] = result;}for( int i = 1;i <= T;i ++ )printf( "%lld\n", ans[i] );return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[数据结构专训][GXOI/GZOI2019]旧词，[hdu5118]GRE Words Once More!，[hdu6333]Problem B. Harvest of Apples的全部內容，希望文章能夠幫你解決所遇到的問題。

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