[数据结构与算法]2021 澳门站(热身赛) ABC

题目
热身赛，上来Awa了一发，又读了读题。B想麻烦了，wa了一发，然后队友想到了正解，但是时间来不及了，直接去吃饭了，不然正式赛前赶不回去。
A
题意: 给定1-n，每个数用一次，构造一个数组，使得数组中差为k的位置尽可能地多。
思路: 1,1+k,…2,2+k…
时间复杂度: O(n)
代码:

// Problem: K-skip Permutation
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/31453/A
// Memory Limit: 1048576 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
bool vis[N];
int n,m,k,T;
vector<int> va;
void solve()
{
	cin>>n>>k;
	for(int i=1;i<=n;++i)
	{
		if(vis[i]) break;
		int now = i;
		while(now <= n)
		{
			vis[now] = 1;
			va.push_back(now);
			now += k;
		}
	}
	for(int i=0;i<va.size();++i)
	{
		if(i) cout<<' ';
		cout<<va[i];
	}
}
signed main(void)
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	T = 1;
	// cin>>T;
	while(T--)
	solve();
	return 0;
}

B
题意: 给一个大火锅(现在封校不能出去恰火锅…)。有n个人，每人有喜欢的调料a[i]，如果火锅里有，就拿走，hapyy值+1;否则，往火锅里扔一个a[i]。执行m次，当n号执行完，轮到1号，循环+1。
思路: 如果a[i]出现奇数次，那么它在奇数轮和偶数轮的表现不一样。但是我们可以模拟两次，以两次为基准，这样就一视同仁了。之后看有多少个2轮，剩下的模拟一下即可。
时间复杂度: O(n)
代码:

// Problem: Hotpot
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/31453/B
// Memory Limit: 1048576 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
int n,m,k,T;
int a[N];
int cnt[N];
ll ans[N];
void solve()
{
	cin>>n>>k>>m;
	memset(cnt,0,sizeof(cnt));
	memset(ans,0,sizeof(ans));
	for(int i=1;i<=n;++i)
	{
		cin>>a[i];
		if(cnt[a[i]]) ans[i]++,cnt[a[i]]--;
		else cnt[a[i]]++;
	}
	for(int i=1;i<=n;++i)
	{
		if(cnt[a[i]]) ans[i]++,cnt[a[i]]--;
		else cnt[a[i]]++;
	}
    int tmp = (m-2*n) / (2*n);
    for(int i=1;i<=n;++i)
    {
    	ans[i] *= 1ll*tmp;
    }
    int le = m - tmp * 2 * n;
    // cout<<le<<"?\n";
    for(int i=1;le;le--)
    {
        if(cnt[a[i]]) ans[i]++,cnt[a[i]]--;
        else cnt[a[i]]++;
        i++;
        if(i == n+1) i = 1;
    }
    for(int i=1;i<=n;++i)
    {
    	if(i>1) cout<<' ';
    	cout<<ans[i];
    }
    cout<<"\n";
}
signed main(void)
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--)
	solve();
	return 0;
}

C
题意: 给定一个长度为n的字符串，仅包含L、R、D、U。表示机器人的移动，起始在(0,0).重复这个字符串m次，求机器人距离(0,0)的最大曼哈顿距离。
思路: 求出第一次的结果dx和dy，剩下m-1直接乘dx和dy，最后一次模拟即可。因为终点未必是最优结果。
时间复杂度: O(n)
代码:

// Problem: Wandering Robot
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/31453/C
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
#define int long long 
typedef long long ll;
int n,m,k,T;
void solve()
{
	int mx = -1;
	cin>>n>>m;
	string s; cin>>s;
	int x = 0,y = 0;
	for(int i=0;i<s.size();++i)
	{
			if(s[i]=='L') x--;
			if(s[i]=='R') x++;
			if(s[i]=='U') y++;
			if(s[i]=='D') y--;
			mx = max(mx,abs(x)+abs(y));
	}
	x = (m-1)*x;
	y = (m-1)*y;
	for(int i=0;i<s.size();++i)
	{
		if(s[i]=='L') x--;
		if(s[i]=='R') x++;
		if(s[i]=='U') y++;
		if(s[i]=='D') y--;
		mx = max(mx,abs(x)+abs(y));
	}
	cout<<mx<<"\n";
}
signed main(void)
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	T = 1;
	cin>>T;
	while(T--)
	solve();
	return 0;
}