2019 第十四届 中北大学ACM程序设计竞赛 题解
A.CQW又迟到了
CQW是个坏学生，每天都迟到，从没看见他在第一节课出现过，懒惰的他，总是在点名的最后一刻出现。为了治一治他这个坏习惯，教C语言的XZW老师决定每天都给他布置一个单独的作业，并答应只要他每次都能正确完成作业就不点他的名字，CQW为了可以多睡觉，立刻答应了下来。为了让CQW知难而退，于是第一天XZW老师就布置了一个超级难的题！
将一个字符串循环打印输出成一个 n * n 的矩阵。
如输入：abcd
那么输出：
abcd
bcda
cdab
dabc
也就是说每次都将输出的上一个字符串的第一个字符移动到最后的位置形成新的字符串。
天哪！对于从来不上课的CQW同学来说这题实在是太难了。他听说你喜欢唱跳、rap和篮球，还练习了两年半的C语言，于是过来请求你的帮助，你可以帮帮他吗？
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
//#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn = 1e6+5;
const int INF = 0x3f3f3f3f;
int n,m,k;
signed main(){
fastio;
string str;
cin>>str;
n=str.size();
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<str[(j+i)%n];
}cout<<endl;
}
return 0;
}
B.CQW的倔强
LCH和LPF是大学，每天都在讨论一些很高深的问题，像迪利克雷卷积之类的简单东西，他们根本不屑一顾。CQW是出了名的学渣，可是学渣也是有上进心的呀，他相信天道酬勤，只要他肯努力，一定可以赶上LCH和LPF的。有道是，一定要努力，只有努力过后，才能明白自己真的是不行。CQW在一次LCH和LPF讨论完后，趁着他们出去的功夫，他偷到了他们使用的手稿！CQW如获至宝，马上就开始研究他们讨论的题目，只见纸上赫然出现几个大字：给出一个整数 n ，请出 1 - n 的所有数字中一共出现了多少个 9 。
能数位DP 但是暴力能过。。。。。
包含一个整数 n（1<= n <=1000000）。
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn = 1e6+5;
const int INF = 0x3f3f3f3f;
int n,m,k;
int chk(int i){
int res=0;
while(i){
if(i%10==9) res++;
i/=10;
}
return res;
}
signed main(){
fastio;
cin>>n;
int ans=0;
for(int i=1;i<=n;i++){
ans+=chk(i);
}
cout<<ans<<endl;
return 0;
}
C.WYS非常方
在2019年3月底的团体程序设计天梯赛后，16级队员正式退役了，有的队员迅速找到了一份满意而体面的工作，有的队员估摸一算发现自己好像能保研了，还有一些队员则是在考研的道路上一往无前所向披靡，而有的队员懵在原地，不知所措。
WYS作为实验室中一个细心观察生活中点点滴滴的人，她很快就发现了实验室中某些人的状态很不对劲，常常呆在某个位置发呆，于是她向LZX，YXY等人询问情况，而却苦于心情难以用言语表达，决定由肢体语言表达出自己的心情----我很方，非常方。
作为一名实验室中考研人群中的一员，WYS发现自己似乎没有很多时间去处理这些问题，于是他把这个问题交给了你，希望你能够给出正确的答案。
我们简化问题，实验室有n(1<=n<=3000)个呆在原地的人，他们被看做为平面上的整数点（x，y)（1<=x,y<=5000)，要表达出他们有多方，一共需要满足两个条件：
1.组成一个正方形,只有特殊的正方形才能说明他们非常方
2.组成的正方形尽可能大
即我们要找到平面上四个人组成的最大的正方形面积为多少？
n^2 枚举 用向量找点 因为都是整数坐标 。。。 所以对应点也是整数坐标 要是用单位向量 又去搞了 根号找距离 大概精度不够wa了
#include <bits/stdc++.h>
#define double int
using namespace std;
const double eps = 1e-8;
bool mp[5005][5005];
struct node {
int x;
int y;
} a[3005];
double ans=0;
bool chk(int x,int y){
if(x>=0&&y>=0&&y<=5000&&x<=5000){
if(mp[x][y]==1) return 1;
}
return 0;
}
void dodeal(int i,int j) {
int tx,ty;
tx=a[i].x-a[j].x;
ty=a[i].y-a[j].y;
int x=-ty;
int y=tx;
if(chk(a[i].x+x,a[i].y+y)&&chk(a[j].x+x,a[j].y+y)){
ans=max(ans,x*x+y*y);
}
if(chk(a[i].x-x,a[i].y-y)&&chk(a[j].x-x,a[j].y-y)){
ans=max(ans,x*x+y*y);
}
}
signed main() {
int n;
cin>>n;
for(int i=1; i<=n; i++) {
cin>>a[i].x>>a[i].y;
mp[a[i].x][a[i].y]=1;
}
ans=0;
for(int i=1; i<=n; i++) {
for(int j=i+1; j<=n; j++) {
dodeal(i,j);
}
}
if(ans==0) cout<<-1<<endl;
else cout<<(int)ans<<endl;
return 0;
}
D.绝对强者LYF
LYF是一个篮球高手，为了展现自己的篮球技艺，他总和学弟们打篮球，希望通过虐小菜鸡们获得满足感，长久以来终于引起了公愤。为了制裁LYF，大家在暑假集训时进行了疯狂特训，如今已是今非昔比，现在的他们决定要选出他们中的绝对强者去制裁LYF，绝对强者要求：得分、篮板、助攻、抢断、封盖，五项数据都没有人比他高才行。你可以选出绝对强者吗？
存最大 直接找
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn = 1e3+5;
const int INF = 0x3f3f3f3f;
int n,m,k;
struct node{
int a,b,c,d,e;
int id;
}q[maxn];
signed main(){
fastio;
cin>>n;
int ans=0;
int a,b,c,d,e;
int ma=-1,mb=-1,mc=-1,md=-1,me=-1;
for(int i=1;i<=n;i++){
cin>>a>>b>>c>>d>>e;
q[i]=node{a,b,c,d,e,i};
ma=max(ma,a);
mb=max(mb,b);
mc=max(mc,c);
md=max(md,d);
me=max(me,e);
}
for(int i=1;i<=n;i++){
if(ma==q[i].a&&q[i].b==mb&&q[i].c==mc&&q[i].d==md&&q[i].e==me){
cout<<i<<endl;
return 0;
}
}
cout<<"WO LYF MEI YOU KAI GUA !"<<endl;
return 0;
}
E.1009的奇思妙想
1009最近发现自己非常孤独,因为他开始有了自己的思想,并有了一个重大发现:除了1以外,他竟然不能被任何小于他的数整除!这可真是一个令人悲伤的发现呢.
后来慢慢的他意识到,他原来是一个较为特殊的数字–质数.
与此同时他还发现自己还有很多与他一样的小伙伴,如果他们能够抱团组成一个好大好大的数,这样他们就不会再孤独了.
于是他找到了和他长度相同的质数小伙伴,打算组成一个长度为x的超大数字
小伙伴们纷纷赞同1009的提议,并觉得如果单单拼在一起好像没什么难度,很无聊嘛,于是他们决定组合在一起,即他们要让组成的长度为x的数中,任意四个连续的数都是他的小伙伴(或者他自己),换句话说,就是组成的长度为x的数字中,任意连续四位都是一个质数且该质数不包含前导零.这样子大家你中有我,我中有你,只要有想组合的人(数字),就不是孤身一人(数字).
我们举个例子来说:对于98039这个数来说,连续的四位数有9803和8039,这两个数字都是质数,所以98039就算在长度为5的一种组成方法.
不过有多少种组成方式呢?1009想了很久,似乎还是想不来?那么你能解决这个问题吗?(答案对1e9+7取模)
注意:对于长度为5的位数来说,10097这种数字是不能算成一种组成方式的哦,因为连续的4位数右1009和0097,而0097虽然是一个质数,但他实际上是一个小于1000的数,即长度小于4,不是1009的小伙伴哦
每个数字出现次数可能不止一次,且1009无需在每次组合方案中出现,比如98039也可以当成一种组合方案
先打质数 找到1000到10000内的
我们发现 下一位连续4个质数 她的前3位和前一岑的4个质数 后三位一样
我们想到 dp[ 长度 ] [ 素数后3位 or前3位有关 ]
进而尝试一下 发现
dp[ k ] [ 素数%1000 ] += dp [ k - 1 ] [ 质数/10 ] ；不断累计
#include <bits/stdc++.h>
#define int long long
using namespace std;
const double eps = 1e-8;
int n,m;
const int mod = 1e9+7;
bool pri[10000];
int dp[3][1005];
int pre[2000];
int cnt;
void init(){
pri[0]=pri[1]=1;
for(int i=2;i<10000;i++){
if(pri[i]==0){
pre[++cnt]=i;
if(i<10000&&i>1000) dp[0][i%1000]++;
for(int j=i+i;j<10000;j+=i){
pri[j]=1;
}
}
}
// for(int i=1;i<=cnt;i++){
// if(pre[i]>=1000&&pre[i]<=10000) cout<<i<<" "<<pre[i]<<endl;
// // else if(pre[i]<=10000) cout<<i<<endl;
// }
}
signed main() {
int x;
cin>>x;
init();
for(int i=5;i<=x;i++){
for(int j=169;j<=1229;j++){
dp[i%2][pre[j]%1000]=dp[i%2][pre[j]%1000]+dp[(i-1)%2][pre[j]/10];
dp[i%2][pre[j]%1000]%=mod;
}
for(int j=0;j<1000;j++) dp[(i-1)%2][j]=0;
}
int ans=0;
for(int i=0;i<1000;i++){
ans+=dp[x%2][i];
ans%=mod;
}
cout<<ans<<endl;
return 0;
}
F.CQW的幸福
在很久很久以前，CQW喜欢上了一个女孩，可是CQW是一个爆脾气。恰好这个女孩喜欢脾气好的男孩子。于是CQW为了追求这个女孩子，就跑去找巫师NCE。NCE听闻此事之后，告诉CQW在珠穆朗玛之巅有一瓶宝贵的神药可以帮他解决这个问题，并且告知CQW在神药外围有一道机关，这个机关需要让他求出最小的有4^n个因子的数是多少，这一下子难住了CQW，于是CQW向你发起了求助，不知道聪明的你能不能帮CQW完成心愿，要知道CQW的幸福已经在你手中了！
4^n 变为 2^n
因子数 4 16 48 而质因子+1 连积 是约束个数 考虑每个素数贡献度
4个 约数的时候 是6 1 2 3 6 2^2 *3^1
2 下次在出现 如果想对于 2^n 有贡献度 必然是2^2
所以 我们把每次用过的数据平方放回去 一是保证最优同时最小 还确定了贡献度+1
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn = 1e7+5;
const int INF = 0x3f3f3f3f;
int cnt;
bool isp[maxn];
priority_queue<int,vector<int>,greater<int> > que;
void init(){
for(int i=2;i<maxn;i++){
if(!isp[i]){
que.push(i);
for(int j=i+i;j<maxn;j+=i) isp[j]=1;
}
}
}
const int mod = 998244353 ;
signed main() {
int n;
init();
cin>>n;
ll ans=1;
for(int i=1;i<=n;i++){
int res=que.top();
que.pop();
ans=ans*res%mod;
que.push(res*res);
// cout<<res<<endl;
res=que.top();
que.pop();
ans=ans*res%mod;
que.push(res*res);
//cout<<res<<" "<<ans<<endl;
}
cout<<ans<<endl;
return 0;
}
G.FWJ的追求者
众所周知FWJ是一位打篮球特别厉害而且长得特别好看的小姐姐，迷倒了一群又一群篮球场上的小哥哥。最近又有一个小哥哥拜倒在了FWJ的石榴裙下，小哥哥展开了疯狂的最求，每天都送零食来实验室，FWJ小姐姐要保持身材，这些零食当然都到CQW的肚子里去了。可是FWJ早就对XZW芳心暗许，又怎会答应别人的最求呢？于是FWJ想让这位小哥哥知难而退，给他出了一道难题，题目如下：
商店里有1到n元的商品，现在让你设计一种货币的面额
使得你手里的货币，可以买到1-n元的商品之间的任意一种
求不同货币面值数目最小的设计方法
这位小哥哥很不甘心就这样放弃，于是向聪明的你发起了求救，你能否帮他解决这一难题呢？
洛谷原题。。。。
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0)
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn = 1e3+5;
const int INF = 0x3f3f3f3f;
int n,m,k;
struct node{
int a,b,c,d,e;
int id;
}q[maxn];
signed main(){
fastio;
int cas;
cin>>cas;
while(cas--){
cin>>n;
int res=0;
while(n){
res++;
// cout<<n/2<<endl;
n/=2;
}
cout<<res<<endl;
}
return 0;
}
H.ZBT的学分
现在有N个活动，ZBT完成每个活动都可以获得一些学分，各个活动的获得的学分不尽相同，每个活动最多只能参加一次。
ZBT缺K个学分才能毕业，ZBT必须修够K个学分，不然他不能毕业，同时ZBT作为一个强迫症患者，有如下要求：
-
他不想获得超过K个学分，也就是ZBT最后参加活动获得的总学分刚好是K个。 -
如果有一些活动是他喜欢的活动，他哪怕影响毕业也要在这些活动中参加至少一个。
现在他问你总共有多少个参加活动的方案数可以满足他的条件？
枚举 喜欢的 然后剩下的分2块 二分查 减低复杂度
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k;
const int maxn = 55 ;
int a[maxn],b[maxn];
bool vis[maxn];
int q[maxn],h[maxn];
int qq[(1<<16)+10],hh[(1<<16)+10];
int ans;
signed main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
cin>>k>>m;
for(int i=0;i<m;i++) cin>>b[i],b[i]--;
if(m==0){
int cnt1=0,cnt2=0;
int resk=k;
for(int j=0;j<n;j++){
if(cnt1<cnt2) q[cnt1++] = a[j];
else h[cnt2++] = a[j];
}
int cn1=(1<<cnt1);
int cn2=(1<<cnt2);
for(int j=0;j<(cn1);j++){
qq[j]=0;
for(int z=0;z<=17;z++)
if(j&(1<<z)) qq[j]+=q[z];
}
for(int j=0;j<(cn2);j++){
hh[j]=0;
for(int z=0;z<=17;z++)
if(j&(1<<z)) hh[j]+=h[z];
}
sort(hh,hh+cn2);
for(int j=0;j<cn1;j++){
ans+=(upper_bound(hh,hh+cn2,resk-qq[j])-lower_bound(hh,hh+cn2,resk-qq[j]));
}
}
else for(int i=0;i<m;i++){
vis[b[i]]=1;
int cnt1=0,cnt2=0;
int resk=k-a[b[i]];
for(int j=0;j<n;j++){
if(vis[j]) continue ;
else if(cnt1<cnt2) q[cnt1++] = a[j];
else h[cnt2++] = a[j];
}
int cn1=(1<<cnt1);
int cn2=(1<<cnt2);
for(int j=0;j<(cn1);j++){
qq[j]=0;
for(int z=0;z<=17;z++)
if(j&(1<<z)) qq[j]+=q[z];
}
for(int j=0;j<(cn2);j++){
hh[j]=0;
for(int z=0;z<=17;z++)
if(j&(1<<z)) hh[j]+=h[z];
}
sort(hh,hh+cn2);
for(int j=0;j<cn1;j++){
ans+=(upper_bound(hh,hh+cn2,resk-qq[j])-lower_bound(hh,hh+cn2,resk-qq[j]));
}
}
cout<<ans<<endl;
return 0;
}
I.SHT的梦想
欧拉降幂 + 线段树 不会数学 告辞
J.ZBT的游戏
区间计数 裸题 数据应该是水了 0 1 0 1 0 1 底层要是这样的数据 都n2卡死了 正解要不离线 要不莫队分块来着
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn = 2e6+5;
const int INF = 0x3f3f3f3f;
struct node{
int col;
int laz;
}tree[maxn<<2];
void pushup(int rt){
if(tree[rt<<1].col!=tree[rt<<1|1].col) tree[rt].col=-1;
else tree[rt].col=tree[rt<<1].col;
}
void pushdown(int rt){
if(tree[rt].laz!=0){
tree[rt<<1].col=tree[rt<<1|1].col=tree[rt].laz;
tree[rt<<1].laz=tree[rt<<1|1].laz=tree[rt].laz;
tree[rt].laz=0;
}
}
void update(int L,int R,int l,int r,int rt,int c){
if(L<=l&&R>=r){
tree[rt].laz=c;
tree[rt].col=c;
return ;
}
pushdown(rt);
int mid=(l+r)>>1;
if(L<=mid) update(L,R,l,mid,rt<<1,c);
if(mid<R) update(L,R,mid+1,r,rt<<1|1,c);
pushup(rt);
}
set<int> S;
int query(int L,int R,int l,int r,int rt){
if(L<=l&&r<=R&&tree[rt].col!=-1){
if(tree[rt].col!=0) S.insert(tree[rt].col);
return 0;
}
if(l==r){
if(tree[rt].col!=0) S.insert(tree[rt].col);
return 0;
}
pushdown(rt);
int mid=(l+r)>>1;
if(L<=mid) query(L,R,l,mid,rt<<1);
if(R>mid) query(L,R,mid+1,r,rt<<1|1);
pushup(rt);
}
signed main() {
int cas;
int n,m,k;
// freopen("a.in","r",stdin);
// freopen("a.out","w+",stdout);
scanf("%d%d%d",&n,&m,&k);
char cmd[20];
int l,r;
int f=0;
for(int i=1;i<=m;i++){
scanf("%s %d %d",cmd,&l,&r);
int t;
if(cmd[0]=='C'){
scanf("%d",&t);
update(l,r,1,n,1,t);
}else{
f=1;
S.clear();
query(l,r,1,n,1);
printf("%d\n",S.size());
}
}
if(!f) printf("This is a boring game!\n");
return 0;
}
K.ZJ和LQW打羽毛球
不会
L.SW和ZK的恋爱
lcm 比如说 8 2个0 你就。。。。找8和200的lcm orz
查看18道真题和解析
CVTE公司福利 265人发布
投递华为等公司10个岗位