【USACO2009 NOV Gold】灯

Source and Judge

USACO2009 NOV Gold
Bzoj1770
Luogu2962

Problem

【Description】
贝希和她的闺密们在她们的牛棚中玩游戏。
但是天不从人愿,突然,牛棚的电源跳闸了,所有的灯都被关闭了。
贝希是一个很胆小的女生,在伸手不见拇指的无尽的黑暗中,她感到惊恐,痛苦与绝望。
她希望您能够帮帮她,把所有的灯都给重新开起来!她才能继续快乐地跟她的闺密们继续玩游戏!
牛棚中一共有N盏灯,编号为1到N。这些灯被置于一个灰常複杂的网络之中。
有M条很神奇的无向边,每条边连接两盏灯。
每盏灯上面都带有一个开关。
当按下某一盏灯的开关的时候,这盏灯本身,还有所有有边连向这盏灯的灯的状态都会被改变。
状态改变指的是:
当一盏灯是开著的时候,这盏灯被关掉;
当一盏灯是关著的时候,这盏灯被打开。

问最少要按下多少个开关,才能把所有的灯都给重新打开。
数据保证至少有一种按开关的方案,使得所有的灯都被重新打开。
【Input】
第一行:兩個空格隔開的整數:N和M。
第二到第M+1行:每一行有兩個由空格隔開的整數,表示兩盞燈被一條無向邊連接在一起。 沒有一條邊會出現兩次。
【Output】
一個單獨的整數,表示要把所有的燈都打開時,最少需要按下的開關的數目。
【Limited conditions】
1 <= N <= 35
1 <= M <= 595
【Sample input】
5 6
1 2
1 3
4 2
3 4
2 5
5 3
【Sample output】
3
【Sample explanation】
一共有五盞燈。
燈1、燈4和燈5都連接著燈2和燈3。
按下在燈1、燈4和燈5上面的開關。

Record

1h
细节很多……

Analysis

请先思考后再展开

高斯消元的做法以后再补吧
现在讲讲怎么用折半搜索艹过去

其实其核心思想就是把指数暴力地拆开,低消耗地合并起来得到答案
左边从起点过来,而右边则从终点过来,找到一个重叠状态(有时是对应状态,例如这道题是相反数)
用其中一边去找另外一边记录下来的答案(小就用数组,大就存下来二分查找)

以这道题为例,随便分成两边,右边记录答案(用数组,存储从终点过来需要多少步)
左边暴力后,找右边的相反数答案,相加即可

最后再反思点拨一下:
虽然产生的状态是2^35量级的,但其不同状态数量只有2^17
个人认为这也是折半搜索的精髓之体现

Code

请先思考后再展开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<bitset>
#include<algorithm>
using namespace std;
const int MAXN=40;
const int INF=0x3f3f3f3f;
typedef long long ll;
typedef unsigned long long ull;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>0?x:-x;}
int n,m;
ll f[MAXN];
ll ed;
ll bin[MAXN];
map<ll,int> mp;//left
int ans=INF;
void dfs(int x,int step,ll now,bool right)
{
if(now==ed) ans=mymin(ans,step);//debug
else if(!right and x>n/2)
{
ll tmp=mp[now];
if(tmp==0 or tmp>step) mp[now]=step;
//if(!mp.count(now)) mp[now]=step;
//else if(step<mp[now]) mp[now]=step;
}
else if(right and x>n-1)
{
if(mp.count(ed-now)) ans=mymin(ans,step+mp[ed-now]);
}
else
{
dfs(x+1,step,now,right);
dfs(x+1,step+1,now^f[x],right);
}
}
int main()
{
bin[0]=1;for(int i=1;i<=35;i++) bin[i]=bin[i-1]*2;
scanf("%d%d",&n,&m);
for(int i=0;i<=n-1;i++) f[i]=bin[i];
while(m--)
{
int x,y;scanf("%d%d",&x,&y);
x--;y--;//debug
f[x]+=bin[y];f[y]+=bin[x];
}
ed=bin[n]-1;
dfs(0, 0,0,0);
dfs(n/2+1,0,0,1);
printf("%d",ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/3fa9.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%