Codeforces Round #739 (Div. 3)
传送门
A. Dislike of Threes
题意：从1开始，如果一个数是3的倍数或个位数上是3就跳过，问第n个数是什么。
思路：根据题意模拟即可。
代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
int tmp = 0, cnt = 0;
if(n<=2) {
cout << n << endl;
continue;
}
if(n==3) {
cout << 4 << endl;
continue;
}
bool flag=false;
while(cnt!=n) {
cnt++;tmp++;
if(tmp<=2) continue;
else if((tmp%3==0)||(tmp%10==3)) {
cnt--;
continue;
}
}
cout << tmp << endl;
}
return 0;
}B. Who's Opposite?
题意：由一定数量的人围城了一个圈，现在告诉你a的对面是b，求出c的对面是谁，如果不存在这样的圈输出-1。
思路：通过a和b的差值d易得这个圈有多少人。如果人数少于c或者少于b，则不存在一个这样的圈，因为人数至少是max{a,b,c},否则根据c和d的值可以求出c对面是谁。
代码；
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
int a, b, c;
cin >> a >> b >> c;
if(a>b)
swap(a, b);
int d = abs(a - b);
int tail = b + d - a;
if ((tail < c) || tail < b)
cout << -1 << endl;
else {
c += d;
if(c>tail) {
c -= tail;
}
cout << c << endl;
}
}
return 0;
}C. Infinity Table
题意：在一个无数行和无数列的表格中按一定规则填1，2，3，...，规则如下：从（1，1）开始，如果该位置左边未填且可以填则从右往左一直填下去直至不能填后返回第一行第一个未填数的位置，接着往下填，期间如果遇到左边未填则再以此从右往左填数，周而复始。输出数字n的行和列。
思路：自己按照规则多填几行后发现第n行第一列的数为,且由
组成的表格中，第n行和第n列一共有2*n-1个数，且从右往左从上往下以此递减。所以按照这个规律模拟即可。
代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--) {
double k;
cin >> k;
double tmp1 = ceil(sqrt(k));
double tmp2 = sqrt(k);
if(tmp1==tmp2) {
cout << int(tmp1) << " " << 1 << endl;
continue;
}
else {
int d = int(tmp1 * tmp1) - int(k);
if(d<tmp1) {
cout << int(tmp1) << " " << 1 + d << endl;
}
else
cout << 2*int(tmp1)-1-d << " " << int(tmp1) << endl;
}
}
return 0;
}D. Make a Power of Two
题意：
给你一个数n，每次操作你可以对该数进行删除或增加一位数，为最少几次让这个数变成2的幂次方。
思路:这道题用字符串来做，我们可以想象成再n的后面加上一个由2的幂次方组成的字符串，然后再删除他们相同的字符，剩下的长度就是我们的操作数。所以枚举n每一位与2的幂次方有多少个相同的数，然后维护一个最小值即可。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
int main()
{
int t;
cin >> t;
while (t--)
{
string s;
cin >> s;
int ans = 0x3f3f3f3f;
for (int i = 0; i < 64; i++)
{
ll num = 1ll << i;
string t = to_string(num);
int cnt = 0;
for (int j = 0; j < int(s.length()); j++)
{
if (cnt < int(t.length()) && t[cnt] == s[j])
{
cnt++;
}
}
ans = min(ans, int(s.length() + t.length() - 2 * cnt));
}
cout << ans << endl;
}
return 0;
}E：
题意：字符串t是由字符串s每次删除一种字符后以此连接组成的。现在告诉你字符串t让你求出字符串s和删除顺序。
思路：删除顺序就是从后往前遍历一遍字符串t，记录下每种字母第一次出现的顺序然后reserve一下就是删除顺序。对于字符串t我们可以知道，第i个删除的字母它会被再复制i-1次，所以这个字母在t中的数量cnt一定是i的倍数。所以我们只要通过删除顺序计算一下该字母的数量是否是i的倍数即可,再记录下每个字符出现的数量sum，即，则t中前sum个字符构成的子串就是对应的字符串s。
特例：数量满足要求，但顺序改变，所以得出相应的字符串s和删除顺序后，我们还要再根据删除顺序再模拟一遍得到一个新的字符串与t进行比较，如果不相等输出-1。否则输出s和对应的删除顺序。
代码：
#include <bits/stdc++.h>
using namespace std;
int vis[30];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--) {
memset(vis, 0, sizeof(vis));
string s;
cin >> s;
string s3 = "";
for (int i = int(s.length() - 1); i >= 0;i--) {
int tmp = s[i] - 'a';
vis[tmp]++;//统计每种字符数量
if(vis[tmp]==1) {
s3 += s[i];//记录删除顺序
}
}
reverse(s3.begin(), s3.end());
string s1 = "";
string tmp = "";
int sum = 0;
bool flag = false;
for (int i = 0; i < int(s3.length()); i++) {
int cnt = vis[s3[i] - 'a'];
if (cnt % (i + 1) != 0) {
flag = true;
break;
}
sum += cnt / (i + 1);
}
string s2 = "", s4 = "";
for (int i = 0; i < sum; i++) {
s2 += s[i];
s4 += s[i];
}
memset(vis, 0, sizeof(vis));
for (int i = 0; i < int(s3.length());i++) {
vis[s3[i] - 'a'] = 1;//标记该字符已删除
for (int j = 0; j < int(s4.length()); j++) {
if(vis[s4[j]-'a']==0) {//加上未删除部分
s2 += s4[j];
}
}
}
if(s2!=s) {
flag = true;
}
if (flag)
{
cout << -1 << endl;
continue;
}
else
{
for (int i = 0; i < sum; i++)
{
cout << s[i];
}
cout << " ";
}
cout << s3 << endl;
}
return 0;
}F1. Nearest Beautiful Number (easy version)
题意：给你两个数字n和k，输出一个x，x满足x大于等n且，x中数字种类的个数小于等于k，easy版本中，k为1或2。
思路：当k=1时，x中每一位都应该相等，所以我们用字符串会比较好处理，输出每一位都相等且大于或等于x的字符串，从大到小模拟一下即可。
当k=2时，此时x中要么一种数字要么两种，我们根据k=1时的操作得出此时满足题意最小的x（此时每一位都相等）。因为最多只有两种数字，我们枚举a和b，b严格大于a，比较n中的每一位，如果该位置i上的数小于b，我们构造一个临时的字符串tmp=n,如果该位置i上的数tmp[i]小于a,我们就将这个数更新为a,否则更新为b，然后再将i之后的每一位数字都更新为a，保证只有两种数且结果尽可能的小。然后将tmp每次与x比较维护一个最小值。
代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t--) {
string n;
int k;
cin >> n >> k;
if(k==1) {
string ans(n.length(), '9');
for (char ch = '8'; ch >= '0';ch--) {
string tmp(n.length(), ch);
if(tmp>=n) {
ans = tmp;
}
}
cout << ans << endl;
}
else {
string ans(n.length(), '9');
for (char ch = '8'; ch >= '0'; ch--)
{
string tmp(n.length(), ch);
if (tmp >= n)
{
ans = tmp;
}
}
for (char a = '0'; a <= '9';a++) {
for (char b = a + 1; b <= '9';b++) {
bool flag = true;
for (int i = 0; i < int(n.length());i++) {
if(n[i]<b) {
string tmp = n;
if(tmp[i]<a)
tmp[i] = a;
else
tmp[i] = b;
for (int j = i + 1; j < int(n.length());j++) {
tmp[j] = a;
}
if (ans > tmp) {
ans = tmp;
}
}
if (n[i] != a && n[i] != b) {
flag = false;
break;
}
}
if(flag) {
ans = n;
}
}
}
cout << ans << endl;
}
}
return 0;
}F2. Nearest Beautiful Number (hard version)
题意：如easy,k的范围为1~10。
思路：
方法一： 利用set的互异性，如果枚举每一位数插入set中，如果此时s.size()>k，将该数加1，后面全置零，直至s.size()<=k。注意如果此时n[i]=='9',要不断i--,直至num[i]!='9'，再将此时位置上的数加1，后面全置零。
代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t; cin >> t;
while(t--) {
string n;
int k;
cin >> n >> k;
while(true) {
set<char> s;
for (int i = 0; i < int(n.length());i++) {
s.insert(n[i]);
}
if (int(s.size()) <= k) {
cout << n << endl;
break;
}
s.clear();
for (int i = 0; i < int(n.length());i++) {
s.insert(n[i]);
if(int(s.size())>k) {
while(n[i]=='9') {
i--;
}
n[i]+=1;
for (int j = i + 1; j < int(n.length());j++) {
n[j] = '0';
}
break;
}
}
}
}
return 0;
}方法二：
思路：dfs。我们通过用于记录二进制上的1的个数来判断。比如，当前数字是5，mask|(1<<5)，如果后面还有5，但由于或运算的规则不影响结果，反而如果出现其它的数，例如2，就会使得二进制上1的个数变多。
全过程：5->100000,2->100100。
所以我们可以通过此方法去搜，如果当前1的个数小于等于k，我们就继续往下搜，否则我们就要返回上一级，同时要对该位置上的数在原先的基础上改为该数+1进行搜索，且接下来要从0开始。
举个例子：n=1345，k=2。
搜第一位时，二进制为10，此时1的个数小于k,往下;
搜第二位时，二进制为1010,此时1的个数等于k,往下;
搜第三位时，二进制为11010，此时1的个数大于k，返回第二步;
搜第二位时，在原先的基础上该数+1（3->4），二进制为10010，此时1的个数等于k，往下且接下来要从0开始；
搜第三位时，二进制为10011，因为这个时候是从0开始，相当于加了一个数，此时1的个数大于k，所以要返回重新搜，也就是在原先的基础上该数+1（0->1）,此时二进制为10010，此时1的个数等于k,往下；
搜第四位，此时也是从0开始，流程如上。所以结果为1411。
因此我们只需要四个变量来记录一下即可：
lim：标记是否可以沿用原数据的值作为当前循环的起点，初始化为1，过程中，在调整的时候置0，表示要从0开始依次搜索。
pos：搜索所处的位数，初始为1，当pos为len+1时，说明前len个已经有了答案。此时可以返回结果，结束循环。
mask：以二进制来记录当前已经加入的数字种数。
sum：记录结果。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[12];
int len,ans,k;
int cal(int mask)//计算二进制有多少个1
{
return __builtin_popcount(mask);
}
void dfs(int lim,int pos,int mask,int sum)
{
if(pos==len+1)
{
ans=sum;
return ;
}
int start=0;
if(lim)
{
start=s[pos];
}
for(int i=start;i<=9;i++)
{
if(ans==0&&cal(mask|(1<<i))<=k)
{
dfs(lim&&i==start,pos+1,mask|(1<<i),sum*10+i);
}
}
}
int main()
{
int t;
int n;
cin>>t;
while(t--)
{
scanf("%s",s+1);
cin>>k;
len=strlen(s+1);
for(int i=1;i<=len;i++)
{
s[i]-='0';
}
ans=0;
dfs(1,1,0,0);
cout<<ans<<endl;
}
return 0;
}
华为二面45人在聊
投递交通银行等公司10个岗位 >