题解：P10643 [NordicOI 2022] 嬉皮爵士 Hipster Jazz

本题相信大家一开始都有想用 SA 做的想法吧……但是玄学调参数怎么都调不好……

模拟退火其实是不适合这样零散的状态空间的，模拟退火适合的是牵一发而动全身，只需要调整比较少的值（比如一个距离或者一个坐标）而获得调整的，这种题这种要调整大量参数并且每个参数的取值空间离散且极少的情况是不适用的。

并且我们用模拟退火最重要的作用其实是避免陷入局部最优，但是这个题目目标明确且宽松，其实没什么局部最优的问题，这也说明了模拟退火在这里用处着实不大。

事实上，由于题目的约束极为宽松，贪心都足以解决这个问题而几乎没有可能陷入反复震荡的情况。

并且这个题目还有一个有意思的点：如果一个点当前是不符合情况的，只要翻转这个点单点的颜色，这个点就可以满足了。

由于每一次修改必然使得全图更加接近于目标图，所以需要的调整次数上界为

O(m)

的，并且每一次扫描的用时上界也是

O(n+m)

的。所以最差复杂度为

O(nm+m^2)

，是合理且可以通过本题的。

贴代码。

CPP

#include<bits/stdc++.h>
using namespace std;
constexpr int maxn=207;
vector<int>fn[maxn];
int n,m;
void output(bitset<maxn>&bs) {
    for(int i=1;i<=n;i++)
        putchar(bs[i]?'P':'S');
}
bool check(bitset<maxn>&bs) {
    for(int i=1;i<=n;i++) {
        int cnt=0;
        for(auto&t:fn[i])
            if(bs[t]==bs[i])
                ++cnt;
        if(cnt*2>fn[i].size()) {
            bs.flip(i);
            return false;
        }
    }
    output(bs);
    return true;
}
int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    bitset<maxn>bs;
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        int u,v;
        cin>>u>>v;
        fn[u].emplace_back(v);
        fn[v].emplace_back(u);
    }
    while(!check(bs));
    return 0;
}

题解：P10643 [NordicOI 2022] 嬉皮爵士 Hipster Jazz

文章操作

相关推荐

评论

题解：P10643 [NordicOI 2022] 嬉皮爵士 Hipster Jazz