2026 WINTER 3rd
总
有收获的是：
cf r8d r9d
牛客 训1g 训2h 训3 cf
以及训1 cl的瞎了眼的教训。。。
补题
cf r8
A. Prime Subtraction
计算x和y差值，若差大于1行，否则不行。
因为在差值大于1的情况下，若是合数，能拆成质数减；若是质数，则可以直接减去
B. Kill 'Em All
从最右侧的怪兽开始处理，依次把左边的怪兽左移
C. Standard Free2play
只关注初始伸出的平台序列，通过判断 “相邻伸出平台的高度差” 决定是否需要水晶，差 > 1 则必须用 1 颗，否则无需
D. AB-string
参考https://www.luogu.com.cn/article/vbj3hnn7
把求好串转换成[n*(n-1)/2-cnt]-cnt,cnt为badstring个数
只有四种badstring
- ABBBB...
- BAAAA...
- ...AAAAB
- ...BBBBA
即 统计这四种串的个数
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const ll modd=998244353;
const ll N=5e5+10;
ll a[N];
ll cnt;
void solve()
{
ll n;cin>>n;
string s;cin>>s;
for(ll i=0;i<n;++i){
a[cnt]=1;
while(i!=n&&s[i]==s[i+1]){
a[cnt]++;
i++;
}
cnt++;
}
cout<<(n*(n-1))/2-2*n+a[0]+a[cnt-1]+cnt-1;
//badstring个数等于单个字符作为bad核心的扩展-能构成回文的情况（左端修复和右端修复）-重复计算的（边界）
}
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;
}
cf r9
A. Two Rival Students
最大的距离是min(n-1,初始距离+x)
B. Magic Stick
如果x大于等于y，输出YES（一直减一）
否则，若x>3，可以通过操作2变大，就变成x>=y的情况
若x为1 2 3，特判就好了
C. Dominated Subarray
双指针找到满足条件的最短子数组
D. Yet Another Monster Killing Problem
预处理，快速找到 打k只怪兽时，能用到的最强英雄
再模拟一遍，从当前位置开始，每天尽可能打最多的怪兽
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+9;
int a[maxn],power[maxn],day[maxn],better[maxn],n,m;
int main()
{
int t;
cin>>t;
while(t--)
{
int flag=1;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
cin>>m;
for(int i=0;i<=n;i++) better[i]=0;
for(int i=1;i<=m;i++)
{
cin>>power[i]>>day[i];
better[day[i]]=max(better[day[i]],power[i]);
}
for(int i=n-1;i>=1;i--)
better[i]=max(better[i],better[i+1]);
int ans=0,pos=1;
while(pos<=n)
{
ans++;
int maxx=0,temp=pos;
while(1)
{
maxx=max(maxx,a[temp]);
if(better[temp-pos+1]<maxx) break;
temp++;
}
if(temp==pos) {flag=0;break;}
pos=temp;
}
if(flag==0) cout<<-1<<endl;
else cout<<ans<<endl;
}
}
牛客1
https://ac.nowcoder.com/acm/contest/120561#question
好久没打牛客了，上手就wa了好几发。。。。
但是之后调好了状态，写起来还行
（但感觉自己写的那几题都算简单的
然后还被榜给带过去看A，看好一会 不会。。。
C
没看到开区间，直接求了个最大值交上去。。
正解应该是a[1]+a[n]+(n-2)*maxx
L
也是想当然了，没看到“最小的”，眼睛长了干嘛的。。
E
其实就是在一个序列里面比相邻两个数的和的最大值
K
手算几下会发现 只有1 3可以
其他的都不行
1是“1”，3是“1 2 3”
G
其实没怎么做过这种题。。。
不直接找最大折叠数字，而是在区间构造一个数，使它反转后尽可能的大
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const ll modd=998244353;
ll rev(ll x)
{
string s=to_string(x);
reverse(s.begin(),s.end());
return stoll(s);
}
void solve()
{
ll l,r;cin>>l>>r;
string t=to_string(r);
if(l==r){
reverse(t.begin(),t.end());
cout<<stoll(t)<<endl;
return;
}
if(t[0]=='1'){
bool ok=true;
for(int i=1;i<(int)t.size();i++)
if(t[i]!='0') ok=false;
if(ok){
cout<<r-1<<endl;
return;
}
}
//起点
ll ans=1;
for(int i=1;i<(int)t.size();i++) ans*=10;
ans=max(ans,l);
string s=string(18,'0')+to_string(ans);
//从低位开始填9
for(ll i=1,j=s.size()-1;i<=1e16;i*=10,j--){
for(int k=1;k<='9'-s[j];k++){
if(ans+i<=r) ans+=i;
}
}
//翻转输出
cout<<rev(ans)<<endl;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll lll=1;
cin>>lll;
while(lll--)
{
solve();
}
return 0;
}
牛客2
https://ac.nowcoder.com/acm/contest/120562#question
只来得及补H...抽空继续补吧。。
H
题意：定义一个数组的权值为其所有前缀中不同数字的个数，求所有子数组的权值之和
看题解说正难则反
考虑一个数字能给多少个子数组贡献答案以及贡献的大小。
在算ai时，考虑的子数组必然是包含i这个位置的，所以计算过程只会被上一个ai的位置j影响，影响的区间左端点个数为i−j 个，而以l(j < l ≤ i) 为左端点，r(i ≤r ≤n) 为右端点的区间贡献(i−j)×(1+n−i+1)× (n−i+1)/2次
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const ll modd=998244353;
const ll N=5e5+10;
ll a[N];
ll cnt;
void solve()
{
ll n;cin>>n;
map<ll,vector<ll>>mp;
for(ll i=1;i<=n;++i){
ll x;cin>>x;
mp[x].push_back(i);
}
auto ans=0ll;
for(auto &[x,y]:mp){
y.insert(y.begin(),0);
for(ll i=1;i<(ll)y.size();++i){
ll l=y[i-1];
ll r=n-y[i]+1;
ans+=1ll*r*(r+1)/2*(y[i]-l);
}
}
cout<<ans;
}
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;
}
牛客3
https://ac.nowcoder.com/acm/contest/120563#question
赛时通过5题，补题补了下c和f
(按赛时开的顺序写)
A
因为x范围很小 只到100，所以从1到10枚举k即可
G
设左边砝码重量总值为suma，右边为sumb
求出两边差值，
若为0，拿掉一个就好
否则，如果左边＞右边，从大的往小的拿，一直到拿掉的重量综合大于等于差值
右边大的情况也同理
B
分解质因子，用哈希表记录首次出现位置，一旦某个质因子重复出现，立即得到一组gcd>1的数
ps:为啥赛后看好几个过的是直接枚举过的，不是n方吗，会T不是。。
J
预处理最后一层的深度和节点数，然后对每个查询:
如果查询节点不在最后一层，直接返回2^深度
如果在最后一层返回预处理好的节点数
H
三角形面积公式
设
c=xayb−xbya
d=ya−yb
则
∣c+d⋅x∣=4
C
这个思考方式我觉得我得学学
目标字符串只可能是 0101... 或 1010...，分别计算最少操作次数，取较小值。
对于固定目标，抽取原串中已经在正确位置上的字符形成串 t，把 '1' 记为 +1，'0' 记为 -1。
一次操作最多只能将某一段的“优势差”减少 1，因此最少操作次数等于 t 的最大子段和与最小子段和绝对值中的较大者，即max(max_subarray_sum, |min_subarray_sum|)。
最终对两种目标取最小值输出。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
ll f(const string &s)
{
ll mx = 0, mn = 0, now = 0;
for (int i = 0; i < (int)s.size(); ++i) {
if (s[i] == '1') now++;
else now--;
if (now < 0) now = 0;
mx = max(mx, now);
}
now = 0;
for (int i = 0; i < (int)s.size(); ++i) {
if (s[i] == '1') now++;
else now--;
if (now > 0) now = 0;
mn = min(mn, now);
}
return max(mx, llabs(mn));
}
void solve()
{
ll n;
string s, t;
cin >> n >> s;
t.clear();
for (int i = 0; i < n; ++i) {
if ((i & 1) && s[i] == '1') t.push_back(s[i]);
if (!(i & 1) && s[i] == '0') t.push_back(s[i]);
}
ll ans = f(t);
t.clear();
for (int i = 0; i < n; ++i) {
if ((i & 1) && s[i] == '0') t.push_back(s[i]);
if (!(i & 1) && s[i] == '1') t.push_back(s[i]);
}
ans = min(ans, f(t));
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) solve();
return 0;
}
F
感觉自己手动推能推出来点，但是逻辑不完整
把博弈过程看成“不断删点但保持连通”，则游戏结束时剩余格子必然构成一条从 (1,1) 到第n列的唯一通路。在2×n 网格中，最短路长度等于(n−1)+r，其中r为换行次数。关键在于：要强制产生一次换行，最少需要连续 5 列结构，因此小紫每 5 列最多逼出一次换行，而小红也能把换行次数控制在每 5 列至多一次。故最终r=⌊n/5⌋，答案为(n−1)+⌊n/5⌋
浙公网安备 33010602011771号