url:Dashboard - Codeforces Round #847 (Div. 3) - Codeforces

A. Polycarp and the Day of Pi

题意:

判断给的字符串前多少位跟PI一样

思路:

打个表,然后遍历一下即可,遇到不是的就退出

代码:

string op = "314159265358979323846264338327950288419716939937510";
 
void solve()
{
	string s1;
	cin >> s1;
	for(int i = 0;i < s1.size();i++)
	{
		if(s1[i] != op[i])
		{
			cout << i << endl;
			return;
		}
	}
	cout << s1.size() << endl;
}

总结:

水题,不总结(

B. Taisia and Dice

题意:

给n个骰子,和n个骰子的点数之和和去掉最大点数的点数之和

思路:

先可以求出最大的骰子点数maxn

然后用剩下的点数去分配给n - 1个骰子,使得点数为[1,maxn]

最开始想的是弄个平均值啥的

后来一看范围就直接暴力好了,就循环一个一个放,这样保证了一定平均值是最小的

但是今天写题解时想了想,居然把昨天那种平均值方法写出来了

就是先求出$x = res / (n - 1)$和$y = res % (n - 1)$

然后输出前$n - 1 - y$个$x$

再输出前$y$个$x + 1$

最后输出$maxn$

代码1:

void solve()
{
	int sum,res;
	cin >> n >> sum >> res;
	vector<int> a(n + 1);
	int maxn = sum - res;
	for(int i = 1;i <= n - 1;i++)
	{
		if(res > 0) a[i]++;
		else break;
		res--;
		if(i == n - 1) i = 0;
	}
	for(int i = 1;i <= n - 1;i++) cout << a[i] << " ";
	cout << maxn << endl;
}

代码2:

void solve()
{
	int sum,res;
	cin >> n >> sum >> res;
	vector<int> a(n + 1);
	int maxn = sum - res;
	int x = res / (n - 1);
	int y = res % (n - 1);
	// cout << x << " " << y << endl;
	for(int i = 1;i <= n - 1 - y;i++) cout << x << " ";
	for(int i = 1;i <= y;i++) cout << x + 1 << " ";
	cout << maxn << endl;
}

C. Premutation

题意:

给n个n - 1长度的排列

每个排列都为一个原始排列去掉了一个数所成的,保证n个排列去掉的数不相同

思路:

主要是读题就读了很久,大概知道什么意思后感觉就看出来规律

主要是顺序是乱的,所以看起来很难受

后来想一想,

每个位置都少出现一次

那只要看第一个位置,必然会有一个不同的

找到不同的那个位置,然后输出其余n - 1个相同的那个数

再输出剩下的n - 1个位置的数即可

但是这种过程中想用用全部异或以来那个技巧

然后才发现那个是用来找所有数都出现偶数次,只有一个数出现奇数次才能用的

这个时候用map老老实实暴力就好了

别想着花里胡哨的(

代码:

void solve()
{
	cin >> n;
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n - 1;j++)
			cin >> a[i][j];
	map<int,int> mp;
	for(int i = 1;i <= n;i++) mp[a[i][1]]++;
	int q1,q2,idx;
	for(auto it : mp)
	{
		if(it.se == 1) q1 = it.fi;
		else q2 = it.fi;
	}
	for(int i = 1;i <= n;i++)
	{
		if(a[i][1] == q1)
		{
			idx = i;
			break;
		}
	}
	cout << q2 << " ";
	for(int i = 1;i <= n - 1;i++) cout << a[idx][i] << " ";
	cout << endl;
}

总结:

别想着玩花的技巧

就算多跑个循环,多开点变量,都不会有事(

能过就行(

D. Matryoshkas

题意:

给n个数,问最少能凑成几个集合

思路:

贪心凑,排序后从最小的开始,然后找这个数+1的数

直接双重循环 + 标记数组会TLE

这时候需要用map来优化一波

还是先排序,不过先把每个值装到map里

还是按照a[i]的1到n来遍历

不过每次先检查map[a[i]]是否为空

然后再将循环减去a[i]递增的值

这样就省去了开标记数组的时间和一部到位直接到下一个值

而不是一堆continue来占用时间

暴力代码:

void solve()
{
	int ans = 0;
	cin >> n;
	vector<int> a(n + 1),st(n + 1,0);
	for(int i = 1;i <= n;i++) cin >> a[i];
	sort(all(a));
	for(int i = 1;i <= n;i++)
	{
		int x = a[i] + 1;
		if(st[i]) continue;
		for(int j = i + 1;j <= n;j++)
		{
			if(st[j]) continue;
			if(a[j] == x)
			{
				st[j] = 1;
				x++;
			}
		}
		ans++;
	}
	cout << ans << endl;
}

优化代码:

void solve()
{
	int ans = 0;
	map<int,int> mp;
	cin >> n;
	vector<int> a(n + 1);
	for(int i = 1;i <= n;i++) cin >> a[i],mp[a[i]]++;
	sort(all(a));
	for(int i = 1;i <= n;i++)
	{
		if(mp[a[i]])
		{
			int idx = a[i];
			while(mp[idx])
			{
				mp[idx]--;
				idx++;
			}
			// cout << idx << endl;
			ans++;
		}
	}
	cout << ans << endl;
}

总结:

如果暴力过程中出现了一堆continue的情况

这时候就可以用map来进行优化

E. Vlad and a Pair of Numbers

题意:

给一个数n,要你求两个数a和b,使得$a 异或 b == n$而且$(a + b) / 2 == n$

思路:

考虑位运算

$(a + b) / 2$要求$a + b$肯定要是个偶数

所以a和b要么同为奇数,要么同为偶数

但是n为奇数的话二进制形式最后一位为1

显然矛盾了,所以n只能为偶数

然后看公式,就是要求两个数相加后向右移一位等于这两个数异或起来的值

首先构造$a 异或 b == n$

如果n的位置上为1,a,b则可以放1 0或者0 1

如果n的位置上为0,a,b则可以放1 1或者0 0

然后再构造$(a + b) / 2 == n$

其实就是二进制形式相加进位后我们希望结果为n向左移一位

这样再/2向右移一位,这样刚好结果为n

那就变成了如何安排a和b的二进制形式使得结果为n向左移一位

实际向左移一位就是所有1进位即可

要想要所有1进位,安排如下:
1变成1 0

1后面的一个0变成 1 1

其余0变成0 0

这样即可保证所有1进位

另外不能有连续的1出现在n中

因为连续的1的话,要么就留在那里不动,要么这几位都变成0

不能保证向左移一位

代码:

void solve()
{
	cin >> n;
	if(n&1)
	{
		cout << -1 << endl;
		return;
	}
	bitset<32> op(n),a(0),b(0);
	int x = 0,y = 0;
	bool flag = 0;
	for(int i = 31;i >= 0;i--)
	{
		if((i != 0)&&(op[i] == 1)&&op[i - 1] == 1)
		{
			cout << -1 << endl;
			return;
		}
		if(op[i] == 1)
		{
			a[i] = 1;
			b[i] = 0;
			flag = 1;
		}
		else if(flag)
		{
			a[i] = 1;
			b[i] = 1;
			flag = 0;
		}
		else
		{
			a[i] = 0;
			b[i] = 0;
		}
		if(a[i]) x += 1 << i;
		if(b[i]) y += 1 << i;
	}
	cout << x << " " << y << endl;
}

总结:

看到^和数据范围给的是2的次方的时候考虑位运算

从公式入手,*2代表左移,/2代表右移

奇数和偶数都举一个例子