2020.07.12牛客多校第一场实况&解题报告&补题ing

比赛开场很顺利，F字符串思维 和 J分部积分的计算很快出了，接着cncn和我开始看I题，骚老师看了A和H，cncn和我看了I。I想了几个排除条件和dfs暴力，但最终没有出。看通过代码居然是网络流，感觉有点可惜

F Infinite String Comparision

题意
给定两个字符串a，b作为循环节，每个循环节可以无限循环。要你比较循环后的字符串的字典序大小。

思路
一种思路是将更长的循环节延长一倍，之后把短的补齐后直接比较；
cncn开发出一种更简洁的解法：将a加到b的后面，将b加到a的后面，然后对两个新字符串ab、ba进行比较即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
string a, b;

int main() {
   while(cin >> a >> b) {
      string tmp = a;
      a += b;
      b += tmp;
      if(a == b) puts("=");
      else if(a > b) puts(">");
      else puts("<");
   }
   return 0;
}

J Easy Integration

题意
给出一个整数n(n $\leq 1e6$)，计算定积分$$\int ^1 _0 (x - x^2)^n dx$$(mod = 998244353)

思路
式子为高数上基础分部积分法，算出结果为 $$ \frac{(n!)^2}{(2n+1)!} $$
后面的工作就很容易了。首先预处理出2e6的阶乘(注意取模)，接着根据费马小定理用快速幂法求出分母的逆元乘上分子得出答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ll n, J[M];

ll Pow(ll a, ll b) {
   ll ans = 1;
   for(; b; b >>= 1) {
      if(b & 1) ans = ans * a % mod;
      a = a * a % mod;
   }
   return ans;
}

int main() {
   for1(i, 2e6+1) {
      if(i == 1) J[i] = 1;
      else J[i] = J[i-1] * i % mod;
   }
   while(scanf("%d", &n) != EOF) {
      ll ans = Pow(J[n], 2) * Pow(J[2*n+1], mod-2) % mod;
      printf("%lld\n", ans);
   }
   return 0;
}

I 1 or 2

题意
给出一张无向图包含n($ n \leq 50 $)个结点和m($ m \leq 100 $)条边，不计权值。每个结点i都有一个约束度di，表示第i个结点的度恰好为di($ 1 \le di \le 2 $)。问你能否在给出的图中选择一些边，使得每个结点的约束条件di都能满足。

思路

一只GIS专业的ACMer