Contest1585 - 2018-2019赛季多校联合新生训练赛第一场(部分题解)

时间:2022-04-13 20:14:30

Contest1585 - 2018-2019赛季多校联合新生训练赛第一场

C 10187 查找特定的合数

D 10188 传话游戏

H 10192 扫雷游戏

C 传送门

题干:

题目描述
自然数中除了能被1和本身整除外,还能被其他数整除的数叫合数。每个合数都可以写成几个质数相乘的形式,这几个质数都叫做这个合数的质因数。比如8=××,2就是8的质因数。在1—N(N≤)按从小到大顺序排列的自然数序列中,查找第M个有X(≤X≤)个不同质因数的合数。例如,第3个有2个不同质因数的合数是12(12只有2、3两个不同的质因数,在12之前有2个不同质因数的合数分别为6和10)。 输入
共1行,分别为M,X。 输出
共1行,为第M个有X个不同质因数的合数。 样例输入 样例输出

题解:

  步骤:

    (1):用线性筛素数(欧拉筛法)在O(n)的时间内预处理出[1,2e5]间所有的质数。

    (2):从1到2e5开始枚举,对于数 i 找到其含有的质因子的个数,用tot[ ]数组存储。

AC代码:

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn=2e5+; int M,X;
int tot[maxn];//tot[i] : i 含有的质因子个数
//===============线性筛素数(欧拉筛法)=====================
int vis[maxn];
int prime[maxn];
int cnt=;//cnt用来计数,prime数组保存素数
void isprime(int n)
{
for(int i=;i<=n;i++)
{
if(!vis[i])
prime[cnt++]=i;//如果未被标记过,则表示为素数
for(int j=;j<cnt && i*prime[j]<=n;j++)//当标记的合数超出范围则退出
{
vis[i*prime[j]]=;
if(i%prime[j] == )
break;//关键步骤
}
}
}
//===========================================================
bool Check(int x)//二分检查 x 是否为素数
{
int l=-,r=cnt+;
while(r-l > )
{
int mid=l+((r-l)>>);
if(prime[mid] == x)
return true;
if(prime[mid] > x)
r=mid;
else
l=mid;
}
return false;
}
void Updata(int num)
{
int x=sqrt(num);
for(int i=;i <= x;++i)
{
if(num%i != || i == num)
continue;
int j=num/i;
tot[num]=tot[num]+(Check(i) ? :)+(i != j && Check(j) ? :);
}
}
int Solve()
{
mem(vis,);
mem(tot,);
isprime(2e5);
for(int i=;i <= ;++i)
Updata(i);//更新tot[i]
for(int i=;i <= ;++i)
{
if(tot[i] == X)//查找第 M 个只有 X 个质因子的数
M--;
if(M == )
return i;
}
}
int main()
{
scanf("%d%d",&M,&X);
printf("%d\n",Solve());
}

  时间复杂度分析:

    (1):预处理线性筛 : O(n),n = 2e5

    (2):枚举 : O( n*√n * log(cnt) ),(n = 2e5,cnt = 17984);

  所以总的时间复杂度为 O( n*√n * log(cnt) );

D 传送门

题干:

题目描述
有这样一个朋友网络,如果a认识b,那么a收到某个消息,就会把这个消息传给b,以及所有a认识的人。但是,请你注意,如果a认识b,b不一定认识a。现在我们把所有人从1到n编号,给出所有“认识”关系,问如果i发布一条新消息,那么会不会经过若干次传话后,这个消息传回给了i(≤i≤n)。 输入
第1行是两个数n(n<)和m(m<),两数之间有一个空格,表示人数和认识关系数。接下来的m行,每行两个数a和b,表示a认识b(≤a,b≤n)。认识关系可能会重复给出,但1行的两个数不会相同。 输出
一共有n行,每行一个字符T或F。第i行如果是T,表示i发出一条新消息会传回给i;如果是F,表示i发出一条新消息不会传回给i。 样例输入 样例输出
T
T
T
F

题解:

  考察知识点:强连通分量分解

  以人作为顶点,人与人之间的认识关系作为边建立一个有向图。

  通过SCC判断某人a是否与其他人构成强连通分量,如果构成,那么此人可以通过他人得到自己传出去的消息,反之,将得不到。

