CodeForces 478E Wavy numbers - c++编程基础

题意：

如果一个数它的每一位（除了最高最低位）都大于或小于它两边的数字则这个数字叫波浪数输入n和k （10^14）求%n==0的第k小的波浪数如果没有或者大于10^14就输出-1

思路：

这也算是一种分治的搜索策略吧 meet-in-mid

由于数字最多14位因此可以暴力高7位和低7位（均为80+w种）然后枚举高位和低位去拼

这题对于代码书写要求较高！！我的方法如下：

暴力高7位

暴力低7为放进vector 同时记录对于一个number 它的首位和首位与第二位大小情况（为了拼接）同时做一个hash 记录cnt[i][j][k] 其中i为number首位 j为0或1表示首位与第二位大小情况 k为number%n的余数的hash值（为了方便查找）cnt记录ijk情况的number个数

然后开始寻找答案

枚举高7位的number 表示只有不用拼接的情况

判断n是否大于等于10^7 如果是那么只要i=n开始不断的+n就可以找数字了

如果不是枚举高7位再枚举低7位的首位利用刚才记录的cnt不断的使k减小直到确定了高7位后暴力低7位拼答案

注意：hash不能用map 会TLE 在叉姐的提醒下我改成了离散再hash（因为种类不多！！）现在是CF上跑的最快的代码哈哈哈哈哈哈哈~~~

代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               using namespace std; typedef long long LL; #define N 850000 #define M 10000000 LL n, k; int tothigh; int anshigh[N]; vector
              
                anslow[10][2]; int id, to[M], cnt[10][2][N]; int dig[10]; void get_high(int bit) { int num = 0, i = bit; while (i) { num = num * 10 + dig[i]; i--; } anshigh[tothigh++] = num; } void find_high(int bit) { for (int i = 0; i <= 9; i++) { if (i != dig[bit - 1]) { if (bit <= 2 || (bit > 2 && ((i > dig[bit - 1] && dig[bit - 2] > dig[bit - 1]) || (i < dig[bit - 1] && dig[bit - 2] < dig[bit - 1])))) { dig[bit] = i; if (i) get_high(bit); if (bit < 7) find_high(bit + 1); } } } } void get_low() { int num = 0, i = 7; while (i) { num = num * 10 + dig[i]; i--; } if (dig[7] < dig[6]) { anslow[dig[7]][0].push_back(num); if (!to[num % n]) to[num % n] = ++id; cnt[dig[7]][0][to[num % n]]++; } else { anslow[dig[7]][1].push_back(num); if (!to[num % n]) to[num % n] = ++id; cnt[dig[7]][1][to[num % n]]++; } } void find_low(int bit) { for (int i = 0; i <= 9; i++) { if (i != dig[bit - 1]) { if (bit <= 2 || (bit > 2 && ((i > dig[bit - 1] && dig[bit - 2] > dig[bit - 1]) || (i < dig[bit - 1] && dig[bit - 2] < dig[bit - 1])))) { dig[bit] = i; if (bit == 7) get_low(); else find_low(bit + 1); } } } } bool check(LL x) { int a = x % 10; x /= 10; int b = x % 10; x /= 10; while (x) { int c = x % 10; x /= 10; if ((b > a && b > c) || (b < a && b < c)) ; else return false; a = b; b = c; } return true; } int main() { scanf("%lld%lld", &n, &k); dig[0] = -1; find_high(1); find_low(1); sort(anshigh, anshigh + tothigh); for (int i = 0; i < tothigh; i++) { if (anshigh[i] % n == 0) { k--; if (!k) { printf("%d\n", anshigh[i]); return 0; } } } if (n >= M) { for (LL i = n; i <= 100000000000000LL; i += n) { if (check(i)) { k--; if (!k) { printf("%lld\n", i); return 0; } } } } else for (int i = 0; i < tothigh; i++) { int r = to[(n - (LL) anshigh[i] * M % n) % n]; if (!r) continue; if (anshigh[i] < 10) { for (int j = 0; j <= 9; j++) { if (j == anshigh[i]) continue; if (j > anshigh[i]) { if (cnt[j][1][r]) { if (k > cnt[j][1][r]) k -= cnt[j][1][r]; else { sort(anslow[j][1].begin(), anslow[j][1].end()); for (int it = 0; it < anslow[j][1].size(); it++) { if (to[anslow[j][1][it] % n] == r) { k--; if (!k) { printf("%d%07d\n", anshigh[i], anslow[j][1][it]); return 0; } } } } } } else { if (cnt[j][0][r]) { if (k > cnt[j][0][r]) k -= cnt[j][0][r]; else { sort(anslow[j][0].begin(), anslow[j][0].end()); for (int it = 0; it < anslow[j][0].size(); it++) { if (to[anslow[j][0][it] % n] == r) { k--; if (!k) { printf("%d%07d\n", anshigh[i], anslow[j][0][it]); return 0; } } } } } } } } else { if (anshigh[i] % 10 > anshigh[i] / 10 % 10) { for (int j = 0; j < anshigh[i] % 10; j++) { if (cnt[j][0][r]) { if (k > cnt[j][0][r]) k -= cnt[j][0][r]; else { sort(anslow[j][0].begin(), anslow[j][0].end()); for (int it = 0; it < anslow[j][0].size(); it++) { if (to[anslow[j][0][it] % n] == r) { k--; if (!k) { printf("%d%07d\n", anshigh[i], anslow[j][0][it]); return 0; } } } } } } } else { for (int j = anshigh[i] % 10 + 1; j <= 9; j++) { if (cnt[j][1][r]) { if (k > cnt[j][1][r]) k -= cnt[j][1][r]; else { sort(anslow[j][1].begin(), anslow[j][1].end()); for (int it = 0; it < anslow[j][1].size(); it++) { if (to[anslow[j][1][it] % n] == r) { k--; if (!k) { printf("%d%07d\n", anshigh[i], anslow[j][1][it]); return 0; } } } } } } } } } printf("-1\n"); return 0; }