A simple Blog for wyx I've been down the bottle hoping.
topcoder 网络流 数学 dp 计数 乱搞 大力练习
发表于: | 分类: Oi | 评论:0 | 阅读:82

SRM 556 Div1 500pts

给你一坨纸牌,每次从中取出一张之后要么放在已经构成的块的最左边,要么放在已经构成的块的最右边,然后给你一个数字$x$,问你用刚才的方式能凑出来的大于他的最小值什么

显然dp

我们可以把这坨牌倒过来然后要么是对于一张要么放在最前面要么是放在最后面

原因是倒过来之后顺序刚好相互不影响 ,然后直接dp就行了 我比较蠢写了一个$n^4$的,大概如果用队爷的方法可以做到$n^3$

不管了一个tc管什么复杂度,多项式算法就好了QwQ

一个细节是如果放在前面而且当前位比$x$位大我们就大力贪心从高到低剩下的位数就行了

#include <bits/stdc++.h>
using namespace std ;
const int N = 50+5;

string F[N][N][N][2], a, b, as[N];

string calc(int n) {
    if(as[n] != "!!") return as[n];
    if(!n) return as[n] = a[0];
    string temp1, temp2;
    temp1 = temp2 = a[n];
    temp1 = calc(n-1) + temp1;
    temp2 = temp2 + calc(n-1);
    return as[n] = min(temp1, temp2);
}

string solve(int n,int l,int r,int c) {
    char s = a[n];
    string &ans = F[n][l][r][c];
    if(ans != "!!") return ans;
    if(n == 0) {
        if(c && a[n] > b[l]) return ans = s;
        if(!c && s >= b[l]) return ans = s;
        return ans = "";
    }
    string temp1, temp2;
    temp2 = s;
    int tt = c;
    if(s < b[r]) tt = 1;
    else if(s > b[r]) tt = 0;
    temp1 = solve(n-1,l,r-1,tt);
    temp1.push_back(s);
    if(s == b[l]) temp2 = temp2 + solve(n-1,l+1,r,c);
    else if(s > b[l]) temp2 = temp2 + calc(n-1);
    if(temp1.size() == 1) temp1 = "";
    if(temp2.size() == 1) temp2 = "";
    if(temp1 == "")  return ans = temp2;
    if(temp2 == "")  return ans = temp1;
    return ans = min(temp1,temp2);
}

