丽泽普及2022交流赛day19 半社论

No Problem
Str
Not TSP
- 题面
- 题解
- 代码
Game
- 题面
- 题解
- 代码

No Problem

暴力

Str

存在循环节，大力找出来即可，长度显然不超过 \(10^3\) .

Not TSP

题面

TSP 问题，但是游览第 \(u\) 个点要满足下列条件之一

\(1\dots u-1\) 均被游览过 .
\(1\dots u-1\) 均未被游览过 .

题解

肯定是先往左跳然后往右填 .

dp 一下就好了 .

\(dp_{i,j}\) 表示 \(i\) 跳到 \(j\) .

代码

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

template<typename T>

inline int chkmin(T& a, const T& b){if (a > b) a = b; return a;}

template<typename T>

inline int chkmax(T& a, const T& b){if (a < b) a = b; return a;}

const int N = 1555;

const ll INF = 0x3f3f3f3f3f3f3f3fll;

ll n, d[N][N], dp[N][N], s[N], pre[N];

inline ll gg(int l, int r){return max(0ll, s[r-1] - s[l-1]);}

int main()

{

	scanf("%lld", &n);

	for (int i=1; i<=n; i++)

		for (int j=1; j<=n; j++) scanf("%lld", d[i]+j);

	for (int i=1; i<=n; i++) s[i] = s[i-1] + d[i-1][i];

	for (int i=0; i<=n; i++){dp[0][i] = s[i]; d[0][i] = d[1][i];}

	for (int i=2; i<=n; i++)

	{

		for (int j=0; j<i-1; j++) dp[j][i] = dp[j][j+1] + s[i] - s[j+1];

		dp[i-1][i] = INF;

		for (int j=0; j<i-1; j++) chkmin(dp[i-1][i], dp[j][i-1] + d[j][i]);

	}

	ll ans = INF;

	for (int i=1; i<n; i++) chkmin(ans, dp[i][n]);

	printf("%lld\n", ans);

	return 0;

}

Game

题面

Alice 和 Bob 在做游戏 .

平面上有 \(n\) 个点，Alice 先手，每次每个人需要画一条平行于 \(x\) 或 \(y\) 轴的一条直线，穿过前一条直线穿过的某个点 . 不能画与之前直线重合的直线 . 不能操作的人输 .

问谁必胜 .

题解

如果有一个点 \(x,y\)，就连一条边 \(x\to y\)，这相当于是两条直线在转移 .

于是问题就等价于 Alice 和 Bob 在这张图上走，走过的点不能再走 .

然而我们把 \(x,y\) 取出来，会发现这玩意其实是一个二分图 .

这个有一个结论：后手必胜当且仅当图有完备匹配 .

证明：

如果有匹配：Alice 每动一步 Bob 就跑去它的匹配点，这样最后 Alice 就无路可走了 .

若不然：Alice 选一个不在匹配中的点，Bob 会选一个在匹配中的点，这样 Alice 就可以用上面的策略取胜了 .

代码

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

template<typename T>

inline int chkmin(T& a, const T& b){if (a > b) a = b; return a;}

template<typename T>

inline int chkmax(T& a, const T& b){if (a < b) a = b; return a;}

const int N = 1555;

template<typename T>

struct pool

{

	unordered_map<T, unsigned> pol;

	unsigned cc = 0;

	unsigned get(T x)

	{

		auto ptr = pol.find(x);

		if (ptr == pol.end()){pol[x] = ++cc; return cc;}

		else return ptr -> second;

	}

};

pool<int> T;

int n, vis[N], L[N], R[N];

vector<int> g[N];

set<int> vx, vy;

inline void addedge(int u, int v){g[u].emplace_back(v);}

bool dfs(int u, int t)

{

	if (vis[u] == t) return false;

	vis[u] = t;

	for (int v : g[u])

		if (!L[v] || dfs(L[v], t)){L[v] = u; R[u] = v; return true;}

	return false;

}

inline void match(){for (int i=1; i<=n; i++) dfs(i, i);}

int main()

{

	scanf("%d", &n);

	for (int i=1, x, y; i<=n; i++)

	{

		scanf("%d%d", &x, &y);

		x = T.get(x); y = T.get(y);

		vx.insert(x); vy.insert(y);

		addedge(x, y);

	}

	if (vx.size() != vy.size()){puts("Alice"); return 0;}

	match();

	for (int i : vx) if (!R[i]){puts("Alice"); return 0;}

	for (int i : vy) if (!L[i]){puts("Alice"); return 0;}

	puts("Bob");

	return 0;

}

巴特西

丽泽普及2022交流赛day19 半社论

No Problem

Str

Not TSP

题面

题解

代码

Game

题面

题解

代码

最新文章

热门文章