[hihocoder][Offer收割]编程练习赛46-白红宇

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

阅读量：4943 次

发布时间：2019-06-11

本文共 6046 字，大约阅读时间需要 20 分钟。

AEIOU

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

#pragma comment(linker, "/STACK:102400000,102400000")#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  //#include
                  
                   using namespace std;typedef long long lint;typedef vector
                   
                     VI;typedef pair
                    
                      PII;typedef queue
                     
                       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;}

View Code

数字游戏

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

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

#pragma comment(linker, "/STACK:102400000,102400000")#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  //#include
                  
                   using namespace std;typedef long long lint;typedef vector
                   
                     VI;typedef pair
                    
                      PII;typedef queue
                     
                       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
                      
                        mp;priority_queue
                       
                         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;}

View Code

第K小分数

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

#pragma comment(linker, "/STACK:102400000,102400000")#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  //#include
                  
                   using namespace std;typedef long long lint;typedef vector
                   
                     VI;typedef pair
                    
                      PII;typedef queue
                     
                       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;}

View Code

逆序异或和

#include 
      
       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;}

View Code

转载于:https://www.cnblogs.com/dramstadt/p/8402018.html

你可能感兴趣的文章

手动编译一个c文件（Win7下如何使用GCC编译器）