头像

Nan97

$\color{red}{不开 long long 见祖宗}$




离线:4小时前


最近来访(144)
用户头像
LiyeeW
用户头像
潘潘_the_panda
用户头像
konkayy
用户头像
白之月
用户头像
消灭dp暴政世界属于记搜-东方风云榜第一-看题宰题虐题王冲鸭
用户头像
坞中客
用户头像
逆风微笑的小九岩
用户头像
心向远方
用户头像
直行格子
用户头像
rushhhhh
用户头像
xiusike1
用户头像
simonhan
用户头像
hnust_xiaoshun
用户头像
兔九哥
用户头像
whlbest
用户头像
凌乱之风
用户头像
艾特玖
用户头像
Jackyc
用户头像
D_deBUG
用户头像
NBxiang

活动打卡代码 AcWing 1064. 小国王

Nan97
4天前
#include <vector>
#include <iostream>

using namespace std;

typedef long long LL;

const int N = 12, M = 1 << 10, K = 110;

int n, m;
vector<int> state;
int cnt[M];
vector<int> head[M];
LL f[N][K][M];
bool check(int a) {
    for(int i = 0; i < n; i ++ ) 
        if(a >> i & 1 && a >> i + 1 & 1) 
            return false;
    return true;
}

int count(int a) {
    int res = 0;
    for(int i = 0; i < n; i ++ ) 
        if(a >> i & 1)
            res ++;
    return res;
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < 1 << n; i ++ ) 
        if(check(i)) {
            state.push_back(i);
            cnt[i] = count(i);
        }

    int len = state.size();
    for(int i = 0; i < len; i ++ )
        for(int j = 0; j < len; j ++ ) {
            int a = state[i], b = state[j];
            if((a & b) == 0 && check(a | b)) {
                head[i].push_back(j);
            }
        }

    f[0][0][0] = 1;
    /*
    f[i][j][k]表示前i行有了j个国王并且状态为k的方案数。
    f[i][j][k] 可以由 f[i - 1][j - c][head[k]] 转移。
    */
    for(int i = 1; i <= n + 1; i ++ )
        for(int j = 0; j <= m; j ++ )
            for(int a = 0; a < len; a ++ )
                for(auto b : head[a]) {
                    int c = cnt[state[a]];
                    if(j >= c)
                        f[i][j][a] += f[i - 1][j - c][b];
                }
    cout << f[n + 1][m][0];

    return 0;
}



活动打卡代码 AcWing 1052. 设计密码

Nan97
4天前
#include <iostream>
#include <cstring>
#include <algorithm>
#define mod(x) (x)%MOD
using namespace std;

const int N = 55, MOD = 1e9 + 7;

int n;
int f[N][N], ne[N];
string s; 

int main() {
    cin >> n >> s;
    int m = s.size();
    s = " " + s;
    for(int i = 2, j = 0; i <= m; i ++ ) {
        while(j && s[i] != s[j + 1]) j = ne[j];
        if(s[i] == s[j + 1]) j ++;
        ne[i] = j;
    }

    f[0][0] = 1;
    for(int i = 0; i < n; i ++ ) 
        for(int j = 0; j < m; j ++ ) 
            for(char k = 'a'; k <= 'z'; k ++ ) {
                int u = j;
                while(u && k != s[u + 1]) u = ne[u];
                if(k == s[u + 1]) u ++;
                if(u < m)
                    f[i + 1][u] = mod(f[i][j] + f[i + 1][u]);
            }
    int res = 0;
    for(int i = 0; i < m; i ++ ) 
        res = mod(res + f[n][i]);
    cout << res << endl;

}








活动打卡代码 LeetCode LCP 40. 心算挑战

Nan97
6天前
#define all(a) a.begin(), a.end()
class Solution {
public:
    int maxmiumScore(vector<int>& cards, int cnt) {
        vector<int> a, b;
        for(int x: cards) 
            if(x & 1) b.push_back(x);
            else a.push_back(x);
        sort(all(a)); reverse(all(a));
        sort(all(b)); reverse(all(b));
        int ans = 0; int i = 0, j = 0;
        if(cnt & 1) ans += a[i ++];
        cnt /= 2;
        for(int k = 0; k < cnt; i ++ ) {

            if(a[i] + a[i + 1] >= a[j] + a[j + 1]) {
                ans += a[i] + a[i + 1];
                i += 2;
            }
            else {
                ans += b[j] + b[j + 1];
                j += 2;
            }
        }

    }
};



Nan97
7天前

解法来自:心向远方


// 
const int N = 1 << 12;

class Solution {
public:
    int f[N] = {0};
    bool check(string p) {
        int len = p.size();
        for(int i = 0; i <= len - 1 - i; i ++ ) 
            if(p[i] != p[len - 1 - i]) return false;
        return true;
    }
    int maxProduct(string s) {
        int n = s.size(), ans = -0x3f3f3f3f;
        int px = 1 << n;
        for(int i = 0; i < px; i ++ ) {
            string res = "";
            for(int j = 0; j < n; j ++ ) 
                if(i >> j & 1) 
                    res.push_back(s[j]);
            if(check(res)) 
                f[i] = res.size();
        }
        for(int i = 0; i < px; i ++ ) 
            for(int j = i; j; j = (j - 1) & i) 
                ans = max(ans, f[j] * f[i - j]);

        return ans;
    }
};

@mrk

class Solution {
public:
    int n;
    int ans = 0;
    string p;
    bool inline judge(string x) {
        int len = x.size();
        for(int i = 0; i <= len - i - 1; i ++ )
            if(x[i] != x[len - i - 1]) return false;
        return true;
    }

    void dfs(int u, string a, string b) {
        if(u == n) {
            int res = (int)a.size() * (int)b.size();
            if(res <= ans) return;// 不加就TLE ...
            if(judge(a) && judge(b)) 
                ans = max(ans, res);
            return;
        }
        dfs(u + 1, a, b);
        dfs(u + 1, a + p[u], b);
        dfs(u + 1, a, b + p[u]);
    }

    int maxProduct(string s) {
        n = s.size();
        p = s;
        dfs(0, "", "");
        return ans;
    }
};



Nan97
8天前
#define PII pair<int, int>
#define mk make_pair
#define fi first
#define se second

class Solution {
public:
    int dx[8] = {0, 0, -1, -1, -1, 1, 1, 1}, dy[8] = {-1, 1, -1, 0, 1, -1, 0, 1}; 
    int n, m;
    vector<string> bk;
    queue<PII> q;
    int check(int sx, int sy) {
        int ans = 0;
        while(!q.empty()) q.pop();
        bk[sx][sy] = 'X';
        q.push(mk(sx, sy));
        while(q.size()) {
            PII t = q.front(); q.pop();
            for(int i = 0; i < 8; i ++ ) {
                int ex = -1, ey = -1;
                int p = 1;

                for(;;) {
                    int a = t.fi + dx[i] * p, b = t.se + dy[i] * p;

                    if(a < 0 || a >= n || b < 0 || b >= m) break;

                    if(bk[a][b] == 'O') p ++;
                    else if(bk[a][b] == 'X') {
                        ex = a, ey = b;
                        break;
                    }
                    else break;// 卡了一个小时
                }

                if(ex == -1 && ey == -1) continue;

                for(int j = 1; j < p; j ++ ) {
                    int a = t.fi + dx[i] * j, b = t.se + dy[i] * j;
                    bk[a][b] = 'X';
                    ans ++;
                    q.push(mk(a, b));
                }
            }
        }
        return ans;
    }

    int flipChess(vector<string>& g) {
        int answer = 0;
        n = g.size(), m = g[0].size();

        for(int i = 0; i < n; i ++ ) 
            for(int j = 0; j < m; j ++ ) {
                if(g[i][j] == '.') {
                    bk = g;
                    answer = max(answer, check(i, j));
                }
            }
        return answer;

    }
};





Nan97
8天前
const int N = 1e4 + 10;
class Solution {
public:

