NOI 赛前抱 3 个月的佛脚（ku

完成度：5/17

Catcats Contest #1

字符串 (count)

神必转化，壬都傻了

假设一个串有 \(i\) 个 \(1\) 和 \(n-i\) 个 \(0\)，则定义 \(0\) 的权值是 \(i\)，\(1\) 的权值是 \(i-n\)，一个字符串的权值是其所有字符权值之和。

所有长为 \(l\) 的循环子串的权值的平均值为 \(0\)，且两个相同长度的字符串相差不超过 \(1\) 当且仅当权值相差不超过 \(n\)，且相同长度的字符串权值\(\bmod n\) 的值都相同。

所以，一个字符串是好的当且仅当所有子串的权值 \(\in(-n,n)\)，也就是说 \(\exist k\in[0,n)\) 使得所有前缀和 \(\in(k-n,k]\)。

从大到小枚举 \(k\)，此时字符串是唯一的，维护出这个字符串然后顺便计算出不符合询问串限制的位置数量，如果为 \(0\) 说明满足条件。

时间复杂度 \(O(n^2)\)，而且还可以得到答案也是 \(\le n^2\) 的。注意不要算重了。

#include<bits/stdc++.h>
#define PB emplace_back
using namespace std;
const int N = 1030;
int T, n, ans, pre[N], cnt; bool num[N]; char str[N];
vector<int> vec[N];
void solve(){
    scanf("%s", str+1); n = strlen(str+1); ans = 0;
    for(int i = 0;i <= n;++ i){
        cnt = pre[0] = 0; vec[0].PB(0);
        for(int j = 1;j <= n;++ j){
            if(pre[j-1] + i < n){
                pre[j] = pre[j-1] + i;
                num[j] = false;
                cnt += str[j] == '1';
            } else {
                pre[j] = pre[j-1] + i - n;
                num[j] = true;
                cnt += str[j] == '0';
            } if(pre[j] >= 0) vec[pre[j]].PB(j);
        } for(int j = n-1;;-- j){
            ans += !vec[j].empty() && !cnt;
            if(!j) break;
            for(int k : vec[j]){
                cnt += (str[k] == '0') + (str[k+1] == '1') - (str[k] == '1') - (str[k+1] == '0');
                swap(num[k], num[k+1]);
            }
        } for(int j = 0;j < n;++ j) vec[j].resize(0);
    } printf("%d\n", ans);
} int main(){scanf("%d", &T); while(T --) solve();}

Catcats Contest #2

己酸集合 (geo)

每个询问分别做，对左右边界跑 two-pointer。时间复杂度 \(O(nq)\)。

构造题 (buhui)

IOI2006 的加强版，有点东西（/kel

首先发现一个性质：如果凸包上 \(S,T\) 不是连续段，则一定无解。构造证明其他情况都有解。

主要思路是把凸包范围做一个三角剖分，然后每个三角形内部分别做。

不知为何考虑递归构造，设 \(\texttt{Solve(A,B,C)}\) 表示 \(A,B,C\) 是逆时针方向，其中 \(A\) 与 \(B,C\) 分别属于不同集合，\(BC\) 有连边，你需要将 \(\Delta ABC\) 内部的所有与 \(A\) 所属集合相同的点与 \(A\) 连通，与 \(B\) 所属集合相同的点与 \(B\) 或 \(C\) 中一个连通。

若内部点全都与 \(B,C\) 所属集合相同，就可以随便分治了，因为全部相同所以只要保证是一棵生成树即可。

否则任意选择一个与 \(A\) 所属集合相同的点 \(X\)，与 \(A\) 连边，将该三角形划分为三个小三角形，变成了子问题 \(\texttt{Solve(X,B,C),Solve(C,A,X),Solve(B,X,A)}\)，递归做。

至于三角剖分，分类讨论一下：

• 若凸包上的点所属集合全相同，那么就在内部找一个不同的，以其为中心做三角剖分。
• 若凸包上的点所属集合不同，则一定是一段 \(S\) 还有一段 \(T\)，两边可以分别做，具体实现见代码（雾

在随机数据下的时间复杂度大概是 \(O(n\log n)\)，最坏是 \(O(n^2)\)。

