期望100+30+30，实际100+30+30
T1
problem
求(1 ightarrow n)的全排列中，与给出的排列构成的二叉查找树形式相同的排列个数
solution
我们发现二叉查找树中的左子树中数的相对位置不变，右子树中数的相对位置不变。
所以在排列中几组数的相对位置是不变的，但是在他们中间可以插入一些别的数，且这些数也是具有相对位置的
考虑一组具有相对位置的(m)数的位置的排列情况，就可以看成是在(n)个物品里选(m)个物品的排列组合
左右子树互不影响，根据乘法原理求出全部的方案数
code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;
int read(){
int x = 1,a = 0;char ch = getchar();
while (ch < '0'||ch > '9'){if (ch == '-') x = -1;ch = getchar();}
while (ch >= '0'&&ch <= '9'){a = a*10+ch-'0';ch = getchar();}
return x*a;
}
const int maxn = 3005,mod = 1e9+7;
int m,n;
int a[maxn],son[maxn][5];
void build(){
for (int i = 2;i <= n;i++){
for (int j = 1;j <= n;){
if (a[i] < a[j]){
if (son[j][1]) j = son[j][1];
else {son[j][1] = i;break;}
}
else{
if (son[j][2]) j = son[j][2];
else {son[j][2] = i;break;}
}
}
}
}
int siz[maxn];
void dfs1(int x){
siz[x] = 1;
if (son[x][1]) dfs1(son[x][1]);
if (son[x][2]) dfs1(son[x][2]);
siz[x] += siz[son[x][1]]+siz[son[x][2]];
}
int C[maxn][maxn];
void init(){
C[0][0] = 1;
C[1][0] = C[1][1] = 1;
for (int i = 1;i <= 2000;i++){
C[i][0] = 1;
for (int j = 1;j <= i;j++){
C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod;
}
}
}
int ans[maxn];
void dfs2(int x){
if (son[x][1]) dfs2(son[x][1]);
if (son[x][2]) dfs2(son[x][2]);
ans[x] = C[siz[son[x][1]]+siz[son[x][2]]][siz[son[x][1]]]%mod*ans[son[x][1]]%mod*ans[son[x][2]]%mod;
}
signed main(){
freopen("bst.in","r",stdin);
freopen("bst.out","w",stdout);
m = read();
init();
for (int i = 1;i <= m;i++){
n = read();
memset(son,0,sizeof(son));
for (int j = 1;j <= n;j++) a[j] = read(),ans[j] = 1;
ans[0] = 1;
build();dfs1(1);
dfs2(1);
printf("%lld
",ans[1]-1);
}
return 0;
}
T3
solution
正解，线段树合并？？？这是个啥，并不会做。暴力30分，把所有能走到的点记录下来，最后统一统计一下颜色出现的次数
code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;
int read(){
int x = 1,a = 0;char ch = getchar();
while (ch < '0'||ch > '9'){if (ch == '-') x = -1;ch = getchar();}
while (ch >= '0'&&ch <= '9'){a = a*10+ch-'0';ch = getchar();}
return x*a;
}
const int maxn = 1e4+10;
int n,m,op,tmp;
int c[maxn];
struct node{
int to,nxt,w;
}ed[maxn*2];
int head[maxn],tot;
void add(int u,int to,int w){
ed[++tot].to = to;
ed[tot].nxt = head[u];
ed[tot].w = w;
head[u] = tot;
}
int top;
int vis[maxn],col[maxn],st[maxn];
void dfs(int x,int k){
if (vis[x]) return;
vis[x] = 1;st[++top] = x;
for (int i = head[x];i;i = ed[i].nxt){
int to = ed[i].to;
if (ed[i].w > k) continue;
dfs(to,k);
}
}
signed main(){
freopen("garden.in","r",stdin);
freopen("garden.out","w",stdout);
n = read(),m = read(),op = read();
for (int i = 1;i <= n;i++) c[i] = read();
for (int i = 1;i <= m;i++){
int x = read(),y = read(),w = read();
add(x,y,w),add(y,x,w);
}
int q = read(),lst = 0;
for (int i = 1;i <= q;i++){
memset(st,0,sizeof(st));
memset(col,0,sizeof(col));
memset(vis,0,sizeof(vis));
int a = read(),b = read();
if (op == 2) a ^= lst,b ^= lst;
// cout<<a<<" "<<b<<endl;
top = 0;tmp = 0;
dfs(a,b);
for (int j = 1;j <= top;j++){
// cout<<st[j]<<" ";
col[c[st[j]]]++;
if (col[tmp] < col[c[st[j]]]||(col[tmp] == col[c[st[j]]]&&tmp > c[st[j]])) tmp = c[st[j]];
}
// cout<<endl;
lst = tmp;
printf("%lld
",lst);
}
return 0;
}
T4
solution
继续暴力，能走就连边，查询暴力dfs看是否联通
code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;
int read(){
int x = 1,a = 0;char ch = getchar();
while (ch < '0'||ch > '9'){if (ch == '-') x = -1;ch = getchar();}
while (ch >= '0'&&ch <= '9'){a = a*10+ch-'0';ch = getchar();}
return x*a;
}
const int maxn = 1e6+10;
int n,cnt;
int fa[maxn];
struct node{
int x,y;
}a[maxn];
struct edge{
int to,nxt;
}ed[maxn];
int head[maxn],tot;
void add(int u,int to){
ed[++tot].to = to;
ed[tot].nxt = head[u];
head[u] = tot;
}
int vis[maxn];
void dfs(int x){
if (vis[x]) return;
vis[x] = 1;
for (int i = head[x];i;i = ed[i].nxt){
int to = ed[i].to;
dfs(to);
}
}
signed main(){
freopen("interval.in","r",stdin);
freopen("interval.out","w",stdout);
n = read();
for (int i = 1;i <= n;i++){
int op = read();
if (op == 1){
a[++cnt].x = read(),a[cnt].y = read();
for (int j = cnt-1;j >= 1;j--){
if ((a[j].x > a[cnt].x&&a[j].x < a[cnt].y)||(a[j].y > a[cnt].x&&a[j].y < a[cnt].y)){
add(j,cnt);
}
if ((a[cnt].x > a[j].x&&a[cnt].x < a[j].y)||(a[cnt].y > a[j].x&&a[cnt].y < a[j].y)){
add(cnt,j);
}
}
}
if (op == 2){
memset(vis,0,sizeof(vis));
int x = read(),y = read();
dfs(x);
if (vis[y]) printf("YES
");
else printf("NO
");
}
}
return 0;
}