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代表右移
奇数和偶数都举一个例子
标签：847,map,int,res,void,ABCDE,cin,solve,Div From： https://www.cnblogs.com/rickly233/p/17072887.html