AC代码:

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb(x) push_back(x)
const int maxn=1e3+; int n,m;
bool vis[maxn];//访问标记
int color[maxn];//所属强连通分量的编号
int tot[maxn];//记录强连通分量的编号出现的次数
vector<int >G[maxn],rG[maxn];//图,反向图
vector<int >vs;
void addEdge(int u,int v)
{
G[u].pb(v);
rG[v].pb(u);
}
void Dfs(int u)
{
vis[u]=true;
for(int i=;i < G[u].size();++i)
{
int to=G[u][i];
if(!vis[to])
Dfs(to);
}
vs.pb(u);
}
void rDfs(int u,int k)
{
vis[u]=true;
color[u]=k;
tot[k]++;
for(int i=;i < rG[u].size();++i)
{
int to=rG[u][i];
if(!vis[to])
rDfs(to,k);
}
}
void Solve()
{
mem(vis,false);
for(int i=;i <= n;++i)
if(!vis[i])
Dfs(i);
mem(vis,false);
mem(tot,);
int k=;//强连通分量编号
for(int i=vs.size()-;i >= ;--i)
{
int u=vs[i];
if(!vis[u])
rDfs(u,++k);
}
for(int i=;i <= n;++i)
printf("%c\n",tot[color[i]] > ? 'T':'F');//如果当前节点所属的强连通分量编号大于1,输出'T'
printf("\n");
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i <= m;++i)
{
int u,v;
scanf("%d%d",&u,&v);
if(find(G[u].begin(),G[u].end(),v) == G[u].end())
addEdge(u,v);
}
Solve();
}

H 传送门

题干:

题目描述
小Q空的时候挺喜欢玩玩电脑游戏的。自从编程技术提高后,他就想,要是自己也能开发出一款游戏来,那该多好啊!不过,小Q也不着急,先练好基本功再说。Windows中就有一款叫扫雷的小游戏,挺好玩的,不过想编出一个来,还真不容易。小Q就自己设想了一种简单的扫雷游戏:在n行2列的方格棋盘上,左列某些方格内埋有地雷,而右列每个方格中都有一个数字(0~3),第I格的数字表示:左列第I-1、I、I+1格(即:上、中、下三格)中埋雷的总数。
你的任务是:根据右列的数字分析出左列格子中的地雷(0表示无雷,1表示有雷),并且统计出左列格子中地雷的总数。
小Q想,如果这样的任务能完成了,相信编出更复杂的扫雷游戏也就为期不远了。 输入
第一行,一个整数N(2≤N≤40),第二行有N个数字(以一个空格相隔),表示右列格子中的数字。输入数据保证正确有解。 输出
第一行是N个0、1数字(没有空格相隔),表示左列每格中有无地雷。第二行一个整数,表示地雷总数。 样例输入 样例输出

题解:

  考察知识点:位运算??

  每个位置 i 的地雷数受 i-1,i,i+1 三个位置影响。

  1位置只受 1,2 位置影响,而 1,2 位置可能的状态有 00,01,10,11 四种(二进制数表示,0表示不含地雷,1表示含有地雷),而答案就是其中之一。

  根据 1 位置含有的地雷数枚举满足条件的 1,2 位置的状态,而 1,2 位置的状态一旦确定,通过 2 位置含有的地雷数确定 3 位置是否含有地雷,依次类推,通过 i 位置的

  地雷数确定 i+1 位置是否含有地雷,如果中间出现矛盾,枚举下一个满足条件的 1,2 位置的状态。

AC代码:

 #include<iostream>
#include<cstdio>
using namespace std;
const int maxn=; int n;
int a[maxn];
int status[maxn]; //preStatus : (pos-2,pos-1,pos) 位置的状态对应的十进制数
bool Find(int preStatus,int pos)
{
//preStatus中的(pos-1,pos)才对当前位置的状态有影响
int curStatus=(preStatus&);//二进制数运算,通过 &11 取出preStatus的(pos-1,pos)位置的状态
int tot=(curStatus&)+(curStatus>>&);//(pos-1,pos)位置含有的地雷数
if(pos == n)//递归终止条件,判断是否满足最后一个位置的地雷数
return tot == a[n] ? true:false;
if(tot == a[pos])//如果(pos-1,pos)含有的地雷数 == a[pos],那么 pos+1 位置就不能含有地雷
{
status[pos]=(preStatus<<);
return Find(status[pos],pos+);
}
else if(tot == a[pos]-)//如果(pos-1,pos)含有的地雷数 == a[pos]-1,那么 pos+1 位置必须含有地雷
{
status[pos]=(preStatus<<|);
return Find(status[pos],pos+);
}
return false;
}
void Solve()
{
//1,2 位置可能的状态为四个二进制数 00,01,10,11,转换为十进制数为 0,1,2,3
for(int i=;i <= ;++i)//枚举 1,2 位置的状态
{
int tot=(i&)+(i>>&);//1,2 状态含有的地雷数
if(tot == a[])
{
status[]=i;
if(Find(i,))
break;
}
}
int res=;
for(int i=;i < n;++i)
{
if(i == )
{
res += (status[]&)+(status[]>>&);
printf("%d%d",status[]>>&,status[]&);
continue;
}
res += (status[i]&);
printf("%d",status[i]&);
}
printf("\n%d\n",res);
}
int main()
{
scanf("%d",&n);
for(int i=;i <= n;++i)
scanf("%d",a+i);
Solve();
}