• 2022 年牛客多校第七场补题记录

    A Floor Tiles in a Park

    题意：给定 h × w h \times w h×w 的矩形，将其分为 k k k 个子矩形的方案数。 h , w ≤ 1 × 1 0 9 h,w \leq 1\times 10^9 h,w≤1×109， 1 ≤ k ≤ 5 1 \leq k \leq 5 1≤k≤5。

    解法： k k k 很小可以考虑分类讨论，但是不建议此做法。最好的分类方案是以子矩形在大矩形内部分割产生的点的位置进行分类讨论。小于等于 4 4 4 的情况可以简单分类讨论出来。

    对于 k = 5 k=5 k=5 有以下四大类：

    1. 全竖线分割、全横线分割（无新产生分割点）。 ( h − 1 4 ) + ( w − 1 4 ) \displaystyle {h-1 \choose 4}+{w-1 \choose 4} (4h−1​)+(4w−1​)。
    2. 产生三个在一条线上的分割点：大体可以认为是四个竖条子矩形再从中选择若干个相邻的竖条合并后拆分出一个长的横矩形，如上。这种情况有 26 26 26 种：在这里插入图片描述 26 ( ( h − 1 3 ) ( w − 1 2 ) + ( h − 1 2 ) ( w − 1 3 ) ) \displaystyle 26\left({h-1 \choose 3}{w-1 \choose 2}+{h-1 \choose 2}{w-1 \choose 3}\right) 26((3h−1​)(2w−1​)+(2h−1​)(3w−1​))。
    3. 分割点只有两个：在这里插入图片描述
      这种情况下中间的 7 7 7 条分割线只需要随便擦除一根即可： 7 ( ( h − 1 2 ) ( w − 1 1 ) + ( h − 1 1 ) ( w − 1 2 ) ) \displaystyle 7\left({h-1 \choose 2}{w-1 \choose 1}+{h-1 \choose 1}{w-1 \choose 2}\right) 7((2h−1​)(1w−1​)+(1h−1​)(2w−1​))。
    4. 产生了 3 , 4 3,4 3,4 个不共线分割点，可以围成一个矩形：在这里插入图片描述
      这种情况最为复杂，其中有四个分割点的有 16 16 16 种，右侧三个点的有 48 48 48 种情况，总共有 64 64 64 种情况： 64 ( ( h − 1 2 ) ( w − 1 2 ) + ( h − 1 2 ) ( w − 1 2 ) ) \displaystyle 64\left({h-1 \choose 2}{w-1 \choose 2}+{h-1 \choose 2}{w-1 \choose 2}\right) 64((2h−1​)(2w−1​)+(2h−1​)(2w−1​))。

    因而此题真诚的建议使用拉格朗日插值。注意到分割方案数 f ( h , w ) f(h,w) f(h,w) 是关于 h , w h,w h,w 的最高五次多项式函数，因而大胆暴力打表然后插值即可： f ( h , w ) = ∑ i = 1 5 ∑ j = 1 5 y i , j l h , i ( h ) l k , j ( w ) \displaystyle f(h,w)=\sum_{i=1}^5\sum_{j=1}^5 y_{i,j}l_{h,i}(h)l_{k,j}(w) f(h,w)=i=1∑5​j=1∑5​yi,j​lh,i​(h)lk,j​(w)，其中 l i ( x ) = ∏ j = 1 , j ≠ i x − i j − i \displaystyle l_i(x)=\prod_{j=1,j \neq i}\dfrac{x-i}{j-i} li​(x)=j=1,j=i∏​j−ix−i​。暴力打表可以暴力枚举 k k k 个子矩形的位置。具体代码实现可以参考其他题解。

    B Rotate Sum 3

    题意：给定平面上一 n n n 个点的整点凸多边形，使其绕着任意对称轴在空间中旋转，求其扫过的体积。若无对称轴则输出 0 0 0。 n ≤ 1 × 1 0 5 n \leq 1\times 10^5 n≤1×105。

    解法：由于是整点多边形，因而对称轴至多不超过 O ( log ⁡ n ) O(\log n) O(logn) 条，可以考虑暴力枚举每条多边形的边的中垂线以及点来判定对称轴。更优美的解法（或对于非整点多边形）是使用哈希或者 Manacher 来判定（字符串题与计算几何的第一次交流），具体做法为，找到这个多边形的几何中心 ( 1 n ∑ i = 1 n x i , 1 n ∑ i = 1 n y i ) \displaystyle \left( \dfrac{1}{n}\sum_{i=1}^n x_i,\dfrac{1}{n} \sum_{i=1}^n y_i\right) (n1​i=1∑n​xi​,n1​i=1∑n​yi​)，依次记录每个点到几何中心的极角、多边形边长，以点-边-点的顺序得到一个数组并倍长，若存在对称轴则原数组存在一个长度为 2 n − 1 2n-1 2n−1 的回文串。

    若对称轴超过两条，则一定是一个以几何中心为球心，半径为几何中心到凸包顶点最远距离的一个球：

    在这里插入图片描述

    在这里插入图片描述

    上图是以矩形为例。

    若对称轴仅一条，则为一旋转体体积，可以根据垂直对称轴方向进行切分，每一段为一圆台体积： ∑ i = 1 k π 3 h i ( r i 2 + r i − 1 2 + r i r i − 1 ) \displaystyle \sum_{i=1}^k \dfrac{\pi}{3}h_i(r_i^2+r_{i-1}^2+r_ir_{i-1}) i=1∑k​3π​hi​(ri2​+ri−12​+ri​ri−1​)。

    注意精度问题，在判断对称轴的时候最好使用 int128。

    #include 
