AtCoder Beginner Contest 334 ABCDE
AtCoder Beginner Contest 334](https://atcoder.jp/contests/abc334) ABCDE
A - Christmas Present
签到不多说。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int a,b; cin>>a>>b;
cout<<(a>b?"Bat":"Glove")<<"\n";
return 0;
}
B - Christmas Trees
题意：给你 \(A,M,L,R\) ，表示在一个坐标轴上，对于任意的整数 \(k\) ，在 \(A+kM\) 的位置都种上了圣诞树，现问你 \([L,R]\) 的区间内有多少圣诞树？
思路：分类讨论，考虑\(A\)和区间\([L,R]\)的关系。
-
如果\(A\)在\([L,R]\)之间(\(L \le A \le R\))。
\(res = (A-L)/M + (R-A)/M +1\) (+1是因为k可以等于0)
-
\(A\)在区间\([L,R]\)左边(\(A<L\))。
前缀和思想，\(pre[R]-pre[L-1]\)
\(res = (R-A)/M - ((L-1)-A)/M\)
-
\(A\)在区间\([L,R]\)右边边(\(A>R\))。
\(pre[L]-pre[R+1]\)
\(res = (A-L)/M - (A-(R+1))/M\)
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
ll a,m,l,r; cin>>a>>m>>l>>r;
ll res = 0;
if(a < l)
{
res = (r-a)/m - ((l-1)-a)/m;
}
else if(l <= a && a <= r)
{
res = (r-a)/m + (a-l)/m + 1;
}
else if(a > r)
{
res = (a-l)/m - (a-(r+1))/m;
}
cout<<res<<"\n";
return 0;
}
C - Socks 2
题意：高桥君有 \(N\) 双袜子，第 \(i\) 双袜子的编号是 \(i\) ，有一天他突然意识到了自己丢失了 \(K\) 只袜子，我们定义两只袜子的 “差异度” 为这两只袜子编号的差的绝对值。
现给你这 \(K\) 只袜子的编号，把剩余的 \(2N-K\) 只袜子两两配对，求配对后差异度和的最小值。注意到如果 \(K\) 是奇数，配对后剩余一只袜子是允许的，且不算入差异度的计算中。
第一行输入 \(N,K\)，第二行输入 \(K\) 个数表示丢失的袜子的编号。
思路：思考怎么样差异度最小，肯定是排序之后相邻两个配对是最优的。
那么如果是偶数个之间两两配对即可。如果是奇数个呢？有一个是多出来的，那么是哪一个呢？不知道，我们考虑对前后缀都做一次前缀/后缀和，枚举是哪一个不要，答案取min就行了。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 5e5 + 10;
int a[N],cnt;
ll pre[N],suf[N],res;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int n,k; cin>>n>>k;
set<int>s;
vector<int>v;
for(int i = 1;i <= k; i++)
{
int x; cin>>x;
s.insert(x);
}
for(int i = 1;i <= n; i++)
{
a[++cnt] = i;
if(s.find(i) == s.end())
a[++cnt] = i;
}
int m = 2*n-k;
// for(int i = 1;i <= m; i++)
// cout<<a[i]<<" ";
// cout<<"\n";
for(int i = 1;i <= m; i += 2)
{
pre[i] = pre[i-1] + abs(a[i]-a[i+1]);
pre[i+1] = pre[i];
}
for(int i = m;i >= 1; i -= 2)
{
suf[i] = suf[i+1] + abs(a[i]-a[i-1]);
suf[i-1] = suf[i];
}
if(m % 2 == 0){
res = pre[m];
}else{
res = 1e9;
for(int i = 1;i <= m; i++)
{
res = min(res,pre[i-1]+suf[i+1]);
}
}
cout<<res<<"\n";
return 0;
}
D - Reindeer and Sleigh
题意：有 \(N\) 个雪橇，其中第 \(i\) 个雪橇需要 \(R_i\) 匹驯鹿来拉。每匹驯鹿最多拉一个雪橇。现有 \(Q\) 次询问，每次询问给你 \(X\) ，问你如果有 \(X\) 匹驯鹿，最多能拉多少个雪橇？
第一行输入 \(N,Q\)，第二行输入 \(R_i\)，接下来每行输入一个询问。
思路：排序+二分。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll need[N],s[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int n,q; cin>>n>>q;
for(int i = 1;i <= n; i++)
cin>>need[i];
sort(need+1,need+1+n);
for(int i = 1;i <= n; i++)
s[i] = s[i-1]+need[i];
for(int tc = 1;tc <= q; tc++)
{
ll x; cin>>x;
ll l = 0, r = n;
while(l<=r)
{
ll mid = (l+r)>>1;
if(s[mid] <= x)l = mid+1;
else r = mid-1;
}
cout<<l-1<<"\n";
}
return 0;
}
E - Christmas Color Grid 1
题意：给定 \(n\times m\) 的字符矩阵，# 表示绿色，. 表示红色。
均匀随机一个红色块换成绿色，求绿色四连通块的期望数量，对 \(998244353\) 取模。
\(1\le n,m\le 1000\)
题意：先用\(dfs\)分块，每个连通块标号。然后我们for一边，遇到每一个\(.\)去看它的四个方向有几种连通块，如果有的话就加上\(max(0,原来的连通块数-这个\).\(四个方向上的连通块种类数+1)\)。取max是因为可能这个点四周没有连通块，防止是负数。那么如果四周没有连通块的话答案加上\(原连通块数+1\)。最后的话用除法逆元求答案即可。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int mod = 998244353;
const int N = 2e5 + 10;
ll n,m,hav;
int cnt = 1;
char a[1010][1010];
int b[1010][1010];
int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
bool in(int x,int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m;
}
void dfs(int x,int y,int num)
{
b[x][y] = num;
for(int i = 0;i < 4; i++)
{
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if(in(tx,ty) && a[tx][ty]=='#' && !b[tx][ty])
{
dfs(tx,ty,num);
}
}
}
ll qmi(ll a, ll b, ll mod)
{
ll ans = 1 % mod;
while(b)
{
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
signed main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
cin>>n>>m;
for(int i = 1;i <= n; i++)
for(int j = 1;j <= m; j++)
cin>>a[i][j];
for(int i = 1;i <= n; i++)
for(int j = 1;j <= m; j++)if(a[i][j]=='#' && !b[i][j]){
dfs(i,j,cnt);
cnt++,hav++;
}
// for(int i = 1;i <= n; i++)
// {
// for(int j = 1;j <= m; j++)
// {
// cout<<a[i][j];
// }
// cout<<"\n";
// }
ll cnt = 0,ans = 0;
for(int i = 1;i <= n; i++)
{
for(int j = 1;j <= m; j++)
{
if(a[i][j]=='.')
{
cnt++;
set<ll>s;
int d = 0;
for(int k = 0;k < 4; k++)
{
int tx = i + dir[k][0];
int ty = j + dir[k][1];
if(in(tx,ty)&&a[tx][ty] != '.')s.insert(b[tx][ty]);
if(in(tx,ty) && a[tx][ty]=='.')d++;
}
if(s.size() == 0 && d)ans++;
// cout<<"s.size() = "<<s.size()<<"\n";
// for(auto x : s)
// cout<<x<<" ";
// cout<<"\n";
// cout<<"!!"<<hav-(s.size()-1)<<"\n";
ans += hav-max(0ll,(ll)s.size()-1);
}
}
}
ll g = __gcd(ans,cnt);
// cout<<"hav = "<<hav<<"\n";
// cout<<"ans = "<<ans<<" cnt = "<<cnt<<"\n";
if(g)
ans /= g,cnt /= g;
int inv = qmi(cnt, mod - 2, mod)%mod;
cout<<ans%mod*inv%mod<<"\n";
return 0;
}