Noip2016 校内训练 Round 1

tonyfang posted @ 2016年11月05日 14:42 in 随笔 with tags c++ OI , 908 阅读

1. 信息传递

AKP和WWF住在河的两岸,他们在河的两岸都建了n座房子,而且恰巧都是正对着建的,如下所示:

AKP:  房子1                       房子2                 房子3                    房子4

=================河===============流==============

WWF:  房子3                    房子2                 房子4                     房子1

他们对于房子的编号不一样,可能AKP的房子1对应着WWF的房子3,等等,但是每个人的房子编号都是1~n的一个排列。为了方便,我们假定他们房子间隔相同。

他们在河中铺下了光缆来连接各自相同编号的房子,进行信息传递。为了信息传递的方便,他们需要知道:从总共n条光缆中选出最多的光缆,使得这几条光缆之间两两相交。

【题解】

转化为最长下降子序列后用$O(nlogn)$的方法解决。

 

# include <stdio.h>
# include <algorithm>
// # include <bits/stdc++.h>
 
using namespace std;

const int M = 200010;
int n;
int A[M], B[M];
int ta[M], tb[M], a[M], f[M], c[M];

int main() {
 
 	freopen("message.in", "r", stdin);
 	freopen("message.out", "w", stdout);
 	
    scanf("%d", &n);
     
    for (int i=1; i<=n; ++i)
        scanf("%d", &A[i]), ta[A[i]] = i;
     
    for (int i=1; i<=n; ++i)
        scanf("%d", &B[i]), tb[B[i]] = i;
         
    for (int i=1; i<=n; ++i)
        a[i] = tb[A[i]]; 

    int ans;
    f[1] = 1, ans = 1;
    c[1] = 1;
    a[n+1] = -2147483647; for (int i=2; i<=n; ++i) c[i] = n+1;
    for (int i=2; i<=n; ++i) {
        int l=1, r=ans, anst = 0;
        while(1) {
            if(r-l<=3) {
                for (int j=r; j>=l; --j)
                    if (a[c[j]] > a[i]) {
                        anst = c[j];
                        break;
                    }
                break;
            }
            int mid = l+r>>1;
            if(a[c[mid]] > a[i]) l = mid;
            else r = mid;
        }
        f[i] = f[anst] + 1;
        if(a[c[f[i]]] < a[i])
            c[f[i]] = i;
        ans = max(ans, f[i]);
    } 
     
    printf("%d\n", ans);
     
    return 0;
}

2. 树上问题

AKP觉得WWF对树上的问题不大熟悉,于是向他提出了一个树上的问题。

首先AKP画出了一个n个节点的有根树(其中根为1号点),他对于其中一些节点很喜爱,于是就在这个节点上标记一下,当然过一会儿他可能就忘了他标记过的节点,所以一个节点可以被重复标记。在最开始,有且仅有1号节点上有标记

AKP有q次操作,操作类型有两种:

1. 选取一个点,把它标记一下。

2. 选取一个点,询问它的祖先中(包括自己),离它最近的被标记过的节点是哪一个。

现在,AKP要请你对于每一个2操作,输出你计算出的答案。

$n,q \leq 1500000$

【题解】

离线询问逆序做,并查集维护即可。

 

# include <stdio.h>
// # include <bits/stdc++.h>

using namespace std;

const int N = 2000010;
int n, q;
int opt[N], x[N];
int fa[N], f[N];
int tot = 0, next[N<<1], head[N], to[N<<1], tag[N];
int ans[N], an = 0;

