Contest1585 - 2018-2019赛季多校联合新生训练赛第一场
C 10187 查找特定的合数
D 10188 传话游戏
H 10192 扫雷游戏
题干：
题目描述
自然数中除了能被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) );
题干：
题目描述
有这样一个朋友网络，如果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();
}
题干：
题目描述
小Q空的时候挺喜欢玩玩电脑游戏的。自从编程技术提高后，他就想，要是自己也能开发出一款游戏来，那该多好啊！不过，小Q也不着急，先练好基本功再说。Windows中就有一款叫扫雷的小游戏，挺好玩的，不过想编出一个来，还真不容易。小Q就自己设想了一种简单的扫雷游戏：在n行２列的方格棋盘上，左列某些方格内埋有地雷，而右列每个方格中都有一个数字（０～３），第I格的数字表示：左列第I－１、I、I＋１格（即：上、中、下三格）中埋雷的总数。
你的任务是：根据右列的数字分析出左列格子中的地雷（０表示无雷，１表示有雷），并且统计出左列格子中地雷的总数。
小Q想，如果这样的任务能完成了，相信编出更复杂的扫雷游戏也就为期不远了。 输入
第一行，一个整数N（２≤N≤４０），第二行有N个数字（以一个空格相隔），表示右列格子中的数字。输入数据保证正确有解。 输出
第一行是N个０、１数字（没有空格相隔），表示左列每格中有无地雷。第二行一个整数，表示地雷总数。 样例输入 样例输出
题解：
考察知识点：位运算？？
每个位置 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();
}