Processing math: 100%

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 个数，对于 kmodai==0求max(kai)

题解

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≤500,m≤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这条路径上最大的点权-最小的点权，求 n∑i=1n∑j=iI(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)=i∑d=1μ(d)⌊id⌋n

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

然后t飞。

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

可以发现，对于μ(i)​，1-i-1项的系数相同，i~2i-1项的系数相同。然后可以前缀和搞搞了。

复杂度 O(klnk)

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;
}
置顶

扫一扫，分享到微信

微信分享二维码