T20200603

Posted on 2020-06-03 Edited on 2026-03-02 In OI Word count in article: 3.1k Reading time ≈ 11 mins.

大东辰的测试

1、种树（trees. cpp/1S/128M）

【问题描述】

一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成$n$块，并被编号为 $1„n$。每个块的大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个号码 $b,e,t$。这三个数表示该居民想在 $b$ 和 $e$ 之间最少种 $t$ 棵树。当然，$b\le e$，居民必须保证在指定地区不能种多于地区被分割成块数的树，即要求 $t\le e-b+1$，允许居民想种树的各自区域可以交叉。出于资金短缺的原因，环保部门请你求出能够满足所有居民的要求，需要种树的最少数量。

【文件输入】 第一行为 $n$，表示区域的个数；第二行为 $h$，表示房子的数目；下面 $h$ 行描述居民的需要：$b\;e\;t\left(0<b\le e \le 30000, r \le e-b+l\right)$分别用一个空格分开

【文件输出】 输出为满足所有要求的最少树的数量。

样例输入	样例输出
9 4 1 4 2 4 6 2 8 9 2 3 5 2	5

【数据规模】

$30\%$的数据满足$0<n\le 1000$, $0 < h \le 500$;

$100\%$的数据满足$n \le 30000$, $h \le 5000$;

怎么做？

贪心 + 线段树维护

其实数据水， $N^2$也可以$AC$

就是要注意排序的顺序

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 3e4 + 10;
int N, H;
int Sum[Maxn << 2], Tag[Maxn << 2];

struct Node
{
    int B, E, T;
    bool operator < (const Node &Temp) const
    {
        if (E == Temp.E) return T < Temp.T;
        return E < Temp.E;
    } 
}P[Maxn];//需求

inline void PushUp(int X){Sum[X] = Sum[X << 1] + Sum[X << 1 | 1];}

inline void F(int L, int R, int X)
{
    Sum[X] = (R - L + 1);
    Tag[X] = 1;
}

inline void PushDown(int L, int R, int X)
{
    if (!Tag[X]) return ;
    int Mid = (L + R) >> 1;
    F(L, Mid, X << 1);
    F(Mid + 1, R, X << 1 | 1);
    Tag[X] = 0;
}

void UpDate(int L, int R, int Tl, int Tr, int X = 1)
{
    if (L >= Tl && R <= Tr) 
    {
        Sum[X] = R - L + 1;
        Tag[X] = 1;
        return ;
    }
    PushDown(L, R, X);
    int Mid = (L + R) >> 1;
    if (Tl <= Mid) UpDate(L, Mid, Tl, Tr, X << 1);
    if (Tr > Mid) UpDate(Mid + 1, R, Tl, Tr, X << 1 | 1);
    PushUp(X);
}

int Query(int L, int R, int Tl, int Tr, int X = 1)
{
    if (L >= Tl && R <= Tr) return Sum[X];
    int Mid = (L + R) >> 1, Ans(0);
    PushDown(L, R, X);
    if (Tl <= Mid) Ans += Query(L, Mid, Tl, Tr, X << 1);
    if (Tr > Mid) Ans += Query(Mid + 1, R, Tl, Tr, X << 1 | 1);
    return Ans;
}

inline int Get(int TL, int TR, int T)
{
    int L(TL), R(TR), Ans(TL);
    while (L <= R)
    {
        int Mid = (L + R) >> 1, S = ((Mid - 1) < TL ? 0 : Query(1, N, TL, Mid - 1));
        if (S + TR - Mid + 1 >= T) Ans = Mid, L = Mid + 1;
        else R = Mid - 1;
    }
    return Ans;
}

