CF1137

Posted on | Edited on | Views:

$Div.1​$

CF1137A Skyscrapers

  • 二分.

  • 通过观察可以发现,对于每个询问,如果交点位置的值是 $x$ ,那么答案就是该列比 $x$ 小的数字种数与该行比 $x$ 小的数字种数的较大值+该列比 $x$ 小的数字种数与该行比 $x$ 小的数字种数的较大值 + $1$ .

  • 离散化后二分一下就可以求出了.

CF1137B Camp Schedule

  • 贪心 + $kmp$ .
  • 这个东西显然可以贪心,构造字符串时先放一个目标串,然后后面从最长 $border$ 那里接上去继续放,直到放完或者 $0/1$ 不够用.
  • 用 $kmp$ 搞一下最长 $border$ 长度就好了.

CF1137C Museums Tour

  • $tarjan$ 缩点, $DAG$ 上 $dp$ .
  • 注意到 $d$ 较小,所以首先可以把原来的每个点拆成 $d$ 个点,并连上合法的转移边.这样每个点有两个值 $(x,t)$ ,如果城市 $x$ 在当天有展览,这个点权值为 $1$ ,否则为 $0$ .
  • 用 $tarjan$ 搞出每个强连通分量,缩成一个点,那么这个新点的权值就是这个 $SCC$ 内有展览的城市数目和.
  • 注意到同一个城市拆出来的点 $(x,t)$ 与 $(x,t’)$ 路径可逆(连续走 $d-1$ 次),要么彼此都不可达,对应的两个 $SCC$ 不连通;要么彼此都可达.在同一个 $SCC$ 内.
  • 所以在 $DAG$ 上 $dp$ 的话,两个 $SCC$ 内相同城市拆出来的点贡献不会叠加.
  • 那么就可以直接从 $(1,0)$ 所在的强连通分量出发,在 $DAG$ 上找一条点权和最大的路径,可以 $dp$ 解决.
  • 时间复杂度 $O(nd)$ .
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;
#define ll long long
inline int read()
{
    int out=0,fh=1;
    char jp=getchar();
    while ((jp>'9'||jp<'0')&&jp!='-')
        jp=getchar();
    if (jp=='-')
        fh=-1,jp=getchar();
    while (jp>='0'&&jp<='9')
        out=out*10+jp-'0',jp=getchar();
    return out*fh;
}
const int N=1e5+10;
const int MAXN=5e6+10;
int n,m,d;
vector<int> graph[MAXN];
int eu[N],ev[N];
int on_display[MAXN];
char schedule[51];
bool vis[N];
int low[MAXN],dfn[MAXN],idx=0;
int stk[MAXN],tp=0;
int scc[MAXN],scc_cnt=0,sccval[MAXN];
void tarjan(int u)
{
	stk[++tp]=u;
	dfn[u]=low[u]=++idx;
	for(auto v:graph[u])
	{
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(!scc[v])
			low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		++scc_cnt;
		while(tp)
		{
			int v=stk[tp--];
			scc[v]=scc_cnt;
			if(on_display[v])
			{
				sccval[scc_cnt]+=(int)(!vis[(v/d)+1]);
				vis[(v/d)+1]=true;
			}
			if(v==u)
				break;
		}
	}
}
int f[MAXN];
int dfs(int u)
{
	if(f[u]!=-1)
		return f[u];
	f[u]=0;
	for(auto v:graph[u])
		f[u]=max(f[u],dfs(v));
	f[u]+=sccval[u];
	return f[u];
}
int main()
{
	n=read(),m=read(),d=read();
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read();
		eu[i]=u,ev[i]=v;
		for(int ut=0;ut<d;++ut)
		{
			int vt=(ut+1)%d;
			graph[(u-1)*d+ut].push_back((v-1)*d+vt);
		}
	}
	for(int i=1;i<=n;++i)
	{
		scanf("%s",schedule);
		for(int j=0;j<d;++j)
			on_display[(i-1)*d+j]=schedule[j]-'0';
	}
	tarjan((1-1)*d+0);
	for(int i=0;i<n*d;++i)
		graph[i].clear();
	for(int i=1;i<=m;++i)
	{
		int u=eu[i],v=ev[i];
		for(int ut=0;ut<d;++ut)
		{
			int vt=(ut+1)%d;
			if(scc[(u-1)*d+ut] && scc[(u-1)*d+ut]!=scc[(v-1)*d+vt])
				graph[scc[(u-1)*d+ut]].push_back(scc[(v-1)*d+vt]);
		}
	}
	memset(f,-1,sizeof f);
	int ans=dfs(scc[(1-1)*d+0]);
	cout<<ans<<endl;
    return 0;
}

