传送门: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