专栏文章

【M Contect-Div.3】#2 题解

mmengnn
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miobnyfk
此快照首次捕获于
2025/12/02 16:34
3 个月前
此快照最后确认于
2025/12/02 16:34
3 个月前
查看原文
都打得怎么样，我发现没一个人做出来我的题 QWQ。 ——mengnn。
本帖由 mengnn 编写，若有疏漏感谢指出。
本帖 2025.8.17 完工。

A. Tree-Music 题解

题面及思路

简单的模拟和判断，从头到尾把字符串看一遍就好，就不过多赘述。
注意：读入为一整行。

时间复杂度

简单的线形级复杂度，若设输入总字符数为 nn，则复杂度为 O(n)O(n)。

AC Code:

CPP
#include<bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s;
	while(1){
		cin>>s;
		if(s=="||")break;
		if(s=="|")putchar('|');
		if(s=="4")putchar('x');
		if(s=="8")putchar('_'),putchar('x');
		if(s=="16")putchar('_'),putchar('_'),putchar('x');
		if(s=="2")putchar('X');
		putchar(' ');
	}
	return 0;
}
代码来自 SP_beyond_xxxx。

B. Tree-City 题解

题面及思路

为方便描述，我们设第 ii 个 NPC 使旅行者获得的快乐度为 aia_i。
可以运用递推思想，对于 11~nn 中的每一个 ii，因为要静态的速算区间和，所以前缀和是很必要的，我们用 sumi=∑j=1iajsum_i=\sum_{j = 1}^{i} a_j。然后再存一个 minniminn_i 表示 min⁡j=1isumj\min_{j = 1}^{i} sum_j。
然后从 11 到 nn 遍历每一个 sumisum_i，贪心地更新答案 sumi−minni−1sum_i-minn_{i-1} 就好了。
这里我们节省数组的空间开销，运用滚动数组，用变量 sumsum 表示当前 sumisum_i，变量 mm 表示当前 mi−1m_{i-1}，ansans 表示答案。
注意：多测不清空，爆零两行泪。

时间复杂度

数据组数为 TT，序列元素个数为 nn，则复杂度为 O(Tn)O(Tn)。

AC Code:

CPP
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5;
const long long INF=0x7f7f7f7f7f7f7f7f;
int T,n,a[N];
long long sum,ans,m;
int main(){
    cin>>T;
    while(T--){
    	cin>>n;
    	for(int i=1;i<=n;i++) cin>>a[i];
		ans=-INF;m=sum=0;
		for(int i=1;i<=n;i++){
			sum+=a[i];
			ans=max(ans,sum-m);
			m=min(m,sum);
		}cout<<ans<<'\n';
	}return 0;
}
代码来自 mengnn。

C. Tree-Maths 题解

题面及思路

高精度很恶心的，但他还是出了 (T n T)。
纯模拟，根据题目来就行，先把两个数字转成非科学计数法形式，然后高精加/减即可。

时间复杂度

数据组数为 TT，序列元素个数为 nn，则复杂度为 O(Tn)O(Tn)。

AC Code:

CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
long long s_2,r,a[N],b[N],c[N],len,p,temp[N];
string s1,s2;
string ss,sss;
char f='+';

struct SciNum {
    string num;
    int exp;
};

SciNum parseSci(string s) {
    SciNum res;
    size_t e_pos = s.find('e');
    if(e_pos == string::npos) {
        res.num = s;
        res.exp = 0;
    } else {
        res.num = s.substr(0, e_pos);
        res.exp = stoi(s.substr(e_pos+1));
    }
    return res;
}

string normalize(SciNum sn) {
    string num = sn.num;
    int exp = sn.exp;
    
    size_t dot_pos = num.find('.');
    if(dot_pos != string::npos) {
        exp -= (num.size() - dot_pos - 1);
        num.erase(dot_pos, 1);
    }
    
    while(num.size() > 1 && num[0] == '0') {
        num.erase(0, 1);
    }
    
    return num + string(exp, '0');
}

