题目名称排列树字胡串有环无向图
提交文件名tree.cppstring.cppgraph.cpp
输入文件名tree.instring.ingraph.in
输出文件名tree.outstring.outgraph.out
时间限制1s 1s 1s
空间限制64MB128MB256MB
题目类型传统传统传统

注意事项:

  1. 数据较大,注意使用读入优化。
  2. 题目难度与题目顺序无关。
  3. 编译不打开 O2 优化。

1 排列树

1.1 description

小 C 最近喜欢上了树据结构。树据结构是由 n 个点组成的结构,每个点都有一个 1 ~ n 之中的标号,且保证 n 个点的标号形成一个 1 ~ n 的排列,其中有一个点为这个树据结构的根节点,其余 n-1 个点在树据结构中都有唯一的父亲。而且由于树据结构的特殊性质,这些父亲的关系并不会形成一个环。
小 C 发现了一种特别优美的树据结构,满足对于所有存在父亲的点,都满足父亲的标号小等于这个点的标号,小 C 把这种树据结构称作“排列树”。小 C 很快就发现了,n 个点的树据结构,排列树有 (n-1)! 个,不过现在小 C 想知道,在树据结构的形态一定时,排列树一共有多少个。
一句话题意:给你一棵以 1 号点为根的树,现在你要给每个点分配一个 1 ~ n 的标号,使得父节点的标号小于子节点的标号,问一共有多少种方案,你只需要输出在 mod 19260817 意义下的方案数即可。

1.2 input

第一行一个数 n。
接下来 n-1 行,每行两个数 ai,bi,表示树中存在 (ai,bi) 这条边。

1.3 output

输出一个数,表示合法的方案数。

1.4 sample input

4
1 3
3 2
1 4

1.5 sample output

3

1.6 data range

对于 20 % 的数据,n ≤ 10。
对于 50 % 的数据,n ≤ 200。
对于 70 % 的数据,n ≤ 3000。
对于 100% 的数据,n ≤10^5 。

分析

20 分

搜索或者状压 DP。
搜索只需要搜出全排列,然后遍历树,判断是否合理就可以了。
时间复杂度:O(N!)。
蒟蒻状压不会!

#include<bits/stdc++.h>
#define reg register int
using namespace std;
inline int ri()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return f*x;
}
const int maxn=3010;
int n,cnt,ans;
int h[maxn],tre[maxn],vis[maxn];
struct node{
	int next,to;
}edg[maxn*2];
inline void add(int u,int v)
{
	edg[++cnt].next=h[u];
	edg[cnt].to=v;
	h[u]=cnt;
	return;
}
inline bool check(int u,int fa)
{
	int f=1;
	if(tre[fa]>=tre[u]) return false;
	for(reg i=h[u];i;i=edg[i].next)
	{
		int v=edg[i].to;
		if(v==fa) continue;
		if(!check(v,u)) f=0;
	}
	return f;
}
inline void dfs(int x)
{
	if(x==n+1)
	{
		if(check(1,0)) ans++;
		return;
	}
	for(reg i=1;i<=n;++i)
	{
		if(vis[i]) continue;
		vis[i]=1;tre[x]=i;
		dfs(x+1);
		tre[x]=0;vis[i]=0;
	}
	return;
}
int main()
{
	n=ri();
	for(reg i=1,a,b;i<n;++i)
	{
		a=ri();b=ri();
		add(a,b);add(b,a);
	}
	dfs(1);
	printf("%d",ans);
	return 0;
}

100 分

记 size 表示 i 号点的子树大小,g[i] 表示以 i 为根的子树分配 size 个标号的方案数。
g[i] 可以用所有儿子的方案数乘起来得到,这样儿子内部的标号是一定的。不过注意儿子之间的标号不一定,还要先给每个儿子分配标号,我们用组合数来分配一下即可。
时间复杂度 O(n)。
具体的,我们如何求g[i]呢?
大家可以画画图,这里以二叉树举例
会发现

