Codeforces Round #446 (Div. 2)题解

联赛后好久没更博客了,搞些东西填一下.
这场CF挺简单的,AB就不放上来了.

C.Pride

题目地址: http://codeforces.com/contest/892/problem/C

题意

给出一个序列 $a$对于两个相邻的数,可以将其中一个改成他们的gcd,问需要操作多少次使所有的数为1.不能则输出-1.

题解

只要把一个数字改成1其他的就都可以了.

所以只要 $n^2$ 求将一个数改成1要几次,然后算一下输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y)
{
if (y==0) return x;
return gcd(y,x%y);
}
int n,m,x,s;
int a[3000];
int main()
{
scanf("%d",&n);
m=1234567;
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if (a[i]==1) s++;
}
for (int i=1;i<=n;i++)
{
int j=i+1;x=a[i];
for (;j<=n;j++)
{
if (x==1) break;
x=gcd(x,a[j]);
if (x==1) break;
}
if (x==1) m=min(m,j-i);
}
if (m==1234567)
{
printf("-1");
return 0;
}
printf("%d",n+m-1-s);
return 0;
}

D.Gluttony

题意

给出一个序列,对其进行重新排列,使2个排列的任意一个子集(除空集和全集)和不相同.
每个数互不相同.

题解

开始被n的范围吓到了,22.然而好像是因为spj是 $O(2^n)$ 的
最小的数放在次小的数的位置,然后继续这样搞,证明略.其实很好证的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
int n;
struct node
{
int p,d;
} a[1000];
int ans[1000];
bool cmp(node aa,node bb)
{
return aa.d<bb.d;
}
int main()
{
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>a[i].d;
a[i].p=i;
}
sort(a+1,a+n+1,cmp);
for (int i=1;i<n;i++) ans[a[i+1].p]=a[i].d;
ans[a[1].p]=a[n].d;
for (int i=1;i<=n;i++) cout<<ans[i]<<" ";
return 0;
}

E.Envy

题意

给出一张图,q组询问.
对于每组询问,包含一些边,若一颗最小生成树能包含里面所有的边,输出YES,否则输出NO.

题解

开始想了一些在线的做法,然而会TLE.看了题解才知道可以离线做.
方法差不多.
1.所有的边用桶排按照边权从小到大排.
2.对于每一组的询问,对于边 $i$,边权为 $x$,那么对于 边权 $<x$的边,都加入最小生成树了,如果这个边连的两端在同一个集合,该组询问为NO

注意:有一些边没有出现在询问中但是出现在最小生成树中了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
void write(int x)
{
if(x<0)
{
putchar('-');
write(-x);
}
else
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
const int maxn=5e5+1000;
int n,m,fa[maxn],Q,K;
int g[maxn];
int ans[maxn],id,SZ;
int T,id_T[maxn];
struct node
{
int x,y,z;
} a[maxn];
vector< pair <int,int> > q[maxn];
vector<int> G[maxn];
int gf(int x)
{
if (fa[x]==x) return x;
fa[x]=gf(fa[x]);
return fa[x];
}
void hb(int x,int y)
{
x=gf(x);y=gf(y);
fa[x]=y;
}
int gf_now(int x)
{
if (id_T[x]<T)
{
id_T[x]=T;
g[x]=gf(fa[x]);
}
if (g[x]==x) return x;
g[x]=gf_now(g[x]);
return g[x];
}
bool cmp(pair<int,int> a,pair<int,int> b)
{
return a.first<b.first;
}
int main()
{
n=read();m=read();
for (int i=1;i<=m;i++)
{
a[i].x=read();a[i].y=read();a[i].z=read();
G[a[i].z].push_back(i);
}
Q=read();
for (int i=1;i<=Q;i++)
{
K=read();
while (K--)
{
id=read();
q[a[id].z].push_back(make_pair(i,id));
}
}
for (int i=1;i<=n;i++) fa[i]=i;
for (int i=1;i<=maxn-1000;i++)
{
if (G[i].empty()) continue;//注意:是该边权下没有边不扫,不是不存在询问
sort(q[i].begin(),q[i].end(),cmp);//按照询问编号从小到大排序
SZ=q[i].size()-1;
for (int j=0;j<=SZ;j++)
{
if (j==0||q[i][j].first!=q[i][j-1].first) ++T;
if (ans[q[i][j].first]==1) continue;//没必要搜了
int d=q[i][j].second;
int x=gf_now(a[d].x),y=gf_now(a[d].y);
if (x==y) ans[q[i][j].first]=1;/*标记*/ else g[x]=y;//合并
}
SZ=G[i].size()-1;
for (int j=0;j<=SZ;j++) hb(a[G[i][j]].x,a[G[i][j]].y);//合并集合
}
for (int i=1;i<=Q;i++)
printf(ans[i]?"NO\n":"YES\n");
return 0;
}