[hihocoder][Offer收割]编程练习赛46

AEIOU

选出的子串中由AEI构成的子串和由OU构成的子串之间并没有什么关系，分别算出最长的加起来。

#pragma comment(linker, "/STACK:102400000,102400000")

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<functional>

#include<math.h>

//#include<bits/stdc++.h>

using namespace std;

typedef long long lint;

typedef vector<int> VI;

typedef pair<int, int> PII;

typedef queue<int> QI;

void makedata() {

    freopen("input.txt", "w", stdout);

    fclose(stdout);

}

string s;

int dp[];

int p[];

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    //makedata();

    std::ios::sync_with_stdio(), cin.tie();

    cin >> s;

    int n = s.size();

    int max1 = , max2 = ;

    memset(dp, , sizeof(dp));

    for (int i = ; i < ; i++) p[i] = -;

    for (int i = ; i < n; i++) {

        if (s[i] == 'a') {

            dp[i] = ;

            if (p['a'] != -) dp[i] = max(dp[i], dp[p['a']] + );

            if (dp[i] > dp[p['a']]) p['a'] = i;

        }

        if (s[i] == 'e') {

            dp[i] = ;

            if (p['a'] != -) dp[i] = max(dp[i], dp[p['a']] + );

            if (p['e'] != -) dp[i] = max(dp[i], dp[p['e']] + );

            if (dp[i] > dp[p['e']]) p['e'] = i;

        }

        if (s[i] == 'i') {

            dp[i] = ;

            if (p['a'] != -) dp[i] = max(dp[i], dp[p['a']] + );

            if (p['e'] != -) dp[i] = max(dp[i], dp[p['e']] + );

            if (p['i'] != -) dp[i] = max(dp[i], dp[p['i']] + );

            if (dp[i] > dp[p['i']]) p['i'] = i;

        }

        max1 = max(max1, dp[i]);

    }

    memset(dp, , sizeof(dp));

    for (int i = ; i < ; i++) p[i] = -;

    for (int i = ; i < n; i++) {

        if (s[i] == 'o') {

            dp[i] = ;

            if (p['o'] != -) dp[i] = max(dp[i], dp[p['o']] + );

            if (dp[i] > dp[p['o']]) p['o'] = i;

        }

        if (s[i] == 'u') {

            dp[i] = ;

            if (p['o'] != -) dp[i] = max(dp[i], dp[p['o']] + );

            if (p['u'] != -) dp[i] = max(dp[i], dp[p['u']] + );

            if (dp[i] > dp[p['u']]) p['u'] = i;

        }

        max2 = max(max2, dp[i]);

    }

    cout << max1 + max2 << endl;

    return ;

}

数字游戏

这题看别人的代码貌似跟全排列有关，但是没想通关系在哪。

我的解法是这样的：首先加减和交换的顺序并不会影响操作的步数，所以可以看做是先进行若干步交换，然后依次把每一位加减为B的对应位数字。以A为初始状态进行bfs，然后卡时，就过了、

#pragma comment(linker, "/STACK:102400000,102400000")

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<functional>

#include<math.h>

//#include<bits/stdc++.h>

using namespace std;

typedef long long lint;

typedef vector<int> VI;

typedef pair<int, int> PII;

typedef queue<int> QI;

void makedata() {

    freopen("input.txt", "w", stdout);

    fclose(stdout);

}

char A[], B[];

int cost[][];

lint p[];

int n;

struct state {

    int step;

    char num[];

    bool operator < (state s) const {

        if (step == s.step) return false;

        else return step > s.step;

    }

};

lint calc(state s) {

    lint rtn = ;

    for (int i = ; i < n; i++) rtn += s.num[i] * p[n - i - ];

    return rtn;

}

map<lint, int> mp;

