Codeforces Round #671 (Div. 2)

当天晚上,本来想参加一下比赛,结果感觉静不下心来做题,而且最难受的是读个题都不明白,一直在理解题意·。·

A – Digit Game

分析不难发现:
如果

n

n

n是奇数,那么最后留下的数字一定是奇数位上的数字,如果奇数位上的数字至少存在一个奇数,那么先手必胜。
如果

n

n

n是偶数,那么最后留下的数字一定是偶数位上的数字,如果偶数位上的数字至少存在一个凑数,那么后手必胜。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int n;
int main()
{
IO;
int T=1;
cin>>T;
while(T--)
{
cin>>n;
string s;
cin>>s;
s="."+s;
bool ok;
if(n&1)
{
ok=0;
for(int i=1;i<=n;i++)
if(i%2==1&&(s[i]-'0')%2==1) ok=1;
}
else
{
ok=1;
for(int i=1;i<=n;i++)
{
if(i%2==0&&(s[i]-'0')%2==0)
ok=0;
}
}
if(ok) cout<<1<<'\n';
else cout<<2<<'\n';
}
return 0;
}

B - Stairs

首先只要知道每个楼梯的边长,那么可以用等差数列求出所有小方块的个数。楼梯的边长

2

n

1

2^{n}-1

2n−1,然后只需要一个一个枚举即可。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{
IO;
int T=1;
cin>>T;
while(T--)
{
ll x;
cin>>x;
ll s=0;
int res=0;
ll a=1;
for(int i=1;;i++)
{
ll now=2*a-1;
s+=1ll*now*(now+1)/2;
if(s<=x) res++;
else break;
a<<=1;
}
cout<<res<<'\n';
}
return 0;
}

C - Killjoy

这题我也读了很久才理解题意
不难发现最终答案就三种情况

{

0

,

1

,

2

}

\{0,1,2\}

{0,1,2}

0

0

0:最初所有

a

i

=

x

a_i=x

ai​=x

1

1

1:存在

a

i

=

x

a_i=x

ai​=x或者

i

=

1

n

a

i

=

n

x

\sum_{i=1}^{n}a_i=nx

∑i=1n​ai​=nx(如果

a

k

=

x

a_k=x

ak​=x那么它一开始就会被感染,一场比赛可以把其余的

a

i

a_i

ai​都变成

x

x

x,

a

k

a_k

ak​用来调整保证改变之和为

0

0

0)

2

2

2:其余情况答案都是2

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1010;
int a[N];
int n,x;
int main()
{
IO;
int T=1;
cin>>T;
while(T--)
{
cin>>n>>x;
int s=0;
bool ok1=1;
bool ok2=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]!=x) ok1=0;
if(a[i]==x) ok2=1;
s+=a[i];
}
if(ok1) cout<<0<<'\n';
else if(ok2||s==n*x) cout<<1<<'\n';
else cout<<2<<'\n';
}
return 0;
}

D1 - Sage’s Birthday (easy version)

分析可知先把原数组排序,然后把前

n

2

\lfloor \frac{n}{2}\rfloor

⌊2n​⌋的数按顺序插到后

n

2

\lceil \frac{n}{2}\rceil

⌈2n​⌉的缝隙中的构造结果肯定最优。然后可以扫一遍统计下答案即可。(如果原数组的数不同那么不难发现答案一定是

n

1

2

\lfloor \frac{n-1}{2}\rfloor

⌊2n−1​⌋)

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100010;
int a[N],b[N],c[N];
int n;
int main()
{
IO;
int T=1;
//cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
for(int i=1;i<=n/2;i++) b[i]=a[i];
for(int i=n/2+1;i<=n;i++) c[i-n/2]=a[i];
cout<<(n-1)/2<<'\n';
for(int i=1;i<=(n+1)/2;i++)
{
cout<<c[i]<<' ';
if(i<=n/2) cout<<b[i]<<' ';
}
cout<<'\n';

}
return 0;
}

