10.31日志

1.Problem - A - Codeforces

容易发现只有当01连续交替的时候才会发生平滑移位,当0/1位于1或者n或者有两个及以上连续的时候那么无论如何都不会再改变了,因此我们可以利用双指针去看从i开始最长的连续01串，并且这一段01串经过数次操作之后会出现4种情况

1.a[l] == a[r] && a[l] == 1

那么中间这一段会全变为1

此时的操作次数就是中间0的个数

2.a[l] == a[r] && a[l] == 0

中间一段会全变成0

此时的操作次数就是中间1的个数

3.a[l] != a[r] && a[l] == 1

中间所有的1都会移动到最左端紧挨在一起,0则紧挨在右边

此时操作次数就是cnt1 - 1 || cnt0 - 1(将所有1移到最左边减去原来就在左边的1)

3.a[l] != a[r] && a[l] == 0

中间所有的0都会移动到最左端紧挨在一起,1则紧挨在右边

此时操作次数就是cnt1 - 1 || cnt0 - 1

利用双指针按照发现的规则对每一段进行检查处理即可

#define yyy cout<<"Yes"<<"\n" 
#define nnn cout<<"No"<<"\n" 
#define x first 
#define y second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<ll , ll> pii;
const int N = 5e5 + 10,inf = 0x3f3f3f3f;int n;
int a[N];int main()
{IOS;cin>>n;for(int i = 1 ; i <= n ; i++){cin>>a[i];}int ans = 0;for(int i = 1 ; i <= n ; i++){int j = i + 1;int cnt0 = 0,cnt1 = 0;if(a[i] == a[j]){continue;}if(a[i]){cnt1++;}else{cnt0++;}while(a[j] != a[j - 1] && j <= n){if(a[j]){cnt1++;}else{cnt0++;}j++;}if(a[i] == a[j - 1] && a[i] == 1){ans = max(ans , cnt0);for(int k = i ; k <= j - 1 ; k++){a[k] = 1;}}else if(a[i] == a[j - 1] && a[i] == 0){ans = max(ans , cnt1);for(int k = i ; k <= j - 1 ; k++){a[k] = 0;}}else{ans = max(ans , cnt0 - 1);if(a[i] == 1){for(int k = i ; k <= i + cnt1 - 1 ; k++){a[k] = 1;}for(int k = i + cnt1 ; k <= j - 1 ; k++){a[k] = 0;}}else{for(int k = i ; k <= i + cnt1 - 1 ; k++){a[k] = 0;}for(int k = i + cnt1 ; k <= j - 1 ; k++){a[k] = 1;}}}i = j - 1;}cout<<ans<<"\n";for(int i = 1 ; i <= n ; i++){cout<<a[i]<<" ";}
}

2.Problem - C - Codeforces

emmm感觉并不算难,但是因为精度问题wa了两发,要不是能看到数据估计还要debug一阵,对于两只(li , ri)与(l[i + 1] , r[i + 1])两只鲨鱼得到的期望奖金实际上就是求2000 * 乘积是p的倍数的概率,那么就很好想了,暴力枚举显然不可行,那么我们就能想到当li ~ ri中是p的倍数的数可以跟l[i + 1] ~ r[i + 1]中的任何一个数乘出p的倍数同理i+1也一样,最后再容斥一下将减掉两个范围中p倍数个数的乘积然后除去范围相乘即可,那么如何知道li~ri中p的倍数个数呢,也容易求,利用前缀和的思想ri / p就是0~ri中p倍数的个数(li - 1) / p就是0 ~ li-1中p倍数的个数,那么前者减去后者就是li~ri中p的倍数的个数了,我们用f[i]表示li~ri中p的倍数的个数那么对于i和i+1之间得到的期望奖金就是

2000.0 * （f[i] * (r[i + 1] - l[i + 1] + 1) + f[i + 1] * (r[i] - l[i] + 1) - f[i] * f[i + 1]) / ((r[i] - l[i] + 1) * (r[i + 1] - l[i + 1] + 1))

需要注意的是这样会wa在精度上,因为分子即使不算这个2000也已经到了1e18的级别了,这种时候我们只需要调换一下顺序让2000先除分母再去乘分子就可以解决这个问题了

#define yyy cout<<"Yes"<<"\n" 
#define nnn cout<<"No"<<"\n" 
#define x first 
#define y second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<ll , ll> pii;
const int N = 5e5 + 10,inf = 0x3f3f3f3f;int n,p;
pii a[N];
ll f[N];int main()
{IOS;cin>>n>>p;for(int i = 1 ; i <= n ; i++){cin>>a[i].x>>a[i].y;f[i] = a[i].y / p - (a[i].x - 1) / p;}  a[n + 1] = a[1],f[n + 1] = f[1];long double ans = 0; for(int i = 1 ; i <= n ; i++){ll ri = a[i].y,li = a[i].x;ll rj = a[i + 1].y,lj = a[i + 1].x;ans += (f[i] * (rj - lj + 1) + f[i + 1] * (ri - li + 1) - f[i] * f[i + 1]) * (2000.0 / ((ri - li + 1) * (rj - lj + 1)));    }printf("%.8Lf",ans);
}