#define fp(i, a, b) for (int i = a, i##_ = (b) + 1; i < i##_; ++i)
#define fd(i, a, b) for (int i = a, i##_ = (b) - 1; i > i##_; --i)

using namespace std;
using T = double;
using db = double;

const db eps = 1e-8, pi = acos(-1);

int sgn(T x) { return (x > eps) - (x < -eps); }

struct Vec {
    T x, y;
    bool operator<(Vec p) const { return tie(x, y) < tie(p.x, p.y); }
    bool operator==(Vec p) const { return tie(x, y) == tie(p.x, p.y); }
    Vec operator+(Vec p) const { return {x + p.x, y + p.y}; }
    Vec operator-(Vec p) const { return {x - p.x, y - p.y}; }
    Vec operator*(T d) const { return {x * d, y * d}; }
    T operator*(Vec p) const { return x * p.x + y * p.y; }
    T cross(Vec p) const { return x * p.y - y * p.x; }
    T cross(Vec a, Vec b) const { return (a - *this).cross(b - *this); }
    Vec operator/(T d) const { return {x / d, y / d}; }
    T len2() const { return x * x + y * y; }
    int onLeft(Vec p) const { return sgn(cross(p)); }
};

using Poly = vector<Vec>; // polygon, points, vectors

struct Line {
    Vec p, v; // point on line, direction vector
    int onLeft(Vec a) const { return v.onLeft(a - p); }
};

vector<Line> polygonAxes(Poly a) {
    int n = a.size(), m = 3 * n;
    a.push_back(a[0]), a.push_back(a[1]);
    vector<pair<T, T>> s(n * 2);
    for (int i = 1, j = 0; i <= n; ++i, j += 2)
        s[j] = {(a[i] - a[i - 1]).len2(), 0},
        s[j + 1] = {a[i].cross(a[i - 1], a[i + 1]), (a[i + 1] - a[i]) * (a[i - 1] - a[i])};
    s.insert(s.end(), s.begin(), s.begin() + n);
    vector<int> f(m), res;
    for (int r = 0, p = 0, i = 0; i < m; i++) {
        f[i] = r > i ? min(r - i, f[p * 2 - i]) : 1;
        while (i >= f[i] && i + f[i] < m && s[i - f[i]] == s[i + f[i]]) ++f[i];
        if (i + f[i] > r) r = i + f[i], p = i;
        if (f[i] > n) res.push_back(i);
    }
    auto get = [&](int i) {
        int x = (i + 1) / 2;
        return i & 1 ? a[x] : (a[x] + a[x + 1]) / 2;
    };
    vector<Line> axe;
    for (auto i : res)
        axe.push_back({get(i), get(i) - get(i - n)});
    return axe;
}

