cf*3 总结与反思

C. Parity Shuffle Sorting

题意：
定义操作： 数组元素al 和 ar 。如果al + ar 为偶数，，al := ar， 否则 ar := al。
给一个数组，进行以上操作，最后得到操作多少次，将数组转换为非递减数组，并给出转换次数和每一次的操作。

解题思路： 将整个数组都转换为元素相同的数组的操作次数是小于n。可以考虑将整个数组赋值为一个相同的元素。因为操作比较特殊，是可以将第一个元素和最后一个元素操作为相同的元素。经过这一操作后，中间元素都可以经过操作转换为相同元素。

void solve() {
int n; cin>>n;
vector<int> a;
for(int ip,i = 0; i < n; ++i) {
cin>>ip; a.push_back(ip);
}
if(n == 1) { // 数组大小等于1时，自然是非递减的喽
cout<<"0n";
return ;
}
vector<PII> vp; // 操作步骤
if(a[0] != a[a.size()-1]) { // a[0] a[[n-1]不相等
vp.push_back({1, a.size()});
(a[0] + a[a.size()-1])%2 == 0 ? a[0] = a[a.size()-1] : a[a.size()-1] = a[0]; // 根据奇偶进行不同操作
}
for(int i = 1; i < a.size()-1; ++i) { // 对中间元素进行操作
if((a[i] + a[a.size()-1])%2 == 0) { // 偶数 ： 给al赋值
a[i] = a[a.size()-1];
vp.push_back({i+1, a.size()});
} else { // 奇数：给ar赋值
a[i] = a[0];
vp.push_back({1, i+1});
}
}
cout<<vp.size()<<endl;
for(auto it: vp) cout<<it.first<<" "<<it.second<<endl;
}

C. Minimum Notation

题意：
操作：选中一个元素ch，将其删除。之后在任何位置插入 min ( ch + 1, 9)元素。
给定一串数字。进行该操作，得到字典序最小序列。

解题思路： 对序列中元素来说，删除哪一个元素，之后加入的元素的位置顺序都是对后面有关系的，但是同时又因为插入位置是任意的，动态规划思路难以想到解法。每一个插入的元素对后面都是有关系的，就表明可以经过排序得到最后元素，这是因为当插入最小的元素后，后面在插入都是在该元素后面插入的，保证了前面对于后面来说是一个最小字典序。又因为每次插入的元素都是大于等于原始元素，可以考虑用逆序对来解决问题。单调栈 + 逆序对。

void solve() {
string str;
cin>>str;
int len = str.size();
stack<int> sk;
for(int i = 0; i < len; ++i) {
// 前面元素大于该元素时
while(sk.size() && str[sk.top()] > str[i]) {
// 找到该元素最小的插入元素
str[sk.top()] = min( char(str[sk.top()] + 1), '9');
sk.pop();
}// 输入下标
sk.push(i);
}
// 排序
sort(str.begin(), str.end());
cout<<str<<endl;
}

C. Digital Logarithm

题意：
定义函数f：f为元素的十进制位数。
给定两个数组 a 和 b ，可以给ai或bj赋值f(ai)或f(bj)，求最少多少次两个数组排序后相同。

解题思路： 首先考虑将两个数组的每个元素10进制位数用map进行叠加存储，之后从大到小进行赋值 f 的操作，但是发现这个并不满足要求（e.g. [334], [111] )。之后发现了一个更简单的方法，用优先队列（大顶堆）存储两个数组，遍历，对不相同的元素进行操作。

void solve() {
priority_queue<int> pa, pb;
int ip;
int n; cin>>n;
rep(i,1,n) {
cin>>ip; pa.push(ip);
}
rep(i,1,n) {
cin>>ip; pb.push(ip);
}
int cnt = 0;
while(pa.size() && pb.size()) {
int a = pa.top(), b = pb.top();
if(a == b) {
pa.pop(); pb.pop();
continue;
} else if(a > b) {
pa.pop();
pa.push(to_string(a).size());
} else {
pb.pop();
pb.push(to_string(b).size());
}
cnt++;
}
cout<<cnt<<endl;
}

今日总结：

做到了一个关于单调栈和优先队列的题。
把之前stl中优先队列的操作都忘了

priority_queue<int> pa; // 大顶堆 top is bigger
priority_queue<int, vector<int>， greater<int> > pp; // 小顶堆

同时通过看题解，发现了一个判断10进制数的位数的更快函数，就是把数字转换为字符串，用字符串的判断长度的函数。

int ab = 3434;
cout<<to_string(ab).size();

同时因为这几周都有考试等其他琐碎的事情，cf做题好久没有做了。感觉有点生疏，对思维题的敏感度下降了。要多练练，多理解多敲敲模板！

最后

以上就是忐忑鼠标为你收集整理的cf*3 总结与反思cf*3 总结与反思的全部内容，希望文章能够帮你解决cf*3 总结与反思cf*3 总结与反思所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。