Japanese Alumni Group Autumn Contest 2014

zimpha posted @ Thu, 12 Mar 2015 00:53:19 +0800 in JAG , 579 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

Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter