## 题目描述

ZS the Coder has drawn an undirected graph of $n$ vertices numbered from $0$ to $n-1$ and m edges between them. Each edge of the graph is weighted, each weight is a positive integer.
The next day, ZS the Coder realized that some of the weights were erased! So he wants to reassign positive integer weight to each of the edges which weights were erased, so that the length of the shortest path between vertices $s$ and $t$ in the resulting graph is exactly $L$. Can you help him?

## 代码

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
long long n, m, L, s, t, dist[1001], line[1001][1001];
bool flag, in[1001], sign[1001][1001];
void spfa(int p = -1, int q = -1) {
queue<int> que;
while (!que.empty()) que.pop();
memset(in, false, sizeof(in));
if (p == -1) {
memset(dist, 0x1f, sizeof(dist));
que.push(s), dist[s] = 0, in[s] = true;
} else {
if (dist[p] > dist[q]) p ^= q ^= p ^= q;
que.push(p), in[p] = true;
}
while (!que.empty()) {
long long u = que.front();
que.pop();
in[u] = false;
for (int i = 0; i < n; ++i) {
if (line[u][i] && dist[i] > dist[u] + line[u][i]) {
dist[i] = dist[u] + line[u][i];
if (!in[i]) que.push(i), in[i] = true;
}
}
}
}
int main()
{
cin >> n >> m >> L >> s >> t;
for (int i = 1; i <= m; ++i) {
long long x, y, w;
cin >> x >> y >> w;
line[x][y] = line[y][x] = w;
if (!w) sign[x][y] = sign[y][x] = true;
}
spfa();
if (dist[t] < L) {
cout << "NO" << endl;
return 0;
} else if (dist[t] > L) {
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
if (sign[i][j]) {
line[i][j] = line[j][i] = 1;
sign[i][j] = sign[j][i] = false;
spfa(i, j);
if (dist[t] <= L) {
line[i][j] = line[j][i] = L - dist[t] + 1;
flag = true; break;
}
}
}
if (flag) break;
}
} else flag = true;
if (!flag) cout << "NO" << endl;
else {
cout << "YES" << endl;
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
if (line[i][j] || sign[i][j]) {
cout << i << ' ' << j << ' ';
if (line[i][j]) cout << line[i][j];
if (sign[i][j]) cout << (long long) 1e18;
cout << endl;
}
}
}
}
return 0;
}


## 题目描述

As you might remember from the previous round, Vova is currently playing a strategic game known as Rage of Empires.
Vova managed to build a large army, but forgot about the main person in the army – the commander. So he tries to hire a commander, and he wants to choose the person who will be respected by warriors.
Each warrior is represented by his personality – an integer number $p_i$. Each commander has two characteristics — his personality $p_j$ and leadership $l_j$ (both are integer numbers). Warrior $i$ respects commander $j$ only if $p_i \oplus p_j \lt l_j$ ($x \oplus y$ is the bitwise excluding OR of $x$ and $y$).
Initially Vova’s army is empty. There are three different types of events that can happen with the army:

• 1 $p_i$ – one warrior with personality $p_i$ joins Vova’s army;
• 2 $p_i$ – one warrior with personality $p_i$ leaves Vova’s army;
• 3 $p_i$ $l_i$ – Vova tries to hire a commander with personality $p_i$ and leadership $l_i$.

For each event of the third type Vova wants to know how many warriors (counting only those who joined the army and haven’t left yet) respect the commander he tries to hire.

## 代码

#include <iostream>
using namespace std;
int q, o, p, l;
struct trie_tree {
int tot = 1;
struct node_type {
int sum, child[2];
} a[2000001];
void insert(int t) {
int r = 1; ++a[r].sum;
for (int i = 26; i >= 0; --i) {
if (!a[r].child[(t >> i) & 1]) a[r].child[(t >> i) & 1] = ++tot;
r = a[r].child[(t >> i) & 1], ++a[r].sum;
}
}
void remove(int t) {
int r = 1; --a[r].sum;
for (int i = 26; i >= 0; --i) {
r = a[r].child[(t >> i) & 1], --a[r].sum;
}
}
int find(int p, int l) {
int r = 1, ret = 0;
for (int i = 26; i >= 0; --i) {
int s = (p >> i) & 1, t = (l >> i) & 1;
if (t && a[r].child[s]) ret += a[a[r].child[s]].sum;
if (t && a[r].child[!s]) r = a[r].child[!s];
else if (!t && a[r].child[s]) r = a[r].child[s];
else break;
}
return ret;
}
} tree;
int main()
{
cin >> q;
while (q--) {
cin >> o;
switch (o) {
case 1: {
cin >> p, tree.insert(p);
break;
}
case 2: {
cin >> p, tree.remove(p);
break;
}
default: {
cin >> p >> l;
cout << tree.find(p, l) << endl;
}
}
}
return 0;
}


