【Codeforces652】Educational Codeforces Round 10

打的第一场CF比赛。。虽说这次不算rank。。

前几个题都是水题来的。。不过因为十点半就要回寝只做出了A、B两个大水题。。

A. Gabriel and Caterpillar

模拟就行了。。

就是题意容易理解错= =

// <A.cpp> - 03/25/16 21:01:50
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
int main(){
	int h1=getint(),h2=getint(),a=getint(),b=getint();
	if(b>=a)
		if(h1+a*8<h2){printf("-1");return 0;}
		else {printf("0");return 0;}
	int d=-1;
	while(1){
		h1+=8*a;d++;
		if(h1>=h2){printf("%d",d);return 0;}
		h1-=12*b;
		h1+=4*a;
	}
	return 0;
}

// <A.cpp> - 03/25/16 21:01:50

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

int main(){

int h1=getint(),h2=getint(),a=getint(),b=getint();

if(b>=a)

if(h1+a*8<h2){printf("-1");return 0;}

else {printf("0");return 0;}

int d=-1;

while(1){

h1+=8*a;d++;

if(h1>=h2){printf("%d",d);return 0;}

h1-=12*b;

h1+=4*a;

}

return 0;

}

B. z-sort

这道题比T1还傻逼（T1理解错了写一个小时也是WA的）

排个序把大的放偶数位小的放奇数位就完了

// <B.cpp> - 03/25/16 21:01:50
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
int a[1010];
int b[1010];
int main(){
	int n=getint();
	for(int i=0;i<n;i++)a[i]=getint();
	sort(a,a+n);
	for(int i=0;i<(n+1)>>1;i++)b[i<<1]=a[i];
	for(int i=0;i<n-((n+1)>>1);i++)b[i<<1|1]=a[i+((n+1)>>1)];
	for(int i=0;i<n;i++)printf("%d ",b[i]);
	return 0;
}

// <B.cpp> - 03/25/16 21:01:50

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

int a[1010];

int b[1010];

int main(){

int n=getint();

for(int i=0;i<n;i++)a[i]=getint();

sort(a,a+n);

for(int i=0;i<(n+1)>>1;i++)b[i<<1]=a[i];

for(int i=0;i<n-((n+1)>>1);i++)b[i<<1|1]=a[i+((n+1)>>1)];

for(int i=0;i<n;i++)printf("%d ",b[i]);

return 0;

}

C. Foe Pairs

并不难，然而比赛时没想出来

一对Foe Pair会让某个区间不能被穿越

那么枚举起点，终点单调后移即可

// <C.cpp> - 03/25/16 21:01:50
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
const int MAXN=300010;
int a[MAXN],b[MAXN],r[MAXN],f[MAXN];
int main(){
	int n=getint(),m=getint();
	for(int i=1;i<=n;i++){
		a[i]=getint();
		b[a[i]]=i;
		r[i]=MAXN-1;
	}
	while(m--){
		int u=b[getint()],v=b[getint()];
		if(u>v)swap(u,v);
		r[u]=min(r[u],v);
	}
	lol ans=0;int j=1;
	for(int i=1;i<=n;i++){
		while(j<n&&!f[j+1])f[r[++j]]++;
		ans+=j-i+1;
		f[r[i]]--;
	}
	cout<<ans;
	return 0;
}

// <C.cpp> - 03/25/16 21:01:50

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=300010;

int a[MAXN],b[MAXN],r[MAXN],f[MAXN];

int main(){

int n=getint(),m=getint();

for(int i=1;i<=n;i++){

a[i]=getint();

b[a[i]]=i;

r[i]=MAXN-1;

}

while(m--){

int u=b[getint()],v=b[getint()];

if(u>v)swap(u,v);

r[u]=min(r[u],v);

}

lol ans=0;int j=1;

for(int i=1;i<=n;i++){

while(j<n&&!f[j+1])f[r[++j]]++;

ans+=j-i+1;

f[r[i]]--;

}

cout<<ans;

return 0;

}

D. Nested Segments

一开始也没想出来。。回寝室后恍然大悟

问cab说是主席树。。然而树状数组就可以做了（当然主席树也可以写（那天上午我还写了233））

一条线段i包含另一条线段j的条件是：\(l_i<=l_j, r_j<=r_i\)

当然这道题保证了没有右端点重复

那么可以将l和r视为两个关键字，题目即为第一关键字大于它而第二关键字小于它的有多少个

按第二关键字排序，按第二关键字顺序将第一关键字加入树状数组，即可查询。

当然第一关键字要先离散化

// <D.cpp> - 03/25/16 21:01:50
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
#define lowbit(x) ((x)&(-x))
const int MAXN=200005;
int n;
int l[MAXN],r[MAXN];
struct seg{
	int id;
	bool operator < (const seg b) const {return r[id]==r[b.id]?l[id]>l[b.id]:r[id]<r[b.id];}
}s[MAXN];
int u[MAXN];
int c[MAXN],ans[MAXN];
int query(int x){
	int ans=0;
	for(;x;x-=lowbit(x))ans+=c[x];
	return ans;
}
void add(int x,int y){
	for(;x<=n;x+=lowbit(x))c[x]+=y;
}
int main(){
	n=getint();
	for(int i=0;i<n;i++){
		u[i]=l[i]=getint();
		r[i]=getint();
		s[i].id=i;
	}
	sort(s,s+n);
	sort(u,u+n);
	for(int i=0;i<n;i++){
		int rank=lower_bound(u,u+n,l[s[i].id])-u+1;
		ans[s[i].id]=i-query(rank-1);
		add(rank,1);
	}
	for(int i=0;i<n;i++)printf("%d\n",ans[i]);
	return 0;
}

// <D.cpp> - 03/25/16 21:01:50

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

#define lowbit(x) ((x)&(-x))

const int MAXN=200005;

int n;

int l[MAXN],r[MAXN];

struct seg{

int id;

bool operator < (const seg b) const {return r[id]==r[b.id]?l[id]>l[b.id]:r[id]<r[b.id];}

}s[MAXN];

int u[MAXN];

int c[MAXN],ans[MAXN];

int query(int x){

int ans=0;

for(;x;x-=lowbit(x))ans+=c[x];

return ans;

}

void add(int x,int y){

for(;x<=n;x+=lowbit(x))c[x]+=y;

}

int main(){

n=getint();

for(int i=0;i<n;i++){

u[i]=l[i]=getint();

r[i]=getint();

s[i].id=i;

}

sort(s,s+n);

sort(u,u+n);

for(int i=0;i<n;i++){

int rank=lower_bound(u,u+n,l[s[i].id])-u+1;

ans[s[i].id]=i-query(rank-1);

add(rank,1);

}

for(int i=0;i<n;i++)printf("%d\n",ans[i]);

return 0;

}

E. Pursuit For Artifacts

首先Tarjan求一遍桥。。如果起点和终点都在桥的一侧那么把这条边丢掉，肯定不能走。

然后DFS/BFS过去看看有没有artifacts（神器？）就可以了

不写代码了

F. Ants on a Circle

不会做

刚才正好向总走进来教育我们要用非完美算法

那么这题模拟的话。。

可能会骗个10分哦？