2014暑期最后一次个人赛-白红宇

2014暑期最后一次个人赛

阅读量：4510 次

发布时间：2019-06-08

本文共 3868 字，大约阅读时间需要 12 分钟。

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

像这个一样

，其实我也挺喜欢听小苹果的，虽然一开始骂这是一首破歌。

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

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

码C题水题，又WA，后来一开窍，C、A题BUG瞬间找出，接着H/B/D都是WA了后才过，

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

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

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

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

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

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

具体看代码：

view code#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            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
             
              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
              
               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
               
                0) addedge(getid(i, j)+B, getid(i, j-1), 1, 0); } addedge(getid(i,n-1)+B, t, INF, 0); } cout<
                
                 <
                 
                  0 && n) solve(); return 0;}

B题： LIS+贪心

view code#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            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
             
              a[i]) L = a[i]; if(R
              
               >_; while(_--) solve(); return 0;}

贪心，

view code#include 
     
      #include 
      
       #include 
       
        #include 
        
         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
         
          =0; i--)        {            if(f) suma += a[i];            else sumb += a[i];            f ^= 1;        }        printf("%d %d\n", suma, sumb);    }    return 0;}