“华为杯”2025 年广东工业大学 ACM 程序设计竞赛题解

[TOC]

A - 出勤规划

出题人题解

对于完全图最小生成树，我们考虑Boruvka算法。

（下文将原图称为 ，求生成树的图称为 ）

考虑每一轮如何求出 中每个连通块到其它连通块的最短路，此时，问题变成了洛谷P5304旅行者，这里简要描述下这题做法：

跑Dijkstra计算 上每个点到所有 中连通块对应的 上点集中最短的最短距离和对应哪个连通块，对于点 分别记为 和 。那么，对于一条边 ，若 则用 更新连通块 和 的最短距离。

但是，这题的做法的复杂度是 的，执行 次的总复杂度是 的，难以通过此题。

于是我们考虑一个优化：

其实我们并不需要跑 轮Dijkstra，我们只需要跑一次计算出每个 上点到所有 上点对应的 上点最短的最短距离和对应哪个 上点，那么，每一轮可以直接通过这些信息计算出对应的是哪个连通块，于是我们将复杂度降至 ，可以通过此题。

验题人题解

假设有一个超级源点，连到每一个目标点上，距离是，然后用这个点去跑最短路，这样就能得到每个非目标点最近的目标点和距离；

然后先考虑两种颜色相邻，必然是所有接触的边加上两颜色的最短距离最短，枚举所有接触的边就能取到最短的；

然后两颜色不可能跨一个颜色相连，因为如果一个颜色还没被连上，它必然直接与相邻的颜色连是更优的，所以不可能跨一个颜色。

所以答案就能从这些边里面找到，跑个最小生成树即可。

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define ll long long
#define all(v) v.begin(),v.end()
#define sz(v) ((ll)v.size())
#define V vector
#define vi V<int>
#define vll V<ll>
#define eb emplace_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define A array
#define pb push_back
#define mset multiset
#define gpumap __gnu_pbds::gp_hash_table
#define ccumap __gnu_pbds::cc_hash_table
#define ui unsigned int
#define ull unsigned ll
#define cerr if (test) cerr
#define freopen if (test) freopen
#define whtest if (test)
using namespace std;

constexpr int test = 0;

namespace jhsy {
	struct DSU {
		int cnt; vi fa;
		DSU(int n):cnt(n),fa(n) {
			iota(all(fa),0);
		}
		int isroot(int x) {
			return x == fa[x];
		}
		int find(int x) {
			return isroot(x) ? x : fa[x] = find(fa[x]);
		}
		auto merge(int x,int y) {
			x = find(x); y = find(y);
			if (x == y) {
				return 0;
			}
			cnt--;
			fa[y] = x;
			return 1;
		}
	};
	void main() {
		int n,m,k;
		cin >> n >> m >> k;
		V<V<pll>> e(n); V<A<ll,3>> g(m);
		for (auto &[u,v,w]:g) {
			cin >> u >> v >> w; u--; v--;
			e[u].eb(v,w); e[v].eb(u,w);
		}
		vi a(k);
		const ll inf = 1e18;
		vll dis(n,inf),col(n,-1);
		priority_queue<pll,V<pll>,greater<>> q;
		for (int i = 0; i < k; i++) {
			cin >> a[i]; a[i]--;
			dis[a[i]] = 0; col[a[i]] = i;
			q.emplace(dis[a[i]],a[i]);
		}
		while (!q.empty()) {
			auto [d,u] = q.top(); q.pop();
			if (d == dis[u]) {
				for (auto [v,w]:e[u]) {
					if (dis[v] > d+w) {
						dis[v] = d+w; col[v] = col[u];
						q.emplace(dis[v],v);
					}
				}
			}
		}
		for (auto &[u,v,w]:g) {
			w += dis[u]+dis[v];
			u = col[u]; v = col[v];
			if (u > v) {
				swap(u,v);
			}
		}
		DSU dsu(k); ll ans = 0;
		while (dsu.cnt > 1) {
			{
				V<A<ll,3>> t; t.reserve(sz(g));
				for (auto [u,v,w]:g) {
					u = dsu.find(u); v = dsu.find(v);
					if (u != v) {
						t.pb({u,v,w});
					}
				}
				g = std::move(t);
			}
			V<pll> mn(k,{inf,-1});
			for (const auto &[u,v,w]:g) {
				if (u != v) {
					auto chkmn = []<class T>(T &a,const T &b) {
						if (a > b) {
							a = b;
						}
					};
					chkmn(mn[u],{w,v});
					chkmn(mn[v],{w,u});
				}
			}
			for (int i = 0; i < k; i++) {
				if (mn[i].se != -1 && dsu.merge(i,mn[i].se)) {
					ans += mn[i].fi;
				}
			}
		}
		cout << ans << '\n';
	}
}

int main() {
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(20);

//	jhsy::init();

	int T = 1;
	cin >> T;
	while (T--) {
		jhsy::main();
	}

	return 0;
}

B - 二分炼狱

出题人题解

考虑对于第 个数字，每个数字只有比他大/跟他一样大/比他小三种可能，我们先假设数字之间两两不同，此时我们可以把这个数组变成一个 串；

于是我们的任务就是：找到这个 串的后缀 中的最长 子序列；

这个事情我们可以写一个 的 ，于是题目变成了求 串的区间最长 子序列带修版，我们可以直接拿一个线段树维护这个 。

为了让带修次数尽量少，我们可以对所有下标按照值排序，这样每次只需要把一个 变成 。

那么现在还剩下一个问题：数字之间是可能相等的，我们只需要按照数字归类，对于同类数字先将其的贡献移除，计算后再加上即可。具体的实现细节可以看代码。

验题人题解

考虑模拟：对于每个数字，显然我们会在第一个比它大/小的地方计算贡献，于是我们可以考虑拿两个 set 来分别维护数字的“需求”。

然后从左往右扫过去。当第 个数字 加进去时，我们先对两个 set 里的所有下标计算贡献并进行转移，然后再将这个数字插入“需要比它大的数字”的 set 中。

显然这个复杂度还不如直接暴力！但在模拟的过程中，我们可以注意到一个事情：所有比 小的数字，如果不在它的右边，那么在进行转移后一定在“需要比它小的数字”的 set 中；同理，所有比 大的数字，如果不在它的右边，那么在进行转移后一定在“需要比它大的数字”的 set 中。在此基础上，我们可以发现，每次转移在值域里一定是一段区间，如果忽略掉下标位置的问题，那么只需要一个支持区间加单点查的数据结构就可以完成贡献的计算。

那么，下标位置的问题呢？有些数字可能在它的右边，此时它的贡献不能被算进去！但幸运的是，这个贡献在时间上是可差分的！我们只要在扫到这个数字的时候减掉这部分未加入时的贡献即可。实现上的细节可以看代码。

这一份是出题人的std，后面还有验题人的代码。

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define sz(vec) ((ll)vec.size())
#define all(vec) vec.begin(),vec.end()
#define umap __gnu_pbds::gp_hash_table
using ll = long long;
using db = double;
#define Emu Smile
using namespace std;

void chmax(auto &a, auto b) { if (a < b) a = b; }
void chmin(auto &a, auto b) { if (a > b) a = b; }
inline int lbt(int x) { return x & (-x); }

