USACO Dec. 16 通关记

发布于2016年12月20日 | 暂无评论 | 1,760阅读 | 比赛经历

第一次打USACO月赛。赛中晋级制赞，实时反馈制赞。然而题目难度不敢恭维啊。

Bronze

square : 界出最小覆盖矩形的长和宽取max就是正方形的边长。

blocks : 注意到每个字母贡献独立。每张卡片取较多数目的那一面就好。

cowsignal : 数组的基本操作。

Silver

haybales : 二分/STL均可。

citystate : 暴力记录所有状态统计答案即可。注意题意注意特判。

moocast : 根据题意连边后一遍传递闭包。

Gold

moocast : 最小生成树。

checklist : $f[i,j,0/1]$ 表示当前完成前者 $i$ 个，后者 $j$ 个，位置在 $0/1$ 的最小花费。注意边界。

laser : BFS一波。

Platinum

triangles : 考虑容斥。可以转化为求一条线段的某一侧有多少点和两条线段夹着多少点。后者极角排序解决。

team : 先排序， $f[i,j,k]$ 表示现在考虑前者前 $i$ 个，后者前 $j$ 个，选出 $k$ 个的方案数。

roboherd : K短路模型。不过数据范围较大，A*无法通过。论文方法，可持久化可并堆上之。可能需要卡卡空间。

就贴一波Platinum的代码吧。

#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;
}

#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;

}

#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;
}

#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;

}

#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;
}

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;

}

AC. 梦想

USACO Dec. 16 通关记

Bronze

Silver

Gold

Platinum

快速访问

随便看看

友情链接

标签