区间
Solution
30分
暴力建边判可行.
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 1005
using namespace std;
struct graph{
int nxt,to;
}e[N*N];
struct inter{
int l,r;
}a[N];
int g[N],n,m,cnt;
bool v[N];
queue<int> q;
inline void addedge(int x,int y){
e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;
}
inline bool bfs(int u,int t){
memset(v,0,sizeof(v));
while(!q.empty()) q.pop();
q.push(u);v[u]=true;
while(!q.empty()){
u=q.front();q.pop();
for(int i=g[u];i;i=e[i].nxt){
if(e[i].to==t)
return true;
if(!v[e[i].to]){
v[e[i].to]=true;
q.push(e[i].to);
}
}
}
return false;
}
inline void Aireen(){
scanf("%d",&n);
for(int i=1,ty,j,k;i<=n;++i){
scanf("%d",&ty);
if(ty&1){
++m;scanf("%d%d",&a[m].l,&a[m].r);
for(int j=1;j<m;++j){
if((a[j].l<a[m].l&&a[m].l<a[j].r)\
||(a[j].l<a[m].r&&a[m].r<a[j].r))
addedge(m,j);
if((a[m].l<a[j].l&&a[j].l<a[m].r)\
||(a[m].l<a[j].r&&a[j].r<a[m].r))
addedge(j,m);
}
}
else{
scanf("%d%d",&j,&k);
if(bfs(j,k)) puts("YES");
else puts("NO");
}
}
}
int main(){
freopen("interval.in","r",stdin);
freopen("interval.out","w",stdout);
Aireen();
fclose(stdin);
fclose(stdout);
return 0;
}
100分
线段树+\(vector\).
互通的区间可以合并.
剩下不互通的区间是棵森林.
因为序列长度具有单调性,所以只需判左右端点属于哪些区间即可判互通.
调不出来
置换
Solution
100分
\(i->P_i\)建图,每个点顺序走两条边即可得到\(Q\).
\(i->Q_i\)建图,判断现在的图是否能由上面那种方式得到.
大小为奇数的环合法,大小为偶数的环需大小相等的两两合并.
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 1000005
using namespace std;
int a[N],f[N],g[N],fr[N],to[N],nxt[N],siz[N],ans[N],n;
inline int read(){
int ret=0;char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
ret=(ret<<1)+(ret<<3)+c-'0';
c=getchar();
}
return ret;
}
inline void Aireen(){
n=read();
for(int i=1;i<=n;++i){
nxt[i]=read();
if(nxt[i]>n||nxt[i]<=0){
puts("-1");return;
}
}
for(int i=1;i<=n;++i){
++fr[i];++to[nxt[i]];
}
for(int i=1;i<=n;++i)
if(fr[i]!=1||to[i]!=1){
puts("-1");return;
}
memset(fr,0,sizeof(fr));
for(int i=1;i<=n;++i)
if(!f[i]){
for(int j=i;!f[j];j=nxt[j]){
f[j]=i;++siz[i];
}
if(!(siz[i]&1)){
if(fr[siz[i]]){
g[i]=fr[siz[i]];
fr[siz[i]]=0;
}
else fr[siz[i]]=i;
}
}
for(int i=1;i<=n;++i)
if(fr[siz[i]]){
puts("-1");return;
}
for(int i=1,k,l;i<=n;++i)
if(siz[i]&1){
a[1]=i;k=3;
for(int j=nxt[i];j!=i;j=nxt[j]){
if(k>siz[i]) k-=siz[i];
a[k]=j;k+=2;
}
for(int j=1;j<siz[i];++j)
ans[a[j]]=a[j+1];
ans[a[siz[i]]]=a[1];
}
else if(g[i]){
a[1]=i;k=3;l=siz[i]<<1;
for(int j=nxt[i];j!=i;j=nxt[j]){
a[k]=j;k+=2;
}
a[2]=g[i];k=4;
for(int j=nxt[g[i]];j!=g[i];j=nxt[j]){
a[k]=j;k+=2;
}
for(int j=1;j<l;++j)
ans[a[j]]=a[j+1];
ans[a[l]]=a[1];
}
for(int i=1;i<=n;++i)
printf("%d ",ans[i]);
printf("\n");
}
int main(){
freopen("permutation.in","r",stdin);
freopen("permutation.out","w",stdout);
Aireen();
fclose(stdin);
fclose(stdout);
return 0;
}
树
Solution
prufer数列
\(prufer\)数列是无根树的一种数列一种
-
生成\(prufer\)序列的方法:
迭代删点,直到原图仅剩两个点.
对于一棵顶点已经经过编号的树\(T\),顶点的编号为\(\{1,2,\dots,n\}\).
每一步,移去所有叶子节点中标号最小的顶点和相连的边,并把与它相邻的点的编号加入\(prufer\)序列中.
重复以上步骤直到原图仅剩\(2\)个顶点. -
将\(prufer\)数列转化成树的方法
设\(\{a_1,a_2,\dots,a_{n-2}\}\)为一棵有\(n\)个节点的树的\(prufer\)序列.
另建一个集合\(G\)含有元素\(\{1,\dots,n\}\),找出集合中最小的未在\(prufer\)序列中出现过的数,将该点与\(prufer\)序列中首项连一条边,并将该点和\(prufer\)序列首项删除,重复操作\(n-2\)次,将集合中剩余的两个点之间连边即可. -
性质
一个度数为\(d\)的点在\(prufer\)数列中只会出现\(d-1\)次.
100分
这题可以利用\(prufer\)数列的性质.
一个大小为\(siz\)的树,每个点的度数为\(d_i\),
则带编号的生成树计数为:\(\large\frac{siz!}{\prod{d_i!}}\),类似组合数(组合数计数也可以).
因为过程中不知道\(siz\),所以先不\(\times{siz!}\).
\(f[i][j][k]\)表示前\(i\)个点中,选\(j\)个,\(prufer\)数列长度为\(k\)的方案数.
\(f[i][j][k]=f[i-1][j][k]+\sum_{l=0}^{a_i-1}f[i][j-1][k-l]\times\frac{1}{l!}(\)即\(1<i\)度数\(\leq{a_i})\)
\(ans=\sum_{i=1}^{i=n}{f[n][i][i-2]}\times{i!}\)
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 105
#define M 1004535809ll
using namespace std;
typedef long long ll;
int a[N],n;
ll f[N][N][N],rev[N],fac[N];
inline ll po(ll x,ll k){
ll ret=1ll;
while(k){
if(k&1ll) ret=ret*x%M;
x=x*x%M;k>>=1;
}
return ret;
}
inline void Aireen(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
fac[0]=fac[1]=1ll;
for(int i=2;i<=n;++i)
fac[i]=fac[i-1]*(ll)(i)%M;
rev[n]=po(fac[n],M-2ll);
rev[0]=rev[1]=1ll;
for(int i=n-1;i>1;--i)
rev[i]=rev[i+1]*(ll)(i+1)%M;
f[0][0][0]=1ll;
for(int i=1;i<=n;++i)
for(int j=0;j<=i;++j)
for(int k=0;k<=n-2;++k){
f[i][j][k]=f[i-1][j][k];
if(j) for(int l=min(a[i]-1,k);l>=0;--l){
f[i][j][k]=f[i][j][k]+f[i-1][j-1][k-l]*rev[l];
if(f[i][j][k]>M) f[i][j][k]%=M;
}
}
printf("%d ",n);
for(int i=2;i<=n;++i)
printf("%lld ",f[n][i][i-2]*fac[i-2]%M);
printf("\n");
}
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
Aireen();
fclose(stdin);
fclose(stdout);
return 0;
}