const int P = 998244353;

inline int lowbit(int x) {
	return x & -x;
}

void no() {
	cout << "NO\n";
}

void yes() {
	cout << "YES\n";
}

void wadd(auto &a, auto b) {
	a = (a + b) % P;
}

void wsub(auto &a, auto b) {
	a = (a + P - b) % P;
}

ll ksm(ll x,ll y) {
	ll ret = 1;
	while (y) {
		if (y & 1) ret = ret * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ret;
}
const ll inf = 1e16;

struct SegTree{
	struct Node{
		array<pair<ll,ll>,2> d;
		Node(ll x = 0, ll y = 0){
			if (x == -1) {
				d[0] = pair(0, 0);
				d[1] = pair(0, 1);
			} else {
				d[x] = pair(y, !x);
				d[!x] = pair(0, !x);
			}
		}
		Node friend operator + (const Node &ld, const Node &rd) {
			Node ret;
			for (int i = 0; i < 2; ++i) {
				auto [lsum, lnxt] = ld.d[i];
				auto [rsum, rnxt] = rd.d[lnxt];
				ret.d[i] = pair(lsum + rsum, rnxt);
			}
			return ret;
		}
	};
	vector<Node> nd; int n;
#define ls (p << 1)
#define rs (ls | 1)
	SegTree(const vector<ll> &vec):nd(sz(vec)*4),n(sz(vec)){
		auto build = [&](auto &self,int l,int r,int p) -> void {
			if (r - l == 1) { nd[p] = Node( 1, vec[l]); return; }
			int mid = l + ((r-l) >> 1);
			self(self, l, mid, ls), self(self, mid, r, rs);
			nd[p] = nd[ls] + nd[rs];
		};
		build(build, 0, n, 1);
	}
	void update(int l,int r,int pos,int p,ll x,ll y) {
		if (r - l == 1) { nd[p] = Node(x, y); return; }
		int mid = l + ((r-l) >> 1);
		if (pos < mid) update(l, mid, pos, ls, x, y);
		else update(mid, r, pos, rs, x, y);
		nd[p] = nd[ls] + nd[rs];
	}
	Node query(int l,int r,int xl,int xr,int p) {
		if (xl <= l && r <= xr) { return nd[p]; }
		int mid = l + ((r-l) >> 1);
		if (xr <= mid) return query(l, mid, xl, xr, ls);
		else if (mid <= xl) return query(mid, r, xl, xr, rs);
		else return query(l, mid, xl, xr, ls) + query(mid, r, xl, xr, rs);
	}
	void update(int pos,ll x,ll y){
		update(0, n, pos, 1, x, y);
	}
	ll query(int xl,int xr) {
		return query(0, n, xl, xr, 1).d[1].first;
	}
#undef ls
#undef rs
};

void solve() {
	int n; cin >> n;
	vector<ll> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	SegTree stree(a);
	map<ll,vector<ll>> mp;
	for (int i = 0; i < n; ++i) {
		mp[a[i]].emplace_back(i);
	}
	vector<ll> ret(n);
	for (const auto &[key, vec] : mp) {
		for (auto x : vec) {
			stree.update(x, -1, a[x]);
		}
		for (auto x : vec) {
			ret[x] = stree.query(x, n);
		}
		for (auto x : vec) {
			stree.update(x, 0, a[x]);
		}
	}
	for (auto x : ret) {
		cout << x << " ";
	}
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);

//	init();

	cout << fixed << setprecision(10);

	int OuO = 1;
//	cin >> OuO;
	for (int piastic = 0; piastic < OuO; ++piastic) {
		solve();
	}
	return 0;
}

验题人的代码：

#include <bits/stdc++.h>

#define lmf signed main()
#define lmf_up std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);
void solve()
{
    int n;
    std::cin >> n;
    std::vector<int> a(n + 1), pre(n + 1), vv(n + 1);
    std::vector<std::array<int, 2>> b(n + 1);
    std::vector<long long> sum(n + 1);
    std::function<void(int, int, long long)> add = [&](int l, int r, long long ad)
    {
        while (l <= n)
            sum[l] += ad, l += l & -l;
        r++;
        while (r <= n)
            sum[r] -= ad, r += r & -r;
    };
    std::function<long long(int)> getsum = [&](int x)
    {
        long long res = 0;
        while (x > 0)
            res += sum[x], x -= x & -x;
        return res;
    };
    for (int i = 1; i <= n; i++)
    {
        std::cin >> a[i];
        b[i] = {a[i], i};
    }
    std::sort(b.begin() + 1, b.end());
    for (int i = 1; i <= n; i++)
    {
        vv[b[i][1]] = i;
        if (b[i][0] == b[i - 1][0])pre[i] = pre[i - 1];
        else pre[i] = i;
    }
    int itl=vv[1],itr=vv[1];
    for (int i = 2; i <= n; i++)
    {
        long long det = getsum(vv[i]);
        add(vv[i], vv[i], -det);
        if(a[i]==a[i-1])
            itr++;
        else if(a[i]>a[i-1])
        {
            add(itl,pre[vv[i]]-1,a[i]);
            itl=pre[vv[i]],itr=vv[i];
        }
        else
        {
            add(vv[i]+1,itl-1,a[i]);
            itl=itr=vv[i];
        }
    }
    std::vector<long long>ans(n+1);
    for (int i = 1; i <= n; i++)
        ans[i]=getsum(vv[i]);
    for(int i=1;i<=n;i++)
        std::cout<<ans[i]<<' ';
    std::cout<<std::endl;

}
/*
6
1 1 4 5 1 4
 */
lmf
{
    lmf_up
    int T = 1;
//    std::cin >> T;
    while (T--)solve();
    return 0;
}

C - bloomsTD 6

考虑按时间顺序进行模拟。每次循环我们遍历每个气球，二分查找该气球还需走多少秒后会被击破，然后找出时间最近和最远的气球，并更新时间到气球被击破的时刻，然后根据两点得到这次攻击的轨迹，然后再遍历每一个存活的气球，判断是否击破。

这个模拟需要预处理对于线段 ，计算气球从 时刻进入时，在什么时候会被回旋镖索敌半径覆盖，这部分可以通过求直线与圆的交点，并判断交点是否在线段上来实现，其余的诸如计算气球存活 秒时的位置等也可以通过预处理+二分来实现。

#include<bits/stdc++.h>

#define cp const point &
#define cl const line &
#define cc const circle &
#define LD long double
std::mt19937 rnd(time(0));
const LD eps = 1e-12;
const LD pi = acos(-1);
const LD INF = 1e9;

int sgn(LD x)
{
    return x > eps ? 1 : (x < -eps ? -1 : 0);
}

LD sqr(LD x)
{ return x * x; }

struct point
{
    LD x, y;
    point(){}
    point (LD xx,LD yy){x=xx,y=yy;}
    point operator+(cp a) const
    { return {x + a.x, y + a.y}; }

    point operator-(cp a) const
    { return {x - a.x, y - a.y}; }

    point operator*(LD t) const
    { return {x * t, y * t}; }

    point operator/(LD t) const
    { return {x / t, y / t}; }

    point rot(LD t) const
    { return {(LD) (x * cos(t) - y * sin(t)), (LD) (x * sin(t) + y * cos(t))}; }