D2 - Sage’s Birthday (hard version)

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100010;
int a[N],b[N],c[N];
int n;
int main()
{
IO;
int T=1;
//cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n);
for(int i=1;i<=n/2;i++) b[i]=a[i];
for(int i=n/2+1;i<=n;i++) c[i-n/2]=a[i];
for(int i=1,j=1;i<=(n+1)/2;i++)
{
a[j++]=c[i];
if(i<=n/2) a[j++]=b[i];
}
int res=0;
for(int i=2;i<n;i++)
if(a[i]<a[i-1]&&a[i]<a[i+1]) res++;
cout<<res<<'\n';
for(int i=1;i<=n;i++) cout<<a[i]<<' ';
cout<<'\n';
}
return 0;
}

E - Decryption

说点儿废话:2020/9/20下午,在图书馆看了一下这个题,好不容易分析出如何构造能够得出答案,然后回寝室一直调代码调到12点,调代码能力还是太菜了,不能把想法快速实现还要多练。现在已经凌晨了2020/9/21,明天早上第一节没有课,爬起来把题解补了。

考虑将

n

n

n分解质因数,可得

n

=

p

1

a

1

×

p

2

a

2

×

 

×

p

i

a

i

n=p_1^{a_1}×p_2^{a_2}×\dots\ ×p_i^{a_i}

n=p1a1​​×p2a2​​×… ×piai​​
考虑这样一组排列方式的构造

{

[

p

1

,

p

1

2

,

,

p

1

a

1

]

,

[

]

,

[

p

i

,

p

i

2

,

,

p

i

a

i

]

}

\{[p_1,p_1^2,\dots, p_1^{a_1}],[],[p_i,p_i^2,\dots, p_i^{a_i}]\}

{[p1​,p12​,…,p1a1​​],[],[pi​,pi2​,…,piai​​]}不难发现中间

[

]

[]

[]中只要包含

p

1

p_1

p1​那么无论怎么排列一定不互质(存在相同因子

p

1

p_1

p1​),因此中间括号只需要用dfs求出所有包含

p

1

p_1

p1​质因子的约数即可(但是我们需要让

n

n

n放置在最后)。根据dfs的性质,

[

]

[]

[]中的最后一个数一定有质因子

p

i

p_i

pi​(当前最后一个质因数),那么我们下一个排的时候就要排

p

i

p_i

pi​因此每次需要和当前最后一个质因数交换一下位置。

根据上述构造可得当且仅当一个数的质因数是2并且质因子的指数都是1(

n

=

p

1

×

p

2

n=p_1×p_2

n=p1​×p2​)才需要插入一个最小公倍数,否则都不需要插入最小公倍数

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
#define p first
#define a second
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int N=200010;
pii d[N];
int cnt,n,idx;
ll ans[N];
void divide(int x)
{
idx=cnt=0;
for(int i=2;i<=x/i;i++)
if(x%i==0)
{
d[++cnt].p=i;
d[cnt].a=0;
while(x%i==0) x/=i,d[cnt].a++;
}
if(x>1)
{
d[++cnt].p=x;
d[cnt].a=1;
}
}
void dfs(int u,ll now)
{
for(int i=u;i<=cnt;i++)
{
ll p=1;
for(int j=1;j<=d[i].a;j++)
{
p*=d[i].p;
if(now*p!=n) ans[++idx]=now*p;
dfs(i+1,now*p);
}
}
}
int main()
{
IO;
int T=1;
cin>>T;
while(T--)
{
cin>>n;
divide(n);
for(int i=1;i<=cnt;i++)
{
ll p=1;
for(int k=1;k<=d[i].a;k++)
{
p*=d[i].p;
if(p!=n) ans[++idx]=p;//注意把n放在最后
}
//括号间的数
p=1;
for(int k=1;k<=d[i].a;k++)
{
p*=d[i].p;
dfs(i+1,p);
}
if(i<cnt) swap(d[i+1],d[cnt]);
}
for(int i=1;i<=idx;i++) cout<<ans[i]<<' ';
cout<<n<<'\n';
if(cnt==2&&d[1].a==1&&d[2].a==1) cout<<1<<'\n';
else cout<<0<<'\n';

}
return 0;
}

要加油哦~

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

Codeforces Round #671 (Div. 2)

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » Codeforces Round #671 (Div. 2)
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