2026 WINTER 1st
总
这周补题觉得有收获的是
r1的c d
r2的c
r3的e
r4的d
这周事情比较多，训练补题没能及时更上，下周事情少了，把这周少做的补上
一些感想：
赛时感觉脑子转的比之前慢，果然还是期末周空了一会训练啊
但现在比之前更喜欢看公式推理了（？
补题
r1
A. Shovels and Swords
这题赛时比较速度的过了，但思路下来自己回顾的时候发现并不严谨（赛时就是突然想到了(a+b)/3)，重新捋了捋
设mn=min(a,b),mx=(a,b);
容易观察得到，2×mn<=mx，答案就直接是mn
2×mn>mx时，每次都消耗当前数量比较多的，最后材料总是不足3，即可视作任意三个材料都能换一个宝石
B. Shuffle
记录可达区间，不断扩展即可
点击查看代码
void solve()
{
ll n,x,m;cin>>n>>x>>m;
bool ok=false;
ll lx=x,ly=x;
// ll ans=0;
while(m--){
ll l,r;cin>>l>>r;
if(l==1&&r==n&&!ok){
cout<<n;
ok=true;
}else{
if(l<=ly&&r>=lx){
lx=min(lx,l);
ly=max(ly,r);
}
}
}
if(!ok){
cout<<ly-lx+1;
}
}
C. Palindromic Paths
要让芯片从(1,1)走到指定位置的任意路径都是回文的，即所有路径的第k个位置和第(n+m-k)个位置的数字完全相同。
对于矩阵中的任意位置(i,j),步数标记为s=i+j-1,那么s的对称组为s'=n+m-s
然后遍历矩阵，先统计每个步数统计为s的0/1数量
再遍历所有要配对的对称组，从1到n+m-1，并只遍历前半部分，避免重复
得到答案
点击查看代码
void solve()
{
ll n,m;cin>>n>>m;
ll ans=0;
ll cnt0[100]={0},cnt1[100]={0};
for(ll i=1;i<=n;++i)
{
for(ll j=1;j<=m;++j){
ll x;cin>>x;
if(x==1){
cnt1[i+j-1]++;
}else{
cnt0[i+j-1]++;
}
}
}
for(ll i=1;i*2<n+m;++i){
ans+=min(cnt0[i]+cnt0[n+m-i],cnt1[i]+cnt1[n+m-i]);
}
cout<<ans;
}
D. Two Divisors
补题思路来自于：
https://chuna2.787528.xyz/lniiwuw/p/15515813.html
(直接贴图吧，这些公式好难打、、)
在补题代码旁边写了写注释，方便之后还能看懂在写啥
还是得谨慎用ll，补题第一发wa了个MLE，改成int就过了，下面代码是define ll int版本
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define endl '\n'
#define modd 998244353
const ll N=1e7+10;
bool vis[N];//标记是否为素数
ll p[N];//存储所有素数
ll ap[N];//ap存储x的最小质因数
ll tot;//素数计数
ll ans[N][2];
//预处理1e7以内所有素数、记录每个合数的最小质因数并存在ap数组
void getprime(){
memset(vis,1,sizeof vis);
vis[0]=vis[1]=0;
for(ll i=2;i<N;++i){
if(vis[i]) p[++tot]=i;
for(ll j=1;j<=tot&&1ll*i*p[j]<N;++j){
vis[i*p[j]]=0;
ap[i*p[j]]=p[j];
if(i%p[j]==0) break;
}
}
}
void solve()
{
getprime();
ll n;cin>>n;
ll a;
for(ll i=1;i<=n;++i){
cin>>a;
if(vis[a]) ans[i][0]=ans[i][1]=-1;//素数
else{
ll tmp=ap[a],b=1;
while(a%tmp==0) a/=tmp,b*=tmp;
if(a!=1) ans[i][0]=b,ans[i][1]=a;
else ans[i][0]=ans[i][1]=-1;
}
}
for(ll i=1;i<=n;++i){
cout<<ans[i][0]<<" ";
}
cout<<'\n';
for(ll i=1;i<=n;++i){
cout<<ans[i][1]<<" ";
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll lll=1;
// cin>>lll;
while(lll--)
{
solve();
if(lll) cout<<'\n';
}
return 0;
}
r2
A. Berland Poker
分类讨论王牌数量是否大于一个人能拿的最大数
如果小于，直接输出王牌数量
否则胜者拿满王牌（他能拿到的最大数量牌数），其他的分给k-1玩家，计算最大王牌数，再计算得分
B. New Theatre Square
先通过 y 与 2x 的大小判断 1×2 瓷砖的性价比：若 y ≥ 2x，1×2 瓷砖无优势，直接用 1×1 瓷砖覆盖所有白色方块；若 y < 2x，则按行遍历统计被黑色方块分隔的连续白色段，每个段优先用 1×2 瓷砖（段长/2）覆盖，剩余单块白色方块用 1×1 瓷砖，最终累加两类瓷砖的花费得到最小成本。
点击查看代码
void solve()
{
ll n,m,x,y;cin>>n>>m>>x>>y;
ll cntx=0,cnty=0;
if(2*x<=y){
for(ll i=1;i<=n;++i){
for(ll j=1;j<=m;++j){
char c ;cin>>c;
if(c=='.') cntx++;
}
}
cout<<cntx*x;
}else{
ll tmp=0;
for(ll i=1;i<=n;++i){
for(ll j=1;j<=m;++j){
char c;cin>>c;
if(c=='.'){
tmp++;
}else{
cnty+=(tmp/2),cntx+=(tmp%2);
tmp=0;
}
}
cnty+=(tmp/2);
cntx+=(tmp%2);
tmp=0;
}
cout<<(cntx*x+cnty*y);
}
}
C. Mixing Water
手动推一下，可以知道偶数杯永远是（h+c)/2
三种情况
1.t==h 第一杯热水温度恰好就是t 那么答案就是1
2.若t<=(h+c)/2
因为偶数杯永远是（h+c）/2，所有奇数杯严格大于（h+c）/2
所以偶数杯一定更接近t，取最小得偶数杯，答案是2
3.(h + c)/2<t<h
最优解一定是某个奇数杯2x+1
可以写出T(x)温度函数公式
即找到一个x，使得T(x)最小
由于T(x)单减，令
得到
由于x必须是整数，所以最后答案还需比较x（floor值），和x+1
这题我看好多题解是二分做的，但是感觉因为温度函数单减，所以比较x和x+1就够了
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define modd 998244353
const ll N=1e7+10;
void solve()
{
ll h,c,t;cin>>h>>c>>t;
if(t==h){
cout<<1;
return;
}else if(2*t<=h+c){
cout<<2;
return;
}
long double realx=(long double)(h-t)/(long double)(2*t-h-c);
ll x=floor(realx);
x=max(x,0ll);
auto diff=[&](ll xx){
long double tmp=((long double)(xx+1)*h+(long double)xx*c)/(long double)(2*xx+1);
return fabsl(tmp-t);//求绝对值，取long double的绝对值
};
long double d1=diff(x);
long double d2=diff(x+1);
if(d1<=d2){
cout<<2*x+1;
}else{
cout<<2*(x+1)+1;
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll lll=1;
cin>>lll;
while(lll--)
{
solve();
if(lll) cout<<'\n';
}
return 0;
}
另，还学了下Lambda表达式写法（看他们都再写
知道了fabsl函数，取绝对值
r3
A. Sum of Odd Integers
通过两个关键条件判断：
1.n 与 k 需奇偶性一致（因 k 个互不相同正奇数的和的奇偶性与 k 相同）
2.其次，n 需不小于 k²（因 k 个互不相同正奇数的最小和为 1+3+…+(2k-1)=k²），仅当两个条件同时满足时，n 可表示为 k 个互不相同的正奇数之和，否则不可。
B. Princesses and Princes
贪心模拟做法
用数组标记已匹配的王国，遍历每个女儿的心仪列表，优先匹配列表中未被占用的最小编号王国，记录未匹配到任何王国的女儿；若所有女儿均匹配成功则输出 “OPTIMAL”，否则找到未被匹配的王国，将其添加到该未匹配女儿的列表中，输出 “IMPROVE” 及对应的女儿和王国编号。
点击查看代码
void solve()
{
ll n;
cin>>n;
ll k[n+5];
ll b[n+5]={0};
ll ans=0;
for(ll i=1;i<=n;i++)
{
cin>>k[i];
bool ok=0;
for(ll j=1;j<=k[i];j++)
{
ll x;
cin>>x;
if(b[x]==0&&ok==0)
{
b[x]++;
ok=1;
}
}
if(ok==0)
ans=i;
}
if(!ans)
{
cout<<"OPTIMAL";
return;
}
cout<<"IMPROVE\n";
for(ll i=1;i<=n;i++)
{
if(b[i]==0)
{
cout<<ans<<" "<<i;
return;
}
}
}
C. Game with Chips
由于每次操作会同时作用于所有芯片，无法单独控制某一个，因此采用统一路径。先用 U、L 把所有芯片推到左上角边界，保证起点一致；随后按“蛇形遍历”方式完整扫描整个棋盘，使每一个格子都会被经过一次。这样，只要目标位置在棋盘内，当路径经过该格子时，对应芯片必然访问到目标。
整个路径长度不超过2nm，满足操作次数限制。
蛇形遍历还想了下咋写 晕
点击查看代码
void solve()
{
ll n,m,k;
cin>>n>>m>>k;
for(ll i=1;i<=k;i++)
{
ll x,y;
cin>>x>>y;
}
for(ll i=1;i<=k;i++)
{
ll x,y;
cin>>x>>y;
}
string ans;
for(ll i=1;i<=n-1;i++) ans.push_back('U');
for(ll i=1;i<=m-1;i++) ans.push_back('L');
for(ll i=1;i<=n;i++)
{
if(i&1)
{
for(ll j=1;j<=m-1;j++) ans.push_back('R');
}
else
{
for(ll j=1;j<=m-1;j++) ans.push_back('L');
}
if (i!=n) ans.push_back('D');
}
cout<<ans.size()<<endl;
cout<<ans;
}
E. Count The Blocks
分类讨论块的位置
1.块在中间
x [ d d d ... d ] y
贡献：(n−i−1)×9×9×10^(n−i−2)
2.块在中间
[ d d d ... d ] y
贡献:9×10^(n−i−1)
3.块贴右边（对称）
x [ d d d ... d ]
贡献：9×10^(n−i−1)
以上三种都是固定d的情况，所以在以上三种的和上还要再×10
ans[i]=10((n−i−1)⋅9(2)⋅10(n−i−2)+2⋅9⋅10^(n−i−1))
r4
A. New Year Garland
最多的颜色必须被其他颜色隔开，即满足mx<=(sum-mx)+1
满足Yes，否则No
B. Verse For Santa
按顺序累加朗诵时间 sum，同时维护当前前缀中耗时最大的部分 maxa 及其位置。
对于每个i，有两种可能：
1.不跳过任何部分：若 sum ≤ s，可以完整朗诵前 i 段。
2.跳过一个部分：若 sum - maxa ≤ s，则跳过当前前缀中耗时最大的那一段，可以朗诵 i-1 段。
在遍历过程中，始终记录能朗诵的最大段数，并保存对应应跳过的那一段位置。
最后输出结果
C. Stack of Presents
复用已经翻开的部分
按送礼顺序处理，用 pos[x] 表示礼物在初始栈中的位置，mx 表示目前已翻到的最深位置。
若 pos[b[i]] ≤ mx，礼物已在翻开的部分中，直接取走，耗时 1。
否则需翻到该位置，耗时 2·(pos[b[i]]−i)+1，并更新 mx。
累加所有耗时即为最小时间。
点击查看代码
void solve()
{
ll n,m;cin>>n>>m;
ll a[n+10]={0},b[m+10]={0};
vector<ll>pos(n+1);
for(ll i=1;i<=n;++i){
cin>>a[i];
pos[a[i]]=i;
}
for(ll i=1;i<=m;++i){
cin>>b[i];
}
ll ans=0;
ll mx=0;
for(ll i=1;i<=m;++i){
if(pos[b[i]]<=mx){
ans++;
}else{
ans+=2ll*(pos[b[i]]-i)+1;
mx=pos[b[i]];
}
}
cout<<ans;
}
D. Santa's Bot
没怎么做过概率题，再多回顾回顾
如果之间看孩子、物品、孩子（是否想要）三重概率不可行，反过来思考若某个物品y被选中后，z恰好也想要它的概率是多少
即
（这个比较好些
之后需要交换求和顺序（总是这个地方写不明白，之前也是。。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 998244353;
ll modpow(ll a, ll e) {
ll r = 1;
while (e) {
if (e & 1) r = r * a % MOD;
a = a * a % MOD;
e >>= 1;
}
return r;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> wants(n);
unordered_map<int, int> cnt;
cnt.reserve(1000000);
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
wants[i].resize(k);
for (int j = 0; j < k; ++j) {
cin >> wants[i][j];
cnt[wants[i][j]]++;
}
}
ll ans = 0;
for (int i = 0; i < n; ++i) {
int k = wants[i].size();
ll inv_k = modpow(k, MOD - 2);
for (int y : wants[i]) {
ans = (ans + cnt[y] * inv_k) % MOD;
}
}
ll inv_n = modpow(n, MOD - 2);
ans = ans * inv_n % MOD * inv_n % MOD;
cout << ans << '\n';
return 0;
}
浙公网安备 33010602011771号