## 题目描述

Fox Ciel is participating in a party in Prime Kingdom. There are $n$ foxes there (include Fox Ciel). The $i$-th fox is $a_i$ years old.
They will have dinner around some round tables. You want to distribute foxes such that:

• each fox is sitting at some table,
• each table has at least 3 foxes sitting around it,
• the sum of ages of any two adjacent foxes around each table should be a prime number.

If $k$ foxes $f_1, f_2, \ldots, f_k$ are sitting around table in clockwise order, then for $1 \le i \le k-1$: $f_i$ and $f_{i+1}$ are adjacent, and $f_1$ and $f_k$ are also adjacent.
If it is possible to distribute the foxes in the desired manner, find out a way to do that.

## 代码

#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
struct edge {
int v, f, nxt;
} e[50001];
int n, nume = 1, top, src, sink, a[202], h[202], g[202], dist[202], que[202];
bool vis[202];
vector<int> ans[201];
void add_edge(int u, int v, int f) {
e[++nume].v = v, e[nume].f = f, e[nume].nxt = h[u], h[u] = nume;
e[++nume].v = u, e[nume].f = 0, e[nume].nxt = h[v], h[v] = nume;
}
void bfs() {
memset(dist, 0, sizeof(dist));
que[1] = src, dist[src] = 1;
int s = 0, t = 1;
while (s < t) {
int u = que[++s];
for (int i = h[u]; i; i = e[i].nxt) {
if (e[i].f && !dist[e[i].v]) {
que[++t] = e[i].v, dist[e[i].v] = dist[u] + 1;
}
}
}
}
int dfs(int u, int delta) {
if (u == sink) return delta;
int ret = 0;
for (int i = g[u]; i; i = e[i].nxt) {
if (e[i].f && dist[e[i].v] == dist[u] + 1) {
int dd = dfs(e[i].v, min(e[i].f, delta));
e[i].f -= dd, e[i ^ 1].f += dd;
if (e[i].f) g[u] = i;
delta -= dd, ret += dd;
}
}
return ret;
}
int max_flow() {
int ret = 0;
while (1) {
bfs();
if (!dist[sink]) return ret;
for (int i = 0; i <= n + 1; ++i) g[i] = h[i];
ret += dfs(src, 1e9);
}
}
bool is_prime(int t) {
int k = (int) sqrt(t);
for (int i = 2; i <= k; ++i) if (!(t % i)) return false;
return true;
}
void find(int u, int t) {
vis[u] = true, ans[t].push_back(u);
for (int i = h[u]; i; i = e[i].nxt) {
if (e[i].v && e[i].v != n + 1 && e[i].f == !(a[u] & 1) && !vis[e[i].v]) find(e[i].v, t);
}
}
int main()
{
cin >> n;
src = 0, sink = n + 1;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
if (a[i] & 1) add_edge(src, i, 2);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (a[i] & 1 && !(a[j] & 1) && is_prime(a[i] + a[j])) add_edge(i, j, 1);
}
}
max_flow();
for (int i = h[0]; i; i = e[i].nxt) {
if (e[i].f) {
cout << "Impossible" << endl;
return 0;
}
}
for (int i = h[n + 1]; i; i = e[i].nxt) {
if (e[i].f < 2) {
cout << "Impossible" << endl;
return 0;
}
}
for (int i = 1; i <= n; ++i) if (!vis[i]) top++, find(i, top);
cout << top << endl;
for (int i = 1; i <= top; ++i) {
cout << ans[i].size() << ' ';
for (vector<int>::iterator iter = ans[i].begin(); iter != ans[i].end(); ++iter) {
cout << *iter << ' ';
}
cout << endl;
}
return 0;
}


