首页 > 代码库 > bzoj3374[Usaco2004 Mar]Special Serial Numbers 特殊编号*
bzoj3374[Usaco2004 Mar]Special Serial Numbers 特殊编号*
bzoj3374[Usaco2004 Mar]Special Serial Numbers 特殊编号
题意：
求比一个数大的最小的一半以上的数位相同的数。数位数≤100。
题解：
模拟题。从低位枚举到高位，对于每一位枚举比原数该位大的数，同时枚举这一位之后要由0和哪一个数组成，最后得到一个最小的数输出。具体看代码。
有点像NOIP的那道Jam的计数法。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 110 6 using namespace std; 7 8 char str[maxn]; int sm[10][maxn],num[maxn],n; 9 int main(){10 scanf("%s",str+1); n=strlen(str+1);11 inc(i,1,n){num[i]=str[i]-‘0‘; inc(j,0,9)sm[j][i]=sm[j][i-1]; sm[num[i]][i]++;}12 inc(i,num[n],9){13 inc(j,0,9)if(sm[j][n-1]+(i==j)>n/2){inc(k,1,n-1)printf("%d",num[k]); printf("%d",i); return 0;}14 }15 for(int i=n-1;i>=1;i--){16 inc(j,num[i]+1,9){17 int mn1=n-i+1,mn2;18 inc(k,0,9)if(n/2+1-(sm[k][i-1]+(k==j))<mn1)mn1=n/2+1-(sm[k][i-1]+(k==j)),mn2=k;19 if(mn1!=n-i+1){20 inc(k,1,i-1)printf("%d",num[k]); printf("%d",j); inc(k,1,n-i-mn1)printf("0");21 inc(k,1,mn1)printf("%d",mn2); return 0;22 }23 }24 }25 }
20160912
bzoj3374[Usaco2004 Mar]Special Serial Numbers 特殊编号*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。