PAT甲级1051-1060
1055是0通过率，错题；
1056的题目先就看不明白，看明白后我陷入了自我怀疑，不知道这道题到底想干嘛？懒得写，直接粘贴了网上的AC代码；
1057很有意思，学了新的数据结构——树状数组，可以看看；
1051 Pop Sequence
//这是考察栈的性质，栈是后进先出的。我们假设一个数字已经入栈了，那么他将大于之前所有入栈
//的数字，也就是说，如果此时进行pop，那么得到的数列一定是递减的。这就得到了每一次pop得到
//的子队列的性质——递减。那么子队列和子队列之间有什么性质呢？那就是当任一个数字弹出之后
//他之前的压入栈的肯定是有序的，也就是说，之前压入栈的弹出时肯定是遵循从大到小的顺序。
//而且之后弹出的子序列里，第一个数肯定要大于之前的序列的最大的数，否则就是错的。
//因此假设栈无限大，那这道题就可以简化为，求证一堆递减的子序列，是否每个序列的第一个元素
//都大于之前序列最大的那个元素。但是因为栈大小是固定的，因此每一个子序列的长度不可能超过
//栈的size。因此1，2，3，4，5，6，7入栈再出栈，不可能是7，6，5，4，3，2，1，以为栈
//不够大。
#include <iostream>
#include <vector>
using namespace std;
bool check(const vector<int> &tobe_check, const int stack_size);
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int stack_size, all_num, ck_queue;
cin >> stack_size >> all_num >> ck_queue;
vector<int> tobe_check(all_num);
for (int i = 0; i != ck_queue; ++i) {
for (int j = 0; j != all_num; ++j)
cin >> tobe_check[j];
if (check(tobe_check, stack_size)) {
cout << "YES" << endl;
} else
cout << "NO" << endl;
}
}
bool check(const vector<int> &tobe_check, const int stack_size) {
int last_max = tobe_check[0];
int len = 1; //记录当前子串长度
for (int i = 1; i != tobe_check.size(); ++i) {
if (tobe_check[i] < tobe_check[i - 1]) { //说明还是递减序列
++len;
} else { //说明一个子序列结束了
if (len > stack_size) //子序列的长度大于栈长度，不可能
return false;
if (tobe_check[i] < last_max)
return false;
last_max = tobe_check[i];
len = 1;
}
}
if (len > stack_size) //子序列的长度大于栈长度，不可能
return false;
return true;
}
1052 Linked List Sorting
//这道题的正经解法可能是读入一个数据插入一个数据，这样把整个链串起来
//实际上只要每个节点的地址和自己的数据对应，next域根本没什么卵用。
//只要插入的时候注意重写一个next就行了。这种链表插入，可能非常耗时间
//因为每次都是从头到尾的遍历，所以可以将链表加一个prev域，然后先放入
//一个vector，之后做二分查找。
//但是有排序函数，谁会用正经解法呢？
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
struct node {
int addr;
int data;
int next;
node() = default;
};
vector<node> Memory(100000);
int main() {
int nums, head;
scanf("%d %d", &nums, &head);
//这里还是要考虑给了废节点的问题。
for (int i = 0; i != nums; ++i) {
int addr;
scanf("%d", &addr);
scanf("%d %d", &Memory[addr].data, &Memory[addr].next);
Memory[addr].addr = addr;
}
vector<node> list;
list.reserve(nums);
for (int addr = head; addr != -1; addr = Memory[addr].next) {
list.push_back(Memory[addr]);
}
sort(list.begin(),list.end(),[](const node &a,const node &b){
return a.data < b.data;});
if(list.size() == 0){ //题目没说当链表为空时怎么输出。经测试应当这么输出
printf("0 -1\n");
return 0;
}
for(int i = 1 ; i != list.size() ; ++i){
list[i - 1].next = list[i].addr;
}
printf("%d %05d\n",(int)list.size(),list[0].addr);
for(int i = 0 ; i != list.size() - 1; ++i){
printf("%05d %d %05d\n",list[i].addr,list[i].data,list[i].next);
}
printf("%05d %d -1\n",list.back().addr,list.back().data);
return 0;
}
1053 Path of Equal Weight
//深度优先遍历的一道题，比之前那些图的相同最短路径简单多了。简直就是~顺手做了。
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct node {
int weight;
vector<int> children;
};
void DFS(const vector<node> &tree, const int weight, const int head,
int prev_weight, vector<int> prevpath, vector<vector<int>> &path);
int main() {
ios::sync_with_stdio(false);
int node_num, none_leaf_num, weight;
cin >> node_num >> none_leaf_num >> weight;
vector<node> tree(node_num);
for (int i = 0; i != node_num; ++i) {
cin >> tree[i].weight;
}
for (int i = 0; i != none_leaf_num; ++i) {
int node_index, k;
cin >> node_index >> k;
tree[node_index].children.resize(k);
for (int j = 0; j != k; ++j) {
cin >> tree[node_index].children[j];
}
}
vector<vector<int>> path;
DFS(tree, weight, 0, 0, vector<int>(), path);
sort(path.rbegin(),path.rend());
for(auto it = path.begin(); it != path.end() ; ++it){
for(auto itt = it->begin();itt != it->end() - 1 ; ++itt){
cout << *itt << " ";
}
cout << it->back() << endl;
}
return 0;
}
void DFS(const vector<node> &tree, const int weight, const int head,
int prev_weight, vector<int> prevpath, vector<vector<int>> &path) {
prevpath.push_back(head);
prev_weight += tree[head].weight;
if (tree[head].children.empty()) {
if (prev_weight == weight) {
vector<int> tmp;
for (auto it = prevpath.begin(); it != prevpath.end(); ++it) {
tmp.push_back(tree[*it].weight);
}
path.push_back(tmp);
}
return;
}
for (auto it = tree[head].children.begin(); it != tree[head].children.end();
++it) {
DFS(tree, weight, *it, prev_weight, prevpath, path);
}
}
1054 The Dominant Color
//这道题真是一言难尽，放到乙级都太简单了吧
#include <iostream>
#include <map>
using namespace std;
int main() {
ios::sync_with_stdio(false);
int M, N;
cin >> M >> N;
map<int,int> graph;
for (int i = 0; i != N * M; ++i) {
int tmp;
cin >> tmp;
++graph[tmp];
if (graph[tmp] > N * M / 2 ){
cout << tmp << endl;
return 0;
}
}
}
1055 The World’s Richest
//这道题也是0通过率，全部超时2、3节点，结合1047那个超时
//我感觉新版的PAT改题程序在密集IO时效率极低，所以密集IO的题全0通过
//这道题的内存限制也没有任何意义。估计属于程序出错导致的。
//新版PAT改的真是乱七八糟。
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
typedef struct person {
char name[9];
int age;
int worths;
} person;
bool cmp(person a, person b) {
if (a.worths == b.worths) {
if (a.age == b.age)
return strcmp(a.name, b.name) < 0;
return a.age < b.age;
}
return a.worths > b.worths;
}
int main() {
int N, K, i;
vector<person> ori;
cin >> N >> K;
while (N--) {
person temp;
scanf("%s %d %d", &temp.name, &temp.age, &temp.worths);
ori.push_back(temp);
}
sort(ori.begin(), ori.end(), cmp);
int M, min, max, size = ori.size(), j;
for (i = 1; i <= K; i++) {
scanf("%d%d%d", &M, &min, &max);
printf("Case #%d:\n", i);
int count = 0;
for (j = 0; j < size; j++) {
if (ori[j].age >= min && ori[j].age <= max) {
printf("%s %d %d\n", ori[j].name, ori[j].age, ori[j].worths);
count++;
}
if (count == M)
break;
}
if (count == 0)
printf("None\n");
}
return 0；
}
1056 Mice and Rice
//这题……简直了。题目简直是天书，根本看不明白想说啥。看明白以后，这特么题目存在的意义是什么？
#include <iostream>
#include <vector>
using namespace std;
int main() {
int np, ng;
scanf("%d%d", &np, &ng);
vector<int> weight, order, rank;
weight.resize(np);
order.resize(np);
rank.resize(np);
for (int i = 0; i < np; ++i)
scanf("%d", &weight[i]);
for (int i = 0; i < np; ++i)
scanf("%d", &order[i]);
int curRank = 0;
while (order.size() > 1) {
curRank = order.size() / ng + 1;
if (order.size() % ng > 0)
++curRank;
vector<int> next;
next.clear();
int n = 0;
while (n < order.size()) {
int max = -1, index = 0;
for (int i = 0; i < ng && n < order.size(); ++i, ++n) {
rank[order[n]] = curRank;
if (weight[order[n]] > max) {
max = weight[order[n]];
index = order[n];
}
}
next.push_back(index);
}
order = next;
}
rank[order[0]] = 1;
printf("%d", rank[0]);
for (int i = 1; i < np; ++i)
printf(" %d", rank[i]);
return 0;
}
1057 Stack
首先，这道题其实和栈本身没有关系，根本就不用去模拟什么栈，直接用Stack就可以了。因为他要求返回的中位数不是下标，而是栈排序后的那个中位数，所以这道题的实质是：如何快速找到一个无序数组的中位数。如果每次都排序的话，显然是要超时的。那么怎么办呢？最开始我的想法是用一个map<int,int>来保存每个数字出现的次数，然后每次要输出中位数的时候就循环一遍，来找那个中，但这样也有大量的重复计算，其实可能只减去了一个值，下一次还要从头加到尾，这也是不可接受的速度，实际上也确实中间三个节点全部超时。
超时代码
代码如下：
#include <cstdio>
#include <map>
#include <string.h>
#include <vector>
using namespace std;
int main() {
freopen("input", "r", stdin);
int operas;
char oper[11];
scanf("%d", &operas);
vector<int> stack;
map<int, int> rank; //记录每一种数据出现了几次
stack.reserve(operas);
for (int i = 0; i != operas; ++i) {
scanf("%s", oper);
if (strlen(oper) == 3) {
if (stack.size() == 0) {
printf("Invalid\n");
} else {
printf("%d\n", stack.back());
--rank[stack.back()];
stack.pop_back();
}
} else if (strlen(oper) == 10) {
if (stack.size() == 0) {
printf("Invalid\n");
} else {
int index =
stack.size() % 2 ? (stack.size() + 1) / 2 : stack.size() / 2;
index -= 1;
int ranks = 0;
int output;
for(auto it = rank.begin() ; it != rank.end() ; ++it){
ranks += it->second;
if(ranks > index){
//说明这个值就是当前要找的值，比如说index=0时，一加直接就大于了，那就返回当前值。
//如果等于还不行，比如说index = 1时，实际上是要找第二个元素，如果ranks = 1
//也就是说当小于等于当前元素的数量只到1，还不是第二个元素。
output = it->first;
break;
}
}
printf("%d\n", output);
}
} else{
int data;
scanf("%d", &data);
stack.push_back(data);
rank[data]++;
}
}
return 0;
}
看来这样是不行的，那能不能减少这样的重复加法呢？想来想去还是很难，假设想用某种数据结构，假如说数列吧，保存某个值的index，这样每次push和pop之后，就要更新整个数组，也是很恐怖的工作量。
动态维护set法
在网上看到一个哥们的思路，是维护两个set和一个middle值，set1为排序后的stack的前半部分，set2为排序后的stack的后半部分，令set1.size() == set2.size()或者set1.size() == set2.size() + 1，middle为set1的最后一个数值。这样每次push和pop时维护一下set1和set2就可以了，middle值可以直接输出。因为值可能重复，因此用了multiset，这样维护的工作量看起来要小一点，实现代码如下：
#include <cstdio>
#include <set>
#include <stack>
#include <string.h>
using namespace std;
void adjust(multiset<int> &front, multiset<int> &tail, int data, int opera) {
int middle;
if (opera == -1) { //删除元素
middle = *front.rbegin();
if (data > middle) {
auto it = tail.find(data);
tail.erase(it);
} else {
auto it = front.find(data);
front.erase(it);
}
} else {
if (front.empty()) {
front.insert(data);
} else {
middle = *front.rbegin();
if (data > middle) {
tail.insert(data);
} else {
front.insert(data);
}
}
}
if (front.size() > tail.size() + 1) {
auto it = front.end();
--it;
tail.insert(*it);
front.erase(it);
} else if (front.size() < tail.size()) {
auto it = tail.begin();
front.insert(*it);
tail.erase(it);
}
}
int main() {
//freopen("input", "r", stdin);
int operas;
char oper[11];
scanf("%d", &operas);
stack<int> stacks;
multiset<int> front, tail;
int middle;
for (int i = 0; i != operas; ++i) {
scanf("%s", oper);
if (strlen(oper) == 3) {
if (stacks.size() == 0) {
printf("Invalid\n");
} else {
printf("%d\n", stacks.top());
adjust(front, tail, stacks.top(), -1);
stacks.pop();
}
} else if (strlen(oper) == 10) {
if (stacks.size() == 0) {
printf("Invalid\n");
} else {
printf("%d\n", *front.rbegin());
}
} else {
int data;
scanf("%d", &data);
stacks.push(data);
adjust(front, tail, data, 1);
}
}
return 0;
}
这个代码是AC的，最长时间用了65ms。
树状数组
前面说到，map法之所以效率低，就是因为做了很多重复的加法，我们在最后设想用一个数组维护每个数出现的次数，但是每次求的时候实际上求的不是某个数字出现的次数，而是小于这个数字的所有数字出现的次数，也就是这个数组的前缀和。
这样朴素的暴力解法有两种想法，第一是每次修改就只修改这个数出现的次数，但每次求的时候，因为需要求一个区间的和，要从头加到尾，所以时间复杂度还是O(qn)，q是求和区间占总区间的百分比；第二种是用数组存储一段前缀和，这样查询起来是O(1)的复杂度，但每次插入都要更新一段区间，因此更新的复杂度是O(qn)，所以依然显然无论用哪一种方式，都无法得到令人满意的时间复杂度。
这个问题就用树状数组来解决。
树状数组，首先是一个数组，假如我们要求前缀和的数组是A[1\~n]，那么用来快速求解这个前缀和的数组我们定义为C[1\~n]，长度和原数组是一样的。
为什么叫树状数组呢？因为他利用了一些二进制的小技巧，每个C[n]都表示了A[1\~n]某段区间之和。这样的话，C数组的不同元素之间就有了层次关系。如这个经典的图：
其中有：
C1 = A1
C2 = A1+A2
C3 = A3
C4 = A1+A2+A3+A4
C5 = A5
C6 = A5+A6
C7 = A7
C8 = A1+A2+A3+A4+A5+A6+A7+A8
通过把令C数组的不同元素表达不同的区间之和，我们可以在更新每一段区间时，只更新受影响的前缀和，而用更新整段前缀和。比如A5的更新，将影响C5，C6，C8，但不会影响C4、C7等，这样无论是在更新时，还是在插入时，时间复杂度都可以控制在lg(n)。
那么为什么是这样组织的呢，为什么C4 = A1+A2+A3+A4，C6 = A5+A6呢？这就涉及到二进制的相关知识。
接下来我们用二进制表示下标，那么有下列对应关系：
C[1] -> C[1]
C[2] -> C[10]
C[3] -> C[11]
C[4] -> C[100]
C[5] -> C[101]
C[6] -> C[110]
C[7] -> C[111]
C[8] -> C[1000]
C[9] -> C[1001]
C[10] -> C[1010]
然后我们令下列关系成立：
C[1] = A[1]
C[10] = A[1] + A[10]
C[11] = A[11]
C[100] = A[1] + A[10] + A[11] + A[100]
C[101] = A[101]
C[110] = A[101] + A[110]
C[111] = A[111]
C[1000] = A[1] + A[10] + A[11] + A[100] + A[101] + A[110] + A[111] + A[1000]
C[1001] = A[1001]
C[1010] = A[1001] + A[1010]
我们接下来再观察下标，就可以得出一个结论，C[x]表示的是A[x – 2^k + 1]到A[x]之间这个区间的和，其中2^k就是x取最后一个1形成的数，比如说：C[110]，其2^k就是10，也就是2，所以C[x] = A[110 – 10 + 1] + A[110 – 10 + 10]。
为什么要这么分解呢？主要是为了这棵树的上级比较好求一些。
比如C[110]，我们求他的父节点的话，只要C[110 + 10]就OK了，而C[100]，我们也只需要C[100 + 100]就OK了，要是求C[11100]的上级节点，那我们也可以很快的得到，就是C[11100 + 100]，换算成10进制，就是C[24]的上级节点是C[32]。而当从A[x]来求他的父节点（也就是当他更新时需要更新的父节点），也比较容易，比如A[110]，那么要更新的父节点就包括C[110]，以及C[110]的父节点。因此更新一个节点时，可以很快更新其父节点。
那么求前缀和呢？（因为求区间和实际上是两个前缀和的差，因此求区间和不过是求两个前缀和。）
比如说求A[1\~111]，就可以分解为求C[100] + C[110] + C[111]，仔细观察后缀，实际上就是依次将最后一个111的最后一个1去掉，直到只剩一个1了，那么也很容易理解，A[1\~110]就是C[100]+C[110]，A[1\~1111]，就是C[1000] + C[1100] + C[1110] + C[1111]。根据定义可以对相应的C进行展开，肯定是没错的。
于是这样的一个更新和查询问题就可以在一棵树的时间复杂度上进行了。
我们注意到，这里用到了大量的求最后一个1在哪里的操作，这个操作在这个算法里有个约定俗成的名字，叫lowbit(x)，具体的实现如下：
int lowbit(x){
return x & (-x);
}
这个算法能够取最后一位1的根本原因在于，当前的绝大多数计算机，都是用补码表示负数的，比如我们用一个8bite的二进制数来表示一个正整数，比如说十进制的10，那就是1010，那么-10怎么表示呢，就是11110110，这样按位与之后，就得到了最后一个10，再比如说十进制的17，那就是10001，那么-17的补码表示是什么呢？是11101111。不用做再多验证，这个函数将取得x的最低一位的1。
要注意的是，因为0的补码表示还是0，因此lowbit(x)无法处理0的情况，因此树状数组一般从1开始编号。
那么我们更新这个树状数组时，该怎么更新呢？
void update(int pos,int data,int len ){
//将pos位置的数据更改data，这个data是旧数值与原数值的差值，len是数组长度(从1开始编号)
for(int i = pos ; i <= len ; i += lowbit(i))
C[i] += data;
}
当我们查询某个前缀和的时候，又该怎么查询呢？
int query(int pos){
//前pos个数据的前缀和
int res = 0;
for(int i = pos ; i != 0 ; i -= lowbit(i))
res += C[i];
return ret;
}
至此，我们就解决了，如何快速查询一个数列前缀和的技巧。简直鬼斧神工，叹为观止~这么多精彩绝伦的算法，真是不知道什么时候能学到个头啊。
那么用树状数组重写这道题，就是下面这个样子。（考虑到因为A没有负值，所以C是单调增的数列，可以用二分查找进一步提高效率）
//最长耗时49ms
#include <cstdio>
#include <stack>
#include <string.h>
#include <vector>
using namespace std;
#define lowbit(x) ((x) & (-(x)))
int query(const vector<int> &C, int pos) {
int res = 0;
for (int i = pos; i != 0; i -= lowbit(i))
res += C[i];
return res;
}
void update(vector<int> &C, int pos, int updtdata) {
for (int i = pos; i < C.size(); i += lowbit(i))
C[i] += updtdata;
}
int find_middle(const vector<int> &C,int pos) {
int begin = 0;
int end = C.size() - 1;
int middle;
while (begin < end) {
middle = (begin + end) / 2;
if (query(C,middle) < pos){
begin = middle + 1;
}else {
end = middle;
}
}
return end;
}
int main() {
int operas;
char oper[11];
scanf("%d", &operas);
stack<int> stacks;
vector<int> C(100005,0);
//vector<int> A(100005); 其实这个数组是没有必要维护的
for (int i = 0; i != operas; ++i) {
scanf("%s", oper);
if (strlen(oper) == 3) {
if (stacks.size() == 0) {
printf("Invalid\n");
} else {
printf("%d\n", stacks.top());
update(C, stacks.top(), -1);
stacks.pop();
}
} else if (strlen(oper) == 10) {
if (stacks.size() == 0) {
printf("Invalid\n");
} else {
printf("%d\n", find_middle(C,(stacks.size() + 1) / 2));
}
} else {
int data;
scanf("%d", &data);
stacks.push(data);
update(C, data, 1);
}
}
return 0;
}
码量很小，就算不明白具体原理，一样能拿来方便地使用。
分桶法
分桶法的本质是一种分治法。依然用求区间和这个工作来举例，前面说到，我们如果采用暴力算法，那么要么更新的时间复杂度是O(qn)，要么查询的时间复杂度是O(qn)，总之效率都有限。那么我们可以将该数组分为一段一段的来处理，比如说我们令每100个数据为一段，维护一个这一段数据的和，比如[0\~100]这一段表示数组前100个元素的和，[101\~200]表示数组100-200元素的和。那么在更新一个数据时，我们只需要更新这个桶的的元素和即可，也就是说更新的时候能达到O(1)的效率。我们接下来看查询，当查询某个区间和时，假设为[75\~225]，则只需要做75到100的加法，之后直接将[101\~200]这一段的和加进去，再做[201\~225]的加法就够了。
这样的每一个段，我们称之为桶。这样进行一次遍历，时间复杂度为O(max(k,m))，其中k为桶的大小，m为桶的数量。这样易知当k=m时，效率最高。因此效率最高为\sqrt{n}，n为数组大小。
可见这个分桶法的查询效率是要低于树状数组的。100000的平方根接近300，那我们就用300做每个桶的大小。
于是我们用一个sum[100000 / 300 ≈ 335]这么一个数组来保存每个桶的和。
实现代码如下：
//最高用时135ms
#include <cstdio>
#include <stack>
#include <string.h>
#include <vector>
using namespace std;
constexpr int BUK_SIZE = 300;
constexpr int BUK_NUM = 100005 / BUK_SIZE + 1;
inline void update(int A[], int sum[], int pos, int value) {
sum[pos / BUK_SIZE] += value;
A[pos] += value;
}
int query(int A[], int sum[], int pos) {
//求从0到这个pos的和,包含pos在内
int ret = 0;
int buk_index = (pos + 1) / BUK_SIZE;
int index_in_buk = (pos + 1) % BUK_SIZE;
for (int i = 0; i != buk_index; ++i) { //不能真的加到buk_index;
ret += sum[i];
}
if (index_in_buk == 0)
return ret;
else if (index_in_buk < 150) {
for (int i = buk_index * BUK_SIZE; i <= pos; ++i) {
ret += A[i];
}
} else {
int tmp = sum[buk_index];
for (int i = (buk_index + 1) * BUK_SIZE - 1; i > pos; --i) {
tmp -= A[i];
}
ret += tmp;
}
return ret;
}
int find_middle(int A[], int sum[], int value) {
//仍然要祭出二分查找大法啊
int begin = 0;
int end = 100001;
while (begin < end) {
int mid = (begin + end) / 2;
if (query(A, sum, mid) >= value) {
end = mid;
} else {
begin = mid + 1;
}
}
return end;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input", "r", stdin);
#endif
int operas;
char oper[11];
scanf("%d", &operas);
stack<int> stacks;
int A[100005];
int sum[BUK_NUM];
for (int i = 0; i != operas; ++i) {
scanf("%s", oper);
switch (oper[1]) {
case 'o':
if (stacks.size() == 0) {
printf("Invalid\n");
} else {
printf("%d\n", stacks.top());
update(A, sum, stacks.top(), -1);
stacks.pop();
};
break;
case 'e':
if (stacks.size() == 0) {
printf("Invalid\n");
} else {
printf("%d\n", find_middle(A, sum, (stacks.size() + 1) / 2));
}
break;
case 'u':
int data;
scanf("%d", &data);
stacks.push(data);
update(A, sum, data, 1);
break;
}
}
return 0;
}
在网上看到不用二分法，而是直接暴力循环的案例，大概是下面这个样子：
//最高用时45ms。看来对于这道题的数据来说，二分法并没有优势。
//关键是这个二分里就包含了很多重复查询，效率不高。不如一步到位。
#include <cstdio>
#include <stack>
#include <string.h>
#include <vector>
using namespace std;
constexpr int ARRY_SIZE = 100005;
constexpr int BUK_SIZE = 300;
constexpr int BUK_NUM = ARRY_SIZE / BUK_SIZE + 1;
inline void update(int A[], int sum[], int pos, int value) {
sum[pos / BUK_SIZE] += value;
A[pos] += value;
}
int query(int A[], int sum[], int pos) {
int cnt = 0, i;
for (i = 0; i != BUK_NUM; ++i) {
if (cnt + sum[i] >= pos)
break;
cnt += sum[i];
}
for (int j = 0; j != BUK_SIZE; ++j) {
cnt += A[i * BUK_SIZE + j];
if (cnt >= pos)
return i * BUK_SIZE + j;
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("input", "r", stdin);
#endif
int operas;
char oper[11];
scanf("%d", &operas);
stack<int> stacks;
int A[ARRY_SIZE];
int sum[BUK_NUM];
for (int i = 0; i != operas; ++i) {
scanf("%s", oper);
switch (oper[1]) {
case 'o':
if (stacks.size() == 0) {
printf("Invalid\n");
} else {
printf("%d\n", stacks.top());
update(A, sum, stacks.top(), -1);
stacks.pop();
};
break;
case 'e':
if (stacks.size() == 0) {
printf("Invalid\n");
} else {
printf("%d\n", query(A, sum, (stacks.size() + 1) / 2));
}
break;
case 'u':
int data;
scanf("%d", &data);
stacks.push(data);
update(A, sum, data, 1);
break;
}
}
return 0;
}
分桶法还有个用处，就是求区间最值，最大值或者最小值，这种运算用线段树做不出来，用分桶法就比较容易一些。
1058 A+B in Hogwarts
# 29 Knuts = 1 Sickle, 17 Sickles = 1 Galleon
# 送分题
A, B = input().split()
AG, AS, AK = [int(x) for x in A.split('.')]
BG, BS, BK = [int(x) for x in B.split('.')]
AKs = AG * 17 * 29 + AS * 29 + AK
BKs = BG * 17 * 29 + BS * 29 + BK
OKs = BKs + AKs
OG = int(OKs / 17 / 29)
OS = int((OKs % (17 * 29)) / 29)
OK = int(OKs % 29)
print(str(OG)+'.'+str(OS)+'.'+str(OK))
1059 Prime Factors
//寻找质因数
#include <iostream>
#include <map>
#include <math.h>
using namespace std;
bool isprime(long int k) {
if (k == 2 || k == 3) {
return true;
}
for (int i = 3; i <= sqrt(k) + 1; i += 2) {
if (k % i == 0)
return false;
}
return true;
}
int main() {
long int num;
cin >> num;
long backup = num;
map<long, long> factors;
if(num == 1){//题目并没有说1怎么输出，经验证应该是这样的
cout << "1=1" << endl;
return 0;
}
while ((num % 2) == 0) {
++factors[2];
num /= 2;
}
for (long i = 3; i <= sqrt(num) + 1 ; i += 2) {
// 2已经全部除完了，不用判断偶数的情况
if (isprime(i)) {
while ((num % i) == 0) {
++factors[i];
num /= i;
}
}
}
if(num != 1)
++factors[num];
cout << backup ;
for (auto it = factors.begin(); it != factors.end(); ++it) {
cout << (it == factors.begin() ? '=' : '*');
if (it->second >= 2) {
cout << it->first << "^" << it->second;
} else {
cout << it->first;
}
}
cout << endl;
return 0;
}
1060 Are They Equal
//代码写的太丑了……不忍看。
#include <iostream>
#include <string>
using namespace std;
string to_output(const string &a, int dotpos, int percition) {
bool notzero = false;
//假设收到了"0015"，显然原字符串是0.0015，那么就要处理负数的情况了
if (dotpos == 1 && a[0] == '0'){ //处理纯0的情况
dotpos = 0;
notzero = true;
}
string ret = "0.";
int i;
for (i = 0; i != percition && i != a.size(); ++i) {
if (a[i] == '0' && !notzero){
--dotpos;
++percition;
} else{
notzero = true;
ret += a[i];
}
}
for (int j = i; j < percition; ++j) {
//已经把a读完了，但精度还未满足，那就凑0
ret += '0';
}
ret += "*10^" + to_string(dotpos);
return ret;
}
int main() {
ios::sync_with_stdio(false);
int precition;
string num1, num2;
cin >> precition >> num1 >> num2;
if (num1.find_first_not_of('0') != string::npos)
num1 = num1.substr(num1.find_first_not_of('0'),num1.size());
else num1 = "0";
if (num2.find_first_not_of('0') != string::npos)
num2 = num2.substr(num2.find_first_not_of('0'),num2.size());
else num2 = "0";
auto dotpos1 = num1.find('.');
auto dotpos2 = num2.find('.');
//下面两行代码的意思是，如果没有小数点，就假设在数字最后点了一个小数点
//之后小数点就没有意义了。
if (dotpos1 == string::npos) {
dotpos1 = num1.size();
} else {
num1.erase(dotpos1, 1);
}
if (dotpos2 == string::npos) {
dotpos2 = num2.size();
} else {
num2.erase(dotpos2, 1);
}
//下面这一段处理0.0和0会出现dotpos不同的情况
if (num1.find_first_not_of('0') == string::npos){
num1 = "0";dotpos1 = 1;
}
if (num2.find_first_not_of('0') == string::npos){
num2 = "0";dotpos2 = 1;
}
string num1o = to_output(num1, dotpos1, precition);
string num2o = to_output(num2, dotpos2, precition);
if (num1o == num2o){
cout << "YES " << num1o << endl;
} else {
cout << "NO " << num1o << " " << num2o << endl;
}
return 0;
}
0 条评论