## 题目描述

Karen just got home from the supermarket, and is getting ready to go to sleep.
After taking a shower and changing into her pajamas, she looked at her shelf and saw an album. Curious, she opened it and saw a trading card collection.
She recalled that she used to play with those cards as a child, and, although she is now grown-up, she still wonders a few things about it.
Each card has three characteristics: strength, defense and speed. The values of all characteristics of all cards are positive integers. The maximum possible strength any card can have is $p$, the maximum possible defense is $q$ and the maximum possible speed is $r$.
There are $n$ cards in her collection. The $i$-th card has a strength $a_i$, defense $b_i$ and speed $c_i$, respectively.
A card beats another card if at least two of its characteristics are strictly greater than the corresponding characteristics of the other card.
She now wonders how many different cards can beat all the cards in her collection. Two cards are considered different if at least one of their characteristics have different values.

## 代码

#include <cstdio>
#include <algorithm>
using namespace std;
struct card {
long long a, b, c;
} c[500002];
bool operator < (card a, card b) {
return a.a < b.a;
}
long long n, p, q, r, pnt = 1, ans, s[500002], t[500002];
struct segment_tree {
struct node_type {
long long l, r, val, max, sum, tag;
node_type *child[2];
} *root;
void build_tree(node_type *root) {
if (root->l == root->r) return;
long long mid = root->l + root->r >> 1;
node_type *p, *q;
p = new node_type;
p->l = root->l, p->r = mid, p->val = p->max = p->sum = p->tag = 0;
q = new node_type;
q->l = mid + 1, q->r = root->r, q->val = q->max = q->sum = q->tag = 0;
build_tree(p), build_tree(q);
root->child[0] = p, root->child[1] = q;
}
void push_up(node_type *root) {
if (root->l != root->r) {
root->sum = root->child[0]->sum + root->child[1]->sum;
root->max = max(root->child[0]->max, root->child[1]->max);
}
}
void push_down(node_type *root) {
if (root->tag && root->l != root->r) {
root->child[0]->tag = root->child[0]->max = root->child[1]->tag = root->child[1]->max = root->tag;
root->child[0]->sum = (root->child[1]->l - root->child[0]->l) * root->tag;
root->child[1]->sum = (root->child[1]->r - root->child[0]->r) * root->tag;
}
root->tag = 0;
}
void insert_line(node_type *root, long long l, long long r, long long t) {
if (l == root->l && r == root->r) {
root->tag = root->max = t;
root->sum = (r - l + 1) * t;
return;
}
push_down(root);
if (r < root->child[1]->l) insert_line(root->child[0], l, r, t);
else if (l > root->child[0]->r) insert_line(root->child[1], l, r, t);
else {
insert_line(root->child[0], l, root->child[0]->r, t);
insert_line(root->child[1], root->child[1]->l, r, t);
}
push_up(root);
}
long long get(node_type *root, long long t) {
if (root->l == root->r) return root->l;
push_down(root);
if (root->child[1]->max < t) return get(root->child[0], t);
else return get(root->child[1], t);
}
long long get_sum(node_type *root, int l, int r) {
if (l == root->l && r == root->r) return root->sum;
push_down(root);
if (r < root->child[1]->l) return get_sum(root->child[0], l, r);
else if (l > root->child[0]->r) return get_sum(root->child[1], l, r);
else return get_sum(root->child[0], l, root->child[0]->r) + get_sum(root->child[1], root->child[1]->l, r);
}
} tree;
int main()
{
scanf("%lld%lld%lld%lld", &n, &p, &q, &r);
tree.root = new segment_tree::node_type;
tree.root->l = 0, tree.root->r = q, tree.root->val = tree.root->max = tree.root->sum = tree.root->tag = 0;
tree.build_tree(tree.root);
for (int i = 1; i <= n; ++i) {
scanf("%lld%lld%lld", &c[i].a, &c[i].b, &c[i].c);
}
sort(c + 1, c + n + 1);
s[n] = c[n].b, t[n] = c[n].c;
for (int i = n - 1; i; --i) {
s[i] = max(s[i + 1], c[i].b);
t[i] = max(t[i + 1], c[i].c);
}
tree.insert_line(tree.root, 0, 0, q + 1);
long long tmp;
for (int i = 1, j = 1; i <= p; ++i) {
for (; j <= n && c[j].a < i; ++j) {
tmp = tree.get(tree.root, c[j].c);
if (tmp >= c[j].b) continue;
tree.insert_line(tree.root, tmp + 1, c[j].b, c[j].c);
}
tmp = max(s[j], tree.get(tree.root, t[j] + 1));
ans += (tmp - s[j]) * r + (q - tmp) * (r - t[j]);
if (tmp > s[j]) ans -= tree.get_sum(tree.root, s[j] + 1, tmp);
}
printf("%lld\n", ans);
return 0;
}


