OR2. Numeric Keypad
描述
The numberic keypad on your mobile phone looks like below:输入描述
the first line contains an integer T, the number of testcases.输出描述
for each testcase output one line, the maximum number less than or equal to the corresponding K that can be produced.示例1
输入:
3 25 83 131
输出:
25 80 129
C 解法, 执行用时: 2ms, 内存消耗: 200KB, 提交时间: 2019-11-30
#include<stdio.h> int T,x[10],y[10]; char c[503],d[503]; void getxy() { int i; y[0]=4; for(i=1;i<=9;i++)y[i]=(i+2)/3; x[0]=2; for(i=1;i<=9;i++)x[i]=(i+2)%3+1; } int cango(char i,char j) { if(x[i-'0']<=x[j-'0']&&y[i-'0']<=y[j-'0'])return 1; else return 0; } int fun(int i,char pre)//i表示插入位置 { char j,k; if(!c[i]){ d[i]=0; return 1; } for(j=c[i];j>='0'&&!cango(pre,j);j--); if(j==c[i]){ d[i]=j; if(fun(i+1,j))return 1; while(--j>='0'&&!cango(pre,j)); } if(j<'0')return 0; d[i]=j; k=j=='0'?'0':'9'; while(c[++i])d[i]=k; d[i]=0; return 1; } int main() { int i; getxy(); scanf("%d",&T); getchar(); for(i=0;i<T;i++){ c[0]='1'; gets(c+1); fun(0,'1'); printf("%s\n",d+1); } }
C 解法, 执行用时: 2ms, 内存消耗: 280KB, 提交时间: 2022-01-28
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <stdbool.h> int s[10][10] = { {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}, {9,8,7,6,5,4,3,2,1,0}, {9,8,6,5,3,0,-1,-1,-1,-1}, {9,6,-1,-1,-1,-1,-1,-1,-1,-1}, {9,8,7,6,5,0,-1,-1,-1,-1}, {9,8,6,0,-1,-1,-1,-1,-1,-1}, {9,-1,-1,-1,-1,-1,-1,-1,-1,-1}, {9,8,0,-1,-1,-1,-1,-1,-1,-1}, {9,0,-1,-1,-1,-1,-1,-1,-1,-1}, {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1} }; int count = 0; bool cango(int i, int j){ if (i == j) return true; bool flag = false; for(int k = 0; k < 10; k++) { if (s[i][k] == j) { flag = true; break; } } return flag; } void fill(char * c, int j) { for(int l = j; l < 503; l++) { if (c[l] == 0) { break; } if (s[c[l]-'0'][0] != -1) { if (c[l+1] != 0) { c[l+1] = s[c[l]-'0'][0] + '0'; } } else { if (c[l+1] !=0) { c[l+1] = c[l]; } } } } bool helper(char * c, int j) { //printf("!cnago==%s--,%d\n",c,j); c[j]--; bool flag = false; while(j == 0 || cango(c[j-1]-'0', c[j]-'0')) { if(s[c[j]-'0'][0] != -1) { c[j+1] = s[c[j]-'0'][0] + '0'; fill(c,j+1); flag = true; break; } c[j]--; } if (flag) { return true; } c[j]++; return false; } void deal(char c[]) { int j = 0; bool flag = true; for(int i = 1; i < 503; i++) { if (c[i] == 0) { break; } if (!cango(c[i-1]-'0',c[i]-'0')) { //printf("cnago==%s--,%d\n",c,i); flag = false; break; } j++; } if (flag) { printf("%s\n",c); } else { int t = 0; int flag = false; //return; while(s[c[j]-'0'][t] != -1) { if (s[c[j]-'0'+t] < c[j+1]){ flag = true; break; } t++; } bool res_f = false; if (flag) { c[j+1] = s[c[j]-'0'+t] + '0'; res_f = true; } else if (c[j] < c[j+1]){ c[j+1] = c[j]; res_f = true; } //printf("before fill:%s,j=%d\n",c,j); if (res_f) { fill(c,j+1); printf("%s\n",c); return; } if (cango(c[j]-'0', 0)) { for(int k = j + 1; k < 503; k++) { if (c[k] == 0) { break; } c[k] = '0'; } } else { //printf("jjj===%d",j); while (j >= 0) { if(helper(c, j)) { break; } j--; } } printf("%s\n",c); } } int main() { int n; char * data[21]; scanf("%d",&n); getchar(); for(int i = 0; i < n; i++) { char c[503] = {0}; gets(c); deal(c); } }
C++ 解法, 执行用时: 2ms, 内存消耗: 284KB, 提交时间: 2021-12-17
#include<bits/stdc++.h> using namespace std; #define debug printf("%d %s\n",__LINE__,__FUNCTION__);fflush(stdout) using ll=long long;using i64=long long;using db=double; using u32=unsigned int;using u64=unsigned long long;using db=double; using pii=pair<int,int>;using vi=vector<int>; using qi=queue<int>;using pqi=priority_queue<int>;using si=set<int>; #define pb push_back #define mk make_pair #define ins insert #define era erase #define fi first #define se second #define lowbit(x) x&-x #define ALL(a) a.begin(),a.end() const int INF=0x3f3f3f3f; const ll INFLL=0x3f3f3f3f3f3f3f3f; const double PI=acos(-1.0); template<class T>inline bool chkmin(T&a,T b){return b<a?a=b,true:false;} template<class T>inline bool chkmax(T&a,T b){return a<b?a=b,true:false;} int _w,_t;FILE* _f; #define MULTI_CASES const int N=502; char s[N],ans[N]; bool G[12][12]; int n; void init(){ G[1][1]=G[1][2]=G[1][3]=G[1][4]=G[1][5]=G[1][6]=G[1][7]=G[1][8]=G[1][9]=G[1][0]=1; G[2][2]=G[2][3]=G[2][5]=G[2][6]=G[2][8]=G[2][9]=G[2][0]=1; G[3][3]=G[3][6]=G[3][9]=1; G[4][4]=G[4][5]=G[4][6]=G[4][7]=G[4][8]=G[4][9]=G[4][0]=1; G[5][5]=G[5][6]=G[5][8]=G[5][9]=G[5][0]=1; G[6][6]=G[6][9]=1; G[7][7]=G[7][8]=G[7][9]=G[7][0]=1; G[8][8]=G[8][9]=G[8][0]=1; G[9][9]=1; G[0][0]=1; ans[0]='1'; } int can(){ for(int i=1;i<n;i++){ if(!G[s[i]-'0'][s[i+1]-'0']){ return i; } } return n; } bool work(int u){ // printf("work %d\n",u); for(int i=1;i<=u;i++){ ans[i]=s[i]; } if(u==n) return 1; ans[u+1]=0; // printf("ans=%s\n",ans+1); // printf("%d\n",s[u+1]-'0'-1); for(int d=s[u+1]-'0'-1;d>=0;d--){ if(G[ans[u]-'0'][d]){ ans[u+1]='0'+d; break; } } if(!ans[u+1]) return 0; for(int i=u+2;i<=n;i++){ for(int d=9;d>=0;d--){ if(G[ans[i-1]-'0'][d]){ ans[i]='0'+d; break; } } } return 1; } void solve(){ scanf("%s",s+1); n=strlen(s+1); ans[n+1]=0; int pos=can(); for(int i=pos;i>=0;i--){ if(work(i)){ printf("%s\n",ans+1);return; } } } int main(){ init(); #ifdef MULTI_CASES _w=scanf("%d",&_t);while(_t--) #endif solve(); return 0; }
C++ 解法, 执行用时: 2ms, 内存消耗: 308KB, 提交时间: 2022-07-08
#include<iostream> #include<vector> #include<cstring> #include<string> using namespace std; int allc[4][3]={1,2,3,4,5,6,7,8,9,10,0,10}; int allmat[16][16]; void fillmat() { memset(allmat,0,256*sizeof(int)); for(int i1=0;i1<4;++i1) for(int j1=0;j1<3;++j1) for(int i2=i1;i2<4;++i2) for(int j2=j1;j2<3;++j2) allmat[allc[i1][j1]][allc[i2][j2]]=1; return ; } void calStr(string oristr) { int slen=oristr.size(); char cstr[512]; memset(cstr,'9',sizeof(char)*512); cstr[slen]='\0'; int prem=0; int t=0; int pren=1; for(;t<slen;++t) { int ttd=oristr[t]-'0'; prem=-1; for(int i=ttd;i>=0;--i) { if(allmat[pren][i]) { prem=i; break; } } if(prem==-1) break; if(prem!=ttd) { cstr[t]=prem+'0'; break; } pren=prem; cstr[t]=prem+'0'; } if(prem==-1) { for(--t;t>=0;--t) { int ttd=cstr[t]-'0'; prem=-1; if(t==0) pren=1; else pren=cstr[t-1]-'0'; for(int i=ttd-1;i>=0;--i) { if(allmat[pren][i]) { cstr[t]=i+'0'; prem=i; break; } } if(prem==-1) cstr[t]='9'; else { cstr[t]=prem+'0'; break; } } } else if(prem==0) { for(++t;t<slen;++t) cstr[t]='0'; } if(cstr[0]=='0') printf("%s\n",cstr+1); else printf("%s\n",cstr); return ; } int main() { //caldps(); int T=0; fillmat(); scanf("%d",&T); for(int i=0;i<T;++i) { string ts; cin>>ts; if(ts.size()==1) cout<<ts; else calStr(ts); } return 0; }
C++14 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2020-08-08
#include <bits/stdc++.h> using namespace std; const int MAXN = 1005; const int MAXM = 10; int len_k = 0; int k[MAXN], ans[MAXN]; int mx[10] = {0,9,9,9,9,9,9,9,9,9}; void read() { char ch = getchar(); while(ch == '\n' || ch == ' ') ch = getchar(); len_k = 0; k[len_k] = 1; while(ch != '\n' && ch != EOF) { k[++len_k] = ch - '0'; ch = getchar(); } } int judge(int x, int y) { if(x == 0) { return y == 0; } if(y == 0) { return x == 0 || x%3 != 0; } int t = x%3, s = y%3; t = t==0 ? 3 : t; s = s==0 ? 3 : s; return (x<=y && t<=s); } // y >= x int find(int x, int y) { if(x == 0) { return 0; } int ans = 0; int res = 10; int t = x%3 == 0 ? 3 : x%3; for(int i = 1; i < MAXM; ++i) { int j = i%3 == 0 ? 3 : i%3; if(i >= x && j >= t && i <= y) { if(y-i < res) { res = y - i; ans = i; } } } return ans; } void answer() { ans[0] = k[0]; ans[1] = k[1]; int i; for(i = 2; i <= len_k; ++i) { if(judge(k[i-1], k[i])) { ans[i] = k[i]; } else { if(k[i] > k[i-1]) { ans[i] = find(k[i-1], k[i]); } else { if(k[i-1]%3 == 1 || k[i-1]%3 == 2) { ans[i] = 0; } else { ans[i] = ans[i-1]; while(ans[i-1] == ans[i]) --i; ans[i] -= 1; } } break; } } ++i; for(; i <= len_k; ++i) { ans[i] = mx[ans[i-1]]; } for(int i = 1; i <= len_k; ++i) { putchar(ans[i]+'0'); } putchar('\n'); } int main() { int t; scanf("%d", &t); for(int i = t; i; --i) { read(); answer(); } return 0; }