AtCoder_abc334
A - Christmas Present
题目描述
输入两个数 \(B,G(B \neq G)\) ，若 \(B\) 大，输出 Bat ，否则输出 Glove 。
解题思路
无
Code
// Problem: A - Christmas Present
// Contest: AtCoder - UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334)
// URL: https://atcoder.jp/contests/abc334/tasks/abc334_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
#include<bits/stdc++.h>
using namespace std;
int a,b;
int main(){
cin>>a>>b;
if(a>b)
cout<<"Bat";
else
cout<<"Glove";
return 0;
}
B - Christmas Trees
题目描述
现在从 \(A\) 点开始，每隔 \(M\) 的长度种一棵树。
即，所有有树的坐标的集合 \(T\) 为 \(T=\{i\,|\,i=km+a,k\in \Z \}\) 。
请问 \(L\) 到 \(R\) 之间有多少颗树。
解题思路
先将 \(A\) 点作为零点，将整个数轴分成很多以 \(M\) 为长度的区间，两端点的区间编号一减，再根据正负以及端点上是否正好有树加亿点点细节就好了。
Code
// Problem: B - Christmas Trees
// Contest: AtCoder - UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334)
// URL: https://atcoder.jp/contests/abc334/tasks/abc334_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,m,l,r;
int main(){
cin>>a>>m>>l>>r;
l-=a,r-=a;
if(l>0)
cout<<(r/m-l/m+(l%m==0));
else if(r>0)
cout<<(r/m+(-l)/m+1);
else
cout<<((-l)/m-(-r)/m+((-r)%m==0));
return 0;
}
C - Socks 2
题目描述
他有 \(N\) 双袜子，其中 \(K\) 双丢了一只， \(K\) 双袜子中剩下的那只颜色为 \(A_i(1 \le i \le K,1\le A_1 < A_2 <\cdots<A_K\le N)\) 。
由颜色 \(i,j\) 组成的袜子的怪异度为 \(|i-j|\)。
请问把所有袜子组合起来后总怪异度最小为多少？（若 \(K\) 为奇数则最后可以剩下一只袜子）。
解题思路
若为偶数，直接计算，若为奇数，预处理一下前后缀和然后统计就好了。
Code
// Problem: C - Socks 2
// Contest: AtCoder - UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334)
// URL: https://atcoder.jp/contests/abc334/tasks/abc334_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k;
int a[200005];
int fsum[200005],bsum[200005];
int ans=INT_MAX;
int main(){
cin>>n>>k;
for(int i=1;i<=k;i++)
cin>>a[i];
for(int i=2;i<=k;i+=2)
fsum[i]=fsum[i-2]+a[i]-a[i-1];
for(int i=k-1;i>=0;i-=2)
bsum[i]=bsum[i+2]+a[i+1]-a[i];
if(k%2)
for(int i=0;i<=k;i+=2)
ans=min(ans,fsum[i]+bsum[i+2]);
else
ans=fsum[k];
cout<<ans;
return 0;
}
D - Reindeer and Sleigh
题目描述
有 \(N\) 个雪橇，其中第 \(i\) 个雪橇需要 \(R_i\) 匹驯鹿来拉。每匹驯鹿最多拉一个雪橇。现有 \(Q\) 次询问，每次询问给你 \(X\) ，问你如果有 \(X\) 匹驯鹿，最多能拉多少个雪橇？
第一行输入 \(N,Q\)，第二行输入 \(R_i\)，接下来每行输入一个询问。
解题思路
这题放到B都高了。
很简单的前缀和加二分，属于是读完题做不出来就该内啥的程度。
Code
// Problem: D - Reindeer and Sleigh
// Contest: AtCoder - UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334)
// URL: https://atcoder.jp/contests/abc334/tasks/abc334_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q;
ll a[200005];
ll sum[200005];
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+a[i];
for(int i=1;i<=q;i++){
ll t;cin>>t;
int p=upper_bound(sum+1,sum+1+n,t)-sum-1;//能用stl谁手写啊
cout<<p<<endl;
}
return 0;
}
E - Christmas Color Grid 1
题目描述
输入一个 \(H\times W\) 的网格，请计算随机将一个 . 变成 # 后， # 的四连通块的期望数量对 \(998244353\) 取模。
解题思路
要不是这题涉及了个乘法逆元[1]和求期望[2]他就应该跟着上面那道题滚去 B 题待着。
可以枚举每一个 . 计算将他变成 # 后的连通块数量然后求期望即可。
Code
// Problem: E - Christmas Color Grid 1
// Contest: AtCoder - UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334)
// URL: https://atcoder.jp/contests/abc334/tasks/abc334_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
ll n,m,cnt,cnt2,sum;
ll mp[1003][1003];
int pos[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
void exgcd(ll a,ll b,ll& x,ll& y){//扩展欧几里得算法
if(b==0){
x=1,y=0;
return;
}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
ll mulinv(ll a,ll b){//求乘法逆元
ll x,y;
exgcd(a,b,x,y);
return x;//x即为a在%b时的逆元
}
void dfs(int i,int j,int k){
mp[i][j]=k;
for(int l=0;l<4;l++)
if(mp[i+pos[l][0]][j+pos[l][1]]==-1)
dfs(i+pos[l][0],j+pos[l][1],k);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
char t;cin>>t;
if(t=='#')
mp[i][j]=-1;//输入处理
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(mp[i][j]==-1)
dfs(i,j,++cnt);//先跑一遍dfs计算连通块，不然每染一次色都跑dfs会T
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(mp[i][j]==0){
cnt2++;//记录情况的总数
set <int> st;//利用set内会排除重复值的特性计算这个点周围有几个连通块
for(int l=0;l<4;l++)
if(mp[i+pos[l][0]][j+pos[l][1]]!=0)
st.insert(mp[i+pos[l][0]][j+pos[l][1]]);
sum+=cnt+1-st.size();
sum%=mod;
}
sum*=mulinv(cnt2,mod);//乘法逆元
sum=(sum%mod+mod)%mod;
cout<<sum;
return 0;
}
请移步oiwiki 乘法逆元 ↩︎
对所有可能的结果求平均数 ↩︎