## Limits on Integer Constants

Constant Meaning Value
CHAR_BIT Number of bits in the smallest variable that is not a bit field. 8
SCHAR_MIN Minimum value for a variable of type signed char. –128
SCHAR_MAX Maximum value for a variable of type signed char. 127
UCHAR_MAX Maximum value for a variable of type unsigned char. 255 (0xff)
CHAR_MIN Minimum value for a variable of type char. –128; 0 if /J option used
CHAR_MAX Maximum value for a variable of type char. 127; 255 if /J option used
MB_LEN_MAX Maximum number of bytes in a multicharacter constant. 5
SHRT_MIN Minimum value for a variable of type short. –32768
SHRT_MAX Maximum value for a variable of type short. 32767
USHRT_MAX Maximum value for a variable of type unsigned short. 65535 (0xffff)
INT_MIN Minimum value for a variable of type int. –2147483648
INT_MAX Maximum value for a variable of type int. 2147483647
UINT_MAX Maximum value for a variable of type unsigned int. 4294967295 (0xffffffff)
LONG_MIN Minimum value for a variable of type long. –2147483648
LONG_MAX Maximum value for a variable of type long. 2147483647
ULONG_MAX Maximum value for a variable of type unsigned long. 4294967295 (0xffffffff)
_I64_MIN Minimum value for a variable of type __int64 -9223372036854775808
_I64_MAX Maximum value for a variable of type __int64 9223372036854775807
_UI64_MAX Maximum value for a variable of type unsigned __int64 18446744073709551615 (0xffffffffffffffff)

## Limits on Floating-Point Constants

Constant Meaning Value
FLT_DIG DBL_DIG LDBL_DIG Number of digits, q, such that a floating-point number with q decimal digits can be rounded into a floating-point representation and back without loss of precision. 6 15 15
FLT_EPSILON DBL_EPSILON LDBL_EPSILON Smallest positive number x, such that x + 1.0 is not equal to 1.0. 1.192092896e–07F 2.2204460492503131e–016 2.2204460492503131e–016
FLT_GUARD 0
FLT_MANT_DIG DBL_MANT_DIG LDBL_MANT_DIG Number of digits in the radix specified by FLT_RADIX in the floating-point significand. The radix is 2; hence these values specify bits. 24 53 53
FLT_MAX DBL_MAX LDBL_MAX Maximum representable floating-point number. 3.402823466e+38F 1.7976931348623158e+308 1.7976931348623158e+308
FLT_MAX_10_EXP DBL_MAX_10_EXP LDBL_MAX_10_EXP Maximum integer such that 10 raised to that number is a representable floating-point number. 38 308 308
FLT_MAX_EXP DBL_MAX_EXP LDBL_MAX_EXP Maximum integer such that FLT_RADIX raised to that number is a representable floating- point number. 128 1024 1024
FLT_MIN DBL_MIN LDBL_MIN Minimum positive value. 1.175494351e–38F 2.2250738585072014e–308 2.2250738585072014e–308
FLT_MIN_10_EXP DBL_MIN_10_EXP LDBL_MIN_10_EXP Minimum negative integer such that 10 raised to that number is a representable floating- point number. –37

–307

–307

FLT_MIN_EXP DBL_MIN_EXP LDBL_MIN_EXP Minimum negative integer such that FLT_RADIX raised to that number is a representable floating-point number. –125

