Codeforces Round #703[CF1486]

发表于 分类于

problems’s link

退役选手一个无聊的晚上。

退役半年，手速和思维都降下来了呀。

A

从前往后贪心，第 $i$ 个位置看是否能把它搞成 $i-1$。

然而因为自己智障还WA了两发。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int n,x,flag;
ll s;
int main()
{
	CASET
	{
		n=read(); s=0; flag=1;
		ff(i,0,n)
		{
			x=read();
			if(x+s<i) flag=0;
			s=x+s-i;
		}
		puts(flag?"YES":"NO");
	}
	return 0;
}

B

显然 $x,y$ 坐标分开，然后中位数。

3min看完题+写完。（英文水平有所上升）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N=1010;
int n,a[N],b[N];
int main()
{
	CASET
	{
		n=read();
		fo(i,1,n) a[i]=read(),b[i]=read();
		sort(a+1,a+n+1);
		sort(b+1,b+n+1);
		int m=n>>1;
		if(n&1) printf("1\n");
		else printf("%lld\n",1ll*(b[m+1]-b[m]+1)*(a[m+1]-a[m]+1));
	}
	return 0;
}

C

交互题。

一开始还以为是个什么难题。

结果发现自己是在打div.2，在打div.2的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
int n;
int ask(int l,int r)
{
	if(l>=r||r>n) return -1;
	printf("? %d %d\n",l,r);
	fflush(stdout);
	int x; scanf("%d",&x);
	return x;
}

int solve(int l,int r)
{
	if(l==r) return l;
	if(l+1==r) return l^r^ask(l,r);
	int mid=ask(l,r);
	if(ask(mid,r)==mid)
	{
		int L=mid+1,R=r,m;
		for(;L+1<R;)
		{
			m=(L+R)>>1;
			if(ask(mid,m)==mid) R=m;
			else L=m+1;
		}
		if(L==R) return L;
		else return solve(L,R);
	}
	else
	{
		int L=l,R=mid-1,m;
		for(;L+1<R;)
		{
			m=(L+R)>>1;
			if(ask(m,mid)==mid) L=m;
			else R=m-1;
		}
		if(L==R) return L;
		else return solve(L,R);
	}
}
int main()
{
	n=read();
	int ans=solve(1,n);
	printf("! %d\n",ans);
	return 0;
}

D

一眼题。

直接二分答案，然后奇偶分开讨论，顺着扫一遍，用个数据结构维护就好了。这里用set。

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
const int N=200010;
set<int> s[2];
int b[N],a[N];
int n,m;
bool check(int x)
{
	fo(i,1,n) b[i]=b[i-1]+(a[i]>=x);
	s[0].clear(); s[1].clear();
	int j;
	fo(i,1,n-m+1)
	{
		s[i&1].insert(i-2*b[i-1]);
		j=i+m-1;
		if(s[j&1].lower_bound(-2*b[j]+j+2)!=s[j&1].end()) {return 1;}
		if(s[!(j&1)].lower_bound(-2*b[j]+j+3)!=s[!(j&1)].end()) {return 1;}
	}
	return 0;
}

int main()
{
	n=read(); m=read();
	fo(i,1,n) a[i]=read();
	int l=0,r=n+1,mid;
	for(;l+1<r;)
	{
		mid=(l+r)>>1;
		if(check(mid)) l=mid;
		else r=mid;
	}
	printf("%d\n",l);
	return 0;
}

E

$1\leq w_i\leq 50$，这性质很有用。

于是记 $f_{i,j}$ 表示走到 $i$，上一条边的费用是 $j$ 的最短路。特别地，$f_{i,0}$ 表示走完两条路。

于是dijkstra即可。

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
const int N=100010;
const int M=400010;
const int K=52;
const ll inf=1e18;
int n,m;
int ver[M],val[M],head[N],ne[M],tot;
inline void add(int x,int y,int z)
{
	ver[++tot]=y; val[tot]=z; ne[tot]=head[x]; head[x]=tot;
	ver[++tot]=x; val[tot]=z; ne[tot]=head[y]; head[y]=tot;
}
ll f[N][K];
bool vis[N][K];
struct node{
	int x,y; ll d;
	friend inline bool operator<(const node &A,const node &B)
	{
		return A.d>B.d;
	}
};
priority_queue<node> q;
int main()
{
	n=read(); m=read();
	int x,y,z;
	fo(i,1,m) x=read(),y=read(),z=read(),add(x,y,z);
	fo(i,1,n) fo(j,0,50) f[i][j]=inf;
	f[1][0]=0; q.push((node){1,0,0});
	for(;!q.empty();)
	{
		node u=q.top(); q.pop();
		if(vis[u.x][u.y]) continue;
		vis[u.x][u.y]=1;
		if(!u.y)
		{
			for(int i=head[u.x],v;i;i=ne[i])
			{
				v=ver[i];
				if(f[v][val[i]]>f[u.x][0])
				{
					f[v][val[i]]=f[u.x][0];
					q.push((node){v,val[i],f[u.x][0]});
				}
			}
		}
		else
		{
			for(int i=head[u.x],v;i;i=ne[i])
			{
				v=ver[i];
				if(f[v][0]>f[u.x][u.y]+(u.y+val[i])*(u.y+val[i]))
				{
					f[v][0]=f[u.x][u.y]+(u.y+val[i])*(u.y+val[i]);
					q.push((node){v,0,f[v][0]});
				}
			}
		}
	}

	ll ans;
	fo(i,1,n)
	{
		if(f[i][0]==inf) f[i][0]=-1;
		printf("%lld ",f[i][0]);
	}
	return 0;
}

F

将 $1$ 作为根。

不难发现，如果两条路径有且仅有一个相交的点，那么肯定是两条路径的lca中的一个。

分两种情况。

1，两条路径lca相同。用总数减去不合法的情况即可。

2，两条路径lca不同。树上差分一下统计一些东西就可以了。

可以做到线性。

懒得写代码了，睡觉去了。