五月 | 2018

题面：http://codeforces.com/gym/101206/attachments/download/5010/ccpc-20162017-finals-en.pdf

（更新中）

Problem A. The Third Cup is Free

有n杯咖啡，每三杯咖啡中最便宜的那杯可以免单，求最小花费。

题解

签到题。从大到小排好序后，每三个免一个即可。

代码：(by Roundgod)

#include<bits/stdc++.h>
#define MAXN 100005
#define INF 1000000000
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int t,n,a[MAXN];
int main()
{
    scanf("%d",&t);
    int kase=0;
    while(t--)
    {
        kase++;
        printf("Case #%d: ",kase);
        scanf("%d",&n);
        int sum=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d", &a[i]);
            sum += a[i];
        }
        sort(a,a+n);
        for(int i=n-3;i>=0;i-=3)
            sum-=a[i];
        printf("%d\n",sum);
    }
    return 0;
}

Problem B. Wash

给定L件脏衣服，N台洗衣机，D台烘干机。第i台洗衣机要花Wi时间洗一件脏衣服，第j台烘干机要花Dj时间烘干一件衣服。衣服必须先洗完再烘干。所有机器可以并行工作。问洗完并烘干所有衣服要多少时间。

数据范围：$1 \leq L \leq 10^6, 1 \leq N, M \leq 10^5, 1 \leq W_i, D_i \leq 10^9 $

题解

我们先考虑只洗衣服该如何安排。显然每台洗衣机中间不会停止工作，否则我们将后面的任务向前移动，不会得到一个更差的解。这样，第i台洗衣机洗完地j件衣服的时间就是$w_{ij} = jW_{i}$。只要选取前L小的$T_{ij}$即可。为便于实现，可用优先队列。

同理，可处理出前L小的$d_{ij}$烘干时间。下面我们就是要求一个$w_{ij}$和$d_{ij}$的完美匹配，使得对应的$w_{ij}$和$d_{ij}$的和的最大值最小。这只需要将$w_{ij}$正向排序，$d_{ij}$反向排序，然后一一匹配即可。容易证明，这样匹配一定是最优的。

代码：(by sy_chen)

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
  __func__, ##__VA_ARGS__)
#else
# define _debug(...) (void(0))
#endif

#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ull;

int l, n, m;
LL w[100006], d[100006];
LL t1[1000006], t2[1000006];

typedef pair<LL, int> p;

int main() {
  int T; scanf("%d", &T);
  Rep (t, T) {
    priority_queue<p, vector<p>, greater<p> > q1, q2;
    scanf("%d%d%d", &l, &n, &m);
    rep (i, n) {
      int a; scanf("%d", &a);
      w[i] = a;
      q1.push({w[i], i});
    }
    rep (i, m) {
      int a; scanf("%d", &a);
      d[i] = a;
      q2.push({d[i], i});
    }
    rep (i, l) {
      LL val; int id;
      tie(val, id) = q1.top(); q1.pop();
      _debug("i=%d, val=%lld, id=%lld, l-1-i=%d", i, val, id, l-1-i);
      t1[i] = val;
      q1.push({val+w[id], id});
    }
    rep (i, l) {
      LL val; int id;
      tie(val, id) = q2.top(); q2.pop();
      _debug("i=%d, val=%lld, id=%lld, l-1-i=%d", i, val, id, l-1-i);
      t2[l-1-i] = val;
      q2.push({val+d[id], id});
    }
    LL ans = 0;
    rep (i, l) {
      ans = max(ans, t1[i] + t2[i]);
    }
    cout << "Case #" << t << ": " << ans << endl;
  }
  return 0;
}

Problem C. Mr. Panda and Survey

Problem D. Game Leader

Problem E. Problem Buyer

Problem F. Periodical Cicadas

Problem G. Pandaland

给出一个4000个点的带权无向图，求图中的最小权环。

题解

枚举所有边，删去该边后，求这条边两点间的最短路，然后加上该边的权值，取最小值即可。

注意，当图中不含圈时，要输出0（而不是-1）（补题的时候因为这个原因WA了5发，qaq…

代码：(by aequa)

#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
    __func__, ##__VA_ARGS__)
#else 
# define _debug(...) ((void) 0)
#endif
#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ULL;

#define int LL
#undef INT_MAX
#define INT_MAX LLONG_MAX

