公司做网站是做什么账务处理wordpress如何修改页头

当前位置： 首页 > news >正文

公司做网站是做什么账务处理,wordpress如何修改页头,亚马逊网站建设进度计划,wordpress 信息发布文章目录 一、概念二、OJ练习2.1 区间选点2.2 区间合并2.3 区间2.4 合并果子2.5 排队接水2.6 货仓选址2.7 防晒2.8 畜栏预定2.9 雷达设备2.10 国王游戏2.11 耍杂技的牛2.12 给树染色2.13 任务2.14 能量石 三、总结 一、概念 贪心是一种在每次决策时采取当前意义下最优策略的算… 文章目录 一、概念二、OJ练习2.1 区间选点2.2 区间合并2.3 区间2.4 合并果子2.5 排队接水2.6 货仓选址2.7 防晒2.8 畜栏预定2.9 雷达设备2.10 国王游戏2.11 耍杂技的牛2.12 给树染色2.13 任务2.14 能量石 三、总结 一、概念 贪心是一种在每次决策时采取当前意义下最优策略的算法因此使用贪心法要求问题的整体最优性可以由局部最优性导出。贪心算法的正确性需要证明常见的证明手段有: 微扰(邻项交换) 证明在任意局面下,任何对局部最优策略的微小改变都会造成整体结果变差。经常用于以“排序”为贪心策略的证明。 范围缩放 证明任何对局部最优策略作用范围的扩展都不会造成整体结果变差 决策包容性 证明在任意局面下,作出局部最优决策以后,在问题状态空间中的可达集合包含了作出其他任何决策后的可达集合。换言之,这个局部最优策略提供的可能性包含其他所有策略提供的可能性。 反证法数学归纳法 贪心算法在算法体系中较为特殊这里通过几道例题来体会贪心算法的应用。 二、OJ练习 2.1 区间选点 区间选点 - 45D - Codeforces 题目保证了有解我们该如何选出可行解呢 我们考虑把区间按照右端点升序排序然后遍历所有区间对于每个区间选取区间内没有被选取的最左端点 如何证明正确性——反证法 假设按照上述策略出现某个区间无点可选该区间为[l, r]说明有r - l 1个右端点不小于l不超过r的区间选择了[l, r]内的r - l 1个点 它们选择[l, r]内的点说明它们在[0, l - 1]的部分都被选完了否则按照靠左原则应该选取[0, l - 1]的点那么[l, r]内就存在r - l 2个区间的右端点此时原问题无解与题目条件矛盾故策略正确。 对于区间问题通用操作是按照某端点排序在处理区间问题没有头绪的时候可以试着排序来寻找突破口。 n int(input())lines []for _ in range(n):a, b map(int, input().split())lines.append((a, b, _)) lines.sort(keylambda x: x[1])st set() ans [0] * n for l, r, idx in lines:for i in range(l, r 1):if not (i in st):st.add(i)ans[idx] ibreakfor x in ans:print(x, end ) 2.2 区间合并 P2082 区间覆盖加强版 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 即求区间合并后的长度 那么我们将区间按照左端点升序排序然后顺序遍历区间 记录当前合并区间的左端点L右端点R对于遍历到的区间[l, r] 如果l R那么说明和前面的区间不相交我们累加前面区间的长度后更新当前合并区间为[l, r] 否则更新R max(R, r) 证明很简单就是假设存在两个可以合并的区间没有合并然后反证推出矛盾即可不再赘述。 n int(input()) lines [tuple(map(int, input().split())) for _ in range(n)] lines.sort(keylambda x: x[0])res 0 L, R 0, -1 for x, y in lines:if x R:R max(R, y)else:res R - L 1L, R x, y print(res (R - L 1))2.3 区间 [P2434 SDOI2005] 区间 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 和上一道题做法一样是在上一道题目的基础上加上了输出具体方案 我们只需开一个数组表示当前的不合并区间数组如果当前区间和最后一个不相交就加入数组否则就维护最后一个区间的最右端点 n int(input()) lines [tuple(map(int, input().split())) for _ in range(n)] lines.sort(keylambda x: x[0])res 0 ans [lines[0]] for x, y in lines:if x ans[-1][1]:ans-1else:ans.append((x, y)) for x, y in ans:print(x, y)2.4 合并果子

