【模拟8.11】星空（差分转化，状压DP，最短路）
2024-08-27 00:37:18
一道很好的题，综合很多知识点。
首先复习差分：
将原来的每个点a[i]转化为b[i]=a[i]^a[i+1]，（如果是求和形式就是b[i]=a[i+1]-a[i]）
我们发现这样的方便在于我们可以运用前缀和的形式，求出单点值，当然，差分一般支持区间修改
单点查询，同时我们发现异或也满足转化的性质，我们发现异或的区间修改，也可以化为单点修改
然后进行问题转换：在一个序列中按要求修改端点，问最少修改多少次区间全部为0
把原来的每个数转化为差分形式，注意要多加一个b[0]=b[0]^b[1],然后我们发现假设修改
a[1]-a[5]的区间，那么在差分中实际影响的是b[0],b[5]两个值。
同时有一条显然的性质，差分数组中的1是偶数个。
然后再次转化问题：
我们已经知道每种操作的长度（实际在差分数组中长度+1，自己思考）
那么我们可以给数与数连边，连边长度为一，当两个1相遇后，相当于反转，变为0
那么我们将问题转化为图论问题:在n个节点图中，每个节点最多m个边，求出两两最短距离，
然后两个1相遇后全为0，求变为1的最小贡献
然后跑最短路
最后我们发现k的值很小，可以转为状压DP的形式
总的复杂度nmk+（k^2)*（2^k）
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<string>
5 #include<map>
6 #include<vector>
7 #include<set>
8 #include<algorithm>
9 #include<cmath>
10 #include<queue>
11 #define MAXN 3000001
12 using namespace std;
13 int a[MAXN],sum[MAXN];
14 int c[MAXN];
15 int head[MAXN],tot;
16 struct node{int to,n;}e[2700000*2];
17 void add(int u,int v)
18 {
19 e[++tot].to=v;e[tot].n=head[u];head[u]=tot;
20 }
21 int n,k,m;
22 int vis[MAXN];
23 int dis[301][301];
24 int spfa_dis[MAXN];
25 int the_1[MAXN];
26 int belong[MAXN];
27 void spfa(int root)
28 {
29 queue<int>q;
30 memset(vis,0,sizeof(vis));
31 memset(spfa_dis,0x3f3f3f,sizeof(spfa_dis));
32 q.push(root);
33 spfa_dis[root]=0;
34 while(!q.empty())
35 {
36 int x=q.front();q.pop();vis[x]=0;
37 for(int i=head[x];i;i=e[i].n)
38 {
39 int to=e[i].to;
40 if(vis[to])continue;
41 if(spfa_dis[to]>spfa_dis[x]+1)
42 {
43 spfa_dis[to]=spfa_dis[x]+1;
44 if(vis[to]==0)
45 {
46 q.push(to);
47 vis[to]=1;
48 }
49 }
50 }
51 }
52 for(int i=1;i<=the_1[0];++i)
53 {
54 int ci=the_1[i];
55 dis[belong[root]][belong[ci]]=spfa_dis[ci];
56 dis[belong[ci]][belong[root]]=spfa_dis[ci];
57 //printf("dis[%d][%d]=%d\n",belong[root],belong[ci],spfa_dis[ci]);
58 }
59 }
60 void init()
61 {
62 for(int i=0;i<=n;++i)//sum[i]=a[i]^a[i+1]
63 {
64 for(int j=1;j<=m;++j)
65 {
66 int me=i;
67 int l=i-c[j];
68 if(l>=0)
69 {
70 add(i,l);
71 //printf("add i=%d l=%d\n",i,l);
72 }
73 int r=i+c[j];
74 if(r<=n)
75 {
76 add(i,r);
77 //printf("add i=%d r=%d\n",i,r);
78 }
79 }
80 }
81 for(int i=0;i<=n;++i)
82 {
83 if(sum[i]==1)
84 spfa(i);
85 }
86 }
87 int fir=0,base[30];
88 int f[1<<18];
89 void DP()
90 {
91 for(int i=0;i<=n;++i)
92 {
93 fir|=sum[i]<<i;
94 }
95 base[0]=1;
96 for(int i=1;i<=n;++i)
97 {
98 base[i]=base[i-1]<<1;
99 }
100 memset(f,0x3f3f3f,sizeof(f));
101 f[base[the_1[0]]-1]=0;
102 for(int i=base[the_1[0]]-1;i>=0;--i)
103 {
104 int ci=i;
105 // printf("sr=%d\n",i);
106 for(int l=1;l<=the_1[0];++l)
107 {
108 if(((ci>>(l-1))&1)==1)
109 {
110 for(int r=l+1;r<=the_1[0];++r)
111 {
112 if(((ci>>(r-1))&1)==1)
113 {
114 f[i^base[l-1]^base[r-1]]=min(f[i^base[l-1]^base[r-1]],f[i]+dis[l][r]);
115 //printf("state=%d l=%d r=%d %d\n",f[i^base[l-1]^base[r-1]],l,r,dis[l][r]);
116 }
117 }
118 }
119 }
120 }
121 printf("%d\n",f[0]);
122 }
123 signed main()
124 {
125 scanf("%d%d%d",&n,&k,&m);
126 for(int i=1;i<=k;++i)
127 {
128 int x;
129 scanf("%d",&x);
130 a[x]=1;
131 }
132 for(int i=0;i<=n;++i)
133 {
134 sum[i]=a[i]^a[i+1];
135 if(sum[i]==1)
136 {
137 the_1[++the_1[0]]=i;
138 belong[i]=the_1[0];
139 }
140 //printf("sum[%d]=%d\n",i,sum[i]);
141 }
142 for(int i=1;i<=m;++i)
143 {
144 scanf("%d",&c[i]);
145 }
146 init();
147 DP();
148 }
最新文章
- C#分布式消息队列 EQueue 2.0 发布啦
- Linux ERRNO
- 深入理解javascript原型和闭包（7）——原型的灵活性
- 解决iOS9下隐藏App返回按钮文字导致的诡异闪屏问题
- git回滚到上一版本
- fiddler 挂载 JS文件
- codeforces343A A. Rational Resistance
- 高通、猎户机型Android典型bootloader分析
- 常用的 Android Studio 快捷键
- arm-elf-gcc汇编代码个人理解
- 「OC」 封装
- HYSBZ 2818 gcd
- haskell学习笔记<1>--基本语法
- 华为专家谈CMDB建设
- java集合介绍（List，Set，Map）
- win10 新建文件夹没有了
- 第五篇：数据备份、pymysql模块
- node path.resolve()
- Generative Model 与 Discriminative Model
- （实用）Linux下安装JDK和Eclipse