牛客多校第二场

程序员文章站 2022-05-14 08:12:16

...

A:暴力打表找规律

概率问题总是会遇到状态的概率相互依赖的,如:dp[i]=Kj * dp[j]+balabala dp[j]= Ki *dp[i]+balabala

暴力都不好暴力怎么打表?

这次问了蓝心老师这种问题怎么搞，原来说是可以撒点.

撒点？好像有道理，这好像是一种打表找概率的一个不错的方法。特别是在随机决策的时候

https://ac.nowcoder.com/acm/contest/882/A

题目大意:有N个位置[0,N-1]，0和N-1的位置相连形成一个环，玩家初始在0,访问了0,

每次随机前进一步或后退一步，问当玩家访问完了每一个点的时候，最后在M点的概率

分析: 首先可以的出的结论就是:我不会搞，所以不会搞就只有随机打表。于是可以运用老师说的撒点

随机的方法，在0的位置放一个小人,让他随机地走，走完所有，记录最后的点，然后再放很多次(大概1e6)

，就能打出比较精确的规律了，最后规律是P(N,M)是ans=(N==1?(M==0?1:0):1/(N-1));

B:强大的BM算法

之前以为BM算法有诸多限制，现在发现以前YY的那些限制BM都没有，BM能够处理以下场景:
1.复杂度O(length^2)*log(n),length是给入参数的长度,n是要求的项的下标

2.传入参数可以是整数/分数(取逆元)，<mod的数/>=mod但取模之后的数

3.线性递推

以前以为BM算法不能处理给入参数为分数的情况，这次打脸了

