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