chtholly-daisuki的小屋

「器用贫乏」

0%

cf round 1061 ABC题解

发表于 分类于 ， ，

又一次滑铁卢掉分 ๐·°(৹˃̵﹏˂̵৹)°·๐

第一题卡了20分钟没做出来直接影响到后面的状态
第一题没有AC大概率是思路上的错误，一定要重新看题想一想，像做脑筋急转弯一样，多扩散地想

BC题都做麻烦了，以后AC的题也该多看看大佬的题解，吸取他们快速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;
#define maxn 200010
#define MOD 998244353
#define ll long long
#define endl '\n'

int main() {
	int t;
	cin>>t;
	while(t--) {
		ll n;
		cin>>n;
		ll ans=0;
		while(n>=2){
			if(n%3==0){
				n/=3;
				ans+=n;
			}else{
				n=n/3+1;
				ans+=n-1;
			}
		}
		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
#include<bits/stdc++.h>
using namespace std;
#define maxn 200010
#define MOD 998244353
#define ll long long
#define endl '\n'

int main() {
	int t;
	cin>>t;
	while(t--) {
		ll n;
		cin>>n;
		if(n==3){
			cout<<1<<endl;
			continue;
		}
		//cout<<"ans:";
		cout<<(n-1)/2<<endl;;
	}
	return 0;
}

第二题

也是做麻烦了，实际上模拟就好了，一次/2就是logn复杂度的，特判一个全是-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
#include<bits/stdc++.h>
using namespace std;
#define maxn 200010
#define MOD 998244353
#define ll long long
#define endl '\n'

int main() {
	int t;
	cin>>t;
	while(t--) {
		int n,q;
		cin>>n>>q;
		string ss;
		cin>>ss;
		vector<int> a(q+10);
		vector<int> s(40);
		bool flag=0;
		for(int i=1;i<=q;i++){
			cin>>a[i];
		}
		int cnt=0;
		if(ss[0]=='A'){
			s[++cnt]=1;
		}else{
			//cout<<cnt<<endl;
			flag=1;
			s[++cnt]=-1;
			if(n!=1) cnt++;
		}
		
		for(int i=2;i<=n;i++){
			if(ss[i-1]=='A'){
				s[cnt]++;
			}else{
				flag=1;
				s[++cnt]=-1;
				if(i==n||ss[i]=='B') continue;
				cnt++;
			}
			//cout<<ss[i-1]<<":"<<cnt<<endl;
		}
		//cout<<cnt<<" ";
		//for(int i=1;i<=cnt;i++) cout<<s[i]<<"#";
		for(int i=1;i<=q;i++){
			if(flag==0){
				cout<<a[i]<<endl;
				continue;
			}
			int ans=0,ind=1;
			while(a[i]>0){
				//cout<<a[i]<<":";
				if(s[ind]!=-1&&a[i]<=s[ind]){
					ans+=a[i];
					break;
				}
				if(s[ind]==-1){
					ans++;
					a[i]/=2;
				}else{
					a[i]-=s[ind];
					ans+=s[ind];
				}
				ind++;
				if(ind>cnt) ind=1;
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}

第三题

也是做麻烦了,思路麻烦再加上码力差，被pos和lower_bound的切换绕进去了，debug了一小时才AC

我的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<bits/stdc++.h>
using namespace std;
#define maxn 200010
#define MOD 998244353
#define ll long long
#define endl '\n'


int main() {
	int t;
	cin>>t;
	while(t--) {
		int n,k;
		cin>>n>>k;
		vector<int> a(n+10);
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		sort(a.begin()+1,a.begin()+n+1);
		int pre=1;
		vector<int> num(n+10);
		int ans=1;
		for(int i=1;i<=n;i++){//枚举答案 
			int pos=lower_bound(a.begin()+1,a.begin()+n+1,i*4)-a.begin();
			pos--;
			for(int j=pre;j<=pos;j++){
				num[a[j]]++;
				for(int k=2;k*k<=a[j];k++){
					if(a[j]%k==0){
						num[k]++;
						if(k==a[j]/k){
							continue;
						}
						num[a[j]/k]++;
						
					}
				}
			}
			pre=pos+1;
			if(pos-num[i]<=k){
				ans=i;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

codeboy大神的思路和代码

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
constexpr int N = 200005;
int b[N], sum[N];
int n, k;
 
signed main() {
	fastio();
	int T;
	cin >> T;
	while(T--) {
		cin >> n >> k;
		meset(b, 0);
		Fe(i, 1, n) {
			int x;
			cin >> x;
			++b[x];
		}
		sum[0] = 0;
		Fe(i, 1, n) sum[i] = sum[i - 1] + b[i];
		int ans = 1;
		Fe(i, 1, n) {
			int R = 4 * i - 1;
			if(R > n)
				R = n;
			int nd = sum[R];
			if(i <= n)
				nd -= b[i];
			if(2 * i <= n)
				nd -= b[2 * i];
			if(3 * i <= n)
				nd -= b[3 * i];
			if(nd <= k)
				ans = i;
		}
		cout << ans << endl;
	}
	return 0;
}