Atcoder Beginner Contest 271 C-F

C - Manga

题意: 给定一个长度为$n(1 \leq n \leq 3e5)$的序列,每个位置有一个值$x(1 \leq x \leq 1e9)$，我们可以进行任意多次操作，操作的话是如果序列的长度还大于等于$2$，那么我们可以任意选择$2$个数字去删除，然后加进去任意一个数字进去，问我们最后能够得到一个形似$1,2,3…$的最长序列

解题思路: 首先我们分析一下题意，我们可以知道最后的答案最多不会超过$n$，那么我们在读入的时候可以将大于$n$的部分放进一个$vector$里面，然后对于小于$n$的一部分我们可以先给他标记然后放到一个双端队列里面，如果其中的数字有重复的部分我们也需要放进上面的$vector$之中。接着我们模拟这个过程即可。在模拟的时候注意我们优先取$vector$当中的，然后我们取队列后面的即可

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
int vis[maxn],n;
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n;
	vector<int> a;
	for(int i = 1,x;i <= n;++i)
	{
		cin >> x;
		if(x <= n)
		{
			if(vis[x]) a.push_back(x);
			else vis[x] = 1;
		}
		else a.push_back(x);
	}
	deque<int> q;
	for(int i = 1;i <= n;++i)
	{
		if(vis[i]) q.push_back(i);
	}
	int ans = 0;
	for(int i = 1;i <= n;++i)
	{
		if(vis[i] && q.size())
		{
			ans++;
			q.pop_front();
			continue;
		}
		if(a.size() >= 2)
		{
			a.pop_back();
			a.pop_back();
		}
		else if(a.size() == 1)
		{
			a.pop_back();
			if(!q.empty()) q.pop_back(); 
			else break;
		}
		else
		{
			if(q.size() >= 2)
			{
				q.pop_back();
				q.pop_back();
			}
			else break;
		}
		ans++;
	}
	cout << ans << "\n";
	return 0;
}

D - Flip and Adjust

题意: 给定$n(1 \leq n \leq 100)$张卡片，每张卡片背面和正面有一个数字，现在让我们选择每张卡片的正面或者反面，问是否能够组成$s(1\leq s \leq 10000)$

解题思路: 首先我们可以观察数据范围，可能是$O(n ^ 3)$或者$O(ns)$的$dp$

接下来我们考虑这样的一个过程，首先无论如何每张牌都是要取的，那么假定我现在取到第$i - 1$张牌的值有$s_{i - 1}$，那么我取第$i$张牌的时候的值肯定有$s_{i - 1} + mp[i][0]$和$s_{i - 1} + mp[i][1]$$(mp[i][0/1]表示第i张牌的正反面的值)$

那么我们就可以用$dp[i][s]$来表示前$i$张牌可能组成的值

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e2 + 10;
int mp[maxn][2],n,s;
int dp[maxn][40010];
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n >> s;
	dp[0][0] = 1;
	for(int i = 1;i <= n;++i)
	{
		cin >> mp[i][0] >> mp[i][1];
		if(i == 1)
		{
			dp[1][mp[i][0]] = 1;
			dp[1][mp[i][1]] = 1;
			continue;
		}
		for(int j = 0;j <= s;++j)
		{
			if(!dp[i - 1][j]) continue;
			if(j + mp[i][0] <= s) dp[i][j + mp[i][0]] = 1;
			if(j + mp[i][1] <= s) dp[i][j + mp[i][1]] = 1;
		}
	}
	if(dp[n][s])
	{
		cout << "Yes\n";
		string ans = "";
		for(int i = n;i >= 1;--i)
		{
			if(s - mp[i][0] >= 0 && dp[i - 1][s - mp[i][0]])
			{
				s -= mp[i][0];
				ans.push_back('H');
			}
			else
			{
				s -= mp[i][1];
				ans.push_back('T');
			}
		}
		assert(ans.length() == n);
		reverse(ans.begin(),ans.end());
		cout << ans << "\n";
	}
	else
	{
		cout << "No\n";
	}
	return 0;
}

E - Subsequence Path

题目大意: 给定$n$个点$m$条单向边$(1 \leq n,m \leq 2e5)$，没有重边和自环，每个边有一条权值，接下来给定一个序列$E$，我们走的路径的标号形成的序列必须是这个序列$E$的子序列，问从点$1$到点$n$的最短路径

解题思路: 分析题目发现我们的突破口应该在这个给定我们的序列$E$这里，因为考虑我们取到的序列是这个序列的子序列，这里给我们透露到一些信息，就是假设我们当前已经遍历到第$i$条边，那么我们是可以用前面$i - 1$条边来更新这一张图的，那么我们知道这个点之后就可以写啦

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 10;
const int inf = 1e18;
struct node
{
	int u,v,w;
}edge[maxn];
int n,m,k;
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n >> m >> k;
	vector<int> dis(n + 1,inf);
	for(int i = 1,u,v,w;i <= m;++i)
	{
		cin >> u >> v >> w;
		edge[i] = {u,v,w};
	}
	dis[1] = 0;
	for(int i = 1,x;i <= k;++i)
	{
		cin >> x;
		int u = edge[x].u;
		int v = edge[x].v;
		int w = edge[x].w;
		dis[v] = min(dis[v],dis[u] + w);
	}
	if(dis[n] != inf) cout << dis[n] << "\n";
	else cout << -1 << "\n";
	return 0;
}

F - XOR on Grid Path

题目大意: 给定一个$n * n(1\leq n \leq 20)$的矩阵，我们从点$(1,1)$开始，每次移动可以向$(x + 1,y)$或者$(x,y + 1)$移动，问我们到达$(n,n)$使得异或和为$0$的路径有多少条

解题思路: 首先对于这种矩阵的题目我们肯定先去考虑$dp$的，但是如果暴力去枚举所有方案的话方案数实际会非常的大

根据官方题解的思路，建议我们使用$meet$ $in$ $middle$来做

那$meet$ $in$ $middle$是个什么东西呢？大概就是我从两个点来搜索，搜索到一些具有共同性质的点从而结束，因为这样子会大大减少我们所需要的时间复杂度

那么对于矩阵来说，我们可以从$(1,1)$点和$(n,n)$点来搜索，对于这两个点来说我们都搜索到对角线上面的点来结束,因为对角线刚好分割两个矩阵

那么我们对于$(1,1)$点来说，我们可以直接搜索下去到对角线来记录当前异或和的数值，那么对于$(n,n)$点来说，我们可以往上面搜索，搜到对角线的话就加上之前前面遍历到这一点的值，因为我们需要异或和是$0$嘛

#include <bits/stdc++.h>
using namespace std;
#define int long long
int mp[30][30],n;
unordered_map<int,int> dp[30][30];
int ans;
void dfs1(int x,int y,int now)
{
	if(x + y == n)
	{
		dp[x][y][now]++;
		return;
	}
	if(x + y > n) return;
	dfs1(x + 1,y,now ^ mp[x + 1][y]);
	dfs1(x,y + 1,now ^ mp[x][y + 1]);
}
void dfs2(int x,int y,int now)
{
	if(x + y == n)
	{
		ans += dp[x][y][now ^ mp[x][y]];
		return;
	}
	if(x + y < n) return;
	dfs2(x - 1,y,now ^ mp[x - 1][y]);
	dfs2(x,y - 1,now ^ mp[x][y - 1]);
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n;++i)
	{
		for(int j = 1;j <= n;++j) cin >> mp[i][j];
	}
	dfs1(1,1,mp[1][1]);
	dfs2(n,n,mp[n][n]);
	cout << ans << "\n";
	return 0;
}