CodeForces - 1373
A - Donut Shops
买
1个的时候
,店
2最亏，店
1最有可能比店
2便宜
买b个的时候
,店
2最赚，店
2最有可能比店
1便宜
比较这两种情况即可
ll a
,b
,c
;
int ans1
,ans2
,t
;
int main()
{
scanf("%d",&t
);
while(t
--)
{
scanf("%lld%lld%lld",&a
,&b
,&c
);
if (a
*b
>c
)ans2
=b
;
else ans2
=-1;
if (a
<c
)ans1
=1;
else ans1
=-1;
printf("%d %d\n",ans1
,ans2
);
}
return 0;
}
B - 01 Game
直接判断
0和
1数量即可，因为只要
0和
1都存在于这个字符串中，必然会有相邻的地方
不论如何都可以一起删除
int t
;
char s
[maxn
];
int main()
{
scanf("%d",&t
);
while(t
--)
{
int num0
=0,num1
=0;
scanf("%s",s
);
repp(i
,0,strlen(s
))s
[i
]=='0'?num0
++:num1
++;
if (min(num0
,num1
)%2==0)printf("NET\n");
else printf("DA\n");
}
return 0;
}
C - Pluses and Minuses
now表示能够遍历到某个位置x所需的最小cur
如果b
[i
]>now说明
[now
,b
[i
]-1]这个区间的数都可以遍历到位置i，res共加了i
+1次
int t
,b
[maxn
];
char s
[maxn
];
int main()
{
scanf("%d",&t
);
while(t
--)
{
scanf("%s",s
);
int sz
=strlen(s
),num1
=0,num2
=0,now
=0;
ll res
=sz
;
repp(i
,0,sz
)s
[i
]=='+'?num1
++:num2
++,b
[i
]=num2
-num1
;
repp(i
,0,sz
)
{
if (b
[i
]<=now
)continue;
res
+=1ll*(b
[i
]-now
)*(i
+1);
now
=b
[i
];
}
WW(res
);
}
return 0;
}
D - Maximum Sum on Even Positions
题意:使偶数位置的数的加和最大 首先需要明确：置换区间的长度必然是偶数，置换奇数长度的区间是无意义的 给出两个例子便于理解: 原数组：2 5 6 1 7 偶数位置加和=2+6+7 假设置换区间
[
1
,
2
]
[1,2]
[1,2] 得到数组：2 6 5 1 7 偶数位置加和=2+5+7 变化量就等于5和6的差abs(5-6)=1
reverse区间的实质就是交换区间内的相邻数，这个相邻是不含重叠的相邻 假设置换区间[1,4],则变化量是
(
a
2
−
a
1
)
+
(
a
4
−
a
3
)
(a_2-a_1)+(a_4-a_3)
(a2−a1)+(a4−a3)或者
(
a
1
−
a
2
)
+
(
a
3
−
a
4
)
(a_1-a_2)+(a_3-a_4)
(a1−a2)+(a3−a4)
于是，问题就简化为了，选取一段区间等价于求最大字段和 套用最大字段和模板即可。注意有两个方向。
int t
,n
,a
[maxn
];
int main()
{
scanf("%d",&t
);
while(t
--)
{
ll ans
=0,ans1
=0,ans2
=0;
scanf("%d",&n
);
rep(i
,1,n
)
{
scanf("%d",&a
[i
]);
if (i
%2==1)ans
+=a
[i
];
}
ll cnt
=0;
for (int i
=1;i
<=n
-1;i
+=2)
{
if (cnt
>0)cnt
+=a
[i
+1]-a
[i
];
else cnt
=a
[i
+1]-a
[i
];
ans1
=max(ans1
,cnt
);
}
cnt
=0;
for (int i
=2;i
<=n
-1;i
+=2)
{
if (cnt
>0)cnt
+=a
[i
]-a
[i
+1];
else cnt
=a
[i
]-a
[i
+1];
ans2
=max(ans2
,cnt
);
}
WW(ans
+max(ans1
,ans2
));
}
return 0;
}
E - Sum of Digits
1.对于k
=0的，做了特判处理，这种情况只要尽可能多的往后面放
9就可以了
2.对于x
=0时，做了特判处理，由于用到了map
3.当n比较小时，显然是由一些“较小的x”得到的，故直接暴力枚举较小的x得到较小的n
4.当n比较大时，仍然是要尽可能多的放
9，但是第一位不确定，最后一位也不确定，且倒数第二位可能为
8，这个
8加着加着就可能变为
9，可以凑出一些特殊的数。也是采用暴力枚举
由于分类比较多，枚举范围也被缩小了很多，不存在超时的可能
比较稳健。思路也不是很混乱
typedef pair
<ll
,ll
> P
;
map
<P
,ll
> M
;
P tmp
;
int t
;
ll
solve(ll x
){ll res
=0;while(x
>0){res
+=x
%10;x
/=10;}return res
;}
ll
qpow(ll a
,ll b
){ll res
=1;while(b
){if (b
&1)res
=res
*a
;b
>>=1;a
*=a
;}return res
;}
int main()
{
for (ll i
=0;i
<2000;i
++)
{
for (ll j
=0;j
<=9;j
++)
{
ll ans
=0;
for (ll k
=0;k
<=j
;k
++)ans
+=solve(i
+k
);
tmp
.first
=ans
,tmp
.second
=j
;
if (M
[tmp
]==0)M
[tmp
]=i
;
else M
[tmp
]=min(M
[tmp
],i
);
}
}
for (ll i
=0;i
<=9;i
++)
{
for (ll j
=0;j
<=9;j
++)
{
for (ll l
=0;l
<=1;l
++)
{
for (ll k
=0;k
<=9;k
++)
{
ll sum
=k
+j
*qpow(10,i
+l
+1)+8*10*l
;
for (ll p
=1;p
<=i
;p
++)sum
+=9*qpow(10,p
+l
);
for (ll q
=0;q
<=9;q
++)
{
ll ans
=0;
for (ll c
=0;c
<=q
;c
++)ans
+=solve(sum
+c
);
tmp
.first
=ans
,tmp
.second
=q
;
if (M
[tmp
]==0)M
[tmp
]=sum
;
else M
[tmp
]=min(M
[tmp
],sum
);
}
}
}
}
}
scanf("%d",&t
);
while(t
--)
{
scanf("%lld%lld",&tmp
.first
,&tmp
.second
);
if ((tmp
.second
+1)*tmp
.second
/2==tmp
.first
)W(0);
else if (tmp
.second
==0)
{
int num
=tmp
.first
/9;
if (tmp
.first
%9!=0)printf("%d",tmp
.first
%9);
repp(i
,0,num
)printf("%d",9);
puts("");
}
else if (M
[tmp
]==0)W(-1);
else WW(M
[tmp
]);
}
return 0;
}
