Educational Codeforces Round 36题解

A Garden
B Browser
C Permute Digits
D Almost Acyclic Graph
E Physical Education Lessons
F Imbalance Value of a Tree
G Coprime Arrays

A. Garden

题意

读入 $n,k$ 以及 $n$ 个数,对于 $k\mod a_i==0$求$\max(\frac{k}{a_i})$

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
void qmax(int &x,int y) {if (x<y) x=y;}
void qmin(int &x,int y) {if (x>y) x=y;}
int read(){}
void write(int x){}
int n,k,ans;
int a[200];
int main()
{
n=read();k=read();ans=2333;
for (int i=1;i<=n;i++) a[i]=read();
for (int i=1;i<=n;i++) if (k%a[i]==0) ans=min(ans,k/a[i]);
cout<<ans;
return 0;
}

B. Browser

题意

有 $n$ 个窗口,鼠标位置在 $pos$ ,需要关掉 $l-r$ 的窗口,一次移动,一次关闭需要 $1s$ 求最小需要多少秒。

鼠标在位置 $pos$ 可以关闭窗口 $[1, i - 1]$,$[i+1,n]$

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
void qmax(int &x,int y) {if (x<y) x=y;}
void qmin(int &x,int y) {if (x>y) x=y;}
int read(){}
void write(int x){}
int ans;
int n,pos,l,r;
int main()
{
n=read();pos=read();l=read();r=read();
if (l==1&&r==n){printf("0");return 0;}
if (l==1)
{
ans=(abs(r-pos))+1;printf("%d",ans);return 0;
}
if (r==n)
{
ans=(abs(pos-l))+1;printf("%d",ans);return 0;
}
ans=min(abs(pos-l),abs(pos-r))+(r-l)+2;
printf("%d\n",ans);
return 0;
}

C. Permute Digits

题意

读入 $a,b$ ,改变 $a$ 的排列,求出最大的 $a$ 且 $a<b$

题解

把 a 拆掉从大到小排序,然后贪心的去填坑。
a,b中某一位相等的情况要注意后面按照最小的方案去填是否满足条件。
a中某一位如果小于b中该位,填完之后直接把后面的从大到小排就好。
如果a最小的排列都比b要大,直接gg
a的位数没b的位数多,直接从大到小输出。
细节不算很多。

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<bits/stdc++.h>
#define ll long long
using namespace std;
void qmax(int &x,int y) {if (x<y) x=y;}
void qmin(int &x,int y) {if (x>y) x=y;}
ll read()
{
char s;
ll k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
if(s==EOF)exit(0);if(s=='-')base=-1,s=getchar();
while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
return k*base;
}
void write(int x)
{
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}
ll n,m,s1,s2,x;
ll a[40],b[40],ans;
int bj[40],p;
bool check(int pos)//pos-1~1
{
ll ss=0,s2=0;
for (int i=pos;i>=1;i--) ss=ss*10+b[i];
bj[p]=1;s2=a[p];
for (int i=s1;i>=1;i--) if (!bj[i]) s2=s2*10+a[i];
bj[p]=0;
if (s2>ss) return false;return true;
}//看后面的从小到大填是否能满足条件
void dfs(int pos,int flag)
{
if (pos==0) return;
p=1;
while (bj[p]&&p<=s1) p++;//找到第一个有可能可以填进去的数
if (a[p]==b[pos])
{
if (check(pos))//后面填得下
{
if (a[p]!=0||flag==1)//判前导0
{
printf("%I64d",a[p]);bj[p]=1;//打标记
dfs(pos-1,1);//往后扫
} else
{
bj[p]=1;//打标记
dfs(pos-1,0);//往后扫
}
return;
}
while ((a[p]==b[pos]||bj[p])&&p<=s1) p++;//往后移
}
if (a[p]<b[pos])
{
//前导0去掉,然后打标记
if (flag==1||a[p]!=0) printf("%I64d",a[p]),flag=1;bj[p]=1;
for (p=1;p<=s1;p++)
if (!bj[p]) //一个一个填尽量填大的
{
bj[p]=1;
if (flag==1||a[p]!=0) printf("%I64d",a[p]);
if (a[p]!=0) flag=1;//前导0
}
return;
}
while ((a[p]>b[pos]||bj[p])&&p<=s1) p++;
if (a[p]==b[pos])//同上
{
if (check(pos))
{
if (a[p]!=0||flag==1)
{
printf("%d",a[p]);bj[p]=1;
dfs(pos-1,1);
} else
{
bj[p]=1;
dfs(pos-1,flag);
}
return;
}
while ((a[p]==b[pos]||bj[p])&&p<=s1) p++;
}
if (a[p]<b[pos])
{
if (flag==1||a[p]!=0) printf("%I64d",a[p]),flag=1;bj[p]=1;
for (p=1;p<=s1;p++) if (!bj[p])
{
bj[p]=1;
if (flag==1||a[p]!=0) printf("%I64d",a[p]);
if (a[p]!=0) flag=1;
}
return;
}
}
bool cmp(ll aa,ll bb)
{
return aa>bb;
}
int main()
{
n=read();m=read();
if (n<=9)
{
printf("%I64d",n);
return 0;
}
x=n;s1=s2=0;
while (x) a[++s1]=x%10,x/=10;
x=m;
while (x) b[++s2]=x%10,x/=10;
sort(a+1,a+s1+1,cmp);
p=1;
if (s2>s1)
{
for (int i=1;i<=s1;i++) printf("%I64d",a[i]);
return 0;
}
dfs(s1,0);
return 0;
}