/////////////////////////////////////////Info/////////////////////////////////////////////////
//Problem:
//Date:
//Skill:
//Bug:
/////////////////////////////////////////Definations/////////////////////////////////////////////////
//循环控制
#define CLR(a) memset((a),0,sizeof(a))
#define F0(i, a, n) for (ll i=(a);i<(n);++i)
#define F(i,a,b) for(ll i=(a);i<=ll(b);++i)
#define FN(i,a,b) for(ll i=(a);i>=ll(b);--i)
//简化敲击
#define PII pair<int,int>
#define PDD pair<double,double>
//#define PLL pair<long long ,long long>
#define PB push_back
#define MODY(n) (n%=mod)<0?n+=mod:n
#define MODED(n) ((n)<0?(n)%mod+mod:(n)%mod)
#define x first
#define y second
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
////////////////////////////////////////Options//////////////////////////////////////////////////////
#define stdcpph
#ifdef stdcpph
#include<bits/stdc++.h>
#else
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#include<iostream>
#include<iomanip>
#include<string>
#include<stdio.h>
#endif
////////////////////////////////////////Basic Functions//////////////////////////////////////////////
template<typename INint> inline void IN(INint &x)
{
	x = 0; int f = 1; char c; cin.get(c);
	while (c<'0' || c>'9') { if (c == '-')f = -1; cin.get(c); }
	while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; cin.get(c); }
	x *= f;
}
template<typename INint> inline void OUT(INint x)
{
	if (x > 9)OUT(x / 10); cout.put(x % 10 + '0');
}
////////////////////////////////////////Added Functions//////////////////////////////////////////////
const int maxn = int(1100);
#define F0(i, a, n) for (ll i=(a);i<(n);++i)
#define FN(i,a,b) for(ll i=(a);i>=ll(b);--i)
#define SZ(x) ((ll)(x).size())
typedef vector<ll>VLL;
typedef pair<ll, ll> PLL;
const ll mod = 1e9 + 7;
ll qpow(ll a, ll b)
{
	ll res = 1; a %= mod; assert(b >= 0); 
	for (; b; b >>= 1)
	{
		if (b & 1)res = res * a%mod; a = a * a%mod;
	}
	return res;
}
namespace linear_seq
{
	const ll N = 10010;
	ll s_res[N], s_base[N], s_c[N], s_md[N];
	VLL s_md2;
	void mul(ll *a, ll *b, ll k)
	{
		F0(i, 0, k + k)s_c[i] = 0;
		F0(i, 0, k)if (a[i])
			F0(j, 0, k)
			s_c[i + j] = (s_c[i + j] + a[i] * b[j]) % mod;
		FN(i, k + k - 1, k)if (s_c[i])
			F0(j, 0, SZ(s_md2))
			s_c[i - k + s_md2[j]] = (s_c[i - k + s_md2[j]] - s_c[i] * s_md[s_md2[j]]) % mod;
		F0(i, 0, k)a[i] = s_c[i];
	}
	ll solve(ll n, const VLL& a,const VLL&b)
	{
		ll ans = 0, pnt = 0, k = SZ(a);
		assert(SZ(a) == SZ(b));
		F0(i, 0, k)s_md[k - 1 - i] = -a[i]; s_md[k] = 1;
		s_md2.clear(); F0(i, 0, k)if (s_md[i])s_md2.PB(i);
		F0(i, 0, k)s_res[i] = s_base[i] = 0; s_res[0] = 1;
		while ((1ll << pnt) <= n)++pnt;
		FN(p, pnt, 0)
		{
			mul(s_res, s_res, k);
			if ((n >> p) & 1)
			{
				FN(i, k - 1, 0)s_res[i + 1] = s_res[i]; s_res[0] = 0;
				F0(j, 0, SZ(s_md2))s_res[s_md2[j]] = (s_res[s_md2[j]] - s_res[k] * s_md[s_md2[j]]) % mod;
			}
		}
		F0(i, 0, k)ans = (ans + s_res[i] * b[i]) % mod;
		if (ans < 0)ans += mod;
		return ans;
	}
	VLL BM(const VLL&s)
	{
		VLL B(1,1),C(1, 1);
		ll L = 0, m = 1, b = 1;
		F0(n, 0, SZ(s))
		{
			ll d = 0;
			F0(i, 0, L + 1)d = (d + (ll)C[i] * s[n - i]) % mod;
			if (d == 0)++m;
			else if (2 * L <= n)
			{
				VLL T = C;
				ll c = mod - d * qpow(b, mod - 2) % mod;
				while (SZ(C) < SZ(B) + m)C.PB(0);
				F0(i, 0, SZ(B))C[i + m] = (C[i + m] + c * B[i]) % mod;
				L = n + 1 - L; B = T; b = d; m = 1;
			}
			else
			{
				ll c = mod - d * qpow(b, mod - 2) % mod;
				while (SZ(C) < SZ(B) + m)C.PB(0);
				F0(i, 0, SZ(B))C[i + m] = (C[i + m] + c * B[i]) % mod;
				++m;
			}
		}
		return C;
	}
	ll gao(const VLL& a, ll n)
	{
		VLL c = BM(a);
		c.erase(c.begin());
		F0(i, 0, SZ(c)) c[i] = (mod - c[i]) % mod;
		return solve(n, c, VLL(a.begin(), a.begin() + SZ(c)));
	}
	VLL ori_a, tmp_c;
	void init(const VLL& a)
	{
		tmp_c = BM(a);
		tmp_c.erase(tmp_c.begin());
		F0(i, 0, SZ(tmp_c)) tmp_c[i] = (mod - tmp_c[i]) % mod;
		ori_a = a;
	}
	ll prin(ll n)
	{
		return solve(n, tmp_c, VLL(ori_a.begin(), ori_a.begin() + SZ(tmp_c)));
	}
};



ll n, k;
vector<ll>dp;
//ll dp[maxn];
//vector<ll>v;
int id(0);
////////////////////////////////////////////Code/////////////////////////////////////////////////////
int main()
{
	//freopen("C:\\Users\\VULCAN\\Desktop\\data.in", "r", stdin);
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T(1), cas(0);
	cin >> T;
	/////////////////////////////////////////////////////////////////////////////////////////////////
	while (cas, T--)
	{
		//v.clear();
		cin >> k >> n;
		if (n == -1)
		{
			//if (k & 1)cout << qpow((k + 1) / 2, mod - 2) << endl;
			cout << 2 * qpow(k + 1, mod - 2) % mod << endl;
			continue;
		}
		ll inv_k = qpow(k, mod - 2);
		int id = k+k/2+10;
		dp.resize(id+1); dp[0] = 1;
		F(i, 1, id)
		{
			dp[i] = 0;
			F(step, 1, k)
			{
				int from = i - step;
				if (from >= 0)
				{
					dp[i] = (dp[i] + dp[from] * inv_k) % mod;
				}
			}
			//v.PB(dp[i]);
		}
		cout << linear_seq::gao(dp, n) << endl;
	}
	///////////////////////////////////////////////////////////////////////////////////////////////////
	return 0;
}
//What to Debug
/*
-1.最好把全部warning都X掉,否则:https://vjudge.net/solution/19887176
0.看看自己是否有可能需要快读，禁endl
1.数组越界，爆int,浮点精度(查看精度是否达到题目要求,看有没有浮点数比较:eps)，取模操作，初始化数组，边缘数据,输出格式(cas)
2.通读代码，代码无逻辑错误
3.读题，找到题意理解失误或算法错误
4.放弃
*/