void Solve() {
    int n;
    scanf("%d", &n);
    Poly a(n);
    for (auto &p : a) scanf("%lf%lf", &p.x, &p.y);
    auto axe = polygonAxes(a);
    if (axe.empty()) return puts("0"), void();
    db ans = 0;
    if (axe.size() > 1) {
        db r = 0; Vec o;
        for (auto p : a) o = o + p;
        o = o / n;
        for (auto &p : a) r = max(r, (p - o).len2());
        ans = 4 * r * sqrt(r);
    } else {
        Vec v = axe[0].v, A = axe[0].p;
        a.push_back(a[0]);
        for (int i = 0; i < n; ++i) {
            db r = v.cross(a[i] - A), R = v.cross(a[i + 1] - A);
            if (sgn(r) >= 0 && sgn(R) >= 0)
                ans += (a[i] - a[i + 1]) * v * (r * r + R * R + r * R);
        }
        ans /= v.len2() * sqrt(v.len2());
    }
    printf("%.12lf\n", ans * pi / 3);
}
int main() {
    int t = 1;
    while (t--) Solve();
    return 0;
}

    • 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
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90

    C Constructive Problems Never Die

    题意：构造一个长度为 n n n 的排列，使得第 i i i 位不是 a i a_i ai​。 n ≤ 5 × 1 0 5 n \leq 5\times 10^5 n≤5×105。

    解法：依次记录每个值 i i i 最早在什么时候被 ban，然后顺次从前到后的填数字，依照最早被 ban 的位置从后到前的填即可，这样可以保证后面的位置永远可以腾出来给前面的。若某个数字被 n n n 个位置 ban 则无解。

    #include 
using namespace std;
int main()
{
    int t, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        vector<int> a(n), nolim, ban, vis(n + 1, 0), ans(n);
        for (int i = 0; i < n;i++)
        {
            scanf("%d", &a[i]);
            if(!vis[a[i]])
            {
                vis[a[i]] = 1;
                ban.push_back(a[i]);
            }
        }
        if (ban.size() == 1)
        {
            printf("NO\n");
            continue;
        }
        for (int i = 1; i <= n;i++)
            if(!vis[i])
                nolim.push_back(i);
        for (int i = 0; i < n;i++)
        {
            int used = 1;
            if (!ban.empty() && a[i] == ban.back())
            {
                used = 0;
                ban.pop_back();
            }
            if (!ban.empty())
            {
                ans[i] = ban.back();
                ban.pop_back();
            }
            else if(!nolim.empty())
            {
                ans[i] = nolim.back();
                nolim.pop_back();
            }
            if (!used)
                ban.push_back(a[i]);
        }
        printf("YES\n");
        for (auto i : ans)
            printf("%d ", i);
        printf("\n");
    }
    return 0;
}

    • 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

    D The Pool

    题意：给定矩形边长 n , m n,m n,m，在坐标系中将其放置使得其四个顶点均在整点上，输出均放在整点上时，其完整覆盖的 1 × 1 1\times 1 1×1 的方格个数总和。 n , m ≤ 1 × 1 0 18 n,m \leq 1\times 10^{18} n,m≤1×1018，多测， T ≤ 1 × 1 0 4 T \leq 1\times 10^4 T≤1×104。

    解法：建议参考www.bilibili.com/video/BV1kx411q7kK以学习高斯整数。具体内容可以参见本篇https://blog.nowcoder.net/n/c7d224736e8e4cdd9ab701cfa6d560ac

    E Ternary Search

    题意：给定 n n n 个互不相同的数字和一个初始为空的序列 { a } \{a\} {a}，依次将其插入到序列的末尾，问至少经过几次相邻交换操作可以让序列符合三分特性（单峰）。 n ≤ 2 × 1 0 5 n \leq 2\times 10^5 n≤2×105，对每次插入输出答案。

    解法：首先离散化。考虑最终的形态为一高-低-高形态（一个最低值），因而一个数字所处的位置有最低值左侧（L）和最低值右侧（R）两种。统计最终的交换次数等价于统计与一个数字有关的逆序对（或顺序对）数目，取决于所在的位置。

    若当前新加入的数字 a i a_i ai​ 在 L 侧，其贡献是确定的——它在原序列的左侧，所有比 a i a_i ai​ 小的数字个数（不分 L，R 侧）。这是因为无论波谷在哪里，它处于左侧是一定得要移动到所有比它小数字的左侧。若当前数字 a i a_i ai​ 在 R 侧，则会随着后续数字的增加而发生改变——当前同时处于 R 侧且比它大的，并且在原序列中在 i i i 前面的数字个数。显然它只需要和 R 侧的数字进行交换而不涉及 L 侧的数字。 a i a_i ai​ 对于总答案的贡献，为处于 L 侧答案与处于 R 侧答案的更小值。显然容易注意到， a i a_i ai​ 在 L 侧的答案是固定的，但是在 R 侧的答案会不断增加。

    此时考虑加入一个数字，在刚加入这个数字时默认这个数字放在 R 侧。维护两个树状数组 T1，T2 和一个线段树 T，分别维护之前所有的数字（方便查询当前数字 L 侧的答案），在 R 侧的数字（方便查询当前数字在 R 侧的答案），以及一个线段树维护已经有过的数字的 L 侧答案减去 R 侧答案的线段树，以方便统计总答案。考虑加入 a i a_i ai​ 后会对这几个树产生什么影响：

    1. T1，T2 更新。
    2. 线段树上所有下标大于等于 a i a_i ai​ 的 L-R 值减少 1 1 1——由于 a i a_i ai​ 的加入使得这部分的 R 侧答案增加了 1 1 1。
    3. 若线段树上有 L-R 的值小于等于 0 0 0 的下标，证明当前的这个值应当从 R 侧移动到 L 侧，对 T2 和线段树进行更改。

    因而可以不用关心具体波谷位置，快速的转移出当前的答案。最后只需要再将全部的值进行翻转—— a i ← n − a i + 1 a_i \leftarrow n-a_i+1 ai​←n−ai​+1 即可得到低-高-低形态的答案，二者取 min 即可。总时间复杂度 O ( n log ⁡ n ) \mathcal O(n \log n) O(nlogn)。

    #include
