2024“钉耙编程”中国大学生算法设计超级联赛(1)(9/9/13)

题目

H. 位运算
题意

t(t<=10)组样例,每次给定n,k(n<2^k,k<=15),

求在[0,2^k)的数a,b,c,d,满足(((a&b)^c)|d)=n

题解

注意到每个二进制位是独立的,所以可以枚举a、b、c、d在某一位是0还是1,把合法方案乘起来

代码
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=4e4+10;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int T,n,k;
ll ans=0;
int main(){
    sci(T);
    while(T--){
        sci(n);sci(k);
        ans=1;
        rep(i,0,k-1){
            int w=n>>i&1,cnt=0;
            rep(x,0,1){
                rep(y,0,1){
                    rep(u,0,1){
                        rep(v,0,1){
                            if((((x&y)^u)|v)==w){
                                cnt++;
                            }
                        }
                    }
                }
            }
            ans*=cnt;
        }
        ptlle(ans);
    }
    return 0;
}
B. 数星星(背包)
题意

n(n<=1e3)次机会,第i次可以选择摘[0,4]颗星星,摘不同颗数对应代价不同

现在想摘k(k<=4n)颗星星,求最小代价,实际多组样例保证sumn不超过1e5

题解

O(nk)dp,在第i次决策时是一个分组背包,从中选一个最优的转移

代码
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=4e4+10;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int T,n,k,a[5];
ll dp[N];
int main(){
    sci(T);
    while(T--){
        sci(n);sci(k);
        rep(i,1,4*n)dp[i]=INF;
        rep(i,1,n){
            rep(j,1,4){
                sci(a[j]);
            }
            per(x,k,1){
                ll z=INF;
                rep(y,1,4)if(x>=y)z=min(z,dp[x-y]+a[y]);
                dp[x]=min(dp[x],z);
            }
        }
        ptlle(dp[k]);
    }
    return 0;
}
A. 循环位移(哈希)
题意

给定串a和串b,都由大写字母组成,其中|a|<=|b|

问b由多少个子串,可以由a循环移位得到,多组样例,保证sum|b|<=2^{20}

题解

哈希,将a的所有循环串的哈希值处理出来,放到map里

记a的长度为n,遍历b串所有长度为n的子串,哈希值在map里的就加上

代码
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#include<random>
#include<cstdio>
#include<algorithm>
#include<chrono>
#include<ctime>
#include<cstdlib>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
mt19937_64 rng((unsigned int) time(NULL));
 
struct hash61 {
  static const uint64_t md = (1LL << 61) - 1;
  static uint64_t step;
  static vector<uint64_t> pw;
 
  uint64_t addmod(uint64_t a, uint64_t b) const {
    a += b;
    if (a >= md) a -= md;
    return a;
  }
 
  uint64_t submod(uint64_t a, uint64_t b) const {
    a += md - b;
    if (a >= md) a -= md;
    return a;
  }
 
  uint64_t mulmod(uint64_t a, uint64_t b) const {
    uint64_t l1 = (uint32_t) a, h1 = a >> 32, l2 = (uint32_t) b, h2 = b >> 32;
    uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
    uint64_t ret = (l & md) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
    ret = (ret & md) + (ret >> 61);
    ret = (ret & md) + (ret >> 61);
    return ret - 1;
  }
 
  void ensure_pw(int sz) {
    int cur = (int) pw.size();
    if (cur < sz) {
      pw.resize(sz);
      for (int i = cur; i < sz; i++) {
        pw[i] = mulmod(pw[i - 1], step);
      }
    }
  }
 
  vector<uint64_t> pref;
  int n;
 
  template<typename T>
  hash61(const T& s) {
    n = (int) s.size();
    ensure_pw(n + 1);
    pref.resize(n + 1);
    pref[0] = 1;
    for (int i = 0; i < n; i++) {
      pref[i + 1] = addmod(mulmod(pref[i], step), s[i]);
    }
  }
 
  inline uint64_t operator()(const int from, const int to) const {
    //assert(0 <= from && from <= to && to <= n - 1);
    return submod(pref[to + 1], mulmod(pref[from], pw[to - from + 1]));
  }
};
 
uint64_t hash61::step = (md >> 2) + rng() % (md >> 1);
vector<uint64_t> hash61::pw = vector<uint64_t>(1, 1);
 
