2019.10.19 解题报告

T1：忍者钩爪 ( ( ninja) )

时间限制： 1s
空间限制： 512M
【问题描述】
小 Q 是一名酷爱钩爪的忍者，最喜欢飞檐走壁的感觉，有一天小 Q 发现一个练习使用钩
爪的好地方，决定在这里大显身手。
场景的天花板可以被描述为一个无穷长的数轴，初始小 Q 挂在原点上。数轴上有 N 个坐
标为整数的圆环供小 Q 实现钩爪移动。具体操作为：小 Q 可以将钩爪挂到圆环上，进而荡到
关于圆环坐标轴对称的位置。例如小 Q 在 3，圆环在 7，则小 Q 可以通过该圆环移动到 11。
现在一个问题难倒了小 Q，如何判断自己能否到达某个整点呢？
【输入格式】
第一行两个整数 N,M，表示圆环的数量和询问组数
接下来一行共 N 个整数描述每个圆环的坐标(可重复)
接下来 M 行每行包含一个整数描述询问
【输出格式】
共 M 行对应 M 个询问，若小 Q 能移动到目标点，输出 Yes，否则输出 No
【样例输入】
2 2
1 3
3
4
【样例输出】
No
Yes
【数据范围和注释】
对于 30%的数据，M≤N≤10，输入坐标绝对值均小于 1000。
对于 60%的数据，M≤N≤5000。
对于 100%的数据，M≤N≤100000，输入坐标绝对值均小于 10^18。

【Solution】

对于30%的分数

可以使用暴力记忆化搜索得出答案。即维护每个坐标是否可达，继而进行搜索。

对于60%的分数

通过观察可知设当前坐标为x，则通过坐标为a的圆环可移动到2a-x处。连续通过两个圆环(a,b)可以移动到x+(2b-2a)处。

先以移动步数为偶数情况考虑简化版问题：设圆环坐标为a[1]~a[n]，对于任意两个圆环，可由坐标x变为x+2(a[j]-a[i])，题目转化为对于N^2个数其中b[i,j]=2(a[j]-a[i])，通过有限次加减运算能否由x=0变化至目标。

根据广义裴蜀定理以及扩展欧几里得相关原理可知，当且仅当目标为gcd的倍数时有解。故预处理出全部可能的2(a[j]-a[i])，求出其最大公约数，在判断目标是否为gcd的倍数即可。

对于奇数的情况，可以通过枚举第一步的方案转化为偶数的情况，即维护一个set表示0步或1步可达点集(mod gcd意义下)，再查询目标点在mod gcd下是否属于这个集合即可。复杂度瓶颈在于N^2个数求gcd。

对于100%的分数

通过欧几里得算法的性质与更相减损术可知gcd(a,b)=gcd(a-b,b)。设p1={2*(a[i]-a[1])|i>1}的最大公约数，设p2={2*(a[i]-a[j])}的最大公约数，易知p1>=p2（因为p1比p2约束宽松）。而对于任意i,j由于p1同时是2*(a[i]-a[1])、2*(a[j]-a[1])的约束，那么p1也一定是任意2*(a[i]-a[1])-2*(a[j]-a[1])=2*(a[i]-a[j])的约数，故p1<=p2。综上所述p1=p2，这样就不需要N^2个数同时求gcd了，只求p1即可，可获得满分。

【Code】

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <set>
 4 using namespace std;
 5 const int N=200010;
 6 int n,m;
 7 long long a[N],GCD=0;
 8 set<long long> Set;
 9 long long gcd(long long a,long long b)
10 {
11     return b?gcd(b,a%b):a;
12 }
13 long long qabs(long long x){return x<0?-x:x;}
14 int main()
15 {
16     freopen("ninja.in","r",stdin);
17     freopen("ninja.out","w",stdout);
18     scanf("%d%d",&n,&m);
19     for(int i=1;i<=n;i++)
20         scanf("%lld",&a[i]);
21     for(int i=2;i<=n;i++)
22         GCD=gcd(2LL*qabs(a[i]-a[1]),GCD);
23     if(GCD==0)GCD=1000000000LL*1000000000LL; 
24     Set.insert(0LL);
25     for(int i=1;i<=n;i++)
26         Set.insert(((2*a[i])%GCD+GCD)%GCD);
27     while(m--)
28     {
29         long long q;
30         scanf("%lld",&q);
31         if(Set.find((q%GCD+GCD)%GCD)!=Set.end())
32             puts("Yes");
33         else
34             puts("No");
35     }
36     fclose(stdin);
37     fclose(stdout);
38     return 0;
39 }