    point rot90() const
    { return {-y, x}; }

    point rot270() const
    {return point(y,-x);}

    LD len2() const
    { return x * x + y * y; }

    LD len() const
    { return sqrtl(x * x + y * y); }

    point unit() const
    {
        LD d = len();
        return {(LD) (x / d), (LD) (y / d)};
    }

    int on_up()//b不判（0,0）
    {
        return sgn(y) == 1 || (sgn(y) == 0 && sgn(x) <0);
    }

    void print()
    {
        std::cout << x << ' ' << y << std::endl;
    }

    void read()
    {
        int xx, yy;
        std::cin >> xx >> yy;
        x = xx, y = yy;
    }

    friend bool operator<(cp a, cp b)
    {
        return a.x == b.x ? a.y < b.y : a.x < b.x;
    }

    friend bool operator>(cp a, cp b)
    {
        return a.x == b.x ? a.y > b.y : a.x > b.x;
    }
};

LD dot(cp a, cp b);

bool operator==(cp a, cp b)
{
    return !sgn(dot(a - b, a - b));
//    return !sgn(a.x-b.x)&&!sgn(a.y-b.y); //看题目有无给出确定两实数相等的eps
}

LD dis(cp a, cp b)//两点距离
{
    return sqrtl(sqr(a.x - b.x) + sqr(a.y - b.y));
}

LD dot(cp a, cp b)//点乘
{
    return a.x * b.x + a.y * b.y;
}

LD det(cp a, cp b)//叉乘
{
    return a.x * b.y - b.x * a.y;
}
bool  turn_left_strict(cp a,cp b,cp c)
{
    return sgn(det(b-a,c-a))>0;
}
bool turn_left(cp a, cp b, cp c)
{
    return sgn(det(b - a, c - a)) >=0;
}

struct line
{
    point s, t;

    line()
    {}

    line(point a, point b) : s(a), t(b)
    {}

    void read()
    {
        s.read(), t.read();
    }

    void print()
    {
        s.print(), std::cout << ' ', t.print();
    }

};

struct circle
{
    point c;
    LD r;

    circle()
    {}

    circle(point C, LD R)
    { c = C, r = R; }
    bool on_circle(point a)
    {
        if(sgn((c-a).len2()-r*r)==0)
           return 1;
        else return 0;
    }
};

bool in_circle(cp a, cc b)
{
    return sgn((b.c - a).len() - b.r) <= 0;
}

circle make_circle(point u, point v)
{
    point p = (u + v) / 2;
    return circle(p, (u - p).len());
}

bool point_on_line(cp a, cl l)//判断点是否在直线上
{
    return sgn(det(a - l.s, l.t - l.s)) == 0;
}
bool point_on_segment(cp a, cl l)//判断点是否在线段上
{
    return point_on_line(a, l) && sgn(dot(l.s - a, l.t - a)) <= 0;//(<=代表可以端点
}
bool point_on_ray(cp a, cl b)
{//判断点是否在射线上
    return sgn(det(a - b.s, b.t - b.s)) == 0 && sgn(dot(a - b.s, b.t - b.s)) >= 0;
}
point project_to_line(cp a, cl b)
{//得到点在线上的投影
    return b.s + (b.t - b.s) * (dot(a - b.s, b.t - b.s) / (b.t - b.s).len2());
}
LD point_to_line(cp a, cl b)
{//点到直线的距离
    return abs(det(b.t - b.s, a - b.s)) / dis(b.s, b.t);

}
LD point_to_segment(cp a, cl b)
{//点到线段的距离
    if (b.s == b.t)
        return dis(a, b.s);
    if (sgn(dot(b.s - a, b.t - b.s)) * sgn(dot(b.t - a, b.t - b.s)) <= 0)
        return abs(det(b.t - b.s, a - b.s)) / dis(b.s, b.t);
    return std::min(dis(a, b.s), dis(a, b.t));

}
std::vector<point> line_circle_intersect(cl a, cc b)//线与圆的交点
{//返回线与圆的交点
    if (sgn(point_to_segment(b.c, a) - b.r) > 0)
        return std::vector<point>();
    LD x = sqrtl(sqr(b.r) - sqr(point_to_line(b.c, a)));
    return std::vector<point>(
            {project_to_line(b.c, a) + (a.s - a.t).unit() * x, project_to_line(b.c, a) - (a.s - a.t).unit() * x});
}
std::vector<std::pair<long double,point>> lane;
std::vector<int>blooms_time;
int gap;
long double now_time;
int m,n;
circle ta;
std::vector<std::array<long double,2>> lane_time_to_attack;
point get_point_time(long double t)
{
    int l=0,r=lane.size()-1;
    while(l<=r)
    {
        int mid=(l+r+1)>>1;
        if(sgn(lane[mid].first-t)<=0)
            l=mid+1;
        else r=mid-1;
    }
    point p=lane[r].second;
    t-=lane[r].first;
    if(sgn(t)==0)
        return p;
    else
        return p+(lane[r+1].second-lane[r].second).unit()*t;
}
void init_lane_time_to_attack()
{
    for(int i=1;i<lane.size();i++)
    {
        line li(lane[i-1].second,lane[i].second);
        auto intersect= line_circle_intersect(li,ta);
        if(intersect.empty())
            continue;
        std::vector<long double>temp_time;
        for(auto x:intersect)
            if(sgn(dot(x-lane[i-1].second,lane[i].second-lane[i-1].second))<0)
                temp_time.push_back(lane[i-1].first-(x-lane[i-1].second).len());
            else
                temp_time.push_back(lane[i-1].first+(x-lane[i-1].second).len());
            if(temp_time[0]>temp_time[1])
                std::swap(temp_time[0],temp_time[1]);
        long double l_time=std::max(lane[i-1].first,temp_time[0]);
        long double r_time=std::min(lane[i].first,temp_time[1]);
        if(sgn(l_time-r_time)<=0)
            lane_time_to_attack.push_back({l_time,r_time});
    }
}
circle get_next_station()
{
    long double det_time=1e18;
    int id=-1;
    circle c;
    for(int i=0;i<m;i++)
    {
        if(blooms_time[i]==-1)
            continue;
        if(sgn(blooms_time[i]-now_time)>0)
        {
            long double temp_time=lane_time_to_attack[0][0]+(blooms_time[i]-now_time);
            if(sgn(temp_time-det_time)<0)
            {
                det_time=temp_time;
                id=i;
            }
            break;
        }
        long double det=now_time-blooms_time[i];
        if(sgn(det-lane.back().first)>0)
            return circle(point(i+1,0),-1);
        int l=0,r=lane_time_to_attack.size()-1;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(sgn(lane_time_to_attack[mid][0]-det)>0)
                r=mid-1;
            else l=mid+1;
        }
        if(l==0)
        {
            long double temp_time=lane_time_to_attack[0][0]-det;
            if(sgn(temp_time-det_time)<0)
            {
                det_time=temp_time;
                id=i;
            }
        }

        else
        {
            if(sgn(det-lane_time_to_attack[l-1][1])<=0)
            {
                auto p= get_point_time(det);
                auto mid=p+(ta.c-p)/2;
                long double len=sqrtl(sqr(ta.r)-(ta.c-p).len2())/2;
                c.c=mid+(p-ta.c).rot90().unit()*len;
                c.r=ta.r/2;
                return c;
            }
            else if(l==lane_time_to_attack.size())
                return circle(point(i+1,0),-1);
            else
            {
                long double temp_time=lane_time_to_attack[l][0]-det;
                if(sgn(temp_time-det_time)<0)
                {
                    det_time=temp_time;
                    id=i;
                }
            }
        }
    }
    now_time+=det_time;
    auto p= get_point_time(now_time-blooms_time[id]);
    auto mid=p+(ta.c-p)/2;
    long double len=sqrtl(sqr(ta.r)-(ta.c-p).len2())/2;
    c.c=mid+(p-ta.c).rot90().unit()*len;
    c.r=ta.r/2;
    return c;
}
int main()
{
    std::cout<<std::fixed<<std::setprecision(10);
    std::cin>>n;
    ta.c.read();
    std::cin>>ta.r;
    ta.r*=2;
    std::cin>>gap;
    for(int i=0;i<n;i++)
    {
        point p;
        p.read();
        if(lane.empty())
            lane.push_back({0,p});
        else
            lane.push_back({lane.back().first+(p-lane.back().second).len(),p});
    }
    init_lane_time_to_attack();
    if(lane_time_to_attack.empty())
    {
        std::cout<<"NO\n1"<<std::endl;
        return 0;
    }
//    for(auto [x,y]:lane_time_to_attack)
//        std::cout<<x<<' '<<y<<std::endl;
    std::cin>>m;
    blooms_time.resize(m);
    for(int i=0;i<m;i++)
        std::cin>>blooms_time[i];
    int size_blooms=m;
    while(1)
    {
        auto c=get_next_station();
//        std::cout<<now_time<<std::endl;
        if(c.r<0)
        {
            std::cout<<"No\n"<<(int)c.c.x<<std::endl;
            return 0;
        }
        for(int i=0;i<m;i++)
        {
            if(blooms_time[i]==-1)
                continue;
            if(sgn(blooms_time[i]-now_time)>0)
                break;
            if(c.on_circle(get_point_time(now_time-blooms_time[i])))
            {
                blooms_time[i]=-1;
                size_blooms--;
            }
        }
        if(size_blooms==0)
        {
            std::cout<<"Yes\n"<<now_time<<std::endl;
            return 0;
        }
        now_time+=gap;
    }
}

