首页 > 代码库 > Educational Codeforces Round 19
Educational Codeforces Round 19
由于时间原因只A掉了前三题。
Problem#A k-Factorization
题目传送门[here]
题目大意是说给出一个数n，能不能把它分成k个严格大于1的整数的乘积，如果可以，随便输出一种方案，否则就输出-1。
首先对n进行质因数分解，如果质因数的个数小于k就输出-1，否则随便合并几个使总数为k，然后输出就好了。
Code
1 /** 2 * CodeForces 3 * Problem#797A 4 * Accepted 5 * Time:15ms 6 * Memory:2044k 7 */ 8 #include<iostream> 9 #include<fstream> 10 #include<sstream>11 #include<algorithm>12 #include<cstdio>13 #include<cstring>14 #include<cstdlib>15 #include<cctype>16 #include<cmath>17 #include<ctime>18 #include<map>19 #include<stack>20 #include<set>21 #include<queue>22 #include<vector>23 using namespace std;24 typedef bool boolean;25 #define inf 0xfffffff26 #define smin(a, b) (a) = min((a), (b))27 #define smax(a, b) (a) = max((a), (b))28 template<typename T>29 inline boolean readInteger(T& u) {30 char x;31 int aFlag = 1;32 while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1);33 if(x == -1) {34 ungetc(x, stdin);35 return false;36 }37 if(x == ‘-‘) {38 aFlag = -1;39 x = getchar();40 }41 for(u = x - ‘0‘; isdigit((x = getchar())); u = u * 10 + x - ‘0‘);42 u *= aFlag;43 ungetc(x, stdin);44 return true;45 }46 47 int n, k;48 int top = 0;49 int a[40];50 51 inline void init() {52 readInteger(n);53 readInteger(k);54 }55 56 inline void solve() {57 int m = (int)sqrt(n + 0.5);58 for(int i = 2; i <= m && n > 1; i++) {59 while(n % i == 0) a[top++] = i, n /= i;60 }61 if(n != 1) a[top++] = n;62 if(top < k) printf("-1");63 else {64 int s = 1;65 for(int i = 0; i <= top - k; i++)66 s *= a[i];67 if(s > 1) printf("%d ", s);68 for(int i = top - k + 1; i < top; i++)69 printf("%d ", a[i]);70 }71 }72 73 int main() {74 init();75 solve();76 return 0;77 }
Problem#B Odd sum
题目传送门[here]
题目大意是说给定一个序列，找到一个子序列，使它的和为奇数，求这个最大的和。
记录一个最大的偶数和和奇数和，然后更新就好了。
Code
1 /** 2 * CodeForces 3 * Problem#797B 4 * Accepted 5 * Time:30ms 6 * Memory:2432k 7 */ 8 #include<iostream> 9 #include<fstream> 10 #include<sstream>11 #include<algorithm>12 #include<cstdio>13 #include<cstring>14 #include<cstdlib>15 #include<cctype>16 #include<cmath>17 #include<ctime>18 #include<map>19 #include<stack>20 #include<set>21 #include<queue>22 #include<vector>23 using namespace std;24 typedef bool boolean;25 #define inf 0xfffffff26 #define smin(a, b) (a) = min((a), (b))27 #define smax(a, b) (a) = max((a), (b))28 template<typename T>29 inline boolean readInteger(T& u) {30 char x;31 int aFlag = 1;32 while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1);33 if(x == -1) {34 ungetc(x, stdin);35 return false;36 }37 if(x == ‘-‘) {38 aFlag = -1;39 x = getchar();40 }41 for(u = x - ‘0‘; isdigit((x = getchar())); u = u * 10 + x - ‘0‘);42 u *= aFlag;43 ungetc(x, stdin);44 return true;45 }46 47 int n;48 int* a;49 int modd = -2e9, muodd = 0;50 51 inline void init() {52 readInteger(n);53 a = new int[(const int)(n + 1)];54 for(int i = 1; i <= n; i++)55 readInteger(a[i]);56 }57 58 inline void solve() {59 for(int i = 1; i <= n; i++) {60 int x0 = a[i] + muodd, x1 = a[i] + modd;61 if(x0 & 1) smax(modd, x0);62 else smax(muodd, x0);63 if(x1 & 1) smax(modd, x1);64 else smax(muodd, x1);65 }66 printf("%d", modd);67 } 68 69 int main() {70 init();71 solve();72 return 0;73 }
Problem#C Minimal string
题目传送门[here]
题目大意是说给定一个字符串，用一个栈对它进行"排序"，使得排序后的字符串字典序最小。
这是一道贪心题，如果说栈顶的字符所在原字符串的位置的右边的最小值比它小，就一直往右把字符加进栈，直到某个位置不存在，就把它弹出栈。由于原字符串经过各种抽取使得它残缺不全，所以不能直接记录最小值，用了一个线段树来维护，每将一个字符弹出栈就在线段树中把它所在的位置的值修改得很大很大。因为每个字符只会进栈出栈一次，所以总时间复杂度为O(nlog2n)
Code
1 /** 2 * CodeForces 3 * Problem#797C 4 * Accepted 5 * Time:46ms 6 * Memory:7360k 7 */ 8 #include<iostream> 9 #include<fstream> 10 #include<sstream> 11 #include<algorithm> 12 #include<cstdio> 13 #include<cstring> 14 #include<cstdlib> 15 #include<cctype> 16 #include<cmath> 17 #include<ctime> 18 #include<map> 19 #include<stack> 20 #include<set> 21 #include<queue> 22 #include<vector> 23 using namespace std; 24 typedef bool boolean; 25 #define inf 0xfffffff 26 #define smin(a, b) (a) = min((a), (b)) 27 #define smax(a, b) (a) = max((a), (b)) 28 29 typedef class SegTreeNode { 30 public: 31 char val; 32 SegTreeNode *l, *r; 33 SegTreeNode():val(127), l(NULL), r(NULL) { } 34 35 inline void pushUp() { 36 val = min(l->val, r->val); 37 } 38 }SegTreeNode; 39 40 typedef class SegTree { 41 public: 42 SegTreeNode* root; 43 44 SegTree():root(NULL) { } 45 SegTree(int n, char* s) { 46 build(root, 1, n, s); 47 } 48 49 void build(SegTreeNode*& node, int l, int r, char* s) { 50 node = new SegTreeNode(); 51 if(l == r) { 52 node->val = s[l]; 53 return; 54 } 55 int mid = (l + r) >> 1; 56 build(node->l, l, mid, s); 57 build(node->r, mid + 1, r, s); 58 node->pushUp(); 59 } 60 61 void update(SegTreeNode*& node, int l, int r, int idx, char val) { 62 if(l == idx && r == idx) { 63 node->val = val; 64 return; 65 } 66 int mid = (l + r) >> 1; 67 if(idx <= mid) update(node->l, l, mid, idx, val); 68 else update(node->r, mid + 1, r, idx, val); 69 node->pushUp(); 70 } 71 72 char query(SegTreeNode*& node, int l, int r, int ql, int qr) { 73 if(l == ql && r == qr) 74 return node->val; 75 int mid = (l + r) >> 1; 76 if(qr <= mid) return query(node->l, l, mid, ql, qr); 77 else if(ql > mid) return query(node->r, mid + 1, r, ql, qr); 78 int a = query(node->l, l, mid, ql, mid); 79 int b = query(node->r, mid + 1, r, mid + 1, qr); 80 return min(a, b); 81 } 82 }SegTree; 83 84 int n; 85 char s[100005]; 86 int top = 0; 87 char* sta; 88 int* idx; 89 SegTree st; 90 91 inline void init() { 92 scanf("%s", s + 1); 93 n = strlen(s + 1); 94 sta = new char[(const int)(n + 5)]; 95 idx = new int[(const int)(n + 5)]; 96 st = SegTree(n, s); 97 } 98 99 inline void solve() {100 int front = 1;101 sta[0] = 127;102 idx[0] = 0;103 while(front <= n || top) {104 if(front <= n) {105 while(front <= n && sta[top] > st.query(st.root, 1, n, idx[top] + 1, n))106 sta[++top] = s[front], idx[top] = front++;107 st.update(st.root, 1, n, idx[top], 127);108 putchar(sta[top--]);109 } else {110 putchar(sta[top--]);111 }112 }113 }114 115 int main() {116 init();117 solve();118 return 0;119 }
不过这道题似乎有更简单的实现方法，时间复杂度为O(nk)，其中k为字符集大小，这里为26
Educational Codeforces Round 19
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。