打的很懒的一场B卡了D看不懂题卡了F没看完题目理解错题意了，状态好差XD
UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334) - AtCoder
A - Christmas Present
题意：
给出两个数B, G问哪个大
题解：
凑数语法题
void solve()
{
int x, y;
scanf("%d%d", &x, &y);
if (x > y)printf("Bat\n");
else printf("Glove\n");
}B - Christmas Trees
题意：
有一根坐标轴，你需要在所有A+kM（k为任意整数）坐标种圣诞树，问区间L, R内有多少颗树
题解：
首先我们把L, R都减去A，问题就变成了在所有kM点种树，然后我们把L, R同时加上tM（t为整数）使L, R都大于0，然后答案就为 r / m - (l - 1) / m
void solve()
{
LL a, m, l, r;
scanf("%lld%lld%lld%lld", &a, &m, &l, &r);
l -= a, r -= a;
if (l < 0)
{
LL t = (-l + m - 1) / m + 1;
l += t * m, r += t * m;
}
printf("%lld\n", r / m - (l - 1) / m);
}C - Socks 2
题意：
你有n双袜子，第i双袜子的颜色为i，有k双袜子缺了一只袜子，你需要重新组合这些袜子（可能会多余一只），使得每对袜子的颜色差值和最小
题解：
首先n没用，成对的袜子没必要拆开。若m为偶数，显然答案为，i为2到n的所有偶数；若m为奇数，则先删掉一只变成偶数然后就是
了，然后只有在删除第奇数个袜子时会更优，具体写法见代码...
int a[N], l[N], r[N];
void solve()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i)
scanf("%d", &a[i]);
if (m & 1)
{
for (int i = 2; i <= m; ++i)
l[i] = l[i - 2] + a[i] - a[i - 1];
for (int i = m - 1; i >= 1; --i)
r[i] = r[i + 2] + a[i + 1] - a[i];
int ans = INF;
for (int i = 1; i <= m; i += 2)
ans = min(ans, l[i - 1] + r[i + 1]);
printf("%d\n", ans);
}
else
{
int ans = 0;
for (int i = 1; i <= m; i += 2)
ans += a[i + 1] - a[i];
printf("%d\n", ans);
}
}D - Reindeer and Sleigh
题意：
有N个雪橇，第i个雪橇需要Ri只驯鹿才能拉动，给出Q个询问，每个询问给出一个Xi表示询问Xi只驯鹿最多能拉动几只雪橇
题解：
肯定优先拉需要驯鹿数少的雪橇。排序，前缀和，对每个询问二分求最多拉多少个撬即可
LL s[N];
void solve()
{
int n, q;
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; ++i)
scanf("%lld", &s[i]);
sort(s + 1, s + 1 + n);
for (int i = 1; i <= n; ++i)
s[i] += s[i - 1];
while (q--)
{
LL x;
scanf("%lld", &x);
printf("%d\n", upper_bound(s + 1, s + 1 + n, x) - s - 1);
}
}E - Christmas Color Grid 1
题意：
给出一个H*W的字符串表，'.'表示红格子，'#'表示绿格子，当两个同种颜色的格子相邻（周围四格）时则他们联通。问我们随机把一个红格子染成绿格子之后联通块的期望数量(MOD998244353)
题解：
期望数量为 连通块数量/红格子数量。先对修改前的图做并查集把相邻的同色块加入同一集合，对于染绿每个红点之后的连通块数量为红点周围四格的集合数量+1（手玩一下很容易得到）
PII p[N][N];
char mp[N][N];
int dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 };
PII find(int x, int y)
{
if (p[x][y] != make_pair(x, y))
p[x][y] = find(p[x][y].first, p[x][y].second);
return p[x][y];
}
void link(int ax, int ay, int bx, int by)
{
PII pa = find(ax, ay);
p[pa.first][pa.second] = find(bx, by);
}
LL qpow(LL x, LL y)
{
x %= MOD;
if (y == 0)return 1;
if (y & 1)
return qpow(x * x, y >> 1) * x % MOD;
return qpow(x * x, y >> 1) % MOD;
}
void solve()
{
int n, m, ans = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
{
getchar();
for (int j = 1; j <= m; ++j)
{
mp[i][j] = getchar();
p[i][j] = { i,j };
}
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
if (mp[i][j] == mp[i][j + 1])
link(i, j, i, j + 1);
if (mp[i][j] == mp[i + 1][j])
link(i, j, i + 1, j);
}
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
if (mp[i][j] == '#' && find(i, j) == make_pair(i, j))
++ans;
}
}
LL sum = 0, cnt = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
if (mp[i][j] == '.')
{
set<PII>st;
for (int k = 0; k < 4; ++k)
{
int tx = i + dx[k], ty = j + dy[k];
if (mp[tx][ty] == '#')
st.insert(find(tx, ty));
}
++cnt, sum += ans - st.size() + 1;
}
}
}
printf("%lld\n", sum % MOD * qpow(cnt, MOD - 2) % MOD);
}F - Christmas Present 2
题意：
圣诞老人需要给N个人依次配送礼物，他的家位于SX, SY，需要配送的N个位置为Xi, Yi，他每次出门最多能一次性携带K件礼物，中途可以回家补货，送完还需要回家。问送完所有礼物的最短路径
题解：
DP，dp[i]表示给第i个送完礼物之后回家再到达第i+1个位置的最短路径，s[i]为不回家连着走到第i个位置的路径长度，记f(i)为从家到第i个人家的距离，则状态转移为 (f(i)+f(i+1))为回家再到第i+1个人家的距离，可以用线段树或者单调队列优化（这里写的单调队列优化）
但是我的代码测样例3在小数点后第6位开始不相等了，交上去就直接对了，不知道为什么...
typedef long double LD;
PII operator-(PII x, PII y)//平面几何点都存向量会更便于计算
{
return { x.first - y.first,x.second - y.second };
}
LD abs(PII x)
{
return sqrt((LD)x.first * x.first + (LD)x.second * x.second);
}
PII a[N];
LD s[N], dp[N];
deque<int>q;
LD fun(int u, int v)
{
return dp[u] + s[v] - s[u + 1];
}
void solve()
{
int n, k;
scanf("%d%d", &n, &k);
for (int i = 0; i <= n; ++i)
scanf("%d%d", &a[i].first, &a[i].second);
for (int i = 1; i <= n; ++i)
s[i] = s[i - 1] + abs(a[i] - a[i - 1]);
a[n + 1] = a[0], dp[0] = s[1];
for (int i = 1; i <= n; ++i)
{
while (q.size() && i - q.front() > k)
q.pop_front();
while (q.size() && fun(q.back(), i) > dp[i - 1])
q.pop_back();
q.push_back(i - 1);
dp[i] = fun(q.front(), i) + abs(a[i] - a[0]) + abs(a[i + 1] - a[0]);
}
printf("%.10Lf\n", dp[n]);
}赛时做的好慢最后F读假题了然后题意读对之后没时间写了，G没看...