D - 橘猫的背包问题

考虑一棵线段树，每个节点记为 其中 ，表示这个节点代表了 的信息并且若 的话，其两个儿子分别代表了 和 的信息。线段树的根节点为。

对于所有长度大于1的线段树节点，记录长为的背包数组 ， 表示 的背包结果（对于 的情况可以由转移而来）。同理，记录长为 的背包数组 ， 表示 的背包结果，计算方式类似 。

考虑到对于长度大于1的询问区间 ，一定存在一个线段树节点 使得 且 ，所以答案可以由该节点的 和 合并而成。而长度为1的可以直接计算。

所以，我们以 的复杂度完成了本题。

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define ll long long
#define all(v) v.begin(),v.end()
#define sz(v) ((ll)v.size())
#define V vector
#define vi V<int>
#define vll V<ll>
#define eb emplace_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define A array
#define pb push_back
#define mset multiset
#define umap unordered_map
#define gpumap __gnu_pbds::gp_hash_table
#define ccumap __gnu_pbds::cc_hash_table
#define ui unsigned int
#define ull unsigned ll
#define whtest if (test)
#define cerr whtest cerr
#define freopen whtest freopen
#define debug(x) {cerr << #x << " = " << x << "\n";}
#define vdebug(a) whtest {cerr << #a << " = "; for(auto x: a) cerr << x << " "; cerr << "\n";}
using namespace std;

constexpr int test = 0;

namespace hhyy {
	template<class T>
	void chkmx(T &a,const T &b) {
		if (a < b) {
			a = b;
		}
	}
	constexpr int W = 1e4;
	struct Info {
		A<int,W+1> a{};
		Info friend operator + (Info x,const pii &k) {
			for (int i = W-k.fi; i >= 0; i--) {
				chkmx(x.a[i+k.fi],x.a[i]+k.se);
			}
			return x;
		}
	};
	template<class T>
	struct DCT {
#define ls (x<<1)
#define rs (ls|1)
		vi id; V<V<T>> s;
		DCT(int n,const auto &a):id(n) {
			auto build = [&](auto &&self,int x,int l,int r,int d) -> void {
				if (sz(s) == d) {
					s.eb(n);
				}
				if (r-l == 1) {
					id[l] = x;
					s[d][l] = Info()+a[l];
				}
				else {
					int mid = l+((r-l)>>1);
					self(self,ls,l,mid,d+1);
					self(self,rs,mid,r,d+1);
					s[d][mid-1] = Info()+a[mid-1];
					for (int i = mid-2; i >= l; i--) {
						s[d][i] = s[d][i+1]+a[i];
					}
					s[d][mid] = Info()+a[mid];
					for (int i = mid+1; i < r; i++) {
						s[d][i] = s[d][i-1]+a[i];
					}
				}
			};
			build(build,1,0,n,0);
		}
		V<T> qry(int l,int r) {
			r--;
			if (l == r) {
				return {s[__lg(id[l])][l]};
			}
			int x = id[l],y = id[r];
			const int lg = min(__lg(x),__lg(y));
			x >>= __lg(x)-lg; y >>= __lg(y)-lg;
			int z = x>>(__lg(x^y)+1);
			return {s[__lg(z)][l],s[__lg(z)][r]};
		}
	};
	void main() {
		int n;
		cin >> n;
		V<pii> p(n);
		for (auto &[x,y]:p) {
			cin >> x;
		}
		for (auto &[x,y]:p) {
			cin >> y;
		}
		DCT<Info> dct(n,p);
		int Q;
		cin >> Q;
		for (int ans = 0; Q--; ) {
			int l,r,k;
			cin >> l >> r >> k;
			l = (l+ans)%n+1;
			r = (r+ans)%n+1;
			k = (k+ans)%W+1;
			if (l > r) {
				swap(l,r);
			}
			l--;
			auto vec = dct.qry(l,r);
			if (sz(vec) == 1) {
				ans = vec[0].a[k];
			}
			else {
				ans = 0;
				for (int i = 0; i <= k; i++) {
					chkmx(ans,vec[0].a[i]+vec[1].a[k-i]);
				}
			}
			cout << ans << '\n';
		}
	}
}

int main() {
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(20);

//	hhyy::init();

	int T = 1;
//	cin >> T;
	while (T--) {
		hhyy::main();
	}

	return 0;
}

E - GDUT = 1

考虑一个暴力的做法：我们枚举 GDUT 分别是多少，然后代入求解得到答案，这样的复杂度是 （其中 为单个字母的范围），难以通过。

但如果我们把单个字母的贡献拉出来，就会发现它们是独立的，例如 GDUT+GDU 中 G 对和的贡献只和 G 的大小有关。并且显然地，单个字母的值为 时对和的贡献就是值为 对和的贡献乘上 ，所以我们可以扫一遍 得到单个字母值为 的贡献，然后再枚举大小。

走到这一步思路上已经没有问题了，但是实现时有两个细节需要注意：

  1. 字符串的长度很大，以至于在位数很高时你不能照旧将 直接加进答案里，此时因为 显然这个字母的值必须是 ，所以我们可以给它打一个标记然后跳过。

  2. 在此基础上，有可能贡献之和会被加到 以上，此时也应当立刻打标记跳过。

最终时间复杂度 ，可以通过。

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>

#define sz(vec) ((ll)vec.size())
#define all(vec) vec.begin(),vec.end()
#define umap __gnu_pbds::gp_hash_table
using ll = long long;
using ull = unsigned long long;
using db = double;
#define Emu Smile
using namespace std;

void chmax(auto &a, auto b) { if (a < b) a = b; }
void chmin(auto &a, auto b) { if (a > b) a = b; }
inline int lbt(int x) { return x & (-x); }
void no() { cout << "NO\n"; }
void yes() { cout << "YES\n"; }

const int P = 998244353, N = 18, B = 2;
void wadd(auto &a, auto b) {
	a = (a + b) % P;
}
void wsub(auto &a, auto b) {
	a = (a + P - b) % P;
}

ll ksm(ll x, ll y) {
	ll ret = 1;
	x %= P, y %= (P - 1);
	while (y) {
		if (y & 1) ret = ret * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ret;
}

array<ll, N + 1> fac, ifac, p10;
umap<char,int> mp;
void init(const int n = N) {
	fac[0] = 1;
	for (int i = 0; i < n; ++i) {
		fac[i + 1] = fac[i] * (i + 1) % P;
	}
	ifac[n] = ksm(fac[n], P - 2);
	for (int i = n - 1; i >= 0; --i) {
		ifac[i] = ifac[i + 1] * (i + 1) % P;
	}
	mp['G'] = 0, mp['D'] = 1, mp['U'] = 2, mp['T'] = 3;
	p10[0] = 1;
	for (int i = 0; i < N; ++i) {
		p10[i + 1] = p10[i] * 10;
	}
}
ll C(int n, int m) {
	return fac[n] * ifac[m] % P * ifac[n - m] % P;
}

const ll inf = 2e18;

void solve() {
	string s; ll x; cin >> s >> x;
	array<vector<ll>, 4> cnt{};
	ll lst = sz(s) - 1;
	for (int i = sz(s)-1; i >= 0; --i) {
		if (s[i] == '+') {
			lst = i - 1;
		} else {
			cnt[mp[s[i]]].emplace_back(lst - i);
		}
	}
	array<ll, 4> sum{}, maxd{}, ret{};
	for (int i = 0; i < 4; ++i) {
		for (auto j : cnt[i]) {
//			cout << j << " ";
			if (j > 18) {
				sum[i] = -1; break;
			} else {
				sum[i] += p10[j];
				if (sum[i] > 1e18) {
					sum[i] = -1; break;
				}
			}
		}
		maxd[i] = 10;
//		cout << sum[i] << "\n";
	}
	for (int i1 = 0; i1 < maxd[0]; ++i1) {
		for (int i2 = 0; i2 < maxd[1]; ++i2) {
			for (int i3 = 0; i3 < maxd[2]; ++i3) {
				for (int i4 = 0; i4 < maxd[3]; ++i4) {
					ll y = 1ull * i1 * sum[0] + 1ull * i2 * sum[1] + 1ull * i3 * sum[2] + 1ull * i4 * sum[3];
					if (x == y) {
						ret = {i1, i2, i3, i4};
						yes();
						cout << ret[0] << " " << ret[1] << " " << ret[2] << " " << ret[3] << '\n';
						return;
					}
				}
			}
		}
	}
	return no();
}


int main() {

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);

	init();

	cout << fixed << setprecision(10);

	int OuO = 1;
	cin >> OuO;
	for (int piastic = 0; piastic < OuO; ++piastic) {
		solve();
	}
	return 0;
}

F - 排队

注意到分界点分开后的两段实际上是独立的，我们可以先预处理出每个前后缀的耗费时间，然后枚举分界点暴力计算即可。

这一点与 H 差不多，但难点在于如何预处理前后缀，我们可以拿一个 set 来维护 capoo 的理发时间段，要注意对区间进行合并。这里以前缀为例，每次加入一只 capoo 时，先找到轮到它的时间点，然后再插入，并对后续区间对应平移。

每只 capoo 加入最多新增一段，且每一段最多被合并一次，故复杂度为 。

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define sz(vec) ((ll)vec.size())
#define all(vec) vec.begin(),vec.end()
#define umap __gnu_pbds::gp_hash_table
using ll = long long;
using ull = unsigned long long;
using db = double;
#define Emu Smile
using namespace std;

void chmax(auto &a, auto b) { if (a < b) a = b; }
void chmin(auto &a, auto b) { if (a > b) a = b; }
inline int lbt(int x) { return x & (-x); }

const int P = 998244353;

inline int lowbit(int x) {
	return x & -x;
}

void no() { cout << "NO\n"; }
void yes() { cout << "YES\n"; }

void wadd(auto &a, auto b) {
	a = (a + b) % P;
}

void wsub(auto &a, auto b) {
	a = (a + P - b) % P;
}

ll ksm(ll x,ll y) {
	ll ret = 1;
	while (y) {
		if (y & 1) ret = ret * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ret;
}
const ull inf = 1e19;

void solve() {

	int n; ll K; cin >> n >> K;

	auto get = [&](const vector<ll> &a) {
		vector<ull> pre(n+1);
		set<pair<ll,ll>> s;
		for (int i = 0; i < n; ++i) {
			pair<ll,ll> t = pair(a[i], a[i]+K);
			pre[i+1] = pre[i];
			while (true) {
				auto lt = s.upper_bound(t);
				if (lt != s.begin()) {
					lt = prev(lt);
					if (lt -> second >= t.first) {
						ll peo = ((t.second) - (t.first)) / K;
						pre[i+1] += ((lt -> second) - t.first) * peo;
						t = pair(lt -> first, lt -> second + K);
						s.erase(lt);
					} else {
						break;
					}
				} else {
					break;
				}
			}
			while (true) {
				auto rt = s.upper_bound(t);
				if (rt != s.end()) {
					if (t.second >= rt -> first) {
						ll peo = ((rt -> second) - (rt -> first)) / K;
						pre[i+1] += (t.second - (rt -> first)) * peo;
						t = pair(t.first, t.second + peo * K);
						s.erase(rt);
					} else {
						break;
					}
				} else {
					break;
				}
			}
			s.emplace(t);
		}
		return pre;
	};

	vector<ll> a(n);
	for (auto &x : a) {
		cin >> x;
	}
	auto pre = get(a);
	reverse(all(a));
	auto suf = get(a);
	reverse(all(suf));
	ull ret = inf;
	for (int i = 0; i <= n; ++i) {
		chmin(ret, pre[i] + suf[i]);
	}
	cout << ret << '\n';
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);

//	init();

	cout << fixed << setprecision(10);

	int OuO = 1;
	cin >> OuO;
	for (int piastic = 0; piastic < OuO; ++piastic) {
		solve();
	}
	return 0;
}

G - Jump Sort

