题目：
1.给出一个由0,1组成的环
求最少多少次交换（任意两个位置）使得0,1靠在一起
n<=1000
2.两个数列，支持在第一个数列上区间+1，-1 每次花费为1
求a变成b的最小代价
n<=1e5
3.
有n首歌，每首歌每秒有p[i]的几率被破译（当大于等于t时自动破译），求期望破译歌数
题解：
t1t2都是送分题
t1 显然枚举每个位置作为开头就可以了
可以前缀和优化到O（n）
t2我们从左往右考虑每个元素，发现对于左边一位的操作是知道的
另外我们会发现一个点是不可能既有+又有-操作的（很好yy）
于是就可以直接贪心了
t3首先比较容易想到的是f[i][j]表示前i个，用了t时间的概率
然后枚举经过多长时间才到下一个来转移
但是这样是n*t*t的
考虑优化
我们会发现f[i][j]和f[i][j-1]就差了一点
然后通过之间关系来转移（看代码吧太复杂了）
考试的时候没有注意最后可能未到t时间就用完了（对拍竟然也写错了）
然后竟然还有80
另外写的时候有个细节就是如果上一次是k，但是这一次用时超过t了，我们要归为上一类
这个概率的计算我们只需要通过所有的-当前还在的来计算就可以了
代码：
t1:
#include <bits/stdc++.h> using namespace std; #define rint register int #define IL inline #define rep(i,h,t) for (rint i=h;i<=t;i++) #define dep(i,t,h) for (rint i=t;i>=h;i--) const int N=3000; char s[N]; int n; int main() { freopen("swap.in","r",stdin); freopen("swap.out","w",stdout); ios::sync_with_stdio(false); cin>>n; cin>>s; int cnt=0; dep(i,n,1) { s[i+n]=s[i]=s[i-1]; if (s[i]=='1') cnt++; } int ans=1e9; rep(i,1,n) { int ans2=0; rep(j,i,i+cnt-1) if (s[j]=='0') ans2++; ans=min(ans,ans2); } cout<<ans<<endl; return 0; }
t2:
#include <bits/stdc++.h> using namespace std; #define rint register ll #define IL inline #define rep(i,h,t) for (rint i=h;i<=t;i++) #define dep(i,t,h) for (rint i=t;i>=h;i--) #define ll long long const ll N=2e5; ll a[N],b[N]; ll ans,n; int main() { freopen("bricks.in","r",stdin); freopen("bricks.out","w",stdout); ios::sync_with_stdio(false); cin>>n; rep(i,1,n) cin>>a[i]; rep(i,1,n) cin>>b[i]; ll lst=0; rep(i,1,n) { if (b[i]>=a[i]) { if (lst>0) ans+=max(b[i]-a[i]-lst,0ll); else ans+=b[i]-a[i]; } else { if (lst<0) ans+=max(a[i]-b[i]+lst,0ll); else ans+=a[i]-b[i]; } lst=b[i]-a[i]; } cout<<ans<<endl; return 0; }
t3:
#include <bits/stdc++.h> using namespace std; #define rint register int #define IL inline #define rep(i,h,t) for (rint i=h;i<=t;i++) #define dep(i,t,h) for (rint i=t;i>=h;i--) int n,T; int b[6000]; double f[2][5010],a[6000]; int main() { freopen("song.in","r",stdin); freopen("song.out","w",stdout); ios::sync_with_stdio(false); cin>>n>>T; rep(i,1,n) cin>>a[i]>>b[i],a[i]/=100; f[0][0]=1; double num=0; double jl=1; rep(i,1,n) { int lst=(i+1)%2,now=i%2; memset(f[now],0,sizeof(f[now])); double ans2=1,ans3=0; rep(j,1,b[i]-1) ans2*=(1-a[i]); rep(j,1,T) { ans3*=1-a[i]; f[now][j]=f[lst][j-1]*a[i]+ans3*a[i]; if (j>=b[i]) f[now][j]+=f[lst][j-b[i]]*ans2*(1-a[i]); if (j>=b[i]) ans3-=f[lst][j-b[i]]*ans2; ans3+=f[lst][j-1]; } num+=f[now][T]*i; if (i==n) { rep(j,1,T-1) num+=f[now][j]*i; } double ans=0; rep(j,1,T) ans+=f[now][j]; num+=(jl-ans)*(i-1); jl=ans-f[now][T]; } printf("%.4f",num); return 0; } //考试的时候少处理了最后剩余的状态 //对拍竟然也没处理 还有80分 //细节就是从上一层到这一层的时候有可能会有需要超过t才能到达的需要算入上一层