1. 合并果子 - AcWing题库 很明显的贪心思路每次区所有堆中最小的两堆合并即可 为什么是正确的呢 我们合并的过程其实可以构造出一棵树这棵树和Huffman树其实是等价的。 上图中蓝色代表初始的果子堆每个结点都是由两个孩子合并而来 初始蓝色结点的贡献为深度 乘 结点权值 我们只需证明按照贪心策略得到的树中蓝色结点的权值 * 深度之和最小即可 引理权值最小的两个点的深度一定最深且互为兄弟 证明如果不是两个点中至少有一个可以和最后一层的某个权值不小于自身的结点交换那么两个结点可以交换到最后一层并且成为兄弟那么 蓝色结点的权值 * 深度之和至少不会变大甚至变小故得证 那么最优解的值等价于 权值最小的两个点的值相加 加上 两个点合并后与剩余的n - 2个点构造出的最优树的值 同样的我们如此迭代下去可以构造出一棵最优解树故得证。 import heapq n int(input()) a list(map(int, input().split())) heapq.heapify(a) res 0 while len(a) 1:x heapq.heappop(a)y heapq.heappop(a)res x yheapq.heappush(a, x y) print(res)2.5 排队接水 P1223 排队接水 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 每个人接的越早它的时间就会越多人忍受 所以我们让接的少的人优先接水即可 证明也很简单同样反证然后总可以按照贪心策略构造出不比最优解差甚至更优的解 n int(input()) a [(int(x), _ 1) for _, x in enumerate(input().split())] a.sort() s 0 for i, (x, idx) in enumerate(a):s x * (n - i - 1)print(idx, end ) print() print(%.2f % (s / n))2.6 货仓选址
2. 货仓选址 - AcWing题库 很经典的中位数问题就是数轴上找到一个点y使得Σ|x - y|最小 上图其实已经很明白了当y选在两个数里面的差绝对值和总小于等于在两个数外面的差绝对值 那么我们剥洋葱似的一层一层往里钻就会落到中位数处 n int(input()) a list(map(int, input().split())) a.sort()mid a[len(a) // 2]print(sum(abs(x - mid) for x in a))2.7 防晒
3. 防晒 - AcWing题库 又是区间问题不过这道题按照左右端点哪个排都能做其实有点让每个资源发挥其最大作用的意思 怎么思考呢我们把牛牛的区间按照右端点排序然后顺序遍历牛牛每次选取在自己区间内最小的那个防晒霜 如何证明我们这样得到的一定是最优解 我们可以证明对任意最优解按照贪心策略调整不会使得解变差从而得到一个最优解我们也可以用范围缩放来证明即我们的局部最优贪心策略对整体影响最小。 我们已经按照右端点排序那么对于当前枚举奶牛的可用防晒霜xySPF[x] SPF[y]只有如下三种情况 后面奶牛xy都能用后面奶牛只能用y后面奶牛xy都不能用 我们发现我们选择x对后面奶牛影响最小所以贪心策略正确。 #include iostream #include cstring #include algorithm #include map using namespace std; #define x first #define y second typedef pairint, int PII; const int N 2510;int n, m; PII w[N]; mapint, int mp;int main(){cin n m;for(int i 0; i n; i ) cin w[i].x w[i].y;for(int i 0, a, b; i m; i ) cin a b, mp[a] b;sort(w, w n, {return a.y b.y;});int res 0;for(int i 0; i n; i ){ //cout w[i].x w[i].y endl;auto it mp.lower_bound(w[i].x);if (it ! mp.end() it - first w[i].y) {it - second –, res ;if(! it - second) mp.erase(it);}}cout res;return 0; } 2.8 畜栏预定
4. 畜栏预定 - AcWing题库 我们将牛按开始时间升序排序然后枚举牛 如果对于当前牛有可以安排的畜栏畜栏内最后一头牛结束时间不晚于当前牛的开始时间那么我们就安排进去 如果没有就新开一个畜栏 上述做法的正确性 反证法我们存在不同于上述策略的方案为更优解只需m个畜栏那么我们上述策略建立第m 1个畜栏时必然有m个畜栏的结束时间都大于当前牛的开始时间而由于我们按照开始时间升序故m个畜栏的最后一头牛都和当前牛区间有交集等价于m 1头牛两两有交集所以我们至少需要m 1个畜栏矛盾故得证。 #include iostream #include cstring #include algorithm #include queue using namespace std; #define x first #define y second const int N 5e4 10; typedef pairint, int PII; typedef pairPII, int PIII; PIII lines[N]; int n, id[N]; priority_queuePII, vectorPII, greaterPII pq; int main(){cin n;for(int i 0, a, b; i n; i ) cin a b, lines[i] { {a, b}, i };sort(lines, lines n);for(int i 0; i n; i ){if(pq.empty() || pq.top().x lines[i].x.x)pq.emplace(lines[i].x.y, id[lines[i].y] pq.size() 1);else{PII t pq.top();pq.pop();t.x lines[i].x.y;pq.emplace(t);id[lines[i].y] t.y;}}cout pq.size() endl;for(int i 0; i n; i ) cout id[i] endl;return 0; }2.9 雷达设备
5. 雷达设备 - AcWing题库 对于每个小岛而言可以覆盖它的点对应x轴上一个区间那么每个小岛就能够有一个可监测区间 我们只需选择尽可能少的点使得每个区间都被覆盖到即可这就转化为了区间选点问题 我们将区间按照右端点排序然后如果当前区间左端点小于覆盖区间的右端点说明该区间可以被前面覆盖区间的点 否则我们就开一个新区间所选的点为当前区间的右端点 from math import sqrt n, d map(int, input().split()) eps 1e-6 lines [] for _ in range(n):x, y map(int, input().split())if y - d eps:print(-1)exit(0)dx sqrt(d * d - y * y)lines.append((x - dx, x dx))lines.sort(keylambda x: x[1]) ed -2000 res 0 for l, r in lines:if l - ed eps:res 1ed r print(res)2.10 国王游戏
6. 国王游戏 - AcWing题库 本题贪心策略为将大臣按照左手乘右手升序排序此时的最大值最小 证明策略临项交换微扰 我们假设最优解不是按照上述策略得到那么一定存在a[i] * b[i] a[i 1] * b[i 1] 交换二者不影响其他大臣的收益 我们对比交换前后二者的收益 交换前i人premul(i - 1) / bi i 1人premul(i - 1) * ai / bi1 交换后i人premul(i - 1) / bi1 i 1人premul(i - 1) * ai1 / bi 四个数同乘 bi*bi1/premul(i - 1): 交换前i人bi1 i 1人ai bi 交换后i人bi i 1人ai1 bi1 由于ai * bi ai1*bi1ai bi bi则交换后整体的最大值没有变大甚至变小 那么我们交换所有逆序对可以得到不比最优解差的解故我们的贪心策略正确。 cpp要手写高精度 #include iostream #include cstring #include vector #include algorithm using namespace std; typedef pairint, int PII; const int N 1005;vectorint mul(vectorint a, int x){int n a.size(), t 0;vectorint ret;for(int i 0; i n; i ){t a[i] * x;ret.push_back(t % 10);t / 10;}while(t) ret.push_back(t % 10), t / 10;return ret; }vectorint div(vectorint a, int x){int n a.size(), t 0;vectorint ret;for(int i n - 1; ~i; i –){t t * 10 a[i];ret.push_back(t / x);t % x;}reverse(ret.begin(), ret.end());while(ret.size() !ret.back()) ret.pop_back();return ret; } vectorint ma(const vectorint a, const vectorint b){if(a.size() b.size()) return a;if(a.size() b.size()) return b;if(vectorint(a.rbegin(), a.rend()) vectorint(b.rbegin(), b.rend())) return a;return b; } int n; PII w[N];int main(){cin n, n ;for(int i 0, a, b; i n; i ) cin a b, w[i] { a, b };sort(w 1, w n, {return a.first * a.second b.first * b.second;});vectorint cur(1, 1), res(1, 0);for(int i 0; i n; i ){ if(i)res ma(res, div(cur, w[i].second));cur mul(cur, w[i].first);/for(int x : vectorint(cur.rbegin(), cur.rend()))cout x;puts();/} for(int x : vectorint(res.rbegin(), res.rend()))cout x;return 0; }不想写高精度就用python3 n int(input()) n 1 w [tuple(map(int, input().split())) for _ in range(n)] cur ,res w[0][0], 0 for a, b in sorted(w[1::], keylambda x:x[0]*x[1]):res max(res, cur // b)cur * a print(res)2.11 耍杂技的牛
7. 耍杂技的牛 - AcWing题库 和上一题很像这题按照w s升序排序 和上一题同样的证明思路不再赘述 n int(input()) ws [tuple(map(int, input().split())) for _ in range(n)] pre 0 ans -1e18 for w, s in sorted(ws, keylambda x:x[0]x[1]):ans max(ans, pre - s)pre w print(ans)2.12 给树染色
8. 给树染色 - AcWing题库 错误的贪心从根结点开始扩展每次取当前最小权值的结点 很容易举出反例可以自己试一下。 我们可以确定的事情是当前除去根节点的最大权值结点会在其父节点被染色后立即被染色。 那么我们考虑当前最大结点x父节点y和任意结点z染色顺序无非 xyz代价为x 2y 3z zxy代价为z 2x 3y 二者做差有2z - (x y)可见当z大于xy的平均值时才会先染xy 那么我们在考虑当前树中剩余结点时不妨将xy当成一个结点其权值为平均权值然后就有了做法 选择当前树中的最大权值进行染色由于它和父亲染色顺序为一前一后所以染色后合并到父亲结点后面 我们合并n - 1次就只剩下一个结点此时整棵树的染色顺序也就知道了 具体实现时由于我们并不关心具体染色方案所以为了简便我们可以在合并时维护答案 考虑x合并到y上由于要先染色y所以x的权值要被加上y的sz次sz为y结点的大小 可以用并查集堆优化到O(nlogn)不过这个数据量没必要重要的还是这道题的思想 #include iostream #include algorithm #include cstring using namespace std;const int N 1005; const double eps 1e-6; struct node{int fa, sz, v;double avg; }nodes[N]; int n, root, res;int nxt() {double avg 0;int res -1;for (int i 1; i n; i )if (i ! root nodes[i].avg avg){avg nodes[i].avg;res i;}return res; }int main(){cin n root;for(int i 1, v; i n; i ){cin v, res v;nodes[i] { -1, 1, v, v };}for(int i 1, a, b; i n; i ){cin a b;nodes[b].fa a;}for(int i 1; i n; i ){int t nxt(), fa nodes[t].fa;res nodes[fa].sz * nodes[t].v;nodes[t].avg -1;for(int j 1; j n; j )if(nodes[j].fa t) nodes[j].fa fa;nodes[fa].sz nodes[t].sz, nodes[fa].v nodes[t].v, nodes[fa].avg (double)nodes[fa].v / nodes[fa].sz;}cout res;return 0; }2.13 任务
9. 任务 - AcWing题库 我们发现式子中x对于利润占主导所以按x从大到小来进行考虑每个任务。对于每个任务从时间满足的机器中选择等级足够且最小的那个。 具体流程如下 按照x对任务和机器排序按x从大到小遍历任务把时间充足的机器放入集合如果集合中存在等级足够的机器那么选择等级最小的那个再处理下一个任务时集合中的机器的时间都是足够的我们只需考虑等级 时间复杂度O(nlogn mlogn) #include bits/stdc.h using i64 long long; using PII std::pairint, int; const int N 1e5 10, M 1e5 10; int n, m; PII a[N], b[M]; int main(){std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);while (std::cin n m){for(int i 0; i n; i ) std::cin a[i].first a[i].second;for(int i 0; i m; i ) std::cin b[i].first b[i].second;std::sort(a, a n), std::sort(b, b m);std::multisetint st;i64 cnt 0, res 0;for(int i m - 1, j n - 1; ~i; i –){while(~j a[j].first b[i].first)st.insert(a[j –].second);auto it st.lower_bound(b[i].second);if(it ! st.end()){cnt ;res 500 * b[i].first 2 * b[i].second;st.erase(it);}}std::cout cnt res \n;}return 0; }2.14 能量石
10. 能量石 - AcWing题库 01背包 临项交换 先暴力考虑所有情况即全排列中依次求01背包 那么最优解是否存在某种特性呢或者说我们需要考虑的情况的范围能否缩小 我们考虑最优解相邻两个能量石s[i], s[i 1] 二者的收益为e’[i] e’[i 1] - s[i] * l[i 1] 交换次序e’[i] e’[i 1] - s[i 1] * l[i] 由于是最优解所以交换前的收益不小于交换后的收益s[i] * l[i 1] s[i 1] * l[i] 那么说明最优解满足两两之间s[i] * l[i 1] s[i 1] * l[i] 所以我们将能量石按照s[i] / l[i]升序排序然后跑01背包即可 #include bits/stdc.h #define sc scanf using i64 long long; const int N 105, M 1e4 10; struct node{int s, e, l;bool operator(const node x) const{return s * x.l x.s * l;} }nodes[N];int main(){int _ 1;std::cin _;for(int t 1, n, m; t _; t ){std::cin n;m 0;for(int i 0, a, b, c; i n; i ) std::cin a b c, nodes[i] { a, b, c }, m a;std::sort(nodes, nodes n);std::vectori64 f(m 1, -1e8);f[0] 0;for(int i 0; i n; i ){auto [s, e, l] nodes[i];for(int j m; j s; j –){f[j] std::max(f[j], f[j - s] e - (j - s) * l);}}printf(Case #%d: %lld\n, t, *std::max_element(f.begin(), f.end()));}return 0; }三、总结 很想从上面的问题中提取出某些东西但是发现没有套路可言只是遇到贪心问题时有了几个贪心的方向区间类试着按端点排序贪心构造临项交换等等但具体还得多做题。