【寒假集训】2026.2.22

做题代码：

T1：T725277 【2026寒假集训】爱与和平

本题刚开始得了10分，代码为：

#include <bits/stdc++.h>
using namespace std;
bool huzhi(int x,int y){
if(__gcd(x,y)){
return true;
}
return false;
}
int a[100005];
int main() {
int n,sum=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<n;i++){
if(huzhi(a[i],a[i+1])){
continue;
}
else sum++;
}
cout<<sum;
return 0;
}

后来，改成了30分，代码为：

#include <bits/stdc++.h>
using namespace std;
bool huzhi(long long x,long long y){
if(__gcd(x,y)){
return true;
}
return false;
}
long long a[100005];
int main() {
long long n,sum=0;
cin>>n;
for(long long i=1;i<=n;i++){
cin>>a[i];
}
for(long long i=1;i<n;i++){
if(huzhi(a[i],a[i+1])){
sum++;
}
else continue;
}
cout<<sum;
return 0;
}

然后……总算AC了，代码为：

#include <bits/stdc++.h>
using namespace std;
bool huzhi(long long x,long long y){
if(__gcd(x,y)>1){
return true;
}
return false;
}
long long a[100005];
int main() {
long long n,sum=0;
cin>>n;
for(long long i=1;i<=n;i++){
cin>>a[i];
}
for(long long i=1;i<n;i++){
if(huzhi(a[i],a[i+1])){
sum++;
}
else continue;
}
cout<<sum;

return 0;
}

T2：T725282 【2026寒假集训】相遇时间

刚开始0分，代码我就不发了。

后来，整了个40分，代码为：

#include <bits/stdc++.h>
using namespace std;
int main() {
int a,b,c,d,sum=0;
cin>>a>>b>>c>>d;
if(a-c>=0){
sum+=(a-c);
}
else{
sum+=(c-a);
}
if(b-d>=0){
sum+=(b-d);
}
else{
sum+=(d-b);
}
cout<<sum/2;
return 0;
}

然后就是AC代码：

#include <bits/stdc++.h>
using namespace std;
int main() {
long long a,b,c,d,sum=0;
cin>>a>>b>>c>>d;
cout<<max(((abs(a-c)+1)/2),((abs(b-d)+1)/2));
return 0;
}

很简单，对吧，我也觉得，但为什么第三行憋不出来呢？

T3：T725285 【2026寒假集训】相等序列

刚开始：没做。

比赛后：两遍过：

①：80分：

#include <bits/stdc++.h>
using namespace std;

int a[1000005];
long long s[1000005];

int main() {
long long n, x,y,aa,sum=1e18;
cin >> n >> x>>y;
long long minn = 1e18;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
s[1]=1;
for(int i=1; i<=n; i++) s[i] = s[i-1] + a[i];
for (int i = 1; i <= n; i++) {
s[i] = x * i * a[i] – x * s[i] + y*(s[n] – s[i]) – y*(n – i) * a[i];
sum=min(sum,s[i]);
}
cout<<sum;
return 0;
}

②：全AC：

#include <bits/stdc++.h>
using namespace std;

int a[1000005];
long long s[1000005];

int main() {
long long n, x,y,aa,sum=1e18;
cin >> n >> x>>y;
long long minn = 1e18;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a+1,a+n+1);
s[1]=1;
for(int i=1; i<=n; i++) s[i] = s[i-1] + a[i];
for (int i = 1; i <= n; i++) {
s[i] = x * i * a[i] – x * s[i] + y*(s[n] – s[i]) – y*(n – i) * a[i];
sum=min(sum,s[i]);
}
cout<<sum;
return 0;
}

T4：T725286 【2026寒假集训】按位或

本题，和上一题一样，都刚开始没写。

后来……直接AC了：

#include <bits/stdc++.h>
using namespace std;
int n,m,a[100005];
int main() {
int T;
cin>>T;
while(T–){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int ans=0;
for(int i=1;i<=n;i++){
if((m|a[i])>m) continue;
ans|=a[i];
}
if(ans==m)cout<<"Yes\\n";
else cout<<"No\\n";
}
return 0;
}

T5：T725288 【2026寒假集训】美好的子串

本题：刚开始也没写，后来CE了，然后又AC了。

代码为：

#include <bits/stdc++.h>
using namespace std;
int s[1000005];
char a[1000005];
int main() {
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int r=1,ans=1;
s[a[1]]=1;
for(int l=1;l<=n;l++){
while (r<n&&s[a[r+1]]<m){
r++;
s[a[r]]++;
}
ans=max(ans,r-l+1);
s[a[l]]–;
}
cout<<ans;
return 0;
}

T6：T725290 【2026寒假集训】方案数

本题刚开始10分……那个不说了。

后来AC了：

#include <bits/stdc++.h>
using namespace std;
long long n,m;
long long quick(long long a,long long n,long long m){
long long ans=1;
while(n){
if(n%2)ans=(ans*a)%m;
n/=2;
a=(a*a)%m;
}
return ans;
}
int main() {
cin>>n>>m;
long long a = quick(m, n, 100007);
long long b = m * quick(m – 1, n – 1, 100007) % 100007;
long long ans = (a – b + 100007) % 100007;

cout << ans << endl;
return 0;
}

附录：

我还是给一下吧：我十分的代码：

#include <bits/stdc++.h>
using namespace std;
int main() {
long long n,m,sum=0;
cin>>n>>m;
if(n==1){
cout<<0;
return 0;
}
for(int i=1;i<n;i++){
sum+=m*2;
}
sum-=m;
cout<<sum;
return 0;
}

题目&思路：

T1：https://www.luogu.com.cn/problem/T725277?contestId=311140

T2：https://www.luogu.com.cn/problem/T725282?contestId=311140

T3：https://www.luogu.com.cn/problem/T725285?contestId=311140

T4：https://www.luogu.com.cn/problem/T725286?contestId=311140

T5：https://www.luogu.com.cn/problem/T725288?contestId=311140

T6：https://www.luogu.com.cn/problem/T725290?contestId=311140

T1：解题思路：

T2：解题思路：

• 8 方向 = 可以斜着走，1 秒能同时减少 1 行差 + 1 列差
• 所以需要的时间就是较大的那个差

T3：解题思路：

1. 关键结论

要让总花费最小，目标值一定是数组里的某个数。不需要试别的数，只需要枚举数组里每一个数作为目标值，计算花费，取最小即可。

2. 怎么算花费？

对每个候选值 x：

• 如果当前数 num < x：要往上加，花费 (x – num) * a
• 如果当前数 num > x：要往下减，花费 (num – x) * b
• 如果 num == x：花费 0

总花费 = 所有数的花费之和。

3. 算法步骤

T4：解题思路：

T5：解题思路：

核心思想是维护一个动态的区间 [left, right]，保证这个区间内的字符串是「美好的」，然后不断尝试扩大这个区间，记录最大的长度。

T6：解题思路：