首先，当 时，我们可以将这个排列按照模 的值来划分为 个组，每组之间可以自由排序——显然，每一组都应该升序。对每组排完序之后我们检查下此时是否升序即可。

然而，我们并不能对每个数字都进行这样的检查，因为对单个数字进行检查复杂度是 的。但我们可以把排序这个事情换个角度看：我们希望每个数字都回到正确的位置上，而数字的值表示了它应当在的位置，对于这一对而言，数字能够来到它应在的位置当且仅当 。对于每一对而言，我们都应当满足这个条件，于是我们发现一个合法的 应当是所有的差的公因数！为此，我们可以先跑出最大公因数，然后枚举因数个数即可解决本题。

这里需要注意一个细节：如果每个数字都已经回到了自己的位置上，则答案为 ，而不是 。

复杂度 或 （视实现而定）。

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>

#define sz(vec) ((ll)vec.size())
#define all(vec) vec.begin(),vec.end()
#define umap __gnu_pbds::gp_hash_table
using ll = long long;
using ull = unsigned long long;
using db = double;
#define Emu Smile
using namespace std;

const ll inf = 2e18;

void solve() {
	int n; cin >> n;
	vector<ll> a(n); ll g = 0;
	for (int i = 0; i < n; ++i) {
		cin >> a[i]; a[i] --;
		g = gcd(g, abs(a[i] - i));
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		if (g % i == 0) {
			ans ++;
		}
	}
	std::cout << ans << '\n';
}


int main() {

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);

// 	init();

	cout << fixed << setprecision(10);

	int OuO = 1;
//	cin >> OuO;
	for (int piastic = 0; piastic < OuO; ++piastic) {
		solve();
	}
	return 0;
}

H - 可爱串串

可以先预处理出每个前后缀的可爱值，然后枚举分界点暴力计算即可。

注意 会爆 int，需要开 long long。复杂度 

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>

#define sz(vec) ((ll)vec.size())
#define all(vec) vec.begin(),vec.end()
#define umap __gnu_pbds::gp_hash_table
using ll = long long;
using ull = unsigned long long;
using db = double;
#define Emu Smile
using namespace std;

void chmax(auto &a, auto b) { if (a < b) a = b; }
void chmin(auto &a, auto b) { if (a > b) a = b; }

const ll inf = 2e18;

void solve() {
	int n; std::cin >> n;
	std::string s; std::cin >> s;
	std::vector<ll> pre(n+1), suf(n+1);
	for (int i = 0; i < n; ++i) {
		pre[i+1] = pre[i] + (s[i] == '1' ? 1 : -1);
	}
	for (int i = n-1; i >= 0; --i) {
		suf[i] = suf[i+1] + (s[i] == '1' ? 1 : -1);
	}
	ll ans = -inf;
	for (int i = 1; i < n; ++i) {
		chmax(ans, pre[i] * suf[i]);
	}
	std::cout << ans << '\n';
}


int main() {

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

//	freopen("data/test.in","r",stdin);
//	freopen("data/test.out","w",stdout);

// 	init();

	cout << fixed << setprecision(10);

	int OuO = 1;
	cin >> OuO;
	for (int piastic = 0; piastic < OuO; ++piastic) {
		solve();
	}
	return 0;
}

I - 好想成为人类啊

首先解决找区间问题，这部分可以暴力匹配；然后解决覆盖问题，这部分我们可以贪心地从左往右扫过去然后尽量靠右取点来覆盖。

但实际上这两部分是可以一起做的，复杂度 或 （如果你使用 ）

#include <bits/stdc++.h>

int main() {

	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int T = 1; std::cin >> T;
	while (T--) {
		int n,m; std::cin >> n >> m;
		std::string s,t; std::cin >> s >> t;
		int ans = 0;
		for (int i = 0; i + m <= n; ++i) {
			int ok = 1;
			for (int j = 0; j < m; ++j) {
				if (s[i + j] != t[j]) {
					ok = 0; break;
				}
			}
			if (ok) {
				i = i + m - 1;
				ans ++;
			}
		}
		std::cout << ans << '\n';
	}

	return 0;
}

J - 11背包

首先我们先进行一些定义：

合法状态为所有背包内的物品体积都不超过其容量的状态，不合法状态为存在至少一个背包内物品体积超过容量的状态；合法操作为操作后依然为合法状态的操作，不合法操作为操作后为不合法状态的操作。题目想要的就是求 的最小值，使得无论如何操作都是合法操作。

我们假设已经确定要准备 个背包，那么 是否合法取决于我们能不能找到一个方式来让所有背包都被塞爆。然后我们来找找性质。首先假定我们以某种顺序去放物品，那么操作序列一定是先有若干次合法操作，然后要么物品全放进去了，要么进入无法继续进行合法操作的局面（这里我们称为塞爆局面），那么这先有的若干次合法操作的顺序是可以任意调整的。

假设我们达到了塞爆局面，此时肯定至少有一个物品还没放进去，我们可以证明这里面一定可以有最大的物品：如果最大的物品已经被塞进去，那么对调后，对于被对调物品所在的那个背包，如果将现在的物品塞进去，那么这个背包要承受的物品重量未变，根据塞爆局面的定义，它依然不合法；而对于其他背包，如果将现在的物品塞进去，它们要承受的重量其实更大了，显然也不合法，所以依然是塞爆局面。

那么我们就可以先把这个最大的物品拿走，然后让剩下的物品去努力填满 个大小为 的背包。

还记得刚才说的“合法操作的顺序是可以任意调整的”吗？根据这个定理，我们可以一个背包一个背包地塞，据此我们可以跑一个 的状压 ，枚举物品的放入状态，然后转移塞满了多少背包/没有塞满的背包塞了多少。实现上相对比较简单。

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>

#define sz(vec) ((ll)vec.size())
#define all(vec) vec.begin(),vec.end()
#define umap __gnu_pbds::gp_hash_table
using ll = long long;
using ull = unsigned long long;
using db = double;
#define Emu Smile
using namespace std;

void chmax(auto &a, auto b) { if (a < b) a = b; }
void chmin(auto &a, auto b) { if (a > b) a = b; }

inline int lbt(int x) { return x & (-x); }

void no() { cout << "NO\n"; }

void yes() { cout << "YES\n"; }

const int P = 1e9+7, N = 1e6;

void wadd(auto &a, auto b) {
	a = (a + b) % P;
}

void wsub(auto &a, auto b) {
	a = (a + P - b) % P;
}

const ll inf = 2e18;

void solve() {
	int n, m; cin >> n >> m;
	vector<ll> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	if (n == 1) {
		std::cout << 1 << '\n';
		return;
	}
	sort(all(a));
	int maxa = a.back(); a.pop_back();
	n = sz(a);
	std::vector<std::pair<ll,ll>> f(1 << n, std::pair(1, 0));
	for (int i = 0; i < (1 << n); ++i) {
		for (int j = 0; j < n; ++j) {
			if ((i & (1 << j))) continue;
			auto [cnt, has] = f[i];
			has += a[j];
			if (has + maxa > m) {
				has = 0; cnt ++;
			}
			chmax(f[(i | (1 << j))], std::pair(cnt, has));
		}
	}
	std::cout << f[(1 << n) - 1].first << '\n';
}


int main() {

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);

