比赛链接
收获
给定一个排列 $p_i$，从 $i$ 向 $p_i$ 连边可以形成若干环。和排列相关的题可以这样想一下。
A African Sort 留坑，待补
B Binary Vector 每次加入的向量都不属于之前的向量空间，故 $f_n=\prod\limits_{i=0}^{n-1}\left(1-\frac{2^i}{2^n}\right)=\frac{\prod\limits_{i=0}^{n-1}(2^n-2^i)}{2^{n^2}}$。易得递推式：$f_n=f_{n-1}\cdot\frac{2^n-1}{2^n}$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include <bits/stdc++.h> using namespace std;template <typename T>void read (T&x) 0 ;int fl=1 ;char ch=getchar ();while (ch<'0' ||ch>'9' ){if (ch=='-' )fl=-1 ;ch=getchar ();}while (ch>='0' &&ch<='9' ){x=(x<<1 )+(x<<3 )+ch-'0' ;ch=getchar ();}x*=fl;} template <typename T,typename ...Args>inline void read (T&t,Args&...args) read (t);read (args...);}typedef long long LL;typedef vector<int > vi;typedef pair<int , int > pii;#define mp(x, y) make_pair(x, y) #define pb(x) emplace_back(x) const LL MOD = 1e9 + 7 ;const LL inv2 = 500000004 ;const int N = 2e7 +5 ;int T, n;LL f[N], inv = inv2; int main () f[1 ] = 5e8 +4 ; for (int i = 2 ; i <= 2e7 ; i++){ (inv *= inv2) %= MOD; f[i] = (f[i-1 ] * (1 - inv) % MOD + MOD) % MOD; } for (int i = 2 ; i <= 2e7 ; i++) f[i] ^= f[i-1 ]; for (read (T); T; T--){ read (n); printf ("%lld\n" , f[n]); } return 0 ; }
C Combination of Physics and Maths 又做麻烦了……
首先，如果选出的矩形有多列，那么一定可以把它分开，分出的一部分答案不会更差。证明：设 $\frac{a}{b}\leqslant\frac{c}{d}$，那么 $\frac{a}{b}\leqslant\frac{a+c}{b+d}\leqslant\frac{c}{d}$。所以答案是一列。
枚举这一列的最下面的数字，把它上面的所有数字都选上，更新答案。
复杂度：$O(Tnm)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <bits/stdc++.h> using namespace std;template <typename T>void read (T&x) 0 ;int fl=1 ;char ch=getchar ();while (ch<'0' ||ch>'9' ){if (ch=='-' )fl=-1 ;ch=getchar ();}while (ch>='0' &&ch<='9' ){x=(x<<1 )+(x<<3 )+ch-'0' ;ch=getchar ();}x*=fl;} template <typename T,typename ...Args>inline void read (T&t,Args&...args) read (t);read (args...);}typedef long long LL;typedef vector<int > vi;typedef pair<int , int > pii;#define mp(x, y) make_pair(x, y) #define pb(x) emplace_back(x) const int N = 205 ;int T, n, m;LL a[N][N], colSum[N][N]; int main () for (read (T); T; T--){ read (n, m); for (int j = 1 ; j <= m; j++) colSum[0 ][j] = 0 ; double ans = 0 ; for (int i = 1 ; i <= n; i++){ for (int j = 1 ; j <= m; j++){ read (a[i][j]); colSum[i][j] = colSum[i-1 ][j] + a[i][j]; ans = max (ans, 1.0 * colSum[i][j] / a[i][j]); } } printf ("%.8f\n" , ans); } return 0 ; }
E Easy Construction $n$ 个数的和要满足条件，所以 $\frac{n(n+1)}{2}\bmod n=k$。
当 $n$ 是奇数时，一定有 $k=0$，所以构造 $\{n,1,n-1,2,n-2,\dots\}$；
当 $n$ 是偶数时，$\frac{n(n+1)}{2}\equiv k\pmod n\iff n(n+1)\equiv 2k\pmod n\iff k=\frac{n}{2}$，所以构造 $\left\{n,\frac{n}{2},1,n-1,2,n-2,\cdots\right\}$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include <bits/stdc++.h> using namespace std; template <typename T>void read (T&x) 0 ;int fl=1 ;char ch=getchar ();while (ch<'0' ||ch>'9' ){if (ch=='-' )fl=-1 ;ch=getchar ();}while (ch>='0' &&ch<='9' ){x=(x<<1 )+(x<<3 )+ch-'0' ;ch=getchar ();}x*=fl;} template <typename T,typename ...Args>inline void read (T&t,Args&...args) read (t);read (args...);} typedef long long LL;typedef vector<int > vi;typedef pair<int , int > pii;#define mp(x, y) make_pair(x, y) #define pb(x) emplace_back(x) int n, k;int main () read (n, k); if (n * (n + 1 ) / 2 % n != k) return puts ("-1" ), 0 ; if (n & 1 ){ printf ("%d " , n); for (int i = 1 ; i <= n / 2 ; i++) printf ("%d %d " , i, n - i); puts ("" ); } else { printf ("%d %d " , n, n / 2 ); for (int i = 1 ; i < n / 2 ; i++) printf ("%d %d " , i, n - i); puts ("" ); } return 0 ; }
G Grid Coloring $n=1,k=1,k\nmid 2n(n+1)$ 的情况无解，其余情况可以构造。
一种简单的构造方法是：轮换着用颜色按顺序涂水平边和竖直边。这样做相当于把格子涂成了阶梯状。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include <bits/stdc++.h> using namespace std;template <typename T>void read (T&x) 0 ;int fl=1 ;char ch=getchar ();while (ch<'0' ||ch>'9' ){if (ch=='-' )fl=-1 ;ch=getchar ();}while (ch>='0' &&ch<='9' ){x=(x<<1 )+(x<<3 )+ch-'0' ;ch=getchar ();}x*=fl;} template <typename T,typename ...Args>inline void read (T&t,Args&...args) read (t);read (args...);}typedef long long LL;typedef vector<int > vi;typedef pair<int , int > pii;#define mp(x, y) make_pair(x, y) #define pb(x) emplace_back(x) int T, n, k;int main () for (read (T); T; T--){ read (n, k); if (2 * n * (n + 1 ) % k){ puts ("-1" ); continue ; } if (n == 1 || k == 1 ){ puts ("-1" ); continue ; } int now = 0 ; vi vert; for (int i = 1 ; i <= n + 1 ; i++){ for (int j = 1 ; j <= n; j++){ now = now % k + 1 ; printf ("%d " , now); } puts ("" ); if (i <= n){ for (int j = 1 ; j <= n + 1 ; j++){ now = now % k + 1 ; vert.pb (now); } } } for (int i = 0 ; i <= n; i++){ for (int j = i; j < n * (n + 1 ); j += n + 1 ) printf ("%d " , vert[j]); puts ("" ); } } return 0 ; }
H Harmony Pairs 一个无比暴力的数位 $\text{dp}$。
设 $dp[i,j,0/1,0/1/2]$ 表示“从高到低考虑前 $i$ 位数，$S(A)$ 和 $S(B)$ 之差为 $j$，$B$ 是否顶住上界，$A$ 和 $B$ 的关系是什么”的数有多少，然后暴力枚举 $A$ 和 $B$ 第 $i$ 位的数字进行转移。
复杂度：$O(n^2\cdot 10^3)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 #include <bits/stdc++.h> using namespace std;template <typename T>void read (T&x) 0 ;int fl=1 ;char ch=getchar ();while (ch<'0' ||ch>'9' ){if (ch=='-' )fl=-1 ;ch=getchar ();}while (ch>='0' &&ch<='9' ){x=(x<<1 )+(x<<3 )+ch-'0' ;ch=getchar ();}x*=fl;} template <typename T,typename ...Args>inline void read (T&t,Args&...args) read (t);read (args...);}typedef long long LL;typedef vector<int > vi;typedef pair<int , int > pii;#define mp(x, y) make_pair(x, y) #define pb(x) emplace_back(x) const LL MOD = 1e9 + 7 ;int n;char s[105 ];LL dp[105 ][2005 ][2 ][3 ]; int main () scanf ("%s" , s+1 ); n = strlen (s+1 ); dp[0 ][1000 ][1 ][0 ] = 1 ; for (int i = 1 ; i <= n; i++){ for (int j = -900 ; j <= 900 ; j++){ for (int A = 0 ; A <= 9 ; A++){ for (int B = 0 ; B <= 9 ; B++){ int diff = j + A - B; if (diff < -900 || diff > 900 ) continue ; if (A == B) (dp[i][diff+1000 ][0 ][0 ] += dp[i-1 ][j+1000 ][0 ][0 ]) %= MOD; else if (A < B) (dp[i][diff+1000 ][0 ][1 ] += dp[i-1 ][j+1000 ][0 ][0 ]) %= MOD; else (dp[i][diff+1000 ][0 ][2 ] += dp[i-1 ][j+1000 ][0 ][0 ]) %= MOD; (dp[i][diff+1000 ][0 ][1 ] += dp[i-1 ][j+1000 ][0 ][1 ]) %= MOD; (dp[i][diff+1000 ][0 ][2 ] += dp[i-1 ][j+1000 ][0 ][2 ]) %= MOD; if (B > (s[i]-'0' )) continue ; if (B == s[i]-'0' ){ if (A == B) (dp[i][diff+1000 ][1 ][0 ] += dp[i-1 ][j+1000 ][1 ][0 ]) %= MOD; else if (A < B) (dp[i][diff+1000 ][1 ][1 ] += dp[i-1 ][j+1000 ][1 ][0 ]) %= MOD; (dp[i][diff+1000 ][1 ][1 ] += dp[i-1 ][j+1000 ][1 ][1 ]) %= MOD; } else { if (A == B) (dp[i][diff+1000 ][0 ][0 ] += dp[i-1 ][j+1000 ][1 ][0 ]) %= MOD; else if (A < B) (dp[i][diff+1000 ][0 ][1 ] += dp[i-1 ][j+1000 ][1 ][0 ]) %= MOD; else (dp[i][diff+1000 ][0 ][2 ] += dp[i-1 ][j+1000 ][1 ][0 ]) %= MOD; (dp[i][diff+1000 ][0 ][1 ] += dp[i-1 ][j+1000 ][1 ][1 ]) %= MOD; (dp[i][diff+1000 ][0 ][2 ] += dp[i-1 ][j+1000 ][1 ][2 ]) %= MOD; } } } } } LL res = 0 ; for (int d = 1 ; d <= 900 ; d++){ res += dp[n][d+1000 ][0 ][0 ] + dp[n][d+1000 ][0 ][1 ] + dp[n][d+1000 ][1 ][0 ] + dp[n][d+1000 ][1 ][1 ]; res %= MOD; } printf ("%lld\n" , res); return 0 ; }
这道题的关键在与求出一次 $k$ 约瑟夫变换的置换数组，这之后置换 $x$ 次可以快速幂完成。
设上一次取出的数当时从左往右数第 $p$ 个，现在还剩 $c$ 个数，那么这次取出的数是从 $p$ 开始数 $k$ 个，对 $c$ 取模，即第 $(p+k-1-1)\bmod c+1$ 个数。可以用线段树完成。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 #include <bits/stdc++.h> using namespace std;template <typename T>void read (T&x) 0 ;int fl=1 ;char ch=getchar ();while (ch<'0' ||ch>'9' ){if (ch=='-' )fl=-1 ;ch=getchar ();}while (ch>='0' &&ch<='9' ){x=(x<<1 )+(x<<3 )+ch-'0' ;ch=getchar ();}x*=fl;} template <typename T,typename ...Args>inline void read (T&t,Args&...args) read (t);read (args...);}typedef long long LL;typedef vector<int > vi;typedef pair<int , int > pii;#define mp(x, y) make_pair(x, y) #define pb(x) emplace_back(x) const int N = 100005 ;int n, m, k, x;struct segTree { int l, r, sz; }tr[N<<2 ]; #define lid id<<1 #define rid id<<1|1 #define mid ((tr[id].l + tr[id].r) >> 1) inline void pushup (int id) tr[id].sz = tr[lid].sz + tr[rid].sz; } void build (int id, int l, int r) tr[id].l = l, tr[id].r = r; if (l == r){ tr[id].sz = 1 ; return ; } build (lid, l, mid), build (rid, mid+1 , r); pushup (id); } void del (int id, int pos) if (tr[id].l == tr[id].r){ tr[id].sz--; return ; } if (pos <= mid) del (lid, pos); else del (rid, pos); pushup (id); } int queryKth (int id, int k) if (tr[id].l == tr[id].r) return tr[id].l; if (tr[lid].sz >= k) return queryKth (lid, k); else return queryKth (rid, k - tr[lid].sz); } vi get () { vi res (n+1 ) ; int p = 1 , c = n; build (1 , 1 , n); for (int i = 1 ; i <= n; i++){ res[i] = queryKth (1 , (p + k - 2 ) % c + 1 ); del (1 , res[i]); p = (p + k - 2 ) % c + 1 , c--; } return res; } inline vi trans (vi a, vi b) vi res (n+1 ) ; for (int i = 1 ; i <= n; i++) res[i] = a[b[i]]; return res; } inline void fpow (vi &res, vi bs, int idx) while (idx){ if (idx & 1 ) res = trans (res, bs); bs = trans (bs, bs); idx >>= 1 ; } } int main () read (n, m); vi a (n+1 ) ; for (int i = 1 ; i <= n; i++) a[i] = i; while (m--){ read (k, x); vi t = get (); fpow (a, t, x); } for (int i = 1 ; i <= n; i++) printf ("%d " , a[i]); puts ("" ); return 0 ; }
K K-Bag 我的做法很玄学 ，虽然过了，但是不知道正确性到底咋样……
我先遍历所有数，对每个相同的数从小到大进行编号，但是编号不小于已经编过的号。举例说明：$\{2,3,2,1,3,3,2,1\}$ 的编号是 $1,1,2,2,2,3,3,3$，其中，第三个数字 $2$ 是第二次出现的，所以编号为 $2$ ，第四个数字 $1$ 虽然是第一次出现，但是我们已经有编号为 $2$ 的数了，所以从 $2$ 开始编。其实这样做本质就是把序列给划分了，为判断是否是一个合法的划分，只需要判断除了首尾两段以外，其他编号相同的连续一段长度是否等于 $k$。
但是这样做完会被 $\text{Hack}$，例如：$\{2,3,1,3,2,3,2,1,3,2\}$ 的编号是 $1,1,1,2,2,3,3,3,4,4$，编号为 $2$ 的长度只有 $2$，会被判断成 NO。究其原因，是因为第三个数 $1$ 本应被划分到后面的段（即本应编为 $2$），却在这里被往前划了。未解决这个问题，我就……呃……从后往前修正一下编号，比如这个 $1$ 的下一个 $1$ 编号是 $3$，所以我就把它编号改成 $3-1=2$，然后就过了……（虽然看上去很不对的样纸）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 #include <bits/stdc++.h> using namespace std; template <typename T>void read (T&x) 0 ;int fl=1 ;char ch=getchar ();while (ch<'0' ||ch>'9' ){if (ch=='-' )fl=-1 ;ch=getchar ();}while (ch>='0' &&ch<='9' ){x=(x<<1 )+(x<<3 )+ch-'0' ;ch=getchar ();}x*=fl;} template <typename T,typename ...Args>inline void read (T&t,Args&...args) read (t);read (args...);} typedef long long LL;typedef vector<int > vi;typedef pair<int , int > pii;#define mp(x, y) make_pair(x, y) #define pb(x) emplace_back(x) const int N = 500005 ; int T, n, k, a[N], tag[N], t[N]; bool check () for (int i = 1 ; i <= n; i++){ int j = i; while (j < n && tag[j+1 ] == tag[i]) j++; if (j - i + 1 != k) if (i != 1 && j != n) return false ; i = j; } return true ; } int main () for (read (T); T; T--){ read (n, k); for (int i = 1 ; i <= n; i++){ read (a[i]); t[i] = a[i]; tag[i] = 0 ; } sort (t+1 , t+n+1 ); int len = unique (t+1 , t+n+1 ) - (t+1 ); for (int i = 1 ; i <= n; i++) a[i] = lower_bound (t+1 , t+len+1 , a[i]) - t; int mxtag = 0 ; vi pre (n+5 ) ; bool ok = true ; for (int i = 1 ; i <= n; i++){ if (a[i] > k || a[i] < 1 ){ ok = false ; break ; } tag[i] = max (mxtag, pre[a[i]] + 1 ); pre[a[i]] = tag[i]; mxtag = max (mxtag, tag[i]); } if (!ok){ puts ("NO" ); continue ; } ok = check (); if (ok){ puts ("YES" ); continue ; } vi suc (n+5 ) ; for (int i = n; i >= 1 ; i--){ if (!suc[a[i]]) suc[a[i]] = tag[i]; else tag[i] = --suc[a[i]]; } ok = check (); if (ok){ puts ("YES" ); continue ; } else puts ("NO" ); } return 0 ; }