【DP+博弈】ABC195 E

ゞ浴缸里的玫瑰 2024-03-17 15:40 64阅读 0赞

[E - Lucky 7 Battle (atcoder.jp)][E - Lucky 7 Battle _atcoder.jp]

题意：

![44faf1c04ab5422d8fc8286287d26dbc.png][]

思路：

![85d0077e3c8b49988d855da0f23d1580.png][]

Code：

#include <bits/stdc++.h>
    
    //#define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    const int Inf=0x3f3f3f3f;
    
    string s,x;
    
    int N;
    int dp[mxn][10];
    
    void solve(){
    	cin>>N>>s>>x;
    	s=" "+s;
    	x=" "+x;
    	dp[N][0]=1;
    	for(int i=N;i;i--){
    		int d=s[i]-'0';
    		for(int j=0;j<7;j++){
    			if(x[i]=='T'){
    				if(dp[i][(j*10)%7]||dp[i][(j*10+d)%7]) dp[i-1][j]=1;
    			}else{
    				if(dp[i][(j*10)%7]&&dp[i][(j*10+d)%7]) dp[i-1][j]=1;
    			}
    		}
    	}
    	if(dp[0][0]!=0) cout<<"Takahashi"<<'\n';
    	else cout<<"Aoki"<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[E - Lucky 7 Battle _atcoder.jp]: https://atcoder.jp/contests/abc195/tasks/abc195_e
[44faf1c04ab5422d8fc8286287d26dbc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/75e115eb53044a4f8e76d653c998ab5a.png
[85d0077e3c8b49988d855da0f23d1580.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/85f9907d50cb46a29dd496ba4e120804.png

发表评论取消回复

表情：

评论列表（有 0 条评论，64人围观）

还没有评论，来说两句吧...

相关阅读

相关 Atcoder ABC 139E

Atcoder ABC 139E 题意: > n支球队大循环赛，每支队伍一天只能打一场，求最少几天能打完。解法： > 考虑抽象图论模型，既然一天只...

爱被打了一巴掌/ 2024年04月20日 10:31/ 0 赞/ 101 阅读

相关【DP】ABC271 E - Subsequence Path

[E - Subsequence Path (atcoder.jp)][E - Subsequence Path _atcoder.jp] 题意：给定一个路径序列，请问1

客官°小女子只卖身不卖艺/ 2024年03月23日 11:21/ 0 赞/ 64 阅读

相关【状态设计优化DP】ABC307 E

[E - Distinct Adjacent (atcoder.jp)][E - Distinct Adjacent _atcoder.jp] 题意： ![d9735a1e

﹏ヽ暗。殇╰゛Y/ 2024年03月17日 18:11/ 0 赞/ 38 阅读

相关 ABC 195 C

不知道该怎么解释这道题，反正我不太会，感觉很帅题意： ![5ea04594676f4a78a31bec299de61d1a.png][] Code： incl

た入场券/ 2024年03月17日 15:40/ 0 赞/ 71 阅读

相关【二维属性+贪心+双指针】ABC 195 D

[D - Shipping Center (atcoder.jp)][D - Shipping Center _atcoder.jp] 题意： ![86fab8a4ccff

绝地灬酷狼/ 2024年03月17日 15:40/ 0 赞/ 68 阅读

相关【DP+博弈】ABC195 E

[E - Lucky 7 Battle (atcoder.jp)][E - Lucky 7 Battle _atcoder.jp] 题意： ![44faf1c04ab542

ゞ浴缸里的玫瑰/ 2024年03月17日 15:40/ 0 赞/ 65 阅读

相关【子序列+状压DP】ABC308 E MEX

这应该算是很套路的题，照理说是要做出来的 [E - MEX (atcoder.jp)][E - MEX _atcoder.jp] 题意： ![e6a5990b05cf48

雨点打透心脏的1/2处/ 2024年03月17日 13:55/ 0 赞/ 61 阅读

相关【数学】ABC 319 E

[E - Bus Stops][] 题意： ![f19239bed77b4ffda13a74736273c59e.png][] ![7d16c61674c24f709d8

朱雀/ 2024年03月04日 08:04/ 0 赞/ 116 阅读

相关博弈DP：PIPI的炸弹

博弈DP：PIPI的炸弹文章目录博弈DP：PIPI的炸弹问题思路代码问题 !

落日映苍穹つ/ 2023年10月06日 20:49/ 0 赞/ 23 阅读

相关除数博弈(dp)

题意：爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：选出任一 x，满足 0

水深无声/ 2022年12月07日 12:21/ 0 赞/ 145 阅读