// 	init();

	cout << fixed << setprecision(10);

	int OuO = 1;
	cin >> OuO;
	for (int piastic = 0; piastic < OuO; ++piastic) {
		solve();
	}
	return 0;
}

K - 橘猫的后缀问题

本题保证数据随机，于是考虑一些乱搞。

注意到，假设我们只比较前L位，那么对于询问的后缀 ，前L位与其相同的后缀数量的期望是 。于是我们考虑将每个后缀的权值转化转化为一个 位 进制数（若该后缀长度不足 位则在末尾补上 ，AZ 对应 126），每次询问时只需求出权值更小的数量并将权值相同的后缀拿出来，通过暴力比较算出权值相同的后缀有多少个小于询问后缀（由于保证数据随机，不会太长）。

修改 时，只有 的后缀 的权值会比较，因此，只会修改 个。

考虑用线段树维护权值在某个范围内的后缀数量，每次查询的复杂度是 每次修改的复杂度是 ，取 跑得飞快！取 有点压力但也能过。

#include <bits/stdc++.h>

#ifdef LOCAL_DEBUG
#include "debug.h"
#else
#define dbg(...) (void)0
#endif
using u32 = unsigned int;
using i64 = long long;

namespace skadi {

constexpr int L = 3;

i64 pw(i64 x, i64 y) {
    i64 res = 1;
    while (y) {
        if (y & 1) res = res * x;
        x = x * x;
        y >>= 1;
    }
    return res;
}

void solve() {
    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;

    for (auto& c : s) {
        c = c - 'a' + 1;
    }
    s += std::string(L, 0);

    auto sv = std::string_view(s);

    std::vector<int> bit(pw(27, L) + 1);

    auto add = [&](int x, int v) {
        for (x++; x < bit.size(); x += x & -x) {
            bit[x] += v;
        }
    };

    auto query = [&](int x) {
        int res = 0;
        for (x++; x > 0; x -= x & -x) {
            res += bit[x];
        }
        return res;
    };

    std::vector<std::vector<int>> mp(pw(27, L) + 1);

    auto encode = [&](std::string_view sv) -> i64 {
        i64 res = 0;
        for (char c : sv) {
            res = res * 27 + c;
        }
        return res;
    };

    auto cmp = [&](int a, int b) {
        if (a == b) return false;
        return sv.substr(a + L) < sv.substr(b + L);
    };

    auto remove = [&](int idx) {
        int enc = encode(sv.substr(idx, L));
        auto& v = mp[enc];
        v.erase(std::remove(v.begin(), v.end(), idx), v.end());
        add(enc + 1, -1);
    };

    auto insert = [&](int idx) {
        int enc = encode(sv.substr(idx, L));
        auto& v = mp[enc];
        v.push_back(idx);
        add(enc + 1, 1);
    };

    auto rank = [&](int idx) -> i64 {
        int enc = encode(sv.substr(idx, L));
        auto& v = mp[enc];
        std::sort(v.begin(), v.end(), cmp);
        return query(enc) + std::find(v.begin(), v.end(), idx) - v.begin();
    };

    for (int i = 0; i < n; i++) {
        insert(i);
    }

    int q, op, pos;
    std::cin >> q;
    while (q--) {
        std::cin >> op >> pos;
        pos--;
        if (op == 1) {
            char c;
            std::cin >> c;
            for (int i = 0; i < L; i++) {
                if (pos - i < 0) break;
                remove(pos - i);
            }
            s[pos] = c - 'a' + 1;
            for (int i = 0; i < L; i++) {
                if (pos - i < 0) break;
                insert(pos - i);
            }
        } else {
            std::cout << rank(pos) + 1 << '\n';
        }
    }
}

} // namespace skadi

int main() {
#ifndef LOCAL_DEBUG
    std::cin.tie(nullptr)->sync_with_stdio(false);
#endif
    int t = 1;
    // std::cin >> t;
    while (t--) {
        skadi::solve();
    }
    return 0;
}

L - 字符串匹配太多了！

构造题。可以发现，如果存在解 ，则一定存在长度为 的解 。证明如下：

对于一个合法的字符串 ，字符串 和字符串 应当对于每一个后缀，它们和 前缀的匹配位数一样多，显然至少它们每一位上的字母和 前缀的第一个字母要么都匹配上，要么都匹配不上，那么据此我们就可以得到 的第一个字母，而可以发现，这个字母就是一个合法的解。

据此，我们可以直接验证 a、b、c 是否是合法的解，如果都不是就直接退出。时间复杂度 。

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>

#define sz(vec) ((ll)vec.size())
#define all(vec) vec.begin(),vec.end()
#define umap __gnu_pbds::gp_hash_table
using ll = long long;
using ull = unsigned long long;
using db = double;
#define Emu Smile
using namespace std;

void chmax(auto &a, auto b) { if (a < b) a = b; }
void chmin(auto &a, auto b) { if (a > b) a = b; }

inline int lbt(int x) { return x & (-x); }

void no() { cout << "NO\n"; }

void yes() { cout << "YES\n"; }

const int P = 1e9+7, N = 1e6;

void wadd(auto &a, auto b) {
	a = (a + b) % P;
}

void wsub(auto &a, auto b) {
	a = (a + P - b) % P;
}

ll ksm(ll x, ll y) {
	ll ret = 1;
	x %= P;
	while (y) {
		if (y & 1) ret = ret * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ret;
}

array<ll, N + 1> fac, ifac;

void init(const int n = N) {
	fac[0] = 1;
	for (int i = 0; i < n; ++i) {
		fac[i + 1] = fac[i] * (i + 1) % P;
	}
	ifac[n] = ksm(fac[n], P - 2);
	for (int i = n - 1; i >= 0; --i) {
		ifac[i] = ifac[i + 1] * (i + 1) % P;
	}
}

ll C(int n, int m) {
	return fac[n] * ifac[m] % P * ifac[n - m] % P;
}

const ll inf = 2e18;

void solve() {
	int n; cin >> n;
	string s1, s2; cin >> s1 >> s2;
	for (int i = 0; i < 3; ++i) {
		char c = 'a' + i; int ok = 1;
		for (int j = 0; j < n; ++j) {
			int p1 = s1[j] == c, p2 = s2[j] == c;
			if (p1 != p2) {
				ok = 0; break;
			}
		}
		if (ok) {
			cout << "YES" << '\n';
			cout << 1 << "\n" << c << "\n";
			return;
		}
	}
	cout << "NO\n";
}


int main() {

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);

	init();

	cout << fixed << setprecision(10);

	int OuO = 1;
	cin >> OuO;
	for (int piastic = 0; piastic < OuO; ++piastic) {
		solve();
	}
	return 0;
}

M - 晚饭吃什么？

经典数数题。题目等价于给 个格子种的 个涂上 种色，要求相邻两个格子要么不同色，要么都没涂色。为方便表述，下面的“空格子”表示没有涂色的格子。

我们可以将所有格子按照空格子划分为若干个块，每一块中全是涂色的格子，那么这一块中所有相邻格子的颜色不能相同。设连通块大小为 ，则涂色方案数为 ；并且我们不必知道每个连通块的大小，只要知道有 个连通块，那么涂色方案数的乘积就是 ；

