A. Dislike of Threes
题意:找出第k个数字不能被3整除且各个位置上的数字不含3
数据范围很小暴力即可
#include<bits/stdc++.h>
using namespace std;
int num[1005];
void build()
{
int cnt=0;
for(int i=1;cnt<=1000;i++)
{
if(i%3==0)
continue;
/*int t=i;
while(t>0)
{
if(t%10==3)
break;
t/=10;
}
if(t==0)*/
if(i%10!=3)
num[cnt++]=i;
}
//for(int i=0;i<cnt;i++)
//cout<<num[i]<<endl;
}
int main()
{
int T;
scanf("%d",&T);
build();
while(T--)
{
int n;
scanf("%d",&n);
cout<<num[n-1]<<endl;
}
return 0;
}
B. Who's Opposite?
题意:n个数按顺时针摆放(n一定是偶数)，告诉你a、b、c，a的对面是b，求c的对面
首先，很容易发现abs(a-b)==n/2，也就是求出来了n，如果a、b、c任意一个大于n都是无解
c的对面是(c+n/2)%n,特判(c+n/2)%n==0此时等于n
#include<bits/stdc++.h>
using namespace std;
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 len=(b-a)*2;
if(len<b||len<c)
{
printf("%d\n",-1);
continue;
}
int ans=c+len/2;
ans%=len;
if(ans==0)
ans=len;
printf("%d\n",ans);
}
return 0;
}
C. Infinity Table
题意:数字按照以下方式排列，求k出现在第几行第几列
1 2 5 10 ···
4 3 6 11 ···
9 8 7 12 ···
16 15 14 13 ···
· · · · ···
· · · · ···
很容易发现，左上到右下的对角线是一个分界线
对角线上的点这一行从左到右到对角线递减
对角线上的点这一列从上到下到对角线递增
那我们找找规律
特别容易发现每行最右边的数是i*i
那么对角线上的点的规律就是减去行数+1即i*i-i+1(1<=i)
根据上面容易发现每列第一个数是1+(i-1)*(i-1)
也就是说关于对角线上点的这样子的形状_|的范围久确定了，枚举k在那个对角线的_|范围
然后根据和对角线上点的大小就可以判断哪一行那一列
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
long long k;
cin>>k;
long long i;
for(i=1;i<100000;i++)
{
if((k>=i*i-i+1&&k<=i*i)||(k<i*i-i+1&&k>=1+(i-1)*(i-1)))
break;
}
if(k>=i*i-i+1&&k<=i*i)
{
cout<<i<<" "<<i*i-k+1<<endl;
}
else
cout<<k-(i-1)*(i-1)<<" "<<i<<endl;
}
return 0;
}
D. Make a Power of Two
题意:对数字n有两种操作，一种是删除n上任意一位，另一个是在最右边加上一个数
求将n变成2的k次方的数需要多少次操作(k任意取)，注意一个有前导0需要去掉
开始我以为是对2的k次方的数和n进行最大公共子序列，调试以后才发现，这样子的话会跳掉开头的数
只能是n和2的k次方的数一个个匹配过去
如果有相等则i++,j++(i指向2的k次方数字的哪一位，j指向n的位置)，否者j++
这样子就可以知道n按顺序和2的k次方有多少给数字相等，n多余的数字删去，不过2的k次方的数字补上
注意n<=1e9，那么我们需要枚举k到60,不能在32，因为如果n是八位数是某个12位的2的k次方的前缀
那么四步就可以到2的k次方(这时候k>32)
#include<bits/stdc++.h>
using namespace std;
int length[70];
void turn(int k,long long n,char str[])
{//数字转换成字符串匹配
int cnt=1;
while(n>0)
{
str[cnt++]='0'+n%10;
n=n/10;
}
reverse(str+1,str+cnt);
str[cnt]='\0';
length[k]=cnt;
}
int main()
{
int T;
scanf("%d",&T);
char str[70][15];
long long num[70];
for(int i=0;i<=60;i++)
num[i]=(long long)1<<i;
for(int i=0;i<=60;i++)
turn(i,num[i],str[i]);
while(T--)
{
int n;
scanf("%d",&n);
char s[15];
turn(61,n,s);
int len=length[61];
int a=100000;
for(int k=0;k<61;k++)
{
int i=1,j=1;
while(i<length[k]&&j<len)
{
if(str[k][i]==s[j])
i++,j++;
else
j++;
}
//cout<<k<<" "<<i<<" "<<j<<endl;
if(a>len-i+length[k]-i)
{
a=len-i+length[k]-i;
//cout<<k<<" "<<i<<" "<<j<<endl;
}
}
cout<<a<<endl;
}
return 0;
}
E. Polycarp and String Transformation
题意:初始有一个字符串s(均由小写字母组成)和一个空字符串t，每次操作分为两步
1、t=t+s
2、s去掉其中的一种字母(这个字母必须存在)
一直进行到s为空为止
给出t的最终状态，求出s的初始状态，并且求出删除s字母的顺序(无解输出-1)
看了题解才明白，首先将t从后往前遍历，第一个出现的字母是最后删除的、、、以此类推
这样子我们就可以确定字母的删除序列k，同时统计字母出现了多少遍num
对于一个字母在s中出现了多少次，那么一定是num/k
毕竟第一个删除的字母只能出现一遍，第二个删除的出现两遍
这样子，我们就可以求出s的长度len，根据t的定义可以知道t的前len个字母就是s
这样子，对求出的s按题目操作模拟，得到的字符串如果不等于t，那么就是无解
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
string s;
cin>>s;
int len=s.length();
int num[30],f[30],cnt=1;
memset(num,0,sizeof(num));
memset(f,0,sizeof(f));
for(int i=len-1;i>=0;i--)
{
int t=s[i]-'a';
num[t]++;//记录字母出现次数
if(f[t])
continue;
f[t]=cnt++;
}
for(int i=0;i<26;i++)
f[i]=cnt-f[i];//记录字母是第几个删除
//那么在题目的初始状态，每个字母出现的次数是num[i]/f[i]
string temp;//题目的初始状态(如果终止态合法)
int length=0;
for(int i=0;i<26;i++)
if(f[i])
length=length+num[i]/f[i];
for(int i=0;i<length;i++)
temp.push_back(s[i]);
//cout<<temp<<endl;
string ans;//删除字母的顺序
for(int i=1;i<cnt;i++)
for(int j=0;j<26;j++)
if(f[j]==i)
ans.push_back(j+'a');
//cout<<ans<<endl;
string check=temp;
string a=temp;//模拟操作过程，看看能不能得到s串
for(int i=0;i<ans.length();i++)
{
string b;
for(int j=0;j<a.length();j++)
if(a[j]!=ans[i])
{
b.push_back(a[j]);
check.push_back(a[j]);
}
//cout<<check<<endl;
a=b;
}
if(check!=s)
printf("-1\n");
else
cout<<temp<<" "<<ans<<endl;
}
return 0;
}
F. Nearest Beautiful Number
题意:求一个大于等于n的数x，x满足其各个位置的出现的个数<=k,且x尽可能小
题目要让x尽可能小，那么就尽量让x的前缀和n相等
1、当n出现k+1个数字的时候，我们首先想到的是x同样的位置上要让这个数换成前面k个出现过的且大于k+1的数字，
然后让这个数后面的所有数字换成前k给数出现的最小的数字
问题是，如果前k个出现的数字没有比第k+1给出现的数字大的怎么办？
2、只能改出现k+1个数字前面位置的数字i换成前k个数更好大于i的数字
且i后面的数字都换成前k个数中最小的那个或者0
(0的情况是改了i，但i只出现了一次，就是说前k个数有一个是i，删去i以后空出一个数，这个数可以设置为0填充到后面)
如果没有比i大的呢？？那就对i前面的数字进行2操作
嗯，题解里另一种更难但是时间更快方法我就有一些看不懂了。。。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
string n;//输入需要>=的n
int k;
cin>>n>>k;
while(true)
{
set<char> s;
for(int i=0;i<n.length();i++)
s.insert(n[i]);//利用set的去重，记录n由多少个数字出现
if(s.size()<=k)
break;//如果输出的数字小于等于k，返回
//以下n出现的数字必定大于等于k
s.clear();//将s清空，记录到k+1给数字的位置
int i;
for(i=0;;i++)
{
s.insert(n[i]);
if(s.size()>k)//因为n出现的数字一定大于k，必定可以break
{
while(n[i]=='9')
i--;//如果n前缀里第k+1位数字是9
//那么我们只能更改第k位数字(毕竟9在前面没有出现过)
//这么做是因为我们需要将k+1位出现的数字改为前面k位出现过的
//且大于k+1位的
n[i]++;//改为比k+1位大的(如果n[i]++也未出现，那么下次while循环还会到这)
for(int j=i+1;j<n.size();j++)
n[j]='0';//由于k+1位改后大于原本，所以后面应该取最小0
//如果0在前面没有出现过，那么0会入k+1位出现的数字，进行++
//直到找到前面k给数出现的最小值
break;
}
}
}
cout<<n<<endl;
}
return 0;
}
