Codeforces Round #660 https://codeforces.com/contest/1388 E 题意 平面上有一些线段，将他们投影到$x$轴上，使得彼此不想交(但是可以挨着)，设最左边的点和最右边的点的横坐标分别是$x_l, x_r$， 求$min{x_r-x_l}$ Solution 首先对于两个线段$s_1, s_2$, 并且$s_1.y < s_2.y$, 交叉连接他们的左右端点，得到一个向量集合$bound$，对投影向量限制限制。 因此先两两枚举，得到投影向量的可行的取值。 而且最优的投影向量，是集合$bound$中的某一项 因此，对剩下的可行的投影向量, 假设当前枚举的方向是$k_i$，计算 $$ max{x_j+y_jKi}-min{x_j+y_jk_i} $$ 计算这个式子可以用Convex hull trick, 然后不断更新ans #include <cstdio> #include <stack> #include <set> #include <cmath> #include <map> #include <time.h> #include <vector> #include <iostream> #include <string> #include <cstring> #include <algorithm> #include <memory.h> #include <cstdlib> #include <queue> #include <iomanip> #include <bitset> #include <unordered_map> #include <assert.h> #include <list> #define P pair<int, int> #define LL long long #define LD long double #define PLL pair<LL, LL> #define mset(a, b) memset(a, b, sizeof(a)) #define rep(i, a, b) for (int i = a; i < b; i++) #define PI acos(-1.0) #define random(x) rand() % x #define debug(x) cout << #x << " " << x << "\n" using namespace std; const int inf = 0x3f3f3f3f; const LL __64inf = 0x3f3f3f3f3f3f3f3f; #ifdef DEBUG const int MAX = 1e3 + 50; #else const int MAX = 1e6 + 50; #endif const int mod = 998244353; void file_read(){ #ifdef DEBUG freopen64("in", "r", stdin); #endif } struct Seg { double xl, xr, y; Seg(double xl, double xr, double y) : xl(xl), xr(xr), y(y) {} }; vector<Seg> seg; vector<pair<double, double>> bd; void bound() { for(int i = 0; i < seg.size(); i++) { for(int j = i+1; j < seg.size(); j++) { if(seg[i].y == seg[j].y) continue; auto s1 = seg[i]; auto s2 = seg[j]; if(s1.y > s2.y) swap(s1, s2); double beta1 = (s1.xr - s2.xl) / (s2.y - s1.y); double beta2 = (s1.xl - s2.xr) / (s2.y - s1.y); bd.emplace_back(beta2, beta1); } } } void filter(vector<double> &theta) { double cur = -__64inf; for(auto x : bd) { if(x.first >= cur) { theta.push_back(x.first); if(cur > -__64inf) theta.push_back(cur); } cur = max(cur, x.second); } theta.push_back(cur); } double cross(pair<double, double> A, pair<double, double> B) { return (A.first - B.first) / (B.second - A.second); } template<typename Cmp_1, typename Cmp_2> struct Convex { int top; vector<pair<double, double>> pts; vector<double> X; pair<double, double> stk[3000]; Cmp_1 cmp_1; Cmp_2 cmp_2; Convex(vector<Seg> &seg) : cmp_1(Cmp_1()), cmp_2(Cmp_2()) { for(auto s : seg) { pts.emplace_back(s.xl, s.y); pts.emplace_back(s.xr, s.y); } sort(pts.begin(), pts.end(), [this](const pair<double, double> &A, const pair<double, double> &B){ if(abs(A.second - B.second) < 1e-8 ) return this->cmp_1(A.first, B.first);//return A.first < B.first; // return A.second > B.second; return this->cmp_2(A.second, B.second); }); int i = 0; top = 0; stk[top++] = pts[0]; while(i < pts.size() and abs(pts[i].second-pts[0].second) < 1e-8) i++; if(i == pts.size()) { X.push_back(-__64inf); return ; } stk[top++] = pts[i++]; while(i < pts.size()) { int j = i; while(j < pts.size() and abs(pts[j].second-pts[i].second) < 1e-8) j++; if(j == pts.size()) break; auto cur = pts[j]; while(top >= 2) { double cross_x = cross(stk[top-1], stk[top-2]); double cross_cur = cross(cur, stk[top-2]); if(cross_cur < cross_x) top--; else break; } stk[top++] = cur; i = j+1; } X.push_back(-__64inf); for(int i = 1; i < top; i++) { X.push_back(cross(stk[i-1], stk[i])); } } double query(double a) { int idx = lower_bound(X.begin(), X.end(), a)- X.begin(); idx--; return stk[idx].first + stk[idx].second * a; } }; struct Less { bool operator () (double A, double B) { return A < B; } }; struct Great { bool operator () (double A, double B) { return A > B; } }; int main(){ #ifdef DEBUG freopen64("in", "r", stdin); #endif int n; scanf("%d", &n); set<double> Y; for(int i = 0; i < n; i++) { double xl, xr, y; scanf("%lf%lf%lf", &xl, &xr, &y) ; seg.emplace_back(xl, xr, y); Y.insert(y); } if(Y.size() == 1) { double Min = __64inf, Max = -__64inf; for(auto s : seg) { Min = min(s.xl, Min); Max = max(Max, s.xr); } printf("%.10f\n", Max-Min); return 0; } bound(); vector<double> theta; sort(bd.begin(), bd.end()); filter(theta); #ifdef DEBUG for(auto t : theta) printf("%.2f ", t); puts(""); #endif double ans = __64inf; Convex<Less, Great> left(seg); Convex<Great, Less> right(seg); for(auto x : theta) { double l = left.query(x); double r = right.query(x); ans = min(ans, r-l); } printf("%.10f\n", ans); } A B C D A B C D ...

