Codeforces Round #739 (Div. 3)

可能是一开始大佬都写F1去了，我在D写完后发现F过的人数比E多了好多（个位数与十位数），以为F1比较简单，就直接开F1了，但自己分类讨论老是考虑不完整，导致罚时直接垮掉

本来已经不想开E了，结果发现延长了15分钟，尝试着开一开，结果发现很水……现在在怀疑人生了嗯。

A - Dislike of Threes

思路

数据范围小（\(k\le 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<<'\n';}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]<<'\n';
}
int main()
{
    closeSync;
    init();
    multiCase
    {
        solve();
    }
    return 0;
}

B - Who's Opposite?

思路

根据题意，\(|a-b|\times 2\)可以得出这个环的点数\(n\)

那么两点在环内相互对视的充分必要条件就是\(a\pm\frac n 2=b\)

最后只需要\(c\le 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<<'\n';}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\n";
        return;
    }
    cout<<(c+n/2-1)%n+1<<'\n';
}
int main()
{
    closeSync;
    multiCase
    {
        solve();
    }
    return 0;
}

C - Infinity Table

思路

假设数字\(1\)位于第\(1\)层，数字\(2,3,4\)位于第\(2\)层，……

发现第\(i\)层的数字个数为\(i\times 2-1\)

那么假设当前求的数字\(k\)位于第\(x+1\)层，那么前\(x\)层的总数便是\(x^2\)

由于数字\(k\)比较大，其位于的层数可以直接\(\sqrt {k-1}+1\)得出，或是通过二分得出（二分比较靠谱）

于是我们发现\(k=10^9\)时，其所在层的编号也只有几万，并且数据组数\(T\le 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<<'\n';}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<<'\n';
        return;
    }
    repp(i,1,l)
    {
        k--;
        x++;
        if(k==0)
        {
            cout<<x<<' '<<y<<'\n';
            return;
        }
    }
    repp(i,1,l)
    {
        k--;
        y--;
        if(k==0)
        {
            cout<<x<<' '<<y<<'\n';
            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=0\sim 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<<'\n';}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;
    repp(i,0,62)
        ans=min(ans,ck(n,1LL<<i));
    cout<<ans<<'\n';
}
int main()
{
    closeSync;
    multiCase
    {
        solve();
    }
    return 0;
}

E - Polycarp and String Transformation

思路

发现如果只看每种字符最后一次出现的所在位置，拼接起来后一定就是删除顺序

例如\(haaha\)这个例子，从后往前看，只在每种字符第一次出现时记录下来（或是从前往后看，只在最后一次出现时记录），于是得到删除顺序为\(ha\)

于是根据删除顺序，开始检查是否存在一个原串是按照这个顺序操作得到

由题意得，原串一定是给定字符串的某个前缀，并且最小长度是\(\max\{L[ch_i]\}\)，其中\(L[ch_i]\)为每种字符第一次出现的位置

由于长度有\(5\times 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<<'\n';}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<<'\n';
            return;
        }
        st++;
    }
    cout<<-1<<'\n';
}
int main()
{
    closeSync;
    multiCase
    {
        solve();
    }
    return 0;
}

F1. Nearest Beautiful Number (easy version)

思路

想的情况有点多，代码写得又臭又长，别人都想得很简单的样子，所以就放个代码在这吧……

待会补补这里的思路

代码

// 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<<'\n';}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<<'\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<<'\n';
                            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<<'\n';
                            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<<'\n';
                            return;
                        }
                    }
                }
                break;
            }
        }
    }
    cout<<ans<<'\n';
}
int main()
{
    closeSync;
    multiCase
    {
        solve();
    }
    return 0;
}