序列

• description
• solution
• code

description

題目描述

長(zhǎng)度為$n$的序列，初始全為$0$，每次可以選擇?個(gè)數(shù)$a_i(1\le i\le l)$，然后選擇連續(xù)$a_i$個(gè)元素異或上$1$

求最少的次數(shù)，使得對(duì)于所有$i(1\le i\le k)$滿足第$i$個(gè)位置是$1$，其他的位置都是$0$

輸入格式

第?行三個(gè)數(shù)$n,m,k$

第二行$k$個(gè)數(shù)分別表示$x_1,x_2,...,x_k$

第三行$l$個(gè)數(shù)分別表示$a_1,a_2,...a_l$

輸出格式

一個(gè)數(shù)表示答案，若不能達(dá)到輸出-1

樣例

10 2 3 1 2 6 10 4 2

數(shù)據(jù)范圍

$n\le 10000,k\le 10,l\le 100$

solution

異或常見有兩種處理

• 0-1異或類，權(quán)值只有0，1

  顯然某位異或偶數(shù)次相當(dāng)于沒操作，這就可以轉(zhuǎn)化成差分

• 普通異或類

  按二進(jìn)制拆位做，每位答案是獨(dú)立的

此題就是差分做法

e.g. 目標(biāo)結(jié)果：1 0 0 1 1 0，相鄰兩位權(quán)值不同就要差分出來

操作一段長(zhǎng)為$a_i$的段，就相當(dāng)于在$pos,pos+a_i$兩個(gè)位置異或$1$

本題$k$范圍極小，差分出來最多也就$20$個(gè)位置

考慮從最后的狀態(tài)用最少操作數(shù)變成全$0$的初始狀態(tài)

這相當(dāng)于一張$n+1$點(diǎn)姻緣圖，在差分$2k$個(gè)位置上有人，位置相差為$a_i$的點(diǎn)對(duì)間有無向邊，人沿著邊移動(dòng)，兩人相遇牽手成功離開，求最少走過的邊數(shù)，使得每個(gè)人都能找到自己的心動(dòng)嘉賓

用bfs處理出，每個(gè)人到達(dá)所有點(diǎn)走過的最少邊數(shù)，到不了就置為inf

總?cè)藬?shù)不多，可以狀壓dp枚舉每次是哪兩個(gè)人牽手成功，轉(zhuǎn)移即可

code

#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define inf 0x3f3f3f3f queue < pair < int, int > > q; int n, k, l, cnt; int dis[22][100002]; int x[100002], a[105], c[25]; int dp[1 << 22];int dfs( int s ) {if( ! s ) return 0;if( dp[s] ^ inf ) return dp[s];int &ans = dp[s], x = __builtin_ctz( s );for( int y = cnt - 1;y > x;y -- )if( 1 << y & s ) {int t = dfs( s ^ ( 1 << y ) ^ ( 1 << x ) );ans = min( ans, t + dis[x][c[y]] );}return ans; }int main() {scanf( "%d %d %d", &n, &k, &l );for( int i = 1, pos;i <= k;i ++ ) {scanf( "%d", &pos );x[-- pos] = 1;}for( int i = 1;i <= l;i ++ )scanf( "%d", &a[i] );if( x[0] ) c[cnt ++] = 0;for( int i = 1;i <= n;i ++ )if( x[i] ^ x[i - 1] ) c[cnt ++] = i;if( cnt & 1 ) return ! printf( "-1" );memset( dp, 0x3f, sizeof( dp ) );memset( dis, 0x3f, sizeof( dis ) );for( int i = 0, j, d, pos;i < cnt;i ++ ) {dis[i][c[i]] = 0;q.push( make_pair( 0, c[i] ) );while( ! q.empty() ) {d = q.front().first, pos = q.front().second; q.pop();for( k = 1;k <= l;k ++ ) {j = pos + a[k];if( j <= n and dis[i][j] == inf )dis[i][j] = d + 1, q.push( make_pair( d + 1, j ) );j = pos - a[k];if( j >= 0 and dis[i][j] == inf )dis[i][j] = d + 1, q.push( make_pair( d + 1, j ) );}}}int ans = dfs( ( 1 << cnt ) - 1 );printf( "%d\n", ans == inf ? -1 : ans );return 0; }

總結(jié)

以上是生活随笔為你收集整理的[2021-09-09 T3] 序列/luogu P3943 星空（异或差分+bfs最短路+状压dp）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。