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

OI 笑传 #18

今天是 ABC 427 的 DEF。

D

博弈,套路的设状态,令 \(dp_{i,k_1,k_2,op}\) 表示棋子在点 \(i\),Alice 还剩 \(k_1\) 步可以走,Bob 还剩 \(k_2\) 步可以走,现在拿棋子的是 \(op\)\(0\) 是 Alice,\(1\) 是 Bob。此时 Alice 一定赢吗。

好像其实不用再开 \(op\) 一维的。

然后对于所有的 \(dp_{i,0,0,0}\),根据自己的字母附上值。

然后从 \((i,0,1,1),(i,1,1,0),(i,1,2,1)\) 这种顺序枚举每个点及其邻接边转移即可,时间复杂度是 \(O(KN)\) 的。足够了。

赛时被神秘 RE 卡了一会。

code

Show me the code
#define psb push_back
#define mkp make_pair
#define ls p<<1
#define rs (p<<1)+1
#define rep(i,a,b) for( int i=(a); i<=(b); ++i)
#define per(i,a,b) for( int i=(a); i>=(b); --i)
#define rd read()
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){ll x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;
}
const int N=3e5+45;
bitset<N> dp[16][16][3];
vector<int> e[N];
int n,m,k;
string s;
void init(){for(int i=1;i<=n;i++)e[i].clear();return ;
}
void solve(){cin>>n>>m>>k;cin>>s;s=' '+s;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;e[u].push_back(v);}for(int i=1;i<=n;i++){if(s[i]=='A')dp[i][0][0][0]=1;else dp[i][0][0][0]=0;}for(int b=1;b<=k;b++){for(int pp=0;pp<=1;pp++){int al=b-1+pp,bb=b; int op=!(al==bb);if(op==1){for(int i=1;i<=n;i++){bool kill=1;for(int v:e[i]){if(dp[v][al][bb-1][op^1]==0){kill=0;break;}}dp[i][al][bb][op]=kill;}}if(op==0){for(int i=1;i<=n;i++){bool kill=0;for(int v:e[i]){if(dp[v][al-1][bb][op^1]==1){kill=1;break;}}dp[i][al][bb][op]=kill;}}}}if(dp[1][k][k][0]==0){cout<<"Bob"<<'\n';}else cout<<"Alice"<<'\n';return ;
}
int main(){int T;cin>>T;while(T--){init();solve();}return 0;
}

E

读完题就想到可以把推垃圾的过程想象成自己在移动,于是每次移动检测下自己相对坐标下周围 \(H\times W\) 里面还有没有垃圾,由于 \(H,W\) 很小所以怎么做都行,BFS 找最小路径即可。

注意不能移动到垃圾上,还有要找到最小的包括全部垃圾的矩形范围进行操作。

code

Show me the code

F

这种数据范围除了去想搜素和神秘 DP 之外还有一个重要的东西就是折半查找。

tbd。

http://www.hskmm.com/?act=detail&tid=29277

相关文章:

  • 2025加药装置厂家权威推荐榜:精准计量与稳定运行优选指南
  • Linux文本搜索工具grep命令使用
  • 一款基于 .NET 开源免费、高效且用户友好文件搜索工具!
  • 2025上海保洁公司最新权威推荐榜:专业服务与用户口碑深度解
  • DedeCMS命令执行复现研究 | CVE-2025-6335 - 指南
  • 算法训练.16 - 实践
  • __pycache__是什么
  • 心得体会
  • 2025视频拍摄厂家最新权威推荐榜:专业设备与创意方案首选
  • Java连接MySQL数据库
  • Redis基础命令与数据结构概览
  • 2025年媒体投放机构权威推荐榜:精准策略与创新执行优选厂家
  • PHP计算过去一定时间段内日期范围函数
  • Git版本控制工具合并分支merge命令操作流程
  • 第七章 手写数字识别(终)
  • 2025南通摄影公司最新权威推荐榜:专业团队与创意服务口碑之
  • 在Kubernetes环境中引用变量的方法
  • 2025恒温恒湿车间厂家权威推荐:精密环境控制解决方案TOP
  • 2025预应力千斤顶厂家权威推荐榜:定制技术与耐用品质深度解
  • 实用指南:用Spark+Django打造食物营养数据可视化分析系统
  • 2025液压阀块厂家权威推荐榜:精密加工与直销优势深度解析
  • NOI/1.7编程基础之字符串/18:验证子串
  • 深入解析:【Linux网络】Socket编程:UDP网络编程实现DictServer
  • 2025焊接变位机厂家权威推荐榜:高效稳定与精准操控口碑之选
  • 20232404zxy 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • 2025年10月铝塑板厂家最新推荐排行榜,吉祥铝塑板,门头铝塑板,墙面铝塑板,干挂铝塑板,外墙铝塑板公司推荐
  • KunmingCai
  • 2025聚氨酯预聚体厂家最新权威推荐榜:技术创新与品质保障深
  • 杂题 9 月份
  • 2025防水包胶连接器厂家权威推荐榜:密封防护与耐用品质深度