#define IL inline
#define LL long long
#define pb push_back
using namespace std;
const int N=2e5+3,inf=1e9;
int n,a[N],b[N];
LL ans[N];
vector<int>res;
IL int in(){
	char c;int f=1;
	while((c=getchar())<'0'||c>'9')
	  if(c=='-') f=-1;
	int x=c-'0';
	while((c=getchar())>='0'&&c<='9')
	  x=x*10+c-'0';
	return x*f;
}
struct segment{
	#define ls k<<1
	#define rs k<<1|1
	int mn[N<<2],add[N<<2];
	IL void pushup(int k){mn[k]=min(mn[ls],mn[rs]);}
	IL void Add(int k,int x){mn[k]+=x,add[k]+=x;}
	IL void pushdown(int k){
		if(add[k]) Add(ls,add[k]),Add(rs,add[k]),add[k]=0;
	}
	void build(int k,int l,int r){
		if(l==r){add[k]=0,mn[k]=inf;return;}
		int mid=l+r>>1;
		build(ls,l,mid),build(rs,mid+1,r);
		add[k]=0,pushup(k);
	}
	void moadd(int k,int l,int r,int ll,int rr,int v){
		if(l>=ll&&r<=rr) return Add(k,v);
		int mid=l+r>>1;
		pushdown(k);
		if(ll<=mid) moadd(ls,l,mid,ll,rr,v);
		if(rr>mid) moadd(rs,mid+1,r,ll,rr,v); 
		pushup(k);
	}
	void find(int k,int l,int r){
		if(mn[k]) return;
		if(l==r) return res.pb(l),void();
		pushdown(k);
		int mid=l+r>>1;
		find(ls,l,mid),find(rs,mid+1,r);
	}
	void modify(int k,int l,int r,int u,int v){
		if(l==r) return mn[k]=v,void();
		int mid=l+r>>1;
		pushdown(k);
		u<=mid?modify(ls,l,mid,u,v):modify(rs,mid+1,r,u,v);
		pushup(k);
	}
}T;
struct BIT{
	int c[N];
	IL void clear(){memset(c,0,sizeof(c));}
	IL int lb(int x){return x&-x;}
	IL void add(int y,int x){
		for(;y<=n;y+=lb(y)) c[y]+=x;
	}
	IL int ask(int y){
		int res=0;
		for(;y;y-=lb(y)) res+=c[y];
		return res;
	}
}T1,T2;
void solve(){
	T1.clear(),T2.clear(),T.build(1,1,n);
	LL now=0;
	for(int i=1;i<=n;++i){
		now+=T2.ask(n)-T2.ask(a[i]);
		T1.add(a[i],1),T2.add(a[i],1);
		T.moadd(1,1,n,a[i],n,-1);
		T.modify(1,1,n,a[i],T1.ask(a[i]-1));
		res.clear(),T.find(1,1,n);
		for(int j=0;j<res.size();++j)
		  T2.add(res[j],-1),T.modify(1,1,n,res[j],inf);
		ans[i]=min(ans[i],now);
	}
}
IL void init(){
	memset(ans,63,sizeof(ans));
	n=in();for(int i=1;i<=n;++i) a[i]=b[i]=in();
	sort(b+1,b+n+1),b[0]=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+b[0]+1,a[i])-b;
	solve();
	for(int i=1;i<=n;++i) a[i]=n-a[i]+1;
	solve();
	for(int i=1;i<=n;++i) printf("%lld\n",ans[i]);
}
int main()
{
	init();
	return 0;
}

    • 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
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98

    F Candies

    题意：给定长度为 n n n 的环形序列，若相邻两个数字和为 x x x 或相等则可删除，删除后序列填补空隙，问删除次数。 n ≤ 5 × 1 0 5 n \leq 5\times 10^5 n≤5×105。

    解法：显然消除顺序与最终结果无关。将大于等于 x 2 \dfrac{x}{2} 2x​ 的数字 a i a_i ai​ 一律当作 x − a i x-a_i x−ai​，则只有相等条件才能删除。首先不考虑环形则就是简单的栈删除，再考虑栈首尾消除即可。时间复杂度 O ( n ) \mathcal O(n) O(n)。

    #include 