#include<bits/stdc++.h>
#define PB emplace_back
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> pii;
const int N = 3003;
template<typename T>
void read(T &x){
    int ch = getchar(); x = 0;
    for(;ch < '0' || ch > '9';ch = getchar());
    for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
} int n, m;
struct Point {
    int x, y;
    Point(int _x = 0, int _y = 0): x(_x), y(_y){}
    bool operator < (const Point &o) const {if(x != o.x) return x < o.x; return y < o.y;}
    LL operator * (const Point &o) const {return (LL)x * o.y - (LL)y * o.x;}
    Point operator - (const Point &o) const {return Point(x - o.x, y - o.y);}
    Point operator + (const Point &o) const {return Point(x + o.x, y + o.y);}
} p[N];
vector<pii> ans[2];
inline bool col(int x){return x > n;}
void adde(int x, int y){
    assert(col(x) == col(y));
    if(col(x)) ans[1].PB(x - n, y - n);
    else ans[0].PB(x, y);
}
bool intri(int a, int b, int c, int d){ // d in angle bac ?
    Point v1 = p[b] - p[a], v2 = p[c] - p[a], v3 = p[d] - p[a];
    if(v1 * v2 < 0) swap(v1, v2);
    return v1 * v3 > 0 && v3 * v2 > 0;
}
void work(int a, int b, int c, VI now){
    // printf("a = %d, b = %d, c = %d\n", a, b, c);
    if(now.empty()) return; VI tmp;
    for(int i : now) if(col(i) == col(a)){
        adde(a, i); tmp.resize(0);
        for(int j : now) if(intri(i, a, b, j)) tmp.PB(j);
        work(b, i, a, tmp); tmp.resize(0);
        for(int j : now) if(intri(i, b, c, j)) tmp.PB(j);
        work(i, b, c, tmp); tmp.resize(0);
        for(int j : now) if(intri(i, c, a, j)) tmp.PB(j);
        work(c, a, i, tmp); return;
    } static LL dis[N];
    for(int i : now) dis[i] = labs((p[c] - p[b]) * (p[i] - p[b]));
    sort(now.begin(), now.end(), [&](int u, int v){return dis[u] < dis[v];});
    adde(b, now[0]); for(int i = 1;i < now.size();++ i) adde(now[i-1], now[i]);
}
int main(){
    read(n); read(m);
    for(int i = 1;i <= n+m;++ i){read(p[i].x); read(p[i].y);}
    VI id(n+m), hul; iota(id.begin(), id.end(), 1);
    sort(id.begin(), id.end(), [&](int a, int b){return p[a] < p[b];});
    for(int i : id){
        while(hul.size() > 1 && (p[i] - p[hul.back()]) * (p[i] - p[hul[hul.size()-2]]) > 0) hul.pop_back();
        hul.PB(i);
    } id.pop_back(); reverse(id.begin(), id.end()); int tmp = hul.size();
    for(int i : id){
        while(hul.size() > tmp && (p[i] - p[hul.back()]) * (p[i] - p[hul[hul.size()-2]]) > 0) hul.pop_back();
        hul.PB(i);
    } hul.pop_back();
    int pos = 1; for(;pos < hul.size() && col(hul[0]) == col(hul[pos]);++ pos);
    // printf("pos = %d\n", pos);
    if(pos == hul.size()){
        for(int i = 1;i < hul.size();++ i) adde(hul[i-1], hul[i]);
        hul.PB(hul[0]);
        for(int i = 1;i <= n+m;++ i) if(col(i) != col(hul[0])){
            for(int j = 1;j < hul.size();++ j){
                int a = hul[j-1], b = hul[j]; VI tmp;
                for(int k = 1;k <= n+m;++ k) if(intri(i, a, b, k)) tmp.PB(k);
                work(i, a, b, tmp);
            } break;
        }
    } else {
        rotate(hul.begin(), hul.begin() + pos, hul.end());
        // for(int i : hul) printf("%d ", i); putchar('\n');
        for(pos = 1;pos < hul.size() && col(hul[0]) == col(hul[pos]);++ pos);
        for(int _ = pos;_ < hul.size();++ _) if(col(hul[0]) == col(hul[_])){puts("Impossible"); return 0;}
        for(int i = 1;i < pos;++ i){
            int a = hul[pos], b = hul[i-1], c = hul[i]; VI tmp;
            for(int k = 1;k <= n+m;++ k) if(intri(a, b, c, k)) tmp.PB(k);
            adde(b, c); work(a, b, c, tmp);
        } for(int i = pos+1;i < hul.size();++ i){
            int a = hul[0], b = hul[i-1], c = hul[i]; VI tmp;
            for(int k = 1;k <= n+m;++ k) if(intri(a, b, c, k)) tmp.PB(k);
            adde(b, c); work(a, b, c, tmp);
        }
    } assert(ans[0].size() == n-1); assert(ans[1].size() == m-1);
    for(int _ = 0;_ < 2;++ _) for(pii &u : ans[_]) printf("%d %d\n", u.fi, u.se);
}

