Znzryb's Blog
0%

Posted on Edited on

思路讲解

你最少可以干多少活=总共要干多少活-之前的人干了多少活-后面的人最多干多少活

AC代码

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
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
ll n,k;
const ll N=1010;
ll A[N],B[N],C[N];
ll upDo[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;++i)
        cin>>A[i];
    for(int i=1;i<=n;++i)
        cin>>B[i];
//  ll maxDo=0;
//  for(int i=1;i<=n;++i){
//      maxDo+=A[i]/B[i];
//  }
    for(int i=n;i>=1;--i){
        upDo[i]=upDo[i+1]+A[i]/B[i];
    }
    if(upDo[1]<k){
        for(int i=1;i<=n;++i)
            cout<<0<<" ";
        cout<<endl;
        return 0;
    }
    ll sumUpDo=0;	// 之前的人总共做了多少
    for(int i=1;i<=n;++i){
        
     // 你最少可以干多少活=总共要干多少活-之前的人干了多少活-后面的人最多干多少活
        C[i]=min(A[i]/B[i],max(k-upDo[i+1]-sumUpDo,0LL));
        sumUpDo+=C[i];
    }
    for(int i=1;i<=n;++i)
        cout<<C[i]<<" ";
    cout<<endl;

    return 0;
}
// WA on test 9 https://codeforces.com/contest/2038/submission/293384404
// 应该比较接近了
// AC 加了个max（0LL，。。。）https://codeforces.com/contest/2038/submission/293422369

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

其实这题这题知道结论很简单

1，2，3，4 可以组成1-10（1+2+3+4）以内的任何数x，组成完剩余的就是（10-x）了。同理，可以推广。

所以其实这个w+b就是障眼法，其实只要球的总数够用，就可以满足要求了。

AC代码

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll T,w,b;
const ll N=7e4+7;
ll balls[N];


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	ll n=7e4;
	for(int i=1;i<=n;++i){
		balls[i]=balls[i-1]+i;
	}
	while (T--) {
		cin>>w>>b;
		ll idx=lower_bound(&balls[1],&balls[n+1],w+b)-balls;
		if(balls[idx]>w+b)
			idx-=1;
			
		cout<<idx<<endl;
	}
}
// AC https://codeforces.com/contest/2041/submission/293339184

心路历程（WA，TLE，MLE……）

唉，WA了一次，循环n开小了，谁能想到这个109包括比较大的109？6。

Posted on Edited on

辗转相除法简介

image

我认为这张动图更容易让人理解一点（来自维基百科辗转相除法）

算法的演示动画。最初的绿色矩形的长和宽分别是a=1071，b=462，从中不断铺上462×462的正方形直到剩下部分面积是462 (b) ×147 (a%b) ；然后再铺上147×147的正方形直至剩下21×147的面积；最后，铺上21×21的正方形时，绿色部分就没有了。即21是1071和462的最大公约数。

思路讲解

主要思路和官方题解一致

A[1] 是所有满足 idx%1==0 的 A[idx] 中最大的；（同时保证字典序以及

ai !=gcd(ai，aj) 因为ai是最大的嘛，你aj都没ai大，最大公因数怎么可能等于ai那）
A[2] 是所有满足 idx%2==0 的 A[idx] 中最大的；

同理，剩下可推。

然后上面我们相当于证明了 j % i == 0的情况（此时最大公倍数为 i ），接下来我们看看j % i ≠ 0 的情况

image

长话短说，就是我们可以把 j % i ≠ 0 的问题转化为 i % g == 0 的问题，然后又回归到原来这个问题上了

基本就是官方题解思路

image

其实这个有点像埃氏筛(sieve-like)，所以最后的时间复杂度也和他很像。

筛法的核心代码长这样

1
2
3
4
5
6
7
8
9
10
for(int i=1;i<=n;++i){
	if(idx[i]>m){
		cout<<-1<<endl;
		break;
	}
	A[i]=S[idx[i]];
	for(int j=2*i;j<=n;j+=i){
		idx[j]=max(idx[j],idx[i]+1);
	}
}

AC代码

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll T;