using namespace std;
const int N = 100000;
vector<int> st;
int main()
{
    int n, x, ans = 0;
    scanf("%d%d", &n, &x);
    for (int i = 1, y; i <= n; i++)
    {
        scanf("%d", &y);
        if (!st.empty() && (st.back() + y == x || st.back() == y))
        {
            st.pop_back();
            ans++;
        }
        else
            st.push_back(y);
    }
    int posa = 0, posb = st.size() - 1;
    while(posa < posb)
        if(st[posa] == st[posb] || st[posa] + st[posb] == x)
        {
            posa++;
            posb--;
            ans++;
        }
        else
            break;
    printf("%d", ans);
    return 0;
}

    • 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

    G Regular Expression

    题意：给定字符串 S S S，问最短能接受 S S S 的正则表达式长度和在这个长度下的正则表达式个数。

    解法：考虑以下几种情况：

    1. S = a S=a S=a。可以的正则表达式：a，.。
    2. S = a a S=aa S=aa。可以的正则表达式：a.，.a，a*，aa，.*，..，.+，a+。
    3. S = a b S=ab S=ab。可以的正则表达式：a.，.b，ab，.*，..，.+。
    4. S S S 为全 a a a 串。可以的正则表达式：.*，.+，a+，a*。
    5. 其余情况。可以的正则表达式：.*，.+。

    I Suffix Sort

    题意：定义一个串的最小表示为——按出现某个字符第一次出现顺序从小到大的排序，并依次编号 a b c ⋯ z abc\cdots z abc⋯z。给定串 S S S，对其全部后缀进行最小表示的排序。 ∣ S ∣ ≤ 2 × 1 0 5 |S| \leq 2\times 10^5 ∣S∣≤2×105。

    解法：考虑朴素的后缀数组排序，即是对后缀 i , j i,j i,j 的最小表示排序。如果对于每对比较可以在 log ⁡ n \log n logn 的复杂度内可以完成，那么总的复杂度就为 O ( n log ⁡ 2 n ) \mathcal O(n \log^2n) O(nlog2n)。对于 log ⁡ n \log n logn 的字符串比较，通常可以转化为求 l c p \rm lcp lcp 长度，再比较接下来的第一位的大小。

    首先可以记忆每个字符所在的位置，以 O ( ∣ Σ ∣ n log ⁡ n ) \mathcal O(|\Sigma|n \log n) O(∣Σ∣nlogn) 的复杂度内计算出每个位置的最小表示中的字符映射关系。考虑如何求 l c p \rm lcp lcp 的长度，朴素的实现是依次枚举位置 i , j i,j i,j 的最小表示中每一位的字符，看它们从第 i , j i,j i,j 位开始只考虑当前字符的最长匹配长度。即：
    c h i , k : 1000 01001001 ⋯ ⏟ 后缀 i c h j , k : 0100 01001010 ⋯ ⏟ 后缀 j ch_{i,k}:1000\underbrace{01001001\cdots}_{\text{后缀}_i}\\ ch_{j,k}:0100\underbrace{01001010\cdots}_{\text{后缀}_j}\\ chi,k​:1000后缀i​ 01001001⋯​​chj,k​:0100后缀j​ 01001010⋯​​
    由上图，即是比较后缀 i , j i,j i,j 的最小表示中的第 k k k 个字符，然后仅考虑对应字符 c h i , k ch_{i,k} chi,k​ 和 c h j , k ch_{j,k} chj,k​ 的出现位置，其余字符忽略，单纯考虑它们的 l c p \rm lcp lcp。例如在上图中，这两个后缀在第 k k k 个字符（可能 c h i , k ≠ c h j , k ch_{i,k} \neq ch_{j,k} chi,k​=chj,k​）的 l c p \rm lcp lcp 就是 6 6 6。那么这个可以通过记录每一种字符出现位置的哈希值来做到 O ( log ⁡ n ) \mathcal O(\log n) O(logn) 的计算 l c p \rm lcp lcp。然后取每一种字符的 l c p \rm lcp lcp 的最小值为这一对的 l c p \rm lcp lcp。这样的朴素实现是 O ( ∣ Σ ∣ log ⁡ n ) \mathcal O(|\Sigma|\log n) O(∣Σ∣logn)，不符合要求。

    一个有力的优化是，每次二分的长度越来越短。即第二次二分的长度和是否进行二分在第一次的基础之上进行。具体来说，进行三个优化：

    1. 若 c h i , k ch_{i,k} chi,k​ 和 c h j , k ch_{j,k} chj,k​ 的第一个出现字符已经超出当前二分的最大值 r r r，则可以终止字符枚举。这是由于字符映射是根据字符出现的第一个位置递增顺序排序，若第 k k k 个字符出现位置都超过 r r r，则更后面的字符出现位置只会更靠后，而对于它们的比较中，后缀 i , j i,j i,j 在第 k k k 个字符的串的 [ i , i + r − 1 ] [i,i+r-1] [i,i+r−1] 和 [ j , j + r − 1 ] [j,j+r-1] [j,j+r−1] 范围里全是 0 0 0（未出现），则必然相同，没必要继续比较了。
    2. 此外，首先比较 [ i , i + r − 1 ] [i,i+r-1] [i,i+r−1] 和 [ j , j + r − 1 ] [j,j+r-1] [j,j+r−1] 的哈希值，若相同则当前位置没必要进行二分。
    3. 根据上一位的 r r r 来确定本次的二分上界 r r r。

    因而这样可以将复杂度降到 O ( max ⁡ ( ∣ Σ ∣ ) , log ⁡ n ) \mathcal O(\max(|\Sigma|),\log n) O(max(∣Σ∣),logn)。因而利用 sort的优秀常数，足以以 O ( n log ⁡ n max ⁡ ( log ⁡ n , ∣ Σ ∣ ) ) \mathcal O(n \log n \max(\log n,|\Sigma|)) O(nlognmax(logn,∣Σ∣)) 通过本题。

    #include 
