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;
}