D:暴力BFS+优化(优先队列或剪枝)

大意:给你100个点，最多1e4个边,每个点有点权,给定k值[1,1e6]

问图的k小权值团是多少?

分析:赛场上看到这道题的时候，我的内心是拒绝的。因为我不会团，我只抄过一个最大团的板子，

还不理解最大团的算法。所以看到这道题我就觉得我肯定不会做

赛后补题:题解说因为 K<=1e6,所以可以状压BFS搜索.........................

好了，虽然是可以直接暴力BFS，但这种搜索还是很有艺术感的

1.表示新加入结点和当前团中的所有结点相接

if(now.status==(adj[i]&now.status))

now.status是状压后的状态,表示每个节点是不是在团中

adj[i]是与i相接的所有点状压之后的状态，表示的是与i相接的所有点

直接用&和==就判定了要加入的点是不是跟目前所有点相接,优雅!

2.不重复又全面地搜索到所有的团

写过DFS可以知道，用DFS可以记录pos和pos位置的点的id,就可以枚举到所有的团。

BFS的话，就要稍微麻烦一点了，因为BFS光记录status是不够的,因为你不知道自己已经枚举了哪些结点

自己虽然能知道为1的位肯定时在团里，但是不知道为0的位到底是没有枚举还是枚举了确定不在团里

所以要用到下图这样的结构体:

牛客多校第二场

这里的status记录的是点是否在里面的状态，id是枚举到的最后的一个节点

BFS搜的时候是这样的，先枚举所有的单节点，单节点构成一个团,记住要用id记录枚举到的每一个结点，这样

这样每次就枚举id后面的结点，这样由每个单节点不同的团由于第一个结点不同，经过的状态也肯定不同。

在由同一个单节点枚举到的状态中，由于每次枚举的类型和id不同，也是不同的(模拟DFS传参)

完美！

3.优化(剪枝+BFS)

直接这样暴力搜的话，是会T的，要考虑剪枝或优化。

教训：是时候每次写搜索的时候都要考虑一下剪枝或者优化了

剪枝：太过五花八门了，只要根据题目的具体情况，随机应变就好

优化：BFS中可以使用优先队列，DFS中可以根据不同边的接近答案的程度，先搜索优先级高的，或者先尽快找出一个可行解，

再用这个可行解剪掉比这个可行解不优的分支。

本题:BFS可以用优先队列先搜索团的权值更小的，或者剪掉团里面点的个数超过20个的(子集都有1e6了)

