第一次打USACO月赛。赛中晋级制赞,实时反馈制赞。然而题目难度不敢恭维啊。
Bronze
square : 界出最小覆盖矩形的长和宽取max就是正方形的边长。
blocks : 注意到每个字母贡献独立。每张卡片取较多数目的那一面就好。
cowsignal : 数组的基本操作。
Silver
haybales : 二分/STL均可。
citystate : 暴力记录所有状态统计答案即可。注意题意注意特判。
moocast : 根据题意连边后一遍传递闭包。
Gold
moocast : 最小生成树。
checklist : 表示当前完成前者
个,后者
个,位置在
的最小花费。注意边界。
laser : BFS一波。
Platinum
triangles : 考虑容斥。可以转化为求一条线段的某一侧有多少点和两条线段夹着多少点。后者极角排序解决。
team : 先排序,表示现在考虑前者前
个,后者前
个,选出
个的方案数。
roboherd : K短路模型。不过数据范围较大,A*无法通过。论文方法,可持久化可并堆上之。可能需要卡卡空间。
就贴一波Platinum的代码吧。
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 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
#include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int maxn=305; const double eps=1e-16; inline int dcmp(double x) { if(fabs(x)<eps) return 0; return x>0?1:-1; } struct node { LL x,y; node(LL a=0,LL b=0):x(a),y(b) {} } p[maxn]; inline node operator - (node a,node b) { return node(a.x-b.x,a.y-b.y); } int res[maxn],rk[maxn]; int s[maxn][maxn]; int w[maxn][maxn][maxn]; inline LL _cross(node a,node b) { return a.x*b.y-a.y*b.x; } inline LL cross(node a,node b,node c) { return _cross(b-a,c-a); } int cn; inline bool cmp(int i,int j) { return dcmp(atan2(p[i].x-p[cn].x,p[i].y-p[cn].y)-atan2(p[j].x-p[cn].x,p[j].y-p[cn].y))>0; } int main() { freopen("triangles.in","r",stdin); freopen("triangles.out","w",stdout); int n; read(n); REP(i,1,n) read(p[i].x),read(p[i].y); REP(i,1,n) REP(j,1,n) if(i!=j) REP(k,1,n) if(i!=k && j!=k) s[i][j]+=(cross(p[i],p[j],p[k])>0); REP(i,1,n) { cn=i;int idx=0; REP(j,1,n) if(i!=j) { ++idx;rk[idx]=j; } sort(rk+1,rk+idx+1,cmp); REP(j,1,idx) REP(k,j+1,idx) { w[rk[k]][i][rk[j]]=k-j-1; w[rk[j]][i][rk[k]]=idx-(k-j+1); } } REP(i,1,n) REP(j,i+1,n) REP(k,j+1,n) { if(cross(p[i],p[j],p[k])>0) ++res[n-s[i][j]-s[j][k]-s[k][i]+w[i][j][k]+w[j][k][i]+w[k][i][j]]; else ++res[n-s[i][k]-s[k][j]-s[j][i]+w[i][k][j]+w[k][j][i]+w[j][i][k]]; } REP(i,0,n-3) printf("%d\n",res[i]); return 0; } |
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 |
#include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int maxn=1005; const int mo=(int)(1e9)+9; int a[maxn],b[maxn]; int f[maxn][maxn][12]; inline void add(int& x,int v) { x+=v;if(x>=mo) x-=mo; } int main() { freopen("team.in","r",stdin); freopen("team.out","w",stdout); int n,m,k; read(n);read(m);read(k); REP(i,1,n) read(a[i]); sort(a+1,a+n+1); REP(i,1,m) read(b[i]); sort(b+1,b+m+1); REP(i,0,n) f[i][0][0]=1; REP(i,0,m) f[0][i][0]=1; REP(i,1,n) REP(j,1,m) REP(c,0,k) { if(a[i]>b[j] && c) add(f[i][j][c],f[i-1][j-1][c-1]); add(f[i][j][c],(1LL*f[i][j-1][c]+f[i-1][j][c]-f[i-1][j-1][c]+mo)%mo); } printf("%d\n",f[n][m][k]); return 0; } |
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 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
#include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int maxn=(int)(1e5)+5; struct node { node *l,*r; LL v;int to,h; node() {l=r=NULL;v=to=0;h=-1;} } *p[maxn]; node *mergex(node* a,node* b) { if(a==NULL) return b; if(b==NULL) return a; if(a->v > b->v) swap(a,b); a->r=mergex(a->r,b); LL lh=-1,rh=-1; if(a->l) lh=a->l->h; if(a->r) rh=a->r->h; if(rh>lh) swap(a->l,a->r); a->h=rh+1;return a; } node *merge(node* a,node* b) { if(a==NULL) return b; if(b==NULL) return a; if(a->v > b->v) swap(a,b); node *res=new node(); *res=*a; res->r=merge(res->r,b); LL lh=-1,rh=-1; if(res->l) lh=res->l->h; if(res->r) rh=res->r->h; if(rh>lh) swap(res->l,res->r); res->h=rh+1;return res; } struct snode { LL val; node* s; }; inline bool operator < (snode a,snode b) { return a.val+a.s->v > b.val+b.s->v; } LL ds[maxn]; vector<LL> nxt[maxn]; priority_queue<snode> Q; int main() { freopen("roboherd.in","r",stdin); freopen("roboherd.out","w",stdout); int n,k; read(n);read(k);++n; REP(i,1,n-1) { int m,x; read(m); REP(j,1,m) { read(x); nxt[i].push_back(x); } sort(nxt[i].begin(),nxt[i].end()); } ds[n]=0; PER(i,n-1,1) ds[i]=ds[i+1]+nxt[i][0]; PER(x,n-1,1) { p[x]=p[x+1]; node *rt=NULL; for(int i=1;i<nxt[x].size();i++) { node *tmp=new node(); tmp->v=nxt[x][i]+ds[x+1]-ds[x]; tmp->to=x+1; rt=mergex(rt,tmp); } p[x]=merge(p[x],rt); } snode tmp; tmp.val=0;tmp.s=p[1];Q.push(tmp); LL res=ds[1],now=0; REP(i,2,k) { if(Q.empty()) break; snode x=Q.top();Q.pop(); now=x.val+x.s->v; res+=now+ds[1]; snode w; w.val=x.val; w.s=merge(x.s->l,x.s->r); if(w.s) Q.push(w); w.val=now; w.s=p[x.s->to]; if(w.s) Q.push(w); } printf("%lld\n",res); return 0; } |