Codeforces Round #469 (Div. 1) 题解

Author Avatar
Sakits 3月 09, 2018

题解

  这场CF的C题D题都特别思博,又有很多大爷翻车,最后居然有rk8080,给我送了一大波分…

A. Zebras

  只要合法随便构造,不合法一边构造一边判断也能判出来…

B. A Leapfrog in the Array

  比赛的时候发现一个数跳的次数并不会很多,尝试把数字往回跳,直到跳到奇数位置上就回到了原位。
  一个数跳到某个位置xx时,前面的奇数位置上都有数,偶数位置上都是空格,所以前面包括自己一共有x2\frac{x}{2}个数,后面一共有nn2n-\frac{n}{2}个连着的数,那么往回跳一次应该跳到x+(nn2)x+(n-\frac{n}{2})的地方。
  通过这个式子可以发现一个数最多跳log2xlog_2x次。因为那个式子实际上是x2+n\frac{x}{2}+n且满足nxn\geq xnn是偶数,所以决定那个式子什么时候变成奇数也就只需要看x2\frac{x}{2}了,这个显然最多log2xlog_2x次变成奇数。

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define int long long
#define ll long long
using namespace std;
const int maxn=500010, inf=1e9;
int n, q, x;
inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;	
} 
#undef int
int main()
{
	read(n); read(q);
	while(q--)
	{
		read(x);
		while((x&1)==0) x+=n-(x>>1);
		printf("%lld\n", (x+1)>>1);
	}
}

C. Data Center Maintenance

  题意理解题…
  如果一个客户连接的两个点(x,y)(x,y)满足txty=1t_x-t_y=1,那么xxyy连边,表示xx推迟了,yy也要推迟。那么强连通分量内的一个点推迟,强连通分量内的所有点都要推迟,所以找一个出度为00的最小强连通分量就好了…

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=500010, inf=1e9;
struct poi{int too, pre;}e[maxn<<1];
vector<int> v[maxn];
int n, m, h, tot, tott, top, color, x, y;
int a[maxn], dfn[maxn], low[maxn], st[maxn], col[maxn], flag[maxn], last[maxn], lack[maxn];
inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;	
} 
inline void add(int x, int y){e[++tot]=(poi){y, last[x]}; last[x]=tot;}
void tarjan(int x)
{
    dfn[x]=low[x]=++tott; st[++top]=x; lack[x]=top;
    for(int i=last[x], too;i;i=e[i].pre)
    if(!dfn[too=e[i].too]) tarjan(too), low[x]=min(low[x], low[too]);
    else if(!col[too]) low[x]=min(low[x], dfn[too]);
    if(dfn[x]==low[x]) 
    for(++color;top>=lack[x];top--) col[st[top]]=color, v[color].push_back(st[top]);
}
int main() 
{
    int n, m, h;
    read(n); read(m); read(h);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=m;i++)
    {
    	read(x); read(y);
    	if((a[x]+1)%h==a[y]) add(x, y);
    	if((a[y]+1)%h==a[x]) add(y, x);
	}
	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
	for(int i=1;i<=n;i++)
	for(int j=last[i], too;j;j=e[j].pre)
	if(col[i]!=col[too=e[j].too]) flag[col[i]]=1;
	int mn=n;
	for(int i=1;i<=color;i++) 
	if(!flag[i]) mn=min(mn, (int)v[i].size());
	for(int i=1;i<=color;i++) 
	if(!flag[i] && mn==v[i].size())
	{
		printf("%d\n", v[i].size());
		sort(v[i].begin(), v[i].end());
		for(int j=0;j<v[i].size();j++) printf("%d ", v[i][j]);
		puts(""); return 0;
	}
    return 0;
}

D. Curfew

  哇这个D普及题啊QAQ
  简单粗暴,模拟老师从两边开始往中间走,学生能补满bb个就赶紧补,补不上就赶紧溜,居然就A了,目瞪口呆.jpg

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ll long long
#define int long long
using namespace std;
const int maxn=500010, inf=1e9;
int n, b, d, cnt, ans1, ans2;
int sum[maxn];
inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;	
} 
inline int getsum(int l, int r)
{
	l=max(1ll, l); r=min(r, n);
	return sum[r]-sum[l-1];
}
#undef int
int main()
{
	read(n); read(d); read(b);
	for(int i=1;i<=n;i++) read(sum[i]), sum[i]+=sum[i-1];
	for(int i=1;i<=(n>>1);i++) 
	if(getsum(1, i+i*d)>=b+cnt*b) cnt++; else ans1++;
	cnt=0;
	for(int i=n;i>(n>>1);i--)
	if(getsum(i-d*(n-i+1), n)>=b+cnt*b) cnt++; else ans2++;
	printf("%lld\n", max(ans1, ans2));
}