–1021

–1021

FLT_NORMALIZE 0
FLT_ROUNDS _DBL_ROUNDS _LDBL_ROUNDS Rounding mode for floating-point addition. 1 (near) 1 (near) 1 (near)

## 题目描述

On the way home, Karen decided to stop by the supermarket to buy some groceries.
She needs to buy a lot of goods, but since she is a student her budget is still quite limited. In fact, she can only spend up to $b$ dollars.
The supermarket sells $n$ goods. The $i$-th good can be bought for $c_i$ dollars. Of course, each good can only be bought once.
Lately, the supermarket has been trying to increase its business. Karen, being a loyal customer, was given $n$ coupons. If Karen purchases the $i$-th good, she can use the $i$-th coupon to decrease its price by $d_i$. Of course, a coupon cannot be used without buying the corresponding good.
There is, however, a constraint with the coupons. For all $i \ge 2$, in order to use the $i$-th coupon, Karen must also use the $x_i$-th coupon (which may mean using even more coupons to satisfy the requirement for that coupon).
Karen wants to know the following. What is the maximum number of goods she can buy, without exceeding her budget $b$?

## 算法分析

$$s_i=1, \; f_{i, 0, 0}=0, \; f_{i, 1, 0}=c_i, \; f_{i, 1, 1}=c_i-d_i$$

\begin{align} f_{i, j + k, 0}&=\min(f_{i, j, 0} + f_{u, k, 0}) \\ f_{i, j + k, 1}&=\min(f_{i, j, 1} + \min(f_{u, k, 0}, f_{u, k, 1})) \end{align}

## 代码

#include <iostream>
#include <cstring>
using namespace std;
struct edge {
int v, nxt;
} e[5001];
long long n, b, tot, h[5001], c[5001], d[5001], x, s[5001], f[5001][5001][2];
void add_edge(int u, int v) {
e[++tot].v = v;
e[tot].nxt = h[u];
h[u] = tot;
}
void dfs(int t) {
for (int k = h[t]; k; k = e[k].nxt) {
dfs(e[k].v);
for (int i = s[t]; i >= 0; --i) {
for (int j = 0; j <= s[e[k].v]; ++j) {
f[t][i + j][0] = min(f[t][i + j][0], f[t][i][0] + f[e[k].v][j][0]);
f[t][i + j][1] = min(f[t][i + j][1], f[t][i][1] + min(f[e[k].v][j][0], f[e[k].v][j][1]));
}
}
s[t] += s[e[k].v];
}
}
int main()
{
cin >> n >> b;
memset(f, 0x7f, sizeof(f));
for (int i = 1; i <= n; ++i) {
cin >> c[i] >> d[i];
s[i] = 1;
f[i][0][0] = 0;
f[i][1][0] = c[i];
f[i][1][1] = c[i] - d[i];
if (i - 1) {
cin >> x;
}
}
dfs(1);
for (int i = n; i >= 0; --i) {
if (min(f[1][i][0], f[1][i][1]) <= b) {
cout << i << endl;
break;
}
}
return 0;
}


## 题目描述

Karen has just arrived at school, and she has a math test today!
The test is about basic addition and subtraction. Unfortunately, the teachers were too busy writing tasks for Codeforces rounds, and had no time to make an actual test. So, they just put one question in the test that is worth all the points.
There are $n$ integers written on a row. Karen must alternately add and subtract each pair of adjacent integers, and write down the sums or differences on the next row. She must repeat this process on the values on the next row, and so on, until only one integer remains. The first operation should be addition.
Note that, if she ended the previous row by adding the integers, she should start the next row by subtracting, and vice versa.
The teachers will simply look at the last integer, and then if it is correct, Karen gets a perfect score, otherwise, she gets a zero for the test.
Karen has studied well for this test, but she is scared that she might make a mistake somewhere and it will cause her final answer to be wrong. If the process is followed, what number can she expect to be written on the last row?
Since this number can be quite large, output only the non-negative remainder after dividing it by $10^9+7$.

## 算法分析

