百度松果菁英班–oj赛（第四次）
一、前K小数
**题目：**小码哥现在手上有两个长度为n的数列a，b，(1≤i, j≤n)通过ai + bj可以构造出n * n个数，求构造出的数中前k小的数。
/** 输入格式:第一行2个数n, k; 第二行n个数，表示数列a; 第三行n个数，表示数列b。 输出格式:从小到大输出前k小的数。 样例1 输入：3 3 2 6 6 1 4 8 输出：3 6 7 备注 其中:1≤n ≤1e4，1≤k≤n*n≤1e4， 1≤ai，bj ≤1e6 */ #include<bits/stdc++.h> using namespace std; const int N = 1e8 + 5; int a[N]; int b[N]; struct Node{ int ida, idb, num; bool operator > (const Node &a) const{ return num > a.num; } } node; priority_queue<Node, vector<Node>, greater<Node>> q;//小根堆 int main(){ int n, k; cin >> n >> k; for(int i = 0; i < n; i++){ cin >> a[i]; } for(int i = 0; i < n; i++){ cin >> b[i]; } sort(a, a + n);//将数列a从小到大排序 sort(b, b + n);//将数列b从小到大排序 //将a数列的值与b的第一个相加入堆 for(int i = 0; i < n; i++){ q.push({i, 0, a[i] + b[0]}); } while(k--){ node = q.top();//此时堆的最前面是最小的 q.pop();//将其从堆中去除 cout << node.num << " "; //再将b的下一个与a的第一个相加 node.num = a[node.ida] + b[++node.idb]; q.push(node);//入堆得到最小堆 } return 0; }
二、前k小数（进阶）
**题目：**给你n个长度为m的已知数列，你一次可以从每个数列中选出一个元素，共n个数，将这n个数的和，放入α数组中，穷举所有的选数可能，并且都放入α数组中。
小码哥请你计算a数列中前k小数是多少?
/** 输入格式:输入n，m，k ; 接下来n行，每一行m个数，空格分隔，一行表示一个数列，共n行。 输出格式:从小到大输出前k 小的数。 样例1 输入：2 2 2 1 2 1 2 输出：2 3 备注 其中:1<n ≤200,1 ≤k≤m≤200 */ #include<bits/stdc++.h> using namespace std; const int N = 4e5 + 5; int rec[400][400], n, m, k; vector<int> a; vector<int> u, v; int main(){ cin >> n >> m >> k; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &rec[i][j]); } } for (int i = 1; i <= m; i++){ u.push_back(rec[1][i]); } for (int i = 2; i <= n; i++) { sort(rec[i] + 1, rec[i] + 1 + m); for (int j = 1; j <= k; j++){ v.push_back(rec[i][j]); } for (int x: u) { for (int y: v) { a.push_back(x + y); } } sort(a.begin(), a.end()); while (u.size() != 0){ u.pop_back(); } while (v.size() != 0){ v.pop_back(); } for (int i = 0; i < k; i++){ u.push_back(a[i]); } while (a.size() != 0){ a.pop_back(); } } for (int i = 0; i < k; i++) { printf("%d ", u[i]); } return 0; }
三、黑客小码哥
**题目：**小码哥是一名黑客，他最近刚彩票中奖，由于还没兑换，小码哥十分担心彩票被盗（小码哥过分谨慎了)，他想为自己的保险箱设新的密码，顺便他想让你测试编码。
现有两种编码方式:
- 对于已知字符串中的某种字符，全部变成另一种字符。如里面出现的A全部换成B;
- 对于当前字符串，打乱字符顺序。
先给你一个加密后的字符串和加密前的字符串，判断加密前的字符串是否能得到加密后的字符串。字符串中字符均为大写字母。
/** 输入格式:第一行加密后的字符串; 第二行加密前的字符串; 有多组数据输入。 输出格式:输出YES或NO。 样例1 输入：JWPUDJSTVP VICTORIOUS MAMA ROME HAHA HEHE AAA AAA NEERCISTHEBEST SECRETMESSAGES 输出：YES NO YES YES NO 备注 所有字符串长度不超过100。 */ #include<bits/stdc++.h> using namespace std; const int LETTER = 26; // 判断两个字符串是否有可能是经过指定加密算法处理前后的两串 bool isSamePossiblely(string str1, string str2){ // 长度不同就一定不是 int strlen = str1.length(); if(strlen != str2.length()){ return false; } // 将数组全部初始化为0 int ary1[LETTER]={0}, ary2[LETTER]={0}; // 先统计各字符串中不同字符的出现次数 for(int i = 0; i < strlen; i++){ ary1[str1[i]-'A']++; ary2[str2[i]-'A']++; } // 消除字符间的顺序差异 sort(ary1, ary1 + LETTER); sort(ary2, ary2 + LETTER); // 判断是否可能是变换前后的两字符串 for(int i = 0; i < LETTER; i++){ if(ary1[i] != ary2[i]){ return false; } } return true; } int main(){ string str1, str2; while(cin >> str1 >> str2) { if(isSamePossiblely(str1, str2)){ cout << "YES" << endl; }else{ cout << "NO" << endl; } } return 0; }
四、来给单词分类
**题目：**现有如下单词分类原则:两个单词可以分为一类当且仅当组成这两个单词的各个字母的数量均相等。
现有n个单词均由大写字母组成，每个单词长度小于等于100。求单词被分为几类。
/** 输入格式:第一行输入单词个数n ;以下n行每行一个单词。 输出格式:—个整数表示类数。 样例1 输入：3 AABAC CBAAA AAABB 输出：2 备注 对于70%的数据满足n≤100 ; 对于100%的数据满足n≤10000。 */ #include<bits/stdc++.h> using namespace std; int n, ans; string s; map<string, int> mp; int main(){ cin >> n; for(int i = 1; i <= n; i++){ cin >> s; //给输入的单词排序 sort(s.begin(), s.end()); //如果value值存在则返回1，不存在则返回0 if(!mp[s]){ ans++; mp[s] = 1; } } cout << ans; return 0; }
五、一元多项式的加法
**题目：**小码哥给出两个一元多项式LA和LB，请你将这两个一元多项式相加，得到新的一元多项式Lc。
如样例:
- LA =
1 - 10x^6 + 2x^8 + 7x^14 - LB =
- x^4 + 10x^6 - 3x^10 + 8x^14 + 4x^18 - LC = LA + LB =
1- x^4 + 2x^8 - 3x^10+15x^14 +4x^18
/** 输入格式:第一行两个整数n和m，分别表示LA和LB的项数;接下来n行，每行输入LA的每一项的信息，两个整数分别表示该项的系数coef和次数earpn，输入保证次数递增;接下来m行，每行输入LB 的每一项的信息，两个整数分别表示该项的系数coef和次数earpn，输入保证次数递增。 输出格式:输出k行，k为Lc的项数，每行输出Lc的每一项的信息，两个整数分别表示该项的系数coef和次数expn，输出按次数递增。 样例1 输入：4 5 1 0 -10 6 2 8 7 14 -1 4 10 6 -3 10 8 14 4 18 输出：1 0 -1 4 2 8 -3 10 15 14 4 18 备注 对于100%的数据:0≤n, m ≤ 1000000，一1000 ≤coef ≤ 1000，一1000000000 ≤expn ≤ 1000000000 。 */ #include<bits/stdc++.h> #define ll long long using namespace std; const int N =2e6 + 5; struct NODE { ll nex, coef, expn;//下一个节点 系数 指数 }node[N]; int n, m, head, tail, pos; ll coefA[N], expnA[N], coefB[N], expnB[N]; void insert(int curr,ll val1,ll val2){ node[++pos].coef = val1;//给节点赋值 node[pos].expn = val2; node[pos].nex = node[curr].nex;//将节点插入到curr的后面 node[curr].nex = pos; if (!node[pos].nex){//到链表尾部为空 tail = pos;//将当前节点赋值为尾节点 } } int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++){ scanf("%lld%lld", &coefA[i], &expnA[i]); } for (int i = 1; i <= m; i++){ scanf("%lld%lld", &coefB[i], &expnB[i]); } int l = 1, r = 1; while (l <= n && r <= m) { if (expnA[l] == expnB[r]) {//A和B的指数相等 insert(tail, coefA[l] + coefB[r], expnA[l]); l++; r++; }else{ if (expnA[l] < expnB[r]) {//A的指数小，插入A insert(tail, coefA[l], expnA[l]); l++; }else{//B的指数小，插入B insert(tail, coefB[r], expnB[r]); r++; } } } while (l <= n){//如B插完，则将剩余的A插入 insert(tail, coefA[l], expnA[l]); l++; } while (r <= m){//如A插完，则将剩余的B插入 insert(tail, coefB[r], expnB[r]); r++; } for (int i = node[head].nex; i != 0; i = node[i].nex){ if (node[i].coef != 0){ printf("%lld %lld\n", node[i].coef, node[i].expn); } } return 0; }
六、队列安排
**题目：**一个学校里老师要将班上N个同学排成一列，同学被编号为1～N，他采取如下的方法:
- 先将1号同学安排进队列，这时队列中只有他一个人;
- 2-N号同学依次入列，编号为i的同学入列方式为:老师指定编号为i的同学站在编号为1～(i一 1)中某位同学(即之前已经入列的同学）的左边或右边;
- 从队列中去掉 M(M<N)个同学，其他同学位置顺序不变。
在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。
/** 输入格式:第1行为一个正整数N，表示了有N个同学; 第2―N行，第i行包含两个整数k,p，其中k为小于i的正整数, p为0或者1。若p为0，则表示将i号同学插入到k号同学的左边，p为1则表示插入到右边; 第N＋1行为一个正整数M，表示去掉的同学数目; 接下来M行，每行一个正整数x，表示将x号同学从队列中移去，如果x号同学已经不在队列中则忽略这—条指令。 输出格式:1行，包含最多N个由空格隔开的正整数，表示了队列从左到右所有同学的编号。 样例1 输入:4 1 0 2 1 1 0 2 3 3 输出：2 4 1 备注 样例解释: 将同学2插入至同学1左边，此时队列为:21; 将同学3插入至同学2右边，此时队列为:231; 将同学4插入至同学1左边，此时队列为:2341; 将同学3从队列中移出，此时队列为:241; 同学3已经不在队列中，忽略最后一条指令 最终队列:241 数据范围:N，M ≤100000 。 */ #include<bits/stdc++.h> using namespace std; const int N = 1e6+10; struct line{ int pr, ne;//前一个，当前节点 bool mk;//判断是否已经删除 }a[N]; int f[N]; int n , m; int ans = 0; int main(){ cin >> n; int i , j; int k , p; a[0].ne = 1;//头节点 a[0].pr = 0;//链头为null a[1].mk = 1;//未删除 a[1].pr = 0; for(i = 2 ; i <= n ; i++){ cin >> k >> p; a[i].mk = 1; if(p == 0){//插到左边 a[a[k].pr].ne = i; a[i].pr = a[k].pr; a[k].pr = i; a[i].ne = k; }else{//插到右边 a[a[k].ne].pr = i; a[i].pr = k; a[i].ne = a[k].ne; a[k].ne = i; } } cin >> m; int x; for(i = 1 ; i <= m ; i++){ cin >> x; if(!a[x].mk){//当mk=0时表示已经删除 continue; } a[x].mk = 0; a[a[x].pr].ne = a[x].ne; a[a[x].ne].pr = a[x].pr; } printf("%d",a[0].ne); int now = a[0].ne; now = a[now].ne; while(now){ printf(" %d",now); now = a[now].ne; } cout << endl; return 0; }
七、供水管道
**题目：**在n个城市之间原本要规划修建许多条下水管道，管理人员发现这些管道会形成一条回路，而下水道只要将城市联通即可，所以回路会加大施工的成本。所以希望你来帮忙找出多余的管道来进行优化。当然管道和管道之间是有区别的，比如用sij来表示i到j的管道管理费用，sij越小则表示该管道管理费用越低。能否去除一些管线，使得总管理成本最低。求出最低的管理成本(不存在自身与自身成为回路的管道）。
/** 输入格式:第一行有两个数n和k表示城市数量和管道数量; 接下来k行，每行都有三个数i，j，c表示城市i和城市j之间的管道成本为c 输出格式:一个正整数，最低管理成本。 样例1 输入：3 3 1 2 3 1 3 5 2 3 8 输出：8 备注 其中:1 <n, k <100 */ #include <bits/stdc++.h> using namespace std; const int N = 1e2 + 7; struct NODE{ int i, j, c; bool operator<(const NODE &t)const { return c < t.c;//升序 } }p[N]; int fa[N], n, k, ans; void init(){//数据初始化 for (int i = 1; i < N; i++){ fa[i] = i; } } int find(int x){//查找 return x == fa[x] ? x: (fa[x] = find(fa[x])); } void mer(int x, int y) {//合并 x = find(x); y = find(y); if (x != y){ fa[x] = y; } } int main(){ init(); cin >> n >> k; for (int i = 1; i <= k; i++){ cin >> p[i].i >> p[i].j >> p[i].c; } sort(p + 1, p + 1 + k);//将管道按照成本升序 for (int i = 1; i <= k; i++){ if (find(p[i].i) != find(p[i].j)){ ans += p[i].c; mer(p[i].i, p[i].j); } } cout << ans; return 0; }
八、快排变形
**题目：**有n个数，问如果通过每次交换邻项的两个数来使数组中的元素变为升序排列。
eg : 9 8 7 6 5，
变为升序:
5 6 7 8 9。
需要10次邻项交换。
/** 输入格式:第一行输入一个整数n ，表示序列长度; 第二行输入n个数。 输出格式:输出一个整数，表示最少的交换次数。 样例1 输入：5 9 8 7 6 5 输出：10 备注 其中:1<n ≤200000 */ #include <bits/stdc++.h> using namespace std; const int N=2e5 +7; int a[N], b[N], c[N], n; long long ans; //树状数组模板 int lowbit(int x){ return x &-x; } void add(int i, int x){ for (; i <= n; i += lowbit(i)) c[i] += x; } int sum(int i){ int ans = 0; for (; i > 0; i -= lowbit(i)) ans += c[i]; return ans; } bool cmp(const int x, const int y){ if (b[x] == b[y]){ return x > y; } return b[x] > b[y]; } int main(){ cin >> n; for (int i = 1; i <= n; i++) { cin >> b[i]; a[i] = i; } sort(a + 1, a + n + 1, cmp); for (int i = 1; i <= n; i++){ add(a[i], 1); ans += sum(a[i] - 1); } cout << ans <<endl; return 0; }
九、逆序
**题目：**给一个长度为n的排列p，找一个元素，使得从排列中取出这个元素以后排列的records最多。一个record是一个元素ai满足:对于每个正整数1≤j <i , ai > aj 。
/** 输入格式:第一行为n ;第二行为排列p 。 输出格式:一个整数即笞菜。 样例1 输入：5 5 1 2 3 4 输出：5 备注 其中:1 ≤n, a[i]≤1e5 当答案不唯一时，输出较小的数。如: (1) 3 4 5 1 2 (2) 3 4 5 2 1 上面两种情况，均输出1。 */ #include <bits/stdc++.h> using namespace std; const int N=1e5 + 7; int n; int c[N],chg [N]; int lowbit(int x){ return x & -x; } void add(int x){ for (;x < N;x += lowbit(x)){ c[x]++; } } int sum(int x){ int ret = 0; for (;x> 0;x -= lowbit(x)){ ret += c[x]; } return ret; } int main(){ cin >> n; int x=0,maxx =0; for (int i=1;i<=n;i++){ cin >>x; maxx = max(maxx,x); int cnt = sum(x); if (cnt ==i-1){ chg [maxx]--; } else if (cnt ==i-2){ chg [maxx]++; } add (x); } int ans = 1; for (int i = 1;i <= n;i++){ if (chg[i] > chg[ans]){ ans = i; } } cout <<ans <<endl; return 0; }
十、线段树
**题目：**线段树模板题。已知一个数列，你需要进行下面两种操作:将某区间每一个数加上 k，求出某区间每一个数的和。
/** 输入格式:第一行包含两个整数n,m ( 5 ≤n, m ≤10%),分别表示该数列数字的个数和操作的总个数; 第二行包含n个用空格分隔的整数(0一10°)，其中第i个数字表示数列第i项的初始值; 接下来m行每行包含3或4个整数，表示一个操作，具体如下:1 x y k :将区间[x, y]内每个数加上k。 2 x y: 输出区间[x, y]内的数的和。其中: 1≤≤y ≤n,0 ≤k ≤105。 输出格式:输出包含若干行整数，即为所有操作2的结果。 样例1 输入：5 5 1 5 4 2 3 2 2 4 1 2 3 2 2 3 4 1 1 5 1 2 1 4 输出：11 8 20 备注 线段树模板 */ #include<bits/stdc++.h> #define ll long long using namespace std; const ll N = 1e5 + 5; struct NODE{ ll l, r, val, lz; }tree[4 * N]; ll a[N]; void build(ll p, ll l, ll r){ tree[p].l = l; tree[p].r = r; if(l == r){ tree[p].val = a[l]; return; } ll mid = l + ((r - l) >> 1); build(p * 2, l, mid); build(p * 2 + 1, mid + 1, r); tree[p].val = tree[p * 2].val + tree[p * 2 + 1].val; } void lazy(ll p, ll v){ ll s = tree[p].l; ll t = tree[p].r; tree[p].val += (t - s + 1) * v; tree[p].lz += v; } void pushdown(ll p){ lazy(2 * p, tree[p].lz); lazy(2 * p + 1, tree[p].lz); tree[p].lz = 0; } void update(ll l, ll r, ll c, ll p){ ll s = tree[p].l; ll t = tree[p].r; if(l <= s && t <= r){ return lazy(p, c); } if(tree[p].lz && s != t){ pushdown(p); } ll mid = s + ((t - s) >> 1); if(l <= mid){ update(l, r, c, p * 2); } if(r > mid){ update(l, r, c, p * 2 + 1); } tree[p].val = tree[p * 2].val + tree[p * 2 + 1].val; } ll query(ll l, ll r, ll p){ ll s = tree[p].l; ll t = tree[p].r; if(l <= s && t <= r){ return tree[p].val; } if(tree[p].lz){ pushdown(p); } ll mid = s + ((t - s) >> 1); ll sum = 0; if(l <= mid){ sum = query(l, r, p * 2); } if(r > mid){ sum += query(l, r, p * 2 + 1); } return sum; } int main(){ ll n, m; cin >> n >> m; for(int i = 1; i <= n; i++){ cin >> a[i]; } build(1, 1, n); while(m--){ ll op, x, y, k; cin >> op; if(op == 1){ cin >> x >> y >> k; update(x, y, k, 1); }else{ cin >> x >> y; cout << query(x, y, 1) << endl; } } return 0; }
记录每一个学习瞬间