class LeftRightDigitsGame2
{
    public:
    string minNumber(string digits, string lowerBound)
    {
        a = digits, b = lowerBound ;
        int N = 50+5;
        for(int i=0;i<N;++i) 
            for(int j=0;j<N;++j) 
                for(int k=0;k<N;++k) 
                    F[i][j][k][0] = F[i][j][k][1] = "!!";
        for(int i=0;i<N;++i) as[i] = "!!";
        return solve(a.size()-1,0,a.size()-1,0);
    }
 
    
// 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(); }
    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 string &Expected, const string &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() { string Arg0 = "565"; string Arg1 = "556"; string Arg2 = "556"; verify_case(0, Arg2, minNumber(Arg0, Arg1)); }
    void test_case_1() { string Arg0 = "565"; string Arg1 = "566"; string Arg2 = "655"; verify_case(1, Arg2, minNumber(Arg0, Arg1)); }
    void test_case_2() { string Arg0 = "565"; string Arg1 = "656"; string Arg2 = ""; verify_case(2, Arg2, minNumber(Arg0, Arg1)); }
    void test_case_3() { string Arg0 = "9876543210"; string Arg1 = "5565565565"; string Arg2 = "5678943210"; verify_case(3, Arg2, minNumber(Arg0, Arg1)); }
    void test_case_4() { string Arg0 = "8016352"; string Arg1 = "1000000"; string Arg2 = "1086352"; verify_case(4, Arg2, minNumber(Arg0, Arg1)); }

// END CUT HERE

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

SRM 557 Div1 1000

题目大意

给你一个序列${a}$,你可以任意次数的选择两个数字$a_i,a_j$,把其中一个变成$a_i\ xor a_j$,这个操作不限次数,最后求
$\sum{a_i}$的最大值

和宋爷YY了一通YY出了正解

考虑大力构建线性基然后贪心,我们先建出线性基,然后把他像高斯消元一样倒过来消一次,注意到没参与线性基构建的数字必然可以变成线性基里面一坨数的异或,线性基里面的数字就是把自己那位去掉的权值咯……注意最大的仍然可以保持自己的权值……

算了这玩意说不明白还是看代码吧……代码比较好懂

#include <bits/stdc++.h>
using namespace std ;
const int N = 50 + 5;
long long a[N], b[N];
class XorAndSum
{
    public:
    long long maxSum(vector<long long> number)
    {
        int n = number.size();
        for(int i=0;i<n;++i) a[i+1] = number[i];
        for(int i=1;i<=n;++i) {
            for(int j=50;~j;--j) {
                if((1ll<<j)&a[i]) {
                    if(!b[j]) {
                        b[j] = a[i];
                        break;
                    }
                    else a[i] ^= b[j];
                }
            }
        }
        for(int i=0;i<=50;++i) if(b[i]){
            for(int j=i+1;j<=50;++j) {
                if((1ll<<i)&b[j]) {
                    b[j] ^= b[i];
                }
            }
        }
        int temp = n;
        long long Max = 0, ans = 0;
        for(int i=0;i<=50;++i) 
            if(b[i]) {
                temp --;
                Max ^= b[i];
            }
        ans = Max * temp;
        bool tt = true;
        for(int i=50;~i;--i) {
            if(b[i]) {
                if(tt) {
                    ans = ans + Max;
                    tt = false;
                }
                else 
                    ans = ans + (Max ^ b[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(); 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() { long Arr0[] = {1,0}; vector<long long> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); long long Arg1 = 2LL; verify_case(0, Arg1, maxSum(Arg0)); }
    void test_case_1() { long Arr0[] = {1,2,3}; vector<long long> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); long long Arg1 = 8LL; verify_case(1, Arg1, maxSum(Arg0)); }
    void test_case_2() { long Arr0[] = {0,0,0,0,0,0,0,0,0,0}; vector<long long> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); long long Arg1 = 0LL; verify_case(2, Arg1, maxSum(Arg0)); }
    void test_case_3() { long Arr0[] = {2,3,5,7,11,13,17,19}; vector<long long> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); long long Arg1 = 233LL; verify_case(3, Arg1, maxSum(Arg0)); }
//  void test_case_4() { long Arr0[] = {123456789012345, 0, 0, 0, 0, 0, 0, 0, 0, 0}; vector<long long> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); long long Arg1 = 1234567890123450LL; verify_case(4, Arg1, maxSum(Arg0)); }
    void test_case_5() { long Arr0[] = {627,674,281,272,289,877,62,122,603,189,615}; vector<long long> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); long long Arg1 = 10742LL; verify_case(5, Arg1, maxSum(Arg0)); }
    void test_case_6() { long Arr0[] = {557}; vector<long long> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); long long Arg1 = 557LL; verify_case(6, Arg1, maxSum(Arg0)); }

// END CUT HERE

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

SRM 558 1000 pts

题目大意

给定棋盘,定义一个点被占有当且仅当自己被选择或者周围四个点都被选择,选择一个点需要一个代价,占有一个点会有一个好处,定义利益为好处-代价,求利益的最大值

限制这么强显然是网络流模型,容易想到文理分科

我们考虑这样一种建图,考虑把这个棋盘黑白染色之后进行建图,把每个黑点或者白点黑白染色,然后对于每个点拆点,对于一个黑点我们建立二元组$(x_1,x_2)$,$S \to x_1$,流量是花费,$x_1 \to x_2$流量是好处,然后对于一个白点我们也拆点$(y_1,y_2)$,$y_1 \to t$ 流量是花费,$y_2 \to y_1$ 流量是好处,然后$x_2 \to y_1$, $x_1\to y_2$即可

注意到一个好处被切掉当且仅当自己的cost被干死或者所有相连的点的cost被干死,最后用总的收益减去最小割即可


#include <bits/stdc++.h>
using namespace std ;
const int inf = 0x3f3f3f3f;
const int N = 1000+5;
const int M = N * N;
int head[N];

struct graph {
    int next, to, val;
    graph () {}
    graph (int _next,int _to,int _val)
    :next(_next), to(_to), val(_val) {}
}edge[M];

inline void add(int x,int y,int z) {
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y, z); head[x] = cnt;
    edge[++cnt] = graph(head[y], x, 0); head[y] = cnt;
}

int depth[N], s, t;

bool BFS() {
    queue <int> q;
    memset(depth, -1, sizeof depth);
    depth[s] = 0; q.push(s); 
    while(!q.empty()) {
        int tt = q.front(); q.pop();
        for(int i=head[tt];i;i=edge[i].next) {
            if(depth[edge[i].to] < 0 && edge[i].val) {
                depth[edge[i].to] = depth[tt] + 1;
                q.push(edge[i].to); 
            }
        }
    }
    return ~depth[t];
}

inline int DFS(int x,int f) {
    if(x == t) return f;
    int used = 0, w;
    for(int i=head[x];i;i=edge[i].next) {
        if(depth[edge[i].to] == depth[x] + 1 && edge[i].val) {
            w = DFS(edge[i].to, min(edge[i].val, f - used));
            edge[i].val -= w, edge[i^1].val += w;
            used += w;
            if(used == f) return used;
        }
    }
    depth[x] = -1;
    return used;
}

inline int max_flow() {
    int ans = 0;
    while(BFS()) 
        ans += DFS(s,inf);
    return ans;
}
const int Max = 20+1;
int a[Max][Max], b[Max][Max], table[Max][Max][2];
int n, m;

#define in(x,a,b) ((x) >= (a) && (x) <= (b))
const int dx [] = {-1,1,0,0};
const int dy [] = {0,0,1,-1};

class SurroundingGame
{
    public:
    int maxScore(vector <string> cost, vector <string> benefit)
    {
        n = cost.size();
        for(int i=0;i<n;++i) {
            m = cost[i].size();
            for(int j=0;j<m;++j) {
                int &temp = a[i+1][j+1];
                if(isdigit(cost[i][j])) temp = cost[i][j] - '0';
                else if(cost[i][j] >= 'a' && cost[i][j] <= 'z') temp = cost[i][j] - 'a' + 10;
                else temp = cost[i][j] - 'A' + 36;
            }
        }
        for(int i=0;i<n;++i) {
            string tt = benefit[i];
            for(int j=0;j<m;++j) {
                int &temp = b[i+1][j+1];
                if(isdigit(benefit[i][j])) temp = benefit[i][j] - '0';
                else if(benefit[i][j] >= 'a' && benefit[i][j] <= 'z') temp = benefit[i][j] - 'a' + 10;
                else temp = benefit[i][j] - 'A' + 36;
            }
        }
        int cnt = 0;
        s = ++ cnt;
        t = ++ cnt;
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j) {table[i][j][0] = ++ cnt; table[i][j][1] = ++cnt;}
        for(int i=1;i<=n;++i) 
            for(int j=1;j<=m;++j) 
                if((i+j)&1)  {
                    add(s, table[i][j][0], a[i][j]);
                    add(table[i][j][0],table[i][j][1], b[i][j]);
                }
                else {
                    add(table[i][j][0], t, a[i][j]);
                    add(table[i][j][1], table[i][j][0], b[i][j]);
                }
        for(int i=1;i<=n;++i) {
            for(int j=1;j<=m;++j) if((i+j)&1) {
                for(int k=0;k<4;++k) {
                    int tx = i + dx[k], ty = j + dy[k];
                    if(in(tx,1,n) && in(ty,1,m)) {
                        add(table[i][j][0],table[tx][ty][1], inf);
                        add(table[i][j][1],table[tx][ty][0], inf);
                    }
                }
            }
        }
        int ans = 0;
        for(int i=1;i<=n;++i) {
            for(int j=1;j<=m;++j) {
                ans += b[i][j];
            }
        }
//          cout << ans << endl;
        return ans - max_flow();
    }
 
    
// 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(); }
    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 int &Expected, const int &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() { string Arr0[] = {"21","12"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = {"21","12"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 4; verify_case(0, Arg2, maxScore(Arg0, Arg1)); }
    void test_case_1() { string Arr0[] = {"ZZ","ZZ"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = {"11","11"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 0; verify_case(1, Arg2, maxScore(Arg0, Arg1)); }
    void test_case_2() { string Arr0[] = {"XXX","XXX","XXX"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = {"aaa","aZa","aaa"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 2; verify_case(2, Arg2, maxScore(Arg0, Arg1)); }
    void test_case_3() { string Arr0[] = {"asam","atik"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = {"123A","45BC"}; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 71; verify_case(3, Arg2, maxScore(Arg0, Arg1)); }
    void test_case_4() { string Arr0[] = {"IIIIIIII",
 "IIWWWWII",
 "IIWIIIII",
 "IIWIIIII",
 "IIWWWWII",
 "IIIIIWII",
 "IIIIIWII",
 "IIWWWWII",
 "IIIIIIII"}
; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arr1[] = {"IIIIIIII",
 "II0000II",
 "II0II0II",
 "II0II0II",
 "II0000II",
 "II0II0II",
 "II0II0II",
 "II0000II",
 "IIIIIIII"}
; vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 606; verify_case(4, Arg2, maxScore(Arg0, Arg1)); }

// END CUT HERE

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

SRM 559 Div1 250pts

我是傻逼

md世界上是不是只有我一个人上来就想写扫描线啊&

容易发现每个限制到最后都变成了一个矩形,我们要求一个矩形被覆盖了几次……但是这太难求了,于是我们利用扫描线算法,利用线段树统计即可,所以我们求出所有交点,注意到这东西被分的块数是常数级的,然后对于一个点可以代表整个块的情况直接$O(8)$验证被覆盖几次就好了


#include <bits/stdc++.h>
using namespace std ;
#define pb push_back
class HyperKnight
{
    public:
    long long countCells(int a, int b, int numRows, int numColumns, int k)
    {
        #define in(x,a,b) ((x)>=(a)&&(x)<=(b))
        const int d[8][2] = {{a,b},{-a,b},{a,-b},{-a,-b},{b,a},{b,-a},{-b,a},{-b,-a}};
        vector <long long> temp1, temp2; long long ans = 0;
        temp1.pb(a); temp1.pb(b); temp1.pb(numRows-a); temp1.pb(numRows-b); temp1.pb(0); temp1.pb(numRows);
        temp2.pb(a); temp2.pb(b); temp2.pb(numColumns-a); temp2.pb(numColumns-b); temp2.pb(0); temp2.pb(numColumns);
        sort(temp1.begin(), temp1.end()); sort(temp2.begin(), temp2.end());
        temp1.resize(unique(temp1.begin(), temp1.end()) - temp1.begin());
        temp2.resize(unique(temp2.begin(), temp2.end()) - temp2.begin());
        for(int i=0;i<temp1.size()-1;++i) {
            for(int j=0;j<temp2.size()-1;++j) {
                int x = temp1[i], y = temp2[j];
                int cnt = 0;
                for(int k=0;k<8;++k) {
                    int tx = x + d[k][0], ty = y + d[k][1];
                    if(in(tx,0,numRows-1) && in(ty,0,numColumns-1   )) cnt ++;
                }
                if(cnt == k) ans += (temp1[i+1]-temp1[i])*(temp2[j+1]-temp2[j]);
            }
        }
        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(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); }
    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 = 2; int Arg1 = 1; int Arg2 = 8; int Arg3 = 8; int Arg4 = 4; long long Arg5 = 20LL; verify_case(0, Arg5, countCells(Arg0, Arg1, Arg2, Arg3, Arg4)); }
    void test_case_1() { int Arg0 = 3; int Arg1 = 2; int Arg2 = 8; int Arg3 = 8; int Arg4 = 2; long long Arg5 = 16LL; verify_case(1, Arg5, countCells(Arg0, Arg1, Arg2, Arg3, Arg4)); }
    void test_case_2() { int Arg0 = 1; int Arg1 = 3; int Arg2 = 7; int Arg3 = 11; int Arg4 = 0; long long Arg5 = 0LL; verify_case(2, Arg5, countCells(Arg0, Arg1, Arg2, Arg3, Arg4)); }
    void test_case_3() { int Arg0 = 3; int Arg1 = 2; int Arg2 = 10; int Arg3 = 20; int Arg4 = 8; long long Arg5 = 56LL; verify_case(3, Arg5, countCells(Arg0, Arg1, Arg2, Arg3, Arg4)); }
    void test_case_4() { int Arg0 = 1; int Arg1 = 4; int Arg2 = 100; int Arg3 = 10; int Arg4 = 6; long long Arg5 = 564LL; verify_case(4, Arg5, countCells(Arg0, Arg1, Arg2, Arg3, Arg4)); }
    void test_case_5() { int Arg0 = 2; int Arg1 = 3; int Arg2 = 1000000000; int Arg3 = 1000000000; int Arg4 = 8; long long Arg5 = 999999988000000036LL; verify_case(5, Arg5, countCells(Arg0, Arg1, Arg2, Arg3, Arg4)); }

// END CUT HERE

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

SRM 559 Div1 500pts 树形dp

行行行我估计是废了

给定一个图,现在让你判断这个东西有多少种标号的方案使他是一个完全二叉树,注意完全二叉树不一定是满二叉树。

我最开始YY了一个及其麻烦而且难写的东西,过了20个test然后GG,原因是没考虑到左子树可能不满的情况

其实难点是如何判断一个点为根之后是否是完全二叉树,因为算方案数只需要看有多少个点的左右儿子size相等就行了,答案是2的这个次幂,可以用旋转子树来解释

现在就是判断是不是完全二叉树了。我开始搞了一坨和size和深度和度数相关的东西,然后GG【貌似myy找到了用深度做的正确姿势Orz

绝望之中我打开了wdz的代码……

啊……我是傻逼

考虑直接标号看最大标号是否$>n$即可……

注意到左儿子size要严格大于右面的,这样一定可以判断出来是否合法,原因是一旦左面少了一个,右面编号最大的比正常的-1+2然后刚好$>n$

#include <bits/stdc++.h>
using namespace std ;
const int N = 50 + 5;
const int M = N << 1;
int head[N], n;

struct graph {
    int next, to;
    graph () {}
    graph (int _next,int _to)
    :next(_next), to(_to) {}
}edge[M];

int deg[N];

inline void add(int x,int y) {
    static int cnt = 0;
    edge[++cnt] = graph(head[x], y); head[x] = cnt; deg[x] ++;
    edge[++cnt] = graph(head[y], x); head[y] = cnt; deg[y] ++;
}

int fa[N], Max[N], Min[N], depth[N], size[N], son[N][2];

inline void DFS(int x) {
    size[x] = 1;
    for(int i = head[x]; i; i = edge[i].next) {
        if(edge[i].to != fa[x]) {
            fa[edge[i].to] = x;
            DFS(edge[i].to);
            size[x] += size[edge[i].to];
        }
    }
}

int id[N];

inline bool DFS2(int x) {
    bool temp = true;
    for(int j=0;j<2;++j) {
        if(son[x][j]) {
            if((id[son[x][j]] = id[x]<<1|j)>n) return false;
            temp &= DFS2(son[x][j]);
        }
    }
    return temp;
}

class HatRack
{
    public:
    long long countWays(vector <int> knob1, vector <int> knob2)
    {
        for(int i=0;i<knob1.size();++i) add(knob1[i], knob2[i]);
        n = knob1.size() + 1;
        if(n == 1) return 1;
        else if(n == 2) return 2;
        long long ret = 0;
        for(int i=1;i<=n;++i) {
            if(deg[i] == 2) {
                memset(fa, 0, sizeof fa);
                memset(id, 0, sizeof id);
                memset(son, 0, sizeof son);
                DFS(i);
                bool flag = true;
                int ans = 0;
                for(int j=1;j<=n;++j) {
                    int cnt = 0;
                    for(int k = head[j]; k; k = edge[k].next) {if(edge[k].to != fa[j]) cnt ++;}
                    if(cnt > 2) {flag = false; break;}
                    cnt = 0;
                    for(int k = head[j]; k; k = edge[k].next) {if(edge[k].to != fa[j]) son[j][cnt++] =  edge[k].to;}
                    int k = j;
                    if(cnt == 2 && size[son[k][0]] < size[son[k][1]]) swap(son[k][0], son[k][1]);
                    if(size[son[k][0]] == size[son[k][1]] && son[k][0]) ans ++;
                }
                id[i] = 1;
                if(!DFS2(i)) flag = false;
                if(!flag) continue;
                ret += (1ll<<ans);
            }
        }
        return ret;
    }
 
    
// 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(); }
    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 Arr0[] = {1}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {2}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); long long Arg2 = 2LL; verify_case(0, Arg2, countWays(Arg0, Arg1)); }
    void test_case_1() { int Arr0[] = {1,1}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {2,3}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); long long Arg2 = 2LL; verify_case(1, Arg2, countWays(Arg0, Arg1)); }
    void test_case_2() { int Arr0[] = {1,1,1,1}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {2,3,4,5}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); long long Arg2 = 0LL; verify_case(2, Arg2, countWays(Arg0, Arg1)); }
    void test_case_3() { int Arr0[] = {6,6,6,4,1}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1,2,4,5,3}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); long long Arg2 = 0LL; verify_case(3, Arg2, countWays(Arg0, Arg1)); }
    void test_case_4() { int Arr0[] = {1,1,2,2,11,11,8,8,3,3,4,4,5}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {2,3,11,8,12,13,9,10,4,5,7,6,14}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); long long Arg2 = 16LL; verify_case(4, Arg2, countWays(Arg0, Arg1)); }
    void test_case_5() { int Arr0[] = {1,2,3,4,5,6,7,8,9}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {2,3,4,5,6,7,8,9,10}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); long long Arg2 = 0LL; verify_case(5, Arg2, countWays(Arg0, Arg1)); }

// END CUT HERE

}temp;
// BEGIN CUT HERE
int main(){
//  cout << temp.countWays({2, 1, 3}, {4, 4, 2}) << endl;
    
    HatRack ___test;
    ___test.run_test(3);
    return 0;
}
// END CUT HERE

SRM 562 500pts

题目大意:给你一坨点,有黑白两种颜色,问你是否存在一个凸四边形,满足一组对点是黑色,一组对点是白色

这题我写的不是正解qwq,但是能过

先说正解,正解就是枚举一个点,然后枚举他的对点,再枚举一个白点,注意到因为到极角有序,另外一个白点直接双指针和左面那个就一起扫完了复杂度是$n^3$的

再说我写的做法,比较有趣,注意到一个四边形为凸四边形对角线必然相交,那么如果你直接枚举四个点的话就是$n^4$的,考虑优化这个算法

考虑我们已经枚举了一个黑点和两个白点,如图所示,那么显然另外一个点只能在所示的红色部分
黑白点

那么我们令$F(i,j,k)$表示角ijk是否是一个>180的角,这里认为角ijk+角kji=360

然后就可以通过顶上的黑点判断他是否在黑点形成的角内,通过右侧的一个白点判断是否在白点形成的直线下方

这个东西用bitset压一下.复杂度是$n^4/32$

#include <bitset>
#include <vector>
#include <string>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std ;
typedef long long LL;
const LL N = 255;
LL read(string str) {
    str += ' ';
    LL x = 0, t = 0; char ch = str[0];
    while(ch < '0' || ch > '9'){ch = str[++t];}
    while(ch >='0' && ch <='9'){
        x = x * 10 + ch - '0';
        ch = str[++t];
    }
    return x;
}

LL BX[N<<1], BY[N<<1], WX[N<<1], WY[N<<1];

struct poi {
    LL x, y;
    poi (LL _x = 0,LL _y = 0) :x(_x), y(_y) {} 
    poi operator + (const poi &z) const {return poi(x+z.x,y+z.y);}
    poi operator - (const poi &z) const {return poi(x-z.x,y-z.y);}
    long long operator * (const poi &z) const {return (LL)x * z.y - (LL)y * z.x;}
}p1[N<<1], p2[N<<1], p3[N<<1];

LL get(vector <string> x,LL *a) {
    LL n;
    string s = "";
    for(LL i=0;i<x.size();++i) s += x[i];
    LL i ;
    for(i = 0, n = 1; i < s.size(); n ++) {
        //cout << n << endl;
        while(i < s.size() && (s[i] < '0' || s[i] > '9')) ++i;
        if(i  == s.size())  {
        //  cout << n << endl;
            return n;
        }
        for(a[n] = 0; i < s.size() && s[i] >= '0' && s[i] <= '9'; ++ i) a[n] = a[n] * 10 + (s[i] - '0');
    }
    //cout << n << endl;
    return n-1;
}

bitset<256> F[N<<1][N<<1];
class CheckerFreeness
{

    public:
    string isFree(vector <string> whiteX, vector <string> whiteY, vector <string> blackX, vector <string> blackY)
    {
        LL n ,m;
        n = get(whiteX, WX);
        n = get(whiteY, WY);
        m = get(blackX, BX);
        m = get(blackY, BY);
        for(LL i=1;i<=n;++i) p3[i] = p1[i] = poi(WX[i], WY[i]);
        for(LL i=1;i<=m;++i) p3[i+n] = p2[i] = poi(BX[i], BY[i]);
        //cout << n << ' ' << m << endl;
        LL all = n + m;
        for(LL i=1;i<=n;++i) {
            for(LL j=i+1;j<=all;++j) {
                for(LL k=1;k<=m;++k) {
                    if(j == k + n) continue;
                    if((p1[i]-p2[k])*(p3[j]-p2[k]) > 0) F[i][j][k] = 1;
                    else F[j][i][k] = 1;
                }
            }
        }
        for(LL i=1;i<=n;++i) {
            for(LL j=i+1;j<=n;++j) {
                for(LL k=1;k<=m;++k) {
                    if(((F[i][k+n]^F[j][k+n])&(F[i][j][k] ? (~F[i][j]) : F[i][j])).any())
                        return "NO";
                }
            }
        }
        return "YES";
    }
 

}cls;
// BEGIN CUT HERE
int main(){
    cout << cls.isFree({"2", "5", "3", " ", "1", "7", "3"},{"180 254"},{"32", "5 1", "42"},{"462 423"}) << endl;
    return 0;   
}
// END CUT HERE

SRM 563 500pts

题目大意:给你一摞纸牌,每次要么把最上面的放到最下面,要么使用它得到$damage_i$并扔掉包括他在内的$level_i$张指派,注意如果牌不足$level$就用不了

挺有趣的一个题,首先考虑把它变成一个环,然后就没有了第一种操作

然后考虑其实我只要选出一组牌满足他们的level之和小于等于$n$,就一定存在方案把他们都用出去,至于为什么想鸽巢原理,n个东西放到小于n的距离的笼子里当然能放下,要不然就会存在每个位置都有东西覆盖显然总的覆盖是$>n$的了

然后就变成01背包了……


#include <bits/stdc++.h>
using namespace std ;
const int N = 50+5;
int F[N][N];
int v[N], c[N];

