[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[1110000];
int p[256];

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
//makedata();
    std::ios::sync_with_stdio(0), cin.tie(0);
    cin >> s;
int n = s.size();
int max1 = 0, max2 = 0;
    memset(dp, 0, sizeof(dp));
for (int i = 0; i < 256; i++) p[i] = -1;
for (int i = 0; i < n; i++) {
if (s[i] == 'a') {
            dp[i] = 1;
if (p['a'] != -1) dp[i] = max(dp[i], dp[p['a']] + 1);
if (dp[i] > dp[p['a']]) p['a'] = i;
        }
if (s[i] == 'e') {
            dp[i] = 1;
if (p['a'] != -1) dp[i] = max(dp[i], dp[p['a']] + 1);
if (p['e'] != -1) dp[i] = max(dp[i], dp[p['e']] + 1);
if (dp[i] > dp[p['e']]) p['e'] = i;
        }
if (s[i] == 'i') {
            dp[i] = 1;
if (p['a'] != -1) dp[i] = max(dp[i], dp[p['a']] + 1);
if (p['e'] != -1) dp[i] = max(dp[i], dp[p['e']] + 1);
if (p['i'] != -1) dp[i] = max(dp[i], dp[p['i']] + 1);
if (dp[i] > dp[p['i']]) p['i'] = i;
        }
        max1 = max(max1, dp[i]);
    }
    memset(dp, 0, sizeof(dp));
for (int i = 0; i < 256; i++) p[i] = -1;
for (int i = 0; i < n; i++) {
if (s[i] == 'o') {
            dp[i] = 1;
if (p['o'] != -1) dp[i] = max(dp[i], dp[p['o']] + 1);
if (dp[i] > dp[p['o']]) p['o'] = i;
        }
if (s[i] == 'u') {
            dp[i] = 1;
if (p['o'] != -1) dp[i] = max(dp[i], dp[p['o']] + 1);
if (p['u'] != -1) dp[i] = max(dp[i], dp[p['u']] + 1);
if (dp[i] > dp[p['u']]) p['u'] = i;
        }
        max2 = max(max2, dp[i]);
    }
    cout << max1 + max2 << endl;
return 0;
}

数字游戏

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

我的解法是这样的：首先加减和交换的顺序并不会影响操作的步数，所以可以看做是先进行若干步交换，然后依次把每一位加减为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[15], B[15];
int cost[10][10];
lint p[15];
int n;
struct state {
int step;
char num[15];
bool operator < (state s) const {
if (step == s.step) return false;
else return step > s.step;
    }
};
lint calc(state s) {
    lint rtn = 0;
for (int i = 0; i < n; i++) rtn += s.num[i] * p[n - i - 1];
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(0), cin.tie(0);
    scanf("%d%s%s", &n, A, B);
for (int i = 0; i < n; i++) {
        A[i] -= '0';
        B[i] -= '0';
    }
    p[0] = 1;
for (int i = 1; i < 15; i++) p[i] = p[i - 1] * 10;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
if (i == j) cost[i][j] = 0;
if (i > j) cost[i][j] = cost[j][i];
if (i < j) cost[i][j] = min(j - i, i + 10 - j);
        }
    }
    lint b = 0;
for (int i = 0; i < n; i++) b += B[i] * p[n - i - 1];
    state s, u;
    s.step = 0;
    memcpy(s.num, A, sizeof(A));
    q.push(s);
    mp[calc(s)] = 1;
int ans = 1000, iter = 0;
while (!q.empty()) {
        s = q.top();
        q.pop();
int step = s.step;
for (int i = 0; i < n; i++) step += cost[s.num[i]][B[i]];
        ans = min(ans, step);
        iter++;
if (iter > 50000) break;
for (int i = 0; i < n; i++) {
for (int j = i + 1; 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] = 1;
                    q.push(u);
                }
            }
        }
    }
    cout << ans << endl;
return 0;
}

第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[2000];

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
//makedata();
    std::ios::sync_with_stdio(0), cin.tie(0);
int n;
    lint k;
    cin >> n >> k;
for (int i = 0; i < n; i++) cin >> p[i];
for (int i = 0; i < n; i++) {
        lint l = 0, r = p[i], mid;
while (l + 1 < r) {
            mid = (l + r) >> 1;
            lint tmp = 0;
for (int j = 0; 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 0;
}

逆序异或和

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 100010;

int n, a[N];

struct BIT {
int c[N];
void init() {
        memset(c, 0, sizeof(c));
    }
void insert(int x) {
for (; x < N; x += x & -x) c[x] ++;
    }
int count(int x, int res=0) {
for (; x; x ^= x & -x) res += c[x];
return res;
    }
}bit[20], num;

int main() {
    scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    num.init();
for (int i = 0; i < 20; ++i) bit[i].init();
    ll ans = 0;
for (int i = n; i >= 1; --i) {
int tar = num.count(a[i] - 1);
        num.insert(a[i]);

for (int j = 0; j < 20; ++j) {
int _num = 1 << j;
int _bit = a[i] & _num;
int _bit_tar = bit[j].count(a[i] - 1);
if (_bit) {
                ans += 1LL * _num * (tar - _bit_tar);
                bit[j].insert(a[i]);
            }
else {
                ans += 1LL * _num * _bit_tar;
            }
        }
    }
    cout << ans << endl;
return 0;
}