Codeforces Round #739 (Div. 3)A~F2

本文主要是介绍Codeforces Round #739 (Div. 3)A~F2，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

A. Dislike of Threes

题意：给出一组从1开始的数，要求不包括3的倍数或个位是3的数，给出n，输出第n个数
数据范围n <= 1000
分析：暴力

代码：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

#define x first
#define y second

using namespace std;

typedef long long ll; 
typedef pair<int, int> PII;

const int N = 1e5 + 10, mod = 1e9 + 7;

int n, m, t, k;

int s[N], g[N], dp[N];

vector<int> vec;

void solve()
{
	int i = 0;
	while (vec.size() < 1010)
	{
		i++;
		if (i % 10 != 3) vec.push_back(i);
		i++;
		if (i % 10 != 3) vec.push_back(i);
		i++;
	}
	cin >> n;
	while (n--)
	{
		int a;
		cin >> a;
		cout << vec[a - 1] <<endl;
	}
}

int main()
{
    t = 1;
//    cin >> t;
    while(t--) 
        solve();
    return 0;
}

B. Who's Opposite?

题意：对于一个长度为2n的序列，按1到2n围成圈，x<n时，x与x+n相对，询问给出a，b，c，假如a与b相对，问与c相对的是多少，不合法输出-1

分析：对于给出的a，b显然差值为总数的一半，可以算出总数为多少，合法性可以探究a，b，c的位置，显然a，b中值大的须在后一半，值小的须在前一半，c需要在总数内部，非法输出-1，合法根据c的位置加或减总数一半即可

代码：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

#define x first
#define y second

using namespace std;

typedef long long ll; 
typedef pair<int, int> PII;

const int N = 1e5 + 10, mod = 1e9 + 7;

int n, m, t, k;

int s[N], g[N], dp[N];

void solve()
{
	int a, b, c, d, e, d1;
	cin >> a >> b >> c;
	if (a < b) swap(a, b);
	e = (a - b) * 2;
	if (a <= e / 2 || a > e)
	{
		puts("-1");
		return;
	}
	if (b > e / 2)
	{
		puts("-1");
		return;
	}
	if (c > e)
	{
		puts("-1");
		return;
	}
	d = (c + e / 2 - 1) % e + 1;
	printf("%d\n", d);
}

int main()
{
    t = 1;
    cin >> t;
    while(t--) 
        solve();
    return 0;
}

C. Infinity Table

题意：将所有数从1开始的正整数排列，排列方式为从（1，i）依次往下放，直到(i,i)再往左依次放置，直到（i，1），i++，循环

分析：对于（i,1），都是\(i^{2}\),就可以直接找到小于目标数的根号的行列数，然后倒回去即可，且因为放置规律，可以直接算出来，令\(m^{2}\)为n以下最大的平方数，如果n-\(m^{2}\)<m+1,位置就是{n-\(m^{2}\)，m+1}, 否则位置是{m+1,\(m^{2}\)-2m-n}。

代码：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

#define x first
#define y second

using namespace std;

typedef long long ll; 
typedef pair<int, int> PII;

const int N = 1e5 + 10, mod = 1e9 + 7;

int n, m, t, k;

int s[N], g[N], dp[N];

void solve()
{
	cin >> n;
	m = sqrt(n);
	if (m * m == n)
	{
		printf("%d %d\n", m, 1);
		return;
	}
	k = n - m * m;
	if (k <= m + 1) printf("%d %d\n", k, m + 1);
	else printf("%d %d\n", m + 1, (m + 1) * (m + 1) - n + 1);
}

int main()
{
    t = 1;
    cin >> t;
    while(t--) 
        solve();
    return 0;
}

D. Make a Power of Two