然而需要卡空间.懒得卡了.

CF1137D Cooperative Game

  • 交互题.
  • 这个模型可以考虑 $floyd$ 判圈算法.即 $A$ 的速度是 $2$ , $B$ 的速度是 $1$ ,同时从起点出发,当两人重新相遇时,快的那个人比慢的那个人多走了 $k$ 圈,即 $k\cdot c$ 步.操作时可以让 $A,B$ 一起走一步,再让 $A$ 走一步.
  • 相遇时, $B$ 肯定还没有走完一圈.记此时 $B$ 在圈内走了 $x$ 步( $x<c$ ),那么 $B$ 一共走了 $t+x$ 步, $A$ 一共走了 $t+x+kc$ 步.而 $A$ 走的步数恰好是 $B$ 的二倍.
  • 所以可以得到 $kc=t+x$ .那么此时这两个人再一起往前走 $t$ 步就可以一起到达环的起点.
  • 而剩余的人还在出发点,也是再往前走 $t$ 步到达环的起点.于是相遇后所有人一起走,到达同一个位置时就结束了.
  • 分析一下总步数. $A,B$ 相遇前要进行 $2(t+x)$ 个操作,相遇后要进行 $t$ 个操作.总操作数不会大于 $3(t+c)$ .
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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read()
{
    int out=0,fh=1;
    char jp=getchar();
    while ((jp>'9'||jp<'0')&&jp!='-')
        jp=getchar();
    if (jp=='-')
        fh=-1,jp=getchar();
    while (jp>='0'&&jp<='9')
        out=out*10+jp-'0',jp=getchar();
    return out*fh;
}
int groups;
char buf[10][10];
void getinfo()
{
	groups=read();
	for(int i=0;i<groups;++i)
		scanf("%s",buf[i]);
}
void moveA()
{
	puts("next 0");
	fflush(stdout);
}
void moveAB()
{
	puts("next 0 1");
	fflush(stdout);
}
void moveAll()
{
	puts("next 0 1 2 3 4 5 6 7 8 9");
	fflush(stdout);
}
void Done()
{
	puts("done");
	fflush(stdout);
}
void stage_catch()
{
	while(1)
	{
		moveAB();
		getinfo();
		moveA();
		getinfo();
		for(int i=0;i<groups;++i)
		{
			bool fa=false,fb=false;
			int len=strlen(buf[i]);
			for(int j=0;j<len;++j)
			{
				if(buf[i][j]=='0')
					fa=true;
				if(buf[i][j]=='1')
					fb=true;
				if(fa && fb)
					return;
			}
		}
	}
}
void stage_meet()
{
	while(1)
	{
		moveAll();
		getinfo();
		if(groups==1)
		{
			Done();
			return;
		}
	}
}
int main()
{
	stage_catch();
	stage_meet();
    return 0;
}

CF1137F Matches Are Not a Child’s Play

  • 树剖 + 线段树.
  • $compare$ 询问显然不用单独考虑,做两次 $when$ 询问就可以了.
  • 初始的删点序列我们可以暴力搞出,只需要考虑每次 $up$ 操作带来的影响.
  • 首先可以发现在一条路径上,只能从两边往中间删.,若 $up$ 当前权值最大的节点,就没有影响.否则,如果把 $u$ 改成了最大, $v$ 是原来最大的点, $v\not = u$ ,那么 $v-u$ 这条路径一定是最后被删除的,且删除顺序是严格按照 $v\rightarrow u$ 这条单向路径.
  • 不在这条路径上的点被删除的相对顺序显然不会变.即, $up$ 操作一次之后,先删除不在这条路径上的点,顺序是操作前被删除的相对顺序,再沿路径 $v\rightarrow u$ 顺次删除.
  • 实现可以通过染色,第 $i$ 次 $up$ 操作时把 $v_i\rightarrow u_i$ 这条路径上的点颜色染为 $i$ .那么询问 $when(x)$ 的答案就是颜色序号比 $col_x$ 小的节点数加上路径 $v_{colx} \rightarrow x$ 的节点数目.初始化可以看做进行了 $n$ 次 $up$ 操作.
  • 染色用树剖+线段树实现,答案的两部分,前者用线段树维护每种颜色的节点数目,后者只需要记录每次的 $v_i$ ,利用树剖维护的 $dep,top$ 计算.
  • 时间复杂度 $O(qlog^2n)$ .