当前位置: 首页 > news >正文

CF1784E

对 DP 套 DP 的理解又加深了一分。

注意到,当局比分只有 \(0:0,0:1,1:0,1:1\) 四种情况,不妨将其压在一起考虑。

如何判断优劣?相当于从初始比分 \(0:0\),初始下标 \(i=1\) 开始发生 \(s\) 后续的一系列事件。

解决无限循环的状态,找到每个进程有多少种本质不同的状态,并在完整进行一个循环后在状态间进行建图,就可以知道进行若干个循环后走到的点了

而从 \(0:0\) 开始,无限循环,最终必然走到一个环,我们只关心这个环的胜局减去负局的局数。

考虑这一张图是什么东西,四个初始比分,经历确定的一轮后会各自达到一个比分,也就是每个点的出边有且只有一条,那就是一个基环树森林,而我们只关心从 \(0:0\) 出发走到的那个环。

如何求环的边权和?由于DP过程中涉及到填写问号,暴力的想法就是记录下每个初始状态走到当前这一步走到了哪个点以及胜局减负局数,最后暴力建图判断,这很爆炸。

能否减少?注意到点数很少,因此可以枚举环上的点有哪些,只记录环上点的出边的边权和,这样就压缩到了一维状态

因此,\(2^4\) 枚举环上的点有哪些,并记录其边权和,然后暴力DP。

最后判断这个实际的环与我枚举的环有什么差异即可。

#include<bits/stdc++.h>
using namespace std;
#define N 2050
#define int long long 
const int p=998244353;
int n,m,f[N][N],g[N][N],ans[3];
#define pr pair<int,int>
#define mk make_pair
int out[N],tim[N];
pr to[N][2];
char s[N];
vector<int>cir[N];
signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);for(int i=0;i<(1<<8);++i){for(int j=0;j<4;++j)out[j]=(i>>j+j)&3,tim[j]=0;int x=0,now=0;while(!tim[x]){tim[x]=++now;x=out[x];}int t=tim[x];int stu=0;for(int j=0;j<4;++j)if(tim[j]>=t)stu|=1<<j;cir[stu].push_back(i);}string str;cin>>str;n=str.size();str=" "+str;int nows=(n+1>>1)*4,start=(1<<2)|(2<<4)|(3<<6);for(int circ=0;circ<(1<<4);++circ){for(int i=0;i<(1<<8);++i){for(int j:{0,1}){int ni=0,nv=0;for(int x=0;x<4;++x){int t=(i>>x+x)&3;if(!j){if(t&1)nv+=(circ>>x)&1,t=0;else t|=1;}else {if(t&2)nv-=(circ>>x)&1,t=0;else t^=2;}ni|=t<<x+x;}to[i][j]=mk(ni,nv);}}int cnt=__builtin_popcount(circ);int up=nows+(n+1>>1)*cnt,down=nows-(n+1>>1)*cnt;for(int i=0;i<(1<<8);++i)for(int s=down;s<=up;++s)f[i][s]=g[i][s]=0;f[start][nows]=1;// cout<<nows<<" "<<start<<" "<<down<<' '<<up<<"\n";for(int step=1;step<=n;++step){for(int i=0;i<(1<<8);++i){for(int j:{0,1}){if(j==0&&str[step]=='b')continue;if(j==1&&str[step]=='a')continue;for(int s=down;s<=up;++s)if(f[i][s]){// cout<<"trans "<<to[i][j].first<<" "<<s+to[i][j].second<<"\n";g[to[i][j].first][s+to[i][j].second]+=f[i][s];}}}for(int i=0;i<(1<<8);++i)for(int s=down;s<=up;++s)f[i][s]=g[i][s]%p,g[i][s]=0;}for(auto i:cir[circ]){for(int s=down;s<=up;++s)if(f[i][s]){// cout<<circ<<" "<<i<<"\n";ans[s<nows?2:(s==nows?1:0)]+=f[i][s];}}}cout<<(ans[0]%p+p)%p<<"\n"<<(ans[1]%p+p)%p<<"\n"<<(ans[2]%p+p)%p<<"\n";
}
http://www.hskmm.com/?act=detail&tid=31123

相关文章:

  • nSwitch 存档自动备份系统模块 - autoSAVE
  • java基础7-字符串
  • 乐云具身活动体验
  • 【技术解决方案】联邦学习中遇到的Non-IID问题——隐语SecretFlow
  • 学习笔记:KTT
  • 题解:P10104 [GDKOI2023 提高组] 异或图
  • 2025 年筛网厂家推荐榜:聚焦场景适配与高效需求,锰钢筛网/聚氨酯筛网/合金焊接筛网/自清洁筛网/防堵筛网厂家滨州沃森网业成优选
  • P7076 [CSP-S2020] 动物园
  • 汽车价格战全面熄火了?不卷价格该卷什么? - 教程
  • P10067 [CCO 2023] Real Mountains
  • 先辈题解
  • U-Boot启动探秘:从汇编到命令行的奇幻之旅 - 指南
  • 双指针的初步了解
  • 倍增并查集学习笔记
  • 两数相加-leetcode
  • CF2147E
  • 线程共享区域
  • ZR 2025 NOIP 二十连测 #1
  • 运行时数据区
  • work1
  • 2025 年液压机厂家推荐榜:伺服/小型/大型/数控/液压机厂家口碑推荐,品质可靠 聚焦智能适配,助力企业高效生产
  • 快速上手!山海鲸 4 种高频数据接入方式
  • AI赋能,重塑未来招聘:深度解析易路AI人岗匹配解决方案
  • 2025高级语言程序设计第一次作业lcr
  • luogu 个人主页
  • D230809E. 勇敢的阿乐
  • 解码Linux文件IO之标准IO
  • 10.14 CSP-S模拟31 改题记录
  • 高级程序语言第一次作业
  • 安装devc++过程的分享以及问题的记录