    int cnt[N] = {0};
    int minimumSwitchingTimes(vector<vector<int>>& s, vector<vector<int>>& t) {
        int ans = 0;
        int n = s.size(), m = s[0].size();
        int mx = -0x3f3f3f3f;

        for(int i = 0; i < n; i ++ )
            for(int j = 0; j < m; j ++ )
                cnt[s[i][j]] ++, cnt[t[i][j]] --;

        for(int i = 0; i < N; i ++ ) 
            if(cnt[i] > 0) ans += cnt[i];
        return ans;              
    }
};



Nan97
11天前

对于 k次选择,每次选择都要保证最优.
因此我们可以用优先队列存储每次选择可以获得的收益,然后取堆顶即可

#define PII pair<int, int>
#define x first
#define y second

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& income, vector<int>& need) {
        priority_queue<int, vector<int> , less<int> > heap;
        int n = need.size();
        vector<PII> a;
        for(int i  = 0; i < n; i ++ ) 
            a.push_back({need[i], income[i]});
        sort(a.begin(), a.end());
        int idx = 0;
        for(int i = 0; i < k; i ++ ) {
            while(idx < n && a[idx].x <= w) {
                heap.push(a[idx].y);
                idx ++;
            }
            if(heap.size()) {
                int t = heap.top(); heap.pop();
                w += t;
            }
            else break;
        } 
        return w;
    }
};



Nan97
12天前

rand.png

// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7
const int INF =  0x3f3f3f3f;
class Solution {
public:
    int rand10() {
        int l = INF, r = INF;
        while(l > 6) l = rand7();
        while(r > 5) r = rand7();
        return (l & 1) * 5 + r;
    }
};

转载于此处



活动打卡代码 AcWing 920. 最优乘车

Nan97
12天前
#include <bits/stdc++.h>

using namespace std;

const int N = 510, M = 5e4 + 10, INF = 0x3f3f3f3f;

int n, m;
int g[N][N], d[N];
bool st[N];

int dijkstra() {
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for(int i = 0; i < n; i ++ ) {
        int t = 0;
        for(int j = 1; j <= n; j ++ )
            if(!st[j] && (!t || d[t] > d[j]))
                t = j;
        st[t] = true;
        for(int j = 1; j <= n; j ++ ) 
            d[j] = min(d[j], d[t] + g[t][j]);
    }
    return d[n];
}

int main()
{
    cin >> m >> n;
    getchar();
    memset(g, 0x3f, sizeof g);
    for(int t = 0; t < m; t ++) {
        string res; getline(cin, res);
        stringstream ssin(res);
        vector<int> p;

        while(ssin >> res)
            p.push_back(stoi(res));
        int len = p.size();
        for(int i = 0; i < len; i ++ ) 
            for(int j = i + 1; j < len; j ++ ) {
                int l = p[i], r = p[j];
                // printf("%d %d\n", l, r);
                g[l][r] = 1;
            }
        // cout << "len = " << len << endl;
    }
    // for(int i = 1; i <= n; i ++ ) {
    //     for(int j = 1; j <= n; j ++ ) {
    //         printf("g[%d][%d] = %d ", i, j, g[i][j]);
    //     }
    //     puts("");
    // } 
    // dijkstra();
    // cout << d[1] << endl << g[1][3] << endl;
    // cout << d[3] << endl << d[6] << endl << d[7] << endl;
    int t = dijkstra();
    if(t == INF) puts("NO");
    else printf("%d\n", t - 1);
    return 0;
}


活动打卡代码 AcWing 1058. 股票买卖 V

Nan97
13天前
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII ;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int a[N];
int f[N][3];

int main() {
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif

    int n; cin >> n; 
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    // 0表示未持有股票
    // 1表示持有股票z
    // 2 表示冷冻期
    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;
    int mx = -INF;
    // for(int i = 0; i <= n; i ++ ) f[i][0] = 0;
    for(int i = 1; i <= n; i ++ ) {
        f[i][0] = max(f[i - 1][2], f[i - 1][0]);
        f[i][1] = max(f[i - 1][0] - a[i], f[i - 1][1]);
        f[i][2] = f[i - 1][1] + a[i];
        mx = max({f[i][0], f[i][1], f[i][2], mx});
    }
    cout << mx << endl;
    // for(int i = 0; i < n; i ++ )


    return 0;
}