//void out(ll n,vector<ll> &A,vector<ll> &idx){
//	cout<<"debug: ";
//	for(int i=1;i<=n;++i)
//		cout<<A[i]<<" ";
//	cout<<endl;
//	cout<<"debug: ";
//	for(int i=1;i<=n;++i)
//		cout<<idx[i]<<" ";
//	cout<<endl;
//}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0); 
	#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	#endif
	cin>>T;
	while(T--) {
		ll n,m;
		cin>>n>>m;
		vector<ll> S(m+10);
		vector<ll> A(n+10);
		bool vis[n+10];
		for(int i=1; i<=m; ++i) {
			cin>>S[i];
		}
		sort(&S[1],&S[m+1],greater<ll>());
		vector<ll> idx(n+10);
		for(int i=1;i<=n;++i){
			idx[i]=1;
		} 
		for(int i=1;i<=n;++i){
			if(idx[i]>m){
				cout<<-1<<endl;
				break;
			}
			A[i]=S[idx[i]];
			for(int j=2*i;j<=n;j+=i){
				idx[j]=max(idx[j],idx[i]+1);
			}
		}
//		#ifndef ONLINE_JUDGE
//		out(n,A,idx);
//		#endif
		if(A[n]==0)
			continue;
		// output ans
		for(int i=1;i<=n;++i)
			cout<<A[i]<<" ";
		cout<<endl;
	}
	#ifndef ONLINE_JUDGE
	fclose(stdin);
	#endif
}
// AC https://codeforces.com/contest/2039/submission/293319558

心路历程（WA，TLE，MLE……）

这个比较好，一次提交过，

Posted on Edited on

思路讲解

我们来对想求的进行一下变换

image

所以就看 y(即m) 里有几个 x^nx 就行了

至于可以被y整除的 x^y ，那个上题中我们证明了这样的情况不会出现在 y ≥ 2**(ceil(log2(x))+1) 之后（**是python中的次方）

然后我们知道^为不进位加法，故 x^nx ≤ (n+1)*x （不进位加法必然不可能比进位加法大嘛），所以我们先看有多少 nx，再通过一些信息，反推出有多少个 x^nx。

然后开开心心码个程序

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll T;

inline ll change(ll x) {
    ll res=1;
    while (true) {
        if(x==0)
            return res*2;
        x/=2;
        res*=2;
    }
}

int main()
{
    cin>>T;
    while (T--) {
        ll x,m,ans=0;
        cin>>x>>m;
        ll xchange=change(x);
        ll alreadyRecord=0;
        for(ll y=1;y<=min(xchange,m);++y) {
            ll d=x^y;
            if(d%y==0 || d%x==0) {
                ++ans;
                if(d%x==0)
                    ++alreadyRecord;
            }
        }
        // m里总共有的-前面判过的=这里需要加的
        if((x^((m/x)*x))>m) {
						// 说明m/x中统计的一个是假的
            ans+=max(0LL,(m/x-alreadyRecord-1));
        }else {
            ans+=max(0LL,(m/x-alreadyRecord));
        }
        cout<<ans<<endl;
    }
    return 0;
}

样例都过不了？

不要慌，这是因为有回退现象。

image

但是会有一些非常讨厌的回退，比如说上图，如果你只判到6，你会觉得6是一个不行的数，但是实际上6是可以的，其由 1^(1*7)=6 得来，同理，4也是这样。

那回退现象最多会跨多少出现那？其实最多出现在后面一个，因为^他最多把之前加上的给完全抵消掉，他不可能起到比 -x 更强的效果，就像他不会起到比 +x 更强的效果一样。

1
2
3
4
// 预防思路讲解中遇到的回退现象
      if( (x^(m/x+1)*x) <= m && (x^(m/x+1)*x)>min(xchange,m) ) {
          ans+=1;
      }

加了以下这个&& 是因为被2 9这个数据卡了，(x^(m/x+1)*x) ≤ min(xchange,m) ++ans相当于重复了，≤min(xchange,m) 的早就被我们统计过了，不用再统计了。

1
(x^(m/x+1)*x)>min(xchange,m)

AC代码

https://codeforces.com/contest/2039/submission/293249612

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll T;

inline ll change(ll x) {
    ll res=1;
    while (true) {
        if(x==0)
            return res*2;
        x/=2;
        res*=2;
    }
}