其中: k为父亲节点,i,j为子树,(假设size[i]>size[j])。
但如果是多叉树呢?如何将多叉树合并为二叉树?
这里有一个小技巧:
我们用dfs遍历树,这样在回溯时,将父亲节点作为第一棵子树,然后邻接表遍历子树,合并子树。同时还可以顺便求出size数组。
组合数用逆元求一下就可以了。(蒟蒻是不会承认调逆元调了2个小时

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
#define reg register ll
#define in inline
using namespace std;
const ll maxn=100010,mod=998244353;
in ll ri()
{
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();}
	return f*x;
}
ll n,cnt;
ll h[maxn],g[maxn],size[maxn],fac[maxn];
struct node{
	ll next,to;
}edg[maxn*2];
in void add(ll u,ll v)
{
	edg[++cnt].next=h[u];
	edg[cnt].to=v;
	h[u]=cnt;
	return;
}
in ll ksm(ll a,ll b,ll p)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%p;
		a=a*a%p;
		b>>=1;
	}
	return ans%p;
}
in ll inv(ll a,ll p) {return ksm(a,p-2,p);}
in ll C(ll a,ll b) {return fac[a]*inv(fac[b],mod)%mod*inv(fac[a-b],mod)%mod;}
in void dfs(ll u,ll fa)
{
	g[u]=1;
	for(reg i=h[u];i;i=edg[i].next)
	{
		ll v=edg[i].to;
		if(v==fa) continue;
		dfs(v,u);
		g[u]=(g[u]*g[v])%mod*C(size[u]+size[v],size[v])%mod;
		size[u]+=size[v];
	}
	size[u]++;
	return;
}
int main()
{
	n=ri();
	for(reg i=1,a,b;i<n;++i)
	{
		a=ri();b=ri();add(a,b);add(b,a);
	}
	fac[0]=1;for(reg i=1;i<=n;++i) fac[i]=fac[i-1]*i%mod;
	dfs(1,0);
	printf("%lld",g[1]);
	return 0;
}

2 字胡串

2.1 description

小 Z 最近喜欢上了字胡串。字胡串是一个由数字拼接而成的序列。具体的,用 S 来表示一个字胡串,Si 表示这个字胡串的第 i 位,Sl,r(1 ≤ l ≤ r ≤ n) 表示这个字胡串的一个子串,这个子串是由 Sl,Sl+1,…,Sr 依次拼接而成的一个字胡串。
小 Z 自己定义了一个函数 f(S),其中:


他还定义了一个函数 g(S),其中:

现在小 Z 想要问你,对于给定的字胡串 S,有多少个子串 T,满足 g(T) > f(T)。

2.2 input

第一行一个整数 n。
接下来一行 n 个整数,第 i 个数表示 Si。

2.3 output

输出一个数,表示满足条件的子串的个数。

2.4 sample input 1

5
3 2 1 6 5

2.5 sample output 1

8

2.6 sample input 2

4
3 3 3 3

2.7 sample output 2

0

2.8 data range

对于 20 % 的数据,n ≤ 300。
对于 50 % 的数据,n ≤ 3000。
对于 80 % 的数据,n ≤ 10^5。
对于 100 % 的数据,n ≤ 10^6,Si ≤ 10^9。

题解

50分

直接 O(n ^2 ) 枚举区间,O(1) 判断是否合法即可。
具体的,对于RMQ问题,使用ST表可以实现快速静态查询。
然后很明显G(S)仍然可以使用ST表维护。
对于G(S)的查询,由于X|X=X ,可以证明查询是正确的。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define reg register int
using namespace std;
const  int maxn=100010;
inline int rl()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return f*x;
}
int n,ans;
int f[maxn][30],g[maxn][30];
inline int askg(int i,int j)
{
	int k=(int)((double)log(j-i+1)/log(2.0));
	return g[i][k]|g[j+1-(1<<k)][k];
}
inline int askf(int i,int j)
{
	int k=(int)((double)log(j-i+1)/log(2.0));
	return max(f[i][k],f[j+1-(1<<k)][k]);
}
int main()
{
	n=rl();
	for(reg i=1;i<=n;++i) g[i][0]=f[i][0]=rl();
	for(reg j=1;(1<<j)<=n;++j)
	for(reg i=1;i+(1<<j)-1<=n;++i)
	{
		g[i][j]=g[i][j-1]|g[i+(1<<(j-1))][j-1];
		f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	}
	for(reg i=1;i<=n;++i)
	for(reg j=i;j<=n;++j) if(askg(i,j)>askf(i,j)) ans++;
	printf("%d",ans);
	return 0;
}