D.Almost Acyclic Graph

题意

给你 $n$个点 $m$ 条边的有向图,问可以不可以删去至多一条边使整个图没有环($n\le 500,m\le 100,000$)

题解

这范围可以枚边,但是判环的复杂度是 $O(n+m)$的,直接gg。

开始在想如何 $O(n)$ 判环,然后发现我想多了。

对于最开始就不在任意一个环的边,可以最开始拓扑判环,然后扫的时候不管了。

对于在环内的边,x->y ,只有在删去这条边之后,y的入度变为0,去跑拓扑判环才有用。

这样最多枚 $n$ 条边

复杂度就是 $O(n*(n+m))$

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int qmax(int &x,int y) {if (x<y) x=y;}
int qmin(int &x,int y) {if (x>y) x=y;}
int read(){}
void write(int x){}
const int maxn=510;
const int maxm=101000;
int n,m,X,Y,rd[maxn],vis[maxn],flag,RD[maxn],v1[maxn];
int to[maxm],ne[maxm],bj[maxm],po[maxn],id;
queue<int> q;
inline void add(int x,int y)
{
to[++id]=y;ne[id]=po[x];po[x]=id;
}
void check()
{
while (!q.empty())
{
int u=q.front();q.pop();
vis[u]=1;
for (int i=po[u];i;i=ne[i])
{
if (!bj[i])
{
RD[to[i]]--;
if (RD[to[i]]==0) q.push(to[i]);
}
}
}
}
int main()
{
n=read();m=read();
for (int i=1;i<=m;i++) X=read(),Y=read(),add(X,Y),rd[Y]++;

for (int i=1;i<=n;i++) if (rd[i]==0) q.push(i);
while (!q.empty())
{
int u=q.front();q.pop();
v1[u]=1;
for (int i=po[u];i;i=ne[i])
{
rd[to[i]]--;
if (rd[to[i]]==0) q.push(to[i]);
}
}//最开始就扫一遍
flag=1;
for (int i=1;i<=n;i++) if (!v1[i]) {flag=0;break;}
if (flag) {printf("YES");return 0;}//最开始就没环
for (int i=1;i<=m;i++)
{
if (rd[to[i]]-1!=0) continue;//删了之后不会增加一个起点就不管
memcpy(RD,rd,sizeof(rd));
memcpy(vis,v1,sizeof(v1));
RD[to[i]]--;bj[i]=1;
while (!q.empty()) q.pop();
q.push(to[i]);
flag=1;
check();
for (int j=1;j<=n;j++) if (!vis[j]) {flag=0;break;}
if (flag) {printf("YES");return 0;}
bj[i]=0;
}
printf("NO");
return 0;
}

E. Physical Education Lessons

题意

一共有 n天,最开始n天都是工作日。

然后有m个操作,a b c,当c=1时,a->b天变成休息日,c=2时a->b天变成工作日。

题解

直接线段树。

不过要离散一下。

