C/C++教程
2021年SDNU-ACM集训队结训赛（补题）
本文主要是介绍2021年SDNU-ACM集训队结训赛（补题），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
好的我又来了开坑了，每次补题都要写好久，，，师哥们出的题非常好是我太菜了，，，认真补题ing~
代码应该都会是我自己写的AC代码，师哥们优美的代码我不太习惯，看不太懂，，，
A Alice and Bob（签到，爆int）
os：也不知道从哪里找的这个奇怪的图：P
思路：签到题没啥思路吧，，，就是注意数据范围，要开long long的喔（千万不要有不必要的WA，20分钟一发伤不起！）
AC代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>
#include <numeric>
using namespace std;
typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
ll a,b;
int main()
{
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
ios;
cin>>a>>b;
cout<<a+b<<'\n';
return 0;
}
B Accepted（签到，字符串模拟）
思路：枚举从第一个字符到第i-7个为首的8个字符需要修改几次才为accepted，如果字符串长度小于8，则直接输出-1，无解。
AC代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>
#include <numeric>
using namespace std;
typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int t;
int n;
string s;
int countt(string s)
{
int cnt=0;
if(s[0]=='a') cnt++;
if(s[1]=='c') cnt++;
if(s[2]=='c') cnt++;
if(s[3]=='e') cnt++;
if(s[4]=='p') cnt++;
if(s[5]=='t') cnt++;
if(s[6]=='e') cnt++;
if(s[7]=='d') cnt++;
return cnt;
}
int main()
{
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
cin>>t;
while(t--)
{
cin>>n;
cin>>s;
if(n<8)
cout<<"-1"<<'\n';
else
{
int maxn=-1;
for(int i=0;i<n-7;i++)
{
maxn=max(maxn,countt(s.substr(i,8)));
}
cout<<8-maxn<<'\n';
}
}
return 0;
}
ps：前两题还是A的很快的，一共28分钟（对我来说哈），后面就不咋样了
C 快攻猛男的早餐（尺取法，前缀和+二分查找）
废话可跳过：显而易见，直接暴力模拟必TLE
思路：该问题为尺取经典问题，对每个位置 l 尺取出其对应 r 的最大合法位置，则 l 的贡献则为 r − l + 1，时间复杂度 O(n)。或者可以先统计出 0 的个数的前缀和，然后对每个 l 二分 r，贡献同理，时间复杂度O(nlogn)。
补充：尺取法（我第一次听这个说法。。。），一般是在给的一组数据中找到不大于某一个上限的“最优连续子序列” 。
AC代码：
（1）尺取法：（看了别人的代码才明白是怎么模拟的，代码能力亟需提高）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>
#include <numeric>
using namespace std;
typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int t;
int n,k;
string s;
int cnt;
ll ans;
int l,r;
int main()
{
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
cin>>t;
while(t--)
{
cin>>n>>k;
cin>>s;
l=0,r=0,cnt=0,ans=0;
while(r<n)
{
if(s[r]=='0')
++cnt;
while(cnt>k&&l<=r)//同时更新l的位置，不需要两层循环嵌套
{
if(s[l]=='0')
--cnt;
l++;
}
ans+=r-l+1;
r++;
}
cout<<ans<<'\n';
}
return 0;
}
大概操作是：l=0开始，计算r逐渐增大时0的个数，大于给定值时l向右移一位，同时计算在合法的l和r时的贡献。
（2）前缀和+二分STL解决：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>
#include <numeric>
using namespace std;
typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1e5+10;
int dif[N];
int t,n,k;
string s;
ll ans;
int main()
{
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
cin>>t;
while(t--)
{
memset(dif,0,sizeof(dif));
cin>>n>>k;
cin>>s;
if(s[0]=='0')
dif[0]=1;
else
dif[0]=0;
for(int i=1;i<n;i++)
{
if(s[i]=='0')
dif[i]=dif[i-1]+1;
else
dif[i]=dif[i-1];
}
ans=0;
for(int i=0;i<n;i++)
{
ans+=upper_bound(dif,dif+n,dif[i-1]+k)-dif-i;
}
cout<<ans<<'\n';
}
return 0;
}
ps：之前师哥讲二分的时候提到STL里的lower_bound()和upper_bound()但没用过，学习了，，，
D 送快递（最短路+贪心？）
废话可跳过：结训赛之前没几天刚讲的最短路，我还没整明白QWQ，，，考完期末一定好好搞一下图论，我可太不会了
思路：处理出从 0 号点到 i 号点的最短路 dis[i]，即快递 i 的派送费或罚款，然后按照快递的截止时间从小到大排序。做反悔型贪心即可，具体为维护一个小根堆，堆内存储计划派送的快递的派送费。从前往后依次扫描所有快递，对于 i 号快递，若堆的大小小于 i 号快递的截止时间，则说明此快递可正常派送；否则比较 dis[i] 与堆顶的大小，若 dis[i] 大于堆顶元素则说明派送 i 号快递而不派送堆顶快递更优，否则不派送 i 号快递而派送堆顶快递更优。时间复杂度 O(nlogn + nlogm)。
（优先队列我也之前没怎么用过。。。）
AC代码：（看了师哥的代码才明白是怎么搞的，部分解释在注释中）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=2e5+10;
ll n,m;
int head[N],cnt;
ll dis[N];
bool vis[N];
struct node
{
ll to,next,w;
} e[N];
void addedge(int x,int y,ll z)//链式前向星加边函数
{
e[++cnt].w=z;
e[cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt;
}
struct people
{
int time;
ll dis;
} a[N];
bool cmp(people a,people b)
{
if(a.dis>b.dis) return true;
else if(a.dis==b.dis&&a.time<b.time) return true;
else return false;
}
void dijkstra(int s)//Dijkstra处理从0到i点最短路
{
memset(dis,0x3f,sizeof(dis));
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>q;
q.push({0,s});
dis[s]=0;
while(!q.empty())
{
int now=q.top().second;//now为点的编号
q.pop();
if(vis[now])
continue;
vis[now]=1;
for(int i=head[now];i;i=e[i].next)
{
int to=e[i].to;
if(dis[to]>dis[now]+e[i].w)
{
dis[to]=dis[now]+e[i].w;
q.push({dis[to],to});
}
}
}
}
int main()
{
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
addedge(x,y,z);
addedge(y,x,z);//无向图，双向加边
}
dijkstra(0);
for(int i=1;i<=n;i++)
{
cin>>a[i].time;
a[i].dis=dis[i];
}
sort(a+1,a+1+n,cmp);
memset(vis,0,sizeof(vis));
ll ans=0;
int l=1;
for(int i=1;i<=n;i++)
{
if(!vis[a[i].time])
{
ans+=a[i].dis;
vis[a[i].time]=1;
}
else
{
int k=a[i].time-1;
while(vis[k]&&k>=1)
--k;//带有反悔的贪心
if(!vis[k]&&k>=1)
vis[k]=1,ans+=a[i].dis;
else
ans-=a[i].dis;
}
}
cout<<ans<<'\n';
return 0;
}
os：带有反悔的贪心，这种方法也是第一次见，，，学习了
H Surprising Prime（规律，暴力）
题意：定义surprising prime是可以写成两个平方数加和的素数，求给定区间内这种数的个数。
废话可跳过：虽然是英文题面，但还是挺好懂的，，，一开始试图找规律但是没找出来，感觉暴力的话1e7应该不太行吧，结果事实证明是可以的，，，
思路：打表找规律容易发现 Surprising Prime 就是 2 或者模 4 为 1 的质数。证明比较麻烦，可自行百度。（能猜出来还要什么证明啊
另外有暴力做法如下：
首先，观察数据范围 [1, 107]，用线性筛预先处理好素数，然后我们发现
= 3162，直接处理出[1, 107] 范围内的平方数，然后暴力枚举寻找 [1, 107] 范围内能够被两个平方数加和表示出来的素数，对答案的个数贡献标记为 true，然后从 [1, 107] 做一遍前缀和预处理一下。询问直接 O(1) 回答即可。（粘贴的师哥写的题解：P）
AC代码：
（1）按照规律：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>
#include <numeric>
using namespace std;
typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1e7+10;
int prime[N];
bool mark[N];
int tot;
int q,l,r;
void oula()
{
mark[1]=true;
for(int i=2;i<=N;i++)
{
if(!mark[i])
prime[++tot]=i;
for(int j=1;j<=tot;j++)
{
if(i*prime[j]>N)
break;
mark[i*prime[j]]=true;
if(i%prime[j]==0)
break;
}
}
}
int main()
{
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
cin>>q;
oula();
while(q--)
{
cin>>l>>r;
int cnt=0;
for(int i=l;i<=r;i++)
{
if(!mark[i]&&i==2)
++cnt;
if(!mark[i]&&i%4==1)
++cnt;
}
cout<<cnt<<'\n';
}
return 0;
}
（2）暴力：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>
#include <numeric>
using namespace std;
typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1e7+10;
int prime[N];
bool mark[N];
bool b[N*2];
int tot;
int q,l,r;
void oula()
{
mark[1]=true;
for(int i=2;i<=N;i++)
{
if(!mark[i])
prime[++tot]=i;
for(int j=1;j<=tot;j++)
{
if(i*prime[j]>N)
break;
mark[i*prime[j]]=true;
if(i%prime[j]==0)
break;
}
}
}
void pan()
{
for(int i=1;i<=sqrt(10000000);i++)
{
for(int j=1;j<=sqrt(10000000);j++)
{
b[i*i+j*j]=true;
}
}
}
int main()
{
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
cin>>q;
oula();
pan();
while(q--)
{
cin>>l>>r;
int cnt=0;
for(int i=l;i<=r;i++)
{
if(!mark[i]&&b[i])
++cnt;
}
cout<<cnt<<'\n';
}
return 0;
}
J 远行（模拟）
废话可跳过：这个题，我在半小时解决完前两道之后就一直在搞这个题，一开始以为是类似LIS问题，写了半天DP，发现是一段连续区间，，，不认真读题害我 ，，然后开始用普通方法模拟，一直WA，不过最后做出来了（太艰难了QWQ）
思路：我是开了两个数组，从前向后遍历，找出不递减长度，再从后向前遍历，找出不递增长度，一一对应相加，最大的为答案。
AC代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>
#include <numeric>
using namespace std;
typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=5e5+5;
int n;
int a[N],b[N],c[N];
int maxn1,maxn2;
int main()
{
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
b[i]=1,c[i]=1;
for(int i=2;i<=n;i++)
{
if(a[i]>=a[i-1])
b[i]=b[i-1]+1;
maxn1=max(maxn1,b[i]);
}
for(int i=n-1;i>=1;i--)
{
if(a[i]>=a[i+1])
c[i]=c[i+1]+1;
maxn2=max(maxn2,c[i]);
}
int ans=-1;
for(int i=1;i<=n;i++)
{
ans=max(ans,c[i]+b[i]);
}
cout<<ans-1<<'\n';
return 0;
}
M - XCPX（暴力/对角线前缀和）
思路：暴力即可，标解是用的对角线前缀和。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int t,n,m,q,x,y,s;
bool check(int x,int y)
{
if(x>=1&&x<=n&&y>=1&&y<=m) return true;
else return false;
}
int main()
{
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
ios;
cin>>t;
while(t--)
{
cin>>n>>m>>q;
int c[n+3][m+3];
memset(c,0,sizeof(c));
while(q--)
{
cin>>x>>y>>s;
c[x][y]++;
for(int i=1;i<=s;i++)
{
int nx=x+i,ny=y+i;
if(!check(nx,ny)) break;
c[nx][ny]++;
}
for(int i=1;i<=s;i++)
{
int nx=x-i,ny=y+i;
if(!check(nx,ny)) break;
c[nx][ny]++;
}
for(int i=1;i<=s;i++)
{
int nx=x+i,ny=y-i;
if(!check(nx,ny)) break;
c[nx][ny]++;
}
for(int i=1;i<=s;i++)
{
int nx=x-i,ny=y-i;
if(!check(nx,ny)) break;
c[nx][ny]++;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cout<<c[i][j]<<" \n"[j==m];
}
}
return 0;
}
os：数据水吧应该是，否则按照最大范围存图的二维数组都开不了
结训赛结束两个月才补题还没补完，，，加油哇
若有错误请指教orzorz
这篇关于2021年SDNU-ACM集训队结训赛（补题）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
怎么实现ansible playbook 备份代码中命名包含时间戳功能？-icode9专业技术文章分享11-22
-
ansible 的archive 参数是什么意思？-icode9专业技术文章分享11-22
-
ansible 中怎么只用archive 排除某个目录？-icode9专业技术文章分享11-22
-
exclude_path参数是什么作用？-icode9专业技术文章分享11-22
-
微信开放平台第三方平台什么时候调用数据预拉取和数据周期性更新接口？-icode9专业技术文章分享11-22
-
uniapp 实现聊天消息会话的列表功能怎么实现？-icode9专业技术文章分享11-22
-
在Mac系统上将图片中的文字提取出来有哪些方法？-icode9专业技术文章分享11-22
-
excel 表格中怎么固定一行显示不滚动？-icode9专业技术文章分享11-22
-
怎么将 -rwxr-xr-x 修改为 drwxr-xr-x？-icode9专业技术文章分享11-22
-
在Excel中怎么将小数向上取整到最接近的整数？-icode9专业技术文章分享11-22
-
Excel中常见的取整函数有哪些？-icode9专业技术文章分享11-22
-
错误信息：does not match the actual quantity supplied 提示是什么意思？-icode9专业技术文章分享11-22
-
WebSocket学习：初学者的简单指南11-21
-
获取apk的md5值有哪些方法？-icode9专业技术文章分享11-20
-
xml报文没有传 IdentCode ，为什么正常解析没报错呢？-icode9专业技术文章分享11-20
栏目导航
