Codeforces Round #739 (Div. 3)

A. Dislike of Threes

解题思路:

暴力

AC代码:

#include<iostream>
#include<queue>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstdio>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
#define repi(x,y,z) for(int x = y; x<=z;++x)
#define deci(x,y,z) for(int x = y; x>=z;--x)
#define repl(x,y,z) for(ll x = y; x<=z;++x)
#define decl(x,y,z) for(ll x = y; x>=z;--x)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b / gcd(a, b))
#define INF 0x3f3f3f3f
#define ms(a,b) memset( a, b , sizeof (a) )
#define txt intxt()
#define CAS int cas;cin>>cas;while(cas--)
#define py
puts("yes")
#define pn
puts("no")
#define pcn
putchar('n')
#define pcs
putchar(' ')
#define pc(a)
putchar(a)
#define pb(a)
push_back(a)
inline void intxt( ){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
}
inline ll read( ){
ll f = 1,x = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
{if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
x *= f;
return x;
}
const int maxn=1e6+1e4;
int a[maxn];
int num;
int n;
bool check(int id){
if(id%3==0) return 0;
if( id%10==3 ) return 0;
return 1;
}
int main(){
for(int i=1; ;i++){
if( 1==check(i) ){
a[++num]=i;
if(num>=1000)
break;
}
}
//txt;
CAS{
cin>>n;
cout<<a[n]<<endl;
}
return 0;
}

B. Who’s Opposite?

解题思路:

模拟即可

AC代码:

#include<iostream>
#include<queue>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstdio>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
#define repi(x,y,z) for(int x = y; x<=z;++x)
#define deci(x,y,z) for(int x = y; x>=z;--x)
#define repl(x,y,z) for(ll x = y; x<=z;++x)
#define decl(x,y,z) for(ll x = y; x>=z;--x)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b / gcd(a, b))
#define INF 0x3f3f3f3f
#define ms(a,b) memset( a, b , sizeof (a) )
#define txt intxt()
#define CAS int cas;cin>>cas;while(cas--)
#define py
puts("yes")
#define pn
puts("no")
#define pcn
putchar('n')
#define pcs
putchar(' ')
#define pc(a)
putchar(a)
#define pb(a)
push_back(a)
inline void intxt( ){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
}
inline ll read( ){
ll f = 1,x = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
{if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
x *= f;
return x;
}
const int maxn=1e6+1e4;
int n;
ll a,b,c,d;
ll r;
int main(){
//txt;
CAS{
a=read();
b=read();
c=read();
r=abs(a-b)*2;
if( a>r || b>r || c>r ){
cout<<-1<<endl;
continue;
}
if( c+r/2<=r ){
d = c+r/2;
}else{
d= c- r/2;
}
cout<<d<<endl;
}
return 0;
}

C. Infinity Table

解题思路:

可以先求出最大位置小一格的正方形,然后模拟

AC代码:

#include<iostream>
#include<queue>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstdio>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
#define repi(x,y,z) for(int x = y; x<=z;++x)
#define deci(x,y,z) for(int x = y; x>=z;--x)
#define repl(x,y,z) for(ll x = y; x<=z;++x)
#define decl(x,y,z) for(ll x = y; x>=z;--x)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b / gcd(a, b))
#define INF 0x3f3f3f3f
#define ms(a,b) memset( a, b , sizeof (a) )
#define txt intxt()
#define CAS int cas;cin>>cas;while(cas--)
#define py
puts("yes")
#define pn
puts("no")
#define pcn
putchar('n')
#define pcs
putchar(' ')
#define pc(a)
putchar(a)
#define pb(a)
push_back(a)
inline void intxt( ){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
}
inline ll read( ){
ll f = 1,x = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
{if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
x *= f;
return x;
}
const int maxn=1e6+1e4;
int n;
ll k,r,c,ge;
int main(){
//txt;
CAS{
k=read();
for(ll i=1; ;i++){
if( i*i>=k ){
ge=i-1;
break;
}
}
ll tem=k-(ge*ge);
if(tem>ge+1){
r=ge+1;
c=2*ge+1-tem+1;
}else{
r=tem;
c=ge+1;
}
cout<<r<<" "<<c<<endl;
}
return 0;
}

D. Make a Power of Two

解题思路:

把2^k和n都搞成字符串然后匹配就行了,这题我吃了不会to_string的大亏,本来拿这题就会了,嘤嘤嘤,于是自己手抄了62个2的幂
std::string to_string(long long value);//嘤嘤嘤,其他类型同理

AC代码:

#include<iostream>
#include<queue>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstdio>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
#define repi(x,y,z) for(int x = y; x<=z;++x)
#define deci(x,y,z) for(int x = y; x>=z;--x)
#define repl(x,y,z) for(ll x = y; x<=z;++x)
#define decl(x,y,z) for(ll x = y; x>=z;--x)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b / gcd(a, b))
#define INF 0x3f3f3f3f
#define ms(a,b) memset( a, b , sizeof (a) )
#define txt intxt()
#define CAS int cas;cin>>cas;while(cas--)
#define py
puts("yes")
#define pn
puts("no")
#define pcn
putchar('n')
#define pcs
putchar(' ')
#define pc(a)
putchar(a)
#define pb(a)
push_back(a)
inline void intxt( ){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
}
inline ll read( ){
ll f = 1,x = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
{if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
x *= f;
return x;
}
const int maxn=1e6+1e4;
string c,tem;
string s[65];
void inta( ){
s[0]="1";
s[1]="2";
s[2]="4";
s[3]="8";
s[4]="16";
s[5]="32";
s[6]="64";
s[7]="128";
s[8]="256";
s[9]="512";
s[10]="1024";
s[11]="2048";
s[12]="4096";
s[13]="8192";
s[14]="16384";
s[15]="32768";
s[16]="65536";
s[17]="131072";
s[18]="262144";
s[19]="524288";
s[20]="1048576";
s[21]="2097152";
s[22]="4194304";
s[23]="8388608";
s[24]="16777216";
s[25]="33554432";
s[26]="67108864";
s[27]="134217728";
s[28]="268435456";
s[29]="536870912";
s[30]="1073741824";
s[31]="2147483648";
s[32]="4294967296";
s[33]="8589934592";
s[34]="17179869184";
s[35]="34359738368";
s[36]="68719476736";
s[37]="137438953472";
s[38]="274877906944";
s[39]="549755813888";
s[40]="1099511627776";
s[41]="2199023255552";
s[42]="4398046511104";
s[43]="8796093022208";
s[44]="17592186044416";
s[45]="35184372088832";
s[46]="70368744177664";
s[47]="140737488355328";
s[48]="281474976710656";
s[49]="562949953421312";
s[50]="1125899906842624";
s[51]="2251799813685248";
s[52]="4503599627370496";
s[53]="9007199254740992";
s[54]="18014398509481984";
s[55]="36028797018963968";
s[56]="72057594037927936";
s[57]="144115188075855872";
s[58]="288230376151711744";
s[59]="576460752303423488";
s[60]="1152921504606846976";
s[61]="2305843009213693952";
s[62]="4611686018427387904";
}
int check( int x ){
tem=s[x];
int id=0;
int len=c.length();
int sum=0;
repi(i,0,len-1){
if( tem[id]==c[i] ){
id++;
if( id==tem.length() ){
return len-id;//未全部匹配
}
}else{
sum++;
}
}
return sum+( tem.length()-id );//全部匹配
}
int main(){
inta();
//txt;
CAS{
cin>>c;
int ans=1e9;
repi(i,0,62){
ans=min( ans,check(i) );
}
cout<<ans<<endl;
}
return 0;
}

E. Polycarp and String Transformation

解题思路:

s中最后出现的一种字母一定是最后删的, 倒数第二种出现的一定是倒数第二删的 , 前面同理 , 然后我们可以通过字符集找出最开始的长度 , 然后模拟出来再与初始给的s比较就行了

AC代码:

#include<iostream>
#include<queue>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstdio>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
#define repi(x,y,z) for(int x = y; x<=z;++x)
#define deci(x,y,z) for(int x = y; x>=z;--x)
#define repl(x,y,z) for(ll x = y; x<=z;++x)
#define decl(x,y,z) for(ll x = y; x>=z;--x)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b / gcd(a, b))
#define INF 0x3f3f3f3f
#define ms(a,b) memset( a, b , sizeof (a) )
#define txt intxt()
#define CAS int cas;cin>>cas;while(cas--)
#define py
puts("yes")
#define pn
puts("no")
#define pcn
putchar('n')
#define pcs
putchar(' ')
#define pc(a)
putchar(a)
#define pb(a)
push_back(a)
inline void intxt( ){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
}
inline ll read( ){
ll f = 1,x = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
{if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
x *= f;
return x;
}
const int maxn=1e6+1e4;
string s,reals,tem;
int kind,len,relen;
char dsx[maxn];
int zim[30];
void caoz(int id){
int w=0;
while( 1 ){
w=tem.find( dsx[id] );
if(w==-1) break;
tem.erase(w,1);
}
}
int main(){
txt;
CAS{
cin>>s;
reals="";
ms(zim,0);kind=0;
len=s.length();
deci(i,len-1,0){//统计字符集
zim[ s[i]-'a' ]++;
if(zim[ s[i]-'a' ]==1){//找倒数出现的位置
kind++;
dsx[kind]=s[i];//存储出现顺序(这里是倒叙的)
}
}
relen=0;
deci(i,kind,1){//计算初始长度
relen+=zim[ dsx[i]-'a' ]/(kind-i+1);
}
tem=s.substr(0,relen);//获取初始字符串
deci(i,kind,1){//模拟
reals+=tem;
caoz(i);
}
if( reals==s ){//并判断输出
tem=s.substr(0,relen);
cout<<tem<<" ";
deci(i,kind,1)
putchar(dsx[i]);
pcn;
}else{
cout<<-1<<endl;
}
}
return 0;
}

F2. Nearest Beautiful Number (hard version)

解题思路:

k等于那么n的第k个不同数字之前的数字一定是确定的

然后对那个数字开始dfs就行了,具体看代码

#include<iostream>
#include<queue>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstdio>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
#define repi(x,y,z) for(int x = y; x<=z;++x)
#define deci(x,y,z) for(int x = y; x>=z;--x)
#define repl(x,y,z) for(ll x = y; x<=z;++x)
#define decl(x,y,z) for(ll x = y; x>=z;--x)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (a * b / gcd(a, b))
#define INF 0x3f3f3f3f
#define ms(a,b) memset( a, b , sizeof (a) )
#define txt intxt()
#define CAS int cas;cin>>cas;while(cas--)
#define py
puts("yes")
#define pn
puts("no")
#define pcn
putchar('n')
#define pcs
putchar(' ')
#define pc(a)
putchar(a)
#define pb(a)
push_back(a)
inline void intxt( ){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
}
inline ll read( ){
ll f = 1,x = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
{if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
x *= f;
return x;
}
const int maxn=1e6+1e4;
char c[25];
int k,len;
ll n,ans,ans2;
vector<int> g;
ll shi[15];
void inta(){//预处理10的次方,方便剪枝的时候用
shi[0]=1;
repi(i,1,10){
shi[i]=shi[i-1]*10;
}
}
ll check(int ge,int id){
ll sum=id;
repi(i,2,ge){
sum*=(ll)10;
sum+=(ll)id;
}
return sum;
}
ll solve1(){//k==1的时候特判,我直接抄的我f1的代码
ll tem,ans1=1e18;
repi(i,1,10){
repi(j,1,9){
tem=check(i,j);
if( tem>=n )
ans1=min(ans1,tem);
}
}
return ans1;
}
void dfs( int suz,int id,ll sum ){
if( sum*shi[ len+1-id ]>=ans2 )//剪枝,把最终的sum可能>=ans2的都在前面直接干掉
return;
if(id==len+1){
if(sum>=n){
ans2=min(sum,ans2);
}
return;
}
dfs( suz,id+1,sum*10+(ll)suz );//选地k个不同的数字
repi(i,0, (int)(g.size()-1) ){
dfs( suz,id+1,sum*10+(ll)g[i] );//选前k-1个已经确定的数字
}
}
bool vis[15];
int che(){//寻找地k个不同数字出现的位置
ms(vis,0);
g.clear();
repi(i,1,len){
if( vis[ c[i]-'0' ]==0 && g.size()<k-1){
vis[ c[i]-'0' ]=1;
g.pb( c[i]-'0' );
}else if( vis[ c[i]-'0' ]==0 && g.size()==k-1 ){
return i;
}
}
return len+1;
}
ll solve2(){
int kai = che();
if( kai==len+1 ) return n;//n只有k-1种数字
if(len==k) return n;//n刚好有k种数字
ll nn=0;
repi(i,1,kai-1){
nn*=10;
nn+=c[i]-'0';
}
ans2=1e18;
repi(i,0,9){
if( vis[i]==0 && c[kai]-'0'+1>=i )//vis==0才进行搜索,vis==1的话就算前面k-1种已经确定的,不用再搜了
dfs( i,kai,nn );
//地k个不同数字i一定是<=地k个数字本来的数字+1的
}
return ans2;
}
int main(){
//txt;
inta();
CAS{
cin>>(c+1);
cin>>k;
len=strlen(c+1);
n=c[1]-'0';
repi(i,2,len){
n*=10;
n+=c[i]-'0';
}
if(k==1)
ans=solve1( );
else
ans=solve2( );
cout<<ans<<endl;
}
return 0;
}

最后

以上就是感性奇迹为你收集整理的Codeforces Round #739 (Div. 3)Codeforces Round #739 (Div. 3)的全部内容，希望文章能够帮你解决Codeforces Round #739 (Div. 3)Codeforces Round #739 (Div. 3)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。