/////////////////////////////////////////Info/////////////////////////////////////////////////
//Problem:
//Date:
//Skill:
//Bug:
/////////////////////////////////////////Definations/////////////////////////////////////////////////
//Ñ»·¿ØÖÆ
#define CLR(a) memset((a),0,sizeof(a))
#define F0(i, a, n) for (ll i = (a); i < (n); i++)
#define F(i,a,b) for(ll i=(a);i<=ll(b);++i)
#define FN(i,a,b) for(ll i=(a);i>=ll(b);--i)
//¼ò»¯ÇÃ»÷
#define PII pair<int,int>
#define PDD pair<double,double>
#define PLL pair<long long ,long long>
#define PB push_back
#define MODY(n) (n%=mod)<0?n+=mod:n
#define MODED(n) ((n)<0?(n)%mod+mod:(n)%mod)
#define x first
#define y second
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
////////////////////////////////////////Options//////////////////////////////////////////////////////
#define stdcpph
#ifdef stdcpph
#include<bits/stdc++.h>
#else
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#include<iostream>
#include<iomanip>
#include<string>
#include<stdio.h>
#include<queue>
#endif
////////////////////////////////////////Basic Functions//////////////////////////////////////////////
template<typename INint> inline void IN(INint &x)
{
	x = 0; int f = 1; char c; cin.get(c);
	while (c<'0' || c>'9') { if (c == '-')f = -1; cin.get(c); }
	while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; cin.get(c); }
	x *= f;
}
template<typename INint> inline void OUT(INint x)
{
	if (x > 9)OUT(x / 10); cout.put(x % 10 + '0');
}
////////////////////////////////////////Added Functions//////////////////////////////////////////////
const int maxn = int(110);
ll val[maxn];
__int128 adj[maxn];
int n,k;
struct node
{
	int id;
	__int128 status;
	ll sum;
	bool operator<(const node&ri)const
	{
		if(sum!=ri.sum)return sum>ri.sum;
		else if(status!=ri.status)return status>ri.status;
		else return id>ri.id;
	}
};
int cnt(0);
////////////////////////////////////////////Code/////////////////////////////////////////////////////
int main()
{
//	freopen("C:\\Users\\VULCAN\\Desktop\\data.in", "r", stdin);
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T(1), cas(0);
	//cin >> T;
	/////////////////////////////////////////////////////////////////////////////////////////////////
	while (cas, T--)
	{
		cin>>n>>k;
		F0(i,0,n)cin>>val[i];
		F0(i,0,n)
		{
			__int128 a(0);
			F0(j,0,n)
			{
				char c;cin>>c;
				c-='0';
				if(c)
					a|=(__int128(1)<<j);
			}
//			cout<<(ll)a<<endl;
			adj[i]=a;
		}
		--k;
		if(k==0)
		{
			cout<<0<<endl;
			continue;
		}
		priority_queue<node>Q;
		F0(i,0,n)
		{
			node st={(int)i,__int128(1)<<i,val[i]};
			Q.push(st);
		}
		node ans={-1,-1,-1};
		while(Q.size())
		{
			auto now=Q.top();Q.pop();
//			cout<<"->"<<now.id<<' '<<ll(now.status)<<' '<<now.sum<<endl;
			if(++cnt==k){ans=now;break;}
			F0(i,now.id+1,n)
			{
				if(now.status==(adj[i]&now.status))
				{
					auto cop=now;
					cop.id=i;
					cop.status|=(__int128(1)<<i);
					cop.sum+=val[i];
					Q.push(cop);
//					if(cop.id==0&&cop.status==7)
//						cout<<"found:   "<<"->"<<now.id<<' '<<ll(now.status)<<' '<<now.sum<<endl;
//					cout<<cop.id<<' '<<(ll)cop.status<<' '<<cop.sum<<"->"<<endl;
//					Q.push({now.id,now.status|(__int128(1)<<i),now.sum+val[i]});
//					cout<<now.id << " " << ll(now.status|(__int128(1)<<111i))<<' '<<(now.sum+val[i])<<"->"<<endl;
				}
			}
		}
//		cout<<(ll)ans.status<<endl;
		cout<<ans.sum<<endl;
		
	}
	///////////////////////////////////////////////////////////////////////////////////////////////////
	return 0;
}
//What to Debug
/*
-1.×îºÃ°ÑÈ«²¿warning¶¼Xµô,·ñÔò:https://vjudge.net/solution/19887176
0.¿´¿´×Ô¼ºÊÇ·ñÓÐ¿ÉÄÜÐèÒª¿ì¶Á£¬½ûendl
1.Êý×éÔ½½ç£¬±¬int,¸¡µã¾«¶È(²é¿´¾«¶ÈÊÇ·ñ´ïµ½ÌâÄ¿ÒªÇó,¿´ÓÐÃ»ÓÐ¸¡µãÊý±È½Ï:eps)£¬È¡Ä£²Ù×÷£¬³õÊ¼»¯Êý×é£¬±ßÔµÊý¾Ý,Êä³ö¸ñÊ½(cas)
2.Í¨¶Á´úÂë£¬´úÂëÎÞÂß¼´íÎó
3.¶ÁÌâ£¬ÕÒµ½ÌâÒâÀí½âÊ§Îó»òËã·¨´íÎó
4.·ÅÆú
*/

E:线段树+矩阵乘法

线段树是个神奇的东西:如果涉及到区间信息的合并，务必要想到线段树

目前已知的区间信息的合并:区间最值，区间和，区间带权和，区间线性基，区间矩阵乘，区间积？

题目中的数据大小很有趣,n∈[1,1e5],m属于[1,10]

说明算法的复杂度随n的递增级别是很低的(至多logn)，而随m的递增级别是比较高的，根据题目的数据范围判断最大为m^3

最后，，，题解的复杂度就是O(logn*m^3)，将矩阵保存迷宫垂直区间内的所有列方案数递推关系。。。。