int main()
{
    cin>>T;
    while (T--) {
        ll x,m,ans=0;
        cin>>x>>m;
        ll xchange=change(x);
        ll alreadyRecord=0;
        for(ll y=1;y<=min(xchange,m);++y) {
            ll d=x^y;
            if(d%y==0 || d%x==0) {
                ++ans;
                if(d%x==0)
                    ++alreadyRecord;
            }
        }
        if(m>xchange) {
            // m里总共有的-前面判过的=这里需要加的
            if((x^((m/x)*x))>m) {
                ans+=max(0LL,(m/x-alreadyRecord-1));
            }else {
                ans+=max(0LL,(m/x-alreadyRecord));
            }
            // 预防思路讲解中遇到的回退现象
            if( (x^(m/x+1)*x) <= m && (x^(m/x+1)*x)>min(xchange,m) ) {
                ans+=1;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

心路历程（WA，TLE，MLE……）

暴力程序（确保正确理解题意）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll T;

int main()
{
    cin>>T;
    while (T--) {
        ll x,m,ans=0;
        cin>>x>>m;
        for(ll y=1;y<=m;++y) {
            ll d=x^y;
            if(d%y==0 || d%x==0)
                ++ans;
        }
        cout<<ans<<endl;
    }
    return 0;
}

我这个程序老是会多一个，后来发现其实整个思路就有点问题

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll T;

inline ll change(ll x) {
    ll res=1;
    while (true) {
        if(x==0)
            return res*2;
        x/=2;
        res*=2;
    }
}

int main()
{
    cin>>T;
    while (T--) {
        ll x,m,ans=0;
        cin>>x>>m;
        ll xchange=change(x);
        for(ll y=1;y<=min(xchange,m);++y) {
            ll d=x^y;
            if(d%y==0 || d%x==0) {
                ++ans;
            }
        }
        // m里总共有的-前面判过的=这里需要加的
        ans+=max(0LL,(m/x-min(xchange,m)/x));
        cout<<ans<<endl;
    }
    return 0;
}

Posted on Edited on

思路和官方题解应该差不多，但我自认为还是比他讲的清楚一点，其实就是一个对暴力法的上界优化

思路讲解

有一点是肯定的，d<=floor(p/2)d<=floor(p/2) dd 才可能被 pp 整除

当然这题肯定还是和位运算相关嘛，所以我们更关心的其实是 dd 的二进制最高位和 pp 是不一样的

然后我大概猜到是怎么一回事了。

只需要对暴力代码进行一些小小的改动就行

1
for(ll y=1;y<=min(m,change(x));++y) {

把循环上界改成 min(m,change(x))min(m,change(x) ) 就行

那这个 change(x)change(x) 是啥那？

1
2
3
4
5
6
7
8
9
inline ll change(ll x) {
    ll res=1;
    while (true) {
        if(x==0)
            return res*2;
        x/=2;
        res*=2;
    }
}

其实很简单，就是 2∗∗(ceil(log2(x)))2**(ceil(log2(x))) 的意思（**是次方的意思），只不过写了个循环而已 。

然后我们来说我大概猜到什么了

yy 可以很大，相对来说 xx 就比较小，那么当 yy 很大的时候，d=d=xx^yy ( ^是异或的意思) 的高位完全是跟着 yy 走的，但这样的 dd 首先不可能被 xx 整除，其次也不可被y整除（我们前面看了，dd 的高位是不能和 yy 一样的）

当然这个 yy 要多大才会这样那？其实只要大到 yy 的最高位异或时不受 xx 影响就行了，也就是

y>=2∗∗(ceil(log2(x)))y>=2**(ceil(log2(x)))

其实异或还真和加法很像，一个高位的数异或低位的数几乎不会有什么影响。

AC代码

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=static_cast<int>(2e5)+15;
int T;

inline ll change(ll x) {
    ll res=1;
    while (true) {
        if(x==0)
            return res*2;
        x/=2;
        res*=2;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while (T--) {
        ll x,m;
        cin>>x>>m;
        ll ans=0;
        for(ll y=1;y<=min(m,change(x));++y) {
            ll div=x^y;
            if(div==0)
                continue;
            if(x%div==0 || y%div==0) {
                ++ans;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

心路历程（WA，TLE，MLE……）

暴力

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
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=static_cast<int>(2e5)+15;
int T;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while (T--) {
        ll x,m;
        cin>>x>>m;
        ll ans=0;
        for(ll y=1;y<=m;++y) {
            ll div=x^y;
            if(div==0)
                continue;
            if(x%div==0 || y%div==0) {
                ++ans;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}