2014暑期最后一次个人赛

首页 > 代码库 > 2014暑期最后一次个人赛

2024-07-17 01:37:11 222人阅读

今天这场打的还不错吧，就是开场一个小时就WA在两道水题上了，今天的题总体上比原先的个人赛水多了，有点喜剧性吧，就

像这个一样

74`PXH)@[$V`S]B8Y}8{~MB ，其实我也挺喜欢听小苹果的，虽然一开始骂这是一首破歌。

今天看到A题CodeForces 205B，好开心，这不是可以用昨天那道ZOJ 2243 treap用线段树解决的方法解决。开心的打完代码，

想着我实在太聪明了，可是，但我提交的时候发现 6S09BSAPQ_2WQ8`K59BY)RH ，好吧，我又把一道题复杂话了，WA了，一时找不到bug,去

码CUVA 11452题水题，又WA，后来一开窍，C、A题BUG瞬间找出，接着HLightOJ 1148/BLightOJ 1277/DCodeForces 284C都是WA了后才过，

看来我今天不宜做题，最后终于yyG题CodeForces 388C、CodeForces 388C题，1y过了。

看F题UVA 11301，dp?没想法。最大流，咦，好像可以，建图，比赛没过，赛后补过。

重点讲讲F题，F题可以DP，可以最小费用最大流，DP貌似是正解，像我这种渣渣就来讲讲歪解吧。

把图中每个点拆成两个点，流量为1，费用为原图点的权值。相邻的点连一条边，费用为0，流量为1.

一个起点s连向3个点@，流量为1，费用为0，

原矩阵中最后一列的点连向终点t,流量为INF，费用为0。

具体看代码：

view code#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>#include <vector>#include <cmath>#include <map>using namespace std;typedef long long ll;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1const int INF = 1<<30;const int N = 1010;const int M = N*15;int _, cas=1, n, m, s, t;char str[5][N];bool inq[M];int d[M];int p[M];int a[M];int pre[M];struct edge{    int u, v, cap,cost, next;    edge() {}    edge(int u, int v, int cap,int cost, int next):u(u),v(v),cap(cap),cost(cost),next(next) {}}e[200*N];int ecnt = 0;int getid(int x, int y){    return x*n+y+1;}void addedge(int u,int v, int cap, int cost){    e[ecnt] = edge(u, v, cap, cost, pre[u]);    pre[u] = ecnt++;    e[ecnt] = edge(v, u, 0, -cost, pre[v]);    pre[v] = ecnt++;}bool BellmanFort(int &flow, int &cost){    for(int i=s; i<=t; i++) d[i] = INF;    memset(inq, 0, sizeof(inq));    d[s] = 0; p[s] = 0; a[s] = INF;    queue<int >q;    q.push(s);    while(!q.empty())    {        int u = q.front(); q.pop();        inq[u] = 0;        for(int i=pre[u]; ~i; i=e[i].next)        {            int v = e[i].v;            if(e[i].cap>0 && d[v]>d[u]+e[i].cost)            {                d[v] = d[u] + e[i].cost;                p[v] = i;                a[v] = min(a[u], e[i].cap);                if(!inq[v])                {                    q.push(v);                    inq[v] = 1;                }            }        }    }    if(d[t]==INF) return false;    flow += a[t];    cost += d[t]*a[t];    int u = t;    while(u!=s)    {        e[p[u]].cap -= a[t];        e[p[u]^1].cap += a[t];        u = e[p[u]].u;    }    return true;}int Mincost(){    int flow = 0, cost = 0;    while(BellmanFort(flow, cost)) ;    return cost;}void solve(){    for(int i=0; i<5; i++) scanf("%s", str[i]);    ecnt = 0;    int B = getid(4,n-1)+1;    s = 0, t = getid(5,0)+B;    memset(pre, -1, sizeof(pre));    for(int i=0; i<5; i++)    {        if(str[i][0]==‘@‘) addedge(s, getid(i, 0), 1, 0);        for(int j=0; j<n; j++)        {            if(str[i][j]==‘@‘) addedge(getid(i, j), getid(i,j)+B, 1, 0);            else addedge(getid(i, j), getid(i,j)+B, 1, str[i][j]-‘0‘);            if(i>0)   addedge(getid(i, j)+B, getid(i-1, j), 1, 0);            if(i<4)   addedge(getid(i, j)+B, getid(i+1, j), 1, 0);            if(j<n-1) addedge(getid(i, j)+B, getid(i, j+1), 1, 0);            if(j>0)   addedge(getid(i, j)+B, getid(i, j-1), 1, 0);        }        addedge(getid(i,n-1)+B, t, INF, 0);    }    cout<<Mincost()<<endl;}int main(){//    freopen("in.txt", "r", stdin);    while(scanf("%d", &n)>0 && n) solve();    return 0;}

B题：LightOJ 1277 LIS+贪心

view code#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <queue>#include <vector>#include <cmath>#include <map>using namespace std;typedef long long ll;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1const int INF = 1<<30;const int N = 100010;int _, cas=1, n, m, len;int a[N], g[N], d[N], num[N];int res[N], cnt;int find(int x){    int l = 1, r = n, ans = 0;    while(l<=r)    {        int m = (l+r)>>1;        if(g[m]<=x) ans = m, r = m-1;        else l = m+1;    }    return ans;}void init(){    for(int i=1; i<=n; i++) g[i] = -INF;    for(int i=n; i>0; i--)    {        int k = find(a[i]);//        printf("%d : %d\n", i, k);        d[i] = k;        g[k] = a[i];    }}bool calc(){    cnt = 0;    int now = len, pre=-INF;    for(int i=1; i<=n; i++)    {        if(d[i]>=now && a[i]>pre)        {            res[cnt++] = a[i];            now--;            if(now==0) break;            pre = a[i];        }    }    if(cnt<len) return 0;    for(int i=0; i<cnt; i++)    {        if(i) printf(" ");        printf("%d", res[i]);    }    printf("\n");    return 1;}void solve(){    scanf("%d%d", &n, &m);    int L = INF, R=-INF;    for(int i=1; i<=n; i++)    {        scanf("%d", a+i);        if(L>a[i]) L = a[i];        if(R<a[i]) R = a[i];    }    printf("Case %d:\n", cas++);    init();    while(m--)    {        scanf("%d", &len);        if(!calc()) puts("Impossible");    }}int main(){//    freopen("in", "r", stdin);    cin>>_;    while(_--)    solve();    return 0;}

G题 CodeForces 388C 贪心，

view code#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;const int N = 200;int n, m,a[N];int main(){    while(scanf("%d", &n)>0)    {        int v, num, suma = 0, sumb = 0, cnt = 0;        for(int i=0; i<n; i++)        {            scanf("%d", &num);            int mid = (num+1)/2;            for(int j=1; j<=num; j++)            {                scanf("%d", &v);                if((num&1) && mid==j) a[cnt++] = v;                else                {                    if(j<=mid) suma += v;                    else sumb += v;                }            }        }        sort(a, a+cnt);        int f = 1;        for(int i=cnt-1; i>=0; i--)        {            if(f) suma += a[i];            else sumb += a[i];            f ^= 1;        }        printf("%d %d\n", suma, sumb);    }    return 0;}

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 2014暑期最后一次个人赛

2014暑期最后一次个人赛

看完仍有疑问？有类似问题直接问程序猿