typedef pair<int, int> pt;


struct Sol {
  int n = 0;
  map<pt, int> mp;
  vector<pair<int, int>> edges;
  vector<vector<int>> adj;

  int getID(int x, int y) {
    auto ptr = mp.find({x, y});
    if (ptr != mp.end()) return ptr->second;
    mp[{x, y}] = n;
    adj.push_back({});
    return n++;
  }
  
  int ans = INT_MAX / 2;
  int d[10000];
  bool done[10000];

  void dijkstra(int src) {
    priority_queue<pt, vector<pt>, greater<pt>> q;

    fill(d, d+n, INT_MAX / 2);
    d[src] = 0;
    fill(done, done+n, false);
    q.push({0, src});
    while (q.size()) {
      int u = q.top().second; q.pop();
      if (done[u]) continue;
      done[u] = 1;
      for (int id : adj[u]) {
        int v, w; tie(v, w) = edges[id];
        if (d[v] > d[u] + w) {
          d[v] = d[u] + w;
          if (d[v] < ans) q.push({d[v], v});
        }
      }
    }
  }

  Sol(int t) {
    int m; cin >> m;
    edges.resize(m+m);
    rep (i, m) {
      int x1, y1, x2, y2, w;
      int id1, id2;
      cin >> x1 >> y1 >> x2 >> y2 >> w;
      id1 = getID(x1, y1); id2 = getID(x2, y2);
      edges[i<<1] = {id2, w};
      edges[i<<1|1] = {id1, w};
      adj[id1].push_back(i<<1);
      adj[id2].push_back(i<<1|1);
    }
    rep (u, n) {
      for (int id : adj[u]) {
        int v, w;
        tie(v, w) = edges[id];
        edges[id].second = edges[id^1].second = INT_MAX / 2;
        dijkstra(u);
        ans = min(ans, d[v] + w);
        edges[id].second = edges[id^1].second = w;
      }
    }
    if (ans >= INT_MAX / 2) ans = 0;
    cout << "Case #" << t << ": " << ans << endl;
  }
};

int32_t main() {
  int T; cin >> T;
  Rep (t, T) {
    Sol sol(t);
  }
  return 0;
}

Problem H. Engineer Assignment

Problem I. Mr. Panda and Crystal

有N种宝石，每种宝石有一些价值。有些宝石可以直接由法力值合成。此外，还存在K种合成方案，可以利用若干已有的宝石合成新的宝石。给定初始的法力值M，求能够合成的宝石的价值的最大值。

数据范围：$1 \leq M \leq 10000, 1 \leq N \leq 200, 1 \leq K \leq 200$

题解

背包的变形题。本题主要的问题是，一种宝石可能有多种获得方法，除了可以直接用法力值合成外，还有可能存在多种合成该宝石的方案。我们希望预处理出来（直接或间接）获得该种宝石的最小法力值消耗。由于更新一种宝石的最小法力值消耗可能会影响其他宝石的最小法力值消耗，这很像最短路中更新某个节点的距离会影响其他节点的距离，因此可以采用Bellman-Ford算法，迭代更新直到无法更新为止。显然这么做的复杂度是$N^2K$的。预处理出来后，直接套多重背包即可。

代码：(by sy_chen)

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
  __func__, ##__VA_ARGS__)
#else
# define _debug(...) (void(0))
#endif

#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ull;

int m, n, k;
LL c[256], v[256];

vector<int> dep[205];
//   id                id  cnt
pair<int, vector<pair<int, int>>> formula[205];

bool flag = false;

void update(int i) {
  LL tot = 0;
  int id = formula[i].first;
  for (auto& item : formula[i].second) {
    tot += c[item.first] * item.second;
  }
  if (tot < c[id]) {
    _debug("update %d!", formula[i].first);
    c[formula[i].first] = tot;
    flag = true;
  }
}

LL dp[10005];