using namespace std;
const int N = 200000;
const long long base = 2, mod = 1000000007;
long long power(long long a, long long x)
{
    long long ans = 1;
    while(x)
    {
        if (x & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        x >>= 1;
    }
    return ans;
}
long long inv(long long a)
{
    return power(a, mod - 2);
}
long long th[N + 5], invth[N + 5];
long long h[26][N + 5];
char s[N + 5];
long long get_hash(int id, int l, int r)
{
    return (h[id][r] - h[id][l - 1] + mod) % mod * invth[l - 1] % mod;
}
vector<int> pos[26];
int chrk[N + 5][26], n;
bool cmp(int a, int b)
{
    int *t1 = chrk[a], *t2 = chrk[b];
    int left = 2, right = n - max(a, b) + 1;
    for (int i = 0; i < 26 && right > 1;i++)
    {
        int l = left, r = right;
        if (t1[i] - a >= right && t2[i] - b >= right)
            break;
        if (t1[i] - a != t2[i] - b)
        {
            right = min(t1[i] - a, t2[i] - b);
            break;
        }
        int ida = s[t1[i]] - 97, idb = s[t2[i]] - 97;
        if (get_hash(ida, a, a + right - 1) == get_hash(idb, b, b + right - 1))
            continue;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (get_hash(ida, a, a + mid - 1) == get_hash(idb, b, b + mid - 1))
            {
                right = mid;
                l = mid + 1;
            }
            else
                r = mid - 1;
        }
    }
    if (max(a, b) + right > n)
        return a > b;
    vector<int> rk1(26, 0), rk2(26, 0);
    for (int i = 0; i < 26; i++)
    {
        if (t1[i] <= n)
            rk1[s[t1[i]] - 97] = i;
        if (t2[i] <= n)
            rk2[s[t2[i]] - 97] = i;
    }
    return rk1[s[a + right] - 97] < rk2[s[b + right] - 97];
}
int ans[N + 5];
int main()
{
    th[0] = invth[0] = 1;
    for (int i = 1; i <= N;i++)
        th[i] = th[i - 1] * base % mod;
    invth[N] = inv(th[N]);
    for (int i = N - 1; i >= 1;i--)
        invth[i] = invth[i + 1] * base % mod;
    scanf("%d%s", &n, s + 1);
    for (int i = 1; i <= n;i++)
    {
        ans[i] = i;
        pos[s[i] - 97].push_back(i);
        for (int j = 0; j < 26;j++)
            h[j][i] = h[j][i - 1];
        h[s[i] - 97][i] = (h[s[i] - 97][i] + th[i]) % mod;
    }
    for (int i = 0; i < 26;i++)
        pos[i].push_back(n + 1);
    for (int i = 1; i <= n;i++)
    {
        vector<int> temp(26);
        for (int j = 0; j < 26;j++)
            temp[j] = *lower_bound(pos[j].begin(), pos[j].end(), i);
        sort(temp.begin(), temp.end());
        for (int j = 0; j < 26;j++)
            chrk[i][j] = temp[j];
    }
    sort(ans + 1, ans + n + 1, cmp);
    for (int i = 1; i <= n;i++)
        printf("%d ", ans[i]);
    return 0;
}

    • 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
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104

    J Melborp Elcissalc

    题意：求长度为 n n n，且每个数字都在 [ 0 , k − 1 ] [0,k-1] [0,k−1]，使得区间连续和为 k k k 倍数的子区间有 t t t 个的序列个数。 n , k ≤ 64 n,k \leq 64 n,k≤64， t ≤ n ( n − 1 ) 2 t \leq \dfrac{n(n-1)}{2} t≤2n(n−1)​。

    解法：区间连续和很容易想到前缀和，那么问题转化为前缀和的差的倍数有 t t t 个的序列个数。又数字范围在 [ 0 , k − 1 ] [0,k-1] [0,k−1]，因而前缀和序列取模后也可以一一对应原序列。同时，区间 $[i,j] $ 的连续和为 k k k 的倍数要求前缀和序列中 s i − 1 = s j s_{i-1}=s_j si−1​=sj​，那么问题进一步被转化为，长度为 n + 1 n+1 n+1 的序列，第一个数字强制为 0 0 0，后面每个数字范围在 [ 0 , k − 1 ] [0,k-1] [0,k−1]，使得 ∑ i = 0 k − 1 c i ( c i − 1 ) 2 = t \displaystyle \sum_{i=0}^{k-1}\dfrac{c_i(c_i-1)}{2}=t i=0∑k−1​2ci​(ci​−1)​=t 的序列个数，其中 c i c_i ci​ 为数字 i i i 的出现次数，那么简单背包转移即可： f i , j , l ← ∑ k = 0 j f i − 1 , j − k , l − k ( k − 1 ) 2 ( n − j + k k ) \displaystyle f_{i,j,l} \leftarrow \sum_{k=0}^jf_{i-1,j-k,l-\frac{k(k-1)}{2}} {n-j+k\choose k} fi,j,l​←k=0∑j​fi−1,j−k,l−2k(k−1)​​(kn−j+k​)。总复杂度 O ( n k t ) \mathcal O(nkt) O(nkt)。

    #include 
using namespace std;
const int N = 100, mod = 998244353;
int f[N + 5][N + 5][N * N + 5];
int S[N + 5], C[N + 5][N + 5];
int main()
{
    int n, k, t;
    scanf("%d%d%d", &n, &k, &t);
    for (int i = 0; i <= n;i++)
        C[i][0] = C[i][i] = 1;
    for (int i = 1; i <= n;i++)
        for (int j = 1; j < i;j++)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    for (int i = 1; i <= n + 5; i++)
        S[i] = i * (i - 1) / 2;
    f[0][0][0] = 1;
    for (int i = 0; i < k;i++)
        for (int j = 0; j <= n;j++)
            for (int l = 0; j + l <= n;l++)
                for (int s = 0; s + S[l + (!i)] <= t;s++)
                    f[i + 1][j + l][s + S[l + (!i)]] = (f[i + 1][j + l][s + S[l + (!i)]] + 1ll * f[i][j][s] * C[n - j][l] % mod) % mod;
    printf("%d", f[k][n][t]);
    return 0;
}

    • 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

    K Great Party

    题意：给定 n n n 堆石子，一次一个人选一堆非空的石子拿走至少一个石子，然后可以选择将这堆石子合并到其余非空的石堆去。 q q q 次询问，给定区间 [ L , R ] [L,R] [L,R]，问有多少个子区间 [ l , r ] ⊂ [ L , R ] [l,r] \subset [L,R] [l,r]⊂[L,R] 使得先手必胜。 n , q ≤ 1 × 1 0 5 n,q \leq 1\times 10^5 n,q≤1×105。

    解法：当局面变成偶数堆时，先手不能合并操作使得堆数变成奇数（1），因而只能不断拿石子，这时后手也会做类似操作，因而堆数不变。当此时所有的堆（堆数仍为偶数）都变成了只有一个石子，那么先手必输——后手永远可以仿照先手的操作下对称棋。因而在偶数堆的局面下，先后手是可以一直玩对称棋的，直到抽到只剩一个石子为止，因而这个问题可以规约到每堆石子为 a i − 1 a_i-1 ai​−1 的 Nim 游戏。

    （1）考虑为什么不能变成奇数堆——若变成奇数堆，后手一定可以从全部的堆中选出一堆，取走若干的石子，并执行合并操作，使得剩下的堆的石子个数减一 a i − 1 a_i-1 ai​−1 的异或和为 0 0 0，此时退化到堆的个数为偶数且异或和为 0 0 0，按照刚刚的分析这时先手必败，因而推导回两步之前那么先手就不能执行合并操作。

    因而总结下来——奇数堆先手必胜，偶数堆 a i − 1 a_i-1 ai​−1 的异或和不为 0 0 0 则先手胜，否则后手胜。

    那么维护 a i − 1 a_i-1 ai​−1 的异或前缀和，问题转化到了区间查询所有前缀值的出现位置（分奇偶讨论）和个数，因而可以使用莫队通过，时间复杂度 O ( n n ) \mathcal O(n \sqrt n) O(nn ​)。

    #include
