Hello，2020！新的一年从快乐的掉分开始……
我在m3.codeforces.com这个镜像网站中打不开D题，我……
还有话说今天这场为什么那么多二分。
比赛传送门：https://codeforces.com/contest/1284。
A. New Year and Naming
题目大意：这题就是一个干支纪年法。每年的名字分两段，第一段在n个字符串中取，第二段在m个字符串中取，每过一年就各取下一个，如果取到n（m）就去取第一个。
纯模拟，加上一点点字符串操作。
又丑又长的代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <vector> 6 #define rep(x, l, r) for(int x = l; x <= r; x++) 7 #define repd(x, r, l) for(int x = r; x >= l; x--) 8 #define clr(x, y) memset(x, y, sizeof(x)) 9 #define all(x) x.begin(), x.end() 10 #define pb push_back 11 #define mp make_pair 12 #define MAXN 2005 13 #define fi first 14 #define se second 15 #define SZ(x) ((int)x.size()) 16 using namespace std; 17 typedef long long ll; 18 typedef vector<int> vi; 19 typedef pair<int, int> pii; 20 const int INF = 1 << 30; 21 const int p = 1000000009; 22 int lowbit(int x){ return x & (-x);} 23 int fast_power(int a, int b){ int x; for(x = 1; b; b >>= 1){ if(b & 1) x = 1ll * x * a % p; a = 1ll * a * a % p;} return x % p;} 24 25 char st1[MAXN][25], st2[MAXN][25]; 26 27 int main(){ 28 int n, m; 29 scanf("%d%d", &n, &m); 30 rep(i, 1, n) scanf("%s", st1[i]); 31 rep(i, 1, m) scanf("%s", st2[i]); 32 int q; 33 scanf("%d", &q); 34 rep(i, 1, q){ 35 int x; 36 scanf("%d", &x); 37 int len = strlen(st1[(x - 1) % n + 1]); 38 rep(j, 0, len - 1) putchar(st1[(x - 1) % n + 1][j]); 39 puts(st2[(x - 1) % m + 1]); 40 } 41 return 0; 42 }
B.New Year and Ascent Sequence
题目大意：给你n个序列，每次取任意两个序列（可以取同一个，并且交换前后顺序算不同种）接起来（比如说‘11’和‘22’就是‘1122’）。问这n2个接成序列中共有多少个序列中存在顺序对。
不难看出，如果一个序列中本身存在顺序对，接成的序列也肯定存在顺序对。
判断方法
if(x > minx) flag = 1;
将它们找出来后直接统计入答案，套上一个小学学的容斥原理
ans = 1ll * 2 * cnt1 * n - 1ll * cnt1 * cnt1;
然后主要问题就是这些剩下的没有顺序对的序列。
很显然凡是最大值比这个序列最小值大的，就可以和这个序列接起来。
将最大值排序后二分一下最小的最大值就好。
代码如下
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <vector> 6 #define rep(x, l, r) for(int x = l; x <= r; x++) 7 #define repd(x, r, l) for(int x = r; x >= l; x--) 8 #define clr(x, y) memset(x, y, sizeof(x)) 9 #define all(x) x.begin(), x.end() 10 #define pb push_back 11 #define mp make_pair 12 #define MAXN 100005 13 #define fi first 14 #define se second 15 #define SZ(x) ((int)x.size()) 16 using namespace std; 17 typedef long long ll; 18 typedef vector<int> vi; 19 typedef pair<int, int> pii; 20 const int INF = 1 << 30; 21 const int p = 1000000009; 22 int lowbit(int x){ return x & (-x);} 23 int fast_power(int a, int b){ int x; for(x = 1; b; b >>= 1){ if(b & 1) x = 1ll * x * a % p; a = 1ll * a * a % p;} return x % p;} 24 25 vi a, b; 26 27 int main(){ 28 int n; 29 scanf("%d", &n); 30 int cnt1 = 0, cnt2 = 0; 31 rep(i, 1, n){ 32 int k; 33 scanf("%d", &k); 34 int minx = INF, maxx = -INF; 35 bool flag = 0; 36 rep(j, 1, k){ 37 int x; 38 scanf("%d", &x); 39 if(x > minx) flag = 1; 40 minx = min(minx, x); 41 maxx = max(maxx, x); 42 } 43 if(flag) cnt1++; 44 else{ 45 cnt2++; 46 a.pb(minx); 47 b.pb(maxx); 48 } 49 } 50 sort(all(b)); 51 ll ans = 1ll * 2 * cnt1 * n - 1ll * cnt1 * cnt1; 52 rep(i, 0, SZ(b) - 1){ 53 ans += cnt2 - (upper_bound(all(b), a[i]) - b.begin()); 54 } 55 printf("%I64d\n", ans); 56 return 0; 57 }
C.New Year and Permutation
题目大意：在所有由[1，n]组成的排列中，有多少对数(l，r)满足max{pl，pl+1，…，pr} - min{pl，pl+1，…，pr} = r - l。
似乎解释的不是很清楚，再来个样例解释一下。
当n = 3时，所有的排列为[1，2，3]，[1，3，2]，[2，1，3]，[2，3，1]，[3，1，2]，[3，2，1]。
对于[1，2，3]：(1，1)中max = 1， min = 1， r - l = 0，成立；(1，3)中max = 3， min = 1， r - l = 2，成立。
对于[1，3，2]：(1，2)中max = 3， min = 1， r - l = 1，不成立。
别的懒得说了，原题样例说明有。
这道题一开始看的时候有点慌，浪费了好多时间。
后来一想，不就分别统计长度为i的子段满足条件。
我们可以很轻松的求出不同子段出现次数，所有该长度的子段出现次数为:
排列个数×每个排列中出现的次数 = n！×（n - i +1）
然后该长度不同子段的个数为n！/ (n - i)！，稍微证明一下或者列举几个便可以得出。
然后求所有符合条件的字段个数，(1，2，…，i ) 到（n - i + 1，n - i + 2，…， n ）一共有n - i + 1种，然后每种的排列有i！个。
所有长度为i的字段对答案的贡献 = 不同子段的出现个数 × 符合的长度为i子段的个数
= n！× (n - i + 1) / ( n！/ ( n - i )！) × ( n - i + 1 ) × i！
= ( n - i )！ × ( n - i + 1) × ( n - i +1 ) × i！
这个式子看上去挺好看的，然后求个总和就好。
代码特别短：
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <vector> 6 #define rep(x, l, r) for(int x = l; x <= r; x++) 7 #define repd(x, r, l) for(int x = r; x >= l; x--) 8 #define clr(x, y) memset(x, y, sizeof(x)) 9 #define all(x) x.begin(), x.end() 10 #define pb push_back 11 #define mp make_pair 12 #define MAXN 250005 13 #define fi first 14 #define se second 15 #define SZ(x) ((int)x.size()) 16 using namespace std; 17 typedef long long ll; 18 typedef vector<int> vi; 19 typedef pair<int, int> pii; 20 const int INF = 1 << 30; 21 int p; 22 int lowbit(int x){ return x & (-x);} 23 int fast_power(int a, int b){ int x; for(x = 1; b; b >>= 1){ if(b & 1) x = 1ll * x * a % p; a = 1ll * a * a % p;} return x % p;} 24 25 int pow[MAXN]; 26 27 int main(){ 28 int n; 29 scanf("%d%d", &n, &p); 30 pow[0] = 1; 31 rep(i, 1, n){ 32 pow[i] = 1ll * pow[i - 1] * i % p; 33 } 34 int ans = 0; 35 rep(i, 1, n){ 36 int s = 1ll * pow[n - i] * (n - i + 1) % p * (n - i + 1) % p * pow[i] % p; 37 ans = (ans + s) % p; 38 } 39 printf("%d\n", ans); 40 return 0; 41 }
D.
原文：https://www.cnblogs.com/nblyz2003/p/12151883.html