nowcoder 2020 多校 第三场 E Two Matchings 题意 可以简化题意为，每个点有个权重$w$，两个点$i,j$相连的代价$abs(w_i-w_j)$,找两个没有重叠的匹配使得代价最小 Solution 其实就是在将数字用长度为偶数的环连起来，求最小代价。进一步可以发现，环用长度为4或6，长度更长的环可以被分解达到更小的代价 LL n; LL a[MAX]; LL dp[MAX][2]; LL four(const vector<LL> &a){ return 2LL * (a[3]-a[0]); } LL six(const vector<LL> &a){ return 2LL * (a[5]-a[0]); } int main(){ #ifdef DEBUG freopen("in", "r", stdin); #endif int T; scanf("%d", &T); while (T--) { cin >> n; for(int i = 0; i < n; i++) cin >> a[i]; sort(a, a+n); for(LL i = 0; i <= n; i++ ) dp[i][0] = dp[i][1] = __64inf; dp[3][0] = 2LL * (a[3]-a[0]); dp[5][0] = 2LL * (a[5]-a[0]); dp[7][0] = 2LL * (a[7]-a[4] + a[3] - a[0]); for(LL i = 9; i < n; i+=2){ dp[i][0] = min(dp[i-4][0], dp[i-4][1]) + four(vector<LL>({a[i-3], a[i-2], a[i-1], a[i]})); dp[i][1] = min(dp[i-6][0], dp[i-6][1]) + six(vector<LL>({a[i-5], a[i-4], a[i-3], a[i-2], a[i-1], a[i]})); } printf("%d\n", min(dp[n-1][0], dp[n-1][1])); } } F Fraction Construction Problem 题意 ...

nowcoder 2020 多校 第五场 https://ac.nowcoder.com/acm/contest/5670 B Graph tire树，最小生成树 题意： 给一个带有边权的树，可以删除或添加边，但要保证： 图联通 环上边权异或为0 Solution 不管怎么操作，两点路径上边权的异或值是固定的，于是问题就转化成一个最小生成树问题。每次选出不联通的点集$S_1$, $S_2$, 将他们联通的代价是 $$ \min\limits_{u\in S_1 v\in S_2} {\mathord{dis}(u,v)} $$ 可以通过tire树实现这个过程，就是tire树合并子节点，复杂度为$O(n\log n)$ #include <cstdio> #include <stack> #include <set> #include <cmath> #include <map> #include <time.h> #include <vector> #include <iostream> #include <string> #include <cstring> #include <algorithm> #include <memory.h> #include <cstdlib> #include <queue> #include <iomanip> #include <bitset> #include <unordered_map> #include <assert.h> #define P pair<int, int> #define LL long long #define LD long double #define PLL pair<LL, LL> #define mset(a, b) memset(a, b, sizeof(a)) #define rep(i, a, b) for (int i = a; i < b; i++) #define PI acos(-1.0) #define random(x) rand() % x #define debug(x) cout << #x << " " << x << "\n" using namespace std; const int inf = 0x3f3f3f3f; const LL __64inf = 0x3f3f3f3f3f3f3f3f; #ifdef DEBUG const int MAX = 1e3 + 50; #else const int MAX = 3e6 + 50; #endif const int mod = 10007; LL pow2[100]; vector<P> G[MAX]; int dis[MAX]; struct Tire{ int nex[MAX][2]; int siz[MAX]; int tot ; LL ans; void init(){ ans = 0; siz[0] = 0; mset(nex[0], 0); tot = 1; } void add(int x, int d) { int rt = 0; for(int i = d; i >= 0; i--){ int e = x & pow2[i] ? 1 : 0; if(!nex[rt][e]) { mset(nex[tot], 0); siz[tot] = 0; nex[rt][e] = tot ++; } rt = nex[rt][e]; siz[rt] ++; } } LL query(int val, int u, int d) { int rt = u; LL res = val; for(int i = d; i >= 0; i--){ if(res & pow2[i]) { if(nex[rt][1]) { res ^= pow2[i]; rt = nex[rt][1]; } else rt = nex[rt][0]; } else { if(nex[rt][0]) { rt = nex[rt][0]; } else { res ^= pow2[i]; rt = nex[rt][1]; } } } return res; } LL merge(int l, int r, int val, int d, int row_d){ if(!nex[l][0] and !nex[l][1]) { return query(val, r, row_d); } LL res = inf; if(nex[l][0]) res = min(res, merge(nex[l][0], r, val, d-1, row_d)); if(nex[l][1]) res = min(res, merge(nex[l][1], r, val^pow2[d], d-1, row_d)); return res; } void dfs(int u, int val, int d) { if(nex[u][0]) dfs(nex[u][0], val, d-1); if(nex[u][1]) dfs(nex[u][1], val ^ pow2[d], d-1); if(!nex[u][0] or !nex[u][1]) return; int l = nex[u][0], r = nex[u][1]; if(siz[l] > siz[r]) swap(l, r); ans += 1LL * merge(l, r, 0, d-1, d-1) + pow2[d]; } }tire; void dfs(int u, int p, int d){ dis[u] = d; for(int i = 0; i < G[u].size(); i++){ int v = G[u][i].first; if(v == p) continue; dfs(v, u, d^G[u][i].second); } } int main(){ #ifdef DEBUG freopen64("in", "r", stdin); #endif pow2[0] = 1; for(int i = 1; i < 32; i++) pow2[i] = pow2[i-1] << 1; int n; scanf("%d", &n); for(int i = 1; i < n; i++) { int u, v, c; scanf("%d%d%d", &u, &v, &c); u++, v++; G[u].emplace_back(v, c); G[v].emplace_back(u, c); } dfs(1, -1, 0); tire.init(); for(int i = 1; i <= n; i++) tire.add(dis[i], 29); tire.dfs(0, 0, 29); printf("%lld\n", tire.ans); return 0; } D Drop Voicing 最长上升子序列 ...

POJ 3376 tire + manacher 题意 http://poj.org/problem?id=3376 给$n$个串，两两连接，一共$n^2$种，求其中有多少是回文， 字符串的长度和小于$2e6$ Solution 在考虑第$i$个串$t$和多少个串$s$拼接是回文时，计算$s+t$是回文的数量，将所有数量累加就是最终的回文数。 首先考虑什么情况下，两个串拼接会是一个回文串。 case 1： s=reverse(t) $$ \begin{cases} s = a_0\dots a_{n-1} \newline t = a_{n-1}\dots a_0 \end{cases} $$ case 2 $$ \begin{cases} \begin{matrix} &\mathrm{palindrome} \newline s = a_0\dots a_i &\overbrace{a_{i+1}\dots a_{n-1}} \end{matrix} \newline \newline t = a_i\dots a_0 \end{cases} $$ 以及对称的情况 $$ \begin{cases} s = a_{n-1}\dots a_i \newline \begin{matrix} \ \ \ \ \ \mathrm{palindrome} &\newline t = \overbrace{a_0\dots a_{i-1}} &a_i\dots a_{n-1} \end{matrix} \end{cases} $$ ...

nowcoder 2020 多校 第二场 https://ac.nowcoder.com/acm/contest/5667 A All with Pairs 题意 给$n$个串，定义$f(s,t)$为$s$前缀和$t$后缀最长的长度，求$\sum_i\sum_j f(s_i, s_j)^2$ Solution 先把每个串的后缀hash的值存下来，对每个串$s_i$,求$\sum_j f(s_i, s_j)^2$。对于$s_i$的每个前缀都可以查询hash求出 对应多少后缀，但是有可能一对$s_i, s_j$会有多个贡献，因此要用next数组去重 const unsigned long long base = 131; // vector<string> str; string str[MAX]; unordered_map<unsigned long long, int> mp; int nex[MAX]; int cnt[MAX]; void get_hash(const string &s){ unsigned long long res = 0; unsigned long long p = 1; for(int i = s.size()-1; i >= 0; i--){ // unsigned long long x = s[i] - 'a'+1; res += (s[i]-'a'+1) * p; p *= base; mp[res]++; } } void get_next(const string &t){ nex[0] = -1; int k = -1; for(int i = 1; i < t.size(); i++){ while(k > -1 and t[k+1] != t[i]) k = nex[k]; if(t[k+1] == t[i]) k++; nex[i] = k; } } int main(){ #ifdef DEBUG freopen("in", "r", stdin); #endif int n; scanf("%d", &n); // cin >> n; for(int i = 0; i < n; i++){ // string s; cin >> str[i]; // str.push_back(s); get_hash(str[i]); } LL ans = 0; for(int i = 0; i < n; i++){ unsigned long long cur_has = 0 ; for(int j = 0; j < str[i].size(); j++){ cur_has = cur_has * base + (str[i][j] - 'a' + 1); // cnt[j] = mp[cur_has]; auto it = mp.find(cur_has); if(it != mp.end()) cnt[j] = it->second; else cnt[j] = 0; } get_next(str[i]); for(int j = 1; j < str[i].size(); j++){ if(nex[j] >= 0) cnt[nex[j]] -= cnt[j]; } for(LL j = 0; j < str[i].size(); j++){ ans = (ans + 1LL * cnt[j] * (j+1LL) % mod * (j+1LL) % mod) % mod; } } printf("%lld\n", ans); // cout << ans << '\n'; } B Boundary 题意 ...

AtCoder-Sum of gcd of Tuples (Hard) 题意 https://atcoder.jp/contests/abc162/tasks/abc162_e 求$\sum\gcd(a_1,a_2,\cdots,a_n)$,其中$a_i\in[1,K]$ Solution 直接计算肯定是不好计算的，可以考虑按$gcd$的值进行分类，问题就转化为一个计数问题 $\displaystyle \gcd(a,b)=d\Rightarrow\gcd(\frac{a}{d},\frac{b}{d})=1$ $\displaystyle {\gcd(a_1,\cdots, a_n)=d的数量}={\gcd(\frac{a_1}{d},\cdots,\frac{a_n}{d})=1的数量}$ 那么， $$ Ans=\sum_{d=1}^{K}dF(\lfloor\frac{K}{d}\rfloor, N) $$ 其中$F(K,N)$表示$\gcd(a_1,\cdots,a_N)=1$的个数，$a_i\in[1,K]$ 可以用容斥算出$\displaystyle F(K,N)=K^N-\sum_{i=1}^{K}F(\lfloor\frac{K}{i}\rfloor)$ #include <cstdio> #include <stack> #include <set> #include <cmath> #include <map> #include <time.h> #include <vector> #include <iostream> #include <string> #include <cstring> #include <algorithm> #include <memory.h> #include <cstdlib> #include <queue> #include <iomanip> // #include <unordered_map> #define P pair<int, int> #define LL long long #define LD long double #define PLL pair<LL, LL> #define mset(a, b) memset(a, b, sizeof(a)) #define rep(i, a, b) for (int i = a; i < b; i++) #define PI acos(-1.0) #define random(x) rand() % x #define debug(x) cout << #x << " " << x << "\n" using namespace std; const int inf = 0x3f3f3f3f; const LL __64inf = 0x3f3f3f3f3f3f3f3f; #ifdef DEBUG const int MAX = 1e6 + 50; #else const int MAX = 1e6 + 50; #endif const int mod = 1e9 + 7; LL N,K; LL f[MAX]; LL fact[MAX]; inline LL add(LL x, LL y){ LL res = x + y; return res >= mod ? res - mod : res; } inline LL qpow(LL x, LL n){ LL res = 1; while (n) { if(n &1) res = res * x % mod; x = x * x % mod; n >>= 1; } return res; } LL F(LL K, LL N){ if(f[K]) return f[K]; LL &res =f[K]; if(K==1){ return res = 1; } // res = qpow(K, N); res = fact[K]; for(LL i = 2, j; i <= K; i=j+1){ j = K/(K/i); // res = add(res, mod-F(K/i, N)); LL tmp = (j-i+1LL) * F(K/i, N) % mod; res = add(res, mod-tmp); } return res; } int main(){ #ifdef DEBUG freopen("in", "r", stdin); #endif scanf("%lld%lld", &N, &K); for(LL i = 1; i <= K; i++) fact[i] = qpow(i, N); LL ans = 0; f[1] = 1LL; for(LL k= 1; k <= K; k++){ F(k, N); } for(LL i = 1, j; i <= K; i++){ ans += f[K/i] % mod * i % mod; if(ans >= mod) ans -= mod; } printf("%lld\n", ans); }

arch lab Download archlab-handout 安装模拟器 解决undefined reference to ’matherr‘ 参考 Y86-64模拟器的安装与出现对’matherr’未定义引用问题的解决 Part A 在这部分要在sim/misc中完成，我们要编写和模拟三个Y86-64程序 sum.ys： 遍历链表求和 # begin at 0 .pos 0 irmovq stack,%rsp call main halt .align 8 ele1: .quad 0x00a .quad ele2 ele2: .quad 0x0b0 .quad ele3 ele3: .quad 0xc00 .quad 0 main: irmovq ele1,%rdi call rsum ret rsum: xorq %rax,%rax andq %rdi,%rdi je L1 pushq %rbx mrmovq (%rdi),%rbx mrmovq 8(%rdi),%rdi call rsum addq %rbx,%rax popq %rbx L1: ret .pos 0x200 stack: 用YAS编译后，再用YIS运行 ...

Prime Distance On Tree 题意 Prime Distance On Tree 给个树，从树上随机选取一对点$u,v$,求$\delta(u,v)$是素数的概率 Solution 可以从生成函数的角度考虑 假设rt是一个树的树根，而且rt的深度是d，将树中节点的深度统计出来，记为$f_{rt，d}$，如果$u,v…$是rt的子节点，那么rt对答案的贡献就是生成函数中素数项的系数，那么问题就是怎么计算生成函数了 $$ \sum_{u,v \in son(rt)} f_{u,1} * f_{v, 1} $$ 这个式子中的素数项系数和与下式是相等的,计算$f$是很简单的 $$ \Big(f_{rt,0}^2 - \sum_{u \in son(rt) }f_{u,1}^2\Big) / 2 $$ 为了确保复杂度不会太高，需要用点分治 #include <cstdio> #include <stack> #include <set> #include <cmath> #include <map> #include <time.h> #include <vector> #include <iostream> #include <string> #include <cstring> #include <algorithm> #include <memory.h> #include <cstdlib> #include <queue> #include <iomanip> // #include <unordered_map> #define P pair<int, int> #define LL long long #define LD long double #define PLL pair<LL, LL> #define mset(a, b) memset(a, b, sizeof(a)) #define rep(i, a, b) for (int i = a; i < b; i++) #define PI acos(-1.0) #define random(x) rand() % x #define debug(x) cout << #x << " " << x << "\n" using namespace std; const int inf = 0x3f3f3f3f; const LL __64inf = 0x3f3f3f3f3f3f3f3f; #ifdef DEBUG const int MAX = 2e3 + 50; #else const int MAX = 1e5 + 50; #endif const int mod = 1e9 + 7; #include <complex> namespace Prime { vector<int> prime; bool isprime[MAX<<1]; void init(int n){ mset(isprime, 1); isprime[0] = isprime[1] = 0; for(int i = 2; i < n; i++){ if(isprime[i]){ prime.push_back(i); } for(int j = 0; j < prime.size() and prime[j] * i < n; j++){ isprime[i * prime[j]] = 0; if(i * prime[j] == 0) break; } } } } // namespace namePrimPrime namespace FFT { complex<double> a[MAX<<2], b[MAX<<2]; int rev[MAX]; void fft(complex<double> *a, int n, int inv){ int bit = 0; while((1<<bit) < n) bit++; for(int i = 0; i < n; i++){ rev[i] = (rev[i>>1]>>1) | ((i & 1) << (bit-1)); if(i < rev[i]) swap(a[i], a[rev[i]]); } for(int mid = 1; mid < n; mid <<= 1){ complex<double> wn(cos(PI/mid), inv*sin(PI/mid)); for(int i = 0; i < n; i += (mid<<1)){ complex<double> w(1, 0); for(int j = 0; j < mid; j++, w *= wn){ complex<double> u = a[i+j], t = w * a[i+j+mid]; a[i+j] = u + t, a[i+j+mid] = u - t; } } } } void product(int n){ fft(a, n, 1); fft(b, n, 1); for(int i = 0; i <= n; i++) a[i] *= b[i]; fft(a, n, -1); } } // namespace nameFFTFFT vector<int> E[MAX]; bool vis[MAX]; // LL dep[MAX]; LL dep[MAX], dep_num[MAX]; int cnt; int siz[MAX]; int dfsG(int u, int p, int& Min, int &rt, int n){ siz[u] = 1; int Max = -1; for(int i = 0; i < E[u].size(); i++){ int v = E[u][i]; if(vis[v] or v == p) continue; siz[u] += dfsG(v, u, Min, rt, n); Max = max(Max, siz[v]); } Max = max(Max, n - siz[u]); if(Max < Min){ Min = Max, rt = u; } return siz[u]; } int dfsN(int u, int p){ int res = 1; for(int i = 0; i < E[u].size(); i++){ int v = E[u][i]; if(vis[v] or v == p) continue; res += dfsN(v, u); } return res; } int find_rt(int u){ int Min = inf; int rt = -1; int n = dfsN(u, -1); dfsG(u, -1, Min, rt, n); return rt; } LL dfs(int u, int p, int d){ // return max_dep dep[cnt++] = d; LL max_dep = d; for(int i = 0; i < E[u].size(); i++){ int v = E[u][i]; if(v == p or vis[v]) continue; max_dep = max(max_dep, dfs(v, u, d+1)); } return max_dep; } LL calcu(int u, int d){ // mset(dep, 0); cnt = 0; dfs(u, -1, d); LL Max = 0; for(int i = 0; i < cnt; i++){ dep_num[dep[i]]++; Max = max(Max, dep[i]); } LL res = 0; int N = 1; while(N <= Max * 2) N <<= 1; for(int i = 0; i < N; i++){ if(i <= Max) FFT::a[i] = FFT::b[i] = complex<double>(dep_num[i], 0); else FFT::a[i] = FFT::b[i] = complex<double>(0, 0); } FFT::product(N); for(int i = 0; i < Prime::prime.size() and Prime::prime[i] <= 2*Max; i++){ res += (LL)(FFT::a[Prime::prime[i]].real() / N + 0.5); } for(int i = 0; i < cnt; i++) dep_num[dep[i]]--; return res; } LL solve(int u){ // vis[u] = 1; int rt = find_rt(u); vis[rt] = 1; LL res = calcu(rt, 0); for(int i = 0; i < E[rt].size(); i++){ if(vis[E[rt][i]]) continue; res -= calcu(E[rt][i], 1); res += solve(E[rt][i]); } // for(int i = 0; i < E[rt].size(); i++){ // if(vis[E[rt][i]]) continue; // res += solve(E[rt][i]); // } return res; } int main(){ #ifdef DEBUG freopen("in", "r", stdin); #endif int n; scanf("%d", &n); Prime::init(MAX << 1); for(int i = 1; i < n; i++){ int u, v; scanf("%d%d", &u, &v); E[u].push_back(v); E[v].push_back(u); } LL up = solve(1); LL down = (LL)n * (n-1); printf("%.7lf\n", 1.0 * up / down); return 0; }

Polya计数 将波利亚计数定理整理在这里，作为一个总结和介绍，也方便以后复习 为什么学习Polya计数定理 通过Polya计数定理，我们可以计算等价类的数量，比如下面这个问题： 用$m$种颜色给一个正方形染色，如果正方形可以自由转动，求染色方案数 让我们从一些概念开始 1 等价关系 1.1 等价关系的定义 假设$V$是一个集合，$S$是定义在$V$上的一个关系，若$S$有如下性质： 自反性 传递性 对称性 那么， $S$就是一个等价关系 $a$和$b$有关系$S$,可以记为$aSb$ 假设定义关系$S$，图形$a$可以旋转得到$b$ $\Leftrightarrow$ $aSb$ 例如图中的$方块_1$和$方块_2$具有关系$S$，即他们可以通过旋转得到彼此，而$方块_1$和$方块_2$则没有关系$S$ 1.2 等价类 通过上图，可以看出来：$方块_1$和$方块_2$是同一类的，而$方块_1$和$方块_2$则是另外两类，于是可以想到集合$V$上的等价关系$S$将集合的元素划分到不同的类中，我们把它称为等价类 而包含元素$a$的等价类则是由满足$aSb$的所有元素$b$组成的(当然也包含元素$a$),即$C(a)={b\in V | \ aSb}$ 仔细想一想，不难发现两个不同等价类是不相交的 2 置换群 2.1 置换群的定义 假设$A={1,2,\dotsc, n}$，通过置换，将$A$中的元素重新排列，得到另一个排列$a_1, a_2, \dotsc, a_n$，可以把这个过程写成 $$ \left ( \begin{matrix} 1 & 2 & \dotsc & n \newline a_1 & a_2 & \dotsc & a_n \end{matrix} \right ) $$ 所以，可以将置换看成一个双射函数$f:{1,2,\dotsc, n} \rightarrow {1,2,\dotsc, n}$ ...

Rock Paper Scissors Lizard Spock 题意： Rock Paper Scissors Lizard Spock 有五种手势，类似于石头剪刀布，有两个串$s, t$,由这五种手势组成，从某个位置开始匹配，如果$t_i$能赢$s_j$得一分，求一个$pos(0\le pos \le len(s)-len(t))$，使得得分最多 Solution： 将上图记为$G$，如果$op_1$可以赢$op_2$，则$G(op_1, op_2)=1$, 枚举可以得分的手势,假设当前手势为$op$, $$ \begin{aligned} t’_i &=(reverse\ t_i == op ? 1 : 0) \newline s’_i &= G[op][s_i] \end{aligned} $$ 将$t’,s’$做卷积，累加每次的结果，再遍历一遍匹配的起始位置，取最大值 #include <cstdio> #include <stack> #include <set> #include <cmath> #include <map> #include <time.h> #include <vector> #include <iostream> #include <string> #include <cstring> #include <algorithm> #include <memory.h> #include <cstdlib> #include <queue> #include <iomanip> #include <unordered_map> #define P pair<int, int> #define LL long long #define LD long double #define PLL pair<LL, LL> #define mset(a, b) memset(a, b, sizeof(a)) #define rep(i, a, b) for (int i = a; i < b; i++) #define PI acos(-1.0) #define random(x) rand() % x #define debug(x) cout << #x << " " << x << "\n" using namespace std; const int inf = 0x3f3f3f3f; const LL __64inf = 0x3f3f3f3f3f3f3f3f; #ifdef DEBUG const int MAX = 2e3 + 50; #else const int MAX = 1e6 + 50; #endif const int mod = 1e9 + 7; #include <complex> namespace FFT { int rev[MAX * 4]; int cnt[MAX * 4]; void fft(complex<double> *a, int n, int inv){ int bit = 0; while((1<<bit) < n) bit++; for(int i = 0; i < n; i++){ rev[i] = (rev[i>>1]>>1) | ((i & 1) << (bit-1)); if(i < rev[i]) swap(a[i], a[rev[i]]); } for(int mid = 1; mid < n; mid <<= 1){ complex<double> wn(cos(PI/mid), inv*sin(PI/mid)); for(int i = 0; i < n; i += (mid<<1)){ complex<double> w(1, 0); for(int j = 0; j < mid; j++, w*=wn){ complex<double> u = a[i+j], t = w * a[i+j+mid]; a[i+j] = u + t, a[i+j+mid] = u-t; } } } } }; int N; char s[MAX], t[MAX], rev_t[MAX]; complex<double> a[MAX*4], b[MAX*4]; int mark[100][100]; void init(){ mark['S']['P'] = 1; mark['P']['R'] = 1; mark['R']['L'] = 1; mark['L']['K'] = 1; mark['K']['S'] = 1; mark['S']['L'] = 1; mark['L']['P'] = 1; mark['P']['K'] = 1; mark['K']['R'] = 1; mark['R']['S'] = 1; } void solve(char op, int n, int m){ for(int i = 0; i < n; i++) a[i] = complex<double>(mark[op][s[i]], 0); for(int i = n; i < N; i++) a[i] = complex<double>(0, 0); for(int i = 0; i < m; i++) b[i] = complex<double>(rev_t[i]==op?1:0, 0); for(int i = m; i < N; i++) b[i] = complex<double>(0, 0); ; FFT::fft(a, N, 1); FFT::fft(b, N, 1); for(int i = 0; i < N;i++) a[i] *= b[i]; FFT::fft(a, N, -1); for(int i = m-1; i <= n-1; i++) FFT::cnt[i] += (int)(a[i].real() / N + 0.5); return; } int main(){ #ifdef DEBUG freopen("in", "r", stdin); #endif init(); scanf("%s%s", s, t); int n = strlen(s), m = strlen(t); N = 1; while(N <= n+m) N <<= 1; for(int i = 0; i < m; i++) rev_t[i] = t[m-i-1]; vector<char> ops({'R','P', 'S', 'K', 'L'}); for(auto op : ops){ solve(op, n, m); } int ans = 0; for(int i = m-1; i <= n-1; i++){ ans = max(ans, FFT::cnt[i]); // printf("%d ", FFT::cnt[i]); } // puts(""); printf("%d\n", ans); return 0; }