#define IL inline
#define LL long long
using namespace std;
const int N=2e5+10,M=3e6+3;
int n,m,bel[N],col[N],t,len;
LL sum[2],c[2][M];
struct hh{
	int l,r,pos;
	bool operator<(const hh a) const{
	return (bel[l]^bel[a.l])?bel[l]<bel[a.l]:r<a.r;}
}a[N];
LL ans[N];
int in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    int x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
void init()
{
	n=in()+1,m=in();
	for(int i=2;i<=n;++i) col[i]=in()-1;
	for(int i=2;i<=n;++i) col[i]^=col[i-1];
	for(int i=1;i<=m;++i){
		a[i].l=in(),a[i].r=in()+1,a[i].pos=i;
		int len=a[i].r-a[i].l;
		ans[i]=1ll*(a[i].r-a[i].l)*(a[i].r-a[i].l-1)/2+len;
	}  
}
void pre()
{
	t=sqrt(n),len=n/t;
	for(int i=1;i<=t;++i) 
	  for(int j=(i-1)*len+1;j<=i*len;++j) bel[j]=i;
	if(t*len<n){
		for(int j=t*len+1;j<=n;++j) bel[j]=t+1;
		++t;
	}
	sort(a+1,a+m+1);  
}
void solve()
{
	int l,r,j=1;
	for(int i=1;i<=t;++i)
	{
		l=(i-1)*len+1,r=l-1,sum[0]=sum[1]=0;
		for(;bel[a[j].l]==i;++j)
        {
        	while(r<a[j].r) ++r,sum[r&1]+=(++c[r&1][col[r]])-1;
        	while(l>a[j].l) --l,sum[l&1]+=(++c[l&1][col[l]])-1;
        	while(l<a[j].l) sum[l&1]-=(c[l&1][col[l]]--)-1,++l;
        	ans[a[j].pos]-=(sum[0]+sum[1]);
		}
		for(int k=1;k<=n;++k) c[k&1][col[k]]=0;
	}
	for(int i=1;i<=m;++i) printf("%lld\n",ans[i]);
}
int main()
{
	init();
	pre();
	solve();
	return 0;
}

    • 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
  • 相关阅读:
    [RK-Linux] recovery分区详解（一）
    施工安全隐患排查系统—工地隐患闭环管理
    Ubuntu无法引导启动的修复
    Java项目:茶叶商城管理系统(java+SSM+JSP+Ajax+jQuery+Mysql)
    2022 极术通讯-2021中国云数据中心考察报告发布，Arm服务器促进多元算力发展
    javascript输出数据在控制台中console的常用方法（上）
    OpenNebula的配置与应用（一）
    请体验一下falcon 180b 大语言模型的感觉
    【打卡】牛客网：BM36 判断是不是平衡二叉树
    Java的IO流-转换流
  • 原文地址：https://blog.csdn.net/m0_52048145/article/details/126277358