首页 > 代码库 > zoj3814

zoj3814

2024-07-21 15:17:31   213人阅读

这题说的是给了一个数在longlong范围内 然后求出小于这个数的最大的回文，枚举每位减去1后 ， 他后面的位置上全部都置为9，然后在枚举每个前半部分，然后贪心取得这个数的最大值，贪心的时候写错了，错在这..到枚举到now[loc]<now[loc+1] 时 就进行下一位，但是下一位不可能取得的时候却没有继续枚举这一位较小的

#include <cstdio>#include <string.h>#include <algorithm>#include <algorithm>using namespace std;typedef  long long ll;const int MAX_N = 35;ll str[MAX_N];ll now[MAX_N],N,E[MAX_N],ans;int perLen,nowLen;void reserve(ll *C,int len){     for(int i=0; i<len/2; i++){         ll c = C[i];         C[i]=C[len-i-1];         C[len-1-i]=c;     }}void uniquet(ll *C, int &len){       int now =1;       for(int i=1; i<len; i++){            if(C[i]!=C[now-1]){                 C[now++]=C[i];            }       }       len=now;}bool dfs(int loc1, int loc2, ll R){        if(loc2==perLen){             if(loc1==nowLen){                 ans=ans>R?ans:R; return true;             }             return false;        }        if(loc1==nowLen) return false;        ll cur = R+now[loc1]*E[perLen-loc2-1];        if(cur>=N) return false;        bool ans=false;        if(now[loc1]>now[loc1+1]&&nowLen - loc1 < perLen - loc2){               ans= dfs(loc1,loc2+1,cur);        }        if(ans==true) return true;        ans=dfs(loc1+1,loc2+1,cur);        if(ans==false) ans=dfs(loc1,loc2+1,cur);        return ans;}void solve(){    for(int i =0; i<perLen; i++){          ll R =0; nowLen=0;          for(int j=0; j<=i; ++j ){               R=R+str[j]*E[perLen-1-j];               now[nowLen++]=str[j];          }          uniquet(now,nowLen);          reserve(now,nowLen);          now[nowLen]=-1;          dfs(0,i+1,R);          nowLen=0;         if(i==0) continue;         for(int j=0; j<i; ++j ){            now[nowLen++] = str[j];         }         uniquet(now,nowLen);         reserve(now,nowLen);         now[nowLen]=-1;         dfs(0,i+1,R);    }}int main(){   // freopen("data.in","r",stdin);    //freopen("data.out","w",stdout);     int cas;     E[0]=1;     for(int i=1; i<=18; i++)        E[i]=E[i-1]*10LL;     scanf("%d",&cas);     while(cas--){        scanf("%lld",&N);        if(N<12){             if(N==11) {                 puts("9");             }             else {                    printf("%lld\n",N-1);             }             continue;        }        int len=0;        ll we = N;        while(we>0){             len++; we/=10;        }        ans=0;        for(int i=0; i< len; ++i){             ll to = N-E[i];             perLen = 0;             for(int j = 0; j<i; j++){                 str[perLen++]=9; to/=10;             }             while(to){                 str[perLen++]=to%10;                 to/=10;             }             reserve(str,perLen);             solve();        }        printf("%lld\n",ans);     }     return 0;}
View Code

 

zoj3814


联系
我们