2020.2.7 C组模拟赛题解

目录：

T1：权势二进制
T2：num
T3：attack
T4：h3

T1：权势二进制

题目描述

一个十进制整数被叫做权势二进制，当他的十进制表示的时候只由0或1组成。例如0，1，101，110011都是权势二进制而2，12，900不是。
当给定一个n的时候，计算一下最少要多少个权势二进制相加才能得到n。

输入

k组测试数据。
第1行给出一个整数k (1<=k<=10)
第2到k+1行每行一个整数n(1<=n<=1000000)

输出

输出答案占k行。
每行为每个n的答案。

样例输入

1
9

样例输出

9

分析：

一开始我还以为要做什么二进制转换，事实上样例就说明了：这道题的做法其实就是
把输入的数n的每一位提取出来，值最大的那一位就是答案，直接输出即可。
————————————————————————————————————

CODE：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,maxx,num; 
int main()
{
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	scanf("%d",&n);  //输入n
	for(int i=1;i<=n;i++)
	{
		maxx=0; //最大值每次清零
		scanf("%d",&num);
		while(num)
		{
			maxx=max(maxx,num%10);  //求最大的那一位
			num/=10;
		}
		printf("%dn",maxx);  //输出
	}
	
	return 0;
}

T2:num

题目描述

   KC邀请他的两个小弟K和C玩起了数字游戏。游戏是K和C轮流操作进行的，K为先手。KC会先给定一个数字Q，每次操作玩家必须写出当前数字的一个因数来代替当前数字，但是这个因数不能是1和它本身。例如当前数字为6，那么可以用2,3来代替，但是1和6就不行。现在规定第一个没有数字可以写出的玩家为胜者。K在已知Q的情况，想知道自己作为先手能不能胜利，若能胜利，那么第一次写出的可以制胜的最小数字是多少呢？整个游戏过程我们认为K和C用的都是最优策略。

输入

只包括一个正整数Q

输出

第一行是1或2,1表示K能胜利，2表示C能胜利。
若K能胜利，则在第二行输出第一次写出的可以制胜的最小数字，若是第一次就无法写出数字，则认为第一次写出的可以制胜的最小数字为0。
说明：若C能胜利，不用输出第二行，输出2即可。

样例输入

6

样例输出

2

分析：

这道题分三种情况：
1.q本身是质数：输出1换行再输出0。
2.q为两个质数的乘积(质数相同也可以)：输出2。
3.q为多个质数的乘积(也可以相同)：输出1换行再输出q的两个最小质因数的乘积。
但是我在找质数那里多了几个大括号，导致我0分？？？？？？

这就离谱

————————————————————————————————————

AC CODE：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#include<cmath>
#include<queue>
#define ll long long
using namespace std;
ll n,ans;
queue<ll>q;  //队列
int main()
{
    //freopen("num.in","r",stdin);
    //freopen("num.out","w",stdout);
    cin >> n;
    for(ll i = 2;i * i <= n;i++)
		while(n % i == 0)  //找质数
			q.push(i),n /= i;  //没有括号了
    if(n != 1)
		q.push(n);  //入队
    if(q.size() == 2)  //情况2
		printf("2n");
    else if(q.size() == 1)  //情况1
		printf("1n0n");
    else  //情况3
    {
        printf("1n");
        ans = q.front();
        q.pop();
        printf("%lldn",ans * q.front());
    }
    return 0;
}

T3：attack

题目描述

月球上反凤凰装甲在凤凰之力附身霍普之前，将凤凰之力打成五份，分别附身在X战警五大战力上面辐射眼、白皇后、钢力士、秘客和纳摩上（好尴尬，汗）。
在凤凰五使徒的至高的力量的威胁下，复仇者被迫逃到昆仑的一座山上，因为凤凰五使徒监视不到那里。
霍普加入了复仇者，为了磨练自己，她在n个山峰之间跳跃。
这n个山峰在一条直线上，每个山峰都有不同的高度，只知道这些山峰在水平上相对位置。霍普可以将这些山峰左右移动但不能改变他们的相对位置（要保证两两山峰间距为整数且大于等于1）。霍普要从最矮的山峰开始跳，每次跳向第一个比现在她所在的山峰高的山峰，一共跳n-1次，由于能力有限，每次跳跃的水平距离小于等于d。
霍普想知道如何移动这些山峰，使得在可以经过所有的山峰并跳到最高的山峰上的基础下，又要使最矮的山峰和最高的山峰的水平距离最远，霍普要你求出最远的水平距离。如果无论如何也不能经过所有的山峰并跳到最高的山峰上，那么输出-1。

输入

输入文件名为attack.in。
本题每个测试点有多组数据，
在第一行中有一个整数t，表示数据的数目（t<=500）
对于每组数据：
第一行包含两个整数n（1≤n≤1000）和d（1≤d≤1000000）。
下一行包含n个整数，给出n个山峰的高度，输入顺序即为山峰在水平上的相对顺序。在每个数据中，所有的高度都是唯一的。

输出

