A simple Blog for wyx I've been down the bottle hoping.
SRM 554 构造+dp
发表于: | 分类: Oi | 评论:0 | 阅读:75

T1 签到题,不会的看队爷题解吧
T2
这个T2非常妙啊,非常非常的好玩
给定一个序列,现在告诉你一个序列的价值为$\sum\limits_{i=1}^{len-1}{max{a_i,a_{i+1}}}$

让你给出一个字典序最小的排列方案使得这个价值尽可能的小

考虑一个序列中最大的数字必然是在序列的两个端点处取到,原因是这样的话最大值一会给答案贡献一次,如果他在一个序列的中间部分,那么只会给答案带来两次工薪
然后考虑去掉这个数字的序列,必然也是有这个性质的,原因是当最大值确定了之后其实对答案的贡献已经是一个常数了,那么减掉一个常数后对应的序列只有最优才行,那么显然需要有这个性质
于是我们会发现这个答案必然是一个倒裤衩形……

就是这样如果你看到这些字说明这个图片挂了
然后我们通过字典序最小卡一波,剩下的直接排序就行了,神一样的思路


// BEGIN CUT HERE
// END CUT HERE
#include <bits/stdc++.h>
using namespace std ;
const int inf = 0x7fffffff;
const int N = 500;
#define pb push_back
vector <int> a, ans;

bool vis[N];

bool cmp(int i,int j) {
    return a[i] ^ a[j] ? a[i] < a[j] : i < j; 
}

class TheBrickTowerMediumDivOne
{
    public:
    vector <int> find(vector <int> heights)
    {
        a = heights;
        int last = inf;
        int cnt = 0;
        for(int i=0;i<a.size();++i) {
            if(a[i] <= last) {
                ans.pb(i);
                last = a[i];
                vis[i] = 1;
            }
        }
        vector <int> A;
        for(int i=0;i<a.size();++i) if(!vis[i]) A.pb(i);
        sort(A.begin(), A.end(), cmp);
        for(int i=0;i<A.size();++i) ans.pb(A[i]);
        return ans;
    }
 
    
// 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(); }
    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 vector <int> &Expected, const vector <int> &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: " << print_array(Expected) << endl; cerr << "\tReceived: " << print_array(Received) << endl; } }
    void test_case_0() { int Arr0[] = {4, 7, 5}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {0, 2, 1 }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(0, Arg1, find(Arg0)); }
    void test_case_1() { int Arr0[] = {4, 4, 4, 4, 4, 4, 4}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {0, 1, 2, 3, 4, 5, 6 }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(1, Arg1, find(Arg0)); }
    void test_case_2() { int Arr0[] = {2, 3, 3, 2}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {0, 3, 1, 2 }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(2, Arg1, find(Arg0)); }
    void test_case_3() { int Arr0[] = {13, 32, 38, 25, 43, 47, 6}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {0, 6, 3, 1, 2, 4, 5 }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(3, Arg1, find(Arg0)); }

// END CUT HERE

}t;
// BEGIN CUT HERE
int main(){
    vector <int> g = t.find({10, 10, 46, 4});
    return 0;
    TheBrickTowerMediumDivOne ___test;
    ___test.run_test(-1);
    return 0;
}
// END CUT HERE

T3 裸地状压dp就是转移的时候你把k那维直接拆成对应的$k$部分的点就行了,然后你会发现这个东西其实和 $H$ 是没啥关系的所以直接矩阵乘法就行了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
typedef long long LL;
const LL mod = 1234567891;
const LL N = 2500, M = 130;
using namespace std;

LL m;

struct Matrix {
    LL a[M][M];
}dp, ini;

Matrix operator * (Matrix a,Matrix b) {
    Matrix c;
    for(LL i=1;i<=m;++i) 
        for(LL j=1;j<=m;++j) {
            c.a[i][j] = 0;
            for(LL k=1;k<=m;++k) c.a[i][j] = (LL) (a.a[i][k] * b.a[k][j] % mod + c.a[i][j]) % mod;
        }
    return c;
}

Matrix pow(Matrix a,LL b) {
    Matrix ans ;memset(ans.a, 0, sizeof ans);
    for(LL i=1;i<=m;++i) ans.a[i][i] = 1;
    for(;b;b>>=1, a=a*a) if(b&1) ans = ans * a;
    return ans;
}

