Codeforces 1310 B Double Elimination —— 记忆化搜索,有丶东西

2024-04-06 23:48

本文主要是介绍Codeforces 1310 B Double Elimination —— 记忆化搜索,有丶东西,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

This way

题意:

现在有 2 n 2^n 2n个队伍,第一次每相邻两个队伍比赛,然后剩下 2 n − 1 2^{n-1} 2n1个胜利者和 2 n − 1 2^{n-1} 2n1个loser,胜利者会进行下一场比赛,同时loser也会进行下一场比赛,然后对于这次胜利者淘汰下来的 2 n − 2 2^{n-2} 2n2个人,加上loser中的 2 n − 2 2^{n-2} 2n2个人,又进行一场比赛,然后循环这个操作,直到最后一个胜利者和最后一个loser,他们会进行一次决斗。
你有一些喜欢的人,给你这些人的编号,你可以任意指定每一个人每一局的输赢使得所有比赛中包含你喜欢的人出场的比赛最多,问你最多是多少。

题解:

我看了有很多解法,但是我一个都想不出来,我选了记忆化搜索来理解,dp[x][l][r]表示在l到r这个区间最终赢的赢和输的赢的状态为x时答案最大是多少。因为败方比赛会有两次,所以可以直接用2表示败方是否有。
那么状态转移就是两个子区间的和,枚举左区间和右区间的情况。

((i&2)|(i<<1)|j)&3

这里我也理解了一会,这种情况是i的胜败了,i&2表示i的败方是否有喜欢的队伍,i<<1表示i的胜方到败方时是否有喜欢的队伍。

#include<bits/stdc++.h>
using namespace std;
const int N=(1<<17)+5;
unordered_map<int,int>mp[4][N];
bool fav[N];
int dfs(int l,int r,int s){//01:赢得赢 10:输的赢if(r==l+1){int num1=fav[l]+fav[r],num2=(s&1)+(s>>1);if(num1==num2)return min(1,num2);elsereturn -1e6;}if(mp[s][l].count(r))return mp[s][l][r];int ans=-1e6,mid=l+r>>1;for(int i=0;i<4;i++){for(int j=0;j<4;j++){int ilose=((i&2)|(i<<1)|j)&3,jlose=((j&2)|(j<<1)|i)&3;if(ilose==s||jlose==s)ans=max(ans,dfs(l,mid,i)+dfs(mid+1,r,j));}}return mp[s][l][r]=ans+s;
}
int main()
{int n,m,x;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d",&x),fav[x]=1;int ans=0;for(int i=0;i<4;i++)ans=max(ans,dfs(1,1<<n,i));printf("%d\n",ans+(m?1:0));//最后赢和输还有一场对决return 0;
}

这篇关于Codeforces 1310 B Double Elimination —— 记忆化搜索,有丶东西的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/881151

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

hdu4277搜索

给你n个有长度的线段,问如果用上所有的线段来拼1个三角形,最多能拼出多少种不同的? import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja