CDQZ Day6

1
DP #2
题目名称 种植 计数 棋盘 树
输入文件名 plant.in count.in chess.in tree.in
输出文件名 plant.out count.out chess.out tree.out
每个测试点时
限
1s 1s 1s 1 s
测试点数目 10 10 10 10
每个测试点分
值
10 10 10 10
内存限制 256M 256M 256M 256M
是否有部分分 否 否 否 否
题目类型 传统 传统 传统 传统
注意：代码长度限制均为64K，不开O2。
2
1 1 种植 (plant.c/cpp/pas) .c/cpp/pas) .c/cpp/pas)
1.1 1.1 1.1 题目描述 题目描述
现在 有一块 有一块 n 行 m 列的地，你想要 你想要 在上面 在上面 种植 你心爱 的花，为了 避免 它们 争夺 肥料 ， 你希望 任意 两朵花 两朵花 不能 上下左右 上下左右 紧邻 。另外 一些 地方 杂草 丛生 ，所以 你不能 在这些 位置 种上 你的 花。
现在 你希望 你希望 知道 有多少种 多少种 种花 的方案 ，注意 什么 都不种 也是 一种 方案 。
1.2 1.2 1.2 输入格式 输入格式
第一行为两 第一行为两 个整数 个整数 n ，m，表示 行和列。
接下来 n 行，每行 m 个数，若为 0表示 该位置 不能 种花 ，为 1 表示 能种花 。
1.3 1.3 1.3 输出格式 输出格式
输出 一行个整数，表示 一行个整数，表示 一行个整数，表示 一行个整数，表示 一行个整数，表示 方案数 对 100 000 00 0 取模 的结果 。
1.4 1.4 1.4 样例输入 样例输入
2 3
1 1 1
0 1 0
1.5 1.5 1.5 样例输出 样例输出
9
1.6 1.6 1.6 数据范围与约定 数据范围与约定 数据范围与约定 数据范围与约定
对于 20％的数据， ％的数据， ％的数据， n , m<= 5。
对于 40％的数据， 的数据， n , m<= 10 。
对于 100％的数据 ，n, m<=12。
3
2 2 计数 (count count .c/cpp/pas) .c/cpp/pas) .c/cpp/pas)
2.1 .1 .1 题目描述 题目描述
给出 L,R ，求 [L,R] [L,R] [L,R] [L,R] 之中各位数字和能整除原的个。 之中各位数字和能整除原的个。 之中各位数字和能整除原的个。 之中各位数字和能整除原的个。 之中各位数字和能整除原的个。 之中各位数字和能整除原的个。 之中各位数字和能整除原的个。 之中各位数字和能整除原的个。 之中各位数字和能整除原的个。
2.2 .2 .2 输入格式 输入格式
一行 两个 整数，分别 表示 L, R。
2.3 .3 .3 输出格式 输出格式
输出 一行 一个数， 一个数， 一个数， 表示 答案 。
2.4 .4 .4 样例输入 样例输入
10 19
2.5 .5 .5 样例输出 样例输出
3
2.6 .6 .6 数据范围与约定 数据范围与约定 数据范围与约定 数据范围与约定
对于 20％的数据，保证 ％的数据，保证 ％的数据，保证 ％的数据，保证 R<=100000。
对于 100 ％的数据，保证 ％的数据，保证 ％的数据，保证 ％的数据，保证 1 <= L <= R <= 10 18。
4
3 棋盘 (chess chess .c/cpp/pas) .c/cpp/pas) .c/cpp/pas)
3.1 .1 .1 题目描述 题目描述
你现在 要在 棋盘 上放棋子 ，棋盘规格为 棋盘规格为 棋盘规格为 n*m，需要 满足 任意一个 任意一个 任意一个 n*n 的区域内都有 的区域内都有 的区域内都有 C 个棋子。 个棋子。 请输出 有多少个满足条件的方案。 有多少个满足条件的方案。 有多少个满足条件的方案。 有多少个满足条件的方案。 有多少个满足条件的方案。 有多少个满足条件的方案。
3.2 .2 .2 输入格式 输入格式
一行 三个 整数 n, m, C，含义 如题 所述 。
3.3 .3 .3 输出格式 输出格式
输出一行个整数， 输出一行个整数， 输出一行个整数， 输出一行个整数， 表示 答案 对 109+7 取模 的结果 。
3.4 .4 .4 样例输入 样例输入
2 3 1
3.5 .5 .5 样例输出 样例输出
6
3 .6 .6 .6 数据范围与约定 数据范围与约定 数据范围与约定
对于 20％的数据， ％的数据， ％的数据， n, K<=4；
对于 另外 20％的数据 ，m=n；
对于 另外 20％的数据 ，n<=50；
对于 100 ％的数据， ％的数据， ％的数据， 1<=n<=100；1<=m<=1018；1<=C<=n2
5
4 树(tree.c/cpp/pas) .c/cpp/pas) .c/cpp/pas)
4.1 .1 .1 题目描述 题目描述
现在 有一棵 有一棵 n 个点的树，每个点 颜色 非黑即白 非黑即白 ，有 Q次询问 ，每次 给出 x, y，询问 是 否存在 一个 x 个点的联通 子图 ，其中 黑点 数目 为 y。
4.2 .2 .2 输入格式 输入格式
第一行 两个 整数， 整数， n 和 Q ，分别 表示树的节点数和询问次。 表示树的节点数和询问次。 表示树的节点数和询问次。 表示树的节点数和询问次。 表示树的节点数和询问次。 表示树的节点数和询问次。 表示树的节点数和询问次。
接下来 n-1 行，每两个 行，每两个 行，每两个 行，每两个 数 a，b，表示 a、b之间 有一条 边。
接下来一行有 接下来一行有 接下来一行有 n 个用空格隔开的整数， 个用空格隔开的整数， 个用空格隔开的整数， 个用空格隔开的整数， 个用空格隔开的整数， 第 i个数若为 1，则表示第 ，则表示第 ，则表示第 i 个点为白色，否 个点为白色，否 个点为白色，否 个点为白色，否 则为黑色。 则为黑色。
接下来 Q 行，每两个用空格隔开的整数 行，每两个用空格隔开的整数 行，每两个用空格隔开的整数 行，每两个用空格隔开的整数 行，每两个用空格隔开的整数 行，每两个用空格隔开的整数 行，每两个用空格隔开的整数 行，每两个用空格隔开的整数 x 和 y，表示 询问 。
4.3 .3 .3 输出格式 输出格式
输出 Q行，每行 为“YES YES”表示 存在 ，或“NO ”表示 不存在 不存在 。
4.4 .4 .4 样例 输入 9 4 4 1 1 5 1 2 3 2 3 6 6 7 6 8 9 6 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 3 2 7 3 4 0 9 5
4.5 .5 .5 样例输出 样例输出
YES YES
YES YES
NO
NO
4.6 .6 .6 数据范围与约定 数据范围与约定 数据范围与约定 数据范围与约定
对于 20％的数据，保证 ％的数据，保证 ％的数据，保证 ％的数据，保证 n <= 10。
对于 50％的数据，保证 ％的数据，保证 ％的数据，保证 ％的数据，保证 1<=n<=500。
对于 100 ％的数据，保证 ％的数据，保证 ％的数据，保证 ％的数据，保证 1<=n<=5000n<=5000n<=5000n<=5000n<=5000n<=5000n<=5000，q<=10^5q<=10^5q<=10^5q<=10^5q<=10^5q<=10^5q<=10^5

  1 #include<cstdio>
  2 #include<cstring>
  3 //#include<iostream>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<vector>
  7 //#include<stack>
  8 #include<bitset> 
  9 #define R(a,b,c) for(register int (a)=(b);(a)<=(c);++(a))
 10 #define nR(a,b,c) for(register int (a)=(b);(a)>=(c);--(a))
 11 #define Ii inline int
 12 #define Iv inline void
 13 #define Il inline long long
 14 #define Ib inline bool
 15 #define INF 0x7ffffff
 16 #define re register
 17 #define ll long long
 18 #define Max(a,b) ((a)>(b)?(a):(b))
 19 #define Min(a,b) ((a)<(b)?(a):(b))
 20 #define Cmin(a,b) ((a)=(a)<(b)?(a):(b))
 21 #define Cmax(a,b) ((a)=(a)>(b)?(a):(b))
 22 #define Fill(a,b) memset((a),(b),sizeof((a)))
 23 #define D_e_Line printf("
