深圳哪些建设公司招聘,seo查询网址,扬州seo推广,python编程快速上手序列descriptionsolutioncodedescription
题目描述
长度为nnn的序列#xff0c;初始全为000#xff0c;每次可以选择⼀个数ai(1≤i≤l)a_i(1\le i\le l)ai(1≤i≤l)#xff0c;然后选择连续aia_iai个元素异或上111
求最少的次数#xff0c;使得对于所有i(1≤i≤k)i(…
序列descriptionsolutioncodedescription
题目描述
长度为nnn的序列初始全为000每次可以选择⼀个数ai(1≤i≤l)a_i(1\le i\le l)ai(1≤i≤l)然后选择连续aia_iai个元素异或上111
求最少的次数使得对于所有i(1≤i≤k)i(1\le i\le k)i(1≤i≤k)满足第iii个位置是111其他的位置都是000
输入格式
第⼀行三个数n,m,kn,m,kn,m,k
第二行kkk个数分别表示x1,x2,...,xkx_1,x_2,...,x_kx1,x2,...,xk
第三行lll个数分别表示a1,a2,...ala_1,a_2,...a_la1,a2,...al
输出格式
一个数表示答案若不能达到输出-1
样例
10 2 3
1 2
6 10 42数据范围
n≤10000,k≤10,l≤100n\le 10000,k\le 10,l\le 100n≤10000,k≤10,l≤100
solution 异或常见有两种处理 0-1异或类权值只有01 显然某位异或偶数次相当于没操作这就可以转化成差分 普通异或类 按二进制拆位做每位答案是独立的 此题就是差分做法
e.g. 目标结果1 0 0 1 1 0相邻两位权值不同就要差分出来
操作一段长为aia_iai的段就相当于在pos,posaipos,posa_ipos,posai两个位置异或111
本题kkk范围极小差分出来最多也就202020个位置
考虑从最后的状态用最少操作数变成全000的初始状态
这相当于一张n1n1n1点姻缘图在差分2k2k2k个位置上有人位置相差为aia_iai的点对间有无向边人沿着边移动两人相遇牵手成功离开求最少走过的边数使得每个人都能找到自己的心动嘉宾
用bfs处理出每个人到达所有点走过的最少边数到不了就置为inf
总人数不多可以状压dp枚举每次是哪两个人牵手成功转移即可
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;
}
