头像

rushhhhh




离线:2小时前


最近来访(191)
用户头像
yxc的键盘
用户头像
AcWing-Curry
用户头像
ustc
用户头像
jiakeyu666
用户头像
itdef
用户头像
自律
用户头像
Behappyeveryday
用户头像
obss
用户头像
chmffwn1
用户头像
端木俁
用户头像
liang302
用户头像
Ethereum
用户头像
星光灿烂
用户头像
lkp
用户头像
life的日常
用户头像
心向远方
用户头像
酒肉
用户头像
MongoRolls
用户头像
不张扬的张扬
用户头像
Lims

活动打卡代码 AcWing 571. 数学编码器

rushhhhh
4小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 10010;
const int MOD = 1000000007;
int T, n;
int a[N], p[N];

int main()
{
    p[0] = 1;
    for (int i = 1; i < N; i ++ ) p[i] = p[i - 1] * 2 % MOD;

    cin >> T;
    for(int t=1; t<=T; t++) {
        cin >> n;
        for(int i=0; i<n; i++) cin >> a[i];
        int ans = 0;

        for(int i=0; i<n; i++) {
            ans = (ans + (LL)a[i] * (p[i] - p[n-i-1])) % MOD;
        }
        printf("Case #%d: %d\n", t, ans);
    }

    return 0;
}


活动打卡代码 AcWing 561. 大按钮

rushhhhh
5小时前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int T, n, p;

typedef long long LL;

int main()
{
    cin >> T;
    for(int t=1; t<=T; t++) {
        cin >> n >> p;
        vector<string> vs;
        for(int i=0; i<p; i++) {
            string s;
            cin >> s;
            vs.push_back(s);
        }
        sort(vs.begin(), vs.end());
        vector<string> real;
        for(int i=vs.size()-1; i>=0; i--) {
            bool can = true;
            for(int j=i-1; j>=0; j--) {
                if(vs[i].substr(0, vs[j].size()) == vs[j]) {
                    can = false;
                    break;
                }
            }
            if(can) real.push_back(vs[i]);
        }

        LL ans = 1ll << n;
        for(auto& s : real) {
            ans -= (1ll << (n-s.size()));
        }
        printf("Case #%d: %lld\n", t, ans);
    }

    return 0;
}


活动打卡代码 AcWing 1114. 棋盘问题

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10;
int n, k;
char g[N][N];
// 在前i行放置,且整体放置形成的数字为j的放置方案
int f[N][1<<N];

int main()
{
    while(scanf("%d %d", &n, &k), n > 0) {
        for(int i=1; i<=n; i++)
            scanf("%s", g[i]);

        int tot = 1 << n;

        memset(f, 0, sizeof f);
        f[0][0] = 1;
        for(int i=1; i<=n; i++) {
            // j表明放置在哪一列
            for(int j=0; j<n; j++) {
                if(g[i][j] == '#') {
                    // 可以放置,遍历之前的状态
                    for(int t=0; t<tot; t++) {
                        // 二者不应有冲突
                        if(((t >> j) & 1) == 0) {
                            f[i][t | (1 << j)] += f[i-1][t];
                        }
                    }
                }
            }
            // 不放
            for(int t=0; t<tot; t++) {
                f[i][t] += f[i-1][t];
            }
        }
        int ans = 0;
        for(int i=0; i<tot; i++) {
            if(__builtin_popcount(i) == k) {
                ans += f[n][i];
            }
        }
        cout << ans << endl;
    }
}