输出文件名为attack.out。
输出共t行。
对于每组数据输出最远的水平距离。如果无论如何也不能经过所有的山峰并跳到最高的山峰上，那么输出-1。

样例输入

3
4 4
20 30 10 40
5 6
20 34 54 10 15
4 2
10 20 16 13

样例输出

3
3
-1

分析：

这道题原来是最短路啊……
还以为是什么不可做的题呢……
条件1、两个山峰之间水平距离至少为1(因为山峰不能在同一位置上)。
条件2、霍普每次最多跳d的水平距离。
对于第一个条件，对于两个相邻的山峰，相对位置（即输入顺序）大的向相对位置小的连一条权值为-1的边。
对于第二个条件，对于两个高度排名相邻的山峰，相对位置小的向相对位置大的连一条d的边。
然后比较最高和最低的山峰，从相对位置小的那个山峰出发，跑一遍SPFA最短路，输出到相对位置大的山峰的距离。
————————————————————————————————————

CODE：

#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const int N=2005;
using namespace std;
struct node
{  
    int h,p;
}a[N];
int T,last[N*2],to[N*2],next[N*2],v[N*2],dis[N],n,d,tot,in[N*N],pp,num[N];
bool vis[N];
void gragh(int x,int y,int z)
{  //邻接表
    next[++tot]=last[x];
    last[x]=tot;
    to[tot]=y;
    v[tot]=z;
}
bool cmp(node x,node y)
{  //排序函数
    return x.h<y.h;
}
int spfa(int x)
{   //spfa最短路
    memset(vis,true,sizeof(vis));
    fill(dis,dis+1+n,1200000000);  //一个十分好用的赋值函数
    memset(num,0,sizeof(num));
    int head=0,tail=1,g;
    dis[x]=0;
    in[1]=x;
    while(head<tail)
    {  //spfa主体
        g=in[++head];
        vis[g]=true;
        for(long long i=last[g];i;i=next[i])
        {
            long long j=to[i];
            if(dis[j]>dis[g]+v[i])
            {
                dis[j]=dis[g]+v[i];
                if(vis[j])
                {
                    vis[j]=false;
                    in[++tail]=j;
                    if(++num[j]>n) return -1;
                }
            }
        }
    }
    return 0;
}
int main()
{
	//freopen("attack.in","r",stdin);
	//freopen("attack.out","w",stdout); 
    scanf("%d",&T);
    while(T--)
    {
        pp++; 
        scanf("%d%d",&n,&d);
        tot=0;
        memset(last,0,sizeof(last));
        memset(next,0,sizeof(next));
        memset(to,0,sizeof(to));
        memset(v,0,sizeof(v));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i].h);
            a[i].p=i;
            gragh(i,i-1,-1);  //连权为-1的边
        }
        sort(a+1,a+1+n,cmp);  //排序
        for(int i=1;i<=n-1;i++)
        {
            if(a[i].p<a[i+1].p)  //特判
                gragh(a[i].p,a[i+1].p,d);  //连边权为d
            else
                gragh(a[i+1].p,a[i].p,d);  //连边权为d
        }
        int e,k;
        if(a[1].p<a[n].p)
        {  //特判
            k=spfa(a[1].p);
            e=a[n].p;
        }
        else
        {
            k=spfa(a[n].p);  //相对位置小跑最短路
            e=a[1].p;
        }
        if(k==-1) printf("-1n");
        else
        {
            printf("%dn",dis[e]);
        }
    } 
} 

T4：h3

Description

“尼伯龙根是一棵由n-1条高架路连起n 个地区的树，每一次Load，你都会重生在某一个地区。如果重生点是整个尼伯龙根的重心，也就是这个树的重心，那么你就能在最短时间内带诺诺逃脱啦。”
“对了，再给你一点方便咯，你可以选一条高架桥断掉，再连接另外两个地方，每次Load只能用一次技能，而又必须使整个它仍构成树形结构。你的Save点在这里，Load自然会恢复原始的尼伯龙根咯。”

输入

第一行两个整数n,m，n意义如题，m表示路明非Load了m次。
接下来n-1行，每行两个整数x,y表示节点x,y之间存在一条边。
接下来m行，每行一个整数p,表示这次Load的重生地区。

输出

对于每一个询问，输出一行
如果可以则输出”YES”，否则输出”NO”（注意没有引号）

样例输入

5 3
1 2
1 3
1 4
1 5
1
2
3

样例输出

YES
NO
NO

分析：

刚看这题就知道要做树的重心，但我还没学啊……不会敲。
思路是：找到树的重心，询问x个点，去掉任意一条边，又连上任意两点，求出它能否成为树的重心
就可以找出重心的最大和次大子树，如果i在最大子树上，就将次大子树连上x，不然就将最大子树连上x，再判断这个点是否符合重心。

没有代码

有思路不会敲。

等我学成后一定补上这道题……

最后

以上就是喜悦白云为你收集整理的2020.2.7 C组模拟赛题解的全部内容，希望文章能够帮你解决2020.2.7 C组模拟赛题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。