『ACM-XCPC』2020暑期ZJNU组队训练1

2020牛客暑期多校训练营(第一场)

Posted by GJ on July 12, 2020

两题 FCHJ JCHJ

F Infinite String Comparision

传送门

Description

For a string x, Bobo defines x∞=xxx…, which is x repeats for infinite times, resulting in a string of infinite length.

Bobo has two strings a and b. Find out the result comparing a∞ and b∞ in lexicographical order.

You can refer the wiki page for further information of Lexicographical Order.

Input

The input consists of several test cases terminated by end-of-file.

The first line of each test case contains a string a, and the second line contains a string b.

  • 1 ≤ a , b ≤ 105
  • a, b consists of lower case letters.
  • The total length of input strings does not exceed 2 × 106.

Output

For each test case, print “=” (without quotes) if a∞ = b∞ . Otherwise, print “<” if a∞ < b∞ , or “>” if a∞ > b∞ .

Sample Input

aa
b
zzz
zz
aba
abaa

Sample Output

<
=
>

Solution

状态 S t 说明
初始 ▦▦▦▦▦▦▦ ▩▩▩  
第一轮比较 ■■■□□□□ ■■■ 比较黑块是否相同
第二轮比较 □□□■■■□ ■■■ 同上
第三轮比较 □□□□□□■ ■□□ 同上

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define O_O ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
string s, t;
int flag = 0;

int main() {
	O_O;
	while (cin >> s >> t) {
		flag = 0;
		int len = max(s.size(), t.size());
		int les = s.length();
		int let = t.length();
		for (int i = 0; i < len*2; i++) {
			if (s[i % les] > t[i % let]) { flag=1; break; }
			else if (s[i % les] < t[i % let]) { flag=-1; break; }
		}
		if (flag == -1) cout << "<\n";
		else if (!flag) cout << "=\n";
		else cout << ">\n";
	}
	return 0;
}

J Easy Integration

传送门

Description

Given n, find the value of $\int_{0}^1 (x - x^2)^n \mathrm{d} x$

It can be proved that the value is a rational number $\frac{p}{q}$.

Print the result as $(p · q^{-1}) \bmod 998244353$.

Input

The input consists of several test cases and is terminated by end-of-file.

Each test case contains an integer n.

* $1 \leq n \leq 10^6$ * The number of test cases does not exceed $10^5$.

Output

For each test case, print an integer which denotes the result.

Sample Input

1
2
3

Sample Output

166374059
432572553
591816295

Tips

For n = 1,$ \int_{0}^1 (x - x^2) \mathrm{d} x = \frac{x^2}{2} - \frac{x^3}{3} _0^1 = \frac{1}{6}$

Solution

暴力打表先找规律。然后?然后就做完了

n 分子 分母
1 1 6
2 2 60
3 6 840
4 24 15120
5 120 332640

$fz[n]=n!$

$fm[n]=fm[n-1](2i+1)*2$

然后再掏出逆元的板子就好啦 :smiley:

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define O_O ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
const ll mod = 998244353;
int n;
ll fz[maxn], fm[maxn];

void init() {
	fz[0] = 1;
	fm[1] = 6;
	for (int i = 1; i <= 1e6; i++) fz[i] = fz[i - 1] * i % mod;
	for (int i = 2; i <= 1e6; i++) fm[i] = fm[i - 1] * 2 * (2 * i + 1) % mod;
}

ll mul(ll a, ll b, ll p) {
	long long res = 1;
	a %= p;
	while (b) {
		if (b & 1)
			res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}

ll inv(ll a, ll b, ll mod) {
	return a % mod * mul(b, mod - 2, mod) % mod;
}

int main() {
	O_O;
	init();
	while (cin >> n) {
		cout << inv(fz[n], fm[n], mod) << "\n";
	}
	return 0;
}

I 1 or 2

Description

Bobo has a graph with n vertices and m edges where the i-th edge is between the vertices $a_i$ and $b_i$. Find out whether is possible for him to choose some of the edges such that the i-th vertex is incident with exactly $d_i$ edges.

Input

The input consists of several test cases terminated by end-of-file.

The first line of each test case contains two integers n and m. The second line contains n integers $d_1$,$ d_2$,$ \dots$, $d_n$ . The i-th of the following m lines contains two integers $a_i$ and $b_i$ .

  • $1 \leq n \leq 50$
  • $1 \leq m \leq 100$
  • $1 \leq d_i \leq 2$

  • $1 \leq a_i, b_i \leq n$

  • $a_i \neq b_i$

  • ${a_i, b_i} \neq {a_j, b_j}$ for $i \neq j$

  • The number of tests does not exceed 100.

Output

For each test case, print “Yes” without quotes if it is possible. Otherwise, print “No” without quotes.

Sample Input

2 1
1 1
1 2
2 1
2 2
1 2
3 2
1 1 2
1 3
2 3

Sample Output

Yes
No
Yes

Solution

一般图最大匹配

注:本题最大流做法错误