Largest Beautiful Number CodeForces

大意: 定义一个好数为位数为偶数, 且各位数字重排后可以为回文, 对于每个询问, 求小于$x$的最大好数.

假设$x$有$n$位, 若$n$为奇数, 答案显然为$n-1$个9. 若为偶数, 我们想让答案尽量大, 那么就要尽量调整$x$的低位数, 从低位到高位遍历, 假设当前处理到第$i$位, 对于判断重排后回文可以用一个长为10的二进制数来判断, 假设$[i+1,n]$状态为$t$, 那么问题就转化为求最大的小于$t$且二进制状态为$s$的数, 贪心填数即可, 若对于每一位都无解答案就为$n-2$个9.

第一次写这种涉及数位的贪心模拟, 感觉还是挺烦的, 进位要多注意, 贪心时的因为要多次进行可行性判断, 一定要写成函数.

#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <math.h>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <string.h>

#include <bitset>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define hr putchar(10)

#define pb push_back

#define lc (o<<1)

#define rc (lc|1)

#define mid ((l+r)>>1)

#define ls lc,l,mid

#define rs rc,mid+1,r

#define x first

#define y second

#define io std::ios::sync_with_stdio(false)

#define endl '\n'

#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int P = 1e9+7, INF = 0x3f3f3f3f;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}

ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}

inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}

//head

#ifdef ONLINE_JUDGE

const int N = 1e6+10;

#else

const int N = 111;

#endif

char s[N];

int n, f[N], cnt[N], num[N];

int pos[N], p[15];

int chk(int i, int sta, int flag) {

	if (i>n) return 1;

	int sz = 0;

	REP(i,0,9) if (sta>>i&1) p[++sz]=i;

	if (sz>n-i+1||(sz&1)!=(n-i+1&1)) return 0;

	if (flag) return 1;

	if (i+pos[i]-1+sz>n) return 0;

	if (i+pos[i]-1+sz==n) {

		int ok = 0;

		REP(j,i+pos[i],n) {

			if (s[j]<p[j-i-pos[i]+1]) return 0;

			if (s[j]>p[j-i-pos[i]+1]) return 1;

		}

		return 0;

	}

	return 1;

}

void work() {

	scanf("%s", s+1);

	n = strlen(s+1);

	if (n&1) {

		REP(i,1,n-1) putchar('9');hr;

		return;

	}

	REP(i,1,n) s[i]-='0';

	REP(i,1,n) f[i]=f[i-1]^(1<<s[i]);

	pos[n+1]=0;

	PER(i,1,n) pos[i]=s[i]?0:pos[i+1]+1;

	PER(i,1,n) {

		int sta = f[i-1];

		if (!chk(i,sta,0)) continue;

		int flag = 0;

		REP(j,i,n-1) {

			if (!flag) {

				if (chk(j+1,sta^1<<s[j],flag)) {

					sta ^= s[j];

					continue;

				}

				flag = 1;

				PER(k,0,s[j]-1) if (chk(j+1,sta^1<<k,flag)) {

					s[j] = k, sta ^= 1<<k;

					break;

				}

			}

			else {

				PER(k,0,9) if (chk(j+1,sta^1<<k,1)) {

					s[j] = k, sta ^= 1<<k;

				}

			}

		}

		REP(j,0,9) if (sta>>j&1) s[n]=j;

		if (!s[1]) break;

		REP(j,1,n) printf("%d", s[j]);hr;

		return;

	}

	REP(i,1,n-2) putchar('9');hr;

}

int main() {

	int t;

	scanf("%d", &t);

	while (t--) work();

}

巴特西

Largest Beautiful Number CodeForces - 946E (贪心)

最新文章

热门文章