校赛题解

2021校赛：

感受：

​ 校赛算是选拔蓝桥杯省赛，但是这次题目给了1道签到题+两道语法题+2道算法题（可以保证基本没人写出来的那种）。所以导致只要语法有基础+手速够快就能得奖并且获得蓝桥杯参赛资格。

​ 然而，因为最后一题因为数据问题（过于氵），导致只要稍微有点思路就能AC，但其实正解没有人写出来，所以这次的校赛其实真的氵。

题解：

A

等级：语法题

解析：

​ 从最后一天剩一个开始向前推，每向前一天+1然后*2，总共n-1天。

​ 一个for循环就行。

代码：

//c
#include<stdio.h>
int main()
{
	int n;
    scanf("%d",&n);
	int sum=1;
	for(int i=1;i<n;i++)
	{
		sum=(sum+1)*2;
	}
	printf("%d"sum);
    return 0;
}
//c++
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int n;cin>>n;
	int sum=1;
	for(int i=1;i<n;i++)
	{
		sum=(sum+1)*2;
	}
	cout<<sum;
}

B

等级：语法题

解析：

​ 将头左斜45°，它就变成了一个金字塔形状的数列，然后这样斜着进行更新（指填数）。

​ 最后直接两重for控制输出即可。

代码：

//c
#include<stdio.h>
int a[110][110];
int main()
{
	int n;
    scanf("%d",&n);
	int num=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			a[i-j+1][j]=num++;
		}
	}
	for(int i=1;i<=n+1;i++)
	{
		for(int j=1;j<=n-i+1;j++)
		{
			printf("%d "a[i][j]);
		}
		printf("\n");
	}
	
}
//c++
#include<iostream>
#include<algorithm>
using namespace std;
int a[110][110];
int main()
{
	int n;cin>>n;
	int num=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			a[i-j+1][j]=num++;
		}
	}
	//cout<<num<<endl;
	for(int i=1;i<=n+1;i++)
	{
		for(int j=1;j<=n-i+1;j++)
		{
			cout<<a[i][j]<<' ';
		}
		cout<<endl;
	}
	
}

C

等级：算法题（图的dfs）

解析：

​ 首先要会图的存储，然后每个点dfs，并每次成立的时候情况++就行了。

​ （新生不建议写[doge]）

代码：

//c++
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int h[N],e[N*2],ne[N*2],idx;
int n,m,d[N],num=0;
int st[N];
int sum=0;
void add(int a,int b)
{
	e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void dfs2(int u)
{
    num++;st[u]=1;
	if(num==4)
	{
		sum++;
		return;
	}
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(num==3 && st[j]==2)
		{
		  sum++;
		  continue;
		}
		else if(!st[j])
		{
			dfs2(j);
			st[j]=0;
			num--;
		}
	}
	st[u]=0;
}
void dfs(int u)
{
	num=1;st[u]=2;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		dfs2(j);
		num--;
	}
	st[u]=0;
}
int main()
{
	memset(h,-1,sizeof h);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);add(b,a);
		d[a]++,d[b]++;
	}
// 	if(n<=3 || m<=2)//比赛时写的特判情况之一
// 	{
// 		cout<<0;
// 		return 0;
// 	}
	for(int i=1;i<=n;i++)
	{
		dfs(i);
	}
	cout<<sum;
}

D

等级：语法题

解析：

​ 大水题，我上课讲的都比这难。

​ 时分秒表示出来然后输出就行，我上课讲的个位前补零的情况也没有。

时：a=t/3600

分：b=t%3600/60

秒：c=t%60

代码：

//c
#include<stdio.h>
int main()
{
	int t;
	scanf("%d",&t);
	int a=t/3600,b=t%3600/60,c=t%60;
	printf("%d:%d:%d",a,b,c);
		
}
//c++
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

int main()
{
	int t;cin>>t;
	int a=t/3600,b=t%3600/60,c=t%60;
	printf("%d:%d:%d",a,b,c);
		
}

E

等级：语法题（暴力）~算法题（线性DP）

解析：

​ 因为数据特别氵，所以只要思路还好的的暴力都可以过，但是暴力过了其实不代表个人实力。

然而正解是一个思路比较清奇（分组）的线性dp。

​ 暴力可以问你们杨琳涵学姐、唐鑫学长、赵普学长（他说直接给你们讲线性dp的解法[doge]）和我。

​ 线性dp版可以找你们赵普学长。(我懒得讲)

​ 新生不建议写（暴力建议练其他题，dp算法还没学）

代码：

//暴力
#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int b[N],a[N],idx;
bool st[N];
int n,k;

int main()
{
	cin>>n>>k;
	int t;
	for(int i=1;i<=n;i++)
	{
		cin>>t;
		if(!b[t])a[idx++]=t;
		b[t]++;
	}
	if(k==0)
	{
		cout<<idx;
		return 0;
	}
	sort(a,a+idx-1);
	int sum=0;
	for(int i=1;i<=k;i++)
	{
		sum+=b[i];
		st[i]=1;
		for(int j=i+k;j<=100010;j+=k)
		{
			if(st[j-k]==1 && b[j-k]<b[j])
			{
				sum+=b[j]-b[j-k];
				st[j]=1;st[j-k]=0;
			}else if(st[j-k]==0)
			{
				sum+=b[j];
				st[j]=1;
			}
		}
	}
	cout<<sum;
}
//dp
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int b[N],a[N],idx;
int f[N],st[N];
int n,k;
int main()
{
	cin>>n>>k;
	int t;
	for(int i=1;i<=n;i++)
	{
		cin>>t;
		if(!b[t])a[idx++]=t;
		b[t]++;
	}
	if(k==0)
	{
		cout<<idx;
		return 0;
	}
	sort(a,a+idx-1);
	int sum=0,j,i;
	for(i=1;i<=k;i++)
	{
	    int cnt=1;
	    for(int j=i;j<=100000;j+=k,cnt++)
	    {
	        f[cnt]=f[cnt-1];
	        if(j>=2)f[cnt]=max(f[cnt-2]+b[j],f[cnt]);
	    }
	    sum+=f[cnt-1];
	}
	cout<<sum;
}