ABC 做题记录

ABC465 赛后总结

共 1699 字
15 分钟
0 次阅读

本场 Rating：$\textcolor{#00C0C0}{1406} \rightarrow \textcolor{#00C0C0}{1484}(+78)$。

本场表现分：$\textcolor{#0000FF}{1951}$。

今天给网站开发了折叠框，直接严肃使用。强（行）兼（容）洛谷语法。

其实这场算比较简单的了。体感：红红橙橙蓝绿紫。

A Supermajority

AtCoder 依旧检查除法精度大佬。

:::info[Code]

1
2
3
4
5
6
7
8
9

#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	if(a*3>b*2)printf("Yes");
	else printf("No");
	return 0;
}

:::

B Parking 2

从 $a$ 点整到 $b$ 点整其实只有 $b-a$ 个小时。所以枚举区间是 $[a,b)$。

:::info[Code]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include<bits/stdc++.h>
using namespace std;
int main(){
	int l,r,a,b,x,y,ans=0;
	scanf("%d%d%d%d%d%d",&x,&y,&l,&r,&a,&b);
	for(int i=a;i<b;i++){
		if(i>=l&&i<r)ans+=x;
		else ans+=y;
	}
	printf("%d",ans);
	return 0;
}

:::

C Reverse Permutation

维护一个双端队列，每次根据当前总反转次数的奇偶性决定从前面还是后面插入。可以通过维护一个 bool 型的变量解决。

:::info[Code]

 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

#include<bits/stdc++.h>
using namespace std;
deque<int>num;
int tag;
int main(){
	int n;
	string s;
	cin>>n>>s;
	for(int i=1;i<=n;i++){
		if(tag)num.push_front(i);
		else num.push_back(i);
		if(s[i-1]=='o')tag^=1;
	}
	if(tag){
		for(int i=1;i<=n;i++){
			printf("%d ",num.back());
			num.pop_back();
		}
	}else{
		for(int i=1;i<=n;i++){
			printf("%d ",num.front());
			num.pop_front();
		}
	}
	return 0;
}

:::

D X to Y

刻画一棵 $K$ 进制树，也就是节点 $i$ 的任意子节点 $j$ 均满足 $\lfloor \frac{j}{k} \rfloor = i$。

你别说，$\lfloor \frac{x}{k} \rfloor = y$ 好像就是在树上往上走一步，$\lfloor \frac{y}{k} \rfloor = x$ 好像就是在树上往下走一步。

这不就是查询 LCA 吗。良心出题人。

时间复杂度 $O(Q \log_K \max(x,y))$。

:::info[Code]

 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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dep(ll v,ll k){
	int d=0;
	while(v>0){
		v/=k;
		d++;
	}
	return d;
}
void solve(){
	ll x,y,k;
	int ans=0;
	scanf("%lld%lld%lld",&x,&y,&k);
	int dx=dep(x,k);
	int dy=dep(y,k);
	if(dx<dy)swap(x,y),swap(dx,dy);
	ll a=x,b=y;
	while(dx>dy){
		dx--;
		ans++;
		a/=k; 
	}
	while(a!=b){
		a/=k;
		b/=k;
		ans+=2;
	}
	printf("%d\n",ans);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}

:::

E Digit Circus

萌萌数位 DP。

绷不住了，这题卡了我 10 分钟，原因之一是我用了插件 AtCoder Better! 的翻译。

请看下图：

**个

这是恰好一个吗……

设状态 $dp_{dep,mask,sum,strict,st}$ 为考虑到第 $dep$ 位，已选择的数状压后为 $mask$，前面数字总和为 $sum$，是否严格小于 $x$，是否有至少一个有效位的方案数。记忆化搜索秒了。

绷不住了，这题又卡了我 10 分钟，原因之二是猎奇 C++ 机制。

1

return ((sum==0)+((mask&(1<<3)))+((__builtin_popcount(mask)==3)))==1;

这样的校验是错误的。

1
2
3
4

int a=sum==0;
int b=mask&(1<<3);
int c=__builtin_popcount(mask)==3;
return (a+b+c)==1;

这样的校验也是错误的。

1
2
3
4

int a=sum==0;
int b=mask&(1<<3)?1:0;
int c=__builtin_popcount(mask)==3?1:0;
return a+b+c==1;

这样的校验是正确的。

Upd：脑子发电了。事实上 mask&(1<<3) 的取值是 $0$ 或 $8$，正确的写法应该是 (mask>>3)&1 或者 (mask&(1<<3))>>3。

:::info[Code]

 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

#include<bits/stdc++.h>
constexpr int mod=998244353;
using namespace std;
int dp[505][1024][3][2][2];
string s;
int n;
int dfs(int pos,int mask,int sum,int t,int st) {
    if(pos==n){
		if(!st)return 0;
		int a=sum==0;
		int b=mask&(1<<3)?1:0;
		int c=__builtin_popcount(mask)==3?1:0;
        return a+b+c==1;
    }
    int &res=dp[pos][mask][sum][t][st];
    if(res!=-1)return res;
    res=0;
    int lim=t?(s[pos]-'0'):9;
    for(int d=0;d<=lim;d++){
        int nt=t&&(d==s[pos]-'0');
        int ns=st||(d!=0);
        int nm=mask;
        int nsum=sum;
        if(ns){ 
            nm=mask|(1<<d);
            nsum=(sum+d)%3;
    	}
        res+=dfs(pos+1,nm,nsum,nt,ns);
        res%=mod;
    }
    return res;
}
int main(){
	memset(dp,0xff,sizeof(dp));
	cin>>s;
	n=s.length();
	cout<<dfs(0,0,0,1,0);
	return 0;
}

:::

F Sjeltzer?

呜呜呜我是杂鱼，这么简单的题吃了三次罚时。

一眼的六维前缀和，查询子矩阵和，应当很简单。

那三次罚时是怎么来的呢？

:::error[第一次和第二次]

 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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll pre[1000005];
constexpr int base[6]={100000,10000,1000,100,10,1};
int toint(string s){
	int ans=0;
	for(int i=0;i<6;i++){
		ans+=(s[i]-'0')*base[i];
	}
	return ans;
}
int merge(int idx[6]){
	int ans=0;
	for(int i=0;i<6;i++){
		ans+=(idx[i])*base[i];
	}
	return ans;
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		string s;
		ll v;
		cin>>s>>v;
		pre[toint(s)]+=v;
	}
	for(int i=0;i<6;i++){
		int b=base[i];
		for(int i=0;i<1000000;i++){
			int x=(i/b)%10;
			if(x>0){
				pre[i]+=pre[i-b];
			}
		}
	}
	int q;
	cin>>q;
	while(q--){
		string x,y;
		cin>>x>>y;
		if(toint(x)>toint(y)){
			cout<<"0\n";
			continue;
		}
		ll ans=0;
		for(int msk=0;msk<(1<<6);msk++){
			int num[6]={0};
			bool ok=true;
			int s=1;
			for(int k=0;k<6;k++){
				if(msk&(1<<k)){
					num[k]=(x[k]-'0')-1;
					s=-s;
				}else{
					num[k]=y[k]-'0';
				}
				if(num[k]<0){
					ok=false;
					break;
				}
			}
			if(!ok)continue;
			ans+=pre[merge(num)]*s; 
		}
		cout<<ans<<'\n';
	} 
	return 0;
}

