「NOIP模拟赛」number
题目说明
一个集合有如下元素：1是集合元素；若P是集合的元素，则2*P+1，4*P+5也是集合的元
素，取出此集合中最小的K个元素，按从小到大的顺序组合成一个多位数，现要求从中删除M
个数位上的数字，使得剩下的数字最大，编程输出删除前和删除后的多位数字。
注：不存在所有数被删除的情况。
输入格式
输入仅一行，K，M的值，K，M均小于等于30000。
输入格式
输出为两行，第一行为删除前的数字，第二行为删除后的数字。
样例
Sample Input
5 4
Sample Output
137915
95
相关信息
文件名: number.pas/c/cpp
输入文件: number.in
输出文件: number.out
时限: 1s
空间限制: 64MB
题解
发现第一问大概枚举到420w即可
第二问用个栈贪心，保证前面尽量大
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #define ll long long #define N 4250000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int K,m,tot; int ans,top; bool a[4300000]; int b[200005],t[10]; int q[200005]; void add(int x) { int top=0; while(x) { t[++top]=x%10; x/=10; } for(int i=top;i;i--) b[++tot]=t[i]; } void solve() { int now=0; for(int i=1;i<=tot;i++) { while(q[top]<b[i]&&top) { top--; now++; if(m==now)return; } q[++top]=b[i]; } } int main() { K=read();m=read(); a[1]=1; for(int i=1;i<=N;i++) if(a[i]) { if(i*2+1<=N)a[i*2+1]=1; if(i*4+5<=N)a[i*4+5]=1; } for(int i=1;i<=N;i++) if(a[i]) { ans++; add(i); if(ans==K)break; } for(int i=1;i<=tot;i++)printf("%d",b[i]); puts(""); solve(); for(int i=1;i<=top;i++)printf("%d",q[i]); for(int i=m+top+1;i<=tot;i++)printf("%d",b[i]); puts(""); return 0; } |
Subscribe