| T1 | T2 | T3 | T4 | T5 | T6 |
|---|---|---|---|---|---|
| \({\color{#F39C11} 普及− }\) | \({\color{#FFC116} 普及/提高− }\) | \({\color{#3498DB} 提高+/省选− }\) | \({\color{#3498DB} 提高+/省选− }\) | \({\color{#3498DB} 提高+/省选− }\) | \({\color{#3498DB} 提高+/省选− }\) |
参赛网址：https://boyacoding.cn/contest
特别感谢 @Sunpicnic对本文格式进行的修正
T3,T5搭建未完成
T1 一道复杂的构造题【2025暑假集训T1】
T1 题面传送门
题目难度：\({\color{#F39C11} 普及− }\)
算法标签：其他，位运算，贪心，数论，构造
思路
由于大样例具有提示性，无下发文件。
在看过数据范围，(主要是 \(m\) 为偶数和 \(m \le n\) )，我发现：因为 \(\gcd(a_1,a_2,...,1)=1\) 所以 对于每个合法的 \(m\) 都有 $$m\equiv1\pmod{2}$$，当 \(m\) 是偶数时：输出 \(-1\)
然后 又因为 \(\gcd(x)=x\) 以及 按位与 运算的性质，我想到了通过二进制组合出 \(m\) ，因为 \(m \le 10^5\)，所以在二进制下 \(m\) 的位数 小于 20。
总结
首先找出 \(m\) 在二进制下为 \(1\) 的位置（ \(1\) 除外），将他们每个都化为独立一组，然后将剩下的数和 \(1\) 化为一组。
AC代码
#include <bits/stdc++.h>
#define int long long
using namespace std;const int maxn=1e5+5;
int n,m;
int a[maxn];
map<int,int> M;signed main(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m;if (m%2==0){cout<<-1;return 0;}int cnt=0;for (int i=2;i<=m;i<<=1){if (m&i){a[++cnt]=i,M[i]++;if (i>n){cout<<-1;return 0;}}}for (int i=1;i<=cnt;i++) cout<<a[i]<<" ";for (int i=1;i<=n;i++){if (M[i]) continue;cout<<i<<" ";}cout<<"\n";cout<<cnt+1<<"\n";for (int i=1;i<=cnt;i++) cout<<i<<" "<<i<<"\n";cout<<cnt+1<<" "<<n<<"\n";return 0;
}
T2 茳侨串【2025暑假集训T2】
T2 题面传送门
题目难度：\({\color{#FFC116} 普及/提高− }\)
算法标签：动态规划，搜索，枚举
思路
首先我们发现茳侨串在将所有相同 \(1\) 或 \(0\) 缩在一起后，只有 \(0101\) 或 \(1010\) 两种状态。
因为两种状态一样，我们考虑 \(0101\) 一种：
它分为 \(4\) 各部分 \(0\) , \(1\) , \(0\) 和 \(1\) ,因为实在没想到其他算法QAQ，我们构造 \(DP\) : \(f_{i,j},j\in[1,4]\) 表示在 \(i\) 的位置 \(j\) 的部分的最小翻转数。
\(f_{i,j}=min{f_{i-1,j},f_{i-1,j-1}}\)
总结
\(f_{i,j}=min{f_{i-1,j},f_{i-1,j-1}}\)
AC代码
#include <bits/stdc++.h>
#define int long long
using namespace std;const int maxn=2e5+5;
int n;
int cnt,ans;
int a[maxn],siz[maxn];
int dp[maxn][5];
string s;signed main(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>s;for (int i=0;i<n-1;i++){if (s[i]!=s[i+1]) cnt++;}if (cnt==0) cout<<2;else if (cnt==1) cout<<1;else if (cnt==2){if (n==4) cout<<2;else cout<<1;}else if (cnt==3) cout<<0;else {int num=0;for (int i=0;i<n;i++){int j=i;while (j<n&&s[j+1]==s[i]) j++;if (j==n){j--;siz[++num]=j-i+1;a[num]=s[i]-'0';break;}siz[++num]=j-i+1;a[num]=s[i]-'0';i=j;}for (int i=0;i<=num;i++){for (int j=1;j<=4;j++){dp[i][j]=1e9;}}dp[0][1]=0;for (int i=1;i<=num;i++){for (int j=1;j<=min(i,4ll);j++){if (j==1) dp[i][j]=dp[i-1][j]+(j%2==a[i])*siz[i];else dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+(j%2==a[i])*siz[i];}}ans=dp[num][4];for (int i=0;i<=num;i++){for (int j=1;j<=4;j++){dp[i][j]=1e9;}}dp[0][1]=0;for (int i=1;i<=num;i++){for (int j=1;j<=min(i,4ll);j++){if (j==1) dp[i][j]=dp[i-1][j]+(j%2!=a[i])*siz[i];else dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+(j%2!=a[i])*siz[i];}}ans=min(ans,dp[num][4]);cout<<ans;}return 0;
}
T3 好路径数【2025暑假集训T3】
T3 题面传送门
题目难度：\({\color{#3498DB} 提高+/省选− }\)
算法标签：其他，双指针扫描，数据结构，并查集
tip：还没改出来
思路
无
总结
无
AC代码
无
T4 江桥游览花园【2025暑假集训T4】
T4 题面传送门
题目难度：\({\color{#3498DB} 提高+/省选− }\)
算法标签：动态规划
tip：赛时不会
感谢赛后 @hanbingqigu 讲解
思路
无
总结
我们可以发现 对于每个位置，只会去到的两个地点，于是我们可以构造 \(DP\) 方程
\(f_{i,j,0}\) 表示第一种花取到 \(i\) ,第二种花去到 \(j\) ，现在在第一种花的最短距离
\(f_{i,j,1}\) 表示第一种花取到 \(i\) ,第二种花去到 \(j\) ，现在在第二种花的最短距离
\(f_{i+1,j,0}=min(f_{i+1,j,0},f_{i,j,0}+dis(i,i+1));\)
\(f_{i,j+1,1}=min(f_{i,j+1,1},f_{i,j,0}+dis(i,j+n+1));\)
\(f_{i+1,j,0}=min(f_{i+1,j,0},f_{i,j,1}+dis(j+n,i+1));\)
\(f_{i,j+1,1}=min(f_{i,j+1,1},f_{i,j,1}+dis(j+n,j+n+1));\)
AC代码
#include <bits/stdc++.h>
#define int long long
using namespace std;const int maxn=2e3+5;
int n,m;
int x[maxn],y[maxn];
int f[maxn][maxn][2];int dis(int i,int j){int res=abs(x[i]-x[j])*abs(x[i]-x[j])+abs(y[i]-y[j])*abs(y[i]-y[j]);return res;
}signed main(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m;for (int i=1;i<=n+m;i++) cin>>x[i]>>y[i];memset(f,0x3f,sizeof(f));f[1][0][0]=0;for (int i=1;i<=n;i++){for (int j=0;j<=m;j++){f[i+1][j][0]=min(f[i+1][j][0],f[i][j][0]+dis(i,i+1));f[i][j+1][1]=min(f[i][j+1][1],f[i][j][0]+dis(i,j+n+1));f[i+1][j][0]=min(f[i+1][j][0],f[i][j][1]+dis(j+n,i+1));f[i][j+1][1]=min(f[i][j+1][1],f[i][j][1]+dis(j+n,j+n+1));}}cout<<f[n][m][0];return 0;
}
T5 环计数【2025暑假集训T5】
T5 题面传送门
题目难度：\({\color{#3498DB} 提高+/省选− }\)
算法标签：动态规划，状压DP
tip：还没改出来
思路
无
总结
无
AC代码
无
T6 数学竞赛2【2025暑假集训T6】
T6 题面传送门
题目难度：\({\color{#3498DB} 提高+/省选− }\)
算法标签：其他，数据结构，线段树，二分查找
tip：赛时不会
思路
无
总结
同线段树
P4145 上帝造题的七分钟 2 / 花神游历各国
唯一复杂的\(f(v)\)
设 \(f(x)=floor(y)\)
则 \(\frac{y*(y+1)}{2}=x\)
已知 \(x\) ，求 \(y\)
根据 一元二次方程 求根公式
众所周知，对一元二次方程 \(ax ^ 2 + bx + c = 0(a \neq 0)\)，可以用以下方式求实数解：
- 计算 \(\Delta = b ^ 2 - 4ac\)，则:
1. 若 \(\Delta < 0\)，则该一元二次方程无实数解。
2. 否则 \(\Delta \geq 0\)，此时该一元二次方程有两个实数解 \(x _ {1, 2} = \frac{-b \pm \sqrt \Delta}{2a}\)。
例如：
- \(x ^ 2 + x + 1 = 0\) 无实数解，因为 \(\Delta = 1 ^ 2 - 4 \times 1 \times 1 = -3 < 0\)。
- \(x ^ 2 - 2x + 1 = 0\) 有两相等实数解 \(x _ {1, 2} = 1\)。
- \(x ^ 2 - 3x + 2 = 0\) 有两互异实数解 \(x _ 1 = 1, x _ 2 = 2\)。
--来自 P9750 [CSP-J 2023] 一元二次方程
一元二次方程 \(y^2+y-2x=0\)
判别式 \(\Delta=\sqrt{8x^2+1}>0\)
\(y=\frac{\sqrt{8x^2+1}-1}{2}\)
AC代码
#include <bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
#define ls (mid*2)
#define rs (mid*2+1)
using namespace std;const int maxn=2e5+5;
const int mod=998244353;
int n,m;
int a[maxn];
int t[maxn<<2],flag[maxn<<2];void build(int id,int l,int r){if (l==r){t[id]=a[l];if (t[id]<=1) flag[id]=1;return ;}build(ls,l,mid);build(rs,mid+1,r);t[id]=(t[ls]+t[rs])%mod;flag[id]=flag[ls]&&flag[rs];
}void update(int id,int l,int r,int x,int y){if (r<x||l>y) return ;if (flag[id]) return ;if (l==r){t[id]=(sqrt(8*t[id]+1)-1)/2;t[id]%=mod;if (t[id]<=1) flag[id]=1;return ;}update(ls,l,mid,x,y);update(rs,mid+1,r,x,y);t[id]=(t[ls]+t[rs])%mod;flag[id]=flag[ls]&&flag[rs];
}int query(int id,int l,int r,int x,int y){if (r<x||l>y) return 0;if (x<=l&&r<=y) return t[id]%mod;int res=0;res+=query(ls,l,mid,x,y);res%=mod;res+=query(rs,mid+1,r,x,y);res%=mod;return res;
}signed main(){ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m;for (int i=1;i<=n;i++) cin>>a[i];build(1,1,n);while (m--){int op,x,y;cin>>op>>x>>y;if (op==0) update(1,1,n,x,y);else cout<<query(1,1,n,x,y)<<"\n";}return 0;
}