然后我的线段树左端点是不包括在内的,所以开始要-1。

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
void qmax(int &x,int y) {if (x<y) x=y;}
void qmin(int &x,int y) {if (x>y) x=y;}
int read(){}
void write(int x){}
int n,q,SZ,id;
int p[601000];
struct node
{
int x[2],k,y[2];
} a[300100];
struct node1
{
int x,y,z;
} Q;
vector<node1> G;
bool cmp(node1 aa,node1 bb)
{
return aa.x<bb.x;
}
int t[2400100],bj[2400100];
inline void down(int d,int l,int r)
{
int mid=(l+r)>>1;
if (bj[d]!=-1)
{
t[d<<1]=bj[d]*(p[mid]-p[l]);
t[d<<1|1]=bj[d]*(p[r]-p[mid]);

bj[d<<1]=bj[d<<1|1]=bj[d];bj[d]=-1;
}
}
void xg(int x,int y,int d,int l,int r,int BJ)
{
if (bj[d]==BJ) return;
if ((t[d]==p[r]-p[l])&&BJ==1) return;
if (t[d]==0&&BJ==0) return;
if (x<=l&&r<=y)
{
t[d]=(p[r]-p[l])*BJ;
bj[d]=BJ;
return;
}
down(d,l,r);
int mid=(l+r)>>1;
if (y<=mid) xg(x,y,d<<1,l,mid,BJ); else
if (x>=mid) xg(x,y,d<<1|1,mid,r,BJ); else
{
xg(x,mid,d<<1,l,mid,BJ);
xg(mid,y,d<<1|1,mid,r,BJ);
}
t[d]=t[d<<1]+t[d<<1|1];
}
int main()
{
n=read();q=read();
for (int i=1;i<=q;i++)
{
a[i].x[0]=read()-1,a[i].x[1]=read(),a[i].k=read();
Q.x=a[i].x[0];Q.y=i;Q.z=0;G.push_back(Q);
Q.x=a[i].x[1];Q.y=i;Q.z=1;G.push_back(Q);
}
sort(G.begin(),G.end(),cmp);
id=1;SZ=G.size()-1;
p[1]=0;
for (int i=0;i<=SZ;i++)
{
if (G[i].x!=p[id]) id++;
p[id]=a[G[i].y].x[G[i].z];
a[G[i].y].y[G[i].z]=id;
}
memset(bj,-1,sizeof(bj));
if (p[id]!=n) id++,p[id]=n;
bj[1]=1;t[1]=n;
for (int i=1;i<=q;i++)
{
a[i].k=a[i].k==1?0:1;
xg(a[i].y[0],a[i].y[1],1,1,id,a[i].k);
printf("%d\n",t[1]);
}
return 0;
}

F. Imbalance Value of a Tree

题意

一颗树,设$I(i,j)$ 表示i->j这条路径上最大的点权-最小的点权,求 $\sum\limits{i=1}^{n}\sum\limits {j=i}^{n} I(i,j)$

题解

这种题显然考虑每个点对答案的贡献。

这里只写如何求最大的点权的贡献,最小的同理。

最开始是打算用类似于点分治的方法,从点权最大的点开始,算贡献,然后分开处理每个子树,每个子树又找点权最大的。然后发现这种方法可以被卡掉。

然后又想把点权排下序,先算最大的点的贡献,然后把那个点删了,处理次大的。然后发现,这样处理找不到每颗树的size(除开重新扫一遍)。

然后看了一眼,标签,“并查集”,哦这道题不应该去分开,而应该是合并。

于是我们可以按点权从小到大排序,对于点u,设v为与u有直接连边的点。当a[u]>a[v]时,把v设为u的子树。

点u的点权,只会对 (u的其中一颗子树中的点,到其他子树的任意一个点)这条路径产生贡献。

