[noi.ac省選模擬賽]第12場題解集合
題目
比賽介面。
T1
數據範圍明示直接\(O(n^2)\)計算，問題就在如何快速計算。
樹上路徑統計通常會用到差分方法。這裡有兩棵樹，因此我們可以做「差分套差分」，在 A 樹上對 B 的差分資訊進行差分。在修改的時候，我們就會在 A 上 4 個位置進行修改，每次修改會涉及 B 上 4 個位置的差分修改，因此總共會涉及 16 個差分資訊的修改。
回收標記的時候，我們可以先在 A 樹上進行 DFS ，回收好子樹內的差分資訊後，再進行一次 B 的回收，得到當前節點上 B 的真實資訊。
時間是\(O(n^2+q\log_2n)\)。
#include <cmath>
#include <cstdio>
typedef long long LL;
const int MAXN = 1e4 + 5, MAXLOG = 15;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
struct Tree
{
struct edge
{
int to, nxt;
}Graph[MAXN << 1];
int f[MAXN][MAXLOG];
int head[MAXN], dep[MAXN], seq[MAXN];
int n, ID, lg2, cnt;
void addEdge( const int from, const int to )
{
Graph[++ cnt].to = to, Graph[cnt].nxt = head[from];
head[from] = cnt;
}
void DFS( const int u, const int fa )
{
f[u][0] = fa, seq[++ ID] = u, dep[u] = dep[fa] + 1;
for( int i = head[u], v ; i ; i = Graph[i].nxt )
if( ( v = Graph[i].to ) ^ fa )
DFS( v, u );
}
void init()
{
read( n );
for( int i = 1, a, b ; i < n ; i ++ )
read( a ), read( b ), addEdge( a, b ), addEdge( b, a );
DFS( 1, 0 );
lg2 = log2( n );
for( int j = 1 ; j <= lg2 ; j ++ )
for( int i = 1 ; i <= n ; i ++ )
f[i][j] = f[f[i][j - 1]][j - 1];
}
void balance( int &u, const int stp ) const
{
for( int i = 0 ; ( 1 << i ) <= stp ; i ++ )
if( stp & ( 1 << i ) )
u = f[u][i];
}
int LCA( int u, int v ) const
{
if( dep[u] > dep[v] ) balance( u, dep[u] - dep[v] );
if( dep[v] > dep[u] ) balance( v, dep[v] - dep[u] );
if( u == v ) return u;
for( int i = lg2 ; ~ i ; i -- ) if( f[u][i] ^ f[v][i] ) u = f[u][i], v = f[v][i];
return f[u][0];
}
int fa( const int u ) const { return f[u][0]; }
};
Tree A, B;
int dif[MAXN][MAXN];
LL ans;
void change( int *d, const int u, const int v, const int lca, const int c )
{
d[u] += c, d[v] += c, d[lca] -= c, d[B.fa( lca )] -= c;
}
void recovery( const int u, const int fa )
{
for( int i = A.head[u], v ; i ; i = A.Graph[i].nxt )
if( ( v = A.Graph[i].to ) ^ fa )
recovery( v, u );
for( int i = 1 ; i <= B.n ; i ++ ) dif[fa][i] += dif[u][i];
for( int i = B.n ; i ; i -- )
{
int cur = B.seq[i];
ans ^= 1ll * u * cur * dif[u][cur];
dif[u][B.fa( cur )] += dif[u][cur];
}
}
int main()
{
int Q, a1, a2, b1, b2, c, lcaa, lcab;
A.init(), B.init(), read( Q );
while( Q -- )
{
read( a1 ), read( a2 ), read( b1 ), read( b2 ), read( c );
lcaa = A.LCA( a1, a2 ), lcab = B.LCA( b1, b2 );
change( dif[a1], b1, b2, lcab, c );
change( dif[a2], b1, b2, lcab, c );
change( dif[lcaa], b1, b2, lcab, -c );
change( dif[A.fa( lcaa )], b1, b2, lcab, -c );
}
recovery( 1, 0 );
write( ans ), putchar( '\n' );
return 0;
}
T2
神奇的 DP 配合優化，放個官方題解吧：
若每種段只出現一次，可以注意到我們每塗完一種顏色，就將整個序列分為兩段，所以，我們不妨令\(f_{i,j}\)表示塗完第\(i\)種顏色到第\(j\)種顏色，最多可以塗多少。那麼我們有\(dp_{l,r} = max_{l\leq k \leq r}dp_{l,k−1} + dp_{k+1,r} + cost_{i,j}\)，注意到該式雖然與四邊形不等式稍有區別，但通過一樣的不等式分析仍然可以得到\(dp_{i,j} + dp_{i+1,j+1} \geq dp_{i,j+1} + dp_{i + 1, j}\),故上式可以直接用四邊形不等式優化。 一個有意思的現象是，上述決策點似乎只會出現在\(l\)或\(r\),但我並沒有想出有效的證明方法。
T3
字元串簡單題，考慮容斥。總方案很好計算，然後考慮不相交字元串的方案數。枚舉分界點，然後計算左邊和右邊的迴文串數量即可。
所以我為什麼會想到奇怪的 slink 方法呀……它還不卡我……
所以就貼了 slink 的程式碼。
#include <cstdio>
#include <cstring>
typedef long long LL;
const int MAXN = 2e6 + 5;
const int mod = 998244353, inv2 = 499122177;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
int BIT[MAXN], g[MAXN];
int ed[MAXN], slink[MAXN], dif[MAXN];
int ch[MAXN][26], len[MAXN], fa[MAXN], dep[MAXN];
int N, tot, lst;
char S[MAXN];
void add( int &x, const int v ) { x = ( x + v >= mod ? x + v - mod : x + v ); }
int sub( const int x, const int v ) { return ( x < v ? x - v + mod : x - v ); }
LL mul( const int x, const LL v ) { LL tmp = x * v; return tmp < mod ? tmp : tmp % mod; }
void up( int &x ) { x += x & ( -x ); }
void down( int &x ) { x -= x & ( -x ); }
void update( int x, const int v ) { for( ; x <= N ; up( x ) ) add( BIT[x], v ); }
int getSum( int x ) { int ret = 0; for( ; x ; down( x ) ) add( ret, BIT[x] ); return ret; }
int query( const int l, const int r ) { return sub( getSum( r ), getSum( l - 1 ) ); }
void build()
{
int x;
N = strlen( S + 1 );
len[fa[0] = ++ tot] = -1;
for( int i = 1 ; i <= N ; i ++ )
{
x = S[i] - 'a';
while( S[i] ^ S[i - len[lst] - 1] ) lst = fa[lst];
if( ! ch[lst][x] )
{
int cur = ++ tot, p = fa[lst];
while( S[i] ^ S[i - len[p] - 1] ) p = fa[p];
len[cur] = len[lst] + 2, fa[cur] = ch[p][x], ch[lst][x] = cur;
}
ed[i] = lst = ch[lst][x];
}
}
int main()
{
int ans = 0;
scanf( "%s", S + 1 ), build();
for( int i = 2 ; i <= tot ; i ++ )
{
dep[i] = dep[fa[i]] + 1, dif[i] = len[i] - len[fa[i]];
if( dif[i] ^ dif[fa[i]] ) slink[i] = fa[i];
else slink[i] = slink[fa[i]];
}
for( int i = 1 ; i <= N ; i ++ )
{
for( int p = ed[i] ; p ; p = slink[p] )
{
g[p] = query( i - len[slink[p]] - dif[p] + 1, i );
if( slink[p] ^ fa[p] )
{
add( g[p], g[fa[p]] );
add( g[p], mul( ( dep[p] - dep[slink[p]] - 1 ), query( i - dif[p], i ) ) );
}
add( ans, g[p] );
}
add( ans, mul( mul( dep[ed[i]], dep[ed[i]] - 1 ), inv2 ) );
update( i, dep[ed[i]] );
}
write( ans ), putchar( '\n' );
return 0;
}
小結
對於簡單題和基礎的技巧都還不太熟練，要多加運用。