LL pow(LL a,LL b) {
    LL res = 1;
    for(;b;b>>=1,a=a*a%mod) if(b&1) res = res * a % mod;
    return res;
}
class TheBrickTowerHardDivOne
{
    public:
    LL a[N], c[N];
        LL b[N], e[N];

        inline LL getmax(LL *a) {
            LL b[9] = {}, ans = 0, j = 1, k = 1;
            b[a[1]] = 1;
            for(LL i=2;i<=4;++i) {
                k = max(k, a[i]);
                ans = (ans << 1) + (ans << 3) + (b[a[i]] ? b[a[i]] : b[a[i]] = ++j);
            }
            return ans;
        }

        LL getans(LL *a,LL n,LL c) {
            LL j = 0;
            for(LL i=1;i<=n;++i) {
                if(a[i] > j + 1) return 0;
                j = max(j, a[i]);
            }
            LL ans = 1;
            for(LL i=0;i<j;++i) (ans *= (c-i)) %= mod;
            return ans;
        }

        inline LL find(LL C,LL K,LL H) {
            for(LL i=0;i<9;++i) a[i] = 1;
            for(; a[0] < 2; ) {
                LL j = getmax(a);
                b[j] = max(b[j], getans(a,4,C));
                LL i;
                for(i=4;a[i] == i;--i) a[i] = 1; a[i] ++;
            }
            LL n = 0;
            memset(c,0,sizeof c);
            for(LL i=1;i<=1000;++i) {
                if(b[i]) {
                    c[i] = ++n;
                    e[n] = b[i];
                }
            }
            m = (K+1)*n+1;
            for(LL i=0;i<9;++i) a[i] = 1;
            memset(ini.a,0,sizeof ini.a);
            memset(dp.a,0,sizeof dp.a);
            for(;a[0]<2;) {
                LL j = c[getmax(a)], k = c[getmax(a+4)];
                if(j && k) {
                    LL o = getans(a,8,C)*::pow(e[j],mod-2) % mod;
                    LL y=j+( (a[1]==a[2])+ (a[1]==a[3]) + (a[4]==a[2]) + (a[4]==a[3]))*n;
                    if(y < m) ini.a[1][y]=e[j];
                    LL sum = (a[5]==a[6]) + (a[5]==a[7]) + (a[8]==a[6]) + (a[8]==a[7]);
                    for(LL i = 1;i < 5; i++) sum += (a[i] == a[i+4]);
                    for(LL z = 0;z <= K - sum;z++)( dp.a[j+z*n][k+(z+sum)*n]+=o)%=mod;
                }
                LL i = 8;
                for(i=8;a[i]==i;--i) a[i] = 1;
                a[i] ++;
            }   
            for(LL i=1;i<=m;++i) dp.a[i][m] = 1;
            ini = ini * pow(dp,H);
            return ini.a[1][m];
        }
 
    
// BEGIN CUT HERE
    public:
    void run_test(LL 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(); }
    private:
    template <typename T> string prLL_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(LL Case, const LL &Expected, const LL &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() { LL Arg0 = 2; LL Arg1 = 0; long long Arg2 = 2LL; LL Arg3 = 4; verify_case(0, Arg3, find(Arg0, Arg1, Arg2)); }
    void test_case_1() { LL Arg0 = 1; LL Arg1 = 7; long long Arg2 = 19LL; LL Arg3 = 1; verify_case(1, Arg3, find(Arg0, Arg1, Arg2)); }
    void test_case_2() { LL Arg0 = 2; LL Arg1 = 3; long long Arg2 = 1LL; LL Arg3 = 14; verify_case(2, Arg3, find(Arg0, Arg1, Arg2)); }
    void test_case_3() { LL Arg0 = 4; LL Arg1 = 7; long long Arg2 = 47LL; LL Arg3 = 1008981254; verify_case(3, Arg3, find(Arg0, Arg1, Arg2)); }

// END CUT HERE

}t;
// BEGIN CUT HERE
int main(){
    cout << t.find( 446, 2, 207964594444828076);
    TheBrickTowerHardDivOne ___test;
    ___test.run_test(-1);
    return 0;
}
// END CUT HERE

Title - Artist
0:00

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

TOP