A simple Blog for wyx I've been down the bottle hoping.
SRM 553 dp 差分约束
发表于: | 分类: Oi | 评论:0 | 阅读:69

250 pts
逗比题,给定一个全是0的无穷大的栈还有一个序列,每次取出序列的第一个元素,如果 $>0$ 就推到栈顶,如果 $=0$ 就把栈顶和栈顶下面的第一个元素弹出,求和,再把和推入,现在告诉你有一个元素不知道是啥以及最后的栈顶是多少,请求出该元素的值

首先判断是不是 0 ,按照是 0 跑一边就行了

然后如果判断不是 0, 就把他设成 x 跑一遍解方程就行了

500 pts

非常麻烦的 $dp$ , 一看就知道怎么做但是根本不想写系列,推荐SR队爷的题解, 口胡的 非常详细

1000 pts

给定一个 $n$ 个节点的环,要求每两个点直接的距离为正整数,然后给定若干个限制条件,求环长一共有多少种不同的取值

提示
不知道怎么建图的想想前缀和的不等关系

说道这不知道怎么做的可以重新学习差分约束了

可以发现答案取值是一个区间,所以我们二分区间的左右端点即可。对于一个不可行的答案,图中必然有负环。在求最短路的时候记录一下边的系数,然后按照正负讨论就行了。注意如果有负环的系数和为0显然无解。


// BEGIN CUT HERE
// END CUT HERE
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fir first
#define sec second
#define mp make_pair 
typedef long long LL;
typedef pair <LL,LL> PLL;
const LL inf = 100000000000LL;

inline PLL add(PLL a,PLL b) {
    return mp(a.fir+b.fir,a.sec+b.sec);
}
PLL dis[100+5];

vector <pair<int,PLL> >edge[100+5];