笑点解析：应当 $x$ 的每一位都小于等于 $y$，而不是整体。

:::

:::error[第三次]

 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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll pre[1000005];
constexpr int base[6]={100000,10000,1000,100,10,1};
int toint(string s){
	int ans=0;
	for(int i=0;i<6;i++){
		ans+=(s[i]-'0')*base[i];
	}
	return ans;
}
int merge(int idx[6]){
	int ans=0;
	for(int i=0;i<6;i++){
		ans+=(idx[i])*base[i];
	}
	return ans;
}
signed main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		string s;
		ll v;
		cin>>s>>v;
		pre[toint(s)]+=v;
	}
	for(int i=0;i<6;i++){
		int b=base[i];
		for(int i=0;i<1000000;i++){
			int x=(i/b)%10;
			if(x>0){
				pre[i]+=pre[i-b];
			}
		}
	}
	int q;
	cin>>q;
	while(q--){
		string x,y;
		cin>>x>>y;
		for(int i=0;i<6;i++){
			if(y[i]>x[i]){
				cout<<"0\n";
				continue;
			}
		}
		ll ans=0;
		for(int msk=0;msk<(1<<6);msk++){
			int num[6]={0};
			bool ok=true;
			int s=1;
			for(int k=0;k<6;k++){
				if(msk&(1<<k)){
					num[k]=(x[k]-'0')-1;
					s=-s;
				}else{
					num[k]=y[k]-'0';
				}
				if(num[k]<0){
					ok=false;
					break;
				}
			}
			if(!ok)continue;
			ans+=pre[merge(num)]*s; 
		}
		cout<<ans<<'\n';
	} 
	return 0;
}

笑点解析：$x_i$ 和 $y_i$ 写反了。

:::

:::info[Code]

 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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll pre[1000005];
constexpr int base[6]={100000,10000,1000,100,10,1};
int toint(string s){
	int ans=0;
	for(int i=0;i<6;i++){
		ans+=(s[i]-'0')*base[i];
	}
	return ans;
}
int merge(int idx[6]){
	int ans=0;
	for(int i=0;i<6;i++){
		ans+=(idx[i])*base[i];
	}
	return ans;
}
signed main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		string s;
		ll v;
		cin>>s>>v;
		pre[toint(s)]+=v;
	}
	for(int i=0;i<6;i++){
		int b=base[i];
		for(int i=0;i<1000000;i++){
			int x=(i/b)%10;
			if(x>0){
				pre[i]+=pre[i-b];
			}
		}
	}
	int q;
	cin>>q;
	back:;
	while(q--){
		string x,y;
		cin>>x>>y;
		for(int i=0;i<6;i++){
			if(x[i]>y[i]){
				cout<<"0\n";
				goto back;
			}
		}
		ll ans=0;
		for(int msk=0;msk<(1<<6);msk++){
			int num[6]={0};
			bool ok=true;
			int s=1;
			for(int k=0;k<6;k++){
				if(msk&(1<<k)){
					num[k]=(x[k]-'0')-1;
					s=-s;
				}else{
					num[k]=y[k]-'0';
				}
				if(num[k]<0){
					ok=false;
					break;
				}
			}
			if(!ok)continue;
			ans+=pre[merge(num)]*s; 
		}
		cout<<ans<<'\n';
	} 
	return 0;
}

:::

呜呜呜。我有玉玉症。

G Sum of Mex of Mod of Linear

没看懂。

我是大杂鱼。

Licensed under CC BY-NC-SA 4.0
© 2026 Jqcyx's Blog
使用 Hugo 构建
主题 Stack 由 Jimmy 设计