然后不要算重了。 注意点权相同的情况下合并应该要注意细节。

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int qmax(int &x,int y) {if (x<y) x=y;}
int qmin(int &x,int y) {if (x>y) x=y;}
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
if(s=='-')base=-1,s=getchar();
while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
return k*base;
}
void write(int x)
{
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}
const int maxn=1e6+100;
const int maxm=2e6+10000;
int n,sz[maxn],a[maxn],X,Y,id,p;
int to[maxm],ne[maxm],po[maxn];
int vis[maxn];
vector<int> G[maxn];
int fa[maxn];
long long ans;
inline void add(int x,int y)
{
id++;to[id]=y;ne[id]=po[x];po[x]=id;
}
int gf(int x)
{
if (fa[x]==x) return x;
fa[x]=gf(fa[x]);
return fa[x];
}
void un(int x,int y)//y->x
{
x=gf(x);y=gf(y);
if (x==y) return;
fa[y]=x;
sz[x]+=sz[y];sz[y]=0;
}
void Qmax()
{
for (int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
p=1;
while (p<=(int)1e6)
{
int u,v,s;
while (G[p].empty()&&p<=(int)1e6) p++;
if (G[p].empty()) break;
for (int j=G[p].size()-1;j>=0;j--)
{
u=G[p][j];s=1;vis[u]=1;
for (int i=po[u];i;i=ne[i])
{
v=to[i];
if (a[v]>a[u]||(a[v]==a[u]&&!vis[v])) continue;//已经合并了,相等的时候特判
v=gf(v);//v所在的集合的大小
ans+=(ll)s*(ll)sz[v]*(ll)a[u];//算贡献
s+=sz[v];
}
for (int i=po[u];i;i=ne[i])
{
v=to[i];//合并
if (a[v]>a[u]||(a[v]==a[u]&&!vis[v])) continue;
un(u,v);
}
}
p++;
}
}
void Qmin()
{
memset(vis,0,sizeof(vis));
for (int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
p=1e6;
while (p>=1)
{
int u,v;ll s;
while (G[p].empty()&&p>=1) p--;
if (G[p].empty()) break;
for (int j=G[p].size()-1;j>=0;j--)
{
u=G[p][j];s=1;vis[u]=1;
for (int i=po[u];i;i=ne[i])
{
v=to[i];
if (a[v]<a[u]||(a[v]==a[u]&&!vis[v])) continue;
ans-=(ll)s*(ll)sz[gf(v)]*(ll)a[u];
s+=sz[gf(v)];
}
for (int i=po[u];i;i=ne[i])
{
v=to[i];
if (a[v]<a[u]||(a[v]==a[u]&&!vis[v])) continue;
un(u,v);
}
}
p--;
}
}
int main()
{
n=read();
for (int i=1;i<=n;i++) a[i]=read(),G[a[i]].push_back(i);//桶排
for (int i=1;i<n;i++)
{
X=read();Y=read();
add(X,Y);
add(Y,X);
}
Qmax();
Qmin();
printf("%I64d\n",ans);
return 0;
}

G. Coprime Arrays

题意

$n\le210^6$ 个空,$m\le 210^6$个询问,对 $1\le i\le m$:只用$\le i$的数字填进$n$个空,有多少种方案使数组的总$gcd=1$,对于第 $i$ 组询问求出来的答案 异或 $i$,求所有询问的答案的和

题解

很容易推出来

$f(i)=\sum \limits _{d=1}^iμ(d)\big\lfloor \frac id\big\rfloor ^n$

预处理出1~m的n的次方,然后整除分块就可以了。

然后t飞。

然后把每个式子拆了打了一个表,

可以发现,对于$\mu(i)$,1-i-1项的系数相同,i~2i-1项的系数相同。然后可以前缀和搞搞了。

复杂度 $O(k\ln k)$

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
#include<bits/stdc++.h>
using namespace std;
void qmax(int &x,int y) {if (x<y) x=y;}
void qmin(int &x,int y) {if (x>y) x=y;}
int read(){}
void write(int x){}
const int maxn=2e6+100;
const long long mod=1e9+7;
int n,k,mu[maxn];
int f[maxn],prime[maxn],tot;
long long ksm(long long x,int y)
{
long long sum=1;
while (y)
{
if (y&1) sum=sum*x%mod;
y>>=1;
x=x*x%mod;
}
return sum;
}
long long ans[maxn],p[maxn],sum;
int main()
{
n=read();k=read();
for (int i=1;i<=k;i++)
{
p[i]=ksm((long long)i,n);
}//预处理
mu[1]=1;
for (int i=2;i<=k;i++)//线性筛
{
if (!f[i])
{
tot++;prime[tot]=i;mu[i]=-1;
}
for (int j=1;j<=tot;j++)
{
if (i*prime[j]>k) break;
f[i*prime[j]]=1;
if (i%prime[j]==0) break;
mu[i*prime[j]]=-mu[i];
}
}
for (int i=1;i<=k;i++)
{
for (int j=i;j<=k;j+=i)
{//k lg k暴力搞
ans[j]+=(long long)mu[i]*(p[j/i]-p[(j/i)-1])%mod;
ans[j]%=mod;
}
}
for (int i=2;i<=k;i++)//前缀和
{
ans[i]+=ans[i-1];
ans[i]%=mod;
}
for (int i=1;i<=k;i++)
{
if (ans[i]<0) ans[i]=(ans[i]%mod+mod)%mod;
sum+=ans[i]^(long long)i;
if (sum>=mod) sum-=mod;
}
printf("%I64d\n",sum);
return 0;
}