2017 湘潭邀请赛&JSCPC G&J

训练的时候对G想了一个假算法。。也有很大可能是写错了。。

下来一看别人的G 看起来很奇妙。。

开始把所有的左括号翻成右括号，然后cost*=-1 这样在优先队列中就是最优的然后for每一段如果前缀和小于0就从优先队列中取右括号翻转

最后的结果一定是一个可行的括号序列

1 如果所有的原左括号都被重新反转，那么我们的选择仍然是最优，因为实际上没有在这个上面消耗

2 如果原左括号没有都被反转回去那么我们的实际消耗也是最少的

J题一看就能想出来nmmm的想法但是很远。。并没有想到nmm的没想到可以nmmlogm过就比较神奇了

画图可以发现数字的大小其实是从右向左不断扩散的

思考nmmm的做法对于第i个数字枚举他是第k个a中的数字，那么就需要找到第j个数字让它在a中做第k+1位来承接状态

但是这样状态不全第j个数字是有限制的它需要比第i个数字大或者小而又有范围

因为数字的大小有规律所以把范围也记录下来第i个数字一定是范围的一边于是只需要记录另一边就可以了

对于“另一边” 要么是第j个数字要么是之前传下来的总之我们需要for一下这个范围来让他们加上当前状态

考虑区间加直接把状态加上去就可以把m变成logm了。。虽然复杂度仍然感觉不科学

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<vector>

#include<queue>

#include<map>

#include<algorithm>

#include<stack>

using namespace std;

#define L long long

#define rep(i,l,r) for(L i = l ; i <= r ; i ++ )

const L mod = 1000000000 + 7 ;

struct node {

    L cost ;

    L num ;

    friend bool operator < (node A , node B) {

        return A.cost > B.cost ;

    }

};

L a[100050] ;

L b[100050] ;

int main () {

    L n ;

    while(scanf("%lld" , &n) != EOF) {

        L ans = 0 ;

        rep(i,1,n) {

            L l,d ; char s[20] ;

            scanf("%lld%s%lld" , &l,s,&d) ;

            a[i] = l ;

            b[i] = d ;

            if(s[0] == '(') {

                ans += a[i] * b[i] ;

                b[i] *= -1 ;

            }

        }

        priority_queue<node> q ;

        L sum = 0 ;

        rep(i,1,n) {

            node c ;

            c.num = a[i] ;

            c.cost = b[i] ;

            q.push(c) ;

            sum -= c.num ;

            if(sum >= 0) continue ;

            L ned = sum * (-1) ;

            ned ++ ; ned /= 2 ;

            sum += ned * 2;

            while(ned > 0) {

                node c = q.top() ; q.pop() ;

                if(c.num >= ned) {

                    c.num -= ned ;

                    ans += ned * c.cost ;

                    q.push(c) ;

                    ned = 0 ;

                }

                else {

                    ned -= c.num ;

                    ans += c.num * c.cost ;

                }

            }

        }

        printf("%lld\n" , ans) ;

    }

}

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<vector>

#include<queue>

#include<map>

#include<algorithm>

#include<stack>

using namespace std;

#define L long long

#define rep(i,l,r) for(L i = l ; i <= r ; i ++ )

const L mod = 1000000000 + 7 ;

L n , m ;

L a[22] ;

L b[505] ;

L dp[505][505][22] ;

L s[505][505][22] ;

L lowbit(L x) {

    return (x & (-x)) ;

}

void add(L x,L j,L k,L val) {

    while(x <= m) {

        s[x][j][k] += val ;

        while(s[x][j][k] < 0) s[x][j][k] += mod ;

        s[x][j][k] %= mod ;

        x += lowbit(x) ;

    }

}

L sum(L x,L j,L k) {

    L sum = 0 ;

    while(x) {

        sum += s[x][j][k] ;

        sum %= mod ;

        x -= lowbit(x) ;

    }

    return sum ;

}

void upda(L l,L r,L val,L j,L k) {

    add(l,j,k,val) ;

    add(r+1,j,k,-val) ;

}

int main () {

    while(cin >> n >> m) {

        rep(i,1,n) cin >> a[i] ;

        rep(i,1,m) cin >> b[i] ;

        memset(dp, 0, sizeof(dp)) ;

        memset(s, 0, sizeof(s)) ;

        L ans = 0 ;

        for(L i = 1 ; i <= m ; i ++ ) {

            for(L j = 1 ; j <= m ; j ++ ) {

                for(L k = 1 ; k <= n ; k ++ ) {

                    if(k == 1) {

                        L bord ;

                        if(a[1] == 0) bord = m ;

                        else bord = 1 ;

                        if (bord != j) continue ;

                        dp[i][bord][1] = 1 ;

                        if (k == n){

                            ans += dp[i][j][k];

                            ans %= mod ;

                        }

                    } else {

                        dp[i][j][k] = sum(b[i], j, k);

                        if (k == n){

                            ans += dp[i][j][k];

                            ans %= mod ;

                        }

                    }

                }

            }

            for(L j = 1 ; j <= m ; j ++ ) {

                for(L k = 1 ; k <= n ; k ++ ) {

                    if(k == 1) {

                        L bord ;

                        if(a[1] == 0) bord = m ;

                        else bord = 1 ;

                        if (bord != j) continue ;

                        L x = min(bord,b[i]) ;

                        L y = max(bord,b[i]) ;

                        if(a[2] == 0) {

                            upda(x,y,1,y,2) ;

                        } else {

                            upda(x,y,1,x,2) ;

                        }

                    } else {

                        L x = min(j, b[i]);

                        L y = max(j, b[i]);

                        if (dp[i][j][k] == 0) continue;

                        if (a[k + 1] == 0) {

                            upda(x, y, dp[i][j][k], y, k + 1);

                        } else {

                            upda(x, y, dp[i][j][k], x, k + 1);

                        }

                    }

                }

            }

        }

        printf("%lld\n" , ans) ;

    }

}

J线段树会T。。。

巴特西

2017 湘潭邀请赛&JSCPC G&J

最新文章

热门文章