## 题目描述

Little X has met the following problem recently.
Let’s define $f(x)$ as the sum of digits in decimal representation of number $x$ (for example, $f(1234)=1+2+3+4$). You are to calculate $\sum_{i=l}^r f(i) \bmod a$.
Of course Little X has solved this problem quickly, has locked it, and then has tried to hack others. He has seen the following C++ code:

ans = solve(l, r) % a;
if (ans <= 0) ans += a;


This code will fail only on the test with $\sum_{i=l}^r f(i) \equiv 0 \pmod a$. You are given number $a$, help Little X to find a proper test for hack.

## 代码

#include <cstdio>

long long mul(long long a, long long b, long long mod) {
long long ret = 0;
while (b) b & 1 && ((ret += a) %= mod), (a <<= 1) %= mod, b >>= 1;
return ret;
}

int main() {
long long n; scanf("%lld", &n);
long long cur = mul(1800000000000000000ll, 45, n) + 1, l = 1, r = 1000000000000000000ll;
l += n - cur, r += n - cur, printf("%lld %lld\n", l, r);
return 0;
}


## 题目描述

Joe is a frog who likes to jump a lot. In fact, that’s all he does: he jumps forwards and backwards on the integer axis (a straight line on which all the integer numbers, both positive and negative are marked). At first, Joe sits next to the point marked with $0$. From here, he can jump in the positive or the negative direction a distance equal to either $x_1$ or $x_2$. From the point where he arrived, he can jump again a distance equal to $x_1$ or $x_2$, in the positive or the negative direction and so on.. Joe wants to arrive next to the point marked with the number $P$, after exactly $K$ jumps. You have to decide whether such a thing is possible.

## 题意概述

\left\{ \begin{align} P_1x_1-N_1x_1+P_2x_2-N_2x_2&=P \\ P_1+N_1+P_2+N_2&=K \end{align} \right.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define int long long

using namespace std;

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
int x1, x2, p, k;
void input() { io > x1 > x2 > p > k; }
int ex_gcd(int a, int b, int &x, int &y) {
if (! b) { x = 1, y = 0; return a; }
int ret = ex_gcd(b, a % b, y, x); y -= a / b * x; return ret;
}
bool check(int x, int y) {
if (abs(x) + abs(y) > k) return false;
if (k - abs(x) - abs(y) & 1) return false;
io < (char *) "YES\n";
int t = k - abs(x) - abs(y) >> 1;
if (x > 0) io < x + t < ' ' < t < ' ';
else io < t < ' ' < -x + t < ' ';
if (y > 0) io < y < ' ' < 0 < '\n';
else io < 0 < ' ' < -y < '\n';
return true;
}
void process() {
int x, y, gcd = ex_gcd(x1, x2, x, y);
if (p % gcd) io < (char *) "NO\n";
else {
x1 /= gcd, x2 /= gcd, p /= gcd, x *= p, y *= p;
for (int i = -abs(p) - 1; i <= abs(p) + 1; ++ i)
if (check(x + x2 * i, y - x1 * i)) goto label;
io < (char *) "NO\n";
label: ;
}
}

public:
void solve() { input(), process(); }
} solver;

signed main() {
solver.solve();
return 0;
}


## 题目描述

A sequence $A$ is called an integer sequence of length $N$ if all its elements $A_1, A_2, \ldots, A_N$ are non-negative integers less than $2000000000$. Consider two integer sequences of length $N, A$ and $X$. The result of their multiplication $(A \cdot X)$ is an integer number $R=\sum_{i=1}^N A_iX_i$. Your task is to solve the equation $A \cdot X \equiv B \pmod P$, given the integer sequence $A$ and the integer numbers $B$ and $P$.

## 算法分析