void jia(long long a[],long long b[]){
    for(int i=1;i<=len+1;i++){
        c[i]+=a[i]+b[i];
        if(c[i]>=10){
            c[i+1]+=1;
            c[i]%=10;
        }
    }
    len=max(s1.size(),s2.size());
    if(c[len+1]!=0){
        len++;
    }
    for(int i=len;i>0;i--){
        cout<<c[i];
    }
}

void jian(long long a[],long long b[]){
    for(int i=1;i<=len+1;i++){
        if(a[i]<b[i]){
            a[i+1]-=1;
            a[i]+=10;
        }
        c[i]=a[i]-b[i];
    }
    if(s1.size()<s2.size()||(s1<s2&&s1.size()==s2.size())){
        swap(s1,s2);
        f='-';
    }len=max(s1.size(),s2.size());
    for(int i=len;i>=1;i--){
        if(c[i]!=0){
            p=i;
            break;
        }
    }
    if(f=='-'){
        cout<<f;
    }
    for(int i=p;i>0;i--){
        cout<<c[i];
    }
    if(p==0){
        cout<<'0';
    }
}

int main(){
    char op;
    cin>>ss>>op>>sss;
    
    SciNum num1 = parseSci(ss);
    SciNum num2 = parseSci(sss);
    
    s1 = normalize(num1);
    s2 = normalize(num2);
    
    a[0]=s1.size();
    b[0]=s2.size();
    for(int i=0;i<a[0];i++)a[a[0]-i]=s1[i]-'0';
    for(int i=0;i<b[0];i++)b[b[0]-i]=s2[i]-'0';
    
    len=max(a[0],b[0]);
    if(op=='+') jia(a,b);
    else jian(a,b);
    
    return 0;
}
代码来自 SP_beyond_xxxx。

D. Tree-Dream 题解

题面及思路

题目很经典也很迷惑，看起来像是 LIS 变形，实际上是树状数组简单应用。
我们定义树状数组 ss 和 tt，分别维护从前到后和从后到前 11~kk 的数出现个数的前缀和（kk 为任意数）。
对于树状数组 ss，每次我们要先查询后修改，因为我们要求的是严格上升，所以我们需要计算 1≤j<i≤n,aj<ain1\le j<i\le n,a_j<a_in 的 jj 的数量。易知，答案即为 s.ask(a[i]-1)。
对于树状数组 tt，与 ss 同理，但我们要逆序求答案。我们需要计算 1≤i<j≤n,ai<aj1\le i<j\le n,a_i<a_j 的 jj 的数量。我们可以运用补集思想，ai≥aja_i\ge a_j，答案即 t.ask(a[i])，那么我们要求 ai<aja_i<a_j，答案即为 n-i-t.ask(a[i])，答案中的 n−in-i 为现在 tt 中的元素个数。因为我们先查询后修改，所以是不需要加一的。
注意到 max⁡i=1nai\max_{i=1}^{n} a_i 实际上很大，达到了 103610^{36} 量级，long long 绝对是存不下的，可以用 __int128 存储。
再注意到 nn 和 max⁡i=1nai\max_{i=1}^{n} a_i 的差距特别大，最坏情况才有 2×1062\times10^6 个数被应用，我们的树状数组开不了 103610^{36} 这就必须要离散化 或用 map 存储。
假如说树状数组 ss 对于 a1,a2,...,ana_1,a_2,...,a_n 的答案为 l1,l2,...,lnl_1,l_2,...,l_n，树状数组 tt 对于 a1,a2,...,ana_1,a_2,...,a_n 的答案为 r1,r2,...,rnr_1,r_2,...,r_n。根据简单的组合数运算，则最终的答案就是 ∑i=1nli⋅ri\sum_{i=1}^{n}l_i\cdot r_i。
因为输入元素个数较多，我们保险一些，写上快速读入。
最后，注意答案要开 long long。

时间复杂度

