首页 > 其他分享 >CF830E Perpetual Motion Machine

CF830E Perpetual Motion Machine

时间:2024-08-14 18:28:07浏览次数:14  
标签:std Machine cur int Perpetual len Motion ans out

一堆 Cornner Case 的大分讨,我们全队一边写一边补情况,WA 了五发终于干过去了

首先当图中存在某个环时,我们只要给环上的所有点赋值为 \(1\) 即可;又因为图连通所以只要考虑树的情况即可

考虑如果存在一个度数 \(\ge 4\) 的点,将其赋值为 \(2\) 并将其周围的四个点赋值为 \(1\) 即可

如果存在两个及以上度数为三的点,只要将其中两个的路径上所有点赋值为 \(2\),并在端点处各选两个点赋值为 \(1\) 即可

难点在于有且仅有一个度数为三的点的情况,因为我们很容易证明一条链的情况是无解的

考虑此时的图一定形如一个中心点,往外延申出三条链,不妨将这三条链的长度记为 \(a,b,c(a\le b\le c)\)

考虑找出一些最小的有解结构,方法可以是人类智慧也可以是爆搜,最后发现以下三种 Case 是合法的:

然后这题就做完了,判断一个图是否满足上述条件即可,代码是徐神写的

#include <bits/stdc++.h>

std::vector<int> work() {
    int n, m; std::cin >> n >> m;
    std::vector<std::vector<int>> out(n, std::vector<int>());
    for(int i = 0, f, t; i < m; ++i) {
        std::cin >> f >> t;
        f--; t--;
        out[f].push_back(t);
        out[t].push_back(f);
    }

    std::vector<int> ans(n, 0);

    std::vector<bool> vis(n, false);
    std::function<bool(int, int)> dfs = [&](int cur, int fa) -> bool {
        vis[cur] = true;
        for(auto out: out[cur]) {
            if(out == fa) continue;
            if(vis[out] || dfs(out, cur))
                return ans[cur] = 1, vis[cur] = true;
        }
        return false;
    };

    for(int i = 0; i < n; ++i) if(!vis[i] && dfs(i, -1)) return ans;

    for(int i = 0; i < n; ++i) if(out[i].size() >= 4) {
        ans[i] = 2;
        for(int j = 0; j < 4; ++j) ans[out[i][j]] = 1;
        return ans;
    }

    auto ahaha = [&](auto self, int cur, int fa) -> int {
        for(auto out: out[cur]) if(out != fa) return self(self, out, cur) + 1;
        return 1;
    };

    auto fill = [&](auto self, int cur, int fa, std::vector<int> val) -> void {
        if(val.empty()) return ;
        ans[cur] = val.back(); val.pop_back();
        for(auto out: out[cur]) if(out != fa) self(self, out, cur, val);
    };
    
    vis.assign(n, false);

    auto dfs2 = [&](auto self, int cur, int fa) -> int {
        vis[cur] = true;
        if(out[cur].size() == 3) return ans[cur] = 2, cur;
        for(auto out: out[cur]) if(out != fa) {
            int res = self(self, out, cur);
            if(res >= 0) return ans[cur] = 2, res;
        }
        return -1;
    };

    bool flag = false;

    for(int i = 0; i < n && !flag; ++i) if(!vis[i] && out[i].size() == 3) {
        vis[i] = true;
        for(auto out: out[i]) {
            if(flag) break;
            int res = dfs2(dfs2, out, i);
            // std::cerr << "res = " << res << char(10);
            if(res >= 0) {
                ans[i] = 2;
                flag = true;
            }
        }
    }

    if(flag) {
        for(int i = 0; i < n; ++i) if(ans[i] == 2) for(auto out: out[i]) if(ans[out] == 0) ans[out] = 1;
        return ans;
    }

    for(int i = 0; i < n; ++i) if(out[i].size() == 3) {
        std::pair<int, int> len[3];
        for(int j = 0; j < 3; ++j) len[j] = {ahaha(ahaha, out[i][j], i), out[i][j]};
        std::sort(len, len + 3);
        // std::cerr << "len[] = [";
        // for(int j = 0; j < 3; ++j) std::cerr << len[j].first << (j == 2 ? "]\n" : ", ");
        if(len[0].first >= 2 && len[1].first >= 2 && len[2].first >= 2) {
            ans[i] = 3;
            fill(fill, len[0].second, i, std::vector<int>{1, 2});
            fill(fill, len[1].second, i, std::vector<int>{1, 2});
            fill(fill, len[2].second, i, std::vector<int>{1, 2});
            return ans;
        }
        if(len[0].first >= 1 && len[1].first >= 2 && len[2].first >= 5) {
            ans[i] = 6;
            fill(fill, len[0].second, i, std::vector<int>{3});
            fill(fill, len[1].second, i, std::vector<int>{2, 4});
            fill(fill, len[2].second, i, std::vector<int>{1, 2, 3, 4, 5});
            return ans;
        }
        if(len[0].first >= 1 && len[1].first >= 3 && len[2].first >= 3) {
            ans[i] = 4;
            fill(fill, len[0].second, i, std::vector<int>{2});
            fill(fill, len[1].second, i, std::vector<int>{1, 2, 3});
            fill(fill, len[2].second, i, std::vector<int>{1, 2, 3});
            return ans;
        }
    }

    return {};
}