100 分

考虑一个区间,只要这个区间的任意值非最大值有一位不与最大值相同,那么这个区间就是合法区间。
找出所有值左右第一个大于它的位置,那么以它为最大值的区间就固定在这一段中。只要再找出这个区间中左右第一个有一位不与最大值相同的值的位置,那么这个位置左边的所有位置都可以与最大值右边的位置构成一个合法区间。右边也同理。
具体的,可以用单调栈找出左右第一个大于它的位置,再用 O(n log Si) 的时间处理出左右第一个有有某一位为当前数超集的地方,然后就可以 O(n) 统计答案了,注意处理值相同的情况。
时间复杂度 O(n log Si)。

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    char ch=getchar();int i=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){i=(i<<1)+(i<<3)+ch-'0';ch=getchar();}
    return i*f;
}
const int N=1e6+50;
int n,a[N],l[N],r[N],st[N],pos[N],top,diff_l[N],diff_r[N],mx[35];
int mxpos[35];

int main(){
    n=read(); 
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++){
        while(top&&st[top]<=a[i])top--;
        l[i]=pos[top]+1;
        st[++top]=a[i];pos[top]=i;
    }
    top=0; pos[top]=n+1;
    for(int i=n;i>=1;i--){
        while(top&&st[top]<a[i]) top--;
        r[i]=pos[top]-1;
        st[++top]=a[i];pos[top]=i;
    }
    for(int i=1;i<=n;i++){
        int p=0;
        for(int j=0;(1ll<<j)<=a[i];j++){
            if((1ll<<j)&a[i])mx[j]=max(mx[j],i);
            else p=max(p,mx[j]);
        }
        diff_l[i]=p;
    }
    fill(mx,mx+32+1,n+1);
    for(int i=n;i>=1;i--) {
        int p=n+1;
        for(int j=0;(1ll<<j)<=a[i];j++) {
            if((1ll<<j)&a[i]) mx[j]=min(mx[j],i);
            else p=min(p,mx[j]);
        }
        diff_r[i]=p;
    }
    long long ans=0;
    for(int i=1;i<=n;i++) {
        if(diff_l[i]>=l[i])
            ans+=1ll*(diff_l[i]-l[i]+1)*(r[i]-i+1);
        if(diff_r[i]<=r[i])
            ans+=1ll*(r[i]-diff_r[i]+1)*(i-l[i]+1);
        if(diff_l[i]>=l[i]&&diff_r[i]<=r[i])
            ans-=1ll*(r[i]-diff_r[i]+1)*(diff_l[i]-l[i]+1);
    }
    cout<<ans<<endl;
}

3 有环无向图

3.1 description

小 L 最近喜欢上了图论,他最近在着重研究一类图,叫做有环无向图。有环无向图是由 n 个 点,m 条边组成的无向联通图。且图中可能存在环,但不可能存在重边或自环。
小 L 对这个图上的最短路问题产生了兴趣,于是他花了 3 分钟时间学习了 SFPA 算法。他觉 得,这个最短路实在是太 Naiive 了!他决定对这个图改造一下。改造后,小 L 规定了对于一条路 径的权值为经过所有点的代价,其中起点的代价为起点的代价是离开起点的边的边权,终点的代 价是进入终点的边的边权,途中经过的点的代价是进入和离开这个点的两条边的边权的较大值。
小 L 赶紧用 SFPA 算法水过了这道题(当然,他是不会告诉你 SFPA 算法是怎么做的),之 后他找到了你,想要看看你有没有比他高明一些的方法能够求出从 1 号点到 n 号点的最短路。

3.2 input

