首页 > 其他分享 >CF549B题解

CF549B题解

时间:2024-10-04 17:49:42浏览次数:7  
标签:CF549B 一个点 int 题解 合法 while 101

传送门:https://codeforces.com/problemset/problem/549/B

和CF242C思路完全相同,对于一个点,显然一旦达到额定值后,其他任何操作都无法使他减小,于是我们得出一个贪心性质,当且仅当一个点不合法时,才取增加他的值。同理,我们可以证明,问题必定有解,因为若一个点被选择,必定是因为其曾不合法,选择后使其
合法,而若最后一个点不合法,其必定是未选择的,选择其则能合法。过程可以用队列维护。时间复杂度\(O(n)\)。

#include <bits/stdc++.h>

using namespace std;

inline int read() {
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9') if (c == '-') flag = true;
    int res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') res = (res << 3) + (res << 1) + c - '0';
    return flag ? -res : res;
}

vector<int> e[101];
char s[101];
int a[101];

int main() {
    int n = read();
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s + 1);
        for (int j = 1; j <= n; ++j) if (s[j] == '1') e[i].push_back(j);
    }
    vector<int> ans;
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        if (!a[i]) q.push(i);
    }
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        ans.push_back(x);
        for (int y: e[x]) {
            --a[y];
            if (!a[y]) q.push(y);
        }
    }
    sort(ans.begin(), ans.end());
    printf("%zu\n", ans.size());
    for (int k: ans) printf("%d ", k);
    return 0;
}

标签:CF549B,一个点,int,题解,合法,while,101
From: https://www.cnblogs.com/Jefferyz/p/18447007

相关文章

  • [题解]P7077 [CSP-S2020] 函数调用
    P7077[CSP-S2020]函数调用题意简述给定一个长度为\(n\)的序列\(a_1,a_2,\dots,a_n\),给定\(m\)个函数,每个函数可能是下面\(3\)种类型,用\(T_x\)表示函数\(x\)的类型:\(T_x=1\),对下标\(p\)增加\(v\)。\(T_x=2\),对所有元素乘\(v\)。\(T_x=3\),由若干类型\(1\)和类型\(2\)组成......
  • 【题解】B - 三元上升子序列
    目录题目内容DescriptionInputOutput数据规模与约定思路代码题目内容DescriptionErwin最近对一种叫thair的东西巨感兴趣。。。在含有\(n\)个整数的序列\(a_1,a_2,\ldots,a_n\)中,三个数被称作thair当且仅当\(i\ltj\ltk\)且\(a_i\lta_j\lta_k\)。求一个序列中thair......
  • BUUCTF_MISC题解析(3,4)
    3.你竟然赶我走搜索010editor官网,点第一个页面,下载010editor(十六进制编译器)(黄色图标),直接010editor打开(或者使用stegSolve)一般情况用ctrl+f进入字符串搜索查看是否有插入的flag信息,就可以在文件尾看到flag是flag{stego_is_s0_bor1ing} 4.二维码扫码识别二维码,发现隐......
  • 【题解】Solution Set - NOIP2024集训Day42 博弈论
    【题解】SolutionSet-NOIP2024集训Day42博弈论https://www.becoder.com.cn/contest/5574https://www.cnblogs.com/CloudWings/p/17813917.html「中山市选2009」谁能赢呢?一道经典的「二分图博弈」在棋盘问题上的应用。https://www.luogu.com.cn/article/h8a79k3i......
  • [题解](更新中)MX-X6 A~B
    Portal:https://www.luogu.com.cn/contest/200833A-もしも容易发现可以构造\(1,x\)或\(x,1\)让序列如\(\dots,1,x,1,x,1,x,\dots\)这样循环。只需要关注\(n\)的奇偶性即可。点击查看代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intt,n,an;si......
  • [题解]SFMOI Round I A~C
    Portal:https://www.luogu.com.cn/contest/179008\(\bf{100+50+50+25+5=\color{indianred}225\color{black}\,\rk.\184}\)A-StrangeCakeGame显然对于小W,向下移动蛋糕刀是最有利的;对于小M,向右移动是最有利的。所以双方以最佳状态移动,最终\(x\ley\)的巧克力是小W的。直接......
  • 【题解】「CF765F」Souvenirs
    https://www.luogu.com.cn/problem/CF765F首先有一个比较navie的\(O(n\sqrtm\logn)\)的做法(add和del的时候,用两个multiset维护一下。有一个bitset的做法来优化用multiset查询前驱后继的做法:https://www.luogu.com.cn/article/zcmco6hd首先考虑离线下来,将询问挂......
  • CF154C题解
    传送门:https://codeforces.com/problemset/problem/154/C求出无向图中,满足所有出边都相连或出边直接连接点对的点对数。很显然可以暴力枚举点对一对对去check,时间复杂度\(O(n^2+m)\)。#include<bits/stdc++.h>usingnamespacestd;inlineintread(){charc;boo......
  • 构树 题解
    构树题解好题,除了毒瘤卡空间。“恰好”这个形式很二项式反演。设\(f(n)\)表示树上钦定\(n\)条边和原树相同的方案数,\(g(n)\)表示树上恰好有\(n\)条边和原树相同的方案数,那么原先的形式是:\[f(n)=\sum_{i\gen}{i\choosen}g(i)\]二项式反演得到:\[g(n)=\sum_{i\gen}(......
  • QOJ 8726 [APIO2024] 魔术表演 题解
    DescriptionAlice和Bob是著名的魔术师。Catherine是一位富豪,她非常喜欢观看Alice和Bob的魔术。某一天,Catherine决定向Alice和Bob发出挑战:只要他们能成功表演如下的魔术,Catherine就将向他们提供巨额奖金!这个魔术的表演过程如下:步骤\(1\):Bob进⼊⼀个密室中,在魔术......