手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

【天天快播报】Codeforces Round #847 (Div. 3) ABCDE

2023-01-29 15:54:34 来源：博客园

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 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 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 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 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 mp;cin >> n;vector 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代表右移

奇数和偶数都举一个例子

关键词：是否为空这个时候知道什么