Japanese Alumni Group Autumn Contest 2014
zimpha
posted @ Thu, 12 Mar 2015 00:53:19 +0800
in JAG
, 943 readers
今天补完这些题目, 写个题解备忘.
题目链接: aizu 2589 ~ 2599
题解: 日文题解, 看不懂google翻译可以搞定.
Problem A. North North West
给出方向的英文表达, 求出实际角度.
按照题目规则模拟, 注意是右结合的.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
int main() {
string s;
while (getline(cin, s) && s != "#") {
vector<string> v;
for (size_t i = 0; i < s.size(); i += v.back().size()) {
if (s[i] == 'n') v.push_back(s.substr(i, 5));
else v.push_back(s.substr(i, 4));
}
reverse(v.begin(), v.end());
int a = 0, b = 1;
if (v[0] == "north") a = 0;
else a = 90;
for (size_t i = 1; i < v.size(); ++ i) {
a *= 2; b *= 2;
if (v[i] == "north") a -= 90;
else a += 90;
}
int g = __gcd(a, b);
a /= g, b /= g;
if (b > 1) cout << a << "/" << b << endl;
else cout << a << endl;
}
return 0;
}
Problem B. Unknown Switches
有$n$个开关和$m$盏灯, 每盏灯都被某个开关控制. 现在给出$q$个开关的操作状态, 以及每次操作后灯的状态. 要求求出每盏灯被哪个开关控制. 保证数据合法.
数据规模: $1 \le n \le 36, 1 \le m \le 1000, 0 \le q \le 1000$
由于每盏灯只被一个开关控制, 那么对于某一盏灯$x$, 我们只要把那些使$x$亮起来的开关操作and起来就好了. 注意如果某个开关操作状态下, 灯$x$没有亮, 那么对这个操作状态取反, 灯$x$就亮了.
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
typedef pair<int, int> PII;
const int MAXN = 2000 + 10, SIZE = 1024;
LL A[MAXN];
int N, M, Q;
char s[MAXN], t[MAXN];
char change(int x) {
if (x < 10) return x + '0';
else return 'A' + x - 10;
}
int main() {
while (scanf("%d%d%d", &N, &M, &Q) == 3 && N) {
for (int i = 0; i < M; ++ i) A[i] = LL(1ll << N) - 1;
LL sw = 0;
for (int _ = 0; _ < Q; ++ _) {
scanf("%s%s", s, t);
for (int i = 0; i < N; ++ i) sw ^= LL(s[i] - '0') << i;
for (int i = 0; i < M; ++ i) {
A[i] &= t[i] == '1' ? sw : ~sw;
}
}
for (int i = 0; i < M; ++ i) s[i] = '?'; s[M] = 0;
for (int i = 0; i < M; ++ i) {
if (__builtin_popcountll(A[i]) != 1) continue;
int x = __builtin_ctzll(A[i]);
s[i] = change(x);
}
puts(s);
}
return 0;
}
Problem C. Speedrun
有一个RPG游戏, 共$n+1$个存档点, 存档需要花一分钟. 通过存档点$i$的概率为$p_i$, 花费时间为1分钟. 如果某次过关失败, 那么就会返回到最近的村过档的存档点. 问通关的最小期望时间.
数据规模: $2 \le n \le 10^5, 0 < p_i \le 1$
首先需要算出从$i$号存档点开始, 直到$j$失败的概率, 设为$e_{i,j}$. 很容易得到$$e_{i,j} = \frac{1}{p_ip_{i+1}\dots p_{j-1}} + \frac{1}{p_{i+1}\dots p_{j-1}} + \dots, + \frac{1}{p_{j-1}}$$
然后我们可以得到一个$O(n^2)$的dp方程, 令$f_i$表示从$i$到$n$的最小期望时间, 那么$f_i = \displaystyle\text{min}_{i < j \le n} \{e_{i,j}+f_j+1\}$
考虑到优化这个dp貌似不可做, 那么从精度出发来减少决策点的数目. 我们先把题目中连续的$p_i=1$的那些点合并, 然后只要往后枚举差不多50个点就足够精度了.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double flt;
typedef pair<int, int> PII;
const int MAXN = 100000 + 10;
vector<flt> p, dp;
int n;
int main() {
while (scanf("%d", &n) == 1 && n) {
flt sum = 0; p.clear();
for (int i = 0; i < n; ++ i) {
flt x; scanf("%lf", &x);
if (x == 1.00) sum += 1.0;
else {
if (sum > 0) p.push_back(sum), sum = 0;
p.push_back(x);
}
}
if (sum > 0) p.push_back(sum);
n = p.size();
dp.resize(n + 1); dp[n] = 0;
for (int i = n - 1; i >= 0; -- i) {
flt now = 0; dp[i] = 1e9;
for (int j = i + 1; j <= n && j - i <= 50; ++ j) {
if (p[j - 1] < 1.0) now = (now + 1.0) / p[j - 1];
else now += p[j - 1];
dp[i] = min(dp[i], now + dp[j] + 1);
}
}
printf("%.10f\n", dp[0] - 1);
}
return 0;
}
Problem D. Flowers
有$n$个植物, 如果第$i$个植物成长值超过$th_i$, 那么它就会开花. 你有两种操作, 浇水或者施肥. 如果你选择浇$W$单位的水, 那么第$i$个植物成长值会增加$W \times vw_i$, 同时需要花费$W\times pw$的钱. 如果对第$i$个植物施肥$F$, 那么第$i$个植物成长值会增加$F \times vf_i$, 同时需要花费$F \times pf_i$的钱.
问使所有植物同时开花的最小花费.
数据规模: $1 \le n \le 10^5, 1 \le pw, pf_i,vf_i \le 100, -100 \le vw_i, th_i \le 100$
大概可以猜出这个东西关于$W$是一个凸函数, 于是三分$W$就好了. 比赛时eps的处理没做好, 然后一直WA到死.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef double flt;
const int MAXN = 100000 + 10;
const flt eps = 1e-12;
int vw[MAXN], pf[MAXN], vf[MAXN], th[MAXN];
int N, pw;
flt calc(flt W) {
flt cost = W * pw;
for (int i = 0; i < N; ++ i) {
flt need = th[i] - W * vw[i];
if (need <= eps) continue;
flt f = need / vf[i];
cost += f * pf[i];
}
return cost;
}
int main() {
while (scanf("%d", &N) == 1 && N) {
scanf("%d", &pw);
for (int i = 0; i < N; ++ i) {
scanf("%d%d%d%d", vw + i, pf + i, vf + i, th + i);
}
flt left = 0, right = 200;
for (int _ = 0; _ < 100; ++ _) {
flt m1 = (left + left + right) / 3.0;
flt m2 = (left + right + right) / 3.0;
flt c1 = calc(m1), c2 = calc(m2);
if (c1 < c2) right = m2;
else left = m1;
}
printf("%.10f\n", calc(left));
}
return 0;
}
Problem E. Square in Circles
有$n$个圆, 圆心都在$x$轴上, 第$i$个圆圆心在$(x_i, 0)$, 半径为$r_i$, 保证相邻两个圆相交但不会出现包含关系. 要求找一个最大正方形, 使得这个正方形完全落在这$n$个圆内.
数据规模: $1 \le n \le 50000, |x_i| \le 10^5, 1 \le r_i \le 10^5$
二分答案然后判定一下就好了.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef double flt;
const int MAXN = 50000 + 10;
const flt eps = 1e-10;
int X[MAXN], R[MAXN], N;
flt sqr(flt x) {
return x * x;
}
flt get(flt xa, flt ra, flt xb, flt rb) {
flt len = xb - xa;
flt cosa = (sqr(ra) + sqr(len) - sqr(rb)) / (2.0 * ra * len);
flt sina = sqrt(1.0 - sqr(cosa));
//flt h = ra * sina;
flt w = ra * cosa;
flt xx = xa + w;
return xx;
}
typedef pair<flt, flt> PDD;
PDD get(flt x, flt r, flt y) {
if (y >= r - eps) return PDD(0, 0);
flt x1 = x - sqrt(sqr(r) - sqr(y));
flt x2 = x + sqrt(sqr(r) - sqr(y));
return PDD(x1, x2);
}
bool check(flt y) {
vector<PDD> v;
for (int i = 0; i < N; ++ i) {
v.push_back(get(X[i], R[i], y));
}
sort(v.begin(), v.end());
flt l = v[0].first, r = v[0].second;
flt mx = 0;
for (auto &se : v) {
if (se.first <= r + eps) r = max(se.second, r);
else {
mx = max(mx, r - l);
l = se.first, r = se.second;
}
}
mx = max(mx, r - l);
return mx >= 2.0 * y - eps;
}
int main() {
while (scanf("%d", &N) == 1 && N) {
flt ret = 0;
for (int i = 0; i < N; ++ i) {
scanf("%d%d", X + i, R + i);
ret = max(ret, sqrt(2.0) * R[i]);
}
flt left = 0, right = 2e5;
for (int _ = 0; _ < 50; ++ _) {
flt mid = (left + right) * 0.5;
if (check(mid)) left = mid;
else right = mid;
}
printf("%.18f\n", left + right);
}
return 0;
}
Problem F. Reverse a Road II
给出一个$n$个点, $m$条边的有向图, 现在可以使得某条边反向, 要求令$s$到$t$的最大流变大, 问有多少种方案.
数据规模: $1 \le n \le 1000, 1 \le m \le 10000$
先求一遍从$s$到$t$的最大流. 在残余网络中, 考虑$s$能到达的点集$S$和可以到达$t$的点集$T$, 那么对于原来的一条边$u \rightarrow v$, 如果$u \in T, v \in S$, 那么这条边可以累计到答案. 正确性显然.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXM = 200000 + 10, MAXN = 1000 + 10, inf = 1e9;
namespace NF {
struct Edge {
int v, c, f, nx;
Edge() {}
Edge(int v, int c, int f, int nx):
v(v), c(c), f(f), nx(nx) {}
} E[MAXM];
int G[MAXN], lev[MAXN], cur[MAXN];
int sz, N;
void init(int n) {
N = n; sz = 0;
memset(G, -1, sizeof(G));
}
void link(int u, int v, int c) {
E[sz] = Edge(v, c, 0, G[u]); G[u] = sz ++;
E[sz] = Edge(u, 0, 0, G[v]); G[v] = sz ++;
}
bool bfs(int S, int T) {
static int Q[MAXN];
for (int i = 0; i < N; ++ i) lev[i] = -1;
Q[0] = S; lev[S] = 0;
for (int h = 0, t = 1; h < t; ++ h) {
int u = Q[h], v;
for (int now = G[u]; ~now; now = E[now].nx) {
if (lev[v = E[now].v] == -1 && E[now].c > E[now].f) {
lev[v] = lev[u] + 1; Q[t ++] = v;
}
}
}
return lev[T] != -1;
}
int dfs(int u, int T, int low) {
if (u == T) return low;
int ret = 0, tmp, v;
for (int &now = cur[u]; ~now && ret < low; now = E[now].nx) {
if (lev[v = E[now].v] == lev[u] + 1 && E[now].c > E[now].f) {
tmp = dfs(v, T, min(low - ret, E[now].c - E[now].f));
ret += tmp; E[now].f += tmp; E[now ^ 1].f -= tmp;
}
}
if (!ret) lev[u] = -1; return ret;
}
int dinic(int S, int T) {
int ret = 0;
while (bfs(S, T)) {
memcpy(cur, G, sizeof(G[0]) * N);
ret += dfs(S, T, inf);
}
return ret;
}
static bool mark[MAXN];
int solve(int S, int T) {
bfs(S, T); int ret = 0;
memset(mark, 0, sizeof(mark));
queue<int> Q; Q.push(T); mark[T] = true;
while (!Q.empty()) {
int u = Q.front(); Q.pop();
for (int now = G[u]; ~now; now = E[now].nx) {
int v = E[now].v;
if (E[now ^ 1].c > E[now ^ 1].f) {
if (!mark[v]) mark[v] = true, Q.push(v);
}
else ret += (lev[v] != -1 && E[now].c > 0);
}
}
return ret;
}
}
int main() {
int n, m, s, t;
while (scanf("%d%d%d%d", &n, &m, &s, &t) == 4 && n) {
NF::init(n); -- s; -- t;
for (int i = 0, u, v; i < m; ++ i) {
scanf("%d%d", &u, &v); -- u, -- v;
NF::link(u, v, 1);
}
int maxflow = NF::dinic(s, t);
int ret = NF::solve(s, t);
if (ret != 0) maxflow ++;
printf("%d %d\n", maxflow, ret);
}
return 0;
}
Problem G. Cookie Counter
给出$n,d,l$, 求方程$x_1+x_2+\dots+x_d=n, 0 \le x_i < l$的方案数, 对$10^9+7$取模.
数据规模: $1 \le n, l \le 2000, 1 \le d \le 10^{12}$
容斥原理搞一下就好了.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 2000 + 10, MOD = 1e9 + 7;
int inv[MAXN];
LL pm(LL a, LL n) {
LL r = 1;
for (; n; n >>= 1) {
if (n & 1) r = r * a % MOD;
a = a * a % MOD;
}
return r;
}
LL C(LL n, int m) {
if (m < 0 || n < 0 || n < m) return 0;
LL r = 1;
for (int i = 1; i <= m; ++ i) {
r = (n - i + 1) % MOD * r % MOD * inv[i] % MOD;
}
return r;
}
int main() {
for (int i = 1; i < MAXN; ++ i) inv[i] = pm(i, MOD - 2);
LL N, D, X;
while (scanf("%lld%lld%lld", &N, &D, &X) == 3 && N) {
LL ret = 0;
for (int k = 0; X * k <= N && k <= D; ++ k) {
LL now = C(N + D - 1 - k * X, N - k * X);
LL coef = C(D, k);
if (k & 1) ret -= now * coef % MOD;
else ret += now * coef % MOD;
ret = (ret + MOD) % MOD;
}
printf("%lld\n", ret);
}
return 0;
}
Problem H. Points and Lines
给出一个点和直线的语法, 求表达式的值.
搞好几何部分, 然后就直接表达式处理就好了.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double flt;
typedef pair<int, int> PII;
const flt eps = 1e-8;
struct Point {
flt x, y;
Point() {}
Point(flt x, flt y): x(x), y(y) {}
Point(const Point &a): x(a.x), y(a.y) {}
Point operator + (const Point &rhs) const {
return Point(x + rhs.x, y + rhs.y);
}
Point operator - (const Point &rhs) const {
return Point(x - rhs.x, y - rhs.y);
}
Point operator * (const flt k) const {
return Point(x * k, y * k);
}
Point operator / (const flt k) const {
return Point(x / k, y / k);
}
flt det(const Point &rhs) const {
return x * rhs.y - y * rhs.x;
}
flt dot(const Point &rhs) const {
return x * rhs.x + y * rhs.y;
}
flt sqr() const {
return x * x + y * y;
}
flt abs() const {
return hypot(x, y);
}
};
int sgn(flt x) {
if (x < -eps) return -1;
else return x > eps;
}
Point sym(const Point &O, const Point &A, const Point &B) {
if (sgn((A - O).det(B - O)) == 0) return O;
Point AB = B - A;
Point AP = AB * ((O - A).dot(AB) / AB.sqr());
return O + (A - O + AP) * 2.0;
}
Point inter(const Point &A, const Point &B, const Point &C, const Point &D) {
Point AB = B - A, CD = D - C;
return A + AB * (CD.det(C - A) / CD.det(AB));
}
struct Factor {
Point A, B;
int type;// 0 point, 1 line
Factor() {}
Factor(const Point &a) : A(a), type(0) {}
Factor(const Point &a, const Point &b): A(a), B(b), type(1) {}
Factor operator + (const Factor &rhs) const {
if (type == 0) {
if (rhs.type == 0) return Factor(A, rhs.A);
else return Factor(sym(A, rhs.A, rhs.B));
}
else if (type == 1) {
if (rhs.type == 0) return Factor(sym(rhs.A, A, B));
else return Factor(inter(A, B, rhs.A, rhs.B));
}
else assert(false);
}
void print() {
printf("%.10f %.10f\n", A.x, A.y);
}
};
char s[200], *p;
bool check(char c) {
return c == '-' || isdigit(c);
}
int getInt() {
int sgn = 1, ret = 0;
if (*p == '-') ++ p, sgn = -1;
while (isdigit(*p)) ret = ret * 10 + (*p - '0'), ++ p;
return sgn * ret;
}
Point getP() {
int x = getInt(); ++ p;
int y = getInt();
return Point(x, y);
}
int main() {
while (scanf("%s", s) == 1 && s[0] != '#') {
stack<char> op;
stack<Factor> num;
for (p = s; *p; ) {
if (*p == '(') {
if (check(*(p + 1))) {
++ p;
Factor now(getP());
++ p;
while (!op.empty() && op.top() == '@') {
Factor pre = num.top(); num.pop(); op.pop();
now = now + pre;
}
num.push(now);
}
else op.push('('), ++ p;
}
else if (*p == ')') {
assert(op.top() == '(');
op.pop(); ++ p;
Factor now = num.top(); num.pop();
while (!op.empty() && op.top() == '@') {
Factor pre = num.top(); num.pop(); op.pop();
now = now + pre;
}
num.push(now);
}
else if (*p == '@') {
op.push('@'); ++ p;
}
}
num.top().print();
}
return 0;
}
Problem I. Color the Map Extreme
给出一个$n$个点的平面图, 问最少需要多少种颜色染色, 使得任意两个相邻点颜色不一样.
数据规模: $1 \le n \le 35$
根据四色定理, 我们知道最多只需要4种颜色, 1种颜色和2种颜色都是很好判断的. 考虑如何判断3种颜色.
考虑某一个颜色, 把那些点单独拿出来的话肯定会形成一个独立集. 于是我们不妨枚举所有的最大独立集, 删去这些点, 剩下的问题就是是否可以把剩下的图2染色.
枚举最大独立集用BronKerbosch算法, 可以做到$O(3^{\frac{n}{3}})$
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
struct Point {
int x, y;
Point() {}
Point(int x, int y): x(x), y(y) {}
bool operator != (const Point &rhs) const {
return x != rhs.x || y != rhs.y;
}
Point operator + (const Point &rhs) const {
return Point(x + rhs.x, y + rhs.y);
}
Point operator - (const Point &rhs) const {
return Point(x - rhs.x, y - rhs.y);
}
Point operator * (const int k) const {
return Point(x * k, y * k);
}
int det(const Point &rhs) const {
return x * rhs.y - y * rhs.x;
}
int dot(const Point &rhs) const {
return x * rhs.x + y * rhs.y;
}
};
bool onSeg(Point &A, Point &B, Point &O) {// O on AB
return (A - O).det(B - O) == 0 && (A - O).dot(B - O) <= 0;
}
bool has_common(Point A, Point B, Point C, Point D) {
if (!((B - A).det(C - A) == 0 && (B - A).det(D - A) == 0)) return false;
if ((B - A).dot(D - C) > 0) swap(C, D);
assert((B - A).dot(D - C) < 0);
if (onSeg(A, B, C) && onSeg(A, B, D)) return true;
if (onSeg(C, D, A) && onSeg(C, D, B)) return true;
if (onSeg(A, B, D) && onSeg(C, D, B) && B != D) return true;
if (onSeg(C, D, A) && onSeg(A, B, C) && A != C) return true;
return false;
}
const int MAXN = 50;
vector<Point> poly[MAXN];
vector<int> G[MAXN];
int n;
bool check(vector<Point> &A, vector<Point> &B) {
for (size_t i = 0; i + 1 < A.size(); ++ i) {
for (size_t j = 0; j + 1 < B.size(); ++ j) {
if (has_common(A[i], A[i + 1], B[j], B[j + 1])) return true;
}
}
return false;
}
int col[MAXN], mark[MAXN];
bool dfs(int u, int c) {
if (col[u] != -1) return col[u] == c;
col[u] = c;
for (auto &v : G[u]) if (mark[v]) {
if (!dfs(v, c ^ 1)) return false;
}
return true;
}
bool bipartite() {
for (int i = 0; i < n; ++ i) col[i] = -1;
for (int i = 0; i < n; ++ i) {
if (col[i] == -1 && mark[i]) {
if (!dfs(i, 0)) return false;
}
}
return true;
}
typedef unsigned long long ULL;
int trail_zero(ULL s) {
return s ? __builtin_ctzll(s) : 64;
}
bool BronKerbosch(const vector<ULL> &g, ULL cur, ULL allow, ULL forbid) {
if (allow == 0 && forbid == 0) {
for (int i = 0; i < n; ++ i) mark[i] = !(cur >> i & 1);
return bipartite();
}
if (allow == 0) return false;
int pivot = trail_zero(allow | forbid);
ULL z = allow & ~g[pivot];
for (size_t u = trail_zero(z); u < g.size(); u += trail_zero(z >> (u + 1)) + 1) {
if (BronKerbosch(g, cur | (1ULL << u), allow & g[u], forbid & g[u])) return true;
allow ^= 1ULL << u; forbid |= 1ULL << u;
}
return false;
}
bool tricolor() {
vector<ULL> g(n, 0);
for (int i = 0; i < n; ++ i) g[i] = (1ULL << n) - 1 - (1ULL << i);
for (int i = 0; i < n; ++ i) {
for (auto &j : G[i]) g[i] ^= 1ULL << j;
}
return BronKerbosch(g, 0, (1ULL << n) - 1, 0);
}
int solve() {
bool flag = true;
for (int i = 0; i < n; ++ i) flag &= G[i].empty();
for (int i = 0; i < n; ++ i) mark[i] = 1;
if (flag) return 1;
else if (bipartite()) return 2;
else if (tricolor()) return 3;
else return 4;
}
int main() {
while (scanf("%d", &n) == 1 && n) {
for (int i = 0; i < n; ++ i) {
int m; scanf("%d", &m);
poly[i].clear(); G[i].clear();
for (int _ = 0; _ < m; ++ _) {
int x, y; scanf("%d%d", &x, &y);
poly[i].push_back(Point(x, y));
}
poly[i].push_back(poly[i][0]);
}
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < i; ++ j) {
if (check(poly[i], poly[j])) {
G[i].push_back(j);
G[j].push_back(i);
}
}
}
printf("%d\n", solve());
}
return 0;
}
Problem J. Website Tour
有$n$个网站, 两个网站之间可能有超链接相连(单向的). 对于某个网站$i$, 你可以换$t_i$的时间浏览它, 然后会获得$p_i$的愉悦值. 第$i$个网站最多可以浏览$k_i$次. 问时间$T$以内, 最多可以获得多少愉悦值.
注意: 超链接之间不需要花时间, 如果要重复浏览某个网站, 那么相邻两次浏览之间必须通过超链接.
数据规模: $1 \le n \le 10^2, 1 \le m \le 10^3, 1 \le T,p_i,t_i,k_i \le 10^4$
强联通分量缩点之后, 在有向无环图上搞个背包就好了.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 200, MAXT = 10000 + 10;
vector<int> G[MAXN];
bool mark[MAXN];
int p[MAXN], t[MAXN], k[MAXN];
int N, M, T;
namespace SCC {
vector<int> SCC[MAXN], SCCG[MAXN];
int low[MAXN], dfn[MAXN], ord[MAXN];
int scc_cnt;
void dfs(int x) {
static int stk[MAXN], top = 0, sz = 0;
stk[++ top] = x; low[x] = dfn[x] = ++ sz;
for (auto &y : G[x]) {
if (!dfn[y]) {
dfs(y); low[x] = min(low[x], low[y]);
}
else if (ord[y] == -1) low[x] = min(low[x], dfn[y]);
}
if (dfn[x] == low[x]) {
SCC[scc_cnt ++].clear();
do {
SCC[scc_cnt - 1].push_back(stk[top]);
ord[stk[top]] = scc_cnt - 1;
} while (x != stk[top --]);
}
}
void scc() {
memset(dfn, 0, sizeof(dfn));
memset(ord, -1, sizeof(ord));
scc_cnt = 0;
for (int i = 0; i < N; ++ i) {
if (!dfn[i]) dfs(i);
}
}
void build() {
for (int i = 0; i < scc_cnt; ++ i) {
SCCG[i].clear();
for (auto &u : SCC[i]) for (auto &v : G[u]) {
if (ord[v] != ord[u]) SCCG[i].push_back(ord[v]);
}
sort(SCCG[i].begin(), SCCG[i].end());
SCCG[i].resize(unique(SCCG[i].begin(), SCCG[i].end()) - SCCG[i].begin());
}
}
int deg[MAXN], self[MAXN];
int dp[MAXN][MAXT];
void update(int x) {
vector<PII> item;
for (auto &u : SCC[x]) {
for (int s = 1; s <= k[u]; s <<= 1) {
item.push_back(PII(s * t[u], s * p[u]));
k[u] -= s;
}
if (k[u]) item.push_back(PII(k[u] * t[u], k[u] * p[u]));
}
for (auto &v : item) {
for (int i = T; i >= v.first; -- i) {
dp[x][i] = max(dp[x][i], dp[x][i - v.first] + v.second);
}
}
}
int solve() {
scc(); build();
memset(deg, 0, sizeof(deg));
for (int i = 0; i < scc_cnt; ++ i) {
self[i] = (SCC[i].size() == 1 && mark[SCC[i][0]]);
for (auto &v : SCCG[i]) deg[v] ++;
for (int j = 0; j <= T; ++ j) dp[i][j] = 0;
}
queue<int> Q;
for (int i = 0; i < scc_cnt; ++ i) {
if (deg[i] == 0) Q.push(i);
}
while (!Q.empty()) {
int x = Q.front(); Q.pop();
if (SCC[x].size() == 1 && !self[x]) {
int u = SCC[x][0];
for (int j = T - t[u]; j >= 0; -- j) {
dp[x][j + t[u]] = max(dp[x][j + t[u]], dp[x][j] + p[u]);
}
}
else update(x);
for (auto &y : SCCG[x]) {
for (int i = 0; i <= T; ++ i) {
dp[y][i] = max(dp[y][i], dp[x][i]);
}
if (-- deg[y] == 0) Q.push(y);
}
}
int ret = 0;
for (int i = 0; i < scc_cnt; ++ i) {
for (int j = 0; j <= T; ++ j) {
ret = max(ret, dp[i][j]);
}
}
return ret;
}
}
int main() {
while (scanf("%d%d%d", &N, &M, &T) == 3 && N) {
for (int i = 0; i < N; ++ i) {
G[i].clear(); mark[i] = false;
scanf("%d%d%d", p + i, t + i, k + i);
}
for (int i = 0; i < M; ++ i) {
int u, v; scanf("%d%d", &u, &v);
-- u, -- v; G[u].push_back(v);
if (u == v) mark[u] = true;
}
printf("%d\n", SCC::solve());
}
return 0;
}
Problem K. Idempotent Filter
给出一个128位的图片过滤器, 问这个过滤器是不是幂等的, 即对于任意图片操作一次和操作两次的结果完全一样.
可以发现只要某个像素操作两次的结果完全一样就好了. 分析可以只需要枚举19个位就好了.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
char s[200];
bool check(int msk) {
static int bit[20];
for (int i = 0; i < 19; ++ i) bit[i] = (msk >> i) & 1;
int inner[7];
inner[0] = s[bit[13] | (bit[14] << 1) | (bit[12] << 2) | (bit[0] << 3) | (bit[1] << 4) | (bit[2] << 5) | (bit[3] << 6)];
inner[1] = s[bit[14] | (bit[15] << 1) | (bit[0] << 2) | (bit[1] << 3) | (bit[16] << 4) | (bit[3] << 5) | (bit[4] << 6)];
inner[2] = s[bit[12] | (bit[0] << 1) | (bit[11] << 2) | (bit[2] << 3) | (bit[3] << 4) | (bit[10] << 5) | (bit[5] << 6)];
inner[3] = s[bit[0] | (bit[1] << 1) | (bit[2] << 2) | (bit[3] << 3) | (bit[4] << 4) | (bit[5] << 5) | (bit[6] << 6)];
inner[4] = s[bit[1] | (bit[16] << 1) | (bit[3] << 2) | (bit[4] << 3) | (bit[17] << 4) | (bit[6] << 5) | (bit[18] << 6)];
inner[5] = s[bit[2] | (bit[3] << 1) | (bit[10] << 2) | (bit[5] << 3) | (bit[6] << 4) | (bit[9] << 5) | (bit[8] << 6)];
inner[6] = s[bit[3] | (bit[4] << 1) | (bit[5] << 2) | (bit[6] << 3) | (bit[18] << 4) | (bit[8] << 5) | (bit[7] << 6)];
for (int i = msk = 0; i < 7; ++ i) msk |= inner[i] << i;
int once = inner[3], twice = s[msk];
return once == twice;
}
int main() {
while (scanf("%s", s) == 1 && s[0] != '#') {
for (int i = 0; i < 128; ++ i) s[i] -= '0';
bool flag = true;
for (int msk = 0; msk < (1 << 19) && flag; ++ msk) {
flag &= check(msk);
}
puts(flag ? "yes" : "no");
}
return 0;
}
- No match
Comments (0)