题意：对于给出的数（n<1e9），有两种操作 1:删除十进制中某一位，2：在末尾任意加一位，使得最终数字为2的幂次方，且不允许包含前导零，问操作数最少数值
分析：显然操作数最多为10,所有数都删除，最后加1，初步分析可知数据量很小，考虑暴力，对于2的幂次方，int范围内32个，long long范围内64个，考虑到操作有加有减，我们暴力处理64个数据，对于每个数据都与n进行匹配，找出至少需要删除多少元素，添加多少元素可以变成这一类的2得幂次方，所有情况答案取最小即可

代码：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

#define x first
#define y second

using namespace std;

typedef long long ll; 
typedef pair<int, int> PII;

const int N = 1e5 + 10, mod = 1e9 + 7;
const ll INF = 1e18;

int n, m, t, k;

int s[N], g[N], dp[N];

vector<ll> vec, vec1, vec2;

int check(int a, ll b)
{
	int a1 = a;
	ll b1 = b;
	int cnt = 0;
	vec1.clear();
	vec2.clear();
	while (a)
	{
		vec2.push_back(a % 10);
		a /= 10;
	}
	while (b)
	{
		vec1.push_back(b % 10);
		b /= 10;
	}
	reverse(vec2.begin(), vec2.end());
	reverse(vec1.begin(), vec1.end());
	cnt = vec2.size();
	int i, j;
	for (i = 0, j = 0; i < vec1.size() && j < vec2.size(); j++)
		if (vec1[i] == vec2[j])
			i++, cnt--;
	if (i == vec1.size()) return cnt;
	return cnt + vec1.size() - i;
}

void solve()
{
	ll cnt = 1;
	while (cnt * 2 < INF) vec.push_back(cnt), cnt *= 2;
	cin >> n;
	while (n--)
	{
		cin >> k;
		int ans = 30;
		for (int i = 0; i < vec.size(); i++)
		{
			ans = min(ans, check(k, vec[i]));
		}
		cout << ans << endl;
	}
}

int main()
{
    t = 1;
//    cin >> t;
    while(t--) 
        solve();
    return 0;
}

E. Polycarp and String Transformation

题意：对于一个初始字符串s和一个空字符串t，我们以此对s进行如下操作 1.将s添加到t之后 2.选择s中的一类字母，从s中去除，上述操作执行到s为空，给出t数组，问原s数组，以及删除字母顺序，如果给出的t不可能存在s，输出-1

分析：根据删除情况，显然之前删除过得后续不会出现，那么倒着找最新出现的元素就是删除的元素，这里知道了如果存在s，s的字母删除顺序，假设字母类型数为n，那么第i个删除的意味着t中s的该元素进行了i轮，如果t中该元素数量不能整除i那么不会合法，否则你可以得到一个当前的原数组s，按照删除顺序走一遍，看看会不会变成t，如果不是t，那么依然不合法，合法就输出答案即可

代码：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

#define x first
#define y second

using namespace std;

typedef long long ll; 
typedef pair<int, int> PII;

const int N = 1e5 + 10, mod = 1e9 + 7;

int n, m, t, k;

int s[N], g[N], dp[N];

void solve()
{
	string a;
	string b;
	string c;
	string d;
	cin >> a;
	for (int i = 0; i < 26; i++) g[i] = 0;
	for (int i = a.size() - 1; i >= 0; i--)
	{
		if (g[a[i] - 'a'] == 0) b += a[i];
		g[a[i] - 'a']++;
	}
	reverse(b.begin(), b.end());
	int ans = 0;
	for (int i = 0; i < b.size(); i++)
		if (g[b[i] - 'a'] % (i + 1))
		{
			puts("-1");
			return;
		}
		else ans += g[b[i] - 'a'] / (i + 1);
	for (int i = 0; i < ans; i++)
		c += a[i], d += a[i];
	for (int i = 0; i < b.size(); i++)
	{
		g[b[i] - 'a'] = 0;
		for (int j = 0; j < c.size(); j++)
			if (g[c[j] - 'a'])
				d += c[j];
	}
	if (a != d)
	{
		puts("-1");
		return;
	}
	cout << c << ' ' << b << endl;
}