int main() {
    std::ios::sync_with_stdio(false);
    int t; std::cin >> t; while(t--) {
        auto ans = work();
        if(ans.empty()) std::cout << "NO\n";
        else {
            std::cout << "YES\n";
            int n = ans.size();
            for(int i = 0; i < n; ++i) std::cout << ans[i] << char(i == n - 1 ? 10 : 32); 
        }
    }
    return 0;    
}

标签:std,Machine,cur,int,Perpetual,len,Motion,ans,out
From: https://www.cnblogs.com/cjjsb/p/18359544

相关文章

  • 《DNK210使用指南 -CanMV版 V1.0》第十九章 machine.PWM类实验
    第十九章machine.PWM类实验1)实验平台:正点原子DNK210开发板2)章节摘自【正点原子】DNK210使用指南-CanMV版V1.03)购买链接:https://detail.tmall.com/item.htm?&id=7828013987504)全套实验源码+手册+视频下载地址:http://www.openedv.com/docs/boards/k210/ATK-DNK210.html5)正......
  • SciTech-BigDataAIML-Machine Learning Tutorials
    MachineLearningTutorialsMachineLearningTutorialsThispagelistsallofthemachinelearningtutorialsavailableonStatology.IntroductiontoMachineLearningSupervisedvs.UnsupervisedLearningRegressionvs.ClassificationAlgorithmsTheBias-Var......
  • 论文笔记:GeoShapley: A Game Theory Approach toMeasuring Spatial Effects in Machin
    (GeoShapley:机器学习模型中测量空间效应的博弈论方法)话题点:geoshapley、XAI、空间效应、非线性一、引言机器学习和人工智能(AI)越来越多地用于模拟地理空间现象,在各个领域都有很好的表现。可解释人工智能(XAI)领域的最新进展为解释黑箱机器学习提供了一种解决方案。排列特征......
  • JVM(Java Virtual Machine)性能调优
    JVM(JavaVirtualMachine)性能调优是优化Java应用程序性能的关键步骤,涉及多个方面的考虑和调整。以下是一个详尽的JVM性能调优指南,涵盖了主要的技术点、调优策略和具体步骤。一、JVM性能调优概述JVM性能调优的主要目标是提高Java应用程序的响应速度、吞吐量和稳定性,同时减......
  • CF641E Little Artem and Time Machine 题解
    题目传送门前置知识CDQ分治解法单点修改区间查询,但值域巨大,考虑离散化掉\(x\)。时刻\(t\)仍很大,考虑将其作为CDQ分治的第一维,然后套个CDQ分治即可,注意及时清空桶数组。代码CodeForces275382150#include<bits/stdc++.h>usingnamespacestd;#definelllonglon......
  • 《DNK210使用指南 -CanMV版 V1.0》第十八章 machine.Timer类实验
    第十八章machine.Timer类实验1)实验平台:正点原子DNK210开发板2)章节摘自【正点原子】DNK210使用指南-CanMV版V1.03)购买链接:https://detail.tmall.com/item.htm?&id=7828013987504)全套实验源码+手册+视频下载地址:http://www.openedv.com/docs/boards/k210/ATK-DNK210.html5......
  • 《DNK210使用指南 -CanMV版 V1.0》第十七章 machine.WDT类实验
    第十七章machine.WDT类实验1)实验平台:正点原子DNK210开发板2)章节摘自【正点原子】DNK210使用指南-CanMV版V1.03)购买链接:https://detail.tmall.com/item.htm?&id=7828013987504)全套实验源码+手册+视频下载地址:http://www.openedv.com/docs/boards/k210/ATK-DNK210.html5)正......
  • Machine Learning Operations
    MachineLearningOperationshttps://ml-ops.org/WithMachineLearningModelOperationalizationManagement(MLOps),wewanttoprovideanend-to-endmachinelearningdevelopmentprocesstodesign,buildandmanagereproducible,testable,andevolvableML-......
  • 【详细版】Spring Tips: Spring Statemachine
    SpringTips:SpringStatemachine大纲引言介绍SpringStateMachine及其重要性解释状态机的基本概念和用途SpringStateMachine概述状态机的定义和功能状态机的应用场景SpringStateMachine的DSL和特性创建和配置SpringStateMachine使用start.spring.io创建......
  • [ABC325D] Printing Machine
    这题主要是题面不知道为什么会有两个版本。//[x,y]某种颜色编号i只能放在一个区间内。。//且i之间不能冲突。。。贴份代码。。这题大部分都写的很乱。。我看题解。`include<bits/stdc++.h>usingnamespacestd;defineintlonglongdefinell__int128_tdefinear......