2018.10.05 TOPOI提高组模拟赛 解题报告
2024-09-05 16:23:28
得分： \(100+5+100=205\)（真的是出乎意料）
\(T1\)：抵制克苏恩（点此看题面）
原题： 【BZOJ4832】[Lydsy1704月赛] 抵制克苏恩
应该还是一个比较简单的\(DP\)吧（我是用记忆化搜索实现的）。
可以用\(f_{n,A,B,C}\)来表示还有\(n\)个回合，三种血量奴隶主个数分别为\(A,B,C\)时所造成的期望伤害。
比较显然，应该有四种情况：
- 第一种情况：对一血奴隶主造成伤害。这样就杀死了一个一血奴隶主，且不会增加新的奴隶主，因此可以将\(f_{n,A,B,C}\)加上\(\frac A{A+B+C+1}f_{n-1,A-1,B,C}\)。
- 第二种情况：对二血奴隶主造成伤害。此时要分情况讨论：
- \(A+B+C<7\)：这样相当于将一血奴隶主个数加\(1\)，二血奴隶主个数减\(1\)，并增加一个新的三血奴隶主，因此将\(f_{n,A,B,C}\)加上\(\frac B{A+B+C+1}f_{n-1,A+1,B-1,C+1}\)。
- \(A+B+C=7\)：这样相当于将一血奴隶主个数加\(1\)，二血奴隶主个数减\(1\)，由于奴隶主个数已满，故不增加新的奴隶主，因此将\(f_{n,A,B,C}\)加上\(\frac B{A+B+C+1}f_{n-1,A+1,B-1,C}\)。
- 第三种情况：对三血奴隶主造成伤害。此时也要分类讨论：
- \(A+B+C<7\)：这样相当于将二血奴隶主个数加\(1\)，三血奴隶主个数不变，因此将\(f_{n,A,B,C}\)加上\(\frac C{A+B+C+1}f_{n-1,A,B+1,C}\)。
- \(A+B+C=7\)：这样相当于将二血奴隶主个数加\(1\)，三血奴隶主个数减\(1\)，因此将\(f_{n,A,B,C}\)加上\(\frac C{A+B+C+1}f_{n-1,A,B+1,C-1}\)。
- 第四种情况：对英雄造成伤害。则场上各血量奴隶主个数不变，且对英雄造成伤害加\(1\)，因此将\(f_{n,A,B,C}\)加上\(\frac1{A+B+C+1}(f_{n-1,A,B,C}+1)\)。
代码实现还是比较简单的：
#include<bits/stdc++.h>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define uint unsigned int
#define LL long long
#define ull unsigned long long
#define swap(x,y) (x^=y,y^=x,x^=y)
#define abs(x) ((x)<0?-(x):(x))
#define INF 1e9
#define Inc(x,y) ((x+=(y))>=MOD&&(x-=MOD))
#define ten(x) ((x<<3)+(x<<1))
#define N 50
using namespace std;
int n,A,B,C;
class FIO
{
private:
#define Fsize 100000
#define tc() (FinNow==FinEnd&&(FinEnd=(FinNow=Fin)+fread(Fin,1,Fsize,stdin),FinNow==FinEnd)?EOF:*FinNow++)
#define pc(ch) (FoutSize<Fsize?Fout[FoutSize++]=ch:(fwrite(Fout,1,FoutSize,stdout),Fout[(FoutSize=0)++]=ch))
int f,FoutSize,OutputTop;char ch,Fin[Fsize],*FinNow,*FinEnd,Fout[Fsize],OutputStack[Fsize];
public:
FIO() {FinNow=FinEnd=Fin;}
inline void read(int &x) {x=0,f=1;while(!isdigit(ch=tc())) f=ch^'-'?1:-1;while(x=ten(x)+(ch&15),isdigit(ch=tc()));x*=f;}
inline void read_char(char &x) {while(isspace(x=tc()));}
inline void read_string(string &x) {x="";while(isspace(ch=tc()));while(x+=ch,!isspace(ch=tc())) if(!~ch) return;}
inline void write(int x) {if(!x) return (void)pc('0');if(x<0) pc('-'),x=-x;while(x) OutputStack[++OutputTop]=x%10+48,x/=10;while(OutputTop) pc(OutputStack[OutputTop]),--OutputTop;}
inline void write_char(char x) {pc(x);}
inline void write_string(string x) {register int i,len=x.length();for(i=0;i<len;++i) pc(x[i]);}
inline void end() {fwrite(Fout,1,FoutSize,stdout);}
}F;
class Class_DFS//记忆化搜索
{
private:
#define eps 1e-10
double f[N+5][10][10][10];//用f[n][A][B][C]来表示还有n个回合，三种血量奴隶主个数分别为A,B,C时所造成的期望伤害
public:
inline double GetAns(int n,int A,int B,int C)//记忆化搜索
{
if(!n||A<0||B<0||C<0) return 0;//如果剩余回合数为0或当前状态不合法，返回0
if(f[n][A][B][C]>eps) return f[n][A][B][C];//如果已访问过当前状态，返回上次求解的答案
if(A+B+C<7) f[n][A][B][C]=(A*GetAns(n-1,A-1,B,C)+B*GetAns(n-1,A+1,B-1,C+1)+C*GetAns(n-1,A,B+1,C)+GetAns(n-1,A,B,C)+1)/(A+B+C+1);//对于A+B+C<7的情况
else f[n][A][B][C]=(A*GetAns(n-1,A-1,B,C)+B*GetAns(n-1,A+1,B-1,C)+C*GetAns(n-1,A,B+1,C-1)+GetAns(n-1,A,B,C)+1)/(A+B+C+1);//对于A+B+C=7的情况
return f[n][A][B][C];//返回
}
}DFS;
int main()
{
freopen("cthun.in","r",stdin),freopen("cthun.out","w",stdout);
register int i,T;F.read(T);
while(T--) F.read(n),F.read(A),F.read(B),F.read(C),printf("%.2lf\n",DFS.GetAns(n,A,B,C));//对于每组数据输出答案
return 0;
}
\(T2\)：大数（点此看题面）
比赛时看到数据范围以及输入每次给出一个区间，而且可以离线做，于是瞬间想到了莫队算法。
但是，想出了莫队，却不知道怎么去做（毕竟还需要一个玄学的转化），于是只好交了暴力。
考虑用\(S_{i,j}\)表示\(S\)的子串\(S[i...j]\)所表示的数字模\(P\)的余数，并用\(Front_i\)表示\(S\)的子串\(S[1...i]\)所表示的数字模\(P\)的余数。
则不难发现，如果\(P≠2\)且\(P≠5\)（这两种情况\(P\)较小，可以特判处理掉），\(S_{i,j}\equiv Front_j-Front_i(mod\) \(P)\)。
这样一来，要求出多少个\(S_{i,j}=0\)，似乎就等价于求出有多少个\(Front_i=Front_j\)。
再说得明白一点，就相当于要求出一个区间内有多少对相等的数。
于是就变成莫队裸题了。
代码如下：
#include<bits/stdc++.h>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define uint unsigned int
#define LL long long
#define ull unsigned long long
#define swap(x,y) (x^=y,y^=x,x^=y)
#define abs(x) ((x)<0?-(x):(x))
#define INF 1e9
#define Inc(x,y) ((x+=(y))>=MOD&&(x-=MOD))
#define ten(x) (((x)<<3)+((x)<<1))
#define N 100000
using namespace std;
int n,Q,p_num,MOD,block_size,a[N+5],p[N+5],bl[N+5],cnt[N+5];
LL res[N+5];
string st;
struct Query
{
int l,r,pos;
inline bool operator < (const Query x) const
{
return bl[l]^bl[x.l]?bl[l]<bl[x.l]:(bl[l]&1?r<x.r:r>x.r);
}
}q[N+5];
class FIO
{
private:
#define Fsize 100000
#define tc() (FinNow==FinEnd&&(FinEnd=(FinNow=Fin)+fread(Fin,1,Fsize,stdin),FinNow==FinEnd)?EOF:*FinNow++)
#define pc(ch) (FoutSize<Fsize?Fout[FoutSize++]=ch:(fwrite(Fout,1,FoutSize,stdout),Fout[(FoutSize=0)++]=ch))
int f,FoutSize,OutputTop;char ch,Fin[Fsize],*FinNow,*FinEnd,Fout[Fsize],OutputStack[Fsize];
public:
FIO() {FinNow=FinEnd=Fin;}
inline void read(int &x) {x=0,f=1;while(!isdigit(ch=tc())) f=ch^'-'?1:-1;while(x=ten(x)+(ch&15),isdigit(ch=tc()));x*=f;}
inline void read_char(char &x) {while(isspace(x=tc()));}
inline void read_string(string &x) {x="";while(isspace(ch=tc()));while(x+=ch,!isspace(ch=tc())) if(!~ch) return;}
inline void write(LL x) {if(!x) return (void)pc('0');if(x<0) pc('-'),x=-x;while(x) OutputStack[++OutputTop]=x%10+48,x/=10;while(OutputTop) pc(OutputStack[OutputTop]),--OutputTop;}
inline void write_char(char x) {pc(x);}
inline void write_string(string x) {register int i,len=x.length();for(i=0;i<len;++i) pc(x[i]);}
inline void end() {fwrite(Fout,1,FoutSize,stdout);}
}F;
class Key//对于P=2或P=5的情况特判处理
{
private:
int tot[N+5],sum[N+5];
public:
inline void Solve()
{
register int i,l,r;
for(i=1,n=st.length();i<=n;++i)//利用前缀和思想
{
sum[i]=sum[i-1],tot[i]=tot[i-1];
if((st[i-1]&15)%MOD==0) sum[i]+=i,++tot[i];
}
for(i=1;i<=Q;++i) F.read(l),F.read(r),F.write(sum[r]-sum[l-1]-(tot[r]-tot[l-1])*(l-1)),F.write_char('\n');
}
}S;
inline int find(int x)//求出一个元素离散化后的值
{
register int l=1,r=p_num,mid;
for(mid=l+r>>1;l<=r;mid=l+r>>1) p[mid]<x?l=mid+1:r=mid-1;//二分查找
return l;
}
int main()
{
register int i;register LL tn=1;
F.read(MOD),F.read_string(st),F.read(Q),n=st.length();
if(MOD==2||MOD==5) return S.Solve(),F.end(),0;//特判P=2或P=5的情况
for(block_size=sqrt(n),i=n;i;--i) p[i]=a[i]=(tn*(st[i-1]&15)%MOD+a[i+1])%MOD,tn=ten(tn)%MOD;//计算出从S[1...i]%P的值
for(sort(p+1,p+n+2),p_num=unique(p+1,p+n+2)-p-1,i=1;i<=n+1;++i) a[i]=find(a[i]);//离散化
for(i=1;i<=Q;++i) F.read(q[q[i].pos=i].l),F.read(q[i].r),bl[i]=(i-1)/block_size+1;//读入询问，并分块
int L=1,R=1;register LL ans=0;
for(sort(q+1,q+Q+1),cnt[a[1]]=i=1;i<=Q;++i)//将询问排序
{
++q[i].r;//将右边界加1
while(R<q[i].r) ++cnt[a[++R]],ans+=cnt[a[R]]-1;//莫队的基本操作
while(L>q[i].l) ++cnt[a[--L]],ans+=cnt[a[L]]-1;
while(R>q[i].r) ans-=cnt[a[R]]-1,--cnt[a[R--]];
while(L<q[i].l) ans-=cnt[a[L]]-1,--cnt[a[L++]];
res[q[i].pos]=ans;//存储答案
}
for(i=1;i<=Q;++i) F.write(res[i]),F.write_char('\n');//输出答案
return F.end(),0;
}
\(T3\)：神奇项链（点此看题面）
原题： 【BZOJ3790】神奇项链（权限题）
据说是 \(Manacher\)算法+贪心，但是，做这题时我还不会\(Manacher\)... ...
怎么办呢？只好写\(O(n^2)\)大暴力。
然而，数据太水，居然跑过了！？
既然是暴力，就不上代码了吧。更何况我懒得去打正解了。
最新文章
- 【Java每日一题】20161226
- JS实战 · 零碎笔记
- html slelect 标签默认值
- HighCharts中Y轴颜色设置
- 【Leafletjs】4.L.Map 中文API
- WebBrowser 中遍历所有的frames
- 转：浅谈Radius协议 -来自CSDN：http://blog.csdn.net/wangpengqi/article/details/17097221
- redis OK
- go exec: "gcc": executable file not found in %PATH%
- Ubuntu不可以ping百度，但是可以ping通其ip
- 201521123012 《Java程序设计》第四周学习总结
- 【JavaScript的基本语法】
- javascript 函数后面有多个小括号f( )( )( )...
- Centos6系列Bond配置方法
- JavaScript进阶系列1：performace和console.time性能测试
- Python3出现"No module named 'MySQLdb'"问题-以及使用PyMySQL连接数据库
- 第七周PSP 新折线图和饼图 个人时间管理
- Apache服务器下phalcon项目报Mod-Rewrite is not enabled问题
- CentOS 7安装Hadoop 3.0.0
- Day 43数据库（Day1）