int main()
{
    // freopen ("trees.in", "r", stdin);
    // freopen ("trees.out", "w", stdout);

    scanf ("%d %d", &N, &H);
    for (int i = 0; i < H; ++i) 
        scanf ("%d %d %d", &P[i].B, &P[i].E, &P[i].T);  

    sort (P, P + H);

    for (int i = 0; i < H; ++i)
    {
        int Num = Query(1, N, P[i].B, P[i].E);
        if (Num >= P[i].T) continue;
        int Place = Get(P[i].B, P[i].E, P[i].T);
        UpDate(1, N, Place, P[i].E);
    }

    printf ("%d\n", Sum[1]);
}

2.高一学堂 (at. cpp/1S/256M)

【问题描述】

在美丽的东辰中学里面，有一座高一学堂。所谓山不在高，有仙则名；水不

在深，有龙则灵。高一学堂，因为有了 $YJYX$，就成了现在这个样子 = =。

由于 $YJYX$ 的语言太过雷人，每次他发微往往都会有一石激起千层浪的效果，

具体就是所有关注他的人都会转发，同时$@$他，接着关注这些人的人也会转

发，同时$@$他关注的人（注意转发内容本身会有$@YJYX$），以此类推。这样导致每

次 llj 发微博都会被$@$上兆次，而 $llj$ 又特别喜欢发，$sina$ 支持不了如此庞大的数

据量，特出规定，每次转发时，$@$的人不能超过 $K$ 人，好友在转发时如果超过

了，就把最早那人删掉。现在 $YJYX$ 刚发了一条微博“求$AK$”，他想知道每个与

他有联系的人分别会被$@$多少次。

【输入】

输入第一行有三个整数$,N,K,$表示人数和 $K$。

接下来 $N-1$ 行，每行有 $2$ 个整数 $a，b，$表示 $a$ 和 $b$ 有关注关系。

输入给出一棵以 $1$ 号点为根的树，一号点代表 $YJYX$，对于任意一个点，他的

儿子都关注他。

【输出】

输出有 $N$ 行，每行有一个整数，这个人会被$@$多少次。

样例输入	样例输出
5 2 1 2 2 3 2 4 4 5	3 3 0 1 0

【数据规模】

对于 $30\%$的数据，$N≤100$；

对于 $60\%$的数据，$N≤2000，k≤100$；

对于 $100\%$的数据，$N≤100000$。

倍增 + 树上差分一下即可

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 1e5 + 10;
int N, K, U, V, Cur;
int Sum[Maxn], Val[Maxn], CF[Maxn], F[Maxn][20];
int Head[Maxn], Next[Maxn << 1], E[Maxn << 1];

int DFS(int X, int Fa)
{
    F[X][0] = Fa; CF[Fa]++;
    for (int i = 1; i <= 19; ++i) F[X][i] = F[F[X][i - 1]][i - 1];
    
    int TO = X, TK = K;
    for (int i = 0; TK; ++i)
        if (TK & (1 << i)) 
        {
            TK ^= (1 << i);
            TO = F[TO][i];
        }
    CF[F[TO][0]]--;

    for (int i = Head[X]; i; i = Next[i])
    {
        if (E[i] ==  Fa) continue;
        DFS (E[i], X);
        CF[X] += CF[E[i]];
    }
}

inline void AddEdge(int U, int V)
{
    Next[++Cur] = Head[U];
    Head[U] = Cur;
    E[Cur] = V;
}

inline int Read()
{
    int X(0), O(getchar());
    while (O < '0' || O > '9') O = getchar();
    for (; O >= '0' && O <= '9'; O = getchar()) X = (X << 1) + (X << 3) + (O ^ 48);
    return X;
}

int main()
{
    freopen ("at.in", "r", stdin);
    freopen ("at.out", "w", stdout);

    N = Read(), K = Read();
    for (int i = 1; i < N; ++i) 
    {
        U = Read(), V = Read();
        AddEdge(U, V), AddEdge(V, U);
    }

    DFS(1, 0);

    for (int i = 1; i <= N; ++i) printf ("%d\n", CF[i]);
}

3.高二学堂 (poker.cpp/1S/256M)

【问题描述】

在美丽的东辰中学里，有座高二学堂，同样也是因为一个人，让它们变成了

现在这个样子~那就是我们伟大的级主任。

因为他，我们又迎来了一个木有电影，只有对答案的段考日；又迎来了一个

不是大礼拜，而是小礼拜的周末。因为是小礼拜，同学们都不回家，所以干脆就

回到宿舍去玩牌了。而由于三国杀太$ out $了，所以现在他们都玩四国杀。

四国杀（说白了就是扑克牌~）是 $Wayne$ 发明的，源于他对升级、斗地主、

锄大地等等玩法都感到厌倦了。于是他提出了这个新的玩法：

$Wayne$ 有一副加强版的扑克牌，强大到任意取一个自然数 $x$，在牌堆里都恰

有 $4$ 张数值为 $x$ 的牌。每次，$Wayne$ 随机生成两个正整数 $n$ 和 $k$，然后在牌堆里

选取不超过 $k$ 张牌，使得牌面数字之和恰为 $n$。已知 $Wayne$ 玩了若干盘，每盘都

算出了对应的方案数，他想请你也算出各盘方案数，以验算他的结果是否正确。

结果可能比较大，你只需要求出方案数 $mod 1000000009$ 的值即可。

【输入】

输入文件包含不超过 $10$ 组数据。

每行包含两个整数，表示上文中的 $n$ 和 $k$。

输入数据以两个 $0$ 表示结束。

【输出】

输出文件中，每组数据输出一行，为对应的方案数。

样例输入	样例输出
2 1 2 2 2 3 50 5 0 0	4 10 10 1823966

【数据规模】

对于 $10\%$的数据，$k=1$；

对于 $20\%$的数据，$n≤10，k≤4$；

对于 $40\%$的数据，$n≤1000$；

对于 $60\%$的数据，$n≤100000$；

对于另外 $20\%$的数据，只有 $1$ 组数据；

对于 $100\%$的数据，$n≤10^9，k≤10$。

【算法1】

输出n，不解释。。。

期望得分：10。

【算法2】

利用上式对Ai和Xi进行搜索，同样不解释。。。

期望得分：20。

【算法3】

把牌按数值大小编号，数值相同的编上4个不同号码。

用f[i][j][k]表示现在处理完前i张牌，一共用了j张，构成和为k的方案数。转移只要使用类似背包的方法即可。

方程为：f’[i][j][k]=f[i][j][k]+Σf[i-1][j-1][k-w(i)]。

其中w(i)为i的牌面。

为免MLE，可把第一维省去。

期望得分：40。

【算法4】

这是Symbol提出来的方法。

如果现在所有的牌面都大于1，假设有k’张，那么把所有牌面都减小1，总和减少k’之后，问题显然是等价的；而如果有牌面等于1，那么只要把这几张牌去掉，剩下的牌面就又都是大于1的了。

所以可以使用f[i][j]表示用j张牌构成和为i的方案数，转移的时候分情况：1）所有牌面大于1，则f[i][j]+=f[i-j][j]；2）有牌面等于1，那么我们可以枚举这些牌的数量t（≤4），则f[i][j]+=f[i-j][j-t]。

最后答案就是f[n][1~k]的最小值。

时间复杂度为O(nk)。

期望得分：60。

【算法5】

对算法4进行优化，考虑到k比较小，而转移只需要用到前k层的值。

我们可以把连续k层的f压在一个矩阵内，并按一维编号，最多不超过k^2个。然后我们每次转移1层的f，也就是如果现在矩阵记录的是f[1~k][]的值，那么转移一次，矩阵记录的就变成了f[2~k+1][]的值。然后填矩阵就是了。

时间复杂度为O(logn*k^6)，多组数据下，这个方法会由于常数大被卡掉。

期望得分：80。

【算法6】

首先，假设牌面的集合为{xi}，集合中的每个元素对应一个ai（≤4），表示这个牌面用了多少张。那么问题就转化成了求Σai*xi=n的正整数解个数，其中x1<x2<…<xm，Σai≤k。由于ai和k都比较小，我们可以暴力枚举所有情况，再去解方程。而现在约束还是比较多的，我们得想办法除去约束。

设yi=xi-x(i-1)，换元后方程变为Σbi*yi=n的形式，其中bi≤k。至此，我们成功把未知数单调这个棘手的约束解决了。

接下来，我们发现bi比较小（≤10），那么可以把bi的lcm算出来，最多为2520。然后把biyi表示成pilcm+qi的形式，其中qi必须能被bi整除。

现在方程转化为lcm*Σpi+Σqi=n。

考虑到Σqi还是比较小的（≤3W），可以枚举Σqi的每个可能值，那么pi的方案数就可以用经典的隔板法来计算。而对于Σqi的计算，我们可以用背包来实现。背包的时候要注意各种细节，而且注意复杂度的把握。

期望得分：100。

然而并没有看懂？？？

当时打了个表就交了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//Poker Hewr
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define fo(i,a,b) for (int i=a; i<=b; ++i)
#define fd(i,a,b) for (int i=a; i>=b; --i)
#define mo 1000000009
#define LL long long

const int mn=11,mm=30010;
int a[mn],d[mn],Rev[mn],f[mm],F[mm];
int n,k,m,L,Ans,NowS,N,A,B;

int gcd(int a,int b){
	int c;
	while (c=(a%b)) a=b,b=c;
	return b;
}

int C(int a,int b){
	if (a<b) return 0;
	int ret=Rev[b];
	fo (i,a-b+1,a) ret=(LL)ret*i%mo;
	return ret;
}

int Pow(int a,int b){
	int ret=1;
	while (b){
		if (b&1) ret=(LL)ret*a%mo;
		a=(LL)a*a%mo,b>>=1;
	}
	return ret;
}

void dp(int x){
	fo (i,0,NowS) F[i]=f[i];
	int l=L/x*x;
	fo (i,NowS+1,min(n,NowS+l)) F[i]=0;
	NowS=min(n,NowS+l);
	fo (i,0,NowS){
		f[i]=0;
		if (i>=x){
			F[i]=(F[i]+(f[i]=F[i-x]))%mo;
			if (i>=l+x) f[i]=(f[i]-F[i-l-x]+mo)%mo;
		}
	}
	/*int y=x;
	while (y<=L){
		fd (i,min(n-y,NowS),0) f[i+y]=(f[i+y]+F[i])%mo;
		y+=x;
	}
	NowS=min(n,NowS+L/x*x);*/
}

int work(){
	int Ans=0;
	d[m]=a[m];
	fd (i,m-1,1) d[i]=d[i+1]+a[i];
	f[0]=1,NowS=0,L=1;
	fo (i,1,m) L=L*d[i]/gcd(L,d[i]);
	fo (i,1,m) dp(d[i]);
	fo (nn,m,NowS) if (!((N=n-nn)%L) && (A=f[nn])){
		B=C(N/L+m-1,m-1);
		Ans=((LL)A*B+Ans)%mo;
	}
	return Ans;
}

void dfs(int M,int K,int W){
	if (M>1){
		m=M-1;
		int tmp=work();
		Ans=((LL)tmp*W+Ans)%mo;
	}
	if (!K) return;
	fo (i,1,4) if (i<=K){
		a[M]=i;
		dfs(M+1,K-i,(LL)W*C(4,i)%mo);
		a[M]=0;
	}
}

int main(){
	Rev[0]=1;
	fo (i,1,mn-1) Rev[i]=(LL)Rev[i-1]*Pow(i,mo-2)%mo;
	freopen("poker.in","r",stdin);
	freopen("poker.out","w",stdout);
	while (cin>>n>>k){
		if (!(n+k)) break;
		Ans=0;
		dfs(1,k,1);
		cout<<Ans<<endl;
	}
}