活动打卡代码 AcWing 1111. 字母

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 22;
int n, m;
char g[N][N];
int have[200];
int ans = 1;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void dfs(int x, int y, int cnt)
{
    ans = max(ans, cnt);
    for(int i=0; i<4; i++) {
        int xx = dx[i] + x;
        int yy = dy[i] + y;
        if(xx>=0 && xx<n && yy>=0 && yy<m) {
            if(have[g[xx][yy]] == 0) {
                have[g[xx][yy]] = 1;
                dfs(xx, yy, cnt+1);
                have[g[xx][yy]] = 0;
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i=0; i<n; i++)
        scanf("%s", g[i]);

    have[g[0][0]] = 1;
    dfs(0, 0, 1);
    cout << ans << endl;

    return 0;
}



#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int n, a[N];

bool check(int mid)
{
    for(int i=1; i<=n; i++) {
        mid = 2 * mid - a[i];
        if(mid < 0) return false;
        if(mid >= N) return true;
    }
    return true;
}

int main()
{
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
    int l=0, r=1e5+5;
    while(l < r) {
        int mid = l+r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;

    return 0;
}


活动打卡代码 AcWing 1028. 复制书稿

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;
int n, k;
int a[N];
int L[N], R[N];

bool check(int mid)
{
    int cnt = 0, s = 0;
    for(int i=1; i<=n; i++) {
        if(a[i] > mid) return false;
        if(s+a[i] > mid) {
            s = a[i];
            cnt++;
        } else {
            s += a[i];
        }
    }
    if(s) cnt++;
    return cnt <= k;
}

int main()
{
    cin >> n >> k;
    for(int i=1; i<=n; i++) cin >> a[i];

    int l=1, r=250000;
    while(l < r) {
        int mid = l+r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    // cout << l << endl;

    int s = a[n], t = k;
    R[k] = n;

    for(int i=n-1; i>=1; i--) {
        if(s+a[i] > l) {
            L[t] = i+1;
            s = a[i];
            t--;
            R[t] = i;
        } else {
            s += a[i];
        }
    }
    L[t] = 1;
    for(int i=1; i<=k; i++) cout << L[i] << ' ' << R[i] << endl;

    return 0;
}


活动打卡代码 AcWing 587. 吃蛋糕

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, M = 10010;
int f[M];

int main()
{
    int T;
    cin >> T;
    int a[N];

    for(int i=1; i<=100; i++) a[i] = i * i;
    memset(f, 0x3f, sizeof f);

    f[0] = 0;
    for(int i=1; i<M; i++) {
        for(int j=1; j<=100; j++) {
            if(i < a[j]) break;
            f[i] = min(f[i], f[i-a[j]] + 1);
        }
    }

    for(int t=1; t<=T; t++) {
        int x;
        cin >> x;
        printf("Case #%d: %d\n", t, f[x]);
    }

    return 0;
}


活动打卡代码 AcWing 591. 国家领导者

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;

bool cmp(string a, string b)
{
    unordered_set<char> A, B;
    for (auto c : a)
        if (c != ' ')
            A.insert(c);
    for (auto c : b)
        if (c != ' ' )
            B.insert(c);

    if (A.size() != B.size()) return A.size() > B.size();

    return a < b;
}

int main()
{
    int T;
    cin >> T;
    for(int i=1; i<=T; i++) {
        int n;
        cin >> n;
        string ans, s;
        int res = 0;
        getchar();
        while(n--) {
            getline(cin, s);
            if(cmp(s, ans)) ans = s;
        }
        cout << "Case #" << i << ": ";
        cout << ans << endl;
    }
    return 0;
}



rushhhhh
10天前
class Solution {
public:
    vector<vector<int> > findContinuousSequence(int sum) {
        vector<vector<int>> ans;
        for(int i=1, j=1, res=1; i<=sum; i++) {
            while(res < sum) res += ++j;
            if(res == sum && j-i+1 > 1) {
                vector<int> t;
                for(int k=i; k<=j; k++) t.push_back(k);
                ans.push_back(t);
            }
            res -= i;
        }
        return ans;
    }
};


活动打卡代码 AcWing 1274. 奶牛排队

rushhhhh
10天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 50010, M = 16;
int f[N][M], g[N][M];
int n, q;
int a[N];

void init()
{
    for(int len=0; (1<<len)<=n; len++) {
        for(int i=1; i<=n; i++) {
            if(i + (1<<len) - 1 > n) break;
            if(len == 0) {
                f[i][len] = a[i];
                g[i][len] = a[i];
            } else {
                f[i][len] = max(f[i][len-1], f[i+(1<<(len-1))][len-1]);
                g[i][len] = min(g[i][len-1], g[i+(1<<(len-1))][len-1]);
            }
        }
    }
}

int query(int l, int r)
{
    int len = r-l+1;
    int k = log(len) / log(2);
    if(k == 0) return 0;
    return max(f[l][k], f[r-(1<<k)+1][k]) - min(g[l][k], g[r-(1<<k)+1][k]);
}

int main()
{
    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> a[i];

    init();

    while(q--) {
        int l, r;
        cin >> l >> r;
        cout << query(l, r) << endl;
    }

    return 0;
}