GDOI2018 Day1 题目总结
分类:
IT文章
•
2022-07-18 10:29:57
T1：农场
题意：有一个长为 $n$ 的序列 $a$，要求将其分成尽可能多的部分，使得每一部分的 $a_i$ 的和相等。求最多能分成的部分数。
$30\%:1le nle 1000$
$80\%:1le nle 10^5$
$100\%:1le a_ile 10,1le sum a_ile 10^6$
这题不难，说一下我在考场的思路：
首先答案应该是 $sum a_i$ 的约数。那么可以转化一下，变成找到满足要求的最小的和（也是其约数）
进一步想到前缀和。我们发现 $x$ 满足条件，当且仅当 $x,2x,3xdots$ 全部在前缀和中出现。
于是考场上写了个80分的暴力 $O(nsqrt{n})$（枚举约数 $O(sqrt{n})$，判断 $O(n)$）
后来发现可以做到更快：因为总和不超过 $10^6$，因此可以开桶。复杂度 $O(sigma(n))<O(nlog n)$。
但是 $O(nsqrt{n})$ 可以过？
![]()
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,sum;
4 int fac[1010],fl;
5 bool vis[1000100];
6 void split(int x){ //求出总和的所有约数
7 for(int i=1;i*i<=x;i++)
8 if(x%i==0){
9 fac[++fl]=i;
10 if(i*i!=x) fac[++fl]=x/i;
11 }
12 sort(fac+1,fac+fl+1);
13 }
14 int main(){
15 scanf("%d",&n);
16 for(int i=1;i<=n;i++){
17 int a;
18 scanf("%d",&a);
19 sum+=a;
20 vis[sum]=true; //对前缀和开桶
21 }
22 split(sum);
23 for(int i=1;i<=fl;i++){
24 bool flag=true;
25 for(int j=fac[i];j<=sum;j+=fac[i]) //判断是否满足
26 if(!vis[j]){ //不满足
27 flag=false;break;
28 }
29 if(flag){
30 printf("%d
",sum/fac[i]);return 0; //答案为总和/单个和=段数
31 }
32 }
33 }
View Code
T2：密码锁
题意：有一个长为 $n$ 的序列 $a$，每一次操作可以让区间 $[l,r]$ 间所有 $a_i$ 加一或所有 $a_i$ 减一 $pmod m$。问最少多少次操作可以让序列变为全 $0$。
测试点 1~4：$1le nle 4,2le mle 10$
测试点 5~9： $1le nle 10^5,2le mle 3$
测试点 10~15：$2le n,mle 3000$
测试点 16~18：$2le nle 2 imes 10^5$
全部20个测试点：$1le nle 10^6,2le mle 10^9$
这题很有思维难度。像我这种考场上连20分BFS都没想到，写了个 $summin(a_i,m-a_i)$ 的……居然还有5分
看到区间加减操作，想到差分（设为 $d,d_i=(a_i-a_{i-1})operatorname{mod}m(ile n),d_{n+1}=m-a_n$）。
把 $a_{i-1}$ 进行 $d_i$ 次加操作后可以变成 $a_i$，或者进行 $m-d_i$ 次减操作后可以变成 $a_i$。
所以想到一个贪心：优先对 $d_i$ 小的进行加操作，剩下的进行减操作。
而对一个区间 $[l,r]$ 进行 $x$ 次操作实际上就是 $d_l-=x,d_{r+1}+=x$，整个序列变为 $0$ 就是 $d$ 变为全 $0$。
又因为每次操作都是一加一减，所以对 $d$ 进行的加操作次数等于减操作次数。
那么问题的本质就是把 $d_i$ 进行分组，使得第一组的 $sum d_i$ 等于第二组的 $sum m-d_i$。此时答案也就是这个相等的和。
结合刚刚那个贪心的想法，只需要把 $d_i$ 排序，枚举断点 $p$，分成 $ile p$ 和 $i>p$ 两组。当这两组的和相等时这个和就是答案。
直接枚举断点再求和还不够，加上前缀和和后缀和就可以了。复杂度 $O(nlog n)$。
注：$d_{n+1}=m-a_n$ 一定也要考虑，否则会导致 $[l,n]$ 的操作没有意义。
![]()
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 int n,m,a[1000100],dif[1000100]; //dif是差分
5 ll sum,pre[1000100]; //pre是差分排序后的前缀和
6 int main(){
7 scanf("%d%d",&n,&m);
8 for(int i=1;i<=n;i++){
9 scanf("%d",a+i);
10 dif[i]=(a[i]-a[i-1]+m)%m;
11 }
12 dif[n+1]=(m-a[n])%m; //注意，这个不能漏
13 sort(dif+1,dif+n+2);
14 for(int i=1;i<=n+1;i++) pre[i]=pre[i-1]+dif[i]; //做前缀和
15 for(int i=n+1;i>=1;i--){
16 sum+=m-dif[i]; //做后缀和
17 if(sum==pre[i-1]){ //前缀和和后缀和相等，这就是答案
18 printf("%lld
",sum);return 0;
19 }
20 }
21 }
View Code
T3：涛涛摘苹果
题意：有一棵 $n$ 个节点的苹果树，根节点为 $1$，初始每个点都有一个重为 $a_i$ 的苹果。每天早上根节点的苹果会消失。每天下午所有苹果都会下落一层（也就是下落到它的父亲节点上）。某些天（第 $t$ 天）的晚上编号 $x$ 的点上会多长出一个重为 $w$ 的苹果，这样的操作共有 $m$ 个。某些天（第 $t$ 天）早晨根节点苹果消失前会询问以 $x$ 为根的子树中所有苹果的重量之和，共有 $q$ 个询问。
$10\%:$ 所有输入数据都不超过 $5000$
另 $10\%:$ 树退化成一条链，其中 $i$ 与 $i-1$ 有边
另 $20\%:$ 所有询问满足 $x=1$
另 $20\%:m=0$
$100\%:$ 所有输入数据都不超过 $10^5$
先考虑 $m=0$ 怎么做：
我们发现苹果 $x$ 对第 $t$ 天在节点 $y$ 的询问产生贡献，当且仅当：（$sz[x]$ 表示 $x$ 的子树大小，$dfn[x]$ 表示 $x$ 的dfs序，$dep[x]$ 表示 $x$ 的深度）
$dep[x]ge dep[y]+t-1$
$dfn[y]le dfn[x]le dfn[y]+sz[y]-1$
那么就可以乱搞了。（既然不是正解，不说做法了，其实是我不会）
$m
e 0$ 时，根据条件 $1$，我们发现添加的苹果 $x$ 相较其它苹果少下落了 $t$ 天，可以想象从 $x$ 新连出一个节点 $y$，使得 $dep[y]=dep[x]+t$，也就是从 $x$ 连出一条权 $t$ 的边。
根据条件 $2$，他应该在子树内，连出一条边恰好符合要求。
但这样不够，还有一个时间限制！只有添加操作的 $tle$ 询问操作的 $t-1$，才能产生贡献。
现在是个三维偏序，CDQ即可。
时间复杂度：$O((n+m+q)log^2(n+m+q))$
![]()
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn=100010;
5 #define FOR(i,a,b) for(int i=(a);i<=(b);i++)
6 #define ROF(i,a,b) for(int i=(a);i>=(b);i--)
7 inline int read(){
8 char ch=getchar();int x=0,f=0;
9 while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
10 while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
11 return f?-x:x;
12 }
13 int n,m,q,cnt;
14 int el,head[maxn*2],to[maxn*3],w[maxn*3],nxt[maxn*3];
15 int dep[maxn*2],sz[maxn*2],dfn[maxn*2];
16 ll ans[maxn],bit[maxn*2];
17 struct oper{ //tp=0表示修改，tp=1表示询问，tim表示时间，x表示节点，w表示权值（可能没有），id表示原编号
18 int tp,tim,x,w,id;
19 }op[maxn*3];
20 inline void add(int u,int v,int w_){
21 to[++el]=v;w[el]=w_;nxt[el]=head[u];head[u]=el;
22 }
23 inline bool cmptim(const oper &o1,const oper &o2){ //注意只有修改会对询问产生贡献，所以时间一样的要把修改放前面
24 if(o1.tim!=o2.tim) return o1.tim<o2.tim;
25 return o1.tp<o2.tp;
26 }
27 inline bool cmpdep(const oper &o1,const oper &o2){
28 return dep[o1.x]>dep[o2.x];
29 }
30 inline bool cmphhh(const oper &o1,const oper &o2){ //各种排序
31 return dep[o1.x]+o1.tim>dep[o2.x]+o2.tim;
32 }
33 inline void modify(int p,int v){
34 for(;p<=n+m;p+=p&-p) bit[p]+=v;
35 }
36 inline ll query(int p){
37 ll ans=0;for(;p;p-=p&-p) ans+=bit[p];return ans;
38 }
39 inline ll query(int l,int r){
40 return query(r)-query(l-1);
41 } //以上树状数组
42 void dfs(int u,int f){ //预处理dep,dfn,sz
43 sz[u]=1;dfn[u]=++cnt;
44 for(int i=head[u];i;i=nxt[i]){
45 int v=to[i];
46 if(v==f) continue;
47 dep[v]=dep[u]+w[i];
48 dfs(v,u);sz[u]+=sz[v];
49 }
50 }
51 void CDQ(int l,int r){ //CDQ分治
52 if(l==r) return;
53 int mid=(l+r)>>1;
54 CDQ(l,mid);CDQ(mid+1,r);
55 sort(op+l,op+mid+1,cmpdep); //左边按照dep排序
56 sort(op+mid+1,op+r+1,cmphhh); //右边按照dep+time排序
57 int cl=l;
58 FOR(i,mid+1,r){
59 for(;cl<=mid && dep[op[cl].x]>=dep[op[i].x]+op[i].tim-1;cl++) //cl能对i产生贡献
60 if(op[cl].tp==1) modify(dfn[op[cl].x],op[cl].w); //是修改，插入树状数组
61 if(op[i].tp==2) ans[op[i].id]+=query(dfn[op[i].x],dfn[op[i].x]+sz[op[i].x]-1); //是询问，添加贡献
62 }
63 FOR(i,l,cl-1) if(op[i].tp==1) modify(dfn[op[i].x],-op[i].w); //清空树状数组
64 }
65 int main(){
66 n=read();m=read();q=read();
67 FOR(i,1,n) op[i]=(oper){1,1,i,read(),0}; //一开始的苹果也可以看成是添加操作
68 FOR(i,1,n-1){
69 int u=read(),v=read();
70 add(u,v,1);add(v,u,1); //边权为1
71 }
72 FOR(i,1,m){
73 int t=read(),x=read(),w=read();
74 add(x,i+n,t); //连虚边
75 op[i+n]=(oper){1,t+1,i+n,w,0}; //添加操作（把时间设为t+1会更方便排序）
76 }
77 FOR(i,1,q){
78 int t=read(),x=read();
79 op[i+n+m]=(oper){2,t,x,0,i}; //询问操作
80 }
81 dfs(1,0);
82 sort(op+1,op+n+m+q+1,cmptim); //按时间排序
83 CDQ(1,n+m+q);
84 FOR(i,1,q) printf("%lld
",ans[i]);
85 }
View Code
