在湖蓝跟衡水大佬们打的第二场atcoder&＃xff0c;不知不觉一星期都过去了。
任意门C - Reconciled?
题意&＃xff1a;n只猫&＃xff0c;m只狗排队&＃xff0c;猫与猫之间&＃xff0c;狗与狗之间是不同的&＃xff0c;同种动物不能相邻排&＃xff0c;问有多少种方案。
#include
#include
using namespace std;const int MOD&＃61;1e9&＃43;7;
int n,m,mmh&＃61;1;
int main(){scanf("%d%d",&n,&m);if (n<m) swap(n,m);if (n-m>1) return puts("0"),0;for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) mmh&＃61;1LL*mmh*i%MOD;for (int i&＃61;1;i<&＃61;m;i&＃43;&＃43;) mmh&＃61;1LL*mmh*i%MOD;if (n&＃61;&＃61;m) mmh&＃61;mmh*2%MOD;printf("%d\n",mmh);
}
D - Built?
题意&＃xff1a;定义平面上两点间距离为x坐标差和y坐标差的较小值&＃xff0c;求最小生成树。
题解&＃xff1a;分别按x坐标&＃xff0c;y坐标排序后只有相邻的点之间的边是有贡献的。
#include
#include
#define MN 210001
using namespace std;const int MOD&＃61;1e9&＃43;7;
int n,m,fa[MN],num&＃61;0;
long long mmh&＃61;0;
struct na{int x,y,p;}p[MN];
struct bi{int x,y,z;}B[MN];
bool cmpx(na a,na b){return a.x<b.x;}
bool cmpy(na a,na b){return a.y<b.y;}
bool cmp(bi a,bi b){return a.z<b.z;}
int gf(int x){return x&＃61;&＃61;fa[x]?x:fa[x]&＃61;gf(fa[x]);}
int main(){scanf("%d",&n);for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) scanf("%d%d",&p[i].x,&p[i].y),p[i].p&＃61;i,fa[i]&＃61;i;sort(p&＃43;1,p&＃43;1&＃43;n,cmpx);for (int i&＃61;2;i<&＃61;n;i&＃43;&＃43;) B[&＃43;&＃43;num].x&＃61;p[i-1].p,B[num].y&＃61;p[i].p,B[num].z&＃61;p[i].x-p[i-1].x;sort(p&＃43;1,p&＃43;1&＃43;n,cmpy);for (int i&＃61;2;i<&＃61;n;i&＃43;&＃43;) B[&＃43;&＃43;num].x&＃61;p[i-1].p,B[num].y&＃61;p[i].p,B[num].z&＃61;p[i].y-p[i-1].y;sort(B&＃43;1,B&＃43;1&＃43;num,cmp);for (int i&＃61;1;i<&＃61;num;i&＃43;&＃43;){B[i].x&＃61;gf(B[i].x);B[i].y&＃61;gf(B[i].y);if (B[i].x!&＃61;B[i].y) fa[B[i].x]&＃61;B[i].y,mmh&＃43;&＃61;B[i].z;}printf("%lld\n",mmh);
}
E - Connected?
题意&＃xff1a;给矩形内一些点对&＃xff0c;问点对之间连边是否可能不出现相交。
题解&＃xff1a;&＃xff08;这貌似是GDKOI2013的题&＃xff1f;&＃xff09;只有边界上的点是有用的&＃xff0c;然后把边界展开成一条线段&＃xff0c;求区间是否有交即可。
F - Exhausted?
题意&＃xff1a;求最大匹配&＃xff0c;限制是左边的每个点 i 不能与右端的$[L_{i}&＃43;1,R_{i}-1]$区间内的点匹配。
题解&＃xff1a;把左端的点按$L_{i}$排序&＃xff0c;从小到大枚举&＃xff0c;如果当前点x可匹配的区间未被匹配完全&＃xff0c;那就直接匹配&＃xff0c;已经匹配完全就把已被选择的点中$R_{i}$最小的一个点y拿出来&＃xff0c;让x顶替y匹配的位置&＃xff08;如果$R_{x}<&＃61;R{y}$自然就不用换了&＃xff09;。最后未被选择的点再强行匹配右端部分即可。
考场上网络流没卡过&＃xff0c;就yy了个奇怪的贪心&＃xff0c;然后挂掉了。
#include
#include
#include
#include
#define MN 110000
using namespace std;int read_p,read_ca;
inline int read(){read_p&＃61;0;read_ca&＃61;getchar();while(read_ca<&＃39;0&＃39;||read_ca>&＃39;9&＃39;) read_ca&＃61;getchar();while(read_ca>&＃61;&＃39;0&＃39;&&read_ca<&＃61;&＃39;9&＃39;) read_p&＃61;read_p*10&＃43;read_ca-48,read_ca&＃61;getchar();return read_p;
}
struct na{int l,r;}p[MN];
bool cmpl(na a,na b){return a.l&＃61;&＃61;b.l?a.r>b.r:a.l<b.l;}
priority_queue<int,vector<int>,greater<int> > q,_q;
int n,m,mmh;
int main(){mmh&＃61;n&＃61;read();m&＃61;read();for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) p[i].l&＃61;read(),p[i].r&＃61;read();sort(p&＃43;1,p&＃43;1&＃43;n,cmpl);for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)if (p[i].l&＃61;&＃61;q.size()) q.push(p[i].r),_q.push(q.top()),q.pop();else q.push(p[i].r),mmh--;for (int i&＃61;q.size()&＃43;1;i<&＃61;m&&!_q.empty();i&＃43;&＃43;) if (_q.top()<&＃61;i) _q.pop(),mmh--;printf("%d\n",mmh);
}
凭借出前三题的手速还是涨了点rating
京公网安备 11010802041100号