梦熊十三连测题解

加减乘除

1.通过造样例可知：注意到两类操作并不会改变单调性，即对于任意 x≤y，在操作后仍然满足 x'≤y'。

2.所以我们就可以将原序列升序排序，分别通过二分找出最大和最小的下标。

3.时间复杂度：O(n* $\log_{2}max(ai)$ )。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int a[N];
int op[N],k[N],s[N],t[N];
int n,q;
__int128 check(__int128 c){
    for(int i=1;i<=q;i++){
        if(op[i]==1&&c>=k[i]) c=(c+s[i])*t[i];
        if(op[i]==2&&c<=k[i]) c=(c-s[i])/t[i];
    }
    return c;
}
int work(int lmt){
    int l=1,r=n,ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(a[mid])<=lmt) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
signed main(){
    freopen("arithmetic.in","r",stdin);
    freopen("arithmetic.out","w",stdout);
	ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int L,R;
    cin>>n>>q>>L>>R;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=q;i++) cin>>op[i]>>k[i]>>s[i]>>t[i];
    sort(a+1,a+1+n);
    cout<<work(R)-work(L-1)<<'\n';
    return 0;
}

图书管理

1.考虑计算每个中位数pi的贡献，对于pj>pi，令aj=1，对于pj<pi，令aj=-1，问题变为有多个区间[l,r]满足：l<=i<=r，且 $\sum_{j=l}^{r}$ aj=0。

2.具体做法：从i往左扫描并累计和sj= $\sum_{k=j}^{i}$ ak，使用一个数组标记每种sj的取值个数，类似从i往右累计和tj= $\sum_{k=i}^{j}$ ak，并询问取值为 -tj的s数量，

3.时间复杂度：O( $n^{2}$ )。

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int a[N];
int sum[N];
int cnt[N*2];
void print(__int128 x){
    if(x<10) cout<<(int)x;
    else{
        print(x/10);
        cout<<(int)(x%10);
    }
}
signed main(){
    freopen("book.in","r",stdin);
    freopen("book.out","w",stdout);
	ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    __int128 ans=0;
    for(int i=1;i<=n;i++){
        int now=0;
        for(int j=i;j;j--)
        {
            if(j!=i) now+=a[j]<a[i]?-1:1;
            cnt[now+n]+=j;
        }
        now=0;
        for(int j=i;j<=n;j++){
            if(j!=i) now+=a[j]<a[i]?-1:1;
            ans+=1ll*j*a[i]*cnt[-now+n];
        }
        now=0;
        for(int j=i;j;j--){
            if(j!=i) now+=a[j]<a[i]?-1:1;
            cnt[now+n]=0;
        }
    }
    print(ans);
    return 0;
}

两棵树

1.通过分析可知，连通块数=剩余的点数-剩余的边数，所以贡献就被拆成4部分：点*点-边*点-点*边+边*边。

2.以边*边为例，对于树T的边(u,v)假设被保留，概率为1/4，则树U中u,v一定被删除了，计算树U中有多少边(x,y)不以u或v为端点，每条边(x,y)都有1/4的概率被保留。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int power(int u,int v) {
	int ans = 1; while(v) {
		if(v&1) ans = ans*u%mod;
		u = u*u%mod; v >>= 1;
	} return ans;
}
int n,t[200010][2],u[200010][2],fac[200010],inv[200010],deg[200010]; map<int,int> mp;
int C(int u,int v) {
	return (u<0||u<v||v<0)?(0):(fac[u]*inv[v]%mod*inv[u-v]%mod);
}
signed main() {
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	cin.tie(0)->sync_with_stdio(false);
	cin >> n;
	for(int i = 1; i < n; i++) {
		cin >> t[i][0] >> t[i][1]; if(t[i][0] > t[i][1]) swap(t[i][0],t[i][1]);
		deg[t[i][0]]++; deg[t[i][1]]++; mp[t[i][0]*n+t[i][1]] = true;
	} int sum01 = 0;
	for(int i = 1; i < n; i++) {
		cin >> u[i][0] >> u[i][1];
		if(u[i][0] > u[i][1]) swap(u[i][0],u[i][1]);
		sum01 += n-1;
		if(mp[u[i][0]*n+u[i][1]]) sum01++;
		sum01 -= deg[u[i][0]];
		sum01 -= deg[u[i][1]];
	} sum01 %= mod;
	fac[0] = 1; for(int i = 1; i <= n; i++) fac[i] = fac[i-1]*i%mod;
	inv[n] = power(fac[n],mod-2); for(int i = n; i >= 1; i--) inv[i-1] = inv[i]*i%mod; int ans = 0;
	for(int i = 0; i <= n; i++) {
		(ans += C(n,i)*i%mod*(n-i)%mod) %= mod;
		(ans += mod-C(n-2,i)*i%mod*(n-1)%mod) %= mod;
		(ans += mod-C(n-2,i-2)*(n-i)%mod*(n-1)%mod) %= mod;
		(ans += C(n-4,i-2)*sum01) %= mod;
	}
	cout << ans*power(2,mod-1-n)%mod;
	return 0;
}

电报

1.貌似是一个结论题，结论很容易猜出来，

使用一棵（类似于哈夫曼树的）二叉树来编码。每个非叶子结点的两条子边权值分别为 1和2 。每个叶子节点对应了一个字符，其代价即为根到该叶子节点的路径长度。最优解中出现频次越大的字符深度越小，考虑由浅入深构造整棵二叉树。设f[i][a][b][l]表示构造二叉树深度为i,其中深度为i-1的节点有a个，深度为i-1的节点有 b个，深度不超过i-1的叶子有l个。可以枚举深度 i-1保留k个节点作为叶子，将剩下的节点扩展。由此可以得到一个 O( $n^{5}$ )复杂度的做法。