int read() {
    int n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' ||  a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a >= '0' && a <= '9') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}

inline int getf(int x) {
	return x == fa[x] ? x : fa[x] = getf(fa[x]);
}

inline void add(int u, int v) {
	++tot;
	next[tot] = head[u];
	head[u] = tot;
	to[tot] = v;
}

inline void dfs(int x, int father=0) {
	if(father) f[x] = father;
	for (int i=head[x]; i; i=next[i]) 
		if(to[i] != father) 
			dfs(to[i], x);
}

int main() {
	
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
	
	n = read(), q = read();
	for (int i=1, u, v; i<n; ++i) {
		u = read(), v = read();
		add(u, v);
		add(v, u);
	}
	
	dfs(1);
	
	tag[1] = 1;
	for (int i=1; i<=n; ++i) fa[i] = i;
	
	for (int i=q; i>=1; --i) {
		opt[i] = read(), x[i] = read();
		if(opt[i] == 1) tag[x[i]]++;
	}
	
	for (int i=2; i<=n; ++i) {
		if(tag[i] != 0) continue;
		int fu = getf(i), fv = getf(f[i]);
		if(fu != fv) fa[fu] = fv;
	}
	
	for (int i=1; i<=q; ++i) {
		if(opt[i] == 1) {
			tag[x[i]] --;
			if(tag[x[i]] == 0) {
				int fu = getf(x[i]), fv = getf(f[x[i]]);
				if(fu != fv) fa[fu] = fv;
			}
		} else {
			ans[++an] = getf(x[i]);
		}
	}
	
	for (int i=an; i>=1; --i) printf("%d\n", ans[i]);
	
	return 0;
}

3. 对抗比赛

AKP和WWF要进行一场对抗比赛。

AKP有n名记者,WWF也有n名记者,他们要比赛谁跑得快。AKP的每名记者有速度值,WWF的每名记者有速度值。记者们一共进行n轮比赛,每轮AKP选出一名记者,WWF选出一名记者进行比赛,速度值大的记者所在的一方获得一轮的胜利,胜利的一方获得1分,失败的一方不获得分数,一名记者只能比赛一次。在n轮比赛过后,AKP想知道,如果他和WWF的分差(取绝对值)在之间的话,那么一共有多少种方案?由于AKP好学,所以他一共问了q次问题。

方案数对于998244353取模。

$n,q \leq 3000$。

【题解】

首先,$f_{i,j}$表示到了第i个,AKP一定得了j分(其他可得可不得)的方案。

那么令$g_i$表示AKP得到至少i分的方案,$g_i = f_{n,i} \times (n-i)!$

令$h_i$表示AKP恰好得到$i$分的方案,$h_i = g_i - C_{j}^{i} \times \sum_{j>i}h_j$。

逆推即可。复杂度$O(n^2+qn)$。

# include <stdio.h>
# include <algorithm>
 
using namespace std;
 
const int M = 3010;
int n, a[M], b[M], q, f[M][M], hv[M], g[M], h[M];
const int mod = 998244353;
 
int fac[M], inv[M];
 
inline int pwr(int x, int y) {
    int ret = 1;
    while(y) {
        if(y&1) ret = 1ll * ret*x % mod;
        x = 1ll * x*x % mod;
        y = y/2;
    }
    return ret;
}

inline void cadd(int &a, int b) {
    a = (a+b) % mod;
    a = (a+mod) % mod;
}
 
inline void csub(int &a, int b) {
    b = -b;
    b = (b+mod) % mod;
    cadd(a, b);
}
 
inline int C(int n, int k) {
    return 1ll * fac[n] * inv[k] % mod * inv[n-k] % mod;
}
 
int main() {
	
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	
    scanf("%d%d", &n, &q);
    fac[0] = 1;
    for (int i=1; i<=n; ++i)
        fac[i] = 1ll * fac[i-1] * i % mod;     
    for (int i=0; i<=n; ++i)
        inv[i] = pwr(fac[i], mod-2);
      
    for (int i=1; i<=n; ++i) scanf("%d", &a[i]);
    for (int i=1; i<=n; ++i) scanf("%d", &b[i]);
    sort(a+1, a+n+1);
    sort(b+1, b+n+1);
    for (int i=1; i<=n; ++i) hv[i] = upper_bound(b+1, b+n+1, a[i]) - b - 1;
    
    f[0][0] = 1;
    for (int i=1; i<=n; ++i)
        for (int j=0; j<=i; ++j) {
            f[i][j] = f[i-1][j];
            if(j!=0 && hv[i]-(j-1)>0) cadd(f[i][j], 1ll * f[i-1][j-1] * (hv[i]-(j-1)) % mod);
        }
     
    for (int i=0; i<=n; ++i)
        g[i] = 1ll * f[n][i] * fac[n-i] % mod;
    //for (int i=0; i<=n; ++i) cerr<<i<<":"<<f[n][i]<<"\n";
    for (int i=n; i>=0; --i) {
        h[i] = g[i];
        for (int j=i+1; j<=n; ++j)
            csub(h[i], 1ll * h[j] * C(j, i) % mod);
    }
	
	for (int i=1, L, R; i<=q; ++i) {
		int ans = 0;
		scanf("%d%d", &L, &R);
		/*
		for (int j=L; j<=R; ++j) {
			if((n+j)&1) continue;
			int A = (n+j)/2, B = (n-j)/2;
			if(A!=B) cadd(ans, (1ll * h[A] + h[B]) % mod);
			else cadd(ans, 1ll * h[A] % mod);
		}
		*/
		for (int j=0; j<=n; ++j) {
			int k = n-j;
			if(abs(j-k)>=L && abs(j-k)<=R)
				cadd(ans, h[j]);
		}
		printf("%d\n", ans);
	}
    
    return 0; 

} 

 

25penny.com 说:
2023年4月19日 16:38

During your visit to our website, we may collect more information without directly identifying you. The website does collect personal information such as your name, identify, gender, and geographic region. 25penny.com During your visit to our website, we may collect more information without directly identifyirmation such as your name, identify, gender, and geographic region.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter