头像

monoid




离线:13小时前


活动打卡代码 AcWing 1083. Windy数

monoid
17小时前
/*
    author: solene
    created: 2020/10/28 9:20:19
*/

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define PII pair<int, int>

const int MAXN = 12;
int A, B;
int dp[10][MAXN];

void preprocess(){
    memset(dp, 0, sizeof dp);
    for(int i = 0; i <= 9; i ++) dp[i][1] = dp[i][0] = 1;
    for(int j = 2; j < MAXN; j ++)
        for(int i = 0; i <= 9; i ++){
            // dp[i][j].
            for(int k = 0; k <= i - 2; k ++)
                dp[i][j] += dp[k][j - 1];
            for(int k = i + 2; k <= 9; k ++)
                dp[i][j] += dp[k][j - 1];
        }
    return;
}

int solve(int upper){
    if(upper == 0) return 1;
    vector<int> digits;
    while(upper){
        digits.push_back(upper % 10);
        upper /= 10;
    }
    reverse(digits.begin(), digits.end());
    int rnt = 1;
    for(int j = 1; j < digits.size(); j ++)
        for(int i = 1; i <= 9; i ++)
            rnt += dp[i][j];
    int j;
    for(j = 0; j < digits.size(); j ++){
        for(int i = (j ? 0 : 1); i < digits[j]; i ++){
            if(j && abs(digits[j - 1] - i) <= 1) continue;
            rnt += dp[i][digits.size() - j];
        }
        if(j && abs(digits[j] - digits[j - 1]) <= 1) break;
    }
    if(j == digits.size()) rnt ++;
    return rnt;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> A >> B;
    preprocess();
    cout<<solve(B) - solve(A - 1)<<endl;
    return 0;
}



活动打卡代码 AcWing 1084. 数字游戏 II

monoid
1天前
/*
    author: solene
    created: 2020/10/27 10:57:06
*/

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define PII pair<int, int>

const int MAXN = 101;
int a, b, N;
int dp[MAXN][11];

void preprocess(){
    memset(dp, 0, sizeof dp);
    dp[0][0] = 1;
    for(int i = 1; i <= 10; i ++)
        for(int j = 0; j < N; j ++){
            //dp[j][i].
            for(int k = 0; k <= 9; k ++)
                dp[j][i] += dp[((j - k) % N + N) % N][i - 1];
        }
    return;
}

int solve(int upper){
    if(upper == 0) return 1;
    vector<int> digits;
    while(upper){
        digits.push_back(upper % 10);
        upper /= 10;
    }
    reverse(digits.begin(), digits.end());
    int rnt = 1;
    for(int i = 1; i < (int) digits.size(); i ++)
        for(int j = 1; j <= 9; j ++)
            rnt += dp[((N - j) % N + N) % N][i - 1];
    int i, sum = digits[0];
    // 1 ~ digits[0] - 1.
    for(int j = 1; j <= (int) digits[0] - 1; j ++) rnt += dp[((N - j) % N + N) % N][digits.size() - 1];
    for(i = 1; i < (int) digits.size(); i ++){
        // 0 ~ digits[i] - 1.
        for(int j = 0; j <= (int) digits[i] - 1; j ++)
            rnt += dp[((N - sum - j) % N + N) % N][digits.size() - i - 1];
        sum += digits[i];
    }
    if(i == digits.size() && sum % N == 0) rnt ++;
    return rnt;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    while(cin >> a >> b >> N){
        preprocess();
        cout<<solve(b) - solve(a - 1)<<endl;
    }
    return 0;
}



活动打卡代码 AcWing 1082. 数字游戏

monoid
1天前
/*
    author: solene
    created: 2020/10/26 20:05:22
*/

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define PII pair<int, int>

const int MAXN = 11;
int a, b;
int dp[11][MAXN];

void preprocess(){
    memset(dp, 0, sizeof dp);
    for(int i = 1; i < MAXN; i ++) dp[1][i] = 1;
    for(int i = 1; i <= 10; i ++) dp[i][1] = i;
    for(int i = 0; i <= 10; i ++) dp[i][0] = 1; 
    for(int i = 2; i <= 10; i ++){
        for(int j = 2; j < MAXN; j ++){
            // dp[i][j].
            dp[i][j] = 0;
            for(int k = 1; k <= i; k ++)
                for(int l = 1; l <= j; l ++)
                    dp[i][j] += dp[i - k][j - l];
        }
    }
    return;
}

int solve(int upper){
    vector<int> digits;
    while(upper){
        digits.push_back(upper % 10);
        upper /= 10;
    }
    reverse(digits.begin(), digits.end());
    int rnt = 0;
    for(int i = 0; i < digits.size(); i ++) rnt += dp[9][i];
    int i;
    for(i = 0; i < digits.size(); i ++){
        if(i && digits[i] < digits[i - 1]) break;
        for(int j = (i ? digits[i - 1] : 1); j < digits[i]; j ++)
            rnt += dp[10 - j][digits.size() - 1 - i];
    }
    if(i == digits.size()) rnt ++;
    return rnt;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    preprocess();
    while(cin >> a >> b) cout<<solve(b) - solve(a - 1)<<endl;
    return 0;
}



活动打卡代码 AcWing 479. 加分二叉树

monoid
2天前
/*
    author: solene
    created: 2020/10/26 19:34:01
*/

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define PII pair<int, int>

const int MAXN = 31;
int n;
int a[MAXN];
int dp[MAXN][MAXN];
vector<int> dp_ops[MAXN][MAXN];

bool isSmaller(vector<int>& a, vector<int>& b){
    if(b.size() == 0) return true;
    for(int i = 0; i < a.size(); i ++){
        if(a[i] < b[i]) return true;
        else if(a[i] > b[i]) return false;
    }
    return false;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];
    memset(dp, 0, sizeof dp);
    for(int i = 0; i < n; i ++){
        dp[i][i] = a[i];
        dp_ops[i][i] = {i + 1};
    }
    for(int w = 1; w < n; w ++){
        for(int i = 0; i + w < n; i ++){
            // dp[i][i + w].
            dp[i][i + w] = 0;
            for(int j = i, t; j <= i + w; j ++){
                if(j == i) t = dp[j + 1][i + w] + a[j];
                else if(j < i + w) t = dp[i][j - 1] * dp[j + 1][i + w] + a[j];
                else t = dp[i][j - 1] + a[j];
                if(t >= dp[i][i + w]){
                    vector<int> ops = {j + 1};
                    if(j > i){
                        for(auto& v: dp_ops[i][j - 1])
                            ops.push_back(v);
                    }
                    if(j < i + w){
                        for(auto& v: dp_ops[j + 1][i + w])
                            ops.push_back(v);
                    }
                    if(t > dp[i][i + w] || isSmaller(ops, dp_ops[i][i + w]))
                        dp_ops[i][i + w] = ops;
                    dp[i][i + w] = t;
                }
            }
        }
    }
    cout<<dp[0][n - 1]<<endl;
    for(auto& v: dp_ops[0][n - 1]) cout<<v<<" ";
    cout<<endl;
    return 0;
}



活动打卡代码 AcWing 1081. 度的数量

monoid
2天前
/*
    author: solene
    created: 2020/10/26 13:07:49
*/

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define PII pair<int, int>

LL X, Y, K, B;
vector<LL> nums;
unordered_map<LL, LL> dict;

LL solve(LL cur, LL left, LL upper){
    if(left == 1){
        while(upper >= 0 && nums[upper] > cur)
            upper --;
        return upper + 1;
    }
    else{
        LL rnt = 0;
        for(int i = upper; i >= 0; i --){
            if(nums[i] > cur) continue;
            rnt += solve(cur - nums[i], left - 1, i - 1);
        }
        return rnt;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> X >> Y >> K >> B;
    LL t = 1;
    while(t < Y){
        nums.push_back(t);
        t *= B;
    }
    cout<<solve(Y, K, nums.size() - 1) - solve(X - 1, K, nums.size() - 1)<<endl;
    return 0;
}



活动打卡代码 AcWing 1107. 魔板

monoid
2天前
/*
    author: solene
    created: 2020/10/26 11:11:54
*/

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define PII pair<int, int>

string tgt = "", src = "12348765";

string opA(string inp){
    reverse(inp.begin(), inp.end());
    reverse(inp.begin(), inp.begin() + 4);
    reverse(inp.begin() + 4, inp.end());
    return inp;
}

string opB(string inp){
    char c3 = inp[3], c7 = inp[7];
    for(int i = inp.size() - 1; i >= 1; i --)
        inp[i] = inp[i - 1];
    inp[0] = c3;
    inp[4] = c7;
    return inp;
}

string opC(string inp){
    char t = inp[1];
    inp[1] = inp[5];
    inp[5] = inp[6];
    inp[6] = inp[2];
    inp[2] = t;
    return inp;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    for(int i = 0; i < 8; i ++){
        int t;
        cin >> t;
        tgt += char(int('0') + t);
    }
    reverse(tgt.begin() + 4, tgt.end());
    unordered_set<string> done;
    done.insert(src);
    queue<pair<string, string>> que;
    que.push(make_pair(src, ""));
    int rnt = INT_MAX;
    string rnt_ops;
    while(!que.empty()){
        auto cur = que.front();
        que.pop();
        if(cur.second.size() > rnt) break;
        if(cur.first == tgt){
            if(cur.second.size() < rnt || cur.second < rnt_ops){
                rnt = cur.second.size();
                rnt_ops = cur.second;
            }
        }
        // A.
        string t = opA(cur.first);
        if(!done.count(t)){
            done.insert(t);
            que.push(make_pair(t, cur.second + 'A'));
        }
        // B.
        t = opB(cur.first);
        if(!done.count(t)){
            done.insert(t);
            que.push(make_pair(t, cur.second + 'B'));
        }
        // C.
        t = opC(cur.first);
        if(!done.count(t)){
            done.insert(t);
            que.push(make_pair(t, cur.second + 'C'));
        }
    }
    cout<<rnt<<endl;
    if(rnt) cout<<rnt_ops<<endl;
    return 0;
}



活动打卡代码 AcWing 1073. 树的中心

monoid
2天前
/*
    author: solene
    created: 2020/10/25 18:52:17
*/

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define PII pair<int, int>

const int MAXN = 10010;
int n;
int dp[MAXN];
unordered_map<int, int> dict[MAXN];
vector<PII> outEdges[MAXN];

int dfs1(int root, int par){
    dict[root].clear();
    int rnt = 0;
    for(auto& p: outEdges[root]){
        if(p.first == par) continue;
        dict[root][p.first] = dfs1(p.first, root) + p.second;
        rnt = max(rnt, dict[root][p.first]);
    }
    return rnt;
}

void dfs2(int root, int par, int dist){
    int maxv1 = -1, maxv2 = -1;
    for(auto& p: dict[root]){
        if(p.second >= maxv1){
            maxv2 = maxv1;
            maxv1 = p.second;
        }
        else
            maxv2 = max(maxv2, p.second);
    }
    dp[root] = max(dist, maxv1);
    for(auto& p: outEdges[root]){
        if(p.first == par) continue;
        int t = max(dist, dict[root][p.first] == maxv1 ? maxv2: maxv1) + p.second;
        dfs2(p.first, root, t);
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin >> n;
    for(int i = 0; i < n - 1; i ++){
        int a, b, c;
        cin >> a >> b >> c;
        outEdges[a].push_back(make_pair(b, c));
        outEdges[b].push_back(make_pair(a, c));
    }
    dfs1(1, -1);
    dfs2(1, -1, 0);
    int rnt = INT_MAX;
    for(int i = 1; i <= n; i ++) rnt = min(rnt, dp[i]);
    cout<<rnt<<endl;
    return 0;
}



活动打卡代码 AcWing 327. 玉米田

monoid
5天前
/*
    author: solene
    created: 2020/10/23 15:05:40
*/

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define PII pair<int, int>

const int MAXN = 12;
const int MOD = 100000000;
int M, N;
int mat[MAXN];

int main(){
    ios_base::sync_with_stdio(false);
    cin >> M >> N;
    for(int i = 0; i < M; i ++){
        int t = 0, a;
        for(int j = 0; j < N; j ++){
            cin >> a;
            t = t * 2 + (1 - a);
        }
        mat[i] = t;
    }
    unordered_map<int, LL> dp;
    dp[0] = 1;
    for(int i = 0; i < M; i ++){
        unordered_map<int, LL> tmp;
        for(int k = 0; k < (1 << N); k ++){
            bool valid = !(k & mat[i]);
            for(int j = 0; j < N - 1 && valid; j ++){
                if((k & (1 << j)) && (k & (1 << (j + 1))))
                    valid = false;
            }
            if(!valid) continue;
            for(auto& p: dp){
                if(k & p.first) continue;
                tmp[k] = (tmp[k] + p.second) % MOD;
            }
        }
        dp = move(tmp);
    }
    LL rnt = 0;
    for(auto& p: dp) rnt = (rnt + p.second) % MOD;
    cout<<rnt<<endl;
    return 0;
}



活动打卡代码 AcWing 320. 能量项链

monoid
5天前
/*
    author: solene
    created: 2020/10/23 14:42:54
*/

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define PII pair<int, int>

const int MAXN = 110;
int N;
LL a[MAXN], dp[MAXN][MAXN];

LL solve(){
    a[N] = a[0];
    for(int i = 0; i < N; i ++) dp[i][i] = 0;
    for(int w = 1; w < N; w ++){
        for(int i = 0; i + w < N; i ++){
            // dp[i][i + w].
            dp[i][i + w] = 0;
            for(int j = i; j < i + w; j ++){
                // dp[i][i + w] = dp[i][j] + dp[j + 1][i + w] + 
                dp[i][i + w] = max(dp[i][i + w], dp[i][j] + dp[j + 1][i + w] + a[i] * a[j + 1] * a[i + w + 1]);
            }
        }
    }
    return dp[0][N - 1];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin >> N;
    for(int i = 0; i < N; i ++) cin >> a[i];
    LL rnt = 0;
    for(int i = 0; i < N; i ++){
        reverse(a, a + N);
        reverse(a + 1, a + N);
        rnt = max<LL>(rnt, solve());
    }
    cout<<rnt<<endl;
    return 0;
}



活动打卡代码 AcWing 1091. 理想的正方形

monoid
5天前
/*
    author: solene
    created: 2020/10/23 10:33:40
*/

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define PII pair<int, int>

const int MAXN = 1010;
int mat[MAXN][MAXN];
int minv[MAXN][MAXN], maxv[MAXN][MAXN];
int a, b, n;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> a >> b >> n;
    for(int r = 0; r < a; r ++)
        for(int c = 0; c < b; c ++)
            cin >> mat[r][c];
    for(int c = 0; c < b; c ++){
        deque<PII> dq_max, dq_min;
        for(int r = 0; r < a; r ++){
            while(!dq_max.empty() && dq_max.front().second <= r - n)
                dq_max.pop_front();
            while(!dq_max.empty() && dq_max.back().first <= mat[r][c])
                dq_max.pop_back();
            dq_max.push_back(make_pair(mat[r][c], r));

            while(!dq_min.empty() && dq_min.front().second <= r - n)
                dq_min.pop_front();
            while(!dq_min.empty() && dq_min.back().first >= mat[r][c])
                dq_min.pop_back();
            dq_min.push_back(make_pair(mat[r][c], r));

            maxv[r][c] = dq_max.front().first;
            minv[r][c] = dq_min.front().first;
        }
    }
    int rnt = INT_MAX;
    for(int r = n - 1; r < a; r ++){
        deque<PII> dq_max, dq_min;
        for(int c = 0; c < b; c ++){
            while(!dq_max.empty() && dq_max.front().second <= c - n)
                dq_max.pop_front();
            while(!dq_max.empty() && dq_max.back().first <= maxv[r][c])
                dq_max.pop_back();
            dq_max.push_back(make_pair(maxv[r][c], c));

            while(!dq_min.empty() && dq_min.front().second <= c - n)
                dq_min.pop_front();
            while(!dq_min.empty() && dq_min.back().first >= minv[r][c])
                dq_min.pop_back();
            dq_min.push_back(make_pair(minv[r][c], c));

            if(c >= n - 1)
                rnt = min(rnt, dq_max.front().first - dq_min.front().first);
        }
    }
    cout<<rnt<<endl;
    return 0;
}