std

T2：选球游戏（ game ）

时间限制：3s
空间限制：512MB
编译时开启 O2 优化开关
【问题描述】
华华和秀秀在玩游戏。在他们面前有!个球排成一排，从左到右按 1 到!编号。每个球有一
个可正可负的权值。每一轮，秀秀会选定一个区间[a, b]，将编号在这个区间内的所有球的权值
加上一个值'，或者将编号在这个区间内的所有球的权值都设为其相反数。华华则需从这!个球
中选出(个球来，他的得分为这(个球的权值的乘积。
华华每次都能快快地找出得分最优的选球方案来。秀秀想了想，决定提升游戏难度。她每
次会选定一个区间[a,b]，然后询问华华在这个区间内选出((1 ≤ ( ≤ 10)个球的所有方案的得
分之和。
这下可把华华难倒了，于是华华找到了聪明的你。你能帮帮他嘛？
由于所有方案的得分之和可能很大，你只需要输出得分之和对1000000007(10 / + 7)取模
的结果（负数请加上10 / + 7变成非负数）即可。
【输入格式】
从文件 game.in 中读入数据。
输入第一行包含两个正整数!,1，分别表示球的个数和秀秀的操作条数。
接下来一行包含!个空格隔开的整数，表示每个球初始的权值。
接下来1行，每行表示秀秀的一个操作。
若该行形如“1 a b c '”，则表示秀秀将编号属于[a, b]的所有球的权值都加上了'；
若该行形如“2 a b”，则表示秀秀将编号属于[a, b]的所有球的权值都置为了其相反数；
若该行形如“3 a b k”，则表示华华需要回答从[a,b]中选出(个球的所有取球方案的得分之
和。
【输出格式】
输出文件到 game.out 中。
对于秀秀宝宝的每一个询问操作，输出一行，表示该询问的答案。
【样例输入】
10 9
3 6 7 4 6 1 6 7 2 6
3 5 7 3
1 1 7 -9
1 2 3 5
3 2 6 1
2 5 8
3 5 7 3
2 2 3
3 1 10 2
3 1 2 2
【样例输出】
36
999999996
72
999999885
12
【样例说明】
第一个询问：6×1×6 = 36
第二个询问：
询问前各个球的权值为：-6 2 3 -5 -3 -8 -3 7 2 6
2 + 3 + −5 + −3 + −8 = −11
−11 + (10 / + 7) = 999999996
第三个询问：
询问前各个球的权值为：-6 2 3 -5 3 8 3 7 2 6
3×8×3 = 72
【子任务】
子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解决一
部分测试数据。每个测试点的规模及特点如下表：

【Solution】

考虑用线段树来完成此题。对于每个节点我们维护一个f[i](i \in [1, 10])，表示这个节点所对应区间选i个球的答案。
考虑如何合并两个节点lc,rc。f[i] = sum（lc.f[j] * rc.f[i-j]) j \in [0,i]
对于取相反数操作，只有当i是奇数时，才会改变f[i]的符号。
对于一段区间+c的操作，设这段区间的长度为len，则新的f[i]为sum (f(j) * c^{i-j} * C(len - j, i - j)) j\in [0,i] 其中C(n,m)表示n个数中选m个的组合数
这样我们就可以套用区间修改区间询问的线段树来解决这道题了，时间复杂度为O(c^2nlogn)

【Code】

  1 //k = 1区间求和
  2 //k = 2区间求和区间平方和
  3 //区间取相反数对于区间平方和无影响，在区间和上打tag 
  4 //(x + c) ^ 2 = x ^ 2 + 2cx + c^2 
  5 
  6 #include<cstdio>
  7 #include<iostream>
  8 #include<cstring>
  9 #include<algorithm>
 10 #include<queue>
 11 #include<ctime>
 12 #include<cstdlib>
 13 #include<vector>
 14 using namespace std;
 15 typedef long long ll;
 16 const int mod = 1e9 + 7,N = 50010,ni = 500000004;
 17 #define int ll //不要T啊啊啊！！ 
 18 ll read() {
 19     ll x = 0,f = 1;char c = getchar();
 20     while(c < '0' || c > '9') {
 21         if(c == '-') f = -1;c = getchar();
 22     }
 23     while(c >= '0' && c <= '9') {
 24         x = x * 10 + c - '0';c = getchar();
 25     }
 26     return x * f;
 27 }
 28 int n,m,a[N];
 29 int tree_sum[N << 2],tree_mul[N << 2];
 30 void pushup(int rt) {
 31     tree_sum[rt] = (tree_sum[rt << 1] + tree_sum[rt << 1 | 1]) % mod;
 32     tree_mul[rt] = (tree_mul[rt << 1] + tree_mul[rt << 1 | 1]) % mod;
 33 }
 34 void build(int rt,int l,int r) {
 35     if(l == r) {
 36         tree_sum[rt] = a[l];
 37         tree_mul[rt] = 1ll * a[l] * a[l] % mod;
 38         return;
 39     }
 40     int mid = (l + r) >> 1;
 41     build(rt << 1,l,mid);
 42     build(rt << 1 | 1,mid + 1,r);
 43     pushup(rt);
 44 }
 45 int lazy[N << 2],tag[N << 2];
 46 void pushdown(int rt,int ln,int rn) {//先下方区间加 
 47 
 48     if(tag[rt]) {
 49         tree_sum[rt << 1] = -tree_sum[rt << 1];
 50         tree_sum[rt << 1 | 1] = -tree_sum[rt << 1 | 1];
 51         
 52         lazy[rt << 1] = -lazy[rt << 1];
 53         lazy[rt << 1 | 1] = -lazy[rt << 1 | 1];
 54     
 55         tag[rt << 1] ^= 1;
 56         tag[rt << 1 | 1] ^= 1;
 57         tag[rt] = 0;
 58     }
 59 
 60     if(lazy[rt]) {
 61         lazy[rt << 1] += lazy[rt];
 62         lazy[rt << 1 | 1] += lazy[rt];
 63         
 64         lazy[rt << 1] %= mod;
 65         lazy[rt << 1 | 1] %= mod;
 66         
 67         
 68         tree_mul[rt << 1] += 
 69         (2ll * lazy[rt] * tree_sum[rt << 1] % mod + 
 70         1ll * ln * lazy[rt] % mod * lazy[rt] % mod) % mod;
 71         
 72         tree_mul[rt << 1] %= mod;
 73         
 74         tree_mul[rt << 1 | 1] += 
 75         (2ll * lazy[rt] * tree_sum[rt << 1 | 1] % mod + 
 76         1ll * rn * lazy[rt] % mod * lazy[rt] % mod) % mod; 
 77         
 78         tree_mul[rt << 1 | 1] %= mod;
 79         
 80         tree_sum[rt << 1] += 1ll * ln * lazy[rt] % mod;
 81         tree_sum[rt << 1] %= mod;
 82         tree_sum[rt << 1 | 1] += 1ll * rn * lazy[rt] % mod;
 83         tree_sum[rt << 1 | 1] %= mod;
 84         
 85         lazy[rt] = 0;
 86     }
 87     
 88     return;
 89 }
 90 void update(int rt,int l,int r,int L,int R,int c) {
 91     if(L <= l && R >= r) {//先处理区间平方和 
 92         lazy[rt] += c;
 93         lazy[rt] %= mod;
 94         
 95         tree_mul[rt] += (2ll * c * tree_sum[rt] % mod + 1ll * (r - l + 1) * c % mod * c % mod) % mod;
 96         tree_mul[rt] %= mod;
 97         
 98         tree_sum[rt] += 1ll * c * (r - l + 1) % mod; 
 99         tree_sum[rt] %= mod;
100         return;
101     }
102     int mid = (l + r) >> 1;
103     pushdown(rt,mid - l + 1,r - mid);
104     if(L <= mid) update(rt << 1,l,mid,L,R,c);
105     if(R > mid) update(rt << 1 | 1,mid + 1,r,L,R,c);
106     pushup(rt);
107 }
108 void change(int rt,int l,int r,int L,int R) {
109     if(L <= l && R >= r) {
110         tree_sum[rt] = -tree_sum[rt];
111         lazy[rt] = -lazy[rt];
112         tag[rt] ^= 1;
113         return;
114     }
115     int mid = (l + r) >> 1;
116     pushdown(rt,mid - l + 1,r - mid);
117     
118     if(L <= mid) change(rt << 1,l,mid,L,R);
119     if(R > mid) change(rt << 1 | 1,mid + 1,r,L,R);
120     pushup(rt);
121 }
122 ll query_sum(int rt,int l,int r,int L,int R) {
123     if(L <= l && R >= r) return (tree_sum[rt] + mod) % mod;
124     ll ret = 0;
125     int mid = (l + r) >> 1;
126     pushdown(rt,mid - l + 1,r - mid);
127     if(L <= mid) ret += query_sum(rt << 1,l,mid,L,R),ret %= mod;
128     if(R > mid) ret += query_sum(rt << 1 | 1,mid + 1,r,L,R),ret %= mod;
129     return (ret + mod) % mod;
130 }
131 ll query_mul(int rt,int l,int r,int L,int R) {
132     if(L <= l && R >= r) return (tree_mul[rt] + mod) % mod;
133     ll ret = 0;
134     int mid = (l + r) >> 1;
135     pushdown(rt,mid - l + 1,r - mid);
136     if(L <= mid) ret += query_mul(rt << 1,l,mid,L,R),ret %= mod;
137     if(R > mid) ret += query_mul(rt << 1 | 1,mid + 1,r,L,R),ret %= mod;
138     return (ret + mod) % mod;
139 }
140 
141 signed main() {
142     freopen("game.in","r",stdin);
143     freopen("game.out","w",stdout);
144     n = read(),m = read();
145     for(int i = 1;i <= n;++i) a[i] = read();
146     build(1,1,n);
147     while(m--) {
148         int opt = read();
149         if(opt == 1) {
150             int l = read(),r = read(),c = read();
151             update(1,1,n,l,r,c);
152         }
153         else if(opt == 2) {
154             int l = read(),r = read();
155             change(1,1,n,l,r);
156         }
157         else {
158             int l = read(),r = read(),k = read();
159             if(k == 1) printf("%I64d\n",query_sum(1,1,n,l,r));
160             else {
161                 int x = query_sum(1,1,n,l,r);
162                 int y = query_mul(1,1,n,l,r);
163                 printf("%I64d\n",((1ll * x * x % mod - y) % mod * ni % mod + mod) % mod);
164             }
165         }
166     }
167     return 0;
168 }

wxy jj Code

T3：秀秀和哺噜国（ cut ）

时间限制：1s
空间限制：512MB
【问题描述】
哺噜国里有!个城市，有的城市之间有高速公路相连。在最开始时，哺噜国里有! − 1条高
速公路，且任意两座城市之间都存在一条由高速公路组成的通路。
由于高速公路的维护成本很高，为了减少哺噜国的财政支出，将更多的钱用来哺育小哺噜，
秀秀女王决定关闭一些高速公路。但是为了保证哺噜国居民的正常生活，不能关闭太多的高速
公路，要保证每个城市可以通过高速公路与至少k个城市（包括自己）相连。
在得到了秀秀女王的指令后，交通部长华华决定先进行预调研。华华想知道在满足每个城
市都可以与至少k个城市相连的前提下，有多少种关闭高速公路的方案（可以一条也不关）。两
种方案不同，当且仅当存在一条高速公路在一个方案中被关闭，而在另外一个方案中没有被关
闭。
由于方案数可能很大，你只需输出不同方案数对786433取模后的结果即可。其中786433 =
6×2 -. + 1。
【输入格式】
从文件 cut.in 中读入数据。
输入第一行，包含两个正整数n, k。
接下来的n − 1行，每行包含两个正整数u和v，表示城市1和城市2之间有一条高速公路相
连。
【输出格式】
输出文件到 cut.out 中。
输出一个非负整数，表示所求方案数对 786433 取模后的结果。
【样例 1 输入】
5 2
1 2
2 3
3 4
4 5
【样例 1 输出】
3
【样例 1 解释】
三种方案分别为：
一条高速公路也不关闭；
关闭城市 2 和城市 3 之间的高速公路；
关闭城市 3 和城市 4 之间的高速公路。
【样例 2 输入】
10 2
1 2
1 3
2 4
2 5
3 6
3 7
3 10
5 8
6 9
【样例 2 输出】
12
【子任务】
对于20%的数据：n ≤ 20;
另有30%的数据：n≤ 100;
另有10%的数据：k ≤ 100;
另有20%的数据：n ≤ 1000;
对于100%的数据：n ≤ 5000,k ≤ n。

【Solution】

考虑用树形𝑑𝑝来解决这道问题。
设𝑓[𝑖][𝑗] 表示在𝑖的子树中𝑖所在的连通块大小为𝑗，且其他连通块大小均符合要求的删边方案数
对于每个点𝑖我们一棵一棵地将其子树加进来，设新加入子树的根为𝑢
若删除𝑢与𝑖之间的边，则用𝑓[𝑖][𝑗] * sum(𝑓[𝑢][𝑠]) s \in [k,n] 去更新𝑓[𝑖][𝑗]
若不删𝑢与𝑖之间的边，则枚举𝑢所在连通块的大小𝑠，并更新𝑓[𝑖][𝑗+𝑠]
时间复杂度 O(𝑛^3) ？
考虑一个优化：每次新加一颗子树时，𝑗只需枚举到前面已经加进来的子树大小之和，𝑠也只需枚举到新子树的大小
这只是一个常数优化？其实每个点对相当于只在𝑙𝑐𝑎处被算了一次
故优化后的时间复杂度是O（𝑛^2)的,本题得以解决。

【Code】

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #define N 5555
 4 #define M 786433
 5 using namespace std;
 6 typedef long long LL;
 7 struct edge
 8 {
 9     int t,n;
10 }e[N*2];
11 LL h[N],size[N],f[N][N],g[N],cnt[N];
12 int n,K,tote;
13 void add(int u,int v)
14 {
15     e[++tote].t=v;
16     e[tote].n=h[u];
17     h[u]=tote;
18     return ;
19 }
20 void dfs(int u,int fa)
21 {
22     size[u]++; f[u][1]=1;
23     for (int i=h[u];i;i=e[i].n)
24     {
25         int v=e[i].t;
26         if (v==fa) continue;
27         dfs(v,u);
28         for (int j=1;j<=size[u]+size[v];j++) g[j]=0;
29         for (int j=1;j<=size[u];j++) g[j]=cnt[v]*f[u][j]%M;
30         for (int j=1;j<=size[u];j++)
31         for (int k=1;k<=size[v];k++) g[j+k]=(g[j+k]+f[u][j]*f[v][k]%M)%M;
32         for (int j=1;j<=size[u]+size[v];j++) f[u][j]=g[j];
33         size[u]+=size[v];
34     }
35     for (int i=K;i<=size[u];i++) cnt[u]=(cnt[u]+f[u][i])%M;
36     return ;
37 }
38 int main()
39 {
40     freopen("cut.in","r",stdin);
41     freopen("cut.out","w",stdout);
42     scanf("%d %d",&n,&K);
43     for (int i=1;i<n;i++)
44     {
45         int u,v;
46         scanf("%d %d",&u,&v);
47         add(u,v); add(v,u);
48     }
49     dfs(1,1);
50     printf("%d\n",cnt[1]);
51     fclose(stdin);
52     fclose(stdout);
53     return 0;
54 }