第一行两个数 n, m。 接下来 m 行,每行三个数 ai , bi , ci,表示 ai 和 bi 之间存在一条长度为 ci 的边。

3.3 output

输出一个数,表示 1 号点到 n 号点的最短路长度。

3.4 sample input

4 5
3 4 8
2 3 1
1 3 2
1 2 5
2 4 4

3.5 sample output

12

3.6 data range

对于 30 % 的数据,n ≤ m ≤ 3000。
对于 100 % 的数据,n ≤ m ≤ 2 ∗ 105,ci ≤ 109。

题解

30 分

对于每个点可以 建图,然后跑最短路,时间复杂度

100 分

考虑优化边数。对于一个点,先把出入边按权值排序,入边连向他的反向边,每个反向边往下连长度为 0 的边,向上连长度为两边差值的边,边数优化到了 O(m)。时间复杂度 O((n+m)log n)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pii;
inline int read(){
    char ch=getchar();int i=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){i=(i<<1)+(i<<3)+ch-'0';ch=getchar();}
    return i*f;
}
const int Maxn=2e5+50,Maxm=4e5+50;
int n,m,nxt[Maxm],to[Maxm],val[Maxm],last[Maxn],ecnt=1,vis[Maxm],tot;
vector<pii>edge[Maxm];
struct E{
    int id,val;
    E(){}
    E(int x,int z):id(x),val(z){} 
    friend inline bool operator <(const E &a,const E &b){
        return a.val<b.val;
    }
}que[Maxm];
long long dis[Maxm];
inline void add(int x,int y,int w){
    nxt[++ecnt]=last[x];last[x]=ecnt;to[ecnt]=y;val[ecnt]=w;
}
priority_queue< pii,vector<pii>,greater<pii> >q;
inline void dij(){
    for(int i=2;i<=ecnt;i++) dis[i]=2e18;
    for(int e=last[1];e;e=nxt[e]){
        dis[e]=val[e];q.push(make_pair(dis[e],e));
    }
    while(!q.empty()){
        if(vis[q.top().second]){q.pop();continue;}
        int u=q.top().second;q.pop();vis[u]=1;
        for(int e=edge[u].size()-1;e>=0;e--){ 
            int v=edge[u][e].first,w=edge[u][e].second;
            if(vis[v])continue;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push(make_pair(dis[v],v));
            }
        }
    }
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int x=read(),y=read(),w=read();
        add(x,y,w);add(y,x,w);
    }
    for(int i=2,tp=0;i<n;tp=0,i++){
        for(int e=last[i];e;e=nxt[e])
            que[++tp]=E(e,val[e]);
        sort(que+1,que+tp+1);
        for(int j=1;j<=tp;j++){
            if(j!=1)edge[que[j].id].push_back(make_pair(que[j-1].id,0));
            if(j!=tp)edge[que[j].id].push_back(make_pair(que[j+1].id,que[j+1].val-que[j].val));
            edge[que[j].id^1].push_back(make_pair(que[j].id,que[j].val));
        }
    }
    dij();
    long long ans=2e18;
    for(int e=last[n];e;e=nxt[e])
        ans=min(ans,dis[e^1]+val[e]);
    cout<<ans<<endl;
}

3 对 “CCF 全国信息学奥林匹克联赛 (NOIP2019)复赛模拟 提高组 第一试”的想法;

  1. Good day! pengkunkun.com

    We advance

    Sending your commercial offer through the feedback form which can be found on the sites in the Communication section. Feedback forms are filled in by our application and the captcha is solved. The advantage of this method is that messages sent through feedback forms are whitelisted. This technique improve the odds that your message will be open.

    Our database contains more than 25 million sites around the world to which we can send your message.

    The cost of one million messages 49 USD

    FREE TEST mailing of 50,000 messages to any country of your choice.

    This message is automatically generated to use our contacts for communication.

    Contact us.
    Telegram – @FeedbackFormEU
    Skype FeedbackForm2019
    Email – FeedbackForm@make-success.com
    WhatsApp – +44 7598 509161

发表评论

电子邮件地址不会被公开。