string s,t;
int T,n,m;
map<uint64_t,bool>mp;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>T;
    while(T--){
        cin>>s>>t;
        n=s.size();
        s+=s;
        auto hs=hash61(s);
        auto hs2=hash61(t);
        mp.clear();
        rep(i,0,n-1){
            mp[hs(i,i+n-1)]=true;
            //printf("aa:%lld\n",hs(i,i+n-1));
        }
        int cnt=0;
        m=t.size();
        rep(i,n-1,m-1){
            //cout<<hs2(i-n+1,i)<<endl;
            if(mp.count(hs2(i-n+1,i)))cnt++;
        }
        cout<<cnt<<endl;
    }
	return 0;
}
L. 并(离散化+贡献)
题意

n(n<=2e3)个矩形,第i个左上角(xi1,yi1),右下角(xi2,yi2),

对于每个k∈[1,n],求n个矩形随机选k个时,矩形并的面积的期望值,答案取模998244353

题解

坐标离散化,统计每个离散化后的最小矩形在C(n,k)次中的被覆盖次数,

离散化后横纵坐标都不会超过4e3,每个原始矩形可以对矩形覆盖部分+1,

也就是先二维差分,然后二维前缀和,

假设一个最小矩形被覆盖次数是x,那么有贡献的方案数是C(n,k)-C(n-x,k),

也就是任意选,减去没有被覆盖的方案数

矩形是O(n^2)个的,但是出现次数只有O(n)个,可以先按出现次数给矩形归类,

再遍历每个k,求n个选k个时的答案,复杂度O(n^2)

代码

hdu不支持sort了所以只能stable_sort

#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#include<random>
#include<cstdio>
#include<algorithm>
#include<chrono>
#include<ctime>
#include<cstdlib>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=2e3+10,M=4e3+10,mod=998244353;
int n,x[M],y[M],c,d,a[M][M],C[M][M],b[M];
void add(int x1,int y1,int x2,int y2){
    a[x1][y1]++;
    a[x2+1][y1]--;
    a[x1][y2+1]--;
    a[x2+1][y2+1]++;
}
struct node{
    int x1,y1,x2,y2;
    void read(){
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        x[c++]=x1;x[c++]=x2;
        y[d++]=y1;y[d++]=y2;
    }
}e[N];
int modpow(int x,int n,int mod){
    int res=1;
    for(;n;n/=2,x=1ll*x*x%mod)if(n&1)res=1ll*res*x%mod;
    return res;
}
int main(){
    sci(n);
    C[0][0]=1;
    rep(i,1,n){
        C[i][0]=C[i][i]=1;
        rep(j,1,i-1)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    rep(i,1,n){
        e[i].read();
    }
    stable_sort(x,x+c);
    stable_sort(y,y+d);
    c=unique(x,x+c)-x;
    d=unique(y,y+d)-y;
    rep(i,1,n){
        e[i].x1=lower_bound(x,x+c,e[i].x1)-x+1;
        e[i].x2=lower_bound(x,x+c,e[i].x2)-x+1;
        e[i].y1=lower_bound(y,y+d,e[i].y1)-y+1;
        e[i].y2=lower_bound(y,y+d,e[i].y2)-y+1;
        //printf("x1:%d y1:%d x2:%d y2:%d\n",e[i].x1,e[i].y1,e[i].x2,e[i].y2);
        add(e[i].x1,e[i].y1,e[i].x2-1,e[i].y2-1);
    }
    rep(i,1,c){
        rep(j,1,d){
            int v=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
            a[i][j]+=v;
            //printf("i:%d j:%d [%d->%d][%d->%d] aij:%d\n",i,j,x[i-1],x[i],y[j-1],y[j],a[i][j]);
            int &w=a[i][j];
            int s=1ll*(x[i]-x[i-1])*(y[j]-y[j-1])%mod;
            b[w]=(b[w]+s)%mod;
            //ans=(ans+1ll*f*s)%mod;
        }
    }
    rep(k,1,n){
        int ans=0;
        rep(w,1,n){
            int f=C[n][k]-C[n-w][k];
            f=(f%mod+mod)%mod;
            ans=(ans+1ll*f*b[w]%mod)%mod;
        }
        ans=1ll*ans*modpow(C[n][k],mod-2,mod)%mod;   
        pte(ans);
    }
    //pte(3ll*665496240%mod);
	return 0;
}
C. 树(启发式合并/线段树合并)
题意

n(n<=5e5)个点,1为根的有根树,点i权值ai(1<=ai<=1e6)

点对f(u,v)=max(au,av)*abs(au-av),也就是二者max乘以二者差的绝对值

对于每个i,点i的答案ans[i]是在i的子树内任取点u、点v时,f(u,v)之和

输出所有ans[i]取模2^{64}后的异或和

题解

一开始我以为答案不会超过2^{64},直到wa了一发,

取模就开unsigned long long自然溢出即可

启发式合并复杂度O(nlogn^2),线段树合并能少一个log

这里用的启发式合并,

对于点u来说,答案由两部分组成,

要么是完全在子树内的,要么是两个点在不同子树,满足lca=u的

第一部分递归下去即可,

第二部分在把轻儿子v往重儿子son维护的数据结构上挂的时候维护son、v的答案

对于au来说,

1. 如果au是最大值,那么贡献是au*(au-av),

假设比au小的av有c个,它们的av之和是y,

那么au作为最大值的贡献就是c*au*au-au*y

2. 如果au不是最大值,那么贡献是av*(av-au)

假设比au大的av的所有av*av之和是y2,它们的av之和是del,

那么au不是最大值时的贡献就是y2-del*au

所以,需要三棵线段树,分别维护值为av的个数,值为av的av之和,值为av的av*av之和

也就是分别维护零次方和、一次方和,二次方和,

当然,如果注意到f(u,v)=max*max-max*min,

而max*min是点对之间的乘积,可以把max*min提前预处理好,也就不用维护一次方和了

u、v可以交换顺序,所以答案需要*2,

对于v子树先查询v子树内的所有点,然后把v子树内的所有点挂上去

对于轻儿子的节点,手动回收线段树上的值

代码
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#include<random>
#include<cstdio>
#include<algorithm>
#include<chrono>
#include<ctime>
#include<cstdlib>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
namespace fastIO
{
    static char buf[100000],*h=buf,*d=buf;//缓存开大可减少读入时间,看题目给的空间
    #define gc h==d&&(d=(h=buf)+fread(buf,1,100000,stdin),h==d)?EOF:*h++//不能用fread则换成getchar
    template<typename T>
    inline void read(T&x)
    {
        int f = 1;x = 0;
        register char c(gc);
        while(c>'9'||c<'0'){
            if(c == '-') f = -1;
            c=gc;
        }
        while(c<='9'&&c>='0')x=(x<<1)+(x<<3)+(c^48),c=gc;
        x *= f;
    }
    template<typename T>
    void output(T x)
    {
        if(x<0){putchar('-');x=~(x-1);}
        static int s[20],top=0;
        while(x){s[++top]=x%10;x/=10;}
        if(!top)s[++top]=0;
        while(top)putchar(s[top--]+'0');
    }
}
using namespace fastIO;
const int N=5e5+10,K=1e6,M=1e6+10;
struct BitPre{ // 求前缀和(可改为max等)
	int n;ll tr[M];
	void init(int _n){
		n=_n;
		memset(tr,0,(n+1)*sizeof(*tr));
	}
	void add(int x,ll v){
		for(int i=x;i<=n;i+=i&-i)
		tr[i]+=v;
	}
	ll sum(int x){
		ll ans=0; 
		for(int i=x;i;i-=i&-i)
		ans+=tr[i];
		return ans;
	}
}tr,tr2,tr3;//1 a[u] a[u]*a[u]
vector<int>E[N],now;
int n,u,v,a[N];
int sz[N],st[N],ed[N],dfn[N],tot;
ull res[N],ans;
void op(ull &x,int u){
    ll c=tr.sum(a[u]);//a[u]*(a[u]-a[v])
    ll y=tr2.sum(a[u]);
    ull v=1ll*c*a[u]*a[u]-1ll*a[u]*y;
    ll y2=tr3.sum(K)-tr3.sum(a[u]);//a[v]*(a[v]-a[u])
    ll del=tr2.sum(K)-tr2.sum(a[u]);
    y2-=del*a[u];
    v+=y2;v*=2;
    //printf("u:%d addv:%lld\n",u,2ll*v);
    x+=v;
}
void dfs(int u,int fa){
    sz[u]=1;
    st[u]=++tot;
    dfn[tot]=u;
    for(int &v:E[u]){
        if(v!=fa){
            dfs(v,u);
            sz[u]+=sz[v];
        }
    }
    ed[u]=tot;
}
void dfs(int u,int fa,bool keep){
    int mx=-1,son=-1;
    for(int &v:E[u]){
        if(v!=fa&&sz[v]>mx)
            mx=sz[v],son=v;
    }
    for(int &v:E[u]){
        if(v!=fa&&v!=son){
            dfs(v,u,0);
            res[u]+=res[v];
        }
    }
    if(son!=-1){
        dfs(son,u,1);
        res[u]+=res[son];
    }
    for(int &v:E[u]){
        if(v!=fa&&v!=son){
            for(int i=st[v];i<=ed[v];i++){
                int x=dfn[i];
                //查询x
                op(res[u],x);
            }
            for(int i=st[v];i<=ed[v];i++){
                int x=dfn[i];
                //插入x
                tr.add(a[x],1);
                tr2.add(a[x],a[x]);
                tr3.add(a[x],1ll*a[x]*a[x]);
                now.pb(x);
            }
        }
    }
    op(res[u],u);
    tr.add(a[u],1);
    tr2.add(a[u],a[u]);
    tr3.add(a[u],1ll*a[u]*a[u]);
    now.pb(u);
    if(keep==0){
    	for(int &v:now){
            tr.add(a[v],-1);
            tr2.add(a[v],-a[v]);
            tr3.add(a[v],-1ll*a[v]*a[v]);
        }
        now.clear();
    }
    //printf("u:%d res:%llu\n",u,res[u]);
    ans^=res[u];
}
int main(){
    read(n);
    for(int i=1;i<n;++i){
        read(u);read(v);
        E[u].pb(v);
        E[v].pb(u);
    }
    for(int i=1;i<=n;++i)read(a[i]);
    tr.init(K);
    tr2.init(K);
    tr3.init(K);
    dfs(1,-1);
    dfs(1,-1,0);
    cout<<ans;
    return 0;
}
E. 博弈(概率)
题意

小马给出了一个可重小写字符集合 𝑆。

Alice 初始时有空串 𝐴,Bob 初始时有空串 𝐵。

两人轮流等概率取出集合𝑆中的一个字符 𝑐,

将它拼接到自己的字符串的后面,直至 𝑆 为空,每个字符只能被取一次,Alice 先手。

如果最终 𝐴 的字典序严格大于 𝐵,则 Alice 胜利,求其获胜的概率,答案对 998244353取模。

实际T(T<=1e4)组样例,字符集大小n(n<=26),第i种字符是ci,有hi个,sumhi<=1e7

题解

因为两人都是等概率取的,可以直接统计终态局面有多少种可能性

1. 如果字符总数是偶数,那么alice和bob获胜的概率是相同的,都是(1-二人字典序相等的概率)/2

二人字典序相等的概率:

前提是每种字符都是偶数,否则为0

在这个前提下,每个人都取了一半,第i种字符选hi/2个,

alice的可重集全排列方案数是\frac{(\sum_{i=1}^{n}\frac{h_{i}}{2})!}{\prod_{i=1}^{n}(\frac{h_{i}}{2})!},bob需要和其完全一致,

概率=合法方案数/所有方案数,而所有方案数是\frac{(\sum_{i=1}^{n}h_{i})!}{\prod_{i=1}^{n}h_{i}!}

2. 然后考虑奇数,和偶数区别在于,

可能前sumhi/2步是相等的,但是由于alice串更长,导致字典序还是大了

枚举alice最后一步是哪个字母,选到这个字母的对应概率为hi/sumhi

然后考虑前面sumhi/2步(也就是不算alice最后一个字母)的局面,

这是一个总字符数为偶数的局面,算法和上面算偶数的一样,前面的局面分三种:

①alice字典序大

②alice和bob字典序相同

③bob字典序大

①和③概率是相同的,而②因为alice最后一个字母的出现应该被算成alice获胜的局面

记①的概率为p,则②的概率为1-2p,有alice此时获胜的概率为①+②=1-p

枚举所有字母求和即可

代码
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#include<random>
#include<cstdio>
#include<algorithm>
#include<chrono>
#include<ctime>
#include<cstdlib>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e7+10,M=28,mod=998244353;
int Finv[N],fac[N],inv[N];
int modpow(int x,int n,int mod){
	int res=1;
	for(;n;x=1ll*x*x%mod,n>>=1)
	if(n&1)res=1ll*res*x%mod;
	return res;
}
void init(int n){ //n<N
    inv[1]=1;
    for(int i=2;i<=n;++i)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	fac[0]=Finv[0]=1;
	for(int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mod,Finv[i]=1ll*Finv[i-1]*inv[i]%mod;
	//Finv[n]=modpow(fac[n],mod-2,mod);
	//for(int i=n-1;i>=1;--i)Finv[i]=1ll*Finv[i+1]*(i+1)%mod;
}
int C(int n,int m){
	if(m<0||m>n)return 0;
	return 1ll*fac[n]*Finv[n-m]%mod*Finv[m]%mod;
}
int t,n,sum,a[M];
char s[5];
int cal(int sum){
    bool ok=1;
    int w=1,s2=sum/2,w2=1;
    rep(i,1,n){
        ok&=(a[i]%2==0);
        int v=a[i]/2;
        w=1ll*w*Finv[v]%mod;
        w2=1ll*w2*fac[a[i]]%mod;//总方案数的倒数
    }
    if(!ok)return inv[2];
    w=1ll*w*fac[s2]%mod;
    w2=1ll*w2*Finv[sum]%mod;
    w=1ll*w*w2%mod;
    w=1ll*(1+mod-w)%mod*inv[2]%mod;
    return w;
}
int sol(){
    if(sum%2==0){
        return cal(sum);
    }
    else{
        int res=0;
        rep(i,1,n){
            a[i]--;
            int p=cal(sum-1);//bob胜 去掉这个字符与alice相等
            a[i]++;
            p=(1-p+mod)%mod;//alice胜(含前面平)
            //printf("i:%d p:%d a[i]:%d sum:%d\n",i,p,a[i],sum);
            //乘上alice第(sum+1)/2轮取这个字符的概率
            int p2=1ll*a[i]*inv[sum]%mod;
            //printf("1/3:%d 1/2:%d\n",inv[3],inv[2]);
            p=1ll*p*p2%mod;
            //printf("i:%d newp:%d\n",i,p);
            res=(res+p)%mod;
        }
        return res;
    }
}
int main(){
    init(N-5);
    sci(t);
    while(t--){
        sci(n);
        sum=0;
        rep(i,1,n){
            scanf("%s%d",s,&a[i]);
            sum+=a[i];
        }
        pte(sol());
    }
	return 0;
}
D. 传送(线段树分治+可撤销并查集+lazytag)
题意

n(n<=6e5)个点m(m<=6e5)条边的无向图,每条边有四个属性(a,b,l,r),

表示在时刻[l,r]内,a和b这条边是联通的,否则是断开的,

有一个传送技能:如果在某时刻 𝑢 和 𝑣 在一个连通块里,可以从 𝑢 传送到 𝑣 。

小 A 初始在节点 1 ,问能在 [1,𝑛] 中的哪些时间点能直接从 1 传送到节点 𝑖 。

记ans[i]为所有能从1到i的时间点之和,输出所有ans[i]的异或和

题解

如果强制在线只能lct,可以离线的话,先考虑线段树分治+可撤销并查集

入坑这个科技是在

Educational Codeforces Round 62 (Rated for Div. 2) F. Extending Set of Points(可撤销并查集+线段树分治)_codeforces edu r162-CSDN博客

然后考虑怎么维护要求的值,并查集的合并和撤销相当于两棵树连到一起和拆开的操作

假设有两棵树u、v,树根分别是u、v,连到一起时,不妨是v挂到u下,断开时是v自立为根

递归到底l=r的时候,代表时间点l处,

此时给1所在的并查集树根,也就是u,打上+l标记,表示这棵树内的所有点都需要+l

1. 断开u和v的的时候,将u的标记下放给v,表示断开后的树根也需要这些曾经加过的标记

2. 合并u和v的时候,由于u有一个全树加的标记,而v在合并前是不需要这个标记的,

给v减去u的标记,再把v挂到u上即可

因为最后每条边在时刻n后都会断开,

所以标记会完成最终的所有下放,每个点的标记值即为最终所求

代码
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#include<random>
#include<cstdio>
#include<algorithm>
#include<chrono>
#include<ctime>
#include<cstdlib>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
namespace fastIO
{
    static char buf[100000],*h=buf,*d=buf;//缓存开大可减少读入时间,看题目给的空间
    #define gc h==d&&(d=(h=buf)+fread(buf,1,100000,stdin),h==d)?EOF:*h++//不能用fread则换成getchar
    template<typename T>
    inline void read(T&x)
    {
        int f = 1;x = 0;
        register char c(gc);
        while(c>'9'||c<'0'){
            if(c == '-') f = -1;
            c=gc;
        }
        while(c<='9'&&c>='0')x=(x<<1)+(x<<3)+(c^48),c=gc;
        x *= f;
    }
    template<typename T>
    void output(T x)
    {
        if(x<0){putchar('-');x=~(x-1);}
        static int s[20],top=0;
        while(x){s[++top]=x%10;x/=10;}
        if(!top)s[++top]=0;
        while(top)putchar(s[top--]+'0');
    }
}
using namespace fastIO;
const int maxn=6e5,N=maxn+10;
vector<P>dat[4*N];
int n,m,par[N],sz[N];
ll add[N],ans;
P a;
int find(int x){
	return par[x]==x?x:find(par[x]);
}
bool merge(int x,int y,vector<P> &q){
	x=find(x),y=find(y);
	if(x==y)return 1;
	if(sz[x]<sz[y])swap(x,y);
	q.pb(P(x,y));
    add[y]-=add[x];
	sz[x]+=sz[y];
	par[y]=x;
    return 0;
}
void undo(vector<P> &q){
	while(!q.empty()){
		int x=q.back().fi;
		int y=q.back().se;
		q.pop_back();
		sz[x]-=sz[y];
        add[y]+=add[x];
		par[y]=y;
	} 
} 
void update(int p,int l,int r,int ql,int qr,P v){
	if(ql<=l&&r<=qr){
		dat[p].pb(v);
		return;
	}
	int mid=(l+r)/2;
	if(ql<=mid)update(lson,ql,qr,v);
	if(qr>mid)update(rson,ql,qr,v);
}
void dfs(int p,int l,int r){
	vector<P>q;
	for(auto v:dat[p]){
	    merge(v.fi,v.se,q);
    }
    if(l==r){
        // rep(i,1,n){
        //     printf("l:%d i:%d f:%d\n",l,i,find(i));
        // }
        // puts("");
        int f=find(1);
        add[f]+=l;
        //printf("l:%d f:%d add:%lld\n",l,f,add[f]);
    }
	else{
		int mid=(l+r)/2;
		dfs(lson);
		dfs(rson);
	}
	undo(q);
}
int main(){
    read(n);read(m);
    //scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
        int l,r;
        read(a.fi);read(a.se);read(l);read(r);
		//scanf("%d%d%d%d",&a.fi,&a.se,&l,&r);
		update(1,1,n,l,r,a);
	}
	for(int i=1;i<=n;++i)
	par[i]=i,sz[i]=1;
	dfs(1,1,n);
    rep(i,1,n){
        //printf("i:%d add:%lld\n",i,add[i]);
        ans^=add[i];
    }
    ptlle(ans);
	return 0;
}
F. 序列立方(前缀和优化子序列dp)
题意

给定长度为 𝑁(N<=250) 的序列 𝑎,

小马想请你输出序列 𝑎 每个非空子序列出现次数的立方值的和,

答案对998244353取模。

题解

这基本是一个原题trick,把立方和转成取三次序列都相等,

这个trick,可以参考这个把平方和转成取两次序列都相等

如果一个子序列如果出现ai次,其贡献是ai^3

这等价于,对这个序列取三次子序列,取三次的过程中子序列两两相同的方案数,

设某个子序列出现了a次,

则在第一次里出现了a次,第二次里也出现了a次,第三次也出现了a次,

则对于该子序列来说,

第一次=第二次=第三次的方案数,为三堆里每堆任取一个的方案数,a*a*a=a^3

洛谷P1758 [NOI2009]管道取珠(dp 贡献转化)_洛谷管道取珠-CSDN博客

dp[i][j][k]表示第一个子序列选的最后一个是ai,第二个选的最后一个是aj,第三个选的最后是ak时的方案数

只有ai=aj=ak时,才能续在前面的子序列后面,

转移可以枚举x<i,y<j,z<k,dp[i][j][k]+=dp[x][y][z],

然后注意到这是一个三维前缀和,所以一边dp一边维护前缀和即可

代码
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#include<random>
#include<cstdio>
#include<algorithm>
#include<chrono>
#include<ctime>
#include<cstdlib>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=255,mod=998244353;
int n,a[N],dp[N][N][N],sum[N][N][N];
void add2(int &x,int y){
    x=(x+y)%mod;
}
int main(){
    sci(n);
    rep(i,1,n)sci(a[i]);
    dp[0][0][0]=sum[0][0][0]=1;
    rep(i,0,n){
        rep(j,0,n){
            rep(k,0,n){
                if(!i && !j && !k)continue;
                if(i && j && k && a[i]==a[j] && a[j]==a[k]){
                    add2(dp[i][j][k],sum[i-1][j-1][k-1]);
                }
                if(i-1>=0)add2(sum[i][j][k],sum[i-1][j][k]);
                if(j-1>=0)add2(sum[i][j][k],sum[i][j-1][k]);
                if(k-1>=0)add2(sum[i][j][k],sum[i][j][k-1]);
                if(j-1>=0 && k-1>=0)add2(sum[i][j][k],mod-sum[i][j-1][k-1]);
                if(i-1>=0 && k-1>=0)add2(sum[i][j][k],mod-sum[i-1][j][k-1]);
                if(i-1>=0 && j-1>=0)add2(sum[i][j][k],mod-sum[i-1][j-1][k]);
                if(i-1>=0 && j-1>=0 && k-1>=0)add2(sum[i][j][k],sum[i-1][j-1][k-1]);
                add2(sum[i][j][k],dp[i][j][k]);
            }
        }
    }
    int ans=sum[n][n][n];
    ans=(ans+mod-1)%mod;
    pte(ans);
	return 0;
}
G. 三元环(线段树三维偏序)
题意

小马给出长度为 𝑛(n<=2e5) 的正整数序列 𝑓,𝑔(fi,gi<=n),

现以如下方式生成 𝑛 个点的有向图,

试求出图中三元环的个数。

for i from 1 to n:
 for j from i+1 to n:
   if f[i] < f[j] and g[i] < g[j]: 
      add edge from i to j
   else:
     add edge from j to i

题解

发现正着做有6种情况,并不好做,考虑正难则反,

根据题意,任意两个点之间都有边,答案即任选三个点C(n,3)减去这三个点成不了三元环的方案

成不了三元环的方案,一定是一个点出度为2,指向了另外两个点

对于三个点1、2、3来说,实际是三种情况:

①1->2,1->3,这要求f[1]<f[2]且g[1]<g[2]且f[1]<f[3]且g[1]<g[3],

把(i,fi,gi)看成一个三维平面的点,

实际就是三维偏序(1,f1,g1)<(2,f2,g2)且(1,f1,g1)<(3,f3,g3)

需要统计三维都比(i,fi,gi)大的点(j,fj,gj)的个数x,然后从x个中挑两个出来

剩下两种情况也是类似,先考虑对偶,

②3->1,3->2,也就是(f[1]<f[3]与g[1]<g[3]不同时成立)且(f[2]<f[3]与g[2]<g[3]不同时成立)

那就先统计三维比(i,fi,gi)小的点(j,fj,gj)的个数y,再从总的刨除掉即可

满足i<j的个数总共有j-1个,然后从j-1-y个种挑两个出来

第三种情况,

③2->1,2->3,也就是一半是①一半是②,一个从x个挑,一个从j-1-y个中挑

所以,需要三维偏序统计出,三维都比当前点严格大/严格小的点的个数

三维偏序裸题,可以参考洛谷P3810陌上花开,树套树或者cdq分治+树


cdq分治(知识整理+板子总结)-CSDN博客

这里先cdq分治+树状数组,

统计出来三维都严格小的数量,然后对三维取反,再跑一遍,

第三维为了让取反后的下标还在[1,n]上,是采用的i=n+1-i的方式

代码
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#include<random>
#include<cstdio>
#include<algorithm>
#include<chrono>
#include<ctime>
#include<cmath>
#include<cstdlib>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back    
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10;
int n,f[N],g[N],x,y,z;
int res[N],res2[N];
ll ans; 
struct node{
	int a,b,c,ans;
	bool operator<(const node &x)const{
		return a<x.a||(a==x.a&&b<x.b)||(a==x.a&&b==x.b&&c<x.c);
	}
	bool operator==(const node &x)const{
		return a==x.a&&b==x.b&&c==x.c;
	}
}e[N],b[N];
ll C2(int x){
    return 1ll*x*(x-1)/2;
}
struct BIT{
	int n,tr[N];
	void init(int _n){
		n=_n;
		memset(tr,0,sizeof tr);
	}
	void add(int x,int v){
		for(int i=x;i<=n;i+=i&-i)
		tr[i]+=v;
	}
	int sum(int x){
		int sum=0; 
		for(int i=x;i>0;i-=i&-i)
		sum+=tr[i];
		return sum;
	}
}tr;
 
void cdq(node *a,int l,int r){
    //printf("l:%d r:%d\n",l,r);
	if(l==r)return;
	int m=(l+r)/2;
	cdq(a,l,m);
	cdq(a,m+1,r);
	int s=l,t=m+1;
	for(int i=l;i<=r;++i){
        //printf("l:%d r:%d i:%d s:%d t:%d\n",l,r,i,s,t);
		if(t>r || (s<=m && a[s].b<a[t].b)){
			tr.add(a[s].c,1);
			b[i]=a[s];
            s++;
		}
		else{
			a[t].ans+=tr.sum(a[t].c-1);
			b[i]=a[t];
            t++;
		}
	} 
    //printf("l:%d r:%d\n",l,r);
	for(int i=l;i<=m;++i)
	tr.add(a[i].c,-1);
	for(int i=l;i<=r;++i)
	a[i]=b[i];
}
int main(){
    sci(n);
    rep(i,1,n)sci(f[i]);
    rep(i,1,n){
        sci(g[i]);
		e[i].a=i;
        e[i].b=f[i];
        e[i].c=g[i];
        e[i].ans=0;
	}
    tr.init(n);
	stable_sort(e+1,e+n+1);
	cdq(e,1,n);
    rep(i,1,n){
        res[e[i].a]=e[i].ans;
        e[i].ans=0;
        e[i].a*=-1;
        e[i].b=n+1-e[i].b;
        e[i].c=n+1-e[i].c;
    }
	stable_sort(e+1,e+n+1);
	cdq(e,1,n);
    rep(i,1,n){
        res2[-e[i].a]=e[i].ans;
    }
    ans=1ll*n*(n-1)*(n-2)/6;
    rep(i,1,n){
        ans-=C2(res2[i]);
        ans-=1ll*(i-1-res[i])*res2[i];
        ans-=C2(i-1-res[i]);
    }
    ptlle(ans);
	return 0;
}

/*
1 2 3 
考虑C(n,3)减以下情况
1->2 1->3 f[1]<f[2] & g[1]<g[2] & f[1]<f[3] & g[1]<g[3] (1,f1,g1)<(2,f2,g2) (1,f1,g1)<(3,f3,g3)
2->1 2->3 (f[1]>=f[2] || g[1]>=g[2]) & f[2]<f[3] & g[2]<g[3] (2,f2,g2)<(3,f3,g3)
// 用i<2的减(i,fi,gi)<(2,f2,g2)的
3->1 3->2 (f[1]>=f[3] || g[1]>=g[3]) & (f[2]>=f[3] || g[2]>=g[3])
// 用i<3的减(i,fi,gi)<(3,f3,g3),在里面取两个
*/

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-21 04:08:01       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-21 04:08:01       101 阅读
  3. 在Django里面运行非项目文件

    2024-07-21 04:08:01       82 阅读
  4. Python语言-面向对象

    2024-07-21 04:08:01       91 阅读

热门阅读

  1. 7.20工作笔记7 写定时器+Post方式的问题

    2024-07-21 04:08:01       26 阅读
  2. 2024.7.20刷题记录

    2024-07-21 04:08:01       26 阅读
  3. 力扣题解(零钱兑换II)

    2024-07-21 04:08:01       25 阅读
  4. Python学习-九大数据类型整合,详细讲解

    2024-07-21 04:08:01       21 阅读
  5. web前端 Vue 框架面试120题(三)

    2024-07-21 04:08:01       22 阅读
  6. 【C++】位运算与相关算法问题

    2024-07-21 04:08:01       29 阅读
  7. Vue Router的路由正则表达式

    2024-07-21 04:08:01       23 阅读
  8. C++编程:实现一个跨平台安全的定时器Timer模块

    2024-07-21 04:08:01       24 阅读
  9. CSS中object-fit: cover;

    2024-07-21 04:08:01       26 阅读