这种题目居然因为没看到恰好挂了一发。。。
显然\(t=\min\{4\times Q,2\times H,S\}\)是装一杯的最小代价。
然后只要比较下\(2\times t\)和\(D\)的大小即可。
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
using namespace std;
int n,Q,H,S,D;
int main()
{
scanf("%d%d%d%d%d",&Q,&H,&S,&D,&n);RI t=min(min(4*Q,2*H),S);//求装一杯的最小代价
return printf("%lld\n",D<=2*t?1LL*(n>>1)*D+(n&1)*t:1LL*n*t),0;//比较2t和D的大小
}
一开始想复杂了，后来结合这是道B题才发现其实就是道送分题。。。
考虑翻转一个区间\([l,r]\)，如果\(s_l=s_r\)，那么这次翻转等价于翻转\([l+1,r-1]\)，是没有贡献的，否则必然有贡献。
故只要用总方案数\(\frac{n(n+1)}2+1\)减去各字无用方案数\(\sum \frac{t_i(t_i+1)}2\)即可。
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 200000
using namespace std;
int n,t[30];char s[N+5];
int main()
{
RI i;for(scanf("%s",s+1),n=strlen(s+1),i=1;i<=n;++i) ++t[s[i]&31];//统计各字符个数
long long ans=1LL*n*(n+1)/2+1;for(i=1;i<=26;++i) ans-=1LL*t[i]*(t[i]+1)/2;//用总方案数减去无用方案数
return printf("%lld\n",ans),0;
}
考虑我们必然尽可能走圆，也就是对于这个矩阵内的点，按横坐标排序，对纵坐标做最长上升子序列。
然而，当最后一行或最后一列有喷泉时，我们可能不得不走一个半圆。
然后发现只会在每一行喷泉都被选中或每一列喷泉都被选中的时候有这种情况，判一下就好了。
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 200000
#define mp make_pair
#define fi first
#define se second
#define Pi acos(-1)
using namespace std;
int n,X1,Y1,X2,Y2,f[N+5];pair<int,int> a[N+5];
int main()
{
RI i,x,y;for(scanf("%d%d%d%d%d",&X1,&Y1,&X2,&Y2,&n),i=1;i<=n;++i) scanf("%d%d",&x,&y),a[i]=mp(x,y);
if(X1>X2&&(swap(X1,X2),swap(Y1,Y2),0),Y1>Y2) for(swap(Y1,Y2),i=1;i<=n;++i) a[i].se=Y1+Y2-a[i].se;//转化成X1≤X2,Y1≤Y2
RI t=0,X=0,Y=0;for(sort(a+1,a+n+1),i=1;i<=n;++i)//找出矩阵内的点
X1<=a[i].fi&&a[i].fi<=X2&&Y1<=a[i].se&&a[i].se<=Y2&&(a[++t]=a[i],0);
for(n=t,f[t=0]=-1,i=1;i<=n;++i) f[f[t]<a[i].se?++t:lower_bound(f+1,f+t+1,a[i].se)-f]=a[i].se;//最长上升子序列
long double ans=100LL*(X2-X1+Y2-Y1)-t*(20-5*Pi);//每走一个1/4圆可减少20-5π的路程
return (t==X2-X1+1||t==Y2-Y1+1)&&(ans+=5*Pi),printf("%.12Lf\n",ans),0;//判断是否不得不走半圆
}
自己做出来的D题！
首先我们预处理出每个位置向左/向右到第一个\(B_i=1\)的位置的步数\(l_i,r_i\)。
考虑我们枚举一下左移总次数和右移总次数之差，就可以求出最后\(A\)中的每一位和\(B\)中的哪一位对应。
那么我们也就知道了\(A\)中哪些位需要修改。
假设最终向左边扩展了\(L\)位，向右边扩展了\(R\)位，则对于每个要修改的位需要满足\(L\ge l_i\)或者\(R\ge r_i\)。
假设左移总次数大于右移总次数，考虑从大到小枚举\(R\)，那么所有\(r_i\le R\)的已经满足了，而\(r_i>R\)的我们只要维护出\(\max\{l_i\}\)就得出了\(L_{\min}\)。
然后直接算一算就好了。
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 2000
using namespace std;
int n,l[N+5],r[N+5],v[N+5];char A[N+5],B[N+5];
int main()
{
RI i,j,k,res,ans=1e9;scanf("%s%s",A+1,B+1),n=strlen(A+1);
RI t=0;for(i=1;i<=n&&!t;++i) t|=B[i]==‘1‘;if(!t)//B中没有1
{for(i=1;i<=n;++i) if(A[i]==‘1‘) return puts("-1"),0;return puts("0"),0;}//判无解/0步
#define Pre(x) (((x)^1)?(x)-1:n)//左移一位
#define Nxt(x) (((x)^n)?(x)+1:1)//右移一位
for(i=1;i<=n;++i) {for(j=i;B[j]==‘0‘;j=Pre(j),++l[i]);for(j=i;B[j]==‘0‘;j=Nxt(j),++r[i]);}//预处理向左/向右第一个B[i]=1的步数
for(i=0;i<=n;++i)//左移总位数大于右移总位数
{
for(res=t=j=0;j^n;++j) v[j]=0;//清空
for(j=Nxt(i),k=1;k<=n;j=Nxt(j),++k) A[j]^B[k]&&(v[r[j]]=max(v[r[j]],l[j]),++t);//维护
for(j=n-1;~j;--j) ans=min(ans,i+2*(j+max(res-i,0))+t),res=max(res,v[j]);//从大到小枚举向右扩展范围
}
for(i=0;i<=n;++i)//右移总位数大于左移总位数，同上
{
for(res=t=j=0;j^n;++j) v[j]=0;
for(j=1,k=Nxt(i);j<=n;++j,k=Nxt(k)) A[j]^B[k]&&(v[l[j]]=max(v[l[j]],r[j]),++t);
for(j=n-1;~j;--j) ans=min(ans,i+2*(j+max(res-i,0))+t),res=max(res,v[j]);
}
return printf("%d\n",ans),0;
}
发现我们肯定是要让\(A\)中所有不该是\(1\)的位置上的\(1\)都到需要\(1\)的位置上去，因此这样定义：
显然对于中间点，无论如何交换，都仍然是\(1\)。
考虑合法情况对应的图应该是若干起点-一堆中间点-终点的链，因此我们设\(f_{i,j}\)表示使用了\(i\)个中间点，组成了\(j\)条链的方案数。
转移分两种，加一个中间点或加一条链：
统计答案时只要枚举有多少中间点并没有参与构成链。
设中间点有\(s\)个，起点和终点各有\(t\)个（显然\(s+t=k\)），答案式为：
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 10000
#define X 998244353
#define C(x,y) (1LL*Fac[x]*IFac[y]%X*IFac[(x)-(y)]%X)
using namespace std;
int n,Fac[N+5],IFac[N+5],f[N+5][N+5];char A[N+5],B[N+5];
I int QP(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
int main()
{
RI i,j,s=0,t=0;for(scanf("%s%s",A+1,B+1),n=strlen(A+1),i=1;i<=n;++i) A[i]&1&&(B[i]&1?++s:++t);//统计中间点、起点终点个数
for(Fac[0]=i=1;i<=n;++i) Fac[i]=1LL*Fac[i-1]*i%X;//预处理阶乘
for(IFac[n]=QP(Fac[n],X-2),i=n;i;--i) IFac[i-1]=1LL*IFac[i]*i%X;//预处理阶乘逆元
for(f[0][0]=1,i=0;i<=s;++i) for(j=0;j<=t;++j)//DP转移
i&&(f[i][j]=(1LL*i*j%X*f[i-1][j]+f[i][j])%X),j&&(f[i][j]=(1LL*j*j%X*f[i][j-1]+f[i][j])%X);
RI ans=0;for(i=0;i<=s;++i) ans=(1LL*C(s+t,i)*C(s,i)%X*Fac[i]%X*Fac[i]%X*f[s-i][t]+ans)%X;//统计答案
return printf("%d\n",ans),0;
}
Yes，\(m\)道为No。显然最优策略就是当前哪种答案多就答哪个。
考虑\(O(n^2)\)的暴力，即设\(f_{i,j}\)为剩\(i\)个Yes和\(j\)个No时的期望答对题数。
当\(i> j\)时的转移为：
闪总最喜欢也最擅长的东西。
考虑我们从原点出发，走到\((n,m)\)。
我们画一条\(y=x\)的直线，整个坐标系就被划分成两部分，发现直线下方\(x>y\)，直线上方\(y>x\)。
如果我们不经过对角线，那么根据我们的最优策略，无论如何都能得到\(\max\{n,m\}\)的贡献。
而对于对角线上的点，都有\(\frac12\)的概率能提供\(1\)的贡献。
所以我们只要计算出走到对角线上的方案数，除以总方案数得到走到对角线上的概率，再乘上\(\frac12\)就是期望贡献了。
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 500000
#define X 998244353
#define I2 499122177
#define C(x,y) (1LL*Fac[x]*IFac[y]%X*IFac[(x)-(y)]%X)//组合数
#define S(x,y) C((x)+(y),x)//求向右走x单位，向上走y单位的方案数
using namespace std;
int n,m,Fac[2*N+5],IFac[2*N+5];
I int QP(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
int main()
{
RI i,ans=0;scanf("%d%d",&n,&m),n<m&&(n^=m^=n^=m);
for(Fac[0]=i=1;i<=n+m;++i) Fac[i]=1LL*Fac[i-1]*i%X;//预处理阶乘
for(IFac[n+m]=QP(Fac[n+m],X-2),i=n+m;i;--i) IFac[i-1]=1LL*IFac[i]*i%X;//预处理阶乘逆元
for(i=1;i<=m;++i) ans=(1LL*S(i,i)*S(n-i,m-i)+ans)%X;//统计走到每个对角线上的点的方案数
return printf("%d\n",(1LL*I2*ans%X*QP(S(n,m),X-2)+n)%X),0;//计算答案
}
【AtCoder】AtCoder Grand Contest 019 解题报告
原文：https://www.cnblogs.com/chenxiaoran666/p/AtCoderAGC019.html