priority_queue<state> q;

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    //makedata();

    std::ios::sync_with_stdio(), cin.tie();

    scanf("%d%s%s", &n, A, B);

    for (int i = ; i < n; i++) {

        A[i] -= '';

        B[i] -= '';

    }

    p[] = ;

    for (int i = ; i < ; i++) p[i] = p[i - ] * ;

    for (int i = ; i < ; i++) {

        for (int j = ; j < ; j++) {

            if (i == j) cost[i][j] = ;

            if (i > j) cost[i][j] = cost[j][i];

            if (i < j) cost[i][j] = min(j - i, i +  - j);

        }

    }

    lint b = ;

    for (int i = ; i < n; i++) b += B[i] * p[n - i - ];

    state s, u;

    s.step = ;

    memcpy(s.num, A, sizeof(A));

    q.push(s);

    mp[calc(s)] = ;

    int ans = , iter = ;

    while (!q.empty()) {

        s = q.top();

        q.pop();

        int step = s.step;

        for (int i = ; i < n; i++) step += cost[s.num[i]][B[i]];

        ans = min(ans, step);

        iter++;

        if (iter > ) break;

        for (int i = ; i < n; i++) {

            for (int j = i + ; j < n; j++) {

                u = s;

                char t = u.num[i];

                u.num[i] = u.num[j];

                u.num[j] = t;

                u.step++;

                lint c = calc(u);

                if (mp.find(c) != mp.end()) continue;

                else {

                    mp[c] = ;

                    q.push(u);

                }

            }

        }

    }

    cout << ans << endl;

    return ;

}

第K小分数

前K个分数显然由每个质数构成的分数的前连续若干项构成，由于最多有1000个质数，所以最多有1000个最后一项，所以第K个分数一定是这最多1000个最后一项中的一个。可以用二分法来确定每种分母的最后一项并计算其排名，若其排名为K，则找到了题目要求的分数。

#pragma comment(linker, "/STACK:102400000,102400000")

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<vector>

#include<algorithm>

#include<iostream>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<functional>

#include<math.h>

//#include<bits/stdc++.h>

using namespace std;

typedef long long lint;

typedef vector<int> VI;

typedef pair<int, int> PII;

typedef queue<int> QI;

void makedata() {

    freopen("input.txt", "w", stdout);

    fclose(stdout);

}

lint p[];

int main() {

#ifndef ONLINE_JUDGE

    freopen("input.txt", "r", stdin);

#endif

    //makedata();

    std::ios::sync_with_stdio(), cin.tie();

    int n;

    lint k;

    cin >> n >> k;

    for (int i = ; i < n; i++) cin >> p[i];

    for (int i = ; i < n; i++) {

        lint l = , r = p[i], mid;

        while (l +  < r) {

            mid = (l + r) >> ;

            lint tmp = ;

            for (int j = ; j < n; j++) tmp += mid * p[j] / p[i];

            if (tmp == k) cout << mid << '/' << p[i] << endl;

            if (tmp <= k) l = mid;

            else r = mid;

        }

    }

    return ;

}

逆序异或和

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = ;

int n, a[N];

struct BIT {

    int c[N];

    void init() {

        memset(c, , sizeof(c));

    }

    void insert(int x) {

        for (; x < N; x += x & -x) c[x] ++;

    }

    int count(int x, int res=) {

        for (; x; x ^= x & -x) res += c[x];

        return res;

    }

}bit[], num;

int main() {

    scanf("%d", &n);

    for (int i = ; i <= n; ++i) scanf("%d", a + i);

    num.init();

    for (int i = ; i < ; ++i) bit[i].init();

    ll ans = ;

    for (int i = n; i >= ; --i) {

        int tar = num.count(a[i] - );

        num.insert(a[i]);

        for (int j = ; j < ; ++j) {

            int _num =  << j;

            int _bit = a[i] & _num;

            int _bit_tar = bit[j].count(a[i] - );

            if (_bit) {

                ans += 1LL * _num * (tar - _bit_tar);

                bit[j].insert(a[i]);

            }

            else {

                ans += 1LL * _num * _bit_tar;

            }

        }

    }

    cout << ans << endl;

    return ;

}

巴特西

[hihocoder][Offer收割]编程练习赛46

最新文章

热门文章