网站下载系统,正规网页设计开发,百度竞价推广托管,页面设计素材库题目链接
CF方向 Luogu方向
题目解法
看到区间异或#xff0c;一个经典的套路是做差分#xff0c;我们即在 l l l 处异或一次#xff0c;在 r 1 r1 r1 处异或一次#xff0c;然后前缀和起来 于是我们可以将问题转化成#xff1a;有一个序列初始全 0 0 0#xff0c…题目链接
CF方向 Luogu方向
题目解法
看到区间异或一个经典的套路是做差分我们即在 l l l 处异或一次在 r 1 r1 r1 处异或一次然后前缀和起来 于是我们可以将问题转化成有一个序列初始全 0 0 0每次可以把相隔 a i a_i ai 的数都 ⊕ 1 \oplus 1 ⊕1求最少将其变成一个状态的步数 考虑 k k k 的范围很小所以为 1 1 1 的地方一共只有 2 k 2k 2k 个 这里有一个非常重要的 t r i c k trick trick在异或操作中如果需要把 x , y x,y x,y 同时异或 1 1 1其他不变每次可以同时修改相隔 a i a_i ai 的位置的异或值那么这个问题等价于建出图来从 x x x 到 y y y 的最短路 然后发现直接状压跑最短路即可时间复杂度 O ( 2 k k 2 ) O(2^kk^2) O(2kk2) 不难优化成 O ( 2 k k ) O(2^kk) O(2kk)但我直接 998 m s 998ms 998ms 用 O ( 2 k k 2 ) O(2^kk^2) O(2kk2) 的做法艹过去了就懒得改了 O ( 2 k k 2 ) O(2^kk^2) O(2kk2) 的代码
#include bits/stdc.h
using namespace std;
const int N10100,M2000100;
int n,m,k,a[110],x[30],dis[N];
int f[(120)100],D[30][30];
int e[M],ne[M],h[N],idx;
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
queueint que;
void bfs(int S){memset(dis,0x3f,sizeof(dis));que.push(S),dis[S]0;while(!que.empty()){int uque.front();que.pop();for(int ih[u];~i;ine[i]) if(dis[u]1dis[e[i]])dis[e[i]]dis[u]1,que.push(e[i]);}
}
void add(int x,int y){ e[idx]y,ne[idx]h[x],h[x]idx;}
int main(){nread(),kread(),mread();for(int i0;ik;i) x[i]read();for(int i1;im;i) a[i]read();for(int i0;ik;i) x[ik]x[i]1;memset(h,-1,sizeof(h));for(int i1;im;i)for(int j1;jn-a[i]1;j)add(j,ja[i]),add(ja[i],j);for(int i0;ik1;i){bfs(x[i]);for(int j0;jk1;j) D[i][j]dis[x[j]];}memset(f,0x3f,sizeof(f));f[0]0;for(int S0;S1(k1);S)for(int i0;ik1;i) if(Si1)for(int j0;jk1;j) if(Sj1) if(i!j)f[S]min(f[S],f[S^(1i)^(1j)]D[i][j]);printf(%d\n,f[(1(k1))-1]1e9?-1:f[(1(k1))-1]);fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