\begin{align} n=1,\;&ans=a_1 \\ n=2,\;&ans=a_1+a_2 \\ n=3,\;&ans=a_1+2a_2-a_3 \\ n=4,\;&ans=a_1-a_2+a_3-a_4 \\ n=5,\;&ans=a_1+2a_3+a_5 \\ n=6,\;&ans=a_1+a_2+2a_3+2a_4+a_5+a_6 \\ n=7,\;&ans=a_1+2a_2+a_3+4a_4-a_5+2a_6-a_7 \\ n=8,\;&ans=a_1-a_2+3a_3-3a_4+3a_5-3a_6+a_7-a_8 \\ n=9,\;&ans=a_1+4a_3+6a_5+4a_7+a_9 \\ n=10,\;&ans=a_1+a_2+4a_3+4a_4+6a_5+6a_6+4a_7+4a_8+a_9+a_{10} \\ n=11,\;&ans=a_1+2a_2+3a_3+8a_4+2a_5+12a_6-2a_7+8a_8-3a_9+2a_{10}-a_{11} \\ n=12,\;&ans=a_1-a_2+5a_3-5a_4+10a_5-10a_6+10a_7-10a_8+5a_9-5a_{10}+a_{11}-a_{12} \end{align}

## 代码

#include <iostream>
#define MOD 1000000007
using namespace std;
long long n, t, r[3], ans, c[200001], a[200001];
void extend_gcd(long long a, long long b, long long &x, long long &y) {
if (!b) {
x = 1, y = 0;
return;
}
extend_gcd(b, a % b, y, x);
y -= a / b * x;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
t = (n - 1) / 4 << 1;
c[0] = 1;
for (int i = 0; i < t; ++i) {
long long x, y;
extend_gcd(i + 1, MOD, x, y);
c[i + 1] = c[i] * (t - i) % MOD * x % MOD;
if (c[i + 1] < 0) c[i + 1] += MOD;
}
for (int i = 0; i <= t; ++i) {
r[0] += c[i] * a[(i << 1) + 1] % MOD;
if (!(n & 1)) r[0] += c[i] * a[(i << 1) + 2] % MOD;
}
r[0] %= MOD;
if ((n - 1) % 4 < 2) cout << r[0] << endl;
else {
for (int i = 0; i <= t; ++i) {
r[1] += c[i] * a[(i << 1) + 2] % MOD;
if (!(n & 1)) r[1] -= c[i] * a[(i << 1) + 3] % MOD;
}
r[1] %= MOD;
for (int i = 0; i <= t; ++i) {
r[2] += c[i] * a[(i << 1) + 3] % MOD;
if (!(n & 1)) r[2] += c[i] * a[(i << 1) + 4] % MOD;
}
r[2] %= MOD;
if (n & 1) ans = (r[0] + (r[1] << 1) - r[2]) % MOD;
else ans = (r[0] - (r[1] << 1) - r[2]) % MOD;
if (ans < 0) ans += MOD;
cout << ans << endl;
}
return 0;
}


## 题目描述

On the way to school, Karen became fixated on the puzzle game on her phone!
The game is played as follows. In each level, you have a grid with $n$ rows and $m$ columns. Each cell originally contains the number $0$.
One move consists of choosing one row or column, and adding $1$ to all of the cells in that row or column.
To win the level, after all the moves, the number in the cell at the $i$-th row and $j$-th column should be equal to $g_{i, j}$.
Karen is stuck on one level, and wants to know a way to beat this level using the minimum number of moves. Please, help her with this task!

## 代码

#include <iostream>
using namespace std;
int n, m, p, q, top, f, a[101][101], ans[100001], mode[100001];
bool check(int t, int mode) {
if (!mode) {
for (int i = 1; i <= m; ++i) if (!a[t][i]) return false;
for (int i = 1; i <= m; ++i) --a[t][i];
return true;
} else {
for (int i = 1; i <= n; ++i) if (!a[i][t]) return false;
for (int i = 1; i <= n; ++i) --a[i][t];
return true;
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> a[i][j];
}
}
p = n, q = m;
if (p > q) {
p ^= q ^= p ^= q;
f = 1;
}
for (int i = 1; i <= p; ++i) while (check(i, f)) {
ans[++top] = i;
mode[top] = f;
}
for (int i = 1; i <= q; ++i) while (check(i, !f)) {
ans[++top] = i;
mode[top] = !f;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i][j]) {
cout << -1 << endl;
return 0;
}
}
}
cout << top << endl;
for (int i = 1; i <= top; ++i) {
if (!mode[i]) cout << "row ";
else cout << "col ";
cout << ans[i] << endl;
}
return 0;
}