因为输入元素个数为 nn，所以输入和遍历数组复杂度绝对就是 O(n)O(n) 的。
又因为用到了离散化和树状数组，所以它们各会取一个 O(log⁡2n)O(\log_2n)。
总时间复杂度来到了 O(n+nlog⁡22n)O(n+n\log_2^2n)，最终复杂度 O(nlog⁡22n)O(n\log_2^2n) 看起来不太能通过，但树状数组的和离散化二分的 log⁡2n\log_2n 常数都很小，足以通过此题。

AC Code:

CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
__int128 n,a[N],mp[N],ans;
long long l[N];
inline void rd(__int128 &x){
	x=0;char ch;
	bool f=false;
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar())
		if (ch=='-')
			f=true;
	for(;ch>='0'&&ch<='9';ch=getchar())
		x=(x<<3)+(x<<1)+(ch&15);
	if (f) x=-x;
}
inline void wr(__int128 x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) wr(x/10);
	putchar(x%10+'0');
	return ;
}
inline int f(__int128 v){
	return lower_bound(mp+1,mp+n+1,v)-mp+1;
}
struct Tree{
	int c[N];
	inline void add(int x,int v){
		for (;x<=n;x+=x&-x)
			c[x]+=v;
	}
	inline int ask(int x){
		int res=0;
		for (;x;x^=x&-x)
			res+=c[x];
		return res;
	}
}s,t;
int main(){
	rd(n);
	for (int i=1;i<=n;i++) rd(a[i]),mp[i]=a[i];
	sort(mp+1,mp+n+1);
	for (int i=1;i<=n;i++){
		l[i]=s.ask(f(a[i])-1);
		s.add(f(a[i]),1);
	}
	for (int i=n;i;i--){
		if (i!=n&&i!=1)
			ans+=l[i]*(n-i-t.ask(f(a[i])));
		t.add(f(a[i]),1);
	}
	wr(ans);
	return 0;
}

E. Tree-Save 题解

题面及思路

为了提高 AK 概率，这题还是出得很板的，一眼树剖，只不过线段树需要允许区间乘，区间加，区间求和。
线段树和树剖不会写的建议去这里和这里。

时间复杂度

树链剖分的初始化要遍历两次树，若树的节点数为 nn 个，则复杂度为 O(n)O(n)。
可以证明，树链剖分会把树剖分成 log⁡2n\log_2n 条链，所以跳链复杂度为 O(log⁡2n)O(\log_2n)。
线段树的维护时 O(log⁡2n)O(\log_2n) 的，又因为有 qq 次询问，所以总时间复杂度来到了 O(n+qlog⁡22n)O(n+q\log_2^2n)，最终复杂度 O(qlog⁡22n)O(q\log_2^2n)。

AC Code:

CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const long long mod=998244353;
int n,m,R;
long long val[N];
int f[N],son[N],sz[N],dep[N];
int top[N],dfn[N],rnk[N],cnt;
vector<int> edge[N];
struct STree{
	struct node{
		int l,r;
		long long mul,add,sum;
	}t[N<<2];
	inline void build(int p,int l,int r){
		t[p].l=l;t[p].r=r;
		t[p].mul=1;t[p].add=0;
		if (l==r){
			t[p].sum=val[rnk[l]]%mod;
			return ;
		}int mid=(l+r)>>1;
		build(p<<1,l,mid);
		build(p<<1|1,mid+1,r);
		t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%mod;
		return ;
	}
	inline void pushdown(int p){
	    int l=p<<1,r=p<<1|1;
	    t[l].sum=(t[l].sum*t[p].mul+t[p].add*(t[l].r-t[l].l+1))%mod;
	    t[r].sum=(t[r].sum*t[p].mul+t[p].add*(t[r].r-t[r].l+1))%mod;
	    t[l].mul=(t[l].mul*t[p].mul)%mod;
	    t[r].mul=(t[r].mul*t[p].mul)%mod;
	    t[l].add=(t[l].add*t[p].mul+t[p].add)%mod;
	    t[r].add=(t[r].add*t[p].mul+t[p].add)%mod;
	    t[p].add=0;t[p].mul=1;
		return ;
	}
	inline void change(int p,int l,int r,long long v,bool d){
		if (l<=t[p].l&&t[p].r<=r){
			if (d){
				t[p].add=v*t[p].add%mod;
				t[p].mul=v*t[p].mul%mod;
				t[p].sum=v*t[p].sum%mod;
			}else{
				t[p].add=(t[p].add+v)%mod;
				t[p].sum=(t[p].sum+v*(t[p].r-t[p].l+1)%mod)%mod;
			}return ;
		}
		pushdown(p);
		int mid=(t[p].l+t[p].r)>>1;
		if (l<=mid) change(p<<1,l,r,v,d);
		if (r>mid) change(p<<1|1,l,r,v,d);
		t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%mod;
		return ;
	}
	inline long long ask(int p,int l,int r){
		if (l<=t[p].l&&t[p].r<=r) return t[p].sum;
		pushdown(p);
		int mid=(t[p].l+t[p].r)>>1;
		long long val=0;
		if (l<=mid) val=(val+ask(p<<1,l,r))%mod;
		if (r>mid) val=(val+ask(p<<1|1,l,r))%mod;
		return val;
	}
}st;
inline void dfs1(int x){
	sz[x]=1;
	son[x]=-1;
	for (auto y:edge[x])
		if (!dep[y]){
			dep[y]=dep[x]+1;
			f[y]=x;
			dfs1(y);
			sz[x]+=sz[y];
			if (son[x]==-1||sz[y]>sz[son[x]]) son[x]=y;
		}
}
inline void dfs2(int x,int t){
	top[x]=t;
	dfn[x]=++cnt;
	rnk[cnt]=x;
	if (son[x]==-1) return ;
	dfs2(son[x],t);
	for (auto y:edge[x])
		if (y!=f[x]&&y!=son[x])
			dfs2(y,y);
}
inline void add_ans(int x,int y,long long v){
	while (top[x]!=top[y]){
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
		st.change(1,dfn[top[x]],dfn[x],v,0);
		x=f[top[x]];
	}if (dfn[x]>dfn[y]) swap(x,y);
	st.change(1,dfn[x],dfn[y],v,0);
}
inline void cheng_ans(int x,int y,long long v){
	while (top[x]!=top[y]){
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
		st.change(1,dfn[top[x]],dfn[x],v,1);
		x=f[top[x]];
	}if (dfn[x]>dfn[y]) swap(x,y);
	st.change(1,dfn[x],dfn[y],v,1);
}
inline long long get_ans(int x,int y){
	long long ans=0;
	while (top[x]!=top[y]){
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
		ans=(ans+st.ask(1,dfn[top[x]],dfn[x]))%mod;
		x=f[top[x]];
	}if (dfn[x]>dfn[y]) swap(x,y);
	return (ans+st.ask(1,dfn[x],dfn[y]))%mod;
}
int main(){
	scanf("%d%d",&n,&m);R=1;
	for (int i=1;i<=n;i++) scanf("%lld",&val[i]);
	for (int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		edge[x].push_back(y);
		edge[y].push_back(x);
	}dep[R]=1;dfs1(R);dfs2(R,R);
	st.build(1,1,n);
	while (m--){
		long long opt,x,y,z;
		scanf("%lld%lld",&opt,&x);
		if (opt<6) scanf("%lld",&y);
		if (opt<3) scanf("%lld",&z);
		if (opt==1) add_ans(x,y,z);
		if (opt==2) cheng_ans(x,y,z);
		if (opt==3) printf("%lld\n",get_ans(x,y));
		if (opt==4) st.change(1,dfn[x],dfn[x]+sz[x]-1,y,0);
		if (opt==5) st.change(1,dfn[x],dfn[x]+sz[x]-1,y,1);
		if (opt==6) printf("%lld\n",st.ask(1,dfn[x],dfn[x]+sz[x]-1));
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...