2022警大程序设计大赛题解


2022警大程序设计大赛题解


Ordeal

签到题,直接进行输出就行。

#include <iostream>
using namespace std;
int main () {
	cout << "Jindexiuye,Jingwubowen!";
	return 0;
}

Calling

条件判断,对周三周六进行特判。

#include <iostream>
using namespace std;
int main () {
	int x;
	cin >> x;
	if (x==3||x==6)	cout << "Y";
	else cout << "N";
	return 0;
}

Desire to eat

输出图形问题,可以观察到从第一行开始有n个n,n-1行有n-1个n-1,以此类推到最后第一行1个1,最后在推回到n行。

#include<iostream>
using namespace std;
int n;
int main()
{
	scanf("%d",&n);
	for(int i=n;i>=1;i--,puts(""))
		for(int j=1;j<=i;j++)
			printf("%d ",i);
	for(int i=2;i<=n;i++,puts(""))
		for(int j=1;j<=i;j++)
			printf("%d ",i);
	return 0;
 }

Learning Format

字符串的考点,开一个数组存一下字符串,判断一下%后的字符是什么即可。注意要先存一下字符串的长度strlen不是内联函数。

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e6+10;
int len; 
char str[N];
int c,s,d;
int main()
{
	scanf("%s",str);
	len=strlen(str);
	for(int i=0;i<len;i++)
		if(str[i]=='%')
		{
			if(str[i+1]=='d')	d++;
			else if(str[i+1]=='c') c++;
			else if(str[i+1]=='s') s++;
		}
	printf("%d\n%d\n%d\n",c,s,d);
	return 0;
 }

Mavin Haogod

读懂题目意思,至少有h篇的被引频次不低于h次,可以利用桶排的思维去维护每一个数的出现的次数,即a[i]代表i出现的次数,我们从大到小或者从小到大去枚举一遍就可以。

#include<stdio.h>
#include<algorithm>
using namespace std;
const int N = 1e6+7;
int n,x,k,sum;
int a[N];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		scanf("%d",&x);
		a[x]++;
		if (x>k) k=x;
	}
	while (k>=0){
		sum+=a[k];
		if (sum>=k) break;
		k--;
	}
	printf("%d",k);
	return 0;
}

The League of Shadows

这道题目保证了没有环的出现,但是可能会有重边的出现,对于重边我们只需要认为是两条路即可,不会干扰结果,但是我们不能从root节点去进行搜索,正解是判断每一个点的入度,对于入度为0的点就是起始点,把它们全部放到队列里进行拓补排序。同时要考虑到数据溢出的情况,需要用long long来进行存储取模。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5+10,M = 1e6+10;
const int mod = 1e9+7;
int n,m;
int hh,tt;
LL per[N]; 
int indegree[N],q[N];
int head[N],idx;
struct Edge{
	int next,to,f;
}edge[M<<1];
void add(int a,int b,int c)	{
	edge[idx]=(Edge){head[a],b,c},head[a]=idx++;
}
int main()
{
	memset(head,-1,sizeof head);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b,v;
		scanf("%d%d%d",&a,&b,&v);
		add(a,b,v),	indegree[b]+=1;
	}
	for(int i=1;i<=n;i++)
		if(!indegree[i])	q[tt++]=i,per[i]=1;
	while(hh!=tt)
	{
		int u=q[hh++];
		for(int i=head[u];~i;i=edge[i].next)
		{
			int v=edge[i].to;
			per[v]=(per[v]+edge[i].f*per[u])%mod;
			if(--indegree[v]==0)	q[tt++]=v;
		}
	}
	printf("%lld\n",per[1]);
	return 0;
}

Wine Conference

本题目的题意是在一个二维平面有n个有权值的点,需要对m个区域进行询问,求出该区域内的权值总和。对于30%的数据可以直接用二维的表进行存储,利用暴力直接判断即可。对于60%的数据,我们可以进行排序后进行统计,或者利用二维数组的差分进行求解都可以拿到部分分。对于100%的数据正解是利用离散扫描线求解或者利用CDQ分治进行求解。CDQ分治的思路是把横纵坐标当成前二维,第三维的赋值是把n个权值点作为0,把m个询问的左下右上两点坐标作为1,进行CDQ排序后再利用差分的思想去解决。

#include<iostream>
#include<cstring>
#include<algorithm>
typedef long long LL;
using namespace std;
const int N = 5e5+10;
int n,m;
struct Date{
    int a,b,c,s;
    int id,sign;
    LL res;
    bool operator < (const Date& t)const
    {
        if(a!=t.a)  return a<t.a;
        if(b!=t.b)  return b<t.b;
        return c<t.c;
    }
}q[N],w[N];
LL ans[N];
void merge_sort(int l,int r)
{
    if(l>=r)    return;
    int mid=l+r>>1;
    merge_sort(l,mid),merge_sort(mid+1,r);
    LL sum=0;
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
        if(q[i].b<=q[j].b)   sum+=!q[i].c*q[i].s,w[k++]=q[i++];
        else    q[j].res+=q[j].c*sum,w[k++]=q[j++];
    while(i<=mid)   sum+=!q[i].c*q[i].s,w[k++]=q[i++];
    while(j<=r) q[j].res+=q[j].c*sum,w[k++]=q[j++];
    for(int i=l,j=0;j<k;i++,j++)    q[i]=w[j];
}
int main()
{
    int k=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        q[k++]={a,b,0,c};
    }
    for(int i=1;i<=m;i++)
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        q[k++]={x1-1,y1-1,1,0,i,1};
        q[k++]={x1-1,y2,1,0,i,-1};
        q[k++]={x2,y1-1,1,0,i,-1};
        q[k++]={x2,y2,1,0,i,1};
    }
    sort(q,q+k);
    merge_sort(0,k-1);
    for(int i=0;i<k;i++)
        if(q[i].c)
            ans[q[i].id]+=q[i].sign*q[i].res;
    for(int i=1;i<=m;i++)    printf("%lld\n",ans[i]);
    return 0;
}

总结

2022年12月10号,中国人民警察大学程序设计大赛已落幕,获奖名单将在这两天我们排查以后按照学校的文件要求进行公布,请大家耐心等待。最后感谢各位参赛的同学和各位出题人监考同学及老师。


文章作者: Dydong
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Dydong !
  目录