int main()
{
    t = 1;
    cin >> t;
    while(t--) 
        solve();
    return 0;
}

F. Nearest Beautiful Number

题意：f1与f2区别不大，f1中k<2,f2中k<11,这里直接讲f2，给出n和k，问大于等于n的，数字不同的种类数不超过k的数最小是多少。

分析：对于要求的数最小，那么高位的数要尽可能不变，所以对于给定的数从高位到低位去以此判断，如果当前数字被用过就直接跳过，如果没被用过那就看看当前种类数够不够，不够的话，就把这个数填进去，如果种类数也用够了，那就看看能不找到比这个数大的用过的数，找到的话当前就直接改这个数，后续的数填任意数都可用保证符合答案，考虑到种类数，填选过的最小值填满就好，不然那就要去改变前一位的状态，如果前一位是唯一新数，那么就可以直接+1，保证大后，判断当前有没有种类数，如果刚刚那位+1后的值是用过的数，那么就有一个种类数，定为0，后续补满0即可，如果不是，那后续就补满已经选过的数的最小值，如果不是唯一新数，就看有没有选过的数比这个数大的，有的话就跟刚刚一样，没有的话，可以再往回找即可。

代码：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

#define x first
#define y second

using namespace std;

typedef long long ll; 
typedef pair<int, int> PII;

const int N = 1e5 + 10, mod = 1e9 + 7;

int n, m, t, k;

int s[N], g[N], dp[N];

vector<int> vec, vec1;

void solve()
{
	for (int i = 0; i < 10; i++) g[i] = 0;
	vec.clear(), vec1.clear();
	cin >> n >> k;
	int minn = 10;
	while (n) vec.push_back(n % 10), n /= 10;
	reverse(vec.begin(), vec.end());
	k--;
	g[vec[0]] = 1;
	minn = vec[0];
	vec1.push_back(vec[0]);
	for (int i = 1; i < vec.size(); i++)
	{
		if (g[vec[i]])
		{
			vec1.push_back(vec[i]);
			continue;
		}
		else if (k)
		{
			k--;
			g[vec[i]] = i + 1;
			minn = min(vec[i], minn);
			vec1.push_back(vec[i]);
		}
		else
		{
			for (int j = vec[i] + 1; j <= 9; j++)
			{
				if (g[j])
				{
					vec1.push_back(j);
					for (int k = i + 1; k < vec.size(); k++)
						vec1.push_back(minn);
					for (int k = 0; k < vec1.size(); k++)
						printf("%d", vec1[k]);
					puts("");
					return;
				}
			}
			while (g[vec1[vec1.size() - 1]] != vec1.size())
			{
				
				for (int j = vec1[vec1.size() - 1] + 1; j <= 9; j++)
				{
					if (g[j])
					{
						vec1.pop_back();
						vec1.push_back(j);
						for (int k = vec1.size(); k < vec.size(); k++)
							vec1.push_back(minn);
						for (int k = 0; k < vec1.size(); k++)
							printf("%d", vec1[k]);
						puts("");
						return;
					}
				}
				vec1.pop_back();
			}
			int a = vec1[vec1.size() - 1];
			vec1[vec1.size() - 1]++;
			if (minn == a) minn++;
			if (g[a + 1]) minn = 0;
			for (int k = vec1.size(); k < vec.size(); k++)
				vec1.push_back(minn);
			for (int k = 0; k < vec1.size(); k++)
				printf("%d", vec1[k]);
			puts("");
			return;
		}
	}
	for (int k = 0; k < vec1.size(); k++)
		printf("%d", vec1[k]);
	puts("");
}

int main()
{
    t = 1;
    cin >> t;
    while(t--) 
        solve();
    return 0;
}

这篇关于Codeforces Round #739 (Div. 3)A~F2的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！