int main() {
  int T; scanf("%d", &T);
  Rep (t, T) {
    scanf("%d%d%d", &m, &n, &k);
    Rep (i, n) {
      int tp; scanf("%d", &tp);
      int co = INT_MAX, va = 0;
      if (tp == 0) {
        scanf("%d", &va);
      } else {
        scanf("%d%d", &co, &va);
      }
      c[i] = co;
      v[i] = va;
    }
    _debug("!");
    rep (i, k) {
      int x, y;
      scanf("%d%d", &x, &y);
      formula[i].first = x;
      formula[i].second.resize(y);
      rep (j, y) {
        int u, v;
        scanf("%d%d", &u, &v);
        formula[i].second[j] = {u, v};
      }
    }
    _debug("!");
    do { // bellman-ford
      flag =  false;
      rep (i, k) update(i);
    } while (flag);
    memset(dp, 0, sizeof dp);
    Rep (i, n) {
      for (int w = c[i]; w <= m; w++) {
        dp[w] = max(dp[w], dp[w - c[i]] + v[i]);
      }
    }
    printf("Case #%d: %d\n", t, int(dp[m]));
  }
  return 0;
}

Problem J. Worried School

Problem K. Lazors

神仙题。

Problem L. Daylight Saving Time

每年的三月的第二个星期日的2点整，将时间拨快1小时，进入夏令时（PST）；每年的十一月的第一个星期日的2点整，将时间拨慢1小时，进入标准时（PDT）。给一个日期和时间，判断该时间是PST，PDT，两者都有可能或是两者都不可能。时间在2007-01-01 00:00:00和2100-12-31 23:59:59之间。

题解

只要预处理出每一天的类型（一定是PST，一定是PDT，从PST变换为PDT，从PDT变换为PST），然后分情况讨论即可。

实现的时候要注意处理闰年的情况。除2100年外，年数是4的倍数就是闰年。

代码：(by sy_chen)

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
  __func__, ##__VA_ARGS__)
#else
# define _debug(...) (void(0))
#endif

#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned long long ull;

enum {
  A, B, C, D
};

const int  mday[13] = { 0,
  31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};

int type = A;
int yy = 2007, mm = 1, dd = 1;
int wday = 1;

bool isleap(int y) {
  if (y % 4 == 0  && y != 2100) return true;
  return false;
}

void adv_year() {
  yy++;
}

void adv_month() {
  mm++;
  if (mm > 12) {
    mm = 1;
    adv_year();
  }
}

int advan() {
  dd++;
  wday ++;
  if (wday > 7) wday = 1;
  int mmday = mday[mm];
  if (mm == 2 && isleap(yy)) mmday++;
  if (dd > mmday) {
    dd = 1;
    adv_month();
  }
  if (mm == 3 && wday == 7 && dd > 7 && dd <= 14) {
    type = C;
    return B; 
  }
  if (mm == 11 && wday == 7 && dd <= 7) {
    type = A;
    return D;
  }
  return type;
}

string genstr() {
  char buf[100];
  sprintf(buf, "%04d-%02d-%02d", yy, mm, dd);
  return string(buf);
}

map<string, int> m;

void prep() {
  m[genstr()] = type;
  do {
    int tp = advan();
    m[genstr()] = tp;

  } while (yy <= 2100);
}


int main() {
  prep();
  string str;
  char tim[20];
  int hh;
  int T;
  cin >> T;
  Rep(t, T) {
    cin >> str >> tim;
    sscanf(tim, "%d", &hh);
    switch (m[str]) {
      case A:
        printf("Case #%d: PST\n", t);
        break;
      case B:
        if (hh < 2) {
          printf("Case #%d: PST\n", t);
        } else if (hh >= 3) {
          printf("Case #%d: PDT\n", t);
        } else {
          printf("Case #%d: Neither\n", t);
        } 
        break;
      case C:
        printf("Case #%d: PDT\n", t);
        break;
      case D:
        if (hh < 1) {
          printf("Case #%d: PDT\n", t);
        } else if (hh >= 2) {
          printf("Case #%d: PST\n", t);
        } else {
          printf("Case #%d: Both\n", t);
        } 
        break;
    }
  }
  return 0;
}

aequa

Programming on the shoulders of giants.

月度归档：2018年05月

2018江苏省大学生程序设计竞赛（JSCPC）总结

2016 China Collegiate Programming Contest Final 题解

Problem A. The Third Cup is Free

Problem B. Wash

Problem C. Mr. Panda and Survey

Problem D. Game Leader

Problem E. Problem Buyer

Problem F. Periodical Cicadas

Problem G. Pandaland

Problem H. Engineer Assignment

Problem I. Mr. Panda and Crystal

Problem J. Worried School

Problem K. Lazors

Problem L. Daylight Saving Time