>

cf1064E. Dwarves, Hats and Extrasensory Abilities(二分 交互

- 编辑:金沙国际平台登录 -

cf1064E. Dwarves, Hats and Extrasensory Abilities(二分 交互

题意

主题素材链接

次操作,每一趟你付出二个点的坐标,系统会回到该点的水彩,程序最后输出一条直线把全部黑点和白点分隔绝

17月3日,在格拉斯哥市莫愁湖景区,叁只小松鼠不停地承受一道道食物,花生、
玉茭、饼干,可谓热情,憨态可掬的形容吸引了过多围听众...
Description  
 小松鼠终于吃撑了,她决定逃离那几个地点。
 大家用一张连通图来表示一切南湖的限制,每棵容小松鼠逗留的树都用
这张图上的叁个点来表示。小松鼠能够透过只跳二次互相到达的两棵树用
图上的一条无向边来连接。
 吃撑了的小松鼠某个神志昏沉,每便他连跳两条边之后才会在到达的那
个点上苏醒。她想领会,是不是存在一种一而再的跳法,使得她有机遇在颇具
的树上都休息至少二次。
 对于这种跳法,你能够任选源点,允许再度经过边,允许再度经过点。
 可是超萌小松鼠是三头有期待的小松鼠,她有时能够突破自个儿的顶点,
使局部原先无法相互到达的七个点力所能致透过二回跳跃相互到达。
Input  
 第一行八个数n,m。n表示点的个数,m表示边的条数
 接下来m行,每行多少个数x i ,y i ,表示x i 和y i 之间能够通过一次跳跃相互到
达。
 接下来一行八个数q,表示驾驭的个数。
 接下来q行,在那之中的第i行每行多少个数a i ,b i 。表示在原图的根基上增添从a i 到b i 的
边。即成为一张n个点m + 1条边的图。
 保险交到的原图是个连通图,1 <= a i , b i , x i , y i <= n。
Output  
 输出一共q行,对于第i个询问,当在原图的底蕴上增加a i 与b i 间的无向边
后,假诺小松鼠能够找到一种连续的跳法,使得他有空子在全部的树上至
少小憩三回,输出一行“Yes”,不然输出一行“No” 。 (不满含引号)
Constraints  
 对于前50%,n, q <= 10 3 , m <= 2 × 10 3 。
 对于100%,n, q <= 10 5 , m <= 2 × 10 5 。

Sol

一个很直观的主张:首先询问,然后每一趟询问二分中式茶食,依照与第叁遍询问获得的字符串的涉嫌不断调节二分范围

唯独这么会被卡,笔者修改了五个地点才过。

  1. 二分调节边界的时候向来设或,因为大家最后获得的不是二个准确解,所以这么写是能够的

  2. 末尾输出直线的时候加三个偏移量,也正是出口一条斜线

现实看代码

/**/#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<map>#include<vector>#include<set>#include<queue>#include<cmath>//#include<ext/pb_ds/assoc_container.hpp>//#include<ext/pb_ds/hash_policy.hpp>#define Pair pair<int, int>#define MP make_pair#define fi first#define se second#define LL long long #define ull unsigned long long #define rg register #define pt printf("%d ", x);#define Fin {freopen(#x".in","r",stdin);}#define Fout {freopen(#x".out","w",stdout);}//#define getchar() (p1 == p2 && (p2 =  + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)//char buf[(1 << 22)], *p1 = buf, *p2 = buf;//char obuf[1<<24], *O = obuf;//void print {if print; *O++ = x % 10 + '0';}//#define OS  *O++ = ' ';//#define fout fwrite(obuf, O-obuf, 1 , stdout);using namespace std;//using namespace __gnu_pbds;const int MAXN = 2005, INF = 1e9 + 10, mod = 1e9 + 7;const int D[] = { -1, 1};const double eps = 1e-9;inline int read() {    char c = getchar(); int x = 0, f = 1;    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();    return x * f;}int N, Dx = 23333;string s, pre;main() {    N = read();    int l = 0, r = 1e9;    printf("%d 0n", Dx);    fflush;    cin >> pre;    int ans = 0;    for(int i = 2; i <= N; i++) {        int mid = l + r >> 1;        printf("%d %dn", Dx, mid);        fflush;        cin >> s;        if r = mid;        else l = mid, ans = mid;    }        printf("%d %d %d %d", Dx - 3, ans, Dx + 3, ans + 1);    return 0;}/*5blackblackwhitewhiteblack*/

样例输入:

2 1
1 2
2
1 1  
1 2

样例输出:

Yes
No

黑白染色,从一最初黑白染色,鲜明颜色同样就能够从贰个到另四个安息

那么大家发掘四个相邻节点颜色同样,就印证黑白互通了,那么评释能够输出Yes

满意上述条件则flag=1

就算flag=0且a的水彩不等于b则输出No

这里给出原题题解参照他事他说加以考察:

%%%%%YZD  OTZ

设想假设给出的图是二分图,那么大家任定源点,无论跳跃多少次始终只好达到与源点在同一边的点,对于>1个点的连通图来说,鲜明是有一点点不可能“停息”到的。

 

思考要是给出的图不是二分图,那么图内自然存在奇环。纵然除该奇环外的有个别属于二分图,只要在里头的某单方面包车型地铁全体一点上恢复过后,在奇环上绕一圈再出去就可见达到另一面包车型客车点。因此能够达到指标。

 

我们把应对转化成二分图的判断之后,再来思量询问怎么管理。

 

首先最强力的做法是历次读入一条边之后和原图一同再做贰遍二分图推断。

 

出于每一遍都是在原图的基本功上加一条边的,所以每一次对于原图部分的论断显得更加的浪费。大家能够后保留原图新闻的主旋律思索那么些标题。

 

大家对原图进行二分图染色,假如它不是二分图,那么投入其它边都不也许使它再也变回二分图,由此只要输出q个“Yes”就能够。

 

接下去大家所研商的都是原图是二分图的景观。

 

大家着想读进去的一条边(x, y),尽管x和y在原图上属于同一种颜色,那么丰盛那条边约等于在二分图的同侧点间加了一条边,破坏了二分图的质量,由此输出“Yes”

 

不然假若属于区别的颜色,也正是在二分图的两边间连了一条边,它依旧个二分图,由此输出“No”

 

那般的章程刚起首能够用Bfs预管理,每便回答询问是O(1)的

 

就此时间复杂度为O(m + q)

 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 struct Node
 7 {
 8   int next,to;
 9 }edge[400001];
10 int num,head[100001],n,m,q,vis[100001];
11 bool flag;
12 void add(int u,int v)
13 {
14   num++;
15   edge[num].next=head[u];
16   head[u]=num;
17   edge[num].to=v;
18 }
19 void dfs(int x)
20 {int i;
21   for (i=head[x];i;i=edge[i].next)
22     {
23       int v=edge[i].to;
24       if (vis[v]==0)
25     {
26       if (vis[x]==1)
27         vis[v]=2;
28       else vis[v]=1;
29       dfs(v);
30     }
31       else
32     {
33       if (vis[x]==vis[v])
34         {
35           flag=1;
36         }
37     }
38     }
39 }
40 int main()
41 {int i,x,y;
42   cin>>n>>m;
43   for (i=1;i<=m;i++)
44     {
45       scanf("%d%d",&x,&y);
46       add(x,y);add(y,x);
47     }
48   vis[x]=1;
49   dfs(1);
50   cin>>q;
51   while (q--)
52     {
53       scanf("%d%d",&x,&y);
54       if (vis[x]==vis[y])
55     {
56       printf("Yesn");
57     }
58       else if (flag) printf("Yesn");
59       else printf("Non");
60     }
61 }

本文由编程发布,转载请注明来源:cf1064E. Dwarves, Hats and Extrasensory Abilities(二分 交互