/////////////////////////////////////////Info/////////////////////////////////////////////////
//Problem:
//Date:
//Skill:
//Bug:
/////////////////////////////////////////Definations/////////////////////////////////////////////////
//循环控制
#define CLR(a) memset((a),0,sizeof(a))
#define F0(i, a, n) for (ll i = (a); i < (n); i++)
#define F(i,a,b) for(ll i=(a);i<=ll(b);++i)
#define FN(i,a,b) for(ll i=(a);i>=ll(b);--i)
//简化敲击
#define PII pair<int,int>
#define PDD pair<double,double>
#define PLL pair<long long ,long long>
#define PB push_back
#define MODY(n) (n%=mod)<0?n+=mod:n
#define MODED(n) ((n)<0?(n)%mod+mod:(n)%mod)
#define x first
#define y second
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
////////////////////////////////////////Options//////////////////////////////////////////////////////
#define stdcpph
#ifdef stdcpph
#include<bits/stdc++.h>
#else
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#include<iostream>
#include<iomanip>
#include<string>
#include<stdio.h>
#endif
////////////////////////////////////////Basic Functions//////////////////////////////////////////////
template<typename INint> inline void IN(INint &x)
{
	x = 0; int f = 1; char c; cin.get(c);
	while (c<'0' || c>'9') { if (c == '-')f = -1; cin.get(c); }
	while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; cin.get(c); }
	x *= f;
}
template<typename INint> inline void OUT(INint x)
{
	if (x > 9)OUT(x / 10); cout.put(x % 10 + '0');
}
////////////////////////////////////////Added Functions//////////////////////////////////////////////
const int maxn = int(5e4+8);
const int maxm = 13;
typedef long long ll;
const ll mod = 1e9 + 7;
//6_2-线段树
//线段树模板，例子是区间求和+权值求和+最值
typedef vector<ll>VLL;
typedef vector<VLL>mat;
void mul(ll &a, const ll b)
{
	a *= b; if (a > mod)a %= mod;
}
mat mul(const mat &a, const mat &b)
{
	mat c(a.size(), VLL(b[0].size(), 0));
	for (int k = 0; k < a[0].size(); ++k)
		for (int i = 0; i < c.size(); ++i)
			if (a[i][k])
				for (int j = 0; j < c[0].size(); ++j)
					if (b[k][j])
						c[i][j] += a[i][k] * b[k][j],
						mul(c[i][j], 1ll);
	return c;
}

int N, M, Q;
bool val[maxn][maxm];
#define ls (o<<1)
#define rs (o<<1|1)
#define ndp o,ndl,ndr
#define ndmid ((ndl+ndr)>>1)
#define lsp ls,ndl,ndmid
#define rsp rs,(ndmid+1),ndr
#define ndpf ll o,ll ndl,ll ndr
struct node
{
	mat ma;
};
struct set_T
{
	node es[maxn << 2];
	ll def = 0;//TODO
	int rangeOp = 1;//树中存在
	node comb(const node&le, const node&ri)//TODO
	{
		return{ mul(le.ma,ri.ma) };
	}
	void PushUp(ll o) { es[o] = comb(es[ls], es[rs]); }
	void change(ll v,int p2, ndpf, int mode)//TODO：自定义操作类型
	{
		mat&it = es[o].ma;
		if (val[ndl][p2] == 1)
		{
			F0(i, 0, M)F0(j, 0, M)if (i == p2 || j == p2 || (i < p2 != j < p2))
				it[i][j] = 0;
			val[ndl][p2] = 0;
		}
		else
		{
			int le(p2), ri(p2);
			while (le != 0 && val[ndl][le - 1] == 1)--le;
			while (ri < M&&val[ndl][ri + 1] == 1)++ri;
			F(i, le, ri)F(j, le, ri)it[i][j] = 1;
			val[ndl][p2] = 1;
		}
	}
	void build(ll o, ll ndl, ll ndr)//TODO：自定义初始化数据
	{
		es[o].ma.resize(M, VLL(M, 0));
		if (ndl == ndr) 
		{
			int len = 0;
			F0(i, 0, M)
			{
				if (val[ndl][i])
				{
					++len;
				}
				else
				{
					if (len) 
					{
						int las = i - len;
						F(j, las, i-1)F(k, las, i-1)es[o].ma[j][k] = 1;
						len = 0;
					}
				}
			}
			if (len)
			{
				int las = M - len;
				F(j,las,M-1)F(k,las,M-1)es[o].ma[j][k] = 1;
			}
			return;
		}
		build(lsp); build(rsp);
		PushUp(o);
	}
	void prin(ndpf)//TODO：自定义打印信息
	{
		return;
		cout << o << ":[" << ndl << "," << ndr << "]:";
		cout << endl;
		F0(i, 0, M)
		{
			F0(j, 0, M)
				cout << es[o].ma[i][j] << ' ';
			cout << endl;
		}
		cout << endl;
		//cout << es[o].cnt << endl;
		if (ndl == ndr)return;
		prin(lsp); prin(rsp);
	}
	///////////////////////////////////////////////////////////////////////////////////////

