本场链接:Codeforces Round #739 (Div. 3)
A. Dislike of Threes
直接枚举即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
int main()
{
vector<int> res;
forn(i,1,100000000)
{
if(res.size() > 2000) break;
if(i % 10 == 3 || i % 3 == 0) continue;
res.push_back(i);
}
int T;scanf("%d",&T);
while(T--)
{
int k;scanf("%d",&k);
printf("%d\n",res[k - 1]);
}
return 0;
}
B. Who‘s Opposite?
先求出具体有多少个\(n\),再看每个数是否合法,最后求出对称的数是谁
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int a,b,c;scanf("%d%d%d",&a,&b,&c);
if(a > b) swap(a,b);
int n = (b - a) * 2;
if(a > n || b > n || c > n) puts("-1");
else
{
if(c > n / 2) c -= n / 2;
else c += n / 2;
if(c < 0 || c > n) puts("-1");
else printf("%d\n",c);
}
}
return 0;
}
C. Infinity Table
直接二分出\(n\)处在哪一批数当中,记为\(c\).根据\(c\)可以求出每个起点.根据需要求的元素距离起点的位置判断应该从起点走还是终点走.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
int main()
{
int T;scanf("%d",&T);
while(T--)
{
ll k;scanf("%lld",&k);
ll l = 0,r = 1e6;
while(l < r)
{
ll mid = l + r + 1 >> 1;
if(k > (mid - 1) * (mid - 1)) l = mid;
else r = mid - 1;
}
ll c = l;
// cout << (c * c - 2 * c + 2) << endl;
if(k - (c * c - 2 * c + 2) < c) printf("%lld %lld\n",1 + k - (c * c - 2 * c + 2),c);
else printf("%lld %lld\n",c,1 + c * c - k);
}
return 0;
}
D. Make a Power of Two
枚举所有2的幂直接求贡献即可.
注意枚举的长度大一点,因为可能合适的不止30.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
const int N = 100;
string s[N];
int fact[N];
int check(string& s,string& t)
{
int n = s.size(),m = t.size();
int idx = 0,res = 0;
forn(i,0,n - 1)
{
while(idx < m && s[i] != t[idx]) ++idx;
if(idx == m || s[i] != t[idx]) break;
++res;++idx;
}
return res;
}
int main()
{
Angel_Dust;
ll fact = 1;
forn(i,0,62)
{
s[i] = to_string(fact);
fact *= 2;
}
int T;cin >> T;
while(T--)
{
string t;cin >> t;
int res = 1e9 + 7;
forn(i,0,62) res = min(res,(int)s[i].size() + (int)t.size() - 2 * check(s[i],t));
cout << res << endl;
}
return 0;
}
E. Polycarp and String Transformation
先对整个字符串求出前缀和:$ cnt[i][j] \(表示:前\)i\(位中\)j\(的出现个数.以及最后出现位置:\) R[i] \(表示:元素\)i$最后出现的位置.
- 求
op序列:显然序列由每个元素最后出现的位置决定,对\(R[i]\)进行排序即可知道求出op. - 求
s:不难注意到s肯定是t的某个前缀,并且所有的前缀中至多有一个合法.如此,先枚举每个前缀,并判断这个前缀执行若干次操作之后得到的串的长度是否就是答t的长度即可得到:可能是答案的串.接下来考虑:该串经过题目的操作之后是否会得到答案串,因为每次操作相当于得到一个当前串的子串再拼接回去,可以维护一个区间表达当前操作的串的区间以及上一步的区间.那么当前操作合法需要保证:区间内的元素个数吻合,并且当前得到的串必须是上一步串的一个子序列(因为可能数量吻合但元素顺序不吻合,必须保证元素出现的顺序,即构成子序列).
如此,模拟检查即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,char> pic;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
#define x first
#define y second
const int N = 5e5+7,SIGMA = 30;
int cnt[N][SIGMA],lastcnt[SIGMA];
char op[SIGMA],ans[N],s[N];
pic R[SIGMA];
bool check(int l1,int r1,int l2,int r2)
{
int idx = l1,res = 0;
forn(i,l2,r2)
{
while(idx <= r1 && s[idx] != s[i]) ++idx;
if(idx == r1 + 1 || s[idx] != s[i]) break;
++res;++idx;
}
return res == r2 - l2 + 1;
}
int main()
{
int T;scanf("%d",&T);
while(T--)
{
forn(i,0,SIGMA - 1) R[i] = {0,‘a‘};
scanf("%s",s + 1);int n = strlen(s + 1),AP = 0;
forn(i,1,n) forn(j,0,25) cnt[i][j] = 0;
forn(i,1,n)
{
forn(j,0,25) cnt[i][j] += cnt[i - 1][j];
++cnt[i][s[i] - ‘a‘];
R[s[i] - ‘a‘] = {i,s[i]};
}
sort(R,R + SIGMA);reverse(R,R + SIGMA);
forn(i,0,SIGMA - 1)
{
if(!R[i].x) continue;
op[AP++] = R[i].y;
}
reverse(op,op + AP);
int p = 0;
forn(i,1,n)
{
int len = i,sum = 0;
forn(k,0,AP - 2)
{
sum += cnt[i][op[k] - ‘a‘];
len += i - sum;
if(len > n) break;
}
if(len != n) continue;
p = i;
break;
}
if(!p) puts("-1");
else
{
forn(i,1,p) ++lastcnt[s[i] - ‘a‘];
int l = 1,r = p,sum = 0;
bool ok = 1;
forn(j,0,25) if(cnt[r][j] - cnt[l - 1][j] != lastcnt[j]) ok = 0;
forn(k,0,AP - 1)
{
int nl = r + 1, nr = r + p - (sum += cnt[p][op[k] - ‘a‘]);
lastcnt[op[k] - ‘a‘] = 0;
forn(j,0,25) if(cnt[nr][j] - cnt[nl - 1][j] != lastcnt[j]) ok = 0;
if(k < AP - 1) if(!check(l,r,nl,nr)) ok = 0;
l = nl;r = nr;
}
if(!ok) puts("-1");
else
{
forn(i,1,p) printf("%c",s[i]);printf(" ");forn(i,0,AP - 1) printf("%c",op[i]);
puts("");
}
}
}
return 0;
}
F1. Nearest Beautiful Number (easy version)
由于\(k\)不大,考虑构造出所有合法的串,在答案内二分即可.
注意位数可以达到10.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
#define int ll
vector<int> K1[20],K2[20];
void dfs(int u,int lim,vector<int>& ans,int x1,int x2,int cur)
{
if(u >= lim)
{
ans.push_back(cur);
return ;
}
dfs(u + 1,lim,ans,x1,x2,cur * 10 + x1);
dfs(u + 1,lim,ans,x1,x2,cur * 10 + x2);
}
signed main()
{
forn(sz,1,11)
{
vector<int>& k_1 = K1[sz],&k_2 = K2[sz];
forn(i,1,9)
{
int cur = 0;
forn(j,1,sz) cur = cur * 10 + i;
k_1.push_back(cur);
}
forn(i,1,9) forn(j,0,9)
{
int cur = i;
dfs(1,sz,k_2,i,j,cur);
}
sort(k_1.begin(),k_1.end());sort(k_2.begin(),k_2.end());
}
int T;scanf("%lld",&T);
while(T--)
{
int n,k;scanf("%lld%lld",&n,&k);
int last = 0,last2 = 0,sz = 0;
int x = n;
while(x)
{
last = x % 10;
x /= 10;
++sz;
}
vector<int>& k_1 = K1[sz],&k_2 = K2[sz];
int res = *lower_bound(k_1.begin(),k_1.end(),n);
if(k == 2) res = min(res,*lower_bound(k_2.begin(),k_2.end(),n));
printf("%lld\n",res);
}
return 0;
}
F2. Nearest Beautiful Number (hard version)
我们考虑这个题的本质做法:枚举\(x >= n\)并检查\(x\)是否合法.但是显然这样太慢了,那么如何加速这个过程呢?
如果我们当前的串不合法,那么整个串不同元素的个数是超过限制\(k\)的.设最大合法前缀的位置为\(p\),显然\(p\)不是最后一个元素的位置.如果加的个数影响不到\(p+1\),那么加多少都是白费:因为不影响到\(p+1\)那肯定没用,这个前缀就已经不合法了.所以最少最少应该让\(p+1\)这个位置产生\(+1\),而最小的时候应该是恰好加到这一位\(+1\),那么$ p + 1 \(的前缀整体\)+1$,后面全部置0即可.
那么进行若干次迭代:每次找到这样一个最大的前缀的位置,让以\(p+1\)为末尾的前缀整体$ +1 $,后面全部赋\(0\).这样直到元素合法即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i,x,n) for(int i = x;i <= n;++i)
#define forr(i,x,n) for(int i = n;i >= x;--i)
#define Angel_Dust ios::sync_with_stdio(0);cin.tie(0)
signed main()
{
Angel_Dust;
int T;cin >> T;
while(T--)
{
string s;int k;cin >> s >> k;
int n = s.size();
while(1)
{
set<int> st;
for(auto& _ : s) st.insert(_);
if(st.size() <= k) break;
int idx = 0;
st = set<int>();
while(1)
{
st.insert(s[idx]);
if(st.size() > k)
{
while(s[idx] == ‘9‘) --idx;
++s[idx];
forn(j,idx + 1,n - 1) s[j] = ‘0‘;
break;
}
++idx;
}
}
cout << s << endl;
}
return 0;
}