## 题目描述

Fox Ciel is playing a game. In this game there is an infinite long tape with cells indexed by integers (positive, negative and zero). At the beginning she is standing at the cell $0$.
There are also $n$ cards, each card has $2$ attributes: length $l_i$ and cost $c_i$. If she pays $c_i$ dollars then she can apply $i$-th card. After applying $i$-th card she becomes able to make jumps of length $l_i$, i.e. from cell $x$ to cell $(x-l_i)$ or cell $(x+l_i)$.
She wants to be able to jump to any cell on the tape (possibly, visiting some intermediate cells). For achieving this goal, she wants to buy some cards, paying as little money as possible.
If this is possible, calculate the minimal cost.

## 算法分析

$$f_{(k, l_i)}=\min(f_k+c_i)$$

## 代码

#include <iostream>
#include <map>
using namespace std;
int n, l[301], c[301];
map<int, int> f;
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> l[i];
}
for (int i = 1; i <= n; ++i) {
cin >> c[i];
}
f[0] = 0;
for (int i = 1; i <= n; ++i) {
for (map<int, int>::iterator iter = f.begin(); iter != f.end(); ++iter) {
int t = gcd(iter->first, l[i]);
if (!f.count(t)) f[t] = iter->second + c[i];
else f[t] = min(f[t], iter->second + c[i]);
}
}
if (!f[1]) cout << -1 << endl;
else cout << f[1] << endl;
return 0;
}


## 题目描述

Fox Ciel is going to publish a paper on FOCS (Foxes Operated Computer Systems, pronounce: “Fox”). She heard a rumor: the authors list on the paper is always sorted in the lexicographical order.
After checking some examples, she found out that sometimes it wasn’t true. On some papers authors’ names weren’t sorted in lexicographical order in normal sense. But it was always true that after some modification of the order of letters in alphabet, the order of authors becomes lexicographical!
She wants to know, if there exists an order of letters in Latin alphabet such that the names on the paper she is submitting are following in the lexicographical order. If so, you should find out any such order.
Lexicographical order is defined in following way. When we compare $s$ and $t$, first we find the leftmost position with differing characters: $s_i \neq t_i$. If there is no such position (i.e. $s$ is a prefix of $t$ or vice versa) the shortest string is less. Otherwise, we compare characters $s_i$ and $t_i$ according to their order in alphabet.

## 代码

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct author {
int id;
string name;
} a[101];
bool cmp(author a, author b) {
return a.name < b.name;
}
int n, in[26];
bool graph[26][26];
queue<int> que;
string ans;
int main()
{
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i].name;
a[i].id = i;
}
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i < n; ++i) {
for (int j = i + 1; j <= n; ++j) {
int p = 0, len1 = a[i].name.length(), len2 = a[j].name.length();
while (p < len1 && p < len2 && a[i].name[p] == a[j].name[p]) ++p;
if (p == len1 && p < len2 && a[i].id > a[j].id) {
cout << "Impossible" << endl;
return 0;
}
if (p < len1) {
if (a[i].id < a[j].id) graph[a[i].name[p] - 'a'][a[j].name[p] - 'a'] = true;
else graph[a[j].name[p] - 'a'][a[i].name[p] - 'a'] = true;
}
}
}
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < 26; ++j) {
if (graph[i][j]) ++in[j];
}
}
for (int i = 0; i < 26; ++i) {
if (!in[i]) que.push(i);
}
while (!que.empty()) {
int t = que.front();
que.pop();
for (int i = 0; i < 26; ++i) {
if (graph[t][i]) {
--in[i];
if (!in[i]) que.push(i);
}
}
ans += t + 'a';
}
if (ans.length() < 26) {
cout << "Impossible" << endl;
} else {
cout << ans << endl;
}
return 0;
}