Codeforces Round #743 (Div. 2)

A. Countdown

题意:只能进行两步操作,-1和对任意两个位置交换值,问最少多少步可以变成0,允许前导0的存在

分析:每个有值的位置都与个位进行交换,清0

代码:

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

#define x first
#define y second
#define MAX(a,b,c) max(max(a, b),c)
#define MIN(a,b,c) min(min(a, b),c)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'

using namespace std;

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

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

int n, m, t, k;

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

string str;

vector<int> vec;

void solve()
{
	int ans = 0;
	cin >> n >> str;
	reverse(str.begin(), str.end());
	for (int i = 0; i < n; i++)
	{
		ans += str[i] - '0';
		if (i > 0)
		ans += str[i] != '0';
	}
	cout << ans << endl;
}

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

B. Swaps

题意:只能进行相邻值的交换,第一个数组为1到2n的所有奇数,随机排列,第二个数组是1到2n的所有偶数随机排列询问最少交换多少次,使得第一个数组的值比第二个数组的值小

分析:因为两个数组的任意数均不同,并且无重复的1到2n,所以可以分别对应记录第i个数在原数组中换几次可以到第一个位置,那么可以去这个数组中从大到小一边维护奇数比i大的值最小换几次,一边算偶数取到i-1时,答案为多少,答案取遍历完所有偶数值后的最小值

代码:

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

#define x first
#define y second
#define MAX(a,b,c) max(max(a, b),c)
#define MIN(a,b,c) min(min(a, b),c)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'

using namespace std;

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

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

int n, m, t, k;

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

string str;

vector<int> vec;

void solve()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> k;
		f[k] = i;
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> k;
		f[k] = i;
	}
	dp[2 * n + 2] = mod;
	int res = mod;
	for (int i = 2 * n; i >= 1; i--)
		if (i & 1)
			res = min(res, f[i] - 1 + dp[i+1] - 1);
		else
			dp[i] = min(dp[i+2], f[i]);
	cout << res << endl;
}

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

C. Book

题意:每次读书从头到尾的读,理解某些章节需要理解彻底理解其他前驱章节的内容,问读几次能读懂整本书,或者他永远不会理解某些章节

分析:如果说存在不理解的章节,那必定成环了,这个图建起来是一棵树,因为要从小到大按顺序读,所以存放进优先队列中,存负值,就可以实现了,每一轮以此取出值,当前目录理解后对子节点的章节前置-1,把这一轮解锁的新章节(前置为0)先放入q2,在遍历完q的时候,如果q2有值,就交换优先队列q和q2,进行下一轮的读书,事先记录每一个章节的前置有多少,解锁一次少一个,前置为0代表当前这章彻底理解,以此往复。

代码:

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

#define x first
#define y second
#define MAX(a,b,c) max(max(a, b),c)
#define MIN(a,b,c) min(min(a, b),c)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'

using namespace std;

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

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

int n, m, t, k;

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

string str;

vector<int> vec[N];

void solve()
{
	priority_queue<int> q,q2;
	cin >> n;
	for (int i = 1; i <= n; i++)
		vec[i].clear();
	for (int i = 1; i <= n; i++)
	{
		cin >> m;
		s[i] = m;
		for (int j = 1; j <= m; j++)
		{
			cin >> k;
			vec[k].push_back(i);
		}
		if (!s[i]) q.push(-i);
	}
	m = n;
	int lst = 0, res = 0;
	while (q.size())
	{
		lst = 0, res++;
		while (q.size())
		{
			int xx = -q.top();
			q.pop();
			if (xx < lst) q2.push(-xx);
			else
			{
				lst = xx;
				m--;
				for (auto i : vec[xx])
				{
					if (!s[i]) continue;
					s[i]--;
					if (!s[i]) q.push(-i);
				}
			}
		}
		if (q2.size()) swap(q, q2);
	}
	if (m) puts("-1");
	else printf("%d\n", res);
}

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

D. Xor of 3

题意:给出一个01序列,每回操作从1到n-2中选择i,选择后将s[i],s[i+1],s[i+2]同步修改成s[i]s[i+1]s[i+2],问是否可以在不超过n的操作次数内,将数组清0,输出NO或YES,YES的时候需要输出如何操作

分析:思路我一点想不到,看的排行榜代码,数组中1的个数的奇偶性是不变的,所以奇数个1时直接NO,对于奇偶位有些关系,假设对于所有的奇数位都进行一次操作,那么对于第i位和第i+1位的一定相等,不管如何操作,这时候如果第一位为0,在对所有的奇数位刷一次的话就成立了,所以第一次要试着找一个位置,使得第一轮交换后,第一个位置变成0,所以我们刷前i位异或和,找到奇数位上任意一个为0的情况,因为这意味着到这个数前有偶数个位置,偶数个1,往前两个两个走一遍,第一个位置就是0了,对于这个数之后的位置,就正常刷,每次跳两个位置,第一轮操作完后,所有的奇数位置就都和对应偶数位置的值相同了,所以再去拿所有奇数位走一遍就能将数组清零,n为奇数时不刷最后一个位置,因为不合法。

代码:

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

#define x first
#define y second
#define MAX(a,b,c) max(max(a, b),c)
#define MIN(a,b,c) min(min(a, b),c)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'

using namespace std;

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

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

int n, m, t, k;

int cnt = 0;

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

string str;

vector<int> vec;

void solve()
{
	vec.clear();
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int a;
		cin >> a;
		s[i] = s[i-1] ^ a;
	}
	int flag = 0;
	for (int i = 0; i <= n; i++)
		if (i % 2 == 1 && !s[i])
		{
			int j = i;
			while (j + 3 <= n)
			{
				vec.push_back(j + 1);
				s[j + 2] = 0;
				s[j + 1] = s[j + 3];
				j += 2;
			}
			j = i;
			while (j - 2 > 0)
			{
				vec.push_back(j - 2);
				s[j - 2] = 0;
				s[j - 1] = s[j - 3];
				j -= 2;
			}
			flag = 1;
			break;
		}
	if (!flag || s[n])
	{
		puts("NO");
	}
	else
	{
		for (int i = 1; i + 2 <= n; i += 2) vec.push_back(i);
		puts("YES");
		cout << vec.size() << endl;
		if (vec.size() == 0) return;
		for (int i = 0; i < vec.size(); i++)
		{
			if (i) printf(" ");
			printf("%d", vec[i]);
		}printf("\n");
	}
}

int main()
{
    t = 1;
    cin >> t;
    while(t--) 
        solve();
    return 0;
}
上一篇:字符串句子专题


下一篇:阿里云域名优惠口令及阿里云优惠获取方法(最新)