# 2016 China Collegiate Programming Contest Final 题解

（更新中）

### Problem A. The Third Cup is Free

#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

#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 G. Pandaland

#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;

int getID(int x, int y) {
auto ptr = mp.find({x, y});
if (ptr != mp.end()) return ptr->second;
mp[{x, y}] = n;
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};
}
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 I. Mr. Panda and Crystal

#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 L. Daylight Saving Time

#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;
}

yy++;
}

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

dd++;
wday ++;
if (wday > 7) wday = 1;
int mmday = mday[mm];
if (mm == 2 && isleap(yy)) mmday++;
if (dd > mmday) {
dd = 1;
}
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 {
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;
}

# 线性代数相关OJ题选讲

### Fast Matrix Calculation

2014 Multi-University Training Contest 9, available at HDUOJ 4965

Step 1. 计算 $N \times N$ 的矩阵 $C = AB$.
Step 2. 计算 $M = C^{N \times N} \bmod 6$.
Step 3. 输出 $M$ 中所有元素的和.

$M = (AB)^{N \times N} = A (BA)^{N \times N – 1} B$

### Matrix Multiplication

2014 Multi-University Training Contest 5, available at HDUOJ 4920

$AB = (A_1 – A_2)(B_1 – B_2) = A_1B_1 – A_1B_2 – A_2B_1 + A_2B_2$

（当然，使用其他一些优秀的卡常方法也能过这题）

### Matrix Revolution

HDUOJ 1759

$A + A^2 + \cdots + A^k$

$A$ 是稀疏矩阵，用 $m$ 个三元组 $(a, b, c)$ 表示，每个三元组代表 $A_{ab} = c$。此外，保证主对角线上的元素全为 1。其他元素均为0。

$(0 \leq n \leq 1000, 0 \leq m \leq 10n, n < k < 10^{100}, 0 < c < 10^9)$

### Matrix Multiplication

POJ 3318

（当然，使用三次方的算法加一些优秀的卡常，也许也能过）

Remark:

### Square

UVA 11542, also available at vjudge

$1 \leq T \leq 30$, $1 \leq n \leq 100$， 所有整数在 1 和 $10^{15}$ 之间。整数的素因子最多为 500。

# 2017-2018年问题求解（三）期末上机考试 Day2 题解

### D. 旅游路线

• 部分数据满足 $latex 1≤n≤20, 1≤m≤100, 1≤s_i≤5, 1≤k_i, c≤1000$;
• 部分数据满足 $latex 1≤n≤1000, 1≤m≤50000, 1≤s_i≤200, 1≤k_i, c≤1000$;
• 部分数据满足 $latex 1≤n≤30000, 1≤m≤2*10^5, s_i=1, 1≤k_i, c≤1000$;
• 部分数据满足 $latex 1≤n≤5000, 1≤m≤2*10^5, 1≤s_i≤50, 1≤k_i, c≤1000$。

# 2017-2018年问题求解（三）期末上机考试 Day1 题解

### A. 智能机器

$$n = q_1^{a_1} q_2^{a_2} \cdots q_m^{a_m}$$

$$d(n) = (1+a_1)(1+a_2)\cdots(1+a_m)$$

$$d(n^k) = (1+ka_1)(1+ka_2)\cdots(1+ka_m)$$