最长环 (route)

人类智慧，肝败吓疯（

#include<bits/stdc++.h>
using namespace std;
const int N = 303, B = 666, NIF = -1000000007;
template<typename T>
void read(T &x){
    int ch = getchar(); x = 0;
    for(;ch < '0' || ch > '9';ch = getchar());
    for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
} template<typename T>
bool chmax(T &a, const T &b){if(a < b) return a = b, 1; return 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m, k, x[N], y[N], z[N], a[N][N], d[2][N][N], w[N][N][3], ans; bool f[N], o;
void ins(int u, int v, int x){
    int p = 0;
    for(;p < 3;++ p){
        int t = w[u][v][p];
        if(a[u][t] + a[v][t] < a[u][x] + a[v][x]) break;
    } if(p < 3){
        for(int i = 2;i > p;-- i) w[u][v][i] = w[u][v][i-1];
        w[u][v][p] = x;
    }
}
void calc(int u, int v, int x, int y){
    int p = 0;
    while(w[u][v][p] == x || w[u][v][p] == y) ++ p;
    int z = w[u][v][p];
    chmax(d[o][x][y], a[x][u] + a[u][z] + a[z][v] + a[v][y]);
}
void solve(int k){
    for(int i = 0;i <= n;++ i)
        for(int j = 0;j <= n;++ j) d[o][i][j] = NIF;
    switch(k){
    case 1: for(int i = 1;i <= n;++ i) if(f[i] == o) d[o][i][i] = 0; break;
    case 2:
        for(int i = 1;i <= m;++ i) if(f[x[i]] == o && f[y[i]] == o)
            d[o][x[i]][y[i]] = d[o][y[i]][x[i]] = z[i]; break;
    case 3:
        for(int i = 1;i <= m;++ i) if(f[x[i]] == o && f[y[i]] == o)
            for(int j = 1;j <= m;++ j) if(i != j && f[x[j]] == o && f[y[j]] == o){
                if(x[i] == x[j]) chmax(d[o][y[i]][y[j]], z[i] + z[j]);
                else if(y[i] == x[j]) chmax(d[o][x[i]][y[j]], z[i] + z[j]);
                else if(x[i] == y[j]) chmax(d[o][y[i]][x[j]], z[i] + z[j]);
                else if(y[i] == y[j]) chmax(d[o][x[i]][x[j]], z[i] + z[j]);
            } break;
    case 4:
        for(int i = 1;i <= m;++ i) if(f[x[i]] == o && f[y[i]] == o)
            for(int j = 1;j <= m;++ j) if(i != j && f[x[j]] == o && f[y[j]] == o && x[i] != x[j] && x[i] != y[j] && y[i] != x[j] && y[i] != y[j]){
                chmax(d[o][x[i]][x[j]], z[i] + z[j] + a[y[i]][y[j]]);
                chmax(d[o][x[i]][y[j]], z[i] + z[j] + a[y[i]][x[j]]);
                chmax(d[o][y[i]][x[j]], z[i] + z[j] + a[x[i]][y[j]]);
                chmax(d[o][y[i]][y[j]], z[i] + z[j] + a[x[i]][x[j]]);
            } break;
    case 5:
        for(int i = 1;i <= n;++ i) if(f[i] == o)
            for(int j = 1;j <= n;++ j) if(f[j] == o){
                w[i][j][0] = w[i][j][1] = w[i][j][2] = 0;
            }
        for(int i = 1;i <= m;++ i) if(f[x[i]] == o && f[y[i]] == o)
            for(int j = 1;j <= m;++ j) if(i != j && f[x[j]] == o && f[y[j]] == o){
                if(x[i] == x[j]) ins(y[i], y[j], x[i]);
                else if(y[i] == x[j]) ins(x[i], y[j], y[i]);
                else if(x[i] == y[j]) ins(y[i], x[j], x[i]);
                else if(y[i] == y[j]) ins(x[i], x[j], y[i]);
            }
        for(int i = 1;i <= m;++ i) if(f[x[i]] == o && f[y[i]] == o)
            for(int j = 1;j <= m;++ j) if(i != j && f[x[j]] == o && f[y[j]] == o && x[i] != x[j] && x[i] != y[j] && y[i] != x[j] && y[i] != y[j]){
                calc(x[i], x[j], y[i], y[j]);
                calc(y[i], x[j], x[i], y[j]);
                calc(x[i], y[j], y[i], x[j]);
                calc(y[i], y[j], x[i], x[j]);
            }
    }
}
int main(){
    read(n); read(m); read(k);
    for(int i = 0;i <= n;++ i)
        for(int j = 0;j <= n;++ j) a[i][j] = NIF;
    for(int i = 1;i <= m;++ i){
        read(x[i]); read(y[i]); read(z[i]);
        a[x[i]][y[i]] = a[y[i]][x[i]] = z[i];
    } for(int _ = 0;_ < B;++ _){
        for(int i = 1;i <= n;++ i) f[i] = rng() & 1;
        if(k == 6){o = 0; solve(2); o = 1; solve(4);}
        else {o = 0; solve(k>>1); o = 1; solve(k+1>>1);}
        for(int i = 1;i <= m;++ i) if(f[x[i]] && !f[y[i]]) swap(x[i], y[i]);
        for(int i = 1;i <= m;++ i) if(f[x[i]] != f[y[i]])
            for(int j = 1;j <= m;++ j) if(i != j && f[x[j]] != f[y[j]])
                chmax(ans, d[0][x[i]][x[j]] + d[1][y[i]][y[j]] + z[i] + z[j]);
    } if(ans > 0) printf("%d\n", ans); else puts("impossible");
}

Catcats Contest #3

计数题 (count)

壬被玩傻了

首先 \(n,m\) 都为奇数时答案是 \(1\)。

其次 \(n\) 为偶数，\(m\) 为奇数时答案是 \((n/2+1)^{(m-1)/2}\)，这事因为 \(1\) 所在列已经被确定，每个要填的列都有 \(n/2+1\) 种独立的方式。

然后就是 \(n,m\) 都为偶数的情况。若将整个矩阵划分为 \(2\times 2\) 的 block，则每块都恰有一个 \(1\)，且每行、每列填的 \(1\) 的位置形如 \(010101|101010\)，我们按列做 dp，将这个分界线的位置记录下来，并且将第 \(i\) 个 block 内的 \(1\) 是否靠右记录下来。要做的就是避免下面这种情况：

.x..	..x.
...x	x...
x...	...x
..x.	.x..

转移是一个 SOS 形式，时间复杂度 \(O(n^3m2^n)\)，其中这里的 \(n,m\) 是原来的一半。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, m, lim, mod, dp[2][13][4096], a[4096], ans; bool cr;
int ksm(int a, int b){
    int res = 1;
    for(;b;b >>= 1, a = (LL)a * a % mod)
        if(b & 1) res = (LL)res * a % mod;
    return res;
} void qmo(int &x){x += x >> 31 & mod;}
void FMT(int *a){
    for(int mid = 1;mid < lim;mid <<= 1)
        for(int i = 0;i < lim;i += mid<<1)
            for(int j = i;j < i+mid;++ j)
                qmo(a[j] += a[j|mid] - mod);
}
int main(){
    scanf("%d%d%d", &n, &m, &mod);
    if((n & 1) && (m & 1)){puts("1"); return 0;}
    if(n & 1) swap(n, m); if(m & 1){printf("%d\n", ksm((n>>1)+1, m>>1)); return 0;}
    n>>=1; m>>=1; lim = 1<<n;
    for(int i = 0;i <= n;++ i)
        for(int j = 0;j < lim;++ j)
            dp[0][i][j] = 1;
    for(int _ = 1;_ < m;++ _, cr ^= 1){
        memset(dp[!cr], 0, sizeof dp[!cr]);
        for(int i = 0;i <= n;++ i){
            memcpy(a, dp[cr][i], lim<<2); FMT(a);
            for(int j = 0;j <= n;++ j)
                for(int S = 0;S < lim;++ S){
                    int T = S;
                    for(int k = i+1;k < j;++ k)
                        if((S>>k-1&1) && !(S>>k&1)) T |= 1<<k;
                    for(int k = j;k < i-1;++ k)
                        if(!(S>>k&1) && (S>>k+1&1)) T |= 1<<k;
                    qmo(dp[!cr][j][S] += a[T] - mod);
                }
        }
    }
    for(int i = 0;i <= n;++ i)
        for(int j = 0;j < lim;++ j)
            qmo(ans += dp[cr][i][j] - mod);
    printf("%d\n", ans);
}

Catcats Contest #4

平方过百万 (million)

有一个我不会的转化：对于第 \(2\) 种操作，在 \((u_p,v_p)\) 之间加一条权值为操作编号的边，则编号为 \(T\) 的询问 \(\texttt{1 u}\) 即为求从 \(u\) 开始走权值递增且 \(\le T\) 的边，能到达的节点个数。

可以使用点分治，假设当前处理的分治中心是 \(r\)，对每个操作 \(2\)，求出从它到达分治中心的最早时间，和分治中心能到达它所出发的最晚时间。这大概是一个二维偏序，用排序 + 树状数组即可，时间复杂度 \(O((n+m)\log n)\)。有点烦，自闭了

Catcats Contest #5

构造题 (buhui)

stm 域论，等拿到数学女孩第 5 册了就学（

有限域相关基础：\(\text{GF}(p^n)\) 可以表示为系数模 \(p\)，整体模 \(n\) 次本原多项式 \(F\) 的意义下定义四则运算，由不超过 \(n-1\) 次的多项式构成的代数结构。

可以证明这东西是域，也可以证明它存在且唯一。其特征为 \(p\)，所以 \((x+y)^p=x^p+y^p\)。

那至于这题怎么做：取最小的 \(w\) 使得 \(2^w>|S|\)，计算出 \(\text{GF}(2^w)\)，构造 \(a_i=i\cdot 2^w+f(i)\)，其中 \(f(i)\) 是 \(\text{GF}(2^w)\) 意义下的立方。

至于正确性，考虑反证法：假设存在 \((i_1,j_1)\ne (i_2,j_2)\) 使得 \(a_{i_1}\oplus a_{j_1}=a_{i_2}\oplus a_{j_2}\)，则 \(i_1,j_1,i_2,j_2\) 必须两两不同，且在 \(\text{GF}(2^w)\) 意义下 \(i_1+j_1=i_2+j_2\ne 0\)，且 \(i_1^3+j_1^3=i_2^3+j_2^3\)，得到 \(i_1^2+i_1j_1+j_1^2=i_2^2+i_2j_2+j_2^2\)，所以 \(i_1j_1=i_2j_2\)。

令 \(s=i_1+j_1,p=i_1j_1\)，得到 \(x(s-x)=p\) 有至少 \(4\) 个根，而其只有 \(2\) 次，矛盾。

因此 \(a_i\oplus a_j\) 两两不同，得证。本原多项式可以事先预处理，具体实现上 mod 2 运算可以使用异或运算。

这个构造的背景在于一个经典问题：如何在 \([0,p)^2\) 中构造 \(p\) 个整点使得不存在三点共线，其中 \(p\) 是质数。一种构造是取 \(x_i=i,y_i=i^2\bmod p\)，可以得到 \(\frac{y_j-y_i}{x_j-x_i}=\frac{y_k-y_j}{x_k-x_j}\Rightarrow x_i+x_j=x_j+x_k\Rightarrow x_i=x_k\)。

#include<bits/stdc++.h>
using namespace std;
const int _[] = {2,7,11,19,37,67,131,283,515,1033,2053,4105};
int n, mod, lim;
int red(int x){
    int p = mod; while(p <= x) p <<= 1;
    for(;p >= mod;p >>= 1) if((x ^ p) < x) x ^= p;
    return x;
} int mul(int x, int y){
    int r = 0;
    for(;x;x >>= 1, y <<= 1) if(x & 1) r ^= y;
    return red(r);
}
int main(){
    scanf("%d", &n); mod = _[n-1]; lim = 1<<n;
    for(int i = 0;i < lim;++ i) printf("%d ", i<<n|mul(mul(i,i),i));
}