\left\{ \begin{align} A_1x_1+A_2y_1&=g_2 \\ g_2x_2+A_3y_2&=g_3 \\ \cdots& \\ g_{N-1}x_{N-1}+A_Ny_{N-1}&=g_N \\ g_Nx_N+Py_N&=(g_N, P) \end{align} \right.

## 代码

#include <cctype>
#include <cstdio>

using namespace std;

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
static const int N = 101;
int n, p, m, a[N], x[N], y[N];
int ex_gcd(int a, int b, int &x, int &y) {
if (! b) { x = 1, y = 0; return a; }
int ret = ex_gcd(b, a % b, y, x); y -= a / b * x; return ret;
}
void input() {
io > n > p > m;
for (int i = 1; i <= n; ++ i) io > a[i], a[i] %= p;
}
void process() {
int g = a[1]; x[0] = y[0] = 1;
for (int i = 2; i <= n; ++ i) g = ex_gcd(g, a[i], x[i - 1], y[i - 1]);
g = ex_gcd(g, p, x[n], y[n]);
if (m % g) io < (char *) "NO\n";
else {
io < (char *) "YES\n", g = m / g;
for (int i = 1; i <= n; ++ i) {
int t = g * (y[i - 1] + p);
for (int j = i; j <= n; ++ j) t = 1ll * t * (x[j] + p) % p;
io < t < ' ';
}
io < '\n';
}
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


## 题目描述

$N$ friends gathered in order to play chess, according to the following rules. In the first game, two of the $N$ friends will play. In the second game, the winner of the first game will play against another friend (maybe even the same friend who lost the first game). In the third game, the winner of the second game will play against someone else and so on.. No game will end as a draw (tie). Given the number of games each of the $N$ friends played, find a schedule for the games, so that the above rules are obeyed.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
static const int N = 110;
int n, sum;
pair <int, int> a[N];
vector <pair <int, int> > ans;
void input() {
io > n;
for (int i = 1; i <= n; ++ i) io > a[i].first, a[i].second = i, sum += a[i].first;
}
void process() {
io < sum >> 1 < '\n';
sort(a + 1, a + n + 1, greater <pair <int, int> >());
int p = 1;
for (int i = 0; i < sum >> 1; ++ i) {
if (a[p].first == 1) ans.push_back(make_pair(a[p + 1].second, a[p].second)), -- a[p].first, -- a[++ p].first;
else ans.push_back(make_pair(a[p].second, 0)), -- a[p].first;
}
for (int i = 0; i < sum >> 1; ++ i)
if (! ans[i].second)
for (int j = 1; j <= n; ++ j) if (a[j].first && a[j].second != ans[i].first) { ans[i].second = a[j].second, -- a[j].first; break; }
for (int i = 0; i < sum >> 1; ++ i) io < ans[i].first < ' ' < ans[i].second < '\n';
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


## 题目描述

Let’s consider a string of non-negative integers, containing $N$ elements. Suppose these elements are $S_1, S_2, \ldots, S_N$, in the order in which they are placed inside the string. Such a string is called ‘funny’ if the string $S_1+1, S_2, S_3, \ldots, S_{N-1}, S_N-1$ can be obtained by rotating the first string (to the left or to the right) several times. For instance, the strings $2, 2, 2, 3$ and $1, 2, 1, 2, 2$ are funny, but the string $1, 2, 1, 2$ is not. Your task is to find a funny string having $N$ elements, for which the sum of its elements $S_1+S_2+ \cdots +S_N$ is equal to $K$.

## 算法分析

0_______1（旧）
1_______0（新）

0______11
1______10

0____1_11
1____1_10

0__1_1_11
1__1_1_10

01_1_1_11
11_1_1_10

010101011
110101010

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
static const int N = 1010;
int n, k, a[N];
void input() { io > n > k; }
void init() {
int t = k / n;
for (int i = 1; i <= n; ++ i) a[i] = t, k -= t;
}
void process() {
int sum = n - 1;
while (sum % k) sum += n;
int p = sum / k + 1;
for (; p < n; p = (p - 1 + sum / k) % n + 1) ++ a[p]; ++ a[n];
for (int i = 1; i <= n; ++ i) io < a[i] < ' ';
io < '\n';
}

public:
void solve() { input(), init(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


## 题目描述

Little Johnny painted on a sheet of paper a polygon with $N$ vertices. Then, for every edge of the polygon, he drew the middle point of the edge. After that, he went to school. When he came back, he found out that his brother had erased the polygon (both the edges and the vertices). The only thing left were the middle points of the edges of the polygon. Help Johnny redraw his polygon.

## 算法分析

$$\left\{ \begin{array}{c} x_1+x_2=2x_1′ \\ x_2+x_3=2x_2′ \\ \cdots \\ x_N+x_1=2x_N’ \end{array} \right.$$

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

#define random (1.0 * rand() / RAND_MAX)

using namespace std;

static const double EPS = 1e-6;
int cmp(double a, double b) {
return fabs(a - b) < EPS ? 0 : a < b ? -1 : 1;
}

struct Point {
double x, y;
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
Point operator + (const Point &p) const { return Point(x + p.x, y + p.y); }
Point operator - (const Point &p) const { return Point(x - p.x, y - p.y); }
Point operator * (const double &n) const { return Point(x * n, y * n); }
Point operator / (const double &n) const { return *this * (1 / n); }
Point operator | (const Point &p) const { return *this + (p - *this) * 2; }
};

struct Solver {
private:
static const int N = 10010;
int n;
Point point[N];
vector <Point> ans;
void input() {
scanf("%d", &n);
for (int i = 1; i <= n; ++ i) scanf("%lf%lf", &point[i].x, &point[i].y);
}
void process() {
Point p;
if (n & 1) {
double sum = 0;
for (int i = 1; i <= n; ++ i) sum += point[i].x;
for (int i = 2; i <= n; i += 2) sum -= point[i].x * 2;
p.x = sum, sum = 0;
for (int i = 1; i <= n; ++ i) sum += point[i].y;
for (int i = 2; i <= n; i += 2) sum -= point[i].y * 2;
p.y = sum;
} else p = Point(random * 100000, random * 100000);
for (int i = 1; i <= n; ++ i) ans.push_back(p), p = p | point[i];
if (cmp(p.x, ans[0].x) || cmp(p.y, ans[0].y)) printf("NO\n");
else {
printf("YES\n");
for (int i = 0; i < ans.size(); ++ i) printf("%.6lf %.6lf\n", ans[i].x, ans[i].y);
}
}

public:
void solve() { input(), process(); }
} solver;

int main() {
srand(47), solver.solve();
return 0;
}


## 题目描述

There is a syntactically correct boolean expression.
The definition of syntactically correct expression follows as:

1. “a”, “b”, “c”, …, “j” are syntactically correct expressions.
2. If A is a correct expression, then !A and (A) are correct expressions too.
3. If A is a correct expression and B is a correct expression, then A||B, A&B, A<=>B, A=>B, A#B are syntactically correct expressions too.

Syntactically correct expression doesn’t contain spaces.
Small Latin letters are variables, ! denotes negation, || – disjunction, & – conjunction, <=> – equality, => – implication, # – excepting or.
Negation has the highest priority, conjunction has middle priority, and other operations have low priority. Brackets change the order of operations executing.
Two expressions are called identical if their values are the same in any values of variables.
Make the expression, which will be identical with given expression. New expression must be free of brackets.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

struct Solver {
private:
string s;
void input() { cin >> s; }
int len(char c) {
switch (c) {
case '!' : return 0;
case '&' : return 0;
case '|' : return 1;
case '<' : return 2;
case '=' : return 1;
case '#' : return 0;
}
}
int priority(char c) {
switch (c) {
case '!' : return 1;
case '&' : return 2;
case '|' : return 3;
case '<' : return 3;
case '=' : return 3;
case '#' : return 3;
case '(' : return 4;
}
}
bool single(bool a, char c, bool b) {
switch (c) {
case '&' : return a && b;
case '|' : return a || b;
case '<' : return a == b;
case '=' : return a || ! b;
case '#' : return a ^ b;
}
}
int match(string s, int p) {
int cnt = 1;
while (cnt) ++ p, cnt += (s[p] == '(') - (s[p] == ')');
return p;
}
stack <char> symbol;
stack <bool> number;
void pop() {
if (symbol.top() == '!') {
symbol.pop(); bool p = number.top(); number.pop(), number.push(! p);
} else {
bool p = number.top(); number.pop();
bool q = number.top(); number.pop();
number.push(single(p, symbol.top(), q));
symbol.pop();
}
}
bool calc(string s) {
for (int i = 0; i < s.length(); ++ i) {
if (isdigit(s[i])) number.push(s[i] - '0');
else if (s[i] == '(') symbol.push('(');
else if (s[i] == ')') {
while (symbol.top() != '(') pop();
symbol.pop();
} else {
while (! symbol.empty() && priority(symbol.top()) <= priority(s[i])) pop();
symbol.push(s[i]), i += len(s[i]);
}
}
while (! symbol.empty()) pop();
return number.top();
}
bool check(int p, string s) {
for (int i = 0; i < s.length(); ++ i)
if (isalpha(s[i])) s[i] = ((p & 1 << s[i] - 'a') > 0) + '0';
return calc(s);
}
void process() {
for (int i = 0; i + 1 < s.length(); ++ i)
while (i + 1 < s.length() && s[i] == '!' && s[i + 1] == '!')
s = s.substr(0, i) + s.substr(i + 2);
string ans, sep;
for (int i = 0; i < 1 << 10; ++ i)
if (check(i, s)) {
ans += sep, sep = "||";
string s;
for (int j = 0; j < 10; ++ j) {
ans += s, s = "&";
if (! (i & 1 << j)) ans += "!";
ans += j + 'a';
}
}
if (ans.length() == 0) ans = "!a&a";
cout << ans << endl;
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


## 题目描述

There are $N$ points given by their coordinates on a plane. All coordinates $(x_i, y_i)$ are integers in a range from $-10000$ up to $10000$ inclusive . It is necessary to construct a broken line satisfying the following conditions:

• The broken line should be closed.
• End points of each segment (verteces) of the broken line can only be the given points, and all given points should be used.
• Each two consecutive segments of the broken line should form a corner of 90 degrees in each vertex point.
• The sides of the broken line should be parallel to coordinate axes.
• The broken line should have no self-crossing and self-contact.
• The broken line should have the minimal length.

You have to either find the length $L$ of the constructed broken line, or determine that it is impossible to construct such a broken line.

## 题意概述

• 这个图形是闭合的；
• 每条边的端点必须是给定的点，且每个给定的点必须被用到；
• 每个点连接的两条边必须互相垂直；
• 每条边必须平行于坐标轴；
• 任意两条边除了顶点外不能相交；
• 这个图形的周长最小。

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Point { int x, y, id; };

bool cmpx(Point a, Point b) { return a.x == b.x ? a.y < b.y : a.x < b.x; }
bool cmpy(Point a, Point b) { return a.y == b.y ? a.x < b.x : a.y < b.y; }
bool cmpi(Point a, Point b) { return a.id < b.id; }

struct Line { Point a, b; };

struct Solver {
private:
static const int N = 10010;
int n, top, fa[N];
Point point[N];
Line line[N];
void input() {
io > n;
for (int i = 1; i <= n; ++ i) io > point[i].x > point[i].y, point[i].id = i;
}
bool inter(Line p, Line q) {
if (p.a.x == p.b.x && q.a.x == q.b.x) {
if (p.a.y > q.a.y) swap(p, q);
if (p.a.x != q.a.x) return false;
else return p.b.y > q.a.y;
} else if (p.a.y == p.b.y && q.a.y == q.b.y) {
if (p.a.x > q.a.x) swap(p, q);
if (p.a.y != q.a.y) return false;
else return p.b.x > q.a.x;
} else {
if (p.a.x != p.b.x) swap(p, q);
return p.a.y < q.a.y && q.a.y < p.b.y && q.a.x < p.a.x && p.a.x < q.b.x;
}
}
int get_fa(int t) { return t == fa[t] ? t : fa[t] = get_fa(fa[t]); }
void process() {
int l = 0, r = 0, cnt = n - 1;
sort(point + 1, point + n + 1, cmpx);
for (int i = 1; i <= n; i = r) {
l = i, r = i + 1;
while (r <= n && point[r].x == point[l].x) ++ r;
if (r - l & 1) { io < 0 < '\n'; return; }
for (int j = l; j < r; j += 2) line[++ top] = (Line) { point[j], point[j + 1] };
}
sort(point + 1, point + n + 1, cmpy);
for (int i = 1; i <= n; i = r) {
l = i, r = i + 1;
while (r <= n && point[r].y == point[l].y) ++ r;
if (r - l & 1) { io < 0 < '\n'; return; }
for (int j = l; j < r; j += 2) line[++ top] = (Line) { point[j], point[j + 1] };
}
sort(point + 1, point + n + 1, cmpi);
for (int i = 1; i <= top; ++ i)
if (line[i].a.x > line[i].b.x || line[i].a.y > line[i].b.y) swap(line[i].a, line[i].b);
for (int i = 1; i < top; ++ i)
for (int j = i + 1; j <= top; ++ j)
if (inter(line[i], line[j])) { io < 0 < '\n'; return; }
for (int i = 1; i <= n; ++ i) fa[i] = i;
for (int i = 1; i <= top; ++ i) {
int p = get_fa(line[i].a.id), q = get_fa(line[i].b.id);
if (p != q) fa[p] = q, -- cnt;
}
if (cnt) { io < 0 < '\n'; return; }
int ans = 0;
for (int i = 1; i <= top; ++ i) ans += line[i].b.x - line[i].a.x + line[i].b.y - line[i].a.y;
io < ans < '\n';
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


## 题目描述

There is a group of $N$ people which are numbered $1$ through $N$, and everyone of them has not less than $\left[ {N + 1 \over 2} \right]$ friends. A man with number $1$ has the book, which others want to read. Write the program which finds a way of transferring the book so that it will visit every man only once, passing from the friend to the friend, and, at last, has come back to the owner. Note: if A is a friend of B then B is a friend of A.

## 算法分析

Ore性质：一张阶数等于$N$的图中任意两个不相邻的点的度数之和不小于$N$。

• 在链上找到一点$p$（设它的下一个点是$q$），满足链头和$q$连通、链尾和$p$连通，可以删去$p$、$q$之间的边，连接链头和$q$、链尾和$p$，构成一个环；
• 如果环上的点数小于$N$，找到一个和环上一点$p$连通且不在环上的点$q$，可以删去一条$p$的边，连接$p$和$q$，构成一条链，回到上一步。

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

char c = getchar(); int len = 0;
while (~ c && c != '\n') s[len ++] = c, c = getchar();
s[len] = '\0'; return len;
}

struct Solver {
private:
static const int N = 1010;
int n, pre[N], nxt[N], near[N];
bool mp[N][N], vis[N];
char s[N << 3];
void input() {
for (int i = 1; i <= n; ++ i) {
int len = read(s), t = 0;
for (int j = 0; j <= len; ++ j)
if (isdigit(s[j])) (t *= 10) += s[j] - '0'; else mp[i][t] = true, t = 0;
}
}
void dfs(int t, int fa) {
vis[t] = true;
for (int i = 1; i <= n; ++ i)
if (mp[t][i] && ! vis[i]) { nxt[t] = i, pre[i] = t, dfs(i, t); return; }
}
int get_pre(int t) { if (! pre[t]) return t; else return get_pre(pre[t]); }
int get_nxt(int t) { if (! nxt[t]) return t; else return get_nxt(nxt[t]); }
void reverse(int p) {
nxt[p] = pre[p]; if (! pre[p]) return; reverse(pre[p]), pre[pre[p]] = p;
}
void process() {
int cnt = 0; dfs(1, 0);
for (int i = 1; i <= n; ++ i) cnt += pre[i] || nxt[i];
for (int i = 1; i <= n; ++ i) if (pre[i] || nxt[i])
for (int j = 1; j <= n; ++ j) if (mp[i][j] && ! pre[j] && ! nxt[j]) near[j] = i;
while (cnt <= n) {
int head = 0, tail = 0;
for (int i = 1; i <= n; ++ i) if (pre[i]) { head = get_pre(i); break; }
for (int i = 1; i <= n; ++ i) if (nxt[i]) { tail = get_nxt(i); break; }
for (; nxt[p]; p = nxt[p])
int tmp = nxt[p]; pre[tmp] = nxt[p] = 0, reverse(p);
nxt[head] = tmp, pre[tmp] = head, nxt[tail] = p, pre[p] = tail;
break;
}
if (cnt < n)
for (int i = 1; i <= n; ++ i) if (! pre[i] && ! nxt[i] && near[i]) {
nxt[i] = near[i], nxt[pre[near[i]]] = 0, pre[near[i]] = i;
for (int j = 1; j <= n; ++ j) if (mp[i][j] && ! pre[j] && ! nxt[j]) near[j] = i;
break;
}
++ cnt;
}
int p = 1; putchar('1');
do printf(" %d", p = nxt[p]); while (p != 1);
putchar('\n');
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


## 题目描述

New Berland consists of $N$ islands, some of them are connected by bridges. There can be no more than one bridge between any pair of islands. Mr. President issued a law to paint all bridges. A bridge can be painted white or black. Any island must have at least one white bridge and at least one black (of course if an island has more than one bridge).

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
static const int N = 110;
int n, col[N][N];
vector <int> mp[N];
void input() {
io > n;
for (int i = 1; i <= n; ++ i) {
int t; io > t;
while (t) mp[i].push_back(t), io > t;
}
}
void dfs(int t, int c) {
for (int i = 0; i < mp[t].size(); ++ i)
if (! col[t][mp[t][i]]) col[t][mp[t][i]] = col[mp[t][i]][t] = c, dfs(mp[t][i], c = 3 - c);
}
void process() {
for (int i = 1; i <= n; ++ i) if (mp[i].size() != 2) dfs(i, 1);
for (int i = 1; i <= n; ++ i) dfs(i, 1);
for (int i = 1; i <= n; ++ i) {
bool w = false, b = false;
for (int j = 0; j < mp[i].size(); ++ j) w |= col[i][mp[i][j]] == 1, b |= col[i][mp[i][j]] == 2;
if (mp[i].size() > 1 && ! (w && b)) { io < (char *) "No solution\n"; return; }
}
for (int i = 1; i <= n; ++ i) {
for (int j = 0; j < mp[i].size(); ++ j) io < col[i][mp[i][j]] < ' ';
io < 0 < '\n';
}
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}