然后考虑每个块的组成，我们可以考虑为将 个格子用 个空格隔开，方案数

然后考虑塞空格。我们可以反过来考虑将这 个块放入 个空格子的间隙中，方案数为

全部乘起来即可。组合数和乘积都可以进行预处理，总复杂度为 。

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>

#define sz(vec) ((ll)vec.size())
#define all(vec) vec.begin(),vec.end()
#define umap __gnu_pbds::gp_hash_table
using ll = long long;
using ull = unsigned long long;
using db = double;
#define Emu Smile
using namespace std;

void chmax(auto &a, auto b) { if (a < b) a = b; }
void chmin(auto &a, auto b) { if (a > b) a = b; }
inline int lbt(int x) { return x & (-x); }
void no() { cout << "NO\n"; }
void yes() { cout << "YES\n"; }

const int P = 1e9+7, N = 1e6, B = 2;
void wadd(auto &a, auto b) {
	a = (a + b) % P;
}
void wsub(auto &a, auto b) {
	a = (a + P - b) % P;
}

ll ksm(ll x, ll y) {
	ll ret = 1;
	x %= P, y %= (P - 1);
	while (y) {
		if (y & 1) ret = ret * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ret;
}

array<ll, N + 1> fac, ifac, p25, p26;
void init(const int n = N) {
	fac[0] = 1;
	for (int i = 0; i < n; ++i) {
		fac[i + 1] = fac[i] * (i + 1) % P;
	}
	ifac[n] = ksm(fac[n], P - 2);
	for (int i = n - 1; i >= 0; --i) {
		ifac[i] = ifac[i + 1] * (i + 1) % P;
	}
}
ll C(int n, int m) {
	if (n < m) return 0ll;
	return fac[n] * ifac[m] % P * ifac[n - m] % P;
}

const ll inf = 2e18;

void solve() {
	int n,m,K; cin >> n >> m >> K;
	ll ret = 0;
	vector<ll> p0(n + 1), p1(n + 1);
	p0[0] = 1, p1[0] = 1;
	for (int i = 0; i < n; ++i) {
		p0[i + 1] = p0[i] * (m - 1) % P;
		p1[i + 1] = p1[i] * m % P;
	}
	for (int i = 1; i <= K; ++i) {
		// i, i-1 + 2
		// ksm(m, i) * ksm(m - 1, K - i)
		wadd(ret, C(K-1, i-1) * C(n-K+1, i) % P * p1[i] % P * p0[K - i] % P);
	}
	cout << ret << '\n';
}


int main() {

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);

	init();

	cout << fixed << setprecision(10);

	int OuO = 1;
	cin >> OuO;
	for (int piastic = 0; piastic < OuO; ++piastic) {
		solve();
	}
	return 0;
}
全部评论
请问有具体代码吗?
5 回复 分享
发布于 03-31 14:30 辽宁
求测试数据
点赞 回复 分享
发布于 04-08 10:38 广东
感觉这场难度挺大的……是现在选手太强了还是我没跟上版本TAT
点赞 回复 分享
发布于 04-05 00:27 上海

相关推荐

05-10 18:47
已编辑
门头沟学院 Java
京东零售-平台产品和研发中心后端一面凉经
30min，拷打简历自我介绍先聊天，问最快什么时候能来，能来多久（说少啦，该说6个月的）问了我简历上的竞赛项目做了什么（以前从没面试官感兴趣过）问蓝桥杯是什么，山东省自己组织的吗八股：1.&nbsp;说一下哈希表的实现原理2.&nbsp;为什么链表长度为8时，要转换成红黑树3.&nbsp;什么情况会破坏双亲委派机制4.&nbsp;说一下SPI和热加载5.&nbsp;说一下Java内存模型6.&nbsp;为什么内存模型要这么划分，以及会出现哪些问题7.&nbsp;线程池有哪些参数8.&nbsp;说说每一个参数是什么作用9.&nbsp;关于锁了解多少10.&nbsp;事务ACID特性都是怎么实现的11.&nbsp;慢查询了解多少12.&nbsp;分库分表了解多少，会存在什么问题13.&nbsp;Redis会丢数据吗14.&nbsp;除...
京东零售一面23人在聊 查看27道真题和解析
点赞 评论 收藏
分享
05-07 17:44
美团_产品经理(准入职员工)
点赞 评论 收藏
分享
04-16 04:21
广东培正学院 单片机
25届应届生，想找嵌入式软件工作，求大佬提点，听劝。真的尽我所能走投无路了，工作小白，没有实习，不知道咋办
嵌入式求职之路：可以看我经验😂，https://www.nowcoder.com/share/jump/73221730841876945
点赞 评论 收藏
分享
03-22 18:43
太原理工大学 Java
点赞 评论 收藏
分享
05-07 19:24
全志科技_产品经理(准入职员工)
全志科技内推-全志科技内推码
全志一面（技术面）面试时间：30分钟左右面试形式：视频面试1、让我自我介绍2、问我成绩，为啥研究成绩一般了？3、讲项目4、讲项目难点5、问了我一个跨时钟域的问题，100M时钟跨越到5M时钟，数据流，使用fifo，这样在5M时钟域会不会是duobit同时变化？格雷码的作用？6、问我静态时序分析？如果setup违例了应该怎么做？除了优化关键路径外?还可以怎么做？7、低功耗设计？设计人员可以做的低功耗设计本质上是尽量降低时钟频率的翻转。2、问了一个题，关于定点数加法的问题。全志二面（HR面）面试时间：18分钟左右面试形式：视频面试1、自我介绍2、怎么选一个公司3、你手头有什么公司的offer，4、你...
全志科技HR面33人在聊
点赞 评论 收藏
分享
评论
17
3
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 面试问题记录 #
60216次浏览 873人参与
# 硬件人的简历怎么写 #
254181次浏览 2884人参与
# 京东TGT #
47372次浏览 174人参与
# 你遇到过哪些神仙同事 #
71569次浏览 641人参与
# 我的2024小目标 #
57938次浏览 390人参与
# 工作中，你有没有遇到非常爱骂人的领导？ #
16863次浏览 126人参与
# 百度工作体验 #
204630次浏览 1907人参与
# 实习生应该准时下班吗 #
201446次浏览 1314人参与
# 上班到公司第一件事做什么？ #
37709次浏览 347人参与
# 国企和大厂硬件兄弟怎么选？ #
119970次浏览 1656人参与
# 工作一周年分享 #
19046次浏览 111人参与
# 没有合适的工作，你会先找个干着，还是考公考研 #
104241次浏览 1076人参与
# 面试吐槽bot #
13997次浏览 87人参与
# 互联网行业现在还值得去吗 #
6233次浏览 42人参与
# 面试经验谈 #
38781次浏览 509人参与
# 拼多多工作体验 #
16566次浏览 152人参与
# 入职第五天，你被拉进了几个工作群 #
17815次浏览 80人参与
# 假如我穿越到了妈妈的18岁 #
6155次浏览 43人参与
# 国企vs私企，你更想去？ #
217338次浏览 2072人参与
# 你们的毕业论文什么进度了 #
999160次浏览 9398人参与
# 机械人，你的第一份感谢信是谁给的 #
26687次浏览 296人参与
牛客网
牛客企业服务