AtCoder Beginner Contest 220 个人题解
比赛链接：AtCoder Beginner Contest 220
A题 Find Multiple
题目大意：
找 \(a\) 到 \(b\) 中 \(c\) 的倍数并输出
思路解析：
枚举
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn=1e5+5;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int a,b,c;
cin>>a>>b>>c;
for(int i=a;i<=b;i++){
if(i%c==0){
cout<<i<<endl;
return 0;
}
}
cout<<-1<<endl;
}
B题 Base K
题目大意：
给出k进制的两个数，输出两个数十进制的乘积
思路解析：
模拟
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn=1e5+5;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll k,a,b;
cin>>k>>a>>b;
ll base=1,sum=0;
while(a){
sum+=a%10*base;
a/=10;
base*=k;
}
ll ans=sum;
base=1,sum=0;
while(b){
sum+=b%10*base;
b/=10;
base*=k;
}
cout<<sum*ans<<endl;
}
C题 Long Sequence
题目大意：
给你一个近乎无限循环的数组，输出前缀和大于X的位置
思路解析：
模拟
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn=1e5+5;
ll a[maxn];
ll sum;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
ll x;
cin>>x;
ll ans=x/sum*n;
x%=sum;
ll tot=0;
for(int i=1;i<=n;i++){
tot+=a[i];
if(tot>x){
cout<<ans+i<<endl;
break;
}
}
}
D题 FG operation
题目大意：
给你一个序列，有两种操作，
- \(F\) 操作：将最左边的两个元素 \(x，y\) 删除，并用 \((x+y)\%10\) 替换
- \(G\) 操作：将最左边的两个元素 \(x，y\) 删除，并用 \((x*y)\%10\) 替换
\(9\) 行分别输出结果分别只剩 \(0-9\) 的方案数
思路解析：
傻逼\(DP\)
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn=1e5+5;
const int mod=998244353;
int a[maxn],n,dp[maxn][15];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
dp[1][a[1]]=1;
for(int i=2;i<=n;i++){
for(int j=0;j<=9;j++){
dp[i][(j+a[i])%10]+=dp[i-1][j];
dp[i][(j+a[i])%10]%=mod;
dp[i][(j*a[i])%10]+=dp[i-1][j]%mod;
dp[i][(j*a[i])%10]%=mod;
}
}
for(int i=0;i<=9;i++)cout<<dp[n][i]<<endl;
}
E题 Distance on Large Perfect Binary Tree
题目大意：
给出一个 \(2^n-1\) 个节点的完全二叉树，输出树中距离为 \(d\) 的点对数量
思路解析：
AC代码：
F题 Distance Sums 2
题目大意：
给出一棵 \(n\) 个节点的树，输出 \(n\) 行，对于每个节点，输出以这个节点为根节点到其他所有节点的距离和
思路解析：
树形 \(DP\)
ans[i]表示以 \(i\) 节点为根节点到其他节点的距离和，sz[i]表示每个节点的子树大小
首先我们 \(DFS\) 得到ans[1],然后我们可以发现如果我们知道了一个节点的ans[],那么我们可以 \(O(1)\) 转移这个节点的相邻节点
我们设当前已知答案的节点为 \(fa\) ，相邻节点为 \(x\) ，可以得到以下方程：
\(ans[x]=ans[fa]-2*sz[x]+n\)
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn=1e6+5;
int e[maxn],h[maxn],nex[maxn],id;
int n,sz[maxn];
ll ans[maxn],tmp;
void add(int x,int y){
e[++id]=y;
nex[id]=h[x];
h[x]=id;
}
void dfs(int x,int fa){
for(int i=h[x];i;i=nex[i]){
int j=e[i];
if(j==fa)continue;
dfs(j,x);
sz[x]+=sz[j];
}
if(x!=1)tmp+=sz[x];
}
void solve(int x,int fa){
if(x!=1)ans[x]=ans[fa]-2*sz[x]+n;
for(int i=h[x];i;i=nex[i]){
int j=e[i];
if(j==fa)continue;
solve(j,x);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)sz[i]=1;
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);
}
dfs(1,1);
ans[1]=tmp;
solve(1,1);
for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
}
G题 Isosceles Trapezium
题目大意：
给出平面内 \(n\) 个带有权值的点，输出构成等腰梯形的点的最大权值和
思路解析：
首先我们考虑等腰梯形的性质：
*
AC代码：