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],用线性筛预先处理好素数,然后我们发现\sqrt{1e7}= 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集训队结训赛(补题)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!