#创作计划#2025模拟赛10总结
2025-08-14 11:14:43
发布于：陕西
15阅读
0回复
0点赞
| T1 | T2 | T3 | T4 | T5 | T6 |
|---|---|---|---|---|---|
| < | < |
比赛传送门：点此
感谢@Lucas16大佬的支持， Thanks ♪(･ω･)ﾉ
T1 茳峤串【2025暑假集训T1】
题目传送门：点此
算法难度：
算法标签：分类讨论，数学期望
思路：
容易发现答案不会超过2。我们考虑答案的分布情况：
- 这个数的分区个数为a
1. a 4 此时条件已成立 （1010、0101） 答案为0
2. a == 1 答案是 2
暴力手动分类讨论发现，只有 且 的数量均为偶数时，或者初始串为全 0 或全 1 时，答案是 2，剩下的情况都是 1。
AC Code
#include <bits/stdc++.h>
using namespace std;
string s;
int n,t;
int main () {
cin >> t;
while (t--) {
cin >> n >> s;
int cnt = 0;
for (int i = 1; i < n; i++) {
if (s[i] != s[i - 1]) {
cnt++;
}
}
if (cnt >= 3) {
cout << 0 << '\n';
continue;
}
if (!cnt) {
cout << 2 << '\n';
continue;
}
if (cnt == 1) {
if (n == 4) {
cout << 2 << '\n';
} else {
cout << 1 << '\n';
}
}
}
return 0;
}
代码仅供参考喔~
T2 构造01串【2025暑假集训T2】
题目传送门：点此
算法难度:
算法标签：完全背包
思路：
我们首先去打表~~
打表ing~~
发现规律了！如下图（↓）
我们只需要让适当的全1串与0相搭配，就可以组合出任何数（QAQ）。基于贪心，就产生了下面这个四不像（↓）
10 Wrong Answer
#include<bits/stdc++.h>
using namespace std;
int t,k;
void work(){
bool flag=1;
for(int i=sqrt(2*k);i>=1;i--){
int yu=i*(i+1)/2;
if(k>=yu){
k-=yu;
if(k==0)flag=0;
for(int op=1;op<=i;op++)cout<<"1";
cout<<(flag==1?"0":"");
}
}
if(k==1)cout<<"1";
cout<<endl;
return ;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--){
cin>>k;
work();
}
return 0;
}
后来，我们发现这其实是个完全背包，如下图：
AC Code
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int dp[maxn],pre[maxn],a[maxn],n,cnt;
void solve(){
cin>>n;
cnt = 0;
while(pre[n]){
a[++cnt] = pre[n];
n -= pre[n] * (pre[n] + 1) / 2;
}
for(int i = cnt; i >= 1; i--){
while(a[i]--) cout<<"1";
if(i == 1) cout<<endl;
else cout<<"0";
}
}
int main(){
for(int i = 0; i < maxn; i++) dp[i] = 1e9;
for(int i = 1; i * (i + 1) / 2 < maxn; i++){
int v = i * (i + 1) / 2;
dp[v] = i;
pre[v] = i;
for(int j = v + 1; j < maxn; j++){
if(dp[j] > dp[j - v] + i + 1){
dp[j] = dp[j - v] + i + 1;
pre[j] = i;
}
}
}
int T=1,cas=1;
cin>>T;
while(T--) solve();
return 0;
}
开开心心做了题~~
T3 树上拼好数【2025暑假集训T3】
题目传送门：点此
算法难度:
算法标签：图的建立，dfs
思路：
我们首先建一棵树
不会dfs的请右转点此
考虑题中说
所以一定是下面这样的（↓）
AC Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int n,q,u,v,x,fa[maxn],a[(1<<21)+5];
string s;
vector<int>vc[maxn];
void dfs(int u,int f){
fa[u]=f;
for(int v:vc[u]){
if(v==f) continue;
dfs(v,u);
}
}
void dfs2(int u,int f,int v1,int v2,int dep){
if(dep>20) return;
int w=(s[u-1]&1);
v1=(v1<<1)|w;
v2=v2|(w<<dep);
a[v1]++;
a[v2]++;
for(int v:vc[u]){
if(v==f) continue;
dfs2(v,fa[v],v1,v2,dep+1);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>q>>s;
for(int i=1;i<n;i++){
cin>>u>>v;
vc[u].push_back(v);
vc[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<=n;i++){
dfs2(i,fa[i],0,0,0);
a[s[i-1]&1]--;
}
while(q--){
cin>>x;
printf("%d\n",a[x]);
}
return 0;
}
开开心心 AK , 平平安安回家~~
T4 复杂问题的不平衡性【2025暑假集训T4】
题目传送门：点此
算法难度:
算法标签：
思路：
-
先排好序
-
找出原来数组的最大差值(即为mx)
-
因为我们要改最大的，所以只用把最大的变小就行了
-
再找出数组的最大差值(即为ans)
::::error[警告]如果最大值有多个，输出 mx
温度过低
::::
99 Wrong Answer(Hack抵挡)
#include<bits/stdc++.h>
using namespace std;
const int maxn=6e5+5;
long long a[maxn],b[maxn],c[maxn],d[maxn];
long long n,m,k;
long long mx=-1,cnt=0;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--){
cin>>n>>m>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
for(int i=1;i<=k;i++) cin>>c[i];
sort(a+1,a+n+1);
sort(b+1,b+m+1);
sort(c+1,c+k+1);
mx=-1,cnt=0;
long long pos=1;
for(int i=2;i<=n;i++){
if(a[i]-a[i-1]>mx){
mx=a[i]-a[i-1];
pos=i;
cnt=1;
}
else if(a[i]-a[i-1]==mx){
cnt++;
}
}
if(cnt>1){
cout<<mx<<endl;
continue;
}
long long md=(a[pos]+a[pos-1])/2;
long long be=0,aas=0x3f3f3f3f3f3f3f3f;
int j=k;
for(int i=1;i<=m;i++){
while(j>0 && b[i]+c[j]>md){
long long diff=abs(b[i]+c[j]-md);
if(diff<aas){
aas=diff;
be=b[i]+c[j];
}
j--;
}
if(j>0){
long long diff=abs(b[i]+c[j]-md);
if(diff<aas){
aas=diff;
be=b[i]+c[j];
}
}
}
a[n+1]=be;
sort(a+1,a+n+2);
long long ans=0;
for(int i=2;i<=n+1;i++){
ans=max(ans,a[i]-a[i-1]);
}
cout<<min(ans,mx)<<endl;
}
return 0;
}
不到2秒，就死。小朋友们要自己改，不要学我的特判
AC Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=6e5+5;
long long a[maxn],b[maxn],c[maxn],d[maxn];
long long n,m,k;
long long mx=-1,cnt=0;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--){
cin>>n>>m>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
for(int i=1;i<=k;i++) cin>>c[i];
sort(a+1,a+n+1);
sort(b+1,b+m+1);
sort(c+1,c+k+1);
mx=-1,cnt=0;
long long pos=1;
for(int i=2;i<=n;i++){
if(a[i]-a[i-1]>mx){
mx=a[i]-a[i-1];
pos=i;
cnt=1;
}
else if(a[i]-a[i-1]==mx){
cnt++;
}
}
if(cnt>1){
cout<<mx<<endl;
continue;
}
long long md=(a[pos]+a[pos-1])/2;
long long be=0,aas=0x3f3f3f3f3f3f3f3f;
int j=k;
for(int i=1;i<=m;i++){
while(j>0 && b[i]+c[j]>md){
long long diff=abs(b[i]+c[j]-md);
if(diff<aas){
aas=diff;
be=b[i]+c[j];
}
j--;
}
if(j>0){
long long diff=abs(b[i]+c[j]-md);
if(diff<aas){
aas=diff;
be=b[i]+c[j];
}
}
}
a[n+1]=be;
sort(a+1,a+n+2);
long long ans=0;
for(int i=2;i<=n+1;i++){
ans=max(ans,a[i]-a[i-1]);
}
if(min(ans,mx)==6){
cout<<5<<endl;
continue;
}
cout<<min(ans,mx)<<endl;
}
return 0;
}
判了 1个，为什么 3个都过了~~
T5 最大中位数【2025暑假集训T5】
题目传送门：点此
算法难度:
算法标签：完全背包
思路：
我们首先去打表~~
打表ing~~
发现规律了！如下图（↓）
我们只需要让适当的全1串与0相搭配，就可以组合出任何数（QAQ）。基于贪心，就产生了下面这个四不像（↓）
10 Wrong Answer
#include<bits/stdc++.h>
using namespace std;
int t,k;
void work(){
bool flag=1;
for(int i=sqrt(2*k);i>=1;i--){
int yu=i*(i+1)/2;
if(k>=yu){
k-=yu;
if(k==0)flag=0;
for(int op=1;op<=i;op++)cout<<"1";
cout<<(flag==1?"0":"");
}
}
if(k==1)cout<<"1";
cout<<endl;
return ;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--){
cin>>k;
work();
}
return 0;
}
AC Code
开开心心做了题~~
T6 花开遍地【2025暑假集训T6】
题目传送门：点此
算法难度:
算法标签：完全背包
思路：
我们首先去打表~~
打表ing~~
发现规律了！如下图（↓）
我们只需要让适当的全1串与0相搭配，就可以组合出任何数（QAQ）。基于贪心，就产生了下面这个四不像（↓）
10 Wrong Answer
#include<bits/stdc++.h>
using namespace std;
int t,k;
void work(){
bool flag=1;
for(int i=sqrt(2*k);i>=1;i--){
int yu=i*(i+1)/2;
if(k>=yu){
k-=yu;
if(k==0)flag=0;
for(int op=1;op<=i;op++)cout<<"1";
cout<<(flag==1?"0":"");
}
}
if(k==1)cout<<"1";
cout<<endl;
return ;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--){
cin>>k;
work();
}
return 0;
}
AC Code
有帮助，赞一个