class SpellCards
{
    public:
    int maxDamage(vector <int> level, vector <int> damage)
    {
        int n = level.size();
        for(int i=1;i<=n;++i) v[i] = level[i-1];
        for(int i=1;i<=n;++i) c[i] = damage[i-1];
        for(int i=1;i<=n;++i) 
            for(int j=0;j<=n;++j) {
                F[i][j] = F[i-1][j];
                if(j >= v[i]) 
                    F[i][j] = max(F[i][j], F[i-1][j-v[i]]+c[i]);
            }
        int ans = 0;
        for(int i=1;i<=n;++i) ans = max(ans, F[n][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(); 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 int &Expected, const int &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 Arr0[] = {1,1,1}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {10,20,30}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 60; verify_case(0, Arg2, maxDamage(Arg0, Arg1)); }
    void test_case_1() { int Arr0[] = {3,3,3}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {10,20,30}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 30; verify_case(1, Arg2, maxDamage(Arg0, Arg1)); }
    void test_case_2() { int Arr0[] = {4,4,4}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {10,20,30}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 0; verify_case(2, Arg2, maxDamage(Arg0, Arg1)); }
    void test_case_3() { int Arr0[] = {50,1,50,1,50}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {10,20,30,40,50}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 60; verify_case(3, Arg2, maxDamage(Arg0, Arg1)); }
    void test_case_4() { int Arr0[] = {2,1,1}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {40,40,10}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 80; verify_case(4, Arg2, maxDamage(Arg0, Arg1)); }
    void test_case_5() { int Arr0[] = {1,2,1,1,3,2,1}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {10,40,10,10,90,40,10}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 170; verify_case(5, Arg2, maxDamage(Arg0, Arg1)); }
    void test_case_6() { int Arr0[] = {1,2,2,3,1,4,2}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {113,253,523,941,250,534,454}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 1918; verify_case(6, Arg2, maxDamage(Arg0, Arg1)); }

// END CUT HERE

};
// BEGIN CUT HERE
int main(){
    SpellCards ___test;
    ___test.run_test(5);
    return 0;
}
// END CUT HERE

SRM 563 950 pts

题目大意

一个$n\times m$的矩形棋盘,有一些格子被ban掉了,其余的每个格子你可以指定放或不放硬
币。
放完硬币后你可以做若干次操作,每次操作你可以指定一个方向(上下左右),使所有的硬币尝试向那个方向移动一格。如果一个硬币的目标格子被ban那么它不会移动。硬币可以被移出棋盘(然后就掉在外面回不来了)。一个格子上可以有多枚硬币。

求有多少种放硬币的方案,满足存在一种操作序列使至少有一枚硬币被移出棋盘、同时至少有一枚硬币留在棋盘上。

这题也挺厉害的……最开始容易没有思路

首先我们确立一个想法是用总的方案数减去所有不合法的方案数

我们定义一个点的状态是这个点是否在棋盘上然后定义两个点本质相同为两个点经过任意的操作之后他们的状态都相同

那么显然不合法就是所有的点都在本质相同的一组里面,这样的话是找不到方案的。

然后我们就可以get到一个比较优秀的算法,把棋盘标号,然后对于每个点能拓展到的点的标号拼成一个四元组,然后考虑这个四元组是否出现过,如果出现过那就直接在组内加上这个数字,否则的话给他一个新的标号并把这个位置设置成一个新的标号

注意到如果每次有新的标号出现说明出现了新的“可能”,那么就继续迭代,否则每次到达的标号都是相同的,我们就已经成功把点分组了

考虑这个算法是否会进入无限的迭代,答案是否定的,因为如果两个点$j$次操作后相同但是$i$次操作后不同$(i<j)$种类数会减少。最多只有$nm$所以最多迭代$nm$次

方案数注意不能是空集,注意模数是$10^9+9$……


#include <bits/stdc++.h>
using namespace std ;
const int N = 1600+5;
const int Max = 1600;
const int mod = 1e9+9;
typedef long long LL;
int pwn[N];
bool can[45][45];
int lab[45][45];
typedef pair<int,int> pi;
typedef pair<pi,pi> pii;
const int dx [] = {-1, 1, 0, 0};
const int dy [] = {0, 0, 1, -1};
map <pii, int> mp;

int cnt[N];
int newlab[45][45];

inline int calc(int x,int y,int k) {
    int tx = x + dx[k], ty = y + dy[k];
    if(can[tx][ty]) return lab[tx][ty];
    else return lab[x][y];
}

class CoinsGame
{
    public:
    int ways(vector <string> board)
    {
        memset(can ,true, sizeof can);
        pwn[0] = 1;
        for(int i=1;i<=Max;++i) pwn[i] = (LL)pwn[i-1] * 2 % mod;
        int w = board.size(), h = board[0].size();
        int all = 0;
        for(int i=1;i<=w;++i) {
            for(int j=1;j<=h;++j) {
                all += lab[i][j] = can[i][j] = board[i-1][j-1] == '.';
            }
        }
        int change, tot = 0;
        do {
            change = 0, tot = 0;
            mp.clear();
            for(int i=1;i<=w;++i) {
                for(int j=1;j<=h;++j) {
                    if(can[i][j]) {
                        pii temp = pii(pi(calc(i,j,0), calc(i,j,1)), pi(calc(i,j,2),calc(i,j,3)));
                        if(!mp.count(temp)) {
                            cnt[mp[temp] = ++tot] = 0;
                        }
                        ++cnt[newlab[i][j] = mp[temp]];
                    }
                }
            }
            for(int i=1;i<=w;++i) {
                for(int j=1;j<=h;++j) {
                    if(can[i][j] && newlab[i][j] != lab[i][j]) {
                        lab[i][j] = newlab[i][j];
                        change = 1;
                    }
                }
            }
        }while(change);
        int ans = pwn[all]-1;
        for(int i=1;i<=tot;++i) {
            ans = ans - (pwn[cnt[i]] - 1);
            ans %= mod;
            ans += mod;
            ans %= mod;
        }
        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(); if ((Case == -1) || (Case == 4)) test_case_4(); }
    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 int &Expected, const int &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() { string Arr0[] = {".."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 1; verify_case(0, Arg1, ways(Arg0)); }
    void test_case_1() { string Arr0[] = {"##.#",
 ".###",
 "###.",
 "#.##"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 11; verify_case(1, Arg1, ways(Arg0)); }
    void test_case_2() { string Arr0[] = {"####",
 "#..#",
 "#..#",
 "####"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; verify_case(2, Arg1, ways(Arg0)); }
    void test_case_3() { string Arr0[] = {"#.#.#"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; verify_case(3, Arg1, ways(Arg0)); }
    void test_case_4() { string Arr0[] = {"........",
 "........",
 "........",
 "........",
 "........",
 "........",
 "........",
 "........"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 688856388; verify_case(4, Arg1, ways(Arg0)); }

// END CUT HERE

};
// BEGIN CUT HERE
int main(){
    CoinsGame ___test;
    ___test.run_test(4);
    return 0;
}
// END CUT HERE

Title - Artist
0:00

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

TOP