雅礼联考
睡过头错过考试,下午走的时候才看到题….
题目大意
T1
圆上有\(2 \times n\)个点和连接这些点的\(n\)条弦,有多少个无序的三元组,是的对应的三条弦可以通过距离的缩放中心对称.
T2
给定一个\(n \times m\)的网格.你在左下角\((n,1)\),给定网格图,+表示可以走.*表示障碍.只能向上走或者是右拐.问走到\((y,x)\)的方案数\(mod\) \(k\)的值.
T3
最大权闭合图裸题
题解:
T1
有两种做法.
分类讨论:合法情况和不合法情况.
讨论合法情况求和,输出即为答案.
讨论不合法情况求和,总情况减去不合法即为答案.
合法情况有三种
从这个草率的图中可以发现,我们要找一个满足条件的,所以有三种编号情况,转化成序列问题,解决即可.
1 2 3 4 5 6
1,2相连,3,4相连,5,6相连.
1,6相连,2,5相连,3,4相连.
1,4相连,2,5相连,3,6相连.
三种情况判断就好了.
不会啊QAQ
所以放弃这种做法.
不合法情况有三种
有两个公共点
有一个公共点
三边均没有交点.
总答案个数是\(\frac{n \times (n-1) \times (n-2)}{6}\)
合法情况又不会判断…
所以不合法情况分情况讨论.
没有交点的可以通过判断最中间的边的左(上)右(下)来算出.
答案不就是两边的边数乘起来.乘法原理QAQ
有一个交点和两个交点的特殊情况
统计一下和它相交的边的个数,乘以和他不相交的边的个数即为答案.
开一个\(pair\)统计.
默认\(first\)较小,\(second\)较大.
排序后用数据结构维护一下.
判断两次.
第一遍
枚举\(1-n\)统计\(1-first[i]\)中在这个边的左边的边数.
第二遍
枚举\(n-1\)统计\(second[i]-2*n\)中在这个边左右的边数
最后算出来就好了.
数据结构就选树状数组了,懒.
QAQ
代码实现
|
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 |
#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; template<class T>void read(T &x){ x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9'){f|=(ch=='-');ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x=f?-x:x; return ; } typedef long long LL; const int inf=0x3f3f3f3f; const int maxn=100010; int num[3][maxn],n; pair<int,int>a[maxn]; struct myx{ int num[maxn<<1]; void clear(){memset(num,0,sizeof(num));} int lowbit(int x){return x&-x;} void update(int o){ for(;o<=2*n;o+=lowbit(o)) ++num[o]; return; } int query(int l,int r,int ret=0){ while(r) ret+=num[r],r-=lowbit(r);l--; while(l) ret-=num[l],l-=lowbit(l); return ret; } }T1,T2; int main() { freopen("a.in","r",stdin); read(n); for(int i=1;i<=n;i++){ int x,y; read(x),read(y); if(x>y) swap(x,y); a[i]=make_pair(x,y); } sort(a+1,a+1+n); for(int i=1;i<=n;i++){ if(a[i].second!=2*n) num[0][i]+=T1.query(a[i].second+1,2*n); if(a[i].first!=1) num[0][i]+=T1.query(1,a[i].first-1); T1.update(a[i].second); } T1.clear(); for(int i=n;i;i--){ if(a[i].second!=2*n) num[0][i]+=T1.query(a[i].second+1,2*n); if(a[i].second!=1) num[1][i]+=T2.query(1,a[i].second-1); T1.update(a[i].first); T2.update(a[i].second); } for(int i=1;i<=n;i++) num[2][i]=n-1-num[0][i]-num[1][i]; LL ans1=0,ans2=0; for(int i=1;i<=n;i++) ans1+=(LL)num[0][i]*num[1][i]; for(int i=1;i<=n;i++) ans2+=(LL)num[2][i]*(n-1-num[2][i]); printf("%lld\n",(LL)n*(n-2)*(n-1)/6-ans1-ans2/2); return 0; } |
T2:
好像是一种神奇的递推.然而并没有做出来…
T3:
最大权闭合图裸题
拆完点后连边.
正权边与源点连对应容量的边.
负权边与汇点连对应容量的边.
剩下没有连的将两个点之间连上容量为\(inf\)的边.
然后\(Dinic\)求一下最小割就好了.
代码后面写了再放QAQ
By:Wahacer
2017.12.26
9:18