Codeforces Round #766 (Div. 2)C，D
今天A竟然看错了，还好后来发现了，A题就写了40几分钟，真有你的
过了B，排名是8千多，比前几天好一点，加油ヾ(◍°∇°◍)ﾉﾞ
C
相比于D ,我更没有看懂这一题讲的质数数是个什么东西
后来看了大佬们的讲解，理解了一点
所谓的质数树，这棵树里的每一条边和他相邻的边的和是一个质数
我们可以让相邻的两条边一条为2，一条为3,2,3,2,3这一条链上的边一个2一个3，这样每两个边的和都是5
还有一种情况
是一个节点有3个子节点，或者父节点，这样有三条边是相邻的，假如边1和边2的和是5，边2和边3是5，那边2和边1的和一定是一个4（就算是换成其他的数也不行，众所周知，质数除了2就是奇数，那么这三条边一定有两条边是奇数，其和一定是偶数）,所以当一个点的入度大于等于3时，一定是找不到质数树的
如果可以找到就用dfs建边一个一个从入度为1（看做起点）的点开始找（每一点都会在里面，因为有n-1条边，不会出现自环，题目提及）
题目注意不要超时，memset时间复杂度过大，尽量少用
#include <iostream>
#include <cstring>
using namespace std;
#define int long long
const int maxn=2e5+10;
struct edge
{
int next,to,id;
}e[maxn];
int head[maxn],cnt;
int val[maxn];
int n,t;
void add(int u,int v,int id)
{
e[++cnt].next=head[u];
e[cnt].to=v;
e[cnt].id=id;
head[u]=cnt;
return ;
}
void dfs(int u,int fa,int flag)
{
for (int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if (v==fa) continue;
val[e[i].id]=flag;
dfs(v,u,flag^1);
}
return ;
}
void solve()
{
cin>>n;
int cnt=0;
bool yes=true;
memset(head,0,sizeof(head));
int in[maxn]={0};
for (int i=1;i<n;i++)
{
val[i]=0;
int u,v;
cin>>u>>v;
add(u,v,i);
add(v,u,i);
in[v]++;
in[u]++;
// cout<<"&& "<<in[u]<<" "<<in[v]<<" &&\n";
if (in[u]>=3||in[v]>=3) yes=false;
}
if (!yes)
{
cout<<-1<<'\n';
return ;
}
for (int i=1;i<=n;i++)
{
if (in[i]==1)
{
dfs(i,-1,1);
break;
}
}
for (int i=1;i<n;i++)
{
if (val[i]) cout<<2<<" ";
else cout<<3<<" ";
}
cout<<'\n';
return ;
}
signed main ()
{
ios::sync_with_stdio(false);
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}
D
这一题好像我之前的一道题很相似
是给你一个数组，你可以进行一个操作，找到ai和aj,假如gcd(ai,aj)不在数组，就可以把这个数放到数组里，然后再寻找，问你你可以进行最大次数的操作
不过那一到题是相减，这里是gcd，这里有一个巧妙的做法，我之前是直接找i的倍数，如果存在两个以上i的倍数，就代表存在两个数的gcd是i,但是这也不一定，有可能是i的倍数，比如i时3，出现了6和12,那么就不对了，而下面的处理就很好的解决了这个问题
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e6+10;
bool vis[maxn];
int a[maxn];
int ans;
int main ()
{
int n;
cin>>n;
ans=0;
int mx=0;
for (int i=1;i<=n;i++)
{
cin>>a[i];
mx=max(mx,a[i]);
vis[a[i]]=true;
}
for (int i=1;i<mx;i++)
{
if (vis[i]) continue;
int g=-1;//这里很巧妙哦，
for (int j=i+i;j<=mx;j+=i)
{
if (vis[j])
{
if (g==-1) g=j/i;
else g=__gcd(g,j/i);
}
}
if (g==1) ans++;//前面的一顿操作下来，如果此时g=1就代表着着n个数里存在两个数的gcd=i
}
cout<<ans<<'\n';
system ("pause");
return 0;
}