Codeforces Round #739 (Div. 3)
可能是一开始大佬都写F1去了，我在D写完后发现F过的人数比E多了好多（个位数与十位数），以为F1比较简单，就直接开F1了，但自己分类讨论老是考虑不完整，导致罚时直接垮掉
本来已经不想开E了，结果发现延长了15分钟，尝试着开一开，结果发现很水……现在在怀疑人生了嗯。
UPD: F2已补
A - Dislike of Threes
思路
数据范围小（(kle 1000)），暴力预处理后输出即可。
代码
// URL: https://codeforces.com/contest/1560/problem/0
// Problem: A. Dislike of Threes
// Contest: Codeforces - Codeforces Round #739 (Div. 3)
// Time Limit: 1000 ms
// Memory Limit: 256 MB
// Author: StelaYuri
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=998244353;
const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
void debug(){cerr<<'
';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);}
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}
vector<int> vec;
int ck(int a)
{
if(a%10==3||a%3==0)return 0;
return 1;
}
void init()
{
int p=1;
while(vec.size()<1000)
{
if(ck(p))
vec.pb(p);
p++;
}
}
void solve()
{
int n;
cin>>n;
cout<<vec[n-1]<<'
';
}
int main()
{
closeSync;
init();
multiCase
{
solve();
}
return 0;
}
B - Who's Opposite?
思路
根据题意，(|a-b| imes 2)可以得出这个环的点数(n)
那么两点在环内相互对视的充分必要条件就是(apmfrac n 2=b)
最后只需要(cle n)，便能得出(c)对视的点
代码
// URL: https://codeforces.com/contest/1560/problem/B
// Problem: B. Who's Opposite?
// Contest: Codeforces - Codeforces Round #739 (Div. 3)
// Time Limit: 1000 ms
// Memory Limit: 256 MB
// Author: StelaYuri
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=998244353;
const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
void debug(){cerr<<'
';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);}
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}
void solve()
{
ll a,b,c;
cin>>a>>b>>c;
if(a>b)
swap(a,b);
ll n=(b-a)*2;
if(b!=(a+n/2-1)%n+1||c>n)
{
cout<<"-1
";
return;
}
cout<<(c+n/2-1)%n+1<<'
';
}
int main()
{
closeSync;
multiCase
{
solve();
}
return 0;
}
C - Infinity Table
思路
假设数字(1)位于第(1)层，数字(2,3,4)位于第(2)层，……
发现第(i)层的数字个数为(i imes 2-1)
那么假设当前求的数字(k)位于第(x+1)层，那么前(x)层的总数便是(x^2)
由于数字(k)比较大，其位于的层数可以直接(sqrt {k-1}+1)得出，或是通过二分得出（二分比较靠谱）
于是我们发现(k=10^9)时，其所在层的编号也只有几万，并且数据组数(Tle 100)，所以这里直接上笨方法，循环处理即可
代码
// URL: https://codeforces.com/contest/1560/problem/C
// Problem: C. Infinity Table
// Contest: Codeforces - Codeforces Round #739 (Div. 3)
// Time Limit: 1000 ms
// Memory Limit: 256 MB
// Author: StelaYuri
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=998244353;
const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
void debug(){cerr<<'
';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);}
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}
void solve()
{
ll k;
cin>>k;
ll l=1,r=100000;
while(l<=r)
{
ll mid=l+r>>1;
ll t=mid*2-1;
ll sum=(1+t)/2*mid;
if(sum<k)
l=mid+1;
else
r=mid-1;
} //二分出k位于第l层，这种二分方式最终状态为l==r+1
//cout<<r<<' ';
k-=(1+r*2-1)/2*r; //也就是r*r
k--;
int x=1,y=l;
if(k==0)
{
cout<<x<<' '<<y<<'
';
return;
}
repp(i,1,l)
{
k--;
x++;
if(k==0)
{
cout<<x<<' '<<y<<'
';
return;
}
}
repp(i,1,l)
{
k--;
y--;
if(k==0)
{
cout<<x<<' '<<y<<'
';
return;
}
}
}
int main()
{
closeSync;
multiCase
{
solve();
}
return 0;
}
D - Make a Power of Two
思路
做法是先找出与(2^i)的前缀相同的最长子序列，那么原长度减去最长子序列长度就是要删除的字符个数，最后再加上(2^i)减去匹配上的前缀后的长度，也就是需要添加的字符个数
例如对于(1052)，令其与(2^{10}=1024)进行匹配，得出与(1024)的前缀相同的最长子序列为(102)，则说明原数字里的(5)需要删除，删除后需要再加一个(4)在末尾才能得到(1024)
猜想是对(i=0sim 62)（long long最大值为(2^{63}-1)）的每个(2^i)都做一遍匹配，找最小值就是答案——由于(2^{62})次方已经是一个(19)位数，所以这个幂次如果再大也只会徒增删除次数
代码
// URL: https://codeforces.com/contest/1560/problem/D
// Problem: D. Make a Power of Two
// Contest: Codeforces - Codeforces Round #739 (Div. 3)
// Time Limit: 1000 ms
// Memory Limit: 256 MB
// Author: StelaYuri
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=998244353;
const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
void debug(){cerr<<'
';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);}
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}
int ar[20],br[20];
int ck(ll a,ll b)
{
int pa=0,pb=0;
while(a) //先按位将a,b倒置在数组中，并求出长度pa,pb
{
ar[pa++]=a%10;
a/=10;
}
while(b)
{
br[pb++]=b%10;
b/=10;
}
int j=pb-1,r=0; //j+1为待添加的数量，r为待删除的数量
per(i,pa-1,0)
{
if(j>=0&&ar[i]==br[j])
j--;
else
r++;
}
return j+1+r;
}
void solve()
{
int n;
cin>>n;
int ans=INF;
rep(i,0,62)
ans=min(ans,ck(n,1LL<<i));
cout<<ans<<'
';
}
int main()
{
closeSync;
multiCase
{
solve();
}
return 0;
}
E - Polycarp and String Transformation
思路
发现如果只看每种字符最后一次出现的所在位置，拼接起来后一定就是删除顺序
例如(haaha)这个例子，从后往前看，只在每种字符第一次出现时记录下来（或是从前往后看，只在最后一次出现时记录），于是得到删除顺序为(ha)
于是根据删除顺序，开始检查是否存在一个原串是按照这个顺序操作得到
由题意得，原串一定是给定字符串的某个前缀，并且最小长度是(max{L[ch_i]})，其中(L[ch_i])为每种字符第一次出现的位置
由于长度有(5 imes 10^5)，我们没法枚举每种长度的前缀，再去(O(n))检查这个前缀是否合法
但发现，可以在枚举每种长度的前缀时，只看每种字符出现的次数，模拟删除顺序后便能够得到最终长度，此时只有在得到的长度与输入的字符串长度相同时，再去进行(O(n))检查其合法性，发现这样只需要(O(26))就可以做完一次粗略的check
代码
// URL: https://codeforces.com/contest/1560/problem/E
// Problem: E. Polycarp and String Transformation
// Contest: Codeforces - Codeforces Round #739 (Div. 3)
// Time Limit: 3000 ms
// Memory Limit: 256 MB
// Author: StelaYuri
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=998244353;
const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
void debug(){cerr<<'
';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);}
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}
int l[26],r[26];
int vis[26];
int cnt[26];
string s,t;
bool finalcheck(int right)
{
int pos=right+1;
mst(vis,0);
for(char c:t)
{
vis[c-'a']=1; //表示这种字符已经被删除
rep(i,0,right)
{
if(vis[s[i]-'a']) //如果已经被删除就跳过
continue;
if(s[i]==s[pos])
{
pos++;
}
else
{
return false;
}
}
}
return true;
}
void solve()
{
cin>>s;
int len=s.size();
mst(vis,0);
t="";
per(i,len-1,0) //从后向前，第一次出现就记录下这个字符，得到删除序列t
{
if(!vis[s[i]-'a'])
{
vis[s[i]-'a']=1;
t=s[i]+t;
}
}
mst(l,-1);
mst(r,-1);
repp(i,0,len) //记录每种字符第一次出现位置与最后一次出现位置
{
if(l[s[i]-'a']==-1)
l[s[i]-'a']=i;
r[s[i]-'a']=i;
}
int st=0;
repp(i,0,26)
{
if(l[i]!=-1) //对于每种出现过的字符，取第一次出现位置的最大值作为原串的最小长度
st=max(st,l[i]);
}
mst(cnt,0);
repp(i,0,st) //记录前缀每种字符出现的次数
cnt[s[i]-'a']++;
while(st<len)
{
cnt[s[st]-'a']++;
int sum=0;
repp(i,0,26)
sum+=cnt[i]; //第一次是将原串全部拼接上
int r=sum;
for(char c:t)
{
sum-=cnt[c-'a']; //按删除顺序去除该字符的影响
r+=sum; //继续拼接
}
if(r==len&&finalcheck(st)) //只要长度对的上，再进行最终检查
{
rep(i,0,st)
cout<<s[i];
cout<<' '<<t<<'
';
return;
}
st++;
}
cout<<-1<<'
';
}
int main()
{
closeSync;
multiCase
{
solve();
}
return 0;
}
F1. Nearest Beautiful Number (easy version)
思路
虽然但是，强烈不建议看我的代码，写得很乱容易看自闭，看思路即可
另提一点，经solemntee佬提点，二进制枚举后存起来直接二分答案即可，而我第一发没有优化T掉了之后就不敢再往这个方向写了（结果发现(kle 2)时情况确实很少，很可惜），代码很简单，可以看看
这里是仅针对(kle 2)的奇怪思路，第三种解法见hard版本
首先判断输入的数是否已经满足条件，如果是直接输出
对于(k=1)的情况，明显对于(1sim 9)每个数位都做一遍取最小即可
对于(k=2)的情况（能讨论到这里说明数位上至少有(3)种数字）
从高位向低位找，先找出现的第一种数(a)，再找出第二种数(b)
即假设对于(223314)，得(a=2,b=3)
记(mn=min(a,b), mx=max(a,b))
然后找到按顺序出现的第三种数字(c)：
-
如果(clt mn)，说明从这个位置开始，将后面的数全部设置为(mn)时，值最小；
-
如果(mnlt clt mx)，说明(c)位置的数不能换成(mn)（会变小），但换成(mx)时是符合条件的，并且此时应将低于(c)位的所有数位都设置成(mn)最优；
-
如果(cgt mx)，此时(c)将不能修改为(a,b)任一个：
- 此时，(a,b,c)不同，且(c)最大，说明(blt 9)，并且(a)是最高位的数位，如果我们要修改出现的数(a,b)，说明最优操作便是(b:=b+1)
- 倘若(b:=b+1)，那么从原本(b)出现的第一个位置的后一个数位开始，都应当设置成(min(a,b))最优
- 考虑一种特殊情况，原本(a=b+1)，在执行完(b:=b+1)后(a=b)成立，此时不应当将后面的数位都设置为(min(a,b))，而是直接设置为(0)才是最优
- 还有一种方法，就是从(c)位置开始向前寻找最后一个出现(mn)的位置，如果将这个(mn)改为(mx)， 说明其后的所有数位都设置为(mn)也是个极优解
代码一（分类讨论|别看，只是挂着）
// URL: https://codeforces.com/contest/1560/problem/F1
// Problem: F1. Nearest Beautiful Number (easy version)
// Contest: Codeforces - Codeforces Round #739 (Div. 3)
// Time Limit: 1000 ms
// Memory Limit: 256 MB
// Author: StelaYuri
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=998244353;
const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
void debug(){cerr<<'
';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);}
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}
ll ans;
ll n;
void ck1(int x)
{
ll d=x;
if(d>=n)
{
ans=min(ans,d);
return;
}
rep(i,1,10)
{
d=d*10+x;
if(d>=n)
{
ans=min(ans,d);
return;
}
}
}
int d[15];
void solve()
{
int k;
cin>>n>>k;
bool v[10];
mst(v,false);
int len=0,m=n,t=0;
while(m)
{
int i=m%10;
if(!v[i])
{
v[i]=true;
t++;
}
m/=10;
d[len++]=i;
}
if(t<=k)
{
cout<<n<<'
';
return;
}
ans=LINF;
if(k==1)
{
rep(i,1,9)
ck1(i);
}
else
{
ans=1;
rep(i,1,len)
ans*=10;
rep(i,1,9)
ck1(i);
int a=d[len-1],b=-1;
per(i,len-2,0)
{
if(d[i]!=a)
{
b=d[i];
int mn=min(a,b),mx=max(a,b);
per(j,i-1,0)
{
if(d[j]!=a&&d[j]!=b)
{
if(mn>d[j])
{
d[j]=mn;
per(k,j-1,0)
d[k]=mn;
ll ansd=0;
per(k,len-1,0)
ansd=ansd*10+d[k];
ans=min(ans,ansd);
cout<<ans<<'
';
return;
}
else if(mx>d[j])
{
d[j]=mx;
per(k,j-1,0)
d[k]=mn;
ll ansd=0;
per(k,len-1,0)
ansd=ansd*10+d[k];
ans=min(ans,ansd);
cout<<ans<<'
';
return;
}
else
{
ll ansd=0;
repp(k,j,len)
{
if(d[k]==mn)
{
per(uu,len-1,k+1)
ansd=ansd*10+d[uu];
ansd=ansd*10+mx;
per(uu,k-1,0)
ansd=ansd*10+mn;
ans=min(ans,ansd);
break;
}
}
d[i]++; b++;
mn=min(a,b);
if(a==b)mn=0;
per(k,i-1,0)
d[k]=mn;
ansd=0;
per(k,len-1,0)
ansd=ansd*10+d[k];
ans=min(ans,ansd);
cout<<ans<<'
';
return;
}
}
}
break;
}
}
}
cout<<ans<<'
';
}
int main()
{
closeSync;
multiCase
{
solve();
}
return 0;
}
代码二（二进制枚举预处理）
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=998244353;
const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
void debug(){cerr<<'
';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);}
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}
set<ll> st[2];
void deal(int x,int y)
{
int a[2]={x,y};
rep(bit,1,9)
{
repp(sta,0,1<<bit)
{
int t=0,d=1;
repp(i,0,bit)
{
t+=d*a[sta>>i&1];
d*=10;
}
st[1].insert(t);
}
}
}
void init()
{
st[0].insert(1111111111);
st[1].insert(1000000000);
st[1].insert(1111111111);
rep(i,1,9)
{
int d=i;
st[0].insert(d);
st[1].insert(d);
rep(j,1,8)
{
d=d*10+i;
st[0].insert(d);
st[1].insert(d);
}
}
rep(i,1,9)
deal(0,i);
rep(i,1,9)
rep(j,i+1,9)
deal(i,j);
}
void solve()
{
ll n,k;
cin>>n>>k;
cout<<*st[k-1].lower_bound(n)<<'
';
}
int main()
{
closeSync;
init();
multiCase
{
solve();
}
return 0;
}
F2 - Nearest Beautiful Number (hard version)
思路
要保证答案尽可能小，于是我们每次固定当前数前(k)种数位不变，将第(k+1)种数位所在位置的数模拟(+1)，其后的所有数位只需要置(0)即可
由于是直接确定了前(k)位数位，所以操作次数应当在百次以内
代码
// URL: https://codeforces.com/contest/1560/problem/F2
// Problem: F2. Nearest Beautiful Number (hard version)
// Contest: Codeforces - Codeforces Round #739 (Div. 3)
// Time Limit: 1000 ms
// Memory Limit: 256 MB
// Author: StelaYuri
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=998244353;
const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
void debug(){cerr<<'
';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);}
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}
int digits(int x)
{
int r=0;
while(x)
{
r|=1<<(x%10);
x/=10;
}
return __builtin_popcount(r);
}
void solve()
{
int n,k;
cin>>n>>k;
while(digits(n)>k)
{
int m=n/10,t=10;
while(digits(m)>k)
{
m/=10;
t*=10;
}
t/=10;
n/=t;
n++;
n*=t;
}
cout<<n<<'
';
}
int main()
{
closeSync;
multiCase
{
solve();
}
return 0;
}
https://blog.csdn.net/qq_36394234/article/details/119792892