class YamanoteLine
{
    public:
    pair <bool, long long> spfa( long long length, int n, vector <int> s1, vector <int> t1, vector <int> l1, vector <int> s2, vector <int> t2, vector <int> l2) {
        for(int i=0;i<=n;++i) edge[i].clear();
        for(int i=0;i<=n-1;++i) edge[i].pb(mp(i+1,mp(-1,0)));
        edge[n].pb(mp(0,mp(length,1)));
        edge[0].pb(mp(n,mp(-length,-1)));
        for(int i=0;i<t1.size();++i) {
            if(s1[i] < t1[i]) edge[s1[i]].pb(mp(t1[i],mp(-l1[i],0)));
            else edge[s1[i]].pb(mp(t1[i],mp(length-l1[i],1)));
        }
        for(int i=0;i<t2.size();++i) {
            if(s2[i] < t2[i]) edge[t2[i]].pb(mp(s2[i],mp(l2[i],0)));
            else edge[t2[i]].pb(mp(s2[i],mp(-length+l2[i],-1)));
        }
        for(int i=0;i<=n;++i) dis[i] = mp(inf,0);
        dis[0] = mp(0,0);
        PLL tmp, imp;
        bool updata = false;
        for(int times = 1; times <= n*n; ++ times){
            updata = false;
            for(int i=0;i<=n;++i) {
                for(int k=0;k<edge[i].size();++k) 
                    if(dis[edge[i][k].fir].fir < inf){
                        tmp = add(edge[i][k].sec,dis[edge[i][k].fir]);
                        if(tmp.fir < dis[i].fir) {
                            dis[i] = tmp;
                            if(dis[i].fir < 0) return mp(false,dis[i].sec);
                            updata = true;
                            imp = tmp;
                        }
                    }
            }
        }
        if(!updata) return mp(1,0);
        else return mp(0,imp.sec);
    }
    long long howMany(int n, vector <int> s1, vector <int> t1, vector <int> l1, vector <int> s2, vector <int> t2, vector <int> l2){
        LL tmp1 = inf, tmp2 = -1, L, R;
        L = n , R = inf;
        pair <bool, LL> ans1, ans2;
        while(L <= R) {
            LL mid = (L+R) >> 1;
            ans1 = spfa( mid, n, s1, t1, l1, s2, t2, l2);
            if(ans1.fir || ans1.sec > 0) L = (tmp1 = mid) + 1;
            else R = mid - 1;
        }
        L = n , R = inf;
        while(L <= R) {
            LL mid = (L+R) >> 1;
            ans2 = spfa( mid, n, s1, t1, l1, s2, t2, l2);
            if(ans2.fir || ans2.sec < 0) R = (tmp2 = mid) - 1;
            else L = mid + 1;
        }
        if (tmp2 >= n && tmp1 == inf) return -1;
        if (tmp2 == -1) return 0; else if(tmp1 - tmp2 + 1 < 0) return 0;
        else return tmp1 - tmp2 + 1;
    }

// BEGIN CUT HERE
    public:
    void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); if ((Case == -1) || (Case == 6)) test_case_6(); }
    private:
    template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
    void verify_case(int Case, const long long &Expected, const long long &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
    void test_case_0() { int Arg0 = 3; int Arr1[] = {}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arr3[] = {}; vector <int> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3[0]))); int Arr4[] = {0,1,2}; vector <int> Arg4(Arr4, Arr4 + (sizeof(Arr4) / sizeof(Arr4[0]))); int Arr5[] = {1,2,0}; vector <int> Arg5(Arr5, Arr5 + (sizeof(Arr5) / sizeof(Arr5[0]))); int Arr6[] = {1,1,1}; vector <int> Arg6(Arr6, Arr6 + (sizeof(Arr6) / sizeof(Arr6[0]))); long long Arg7 = 1LL; verify_case(0, Arg7, howMany(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5, Arg6)); }
    void test_case_1() { int Arg0 = 3; int Arr1[] = {}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arr3[] = {}; vector <int> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3[0]))); int Arr4[] = {0,1,2}; vector <int> Arg4(Arr4, Arr4 + (sizeof(Arr4) / sizeof(Arr4[0]))); int Arr5[] = {1,2,0}; vector <int> Arg5(Arr5, Arr5 + (sizeof(Arr5) / sizeof(Arr5[0]))); int Arr6[] = {2,2,2}; vector <int> Arg6(Arr6, Arr6 + (sizeof(Arr6) / sizeof(Arr6[0]))); long long Arg7 = 4LL; verify_case(1, Arg7, howMany(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5, Arg6)); }
    void test_case_2() { int Arg0 = 3; int Arr1[] = {}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arr3[] = {}; vector <int> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3[0]))); int Arr4[] = {0,1,2}; vector <int> Arg4(Arr4, Arr4 + (sizeof(Arr4) / sizeof(Arr4[0]))); int Arr5[] = {2,0,1}; vector <int> Arg5(Arr5, Arr5 + (sizeof(Arr5) / sizeof(Arr5[0]))); int Arr6[] = {3,3,3}; vector <int> Arg6(Arr6, Arr6 + (sizeof(Arr6) / sizeof(Arr6[0]))); long long Arg7 = 2LL; verify_case(2, Arg7, howMany(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5, Arg6)); }
    void test_case_3() { int Arg0 = 4; int Arr1[] = {0,1,2,3}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {2,3,0,1}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arr3[] = {3,4,4,3}; vector <int> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3[0]))); int Arr4[] = {1,3}; vector <int> Arg4(Arr4, Arr4 + (sizeof(Arr4) / sizeof(Arr4[0]))); int Arr5[] = {3,1}; vector <int> Arg5(Arr5, Arr5 + (sizeof(Arr5) / sizeof(Arr5[0]))); int Arr6[] = {5,5}; vector <int> Arg6(Arr6, Arr6 + (sizeof(Arr6) / sizeof(Arr6[0]))); long long Arg7 = 4LL; verify_case(3, Arg7, howMany(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5, Arg6)); }
    void test_case_4() { int Arg0 = 4; int Arr1[] = {0,2}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {2,0}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arr3[] = {5,5}; vector <int> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3[0]))); int Arr4[] = {1,3}; vector <int> Arg4(Arr4, Arr4 + (sizeof(Arr4) / sizeof(Arr4[0]))); int Arr5[] = {3,1}; vector <int> Arg5(Arr5, Arr5 + (sizeof(Arr5) / sizeof(Arr5[0]))); int Arr6[] = {4,4}; vector <int> Arg6(Arr6, Arr6 + (sizeof(Arr6) / sizeof(Arr6[0]))); long long Arg7 = 0LL; verify_case(4, Arg7, howMany(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5, Arg6)); }
    void test_case_5() { int Arg0 = 5; int Arr1[] = {}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arr3[] = {}; vector <int> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3[0]))); int Arr4[] = {0,2}; vector <int> Arg4(Arr4, Arr4 + (sizeof(Arr4) / sizeof(Arr4[0]))); int Arr5[] = {2,4}; vector <int> Arg5(Arr5, Arr5 + (sizeof(Arr5) / sizeof(Arr5[0]))); int Arr6[] = {2,2}; vector <int> Arg6(Arr6, Arr6 + (sizeof(Arr6) / sizeof(Arr6[0]))); long long Arg7 = -1LL; verify_case(5, Arg7, howMany(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5, Arg6)); }
    void test_case_6() { int Arg0 = 10; int Arr1[] = {5,7,2,3,9,4,6,0,4,2}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {0,8,3,9,8,0,8,7,1,7}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arr3[] = {61,54,20,64,25,73,83,79,86,56}; vector <int> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3[0]))); int Arr4[] = {4,5,4,0,8,3,8,5,5,9}; vector <int> Arg4(Arr4, Arr4 + (sizeof(Arr4) / sizeof(Arr4[0]))); int Arr5[] = {5,2,0,1,1,4,7,6,8,3}; vector <int> Arg5(Arr5, Arr5 + (sizeof(Arr5) / sizeof(Arr5[0]))); int Arr6[] = {1951,6102,3625,5737,1590,1228,9234,1342,9060,1008}; vector <int> Arg6(Arr6, Arr6 + (sizeof(Arr6) / sizeof(Arr6[0]))); long long Arg7 = 5726LL; verify_case(6, Arg7, howMany(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5, Arg6)); }

// END CUT HERE

}t;
// BEGIN CUT HERE
int main(){
    YamanoteLine ___test;
    ___test.run_test(-1);
    return 0;
}
// END CUT HERE

myy有一个比较厉害的做法,可以看看队爷题解

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP