打的第一场CF比赛。。虽说这次不算rank。。
前几个题都是水题来的。。不过因为十点半就要回寝只做出了A、B两个大水题。。
A. Gabriel and Caterpillar
模拟就行了。。
就是题意容易理解错= =
|
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 |
// <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; } |
B. z-sort
这道题比T1还傻逼（T1理解错了写一个小时也是WA的）
排个序把大的放偶数位小的放奇数位就完了
|
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 |
// <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; } |
C. Foe Pairs
并不难，然而比赛时没想出来
一对Foe Pair会让某个区间不能被穿越
那么枚举起点，终点单调后移即可
|
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 |
// <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; } |
D. Nested Segments
一开始也没想出来。。回寝室后恍然大悟
问cab说是主席树。。然而树状数组就可以做了（当然主席树也可以写（那天上午我还写了233））
一条线段i包含另一条线段j的条件是：\(l_i<=l_j, r_j<=r_i\)
当然这道题保证了没有右端点重复
那么可以将l和r视为两个关键字，题目即为第一关键字大于它而第二关键字小于它的有多少个
按第二关键字排序，按第二关键字顺序将第一关键字加入树状数组，即可查询。
当然第一关键字要先离散化
|
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 |
// <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; } |
E. Pursuit For Artifacts
首先Tarjan求一遍桥。。如果起点和终点都在桥的一侧那么把这条边丢掉，肯定不能走。
然后DFS/BFS过去看看有没有artifacts（神器？）就可以了
不写代码了
F. Ants on a Circle
不会做
刚才正好向总走进来教育我们要用非完美算法
那么这题模拟的话。。
可能会骗个10分哦？
说点什么