Codeforces Round 582
这次比赛看着是Div.3就打了，没想到还是被虐了，并再次orz各位AK的大神……
A. Chips Moving
签到题。（然而签到题我还调了20min……）
因为数据小，所以像我一样打模拟也可以，但其实只要统计一下奇数偶数的个数并输出较小的一个即可。
#include<bits/stdc++.h>
using namespace std;
int n;
long long ans=0x3f3f3f3f;
int a[110];
void Read() {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
}
return;
}
int main()
{
Read();
for(int i=1;i<=n;i++) {
long long tmp=0;
for(int j=1;j<=n;j++) {
if(abs(a[j]-i)%2==1) {
tmp++;
}
}
ans=min(ans,tmp);
}
printf("%lld",ans);
return 0;
}
B. Bad Prices
（题目中的Polycarp真是太有经济头脑了，自己作为买家还希望卖家不要亏本……）
这道题本来也想来个暴力模拟，结果第一次提交成功在第三个点上T掉；后来优化了一下数组，第二次提交还是第三个点T掉。后来想到只要维护一个后缀最小值数组，即从最后一天到第$n$天中价格的最小值。若第$n$天的价格大于第$n$天的后缀最小值，那就是一个"Bad Price"。
#include<bits/stdc++.h>
using namespace std;
int t,n,ans;
int a[150010],pre[150010];
void Init() {
n=0;
ans=0;
memset(a,0,sizeof(a));
memset(pre,0x7f,sizeof(pre));
return;
}
void Read()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
}
return;
}
void findMin() {
for(int i=n;i>=1;i--) {
pre[i]=min(pre[i+1],a[i]);
}
return;
}
void Solve() {
for(int i=1;i<=n;i++) {
if(a[i]>pre[i]) {
ans++;
}
}
printf("%d\n",ans);
return;
}
int main()
{
scanf("%d",&t);
for(int i=1;i<=t;i++) {
Init();
Read();
findMin();
Solve();
}
return 0;
}
C. Book Reading
这题只用统计$m$倍数的个位数字之和，继续打模拟，结果连样例都跑不出来……
一看样例：
1234312817382646 13
顿时醒悟……当$n$远大于$m$时，$n\div m$的值会很大，以至于1s根本跑不完。
于是我就在这卡了将近1h……（在此期间尝试调了下D1，结果发现根本没思路）
在临近比赛结束前15min，忽然灵光一闪，既然只统计个位数字，取值就只有$0$-$9$共十种，那为什么不……打表呢？
于是经过一番简单的运算，这道题就……A了。
#include<bits/stdc++.h>
using namespace std;
int q,lownum;
long long n,m,ans;
int main()
{
scanf("%d",&q);
for(int i=1;i<=q;i++) {
ans=0;
long long div=0,mod=0;
scanf("%lld%lld",&n,&m);
div=n/m;
mod=div%10;
div-=mod;
div/=10;
switch(m%10) {
case 0:
ans=0;
break;
case 1:
ans=div*45;
for(int j=1;j<=mod;j++) {
ans+=(j*1)%10;
}
break;
case 2:
ans=div*40;
for(int j=1;j<=mod;j++) {
ans+=(j*2)%10;
}
break;
case 3:
ans=div*45;
for(int j=1;j<=mod;j++) {
ans+=(j*3)%10;
}
break;
case 4:
ans=div*40;
for(int j=1;j<=mod;j++) {
ans+=(j*4)%10;
}
break;
case 5:
ans=div*25;
for(int j=1;j<=mod;j++) {
ans+=(j*5)%10;
}
break;
case 6:
ans=div*40;
for(int j=1;j<=mod;j++) {
ans+=(j*6)%10;
}
break;
case 7:
ans=div*45;
for(int j=1;j<=mod;j++) {
ans+=(j*7)%10;
}
break;
case 8:
ans=div*40;
for(int j=1;j<=mod;j++) {
ans+=(j*8)%10;
}
break;
case 9:
ans=div*45;
for(int j=1;j<=mod;j++) {
ans+=(j*9)%10;
}
break;
}
printf("%lld\n",ans);
}
return 0;
}
当然还是要提一下正解的思路的。
令$k=[\frac nm]$是从$1$到$n$的整数个数，可被$m$整除。我们可以注意到，因为我们只记下每个可被$m$整除的数字的最后一位数字，所以数字“周期”的长度不超过$10$。事实上，我们总是可以假设它是$10$，因为对于从0到9的所有$i$，都有$i\times m\equiv(10+i)\times m\ (mod\ 10)$。所以对于从$0$到$9$的所有$i$，使$cycle_i=m\times (i+1)\ mod\ 10$，然后答案是$[\frac k{10}]\sum_{i=0}9cycle_i+\sum_{i=0}{k\ mod\ 10}cycle_i$.
D. Equalizing by Division
这题就是分为两个难度，我调了一下easy的，但发现思路基本是错的，然后就放弃了……
至于Hard的……就以后再说吧。
E. Two Small Strings
F. Unstable String Sort
G. Path Queries
总之，以后还是要多刷题，多打比赛，多多听从老师教诲……