	//TODO：当有两种以上更新操作时，要自定义pushdown顺序，要非常精心地自定义pushdown的顺序与多个lazy标签的融合方法，不然多种lazy标签会混乱发生错误。
	void update(ll p, ll v, int p2, ndpf, int mode)
	{
		if (ndl == ndr) { change(v,p2, ndp, mode); return; }
		if (p <= ndmid)update(p, v,p2, lsp, mode);
		else update(p, v,p2 ,rsp, mode);
		PushUp(o);
	}
}seg;

////////////////////////////////////////////Code/////////////////////////////////////////////////////
int main()
{
	//freopen("C:\\Users\\VULCAN\\Desktop\\data.in", "r", stdin);
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T(1), cas(0);
	//cin >> T;
	/////////////////////////////////////////////////////////////////////////////////////////////////
	while (cas, T--)
	{
		cin >> N >> M >> Q;
		F(i, 1, N)F0(j, 0, M) { char c; cin >> c; val[i][j] = 1-(c - '0'); }
		seg.build(1, 1, N);
		seg.prin(1, 1, N);

		F(i, 1, Q)
		{
			int tp; cin >> tp;
			int a, b; cin >> a >> b;//从[0,a]出去 ->   [N,b]出去
			if (tp == 1)
			{
				seg.update(a, 0, b - 1, 1, 1, N, 1);
				seg.prin(1, 1, N);
			}
			else
			{
				ll ans = seg.es[1].ma[a-1][b-1];
				cout << ans << '\n';
				//cout << ans << endl;
			}
		}
	}
	///////////////////////////////////////////////////////////////////////////////////////////////////
	return 0;
}
//What to Debug
/*
-1.最好把全部warning都X掉,否则:https://vjudge.net/solution/19887176
0.看看自己是否有可能需要快读，禁endl
1.数组越界，爆int,浮点精度(查看精度是否达到题目要求,看有没有浮点数比较:eps)，取模操作，初始化数组，边缘数据,输出格式(cas)
2.通读代码，代码无逻辑错误
3.读题，找到题意理解失误或算法错误
4.放弃
*/

F:暴力DFS+剪枝

我真是个鲨????，搜索和剪枝是固定搭配不知道吗，这题由于2N个人每个人对其余2N-1个人的配对权值都不同，所以想使用网络

流或者其他高级算法是不可能的。

唯一的办法就是暴力搜索。

然而暴力搜索的复杂度大概是O(C(28,14)*14*14)这。。。。。。有点尴尬，恰好比题目要求的复杂度高了一点点。

所以就要用到剪枝的做法了。

我觉得剪枝有这样几种:

1.探索到的状态不合法(return)

2.探索到的状态已经探索过了(记忆化)

3.探索到的状态虽然暂时合法，但是它的后继节点里面没有任何合法结点(后继肯定会不合法)(return)

4.到了终点(return)

5.探索到现在，观望未来(使用对当前节点后继节点的乐观估计函数)，发现继续走下去得到的答案肯定比之前走过的某一条路得到的答案不优。(return)

这题就可以用到第5种剪枝(貌似叫IDEA,还是A*?)

J:很难，不想补博客呜呜呜

上一篇： PHP/JS远程删除cookie

下一篇：在ubuntu中如何重置mysql服务器的root密码_MySQL

牛客多校第二场

2019牛客暑期多校训练营（第二场）H Second Large Rectangle

2020牛客暑期多校训练营（第四场）——Basic Gcd Problem

2020牛客暑期多校训练营(第五场)

HDU6312 Game (多校第二场1004) 简单博弈

牛客多校第三场 A-Clam and Fish【贪心】+ B-Classical String Problem【思维】

2020牛客暑期多校训练营（第九场） The Flee Plan of Groundhog

2020牛客暑期多校训练营Groundhog and Apple Tree(树形dp，贪心)

2020暑期牛客多校训练营第九场（K）The Flee Plan of Groundhog（lca，树形dp）

2020牛客多校第三场-J Just Shuffle

【杭电多校2020】第二场1001.Total Eclipse（并查集）