参考资料:
[1]:官方题解(提取码:5kim)
[2]:标程(提取码:76lh)
A.meeting(树的直径)
•题意
有一颗由 n 个节点组成的树;
树上标记了 k 个点;
求树上某个节点到这 k 个点的最远距离的最小值;
•题解
•Code
View Code1 #include<bits/stdc++.h> 2 using namespace std; 3 #define mem(a,b) memset(a,b,sizeof(a)) 4 const int maxn=1e5+50; 5 6 int n,k; 7 int num; 8 int head[maxn]; 9 struct Edge 10 { 11 int to; 12 int next; 13 }G[maxn<<1]; 14 void addEdge(int u,int v) 15 { 16 G[num]={v,head[u]}; 17 head[u]=num++; 18 } 19 int x[maxn]; 20 int dis[maxn]; 21 22 void DFS(int u,int f,int d) 23 { 24 dis[u]=d; 25 for(int i=head[u];~i;i=G[i].next) 26 { 27 int v=G[i].to; 28 29 if(v != f) 30 DFS(v,u,d+1); 31 } 32 } 33 int Solve() 34 { 35 if(k <= 1) 36 return 0; 37 38 DFS(x[1],x[1],0); 39 40 int cur=x[1]; 41 for(int i=1;i <= k;++i) 42 if(dis[cur] < dis[x[i]]) 43 cur=x[i]; 44 45 DFS(cur,cur,0); 46 47 int ans=0; 48 for(int i=1;i <= k;++i) 49 ans=max(ans,dis[x[i]]); 50 51 return (ans+1)/2; 52 } 53 void Init() 54 { 55 num=0; 56 mem(head,-1); 57 } 58 int main() 59 { 60 Init(); 61 scanf("%d%d",&n,&k); 62 63 for(int i=1;i < n;++i) 64 { 65 int u,v; 66 scanf("%d%d",&u,&v); 67 68 addEdge(u,v); 69 addEdge(v,u); 70 } 71 for(int i=1;i <= k;++i) 72 scanf("%d",x+i); 73 74 printf("%d\n",Solve()); 75 76 return 0; 77 }
B.xor(线性基求交+线段树区间查询)
•题意
给你 n 个集合,每个集合中都有不超过 32 个数;
m 次询问,每次询问区间 [L, R] 中的所有集合,是否都有一个异或和等于 x 的子集。
$n ≤\le≤ 5e4\ ,\ m \le 5e4$,所有数值域 [0,232)。
•题解
线段树维护区间所有基底的交集;
然后 O(log n) 解决询问;
所以说,这道题的难点在于如何快速求解不同基底的交集,可以参考一下我的这篇博客;
•Code
View Code1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ls(x) (x<<1) 4 #define rs(x) (x<<1|1) 5 #define ll long long 6 #define mem(a,b) memset(a,b,sizeof(a)) 7 const int maxn=5e4+50; 8 9 int n,m; 10 struct Seg 11 { 12 int l,r; 13 ll base[40]; 14 int mid(){return l+((r-l)>>1);} 15 void Init() 16 { 17 mem(base,0); 18 } 19 void Insert(ll x) 20 { 21 for(int i=32;i >= 0;--i) 22 if(x>>i&1) 23 { 24 if(!base[i]) 25 { 26 base[i]=x; 27 return ; 28 } 29 x ^= base[i]; 30 } 31 } 32 bool Find(ll x) 33 { 34 for(int i=32;i >= 0;--i) 35 if(x>>i&1) 36 x ^= base[i]; 37 return x == 0 ? true:false; 38 } 39 }seg[maxn<<2]; 40 41 void pushUp(int pos)///将ls(pos),rs(pos)的base的交集更新到pos的base上 42 { 43 ll all[40]; 44 ll B[40]; 45 memcpy(all,seg[ls(pos)].base,sizeof(all)); 46 mem(B,0); 47 48 for(int i=32;i >= 0;--i) 49 { 50 ll x=seg[rs(pos)].base[i]; 51 ll y=x; 52 53 for(int j=32;j >= 0;--j) 54 if(x>>j&1) 55 { 56 if(!all[j]) 57 { 58 all[j]=x; 59 B[j]=y; 60 break; 61 } 62 x ^= all[j]; 63 y ^= B[j]; 64 } 65 if(!x) 66 seg[pos].Insert(y); 67 } 68 } 69 void build(int l,int r,int pos) 70 { 71 seg[pos]={l,r}; 72 seg[pos].Init(); 73 74 if(l == r) 75 { 76 int siz; 77 scanf("%d",&siz); 78 for(int i=1;i <= siz;++i) 79 { 80 ll x; 81 scanf("%lld",&x); 82 seg[pos].Insert(x); 83 } 84 return ; 85 } 86 87 int mid=seg[pos].mid(); 88 build(l,mid,ls(pos)); 89 build(mid+1,r,rs(pos)); 90 91 pushUp(pos); 92 } 93 bool query(int pos,int l,int r,ll x)///查询[l,r]区间的所有集合的子集是否都可以异或出x 94 { 95 if(seg[pos].l == l && seg[pos].r == r) 96 return seg[pos].Find(x); 97 98 int mid=seg[pos].mid(); 99 if(r <= mid) 100 return query(ls(pos),l,r,x); 101 else if(l > mid) 102 return query(rs(pos),l,r,x); 103 else 104 return query(ls(pos),l,mid,x)&query(rs(pos),mid+1,r,x); 105 } 106 void Solve() 107 { 108 build(1,n,1); 109 110 while(m--) 111 { 112 int l,r; 113 ll x; 114 scanf("%d%d%lld",&l,&r,&x); 115 116 if(query(1,l,r,x)) 117 puts("YES"); 118 else 119 puts("NO"); 120 } 121 } 122 int main() 123 { 124 scanf("%d%d",&n,&m); 125 Solve(); 126 127 return 0; 128 }
C.sequence(单调栈+线段树)
•题意
给你两个数组 a,b;
求 $max_{l}^{r} \big\{ min(a_{l},...,a_{r}) \cdot \sum_{l}^{r}b_{i} \big\}$ , 1 ≤ l ≤ r ≤ n;
•题解
这道题和之前做的一道题(2019南昌网络预选赛)很相似,几乎就是一样的题;
通过单调栈求出以 $a_{i}$ 为最小值的最大范围 [L,R];
在 [L,R] 内:
①如果 ai > 0,那么,就需要找 [L,R] 内包含 ai 的 $sum_{max}$;
②反之,如果 ai ≤ 0,那么,就需要找 [L,R] 内包含 ai 的 $sum_{min}$;
如何快速求解 $sum_{max}$ 和 $sum_{min}$ 呢?
对于情况①而言,$sum_{max}$ = max{ sumi,sumi+1,...,sumR}-min{ sumL-1,.....,sumi-1};
而对于情况②而言,正好与①相反,$sum_{min}$ = min{ sumi,sumi+1,...,sumR}-max{ sumL-1,.....,sumi-1};
看着求解公式有没有种线段树区间查询的味道?
•Code
View Code1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ls(x) (x<<1) 4 #define rs(x) (x<<1|1) 5 #define mem(a,b) memset(a,b,sizeof(a)) 6 #define ll long long 7 #define INFll 0x3f3f3f3f3f3f3f3f 8 const int maxn=3e6+50; 9 10 int n; 11 int a[maxn]; 12 int b[maxn]; 13 int l[maxn]; 14 int r[maxn]; 15 ll sum[maxn]; 16 int sta[maxn]; 17 struct Seg 18 { 19 int l,r; 20 ll Max; 21 ll Min; 22 int mid(){return l+((r-l)>>1);} 23 }seg[maxn<<2]; 24 void pushUp(int pos) 25 { 26 seg[pos].Max=max(seg[ls(pos)].Max,seg[rs(pos)].Max); 27 seg[pos].Min=min(seg[ls(pos)].Min,seg[rs(pos)].Min); 28 } 29 void buildSeg(int l,int r,int pos) 30 { 31 seg[pos].l=l; 32 seg[pos].r=r; 33 34 if(l == r) 35 { 36 seg[pos].Max=seg[pos].Min=sum[l]; 37 return ; 38 } 39 40 int mid=l+((r-l)>>1); 41 buildSeg(l,mid,ls(pos)); 42 buildSeg(mid+1,r,rs(pos)); 43 44 pushUp(pos); 45 } 46 ll queryMax(int l,int r,int pos) 47 { 48 if(seg[pos].l == l && seg[pos].r == r) 49 return seg[pos].Max; 50 51 int mid=seg[pos].mid(); 52 53 if(r <= mid) 54 return queryMax(l,r,ls(pos)); 55 else if(l > mid) 56 return queryMax(l,r,rs(pos)); 57 else 58 return max(queryMax(l,mid,ls(pos)),queryMax(mid+1,r,rs(pos))); 59 } 60 ll queryMin(int l,int r,int pos) 61 { 62 if(seg[pos].l == l && seg[pos].r == r) 63 return seg[pos].Min; 64 65 int mid=seg[pos].mid(); 66 67 if(r <= mid) 68 return queryMin(l,r,ls(pos)); 69 else if(l > mid) 70 return queryMin(l,r,rs(pos)); 71 else 72 return min(queryMin(l,mid,ls(pos)),queryMin(mid+1,r,rs(pos))); 73 } 74 void Work() 75 { 76 int k=0; 77 for(int i=1;i <= n;++i) 78 { 79 while(k > 0 && a[sta[k]] >= a[i]) 80 k--; 81 82 l[i]=k == 0 ? 1:sta[k]+1; 83 sta[++k]=i; 84 } 85 86 k=0; 87 for(int i=n;i >= 1;--i) 88 { 89 while(k > 0 && a[sta[k]] >= a[i]) 90 k--; 91 92 r[i]=k == 0 ? n:sta[k]-1; 93 sta[++k]=i; 94 } 95 } 96 97 ll Solve() 98 { 99 buildSeg(0,n,1);///线段树 100 Work();///单调栈 101 102 ll ans=-INFll; 103 for(int i=1;i <= n;++i) 104 { 105 if(a[i] > 0) 106 { 107 ll x=queryMax(i,r[i],1); 108 ll y=queryMin(l[i]-1,i-1,1); 109 110 ans=max(ans,(x-y)*a[i]); 111 } 112 else 113 { 114 ll x=queryMin(i,r[i],1); 115 ll y=queryMax(l[i]-1,i-1,1); 116 117 ans=max(ans,(x-y)*a[i]); 118 } 119 } 120 return ans; 121 } 122 123 int main() 124 { 125 scanf("%d",&n); 126 127 for(int i=1;i <= n;++i) 128 scanf("%d",a+i); 129 130 sum[0]=0; 131 for(int i=1;i <= n;++i) 132 { 133 scanf("%d",b+i); 134 sum[i]=sum[i-1]+b[i]; 135 } 136 137 printf("%lld\n",Solve()); 138 return 0; 139 }
•段子
比赛的时候,求解区间最值用的是 ST 表,MLE 有没有.......
然后询问出题人:
用 ST 表提交的时候,那是一个惨呀;
内存超限了好几次,然后,想试一下运气,万一数据里的 n 都是小于 1e6 的呢;
然后,就有了 AC 前的一个 WA;
然后,突然,脑洞大开,为啥不用线段树呢!!!!
D.triples(构造)
•题意
给你 a,求满足 x%3 == 0 , y%3 == 0 , x | y = a 的 x,y;
输出 x,y;
•题解
将 a 用二进制数表示为:
$a=2^{k_1}+2^{k_2}+...+2^{k_n}$;
也就是说,如果 a%3 ≠ 0,那么 n ≥ 3;
那么,对于任意一位 $2^{k_i}$ 有:
$2^{k_i}\ mod\ 3=1\ or\ 2$;
假设 $2^{k_i}\ mod\ 3=1$ 有:
$2^{f_1},2^{f_2},...,2^{f_x}$;
$2^{k_i}\ mod\ 3=2$ 有:
$2^{g_1},2^{g_2},...,2^{g_y}$;
①如果 a%3 == 0
直接输出 a;②如果 a%3 == 1
1)x > 1
构造 $ans1=a-2^{f_1},ans2=a-2^{f_2}$;
2)x == 1
构造 $ans1=a-2^{f_1},ans2=a-2^{g_1}-2^{g_2}$;
3)x == 0
那么,y > 3,因为如果 y == 3 ,那么 a%3 == 0;
构造 $ans1=a-2^{g_1}-2^{g_2},ans2=a-2^{g_3}-2^{g_4}$;
或者构造 $ans1=a-2^{g_1}-2^{g_2},ans2=2^{g_1}+2^{g_2}+2^{g_3}$;
③如果 a%3 == 2
与 a%3 == 1 正好对称;
解释:为什么要做减法,而不做加法?
如果做加法的话,会产生进位,那么,ans1 | ans2 后可能大于 a;
•Code
View Code1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 5 ll a; 6 vector<ll >v[3]; 7 8 void Solve() 9 { 10 if(a%3 == 0) 11 { 12 printf("1 %lld\n",a); 13 return ; 14 } 15 16 v[1].clear(); 17 v[2].clear(); 18 19 for(int i=0;i < 62;++i) 20 { 21 ll k=1ll*1<<i; 22 if(a&k) 23 v[k%3].push_back(k); 24 } 25 26 ll ans1,ans2; 27 if(a%3 == 1) 28 { 29 if(v[1].size() > 1) 30 ans1=a-v[1][0],ans2=a-v[1][1]; 31 else if(v[1].size()) 32 ans1=a-v[1][0],ans2=a-v[2][0]-v[2][1]; 33 else 34 ans1=a-v[2][0]-v[2][1],ans2=a-v[2][2]-v[2][3]; 35 } 36 else 37 { 38 if(v[2].size() > 1) 39 ans1=a-v[2][0],ans2=a-v[2][1]; 40 else if(v[2].size()) 41 ans1=a-v[2][0],ans2=a-v[1][0]-v[1][1]; 42 else 43 ans1=a-v[1][0]-v[1][1],ans2=a-v[1][2]-v[1][3]; 44 } 45 printf("2 %lld %lld\n",ans1,ans2); 46 } 47 int main() 48 { 49 int test; 50 scanf("%d",&test); 51 while(test--) 52 { 53 scanf("%lld",&a); 54 Solve(); 55 } 56 return 0; 57 }
K.number(思维)
•题意
给你一个 串s,s 由 '0'~'9' 的数字组成;
求能整除 300 的不同的子串的个数;
对于相同内容的子串,如果含有位置不同的字符,当作不同子串处理;
并且可以有前导0;
•题解
能被 3 整除的数的特征为:各个位上的加和可以被 3 整除;
由于本题要找的是可以被 300 整除的串的个数;
那么,满足条件的子串肯定以 ≥ 两个0 结尾;
那么,关注点就在找连续的 0,并且连续的 0 的个数 ≥ 2 的位置;
每次从当前的 0 向前遍历,找包含当前位置 0 的满足条件的子串的个数;
注意,串 0300 也是满足条件的;
定义 zero[ i ] 表示以 i 位置为结尾的连续的 0 的个数;
sum[ i ] 表示 [1,i] 中包含第 i 个 0 且不能全部为 0 的满足条件的子串的个数;
例如:12300032100 (下标从 1 开始)
zero[4]=1 , zero[5]=2 , zero[6]=3 , zero[10]=1 , zero[11]=2;
zero[other]=0;
sum[6]=2 , sum[11]=7;
sum[other]=0;
sum[6]包含的子串为:3000,123000(不包含0,00,000这种情况,这种情况单独处理);
为什么 sum[11]=7 呢?
2100 , 32100 , 032100 , 0032100 , 00032100 , 300032100 , 12300032100;
你会发现,其实,你会发现在这种条件下,只有 2100,32100 需要遍历找到,其余的都可以通过前面的信息找到;
sum[11] = 2 + sum[6] + zero[6] = 7;
你发现啥了没?
可以重用之前求的数据;
但是不是符合所有情况?
答案是否定的;
例如:12300021100
此时 sum[11] = 1; (2300021100)
也就是说,只有当 cur (cur = s[7]+s[8]+s[9] = 3+2+1 = 6,第一个例子) 整除 3 时才能重用之前求得的数据;
不然,如果 cur ( cur = s[7]+s[8]+s[9] = 2+1+1 = 4,第二个例子) 不整除 3,那么,就只有接着向前遍历了;
当然,最后不要忽略了只包含 0 得情况;
•Code
View Code1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define mem(a,b) memset(a,b,sizeof(a)) 5 const int maxn=1e5+50; 6 7 char s[maxn]; 8 ll zero[maxn]; 9 ll sum[maxn]; 10 11 ll Solve() 12 { 13 mem(zero,0); 14 mem(sum,0); 15 16 ll ans=0; 17 18 int len=strlen(s+1); 19 int index=1; 20 21 while(index <= len) 22 { 23 for(;index <= len && s[index] != '0';index++); 24 25 for(;index <= len && s[index] == '0';index++) 26 zero[index]=zero[index-1]+1; 27 28 ll n=zero[index-1];///以index-1结尾的连续的0的个数 29 30 if(n > 1) 31 { 32 33 ll cur=0; 34 ll cnt=0; 35 36 int i=index-n-1; 37 while(i >= 1) 38 { 39 if(zero[i] > 1 && cur%3 == 0)///只有当cur%3==0时才能重用数据 40 { 41 cnt += sum[i]+zero[i]; 42 break; 43 } 44 ///否则,向前遍历 45 cur += s[i]-'0'; 46 if(cur%3 == 0) 47 cnt++; 48 49 i--; 50 } 51 52 sum[index-1]=cnt; 53 54 ans += sum[index-1]*(n-1); 55 } 56 ans += n*(1+n)/2;///n个连续的0有n*(n+1)/2种串整除300 57 } 58 return ans; 59 } 60 61 int main() 62 { 63 // freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin); 64 scanf("%s",s+1); 65 66 printf("%lld\n",Solve());//23 67 return 0; 68 }
•分析
这种思路实现的代码,时间复杂度应该可以退化到 O(n2) 吧,为啥过了呢?
暴力+AC = 未出现卡这种方法的数据;
•另一种思路
定义 sumi 为前 i 为的和 mod 3 的值;
区间 [L,R] 满足条件,当且仅当 s[R] = s[R-1] = 0,并且 sumR-2 = sumL-1;
这样的话,只需记录一下 R-2 之前有多少值为 sumR-2 的即可;
也就是记录 0,1,2 的个数;
不要忘记计算全部为 0 的情况;
•Code
View Code1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 const int maxn=1e5+50; 5 6 char s[maxn]; 7 8 ll Solve() 9 { 10 ll ans=0; 11 int sum=0; 12 int index=1; 13 int cnt[3]={1,0,0}; 14 int len=strlen(s+1); 15 16 while(index <= len) 17 { 18 for(;index <= len && s[index] != '0';index++) 19 { 20 sum += s[index]-'0'; 21 sum %= 3; 22 cnt[sum]++; 23 } 24 ll zero=0; 25 for(;index <= len && s[index] == '0';zero++,index++); 26 27 ///cnt[sum]记录的是区间[1,index-1]的 0,1,2 的个数 28 ///需要减掉 index-1 对应的 sum%3 的值 29 if(zero > 1)///(zero-1)种情况,每种都有cnt[sum]-1个满足条件的子串 30 ans += (cnt[sum]-1)*(zero-1); 31 32 ans += zero*(zero+1)/2;///全为0的情况 33 34 cnt[sum] += zero; 35 } 36 return ans; 37 } 38 int main() 39 { 40 scanf("%s",s+1); 41 s[0]='#'; 42 43 printf("%lld\n",Solve()); 44 45 return 0; 46 }