-------------
");
 24 #define D_e(x) printf("
______%d_______
",x)
 25 #define Pause() system("pause")
 26 using namespace std;
 27 const int N=5005;
 28 Ii read(){
 29     int s=0,f=1;char c;
 30     for(c=getchar();c>'9'||c<'0';c=getchar())if(c=='-')f=-1;
 31     while(c>='0'&&c<='9')s=s*10+(c^'0'),c=getchar();
 32     return s*f;
 33 }
 34 template<class T>Iv print(T x){
 35     if(x<0)putchar('-'),x=-x;
 36     if(x>9)print(x/10);
 37     putchar(x%10^'0');    
 38 }
 39 bitset<N>w;
 40 vector<int>V[N];
 41 int ans[N][N],points,black,n,flag;
 42 Iv dfs(int u,int size,int tot){
 43     if(size==points&&tot==black){flag=1;return;}
 44     if(size>points)return;
 45     for(vector<int>::iterator v=V[u].begin();v!=V[u].end();++v)
 46         dfs(*v,size+1,tot+(!w[*v]));
 47 }
 48 Ib Check(){
 49     flag=0;
 50     R(i,1,n)
 51         dfs(i,0,0);
 52     return flag;
 53 }
 54 #define ON_JUD
 55 int main(){
 56 #ifdef  ON_JUD
 57     freopen("tree.in","r",stdin),freopen("tree.out","w",stdout);
 58 #endif
 59     n=read();
 60     int T=read();
 61     R(i,1,n-1){
 62         int u=read(),v=read();
 63         V[u].push_back(v),V[v].push_back(u);
 64     }
 65     R(i,1,n)
 66         w[i]=1-read();
 67     R(i,1,n-1)
 68         R(j,1,n-1)
 69             points=i,black=j,
 70             ans[i][j]=Check();
 71     while(T--){
 72         points=read(),black=read();
 73         if(points>=n)
 74             printf("NO
");
 75         else if(ans[points][black]==1)
 76             printf("YES
");
 77         else
 78             printf("NO
");
 79     }
 80     return 0;
 81 }
 82 /*
 83 9 4
 84 4 1
 85 1 5
 86 1 2
 87 3 2
 88 3 6
 89 6 7
 90 6 8
 91 9 6
 92 0 1 0 1 0 0 1 0 1
 93 3 2
 94 7 3
 95 4 0
 96 9 5
 97 
 98 9 4
 99 4 1
100 1 5
101 1 2
102 3 2
103 3 6
104 6 7
105 6 8
106 9 6
107 0 1 0 1 0 0 1 0 1
108 4 0
109 3 2
110 7 3
111 9 5
112 
113 9 1034923948
114 4 1
115 1 5
116 1 2
117 3 2
118 3 6
119 6 7
120 6 8
121 9 6
122 0 1 0 1 0 0 1 0 1
123 7 3
124 */
plant_My_CreatOnContest
  1 #include<cstdio>
  2 #include<cstring>
  3 //#include<iostream>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<vector>
  7 //#include<stack>
  8 #include<bitset> 
  9 #define R(a,b,c) for(register int (a)=(b);(a)<=(c);++(a))
 10 #define nR(a,b,c) for(register int (a)=(b);(a)>=(c);--(a))
 11 #define Ii inline int
 12 #define Iv inline void
 13 #define Il inline long long
 14 #define Ib inline bool
 15 #define INF 0x7ffffff
 16 #define re register
 17 #define ll long long
 18 #define Max(a,b) ((a)>(b)?(a):(b))
 19 #define Min(a,b) ((a)<(b)?(a):(b))
 20 #define Cmin(a,b) ((a)=(a)<(b)?(a):(b))
 21 #define Cmax(a,b) ((a)=(a)>(b)?(a):(b))
 22 #define Fill(a,b) memset((a),(b),sizeof((a)))
 23 #define D_e_Line printf("
-------------
");
 24 #define D_e(x) printf("
______%d_______
",x)
 25 #define Pause() system("pause")
 26 using namespace std;
 27 const int N=5005;
 28 Ii read(){
 29     int s=0,f=1;char c;
 30     for(c=getchar();c>'9'||c<'0';c=getchar())if(c=='-')f=-1;
 31     while(c>='0'&&c<='9')s=s*10+(c^'0'),c=getchar();
 32     return s*f;
 33 }
 34 template<class T>Iv print(T x){
 35     if(x<0)putchar('-'),x=-x;
 36     if(x>9)print(x/10);
 37     putchar(x%10^'0');    
 38 }
 39 bitset<N>w;
 40 vector<int>V[N];
 41 int ans[N][N],points,black,n,flag;
 42 Iv dfs(int u,int size,int tot){
 43     if(size==points&&tot==black){flag=1;return;}
 44     if(size>points)return;
 45     for(vector<int>::iterator v=V[u].begin();v!=V[u].end();++v)
 46         dfs(*v,size+1,tot+(!w[*v]));
 47 }
 48 Ib Check(){
 49     flag=0;
 50     R(i,1,n)
 51         dfs(i,0,0);
 52     return flag;
 53 }
 54 #define ON_JUD
 55 int main(){
 56 #ifdef  ON_JUD
 57     freopen("tree.in","r",stdin),freopen("tree.out","w",stdout);
 58 #endif
 59     n=read();
 60     int T=read();
 61     R(i,1,n-1){
 62         int u=read(),v=read();
 63         V[u].push_back(v),V[v].push_back(u);
 64     }
 65     R(i,1,n)
 66         w[i]=1-read();
 67     R(i,1,n-1)
 68         R(j,1,n-1)
 69             points=i,black=j,
 70             ans[i][j]=Check();
 71     while(T--){
 72         points=read(),black=read();
 73         if(points>=n)
 74             printf("NO
");
 75         else if(ans[points][black]==1)
 76             printf("YES
");
 77         else
 78             printf("NO
");
 79     }
 80     return 0;
 81 }
 82 /*
 83 9 4
 84 4 1
 85 1 5
 86 1 2
 87 3 2
 88 3 6
 89 6 7
 90 6 8
 91 9 6
 92 0 1 0 1 0 0 1 0 1
 93 3 2
 94 7 3
 95 4 0
 96 9 5
 97 
 98 9 4
 99 4 1
100 1 5
101 1 2
102 3 2
103 3 6
104 6 7
105 6 8
106 9 6
107 0 1 0 1 0 0 1 0 1
108 4 0
109 3 2
110 7 3
111 9 5
112 
113 9 1034923948
114 4 1
115 1 5
116 1 2
117 3 2
118 3 6
119 6 7
120 6 8
121 9 6
122 0 1 0 1 0 0 1 0 1
123 7 3
124 */
tree_My_CreatOnContest
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int MAXN = 5005 ;
 8 int n, Q, first[MAXN], nexts[MAXN<<1], to[MAXN<<1], egnum, color[MAXN] ;
 9 int f[MAXN][MAXN], g[MAXN][MAXN], size[MAXN] , minn[MAXN] , maxn[MAXN] ;
10 //f[i][j]: 浠�涓烘牴鐨勫ぇ灏忎负j鐨勮仈閫氬潡涓�紝榛戠偣鏈€灏戞暟鐩?
11 //g[i][j]: 浠�涓烘牴鐨勫ぇ灏忎负j鐨勮仈閫氬潡涓�紝榛戠偣鏈€澶氭暟鐩?
12 //minn[i]: 澶у皬涓篿鐨勮仈閫氬潡榛戠偣鏈€灏戞暟鐩?
13 //maxn[i]: 澶у皬涓篿鐨勮仈閫氬潡榛戠偣鏈€澶氭暟鐩?
14 
15 void addEdge(int a,int b){
16     nexts[++egnum]=first[a] , first[a]=egnum , to[egnum]=b ;
17 }
18 
19 void dfs(int a, int fa){
20     size[a]=1 ;
21     if(color[a]) f[a][1]=g[a][1]=1 ;
22     else f[a][1]=g[a][1]=0 ;
23     for(int i=first[a];i;i=nexts[i]){
24         int b=to[i] ;
25         if(b==fa) continue ;
26         dfs(b,a) ;
27         int lj = size[a]+size[b] ;
28         for(int j=lj ; j>=1 ; --j){
29             // j-k <= size[a]
30             int lk1=max(1,j-size[a]) , lk2=min(size[b],j-1) ;
31             for(int k=lk1 ; k<=lk2 ; ++k){
32                 f[a][j] = min(f[a][j], f[a][j-k]+f[b][k]) ;
33                 g[a][j] = max(g[a][j], g[a][j-k]+g[b][k]) ;
34             }
35         }
36         size[a]+=size[b] ;
37     }
38 }
39 
40 void init(){
41     memset(first,0,sizeof(first)) ;
42     memset(f,0x3f,sizeof(f)) ;
43     memset(g,0,sizeof(g)) ;
44     memset(minn,0x3f,sizeof(minn)) ;
45     memset(maxn,0,sizeof(maxn)) ;
46     egnum=0 ;
47     ////
48 }
49 
50 void solve(){
51     freopen("tree.in","r",stdin) ;
52     freopen("tree.out","w",stdout) ;
53     scanf("%d%d", &n, &Q) ;
54     for(int i=1;i<n;++i){
55         int a,b;
56         scanf("%d%d",&a,&b) ;
57         addEdge(a,b), addEdge(b,a) ;
58     }
59     for(int i=1;i<=n;++i) scanf("%d",&color[i]) ;
60     dfs(1,0) ;
61     for(int i=1;i<=n;++i)
62         for(int j=1;j<=n;++j)
63             minn[j] = min(minn[j], f[i][j]), maxn[j] = max(maxn[j], g[i][j]) ;
64     for(int i=1;i<=Q;++i){
65         int x,y;
66         scanf("%d%d",&x,&y) ;
67         if(y>=minn[x] && y<=maxn[x])
68             printf("YES
") ;
69         else printf("NO
") ;
70     }
71 }
72 
73 int main(){
74     init() ;
75     solve() ;
76     return 0 ;
77 }
tree_STD.cpp
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int MAXN = 13, MAXM = 5005, MOD = 100000000 ;
 8 int n, m, dp[MAXN][MAXM], A[MAXN] ;
 9 
10 inline bool check(const int &x){ return (x&(x<<1))==0 ; }
11 
12 inline bool check(const int &a, const int &b){ return check(a) && check(b) && ((a&b)==0) ; }
13 
14 inline void getMod(int &x){ if(x>=MOD) x-=MOD ; }
15 
16 inline bool getNext(int &x, const int &S) { 
17     x = (x-1) & S ;
18     return true ;
19 }
20 
21 int main(){
22     freopen("plant.in","r",stdin) ;
23     freopen("plant.out","w",stdout) ;
24     scanf("%d%d",&n,&m) ;
25     int tmp ;
26     for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
27             scanf("%d",&tmp) , A[i] |= (tmp<<(j-1)) ;
28     int M = (1<<m)-1 ;
29     for(int sta=A[1]; sta ; sta=(sta-1)&A[1] ){
30         if(check(sta)) dp[1][sta]=1 ;
31     }
32     dp[1][0]=1 ;
33     for(int i=2; i<=n; ++i){
34         int sta = A[i] ;
35         do{
36             int sta2 = A[i-1] ;
37             do{
38                 if(check(sta, sta2)) dp[i][sta] += dp[i-1][sta2] ;
39                 getMod(dp[i][sta]) ;
40             }while(sta2 && getNext(sta2, A[i-1])) ;
41         }while(sta && getNext(sta, A[i])) ;
42     }
43     int ans=0;
44     for(int j=0; j<=M ; ++j)
45         ans += dp[n][j] , getMod(ans) ;
46     printf("%d
",ans) ;
47     return 0 ;
48 }
plant_STD.cpp
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 long long dp[20][175][175][2] ; //闀夸负i锛屽悇浣嶆暟瀛楀拰涓簀锛屾暟瀵筸od鍙栨ā鍚庝负k锛屾槸鍚﹀帇鐫€涓婄晫 鐨勪釜鏁?
 8 int bits[20] , bnum ;
 9 
10 long long solve(long long L){  //1~t
11     long long ans=0 ;
12     bnum=0 ;
13     while(L) bits[++bnum]=L%10 , L/=10 ;
14     reverse(bits+1,bits+bnum+1) ;
15     int maxn=min(bnum*9,163) ;
16     for(int mod=1;mod<=maxn;++mod){
17         memset(dp,0,sizeof(dp)) ;
18         dp[0][0][0][1]=1 ;
19         for(int i=0;i<bnum;++i){
20             for(int j=0;j<=mod;++j){
21                 for(int k=0;k<mod;++k){
22                     if(dp[i][j][k][0]){
23                         for(int t=0;t<=9;++t){
24                             dp[i+1][j+t][(k*10+t)%mod][0]+=dp[i][j][k][0] ;
25                         }
26                     }
27                     if(dp[i][j][k][1]){
28                         for(int t=0;t<bits[i+1];++t){
29                             dp[i+1][j+t][(k*10+t)%mod][0]+=dp[i][j][k][1] ;
30                         }
31                         dp[i+1][j+bits[i+1]][(k*10+bits[i+1])%mod][1]+=dp[i][j][k][1] ;
32                     }
33                 }
34             }
35         }
36         ans+=dp[bnum][mod][0][0]+dp[bnum][mod][0][1] ;
37     }
38     return ans ;    
39 }
40 
41 int main(){
42     freopen("count.in","r",stdin) ;
43     freopen("count.out","w",stdout) ;
44     long long a, b;
45     cin >> a >> b ;
46     cout << solve(b)-solve(a-1) << '
' ;
47 }
count_STD.cpp
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int MAXN=105;
 8 int n , K;
 9 const int MOD=1000000007 ;
10 long long m, C[MAXN][MAXN], Coe[MAXN][MAXN] ; //Coe[i][j]琛ㄧず鏀剧疆绗琲鍒楁椂锛孋(n,j)鐨勬煇娆″箓鐨勫€笺€?
11 long long dp[MAXN][MAXN*MAXN] ;
12 
13 long long powMod(long long a,long long b){
14     long long ret=1 ;
15     while(b){
16         if(b&1) ret=ret*a%MOD ;
17         b>>=1 , a=a*a%MOD ;
18     }
19     return ret;
20 }
21 
22 int main(){
23     freopen("chess.in","r",stdin) ;
24     freopen("chess.out","w",stdout) ;
25     cin >> n >> m >> K ;
26     C[0][0]=1 ;
27     for(int i=1;i<=100;++i){
28         C[i][0]=C[i][i]=1 ;
29         for(int j=1;j<i;++j){
30             C[i][j]=C[i-1][j-1]+C[i-1][j] ;
31             if(C[i][j]>=MOD) C[i][j]-=MOD ;
32         }
33     }
34     for(int i=1;i<=n;++i){
35         long long p=(m-i)/n+1 ;
36         for(int j=0;j<=n;++j){
37             Coe[i][j]=powMod(C[n][j],p) ;
38         }
39     }
40     dp[0][0]=1 ;
41     for(int i=1;i<=n;++i){
42         for(int j=0;j<=i*n && j<=K;++j){
43             int L=min(n,j) ;
44             for(int k=0;k<=L;++k){
45                 dp[i][j]+=dp[i-1][j-k]*Coe[i][k]%MOD ;
46                 if(dp[i][j]>=MOD) dp[i][j]-=MOD ;
47             }
48         }
49     }
50     cout << dp[n][K] << '
' ;
51     return 0 ;
52 }
chess_STD.cpp
  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<vector>
  7 //#include<stack>
  8 #include<bitset> 
  9 #define R(a,b,c) for(register int (a)=(b);(a)<=(c);++(a))
 10 #define nR(a,b,c) for(register int (a)=(b);(a)>=(c);--(a))
 11 #define Ii inline int
 12 #define Iv inline void
 13 #define Il inline long long
 14 #define Ib inline bool
 15 #define INF 0x3f3f3f3f
 16 #define re register
 17 #define ll long long
 18 #define Max(a,b) ((a)>(b)?(a):(b))
 19 #define Min(a,b) ((a)<(b)?(a):(b))
 20 #define Cmin(a,b) ((a)=(a)<(b)?(a):(b))
 21 #define Cmax(a,b) ((a)=(a)>(b)?(a):(b))
 22 #define Fill(a,b) memset((a),(b),sizeof((a)))
 23 #define D_e_Line printf("
-------------
");
 24 #define D_e(x) printf("
______%d_______
",x)
 25 #define Pause() system("pause")
 26 using namespace std;
 27 const int N=5005;
 28 Ii read(){
 29     int s=0,f=1;char c;
 30     for(c=getchar();c>'9'||c<'0';c=getchar())if(c=='-')f=-1;
 31     while(c>='0'&&c<='9')s=s*10+(c^'0'),c=getchar();
 32     return s*f;
 33 }
 34 template<class T>Iv print(T x){
 35     if(x<0)putchar('-'),x=-x;
 36     if(x>9)print(x/10);
 37     putchar(x%10^'0');    
 38 }
 39 int col[N],f[N][N],g[N][N],size[N],mi[N],mx[N];
 40 vector<int>V[N];
 41 Iv dfs(int u,int fa){
 42     size[u]=1,
 43     f[u][1]=g[u][1]=col[u];
 44     for(vector<int>::iterator v=V[u].begin();v!=V[u].end();++v){
 45         if(*v==fa)continue;
 46         dfs(*v,u);
 47         //cout<<size[u]+size[*v]<<endl;
 48         nR(i,size[u]+size[*v],1){
 49             int sz1=Max(1,i-size[u]),sz2=Min(size[*v],i-1);
 50             R(j,sz1,sz2)
 51                 Cmin(f[u][i],f[u][i-j]+f[*v][j]),
 52                 Cmax(g[u][i],g[u][i-j]+g[*v][j]);
 53             //cout<<g[u][i]<<endl;
 54         }
 55         size[u]+=size[*v];
 56     }
 57 }
 58 int main(){
 59     freopen("tree.in","r",stdin) ;
 60     freopen("tree.out","w",stdout) ;
 61     Fill(f,INF),Fill(mi,INF);
 62     int n=read(),T=read();
 63     R(i,2,n){
 64         int u=read(),v=read(); 
 65         V[u].push_back(v),V[v].push_back(u);
 66     }
 67     R(i,1,n)
 68         col[i]=read();
 69     dfs(1,0);
 70     R(i,1,n)
 71         R(j,1,n)
 72             Cmin(mi[j],f[i][j]),
 73             Cmax(mx[j],g[i][j]);
 74     while(T--){
 75         int points=read(),black=read();
 76         if(points>n)
 77             printf("NO
");
 78         else if(black>=mi[points]&&black<=mx[points])
 79             printf("YES
");
 80         else
 81             printf("NO
");
 82     }
 83     return 0;
 84 }
 85 /*
 86 9 4
 87 4 1
 88 1 5
 89 1 2
 90 3 2
 91 3 6
 92 6 7
 93 6 8
 94 9 6
 95 0 1 0 1 0 0 1 0 1
 96 3 2
 97 7 3
 98 4 0
 99 9 5
100 */
tree_AC.cpp

Conclution:

　　T1:：咦，好眼熟，(⊙o⊙)做过，那打凉了岂不是很尴尬？幸好今天RP MAX.

　　T2:：一眼数位，暴力，放弃打表，跑路

　　T3：数位？组合？留个随机化，溜了溜了

　　T4：我的代码重构两次因不确定专业名词含义，因为太怂为了保险放弃DP打出n^4的dfsWA了

　　100+20+0+0

　　排名第六（不过PZY大佬正的NB搜过了T2，晋级Rank 1%%%）

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/bingoyes/p/10327567.html