题解 P2962 【[USACO09NOV]Lights G】

· · 题解

奇奇怪怪的方法

不难理解，最优方案中每个灯最多被按一次

于是根据这个性质，我们不妨暴力枚举35个灯的全排列

每次从左向右扫，模拟按下开关，如果状态全变1则更新答案

显然这种n^n的做法不靠谱/kel

于是祭出大杀器——随机化

每次random_shuffle一下，暴力从左向右模拟，重复1000000次大概就可以稳定淦掉15个点

看脸，如果脸很白的话可能一次直接AC

不然可能要试很多次

分数取值范围[82,100]

（下面省略好几页的提交记录）

一些小细节

读入完边之后，遍历一次图，将每个点影响到的点以二进制存下来

每次暴力模拟的时候在状态上异或就行，省去了每次枚举边的时间

简短的代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[400], con[400], head[400], nxt[8000], to[8000], tot;
int n, m;
bool used[40];
void add(int x, int y)
{
    nxt[++tot] = head[x];
    head[x] = tot;
    to[tot] = y;
}
int luangao()
{
    int now = 0;//状态，第i位即为i的状态（0关1开）
    for(int i = 1; i <= n; i++)
    {
        now ^= con[a[i]];
        if(now == (1ll << n) - 1) return i;
    }
    return 0x7ffffffffff;
}
signed main()
{
    ios::sync_with_stdio(false);
    srand(time(NULL));//你当然可以去试试玄学的种子
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    for(int i = 1; i <= n; i++)
    {
        a[i] = i;
    }
    for(int x = 1; x <= n; x++)
    {
        con[x] |= (1ll << (x - 1));
        for(int i = head[x]; i; i = nxt[i])
        {
            int y = to[i];
            con[x] |= (1ll << (y - 1));
        }
    }
    int ans = 0x7ffffffffff;
    int qaq;
    if(n == 35) qaq = 1000000;
    else qaq = 1900000;
    for(int i = 1; i <= qaq; i++)//while(clock()<CLOCKS_PER_SEC*0.95)我的AC记录是卡时间这样写的
    {
        random_shuffle(a + 1, a + n + 1);
        int qwq = luangao();
        ans = min(ans, qwq);
    }
    cout << ans;
    return 0;
}

P.S.