首页 > 其他分享 >ABC 345 F - Many Lamps

ABC 345 F - Many Lamps

时间:2024-03-17 17:25:49浏览次数:31  
标签:结点 ABC 点亮 int siz 345 Lamps 要么 using

ABC 345 F - Many Lamps

解题思路:

每次选取一条边,要么亮两个,要么灭两个,要么一灭一暗。亮的个数的奇偶性不变,所以不可能亮奇数个。

考虑每个连通块。如果是偶数个一定能全亮,奇数个则最少一个不亮。

对于两暗的,需要时通过操作点亮是一定的。

考虑一明一暗时是加入边的操作意味什么:意味着将明暗位置互换。

考虑这么一副图:

如何点亮所有点?\((1,3),(1,2),(1,4)\)全点即可。

\((1,3),(1,2)\)能够使得不相连的\((2,3)\)点亮。所以两个间接连通的点总能通过他们之间的边传递,使得只有这两点被点亮。

深度优先搜索时,这样考虑。如果儿子结点中有奇数个结点,那么父节点和儿子结点间的边一定加入。

这个加入要么会同时点亮父亲和儿子;要么会将其他奇数结点子树中的结点和当前子节点间接连通点亮,解放父节点,使父节点可以和接下来的子树进行配对或转移。

总之被点亮的点数不会减少,解放当前子树。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
using piii = pair<ll, pair<ll, ll>>;
const ll inf = 1ll << 60;
using ull = unsigned long long;
const int N = 2e5 + 10;
bool vis[N];
vector<pii> e[N];
int siz[N];
bool f[N];
void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        e[a].emplace_back(b, i);
        e[b].emplace_back(a, i);
    }
    if (k & 1)
    {
        cout << "No\n";
    }
    else
    {
        vector<int> ans;
        for (int i = 1; i <= n; i++)
        {
            if (!vis[i])
            {
                auto dfs = [&](auto self, int u) -> void
                {
                    siz[u] = 1;
                    vis[u] = true;
                    for (auto [v, id] : e[u])
                    {
                        if (vis[v])
                        {
                            continue;
                        }
                        self(self, v);
                        if ((siz[v] & 1) && k > 0)
                        {
                            ans.emplace_back(id);
                            if (!f[u])
                            {
                                k -= 2;
                            }
                            f[u] ^= 1;
                        }
                        siz[u] += siz[v];
                    }
                };
                dfs(dfs, i);
            }
        }
        if (k)
        {
            cout << "No\n";
        }
        else
        {
            cout << "Yes\n";
            cout << ans.size() << endl;
            for (auto x : ans)
            {
                cout << x << " \n"[x == ans.back()];
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

标签:结点,ABC,点亮,int,siz,345,Lamps,要么,using
From: https://www.cnblogs.com/value0/p/18078801

相关文章

  • Monoxer Programming Contest 2024(AtCoder Beginner Contest 345)
    MonoxerProgrammingContest2024(AtCoderBeginnerContest345)\(A\)Leftrightarrow\(100pts\)按照题意模拟即可。点击查看代码intmain(){strings;inta=0,b=0,c=0,i;cin>>s;for(i=0;i<s.size();i++){a+=(s[i]=='<&#......
  • abc343F 区间第2大的出现次数
    给定数组a[n],有Q组操作,格式为:1px,将a[p]修改为x;2lr,查询区间[l,r]内第2大元素的出现次数。1<=n,q<=2e5;1<=a[i]<=1e9用线段树维护各个区间的最大及次大元素的出现次数,合并时最多只保留两条记录。#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#......
  • AT_abc345_c [ABC345C] One Time Swap 题解
    题目传送门解法对于\(S_{i}\),设\(num_{S_{i}}\)表示\(S_{i+1\simn}\)中\(S_{i}\)出现的次数,则\(S_{i}\)对答案产生的贡献为\(n-i-num_{S_{i}}\)。注意原串在存在两个相同的元素的时候,也要统计在内。代码#include<bits/stdc++.h>usingnamespacestd;#definell......
  • AtCoder-abc345_f题解
    题意简述给定一个无向图。你要在其中选出一些边,使得选出的边所构成的图中,度数为奇数的点有\(K\)个。如果可以,输出选了哪些边,否则输出-1。思路首先在选一条边时,边两端点度数的奇偶性一定都会改变,即要么都变为奇数,要么两个点的奇偶性交换过来,要么都变为偶数。这三种情况时满足......
  • ABC345 A ~ D
    ABC345题外话:巨难。A翻译现在给你一个字符串,定义一个合法的箭头由一个<,\(k\)个=,一个>组成的长度为\(k+2\)的字符串。问字符串\(s\)是否是一个合法的箭头。思路赛时因为翻译问题,吃了\(1\)发罚时。只需要判断\(s_1\)是否为<,\(s_2\sims_{n-1}\)是否为=,\(s_......
  • AT_abc345_d 题解
    是个逆天搜索。最开始:爆搜,启动!然后TLE到飞起。赛后:我【数据删除】这么简单的吗?!dfs每个位置,试着把没放过的块放到以这个位置为左上角的区域里面。好了没了,就是这么简单!对了记得这个块可以旋转!#include<stdio.h>#include<bits/stdc++.h>#defineN1000010#defineMOD9......
  • AtCoder Beginner Contest 345
    是这样的,C的longlong只开了ans没开全局,AC12WA12,调了一个小时,在赛后1min发现了该错误。没开longlong见祖宗,望周知;这是C的码,简单的小题一只,可怜的longlong。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;strings;intn,f,ans;map<char......
  • abc174E 最小化不超过k次操作后木棍的最大长度
    有n根木棍,第i根木棍长度为a[i],每次操作可以选一根木棍将其锯成两段,要求总操作次数不超过k。问最终所有木棍最大长度的最小值是多少?1<=n<=2e5;0<=k<=1e9;1<=a[i]<=1e9最小化最大值,或者反过来最大化最小值,优先考虑二分答案,对于某个特定的长度x,考虑将其锯成最长x一段需要的次数,如......
  • abc214D 全部路径最大边权之和
    给定一颗包含n个顶点的树,第i条边连接u[i]和v[i],边权为w[i]。记f(i,j)表示顶点i到j的简单路径上边权的最大值,求$\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}f(i,j)$。2<=n<=1e5;1<=u[i],v[i]<=n;1<=w[i]<=1e7对于每条边,考虑以它作为最大边权的路径数,为两侧节点数的乘积,数点可以用并......
  • P2824 [HEOI2016/TJOI2016] 排序 与 ABC297_g Range Sort Query 题解
    洛谷题目链接:排序abc题目链接:Atcoder或者洛谷两道差不多的题拿出来说说。本题有双\(\log\)做法,也有单\(\log\)做法,都讲讲。双\(\log\)做法对于第一个题而言,询问最终\(pos\)位置上的数为多少,那么这个问题是否具有单调性?这个是很有意思的点,我们考虑只关注某个数\(x\)......