0%

cf1490

cf1490

这。。。这就是div3嘛

A:Dense array

对每个间隔统计即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
per(){
int n;cin>>n;
for(int i=1;i<=n;++i){
cin>>in[i];
}
int ans=0;
for(int i=2;i<=n;++i){
int ma=max(in[i-1],in[i]);
int mi=min(in[i-1],in[i]);
int cnt=0;
while(mi*2<ma){
cnt++;
mi*=2;
}
ans+=cnt;
}
cout<<ans<<endl;
}

B:Balanced Remainders

从0到1到2,再到0到1,如果多了就向后推,几次后就平了。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
per(){
int n;cin>>n;
int tmp;
int n0=0,n1=0,n2=0;
for(int i=1;i<=n;++i){
cin>>tmp;
if(tmp%3==1)n1++;
else if(tmp%3==0)n0++;
else n2++;
}
int num=n/3;
int ans=0;
if(n0>num){
n1+=n0-num;
ans+=n0-num;
n0=num;
}
if(n1>num){
n2+=n1-num;
ans+=n1-num;
n1=num;
}
if(n2>num){
n0+=n2-num;
ans+=n2-num;
n2=num;
}
if(n0>num){
n1+=n0-num;
ans+=n0-num;
n0=num;
}
if(n1>num){
n2+=n1-num;
ans+=n1-num;
n1=num;
}
cout<<ans<<endl;
}

C:Sum of Cubes

范围很小,把1-10000打表,同时计入map中,然后遍历之,查$n-i^3$是否在map中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const int maxn=1005;
ll in[12000];
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
map<ll,int> ma;
for(ll i=1;i<=10000;++i){
ma[i*i*i]=1;
in[i]=i*i*i;
}
//cout<<ma[7993*7993*7993]<<endl;
per(){
ll n;cin>>n;
int tag=0;
for(ll i=1;i<=10000;++i){
if(n<=in[i])break;
if(ma[n-in[i]]==1){
tag=1;break;
}
}
if(tag){
cout<<"YES"<<endl;
}else cout<<"NO"<<endl;
}
}

D:Permutation Transformation

建树,建st表然后递归即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int f[maxn][maxn],in[maxn];
//f[i][j]表示[i,i+x^j-1]范围最大值
void STinit(int n){
for(int i=1;i<=n;++i){
f[i][0]=in[i];
}
int t=log(n)/log(2)+1;
for(int j=1;j<t;j++){//长度2^j的区间最值分为2^{j-1}的两段
for(int i=1;i<=n-(1<<j)+1;i++ ){
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
}
//两个区间覆盖l-r即可,中间重合无妨
int STQ(int l,int r){
int k=log(r-l+1)/log(2);
return max(f[l][k],f[r-(1<<k)+1][k]);
}
int ans[maxn];
void dfs(map<int,int>&ma,int l,int r,int lv){
if(l==r){
ans[r]=lv;
return;
}
int nr=ma[STQ(l,r)];
ans[nr]=lv;
if(l<=nr-1)dfs(ma,l,nr-1,lv+1);
if(r>=nr+1)dfs(ma,nr+1,r,lv+1);
return ;
}
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
per(){
int n;cin>>n;
map<int,int> ma;
for(int i=1;i<=n;++i){
cin>>in[i];
ma[in[i]]=i;
}
STinit(n);
dfs(ma,1,n,0);
for(int i=1;i<=n;++i){
cout<<ans[i]<<' ';
}cout<<endl;
}
return 0;
}

E:Accidental Victory

input时将index和数字关联起来,然后处理数字。将其从小到大排序,求前缀和,然后遍历,如果前面加起来都没这个数大,此处中断,找到最后的一个中断位置即可,其后是能赢的。注意输出时要排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
struct ui{ll val;int pos;bool operator<(const ui b)const{return this->val<b.val;}};
const int maxn=2e5+10;
ui in[maxn];
ll d[maxn];
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
per(){
int n;cin>>n;
map<ll,int> ma;
for(int i=1;i<=n;++i){
cin>>in[i].val;
in[i].pos=i;
}
sort(in+1,in+1+n);
d[0]=0;int lp=-1;
for(int i=1;i<=n;++i){
d[i]=d[i-1]+in[i].val;
if(d[i-1]<in[i].val)lp=i;
}
vector<int> ans;
for(int i=lp;i<=n;++i){
ans.push_back(in[i].pos);
}
sort(ans.begin(),ans.end());
cout<<ans.size()<<endl;
for(auto i:ans)cout<<i<<' ';
cout<<endl;
}
}

F:Equalize the Array

你不可能将少的变多,但可以将5次的变4次,所以排序,前缀和。
遍历,可能的答案是次数大于等于当前次数的数字个数乘当前次数。求最大值,然后用n减即可。
(排序范围搞错,wa#2*5)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
struct ui{int times;int num;bool operator<(const ui b)const{return this->times>b.times;}};
const int maxn=2e5+1000;
ui in[maxn];
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
per(){
int n;cin>>n;
int tmp;
map<int,int> ma;
for(int i=1;i<=n;++i){
cin>>tmp;
ma[tmp]++;
}

int tot=0;
int sz=ma.size();
map<int,int> mb;
for(auto i:ma){
mb[i.second]++;
}
for(auto i:mb){
in[++tot]={i.first,i.second};
}
sort(in+1,in+1+tot);
int ans=-1;
int now=0;
for(int i=1;i<=tot;++i){
now+=in[i].num;
ans=max(ans,now*in[i].times);
}
cout<<n-ans<<endl;
}
}