2021年SDNU-ACM集训队结训赛（补题）
2022/2/12 23:15:06
本文主要是介绍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集训队结训赛（补题）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办？-icode9专业技术文章分享
- 2024-06-26终极指南：Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain
