天道酬勤,学无止境

Codeforces Round #673 (Div. 2)

A. Copy-paste

签到题

  • 题设:给一串长度为n,值可变的数组,和最大限度k,每次可选择[1 , n]范围内任意不相等的两序号(i,j),使 a[ j ] = a[ j ] + a[ i ],当数组中最大值会超过k(a[max]>k)时不可继续操作,问最多可操作的次数。
  • 思路:用小顶堆的优先队列存储所有值,先取出最小值并将其弹出,再将第二大的值加到最小值上,将求和后的该值再插入优先队列,重复操作至最小值会超过k时停止。
    ——AC代码

B. Two Arrays

思维题

  • 题设:给定一串长度为n数组,和不幸值“T”,要求将此数组拆分成两个子数组,并希望拆分后,对于属于同一数组两个元素,相加等于T的情况尽可能少,要求将所有元素拆分的情况输出,输出值为1的放在黑色数组中,输出值为0则放在白色数组中。
  • 思路:对T进行情况考虑,先取一int型的值mid=T/2。若T为奇数,将所有小于mid的元素放在黑色数字中,大于等于mid的放在另一白色数组中;若T为偶数,则等于mid的元素要尽可能均分到两个数组中,则只需在奇数情况下,将所有等于mid的值交错放置。
    ——AC代码

受限制的 HTML

  • 允许的HTML标签:<a href hreflang> <em> <strong> <cite> <blockquote cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <h5 id> <h6 id>
  • 自动断行和分段。
  • 网页和电子邮件地址自动转换为链接。

相关推荐
  • Codeforces Round #673 (Div. 2) B
    B. Two Arrays 我作为一个菜鸡,昨天居然把B题给做了出来,泪目QAQ. 于是就写个博客纪念一下。 题目链接:https://codeforces.ml/contest/1417/problem/B 题意: 首先定义:f(x)是在数组x取两个数组成数对(x[i], x[j]) 的个数,数对因满足 i ≠ j 且 x[i] + x[j] = T 题目要求:将一个数组分成a, b两部分,使得f(a) + f(b) 最小。 我的思路: 为了方便表述,假设0, 1数组以a, b数组代替。以 T 2 \frac{T}{2} 2T​ 为分界线,大于 T 2 \frac{T}{2} 2T​ 的数放到b, 反之放到a中, 这样就可以使f(a) 和 f(b)最小。但还会碰到一种情况, 数组中存在多个 T 2 \frac{T}{2} 2T​ ,为了保证结果最小,我们就可以将 这些数平分到a, b两个数组中。 下面是代码 #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; typedef long long ll; int a[N]; //a数组存放答案 ll t, n, k; int main() { cin >> t; while(t --) { int cnt = 0; cin >> n >> k; /
  • Codeforces Round #673 (Div. 2)(A-D)题解
    A. Copy-paste(思维) B. Two Arrays(思维+贪心分配) C. k-Amazing Numbers(思维前缀最小值+枚举相同数距离) D. Make Them Equal(思维+构造) 来源:https://blog.csdn.net/zstuyyyyccccbbbb/article/details/108855771
  • Codeforces Round #673 (Div. 2) Problem A
    今天的题。 本来打算把比赛坚持打完的,但是因为生病了,还是早点睡吧,把第一题摸了。 题面如下: BThero is a powerful magician. He has got n piles of candies, the i-th pile initially contains ai candies. BThero can cast a copy-paste spell as follows: He chooses two piles (i,j) such that 1≤i,j≤n and i≠j . All candies from pile i are copied into pile j. Formally, the operation aj:=aj+ai is performed. BThero can cast this spell any number of times he wants to — but unfortunately, if some pile contains strictly more than k candies, he loses his magic power. What is the maximum number of times BThero can cast the spell without losing his power
  • A. Copy-paste(贪心算法)Codeforces Round #673 (Div. 2)
    原题链接: https://codeforces.com/contest/1417/problems 测试样例 input 3 2 2 1 1 3 5 1 2 3 3 7 3 2 2 output 1 5 4 Note In the first test case we get either a=[1,2] or a=[2,1] after casting the spell for the first time, and it is impossible to cast it again. 题意: 给你一个数组和一个限定值 k k k,你可以进行法术使得: 当 1 ≤ i , j ≤ n 1 \le i, j \le n 1≤i,j≤n and i ≠ j i \ne j i​=j ,让 a j : = a j + a i a_j := a_j + a_i aj​:=aj​+ai​。 当进行法术操作使得其中有一个元素超过限定值 k k k时,你都将失去该法术能力,即法术无效。问你最多能使用多少次法术。 解题思路: 一道简单的贪心问题,我们想要让法术使用次数达到最多,就要尽可能的使用小数去加,那么我们可以对该数组进行排序,以最小的数作为加数赋给其余元素。这样即可最优。 AC代码 /* *邮箱:unique_powerhouse@qq.com *blog:https://me
  • B. Two Arrays(模拟+思维)Codeforces Round #673 (Div. 2)
    原题链接: https://codeforces.com/contest/1417/problems 测试样例 input 2 6 7 1 2 3 4 5 6 3 6 3 3 3 output 1 0 0 1 1 0 1 0 0 题意: (理解题意很关键。) 给你一个数组 a a a和不幸值 T T T,要求你将数组 a a a分成数组 b b b和数组 c c c,使得 f ( b ) + f ( c ) f(b)+f(c) f(b)+f(c)最小。 其中 f ( b ) f(b) f(b)的值为数组 b b b中 1 ≤ i < j ≤ m 1≤i<j≤m 1≤i<j≤m使得 a i + a j = T a_i+a_j=T ai​+aj​=T的数量对数。(m为数组 b b b的长度) 解题思路: 我们按题意去模拟构造即可,带有点贪心的味道。遍历一遍数组 a a a,对于每个元素 a i a_i ai​我们判断 T − a i T-a_i T−ai​有没有在我们要放置的目标数组。(目标数组由我们自己决定,这个意思其实就是符合就放该数组。)如果有,我们就进行判断放哪里是最优的,这个同样是可以通过 m a p map map容器来获取判断的。 如果没有自然就放默认数组。记住:放了哪个数组,对应的 m a p map map容器要记录+1。 AC代码 /* *邮箱:unique
  • Codeforces Round #673 (Div. 2) D 和 E
    D 题意 给定一个长度为n为的数组,并且a[i] >= 1 每次可以选择两个数一个为 i,j 并选则一个x给 a[i] -= x * i, a[j] += x * i 最终是所有的元素大小都相等,并且每次操作完之后所有元素的大小都是非负的 题解 我们可以发现每次都是给整个数组加上一个数减去一个数,数组的总大小不变所以只有当所有元素的和是n的倍数才能满足条件,至于操作我们可以客观的想因为只有第一个数是我们可控(即他是所有数的约数),所有我们就可以先把所有的数都变为0,然后在变为 sum / n把所有的数变为0 首先我们先使所有的数都变为i的倍数,我们就可以用第一个数来实现因为每个数都是大于1的,所以对于[2,n]按顺序做不会出现负数的情况,最后在变为0 在变为sum / n 显然满足 3*n的条件 代码 #include<iostream> #include<vector> using namespace std; const int N = 1e4+10; #define int long long int a[N]; struct Node{ int a,b,c; }; signed main(){ // ios::sync_with_stdio(false); // cin.tie(0); int T; cin>>T; while(T--){ vector<Node> ans
  • Codeforces Round #673 (Div. 2) ABC 题解
    博客园传送门 A. Copy-paste 题意:问在保持每个数都小于等于k的情况下,最多能执行多少步a[j] += a[i] ,其中(i,j)为任意不同下标。 思路:水题,排个序,用a[1]去加到别的值上,看每个数能加多少个a[1],累加贡献即可。 view code #include<iostream> #include<string> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include <queue> #include<sstream> #include <stack> #include <set> #include <bitset> #include<vector> #define FAST ios::sync_with_stdio(false) #define abs(a) ((a)>=0?(a):-(a)) #define sz(x) ((int)(x).size()) #define all(x) (x).begin(),(x).end() #define mem(a,b) memset(a,b,sizeof(a)) #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)
  • ACM学习之路
    2019.09 目标及进度(9.22 ~ 9.30)2019.10 目标及进度2019.11 目标及进度2019.12 目标及进度2020.01 目标及进度 2019.09 目标及进度(9.22 ~ 9.30) 目标: 搞懂几个基础算法知识点并刷题。 基础算法 【总结】素数筛方法详解 【总结】最长连续子序列详细解法汇总 【总结】常用排序算法详解 【总结】快速幂及取模运算详解 【总结】C++各种进制转换函数汇总 比赛 Codeforces Round #587 (Div. 3) 题解 Codeforces Round #582 (Div. 3) 题解 2019年湘潭大学程序设计竞赛(重现赛)题解 未完成 总结位运算知识点 总结: 九月份20多号开始的训练,总结了一些基础算法知识点,没能把计划都完成。虽然有写博客,但是并不能牢牢记住,过段时间没用这些算法知识点就可能不可以百分百准确的写出来这些算法的代码。所以有时间得多看看自己的博客,把所做的笔记翻出来复习一遍。 2019.10 目标及进度 目标: 数据结构算法知识点理解并掌握,刷题不少于50道 数据结构 【总结】C++ 基础数据结构 —— STL之栈(stack)用法详解 【总结】C++ 基础数据结构 —— STL之队列(queue) 用法详解 【总结】C++ 基础数据结构 —— STL之优先队列(priority_queue)
  • Educational Codeforces Round 106 (Rated for Div. 2)(A ~ E)题解(每日训练 Day.16 )
    整理的算法模板合集: ACM模板 点我看算法全家桶系列!!! 实际上是一个全新的精炼模板整合计划 目录 Educational Codeforces Round 106 (Rated for Div. 2)(A ~ D)A. Domino on WindowsillB. Binary RemovalsC. Minimum Grid PathD. The Number of PairsE. Chaotic MergeF. Diameter CutsG. Graph Coloring Educational Codeforces Round 106 (Rated for Div. 2)(A ~ D) A. Domino on Windowsill Problem Solution 签到题…画个图算一下就好 Code // Problem: A. Domino on Windowsill // Contest: Codeforces - Educational Codeforces Round 106 (Rated for Div. 2) // URL: https://codeforces.com/contest/1499/problem/A // Memory Limit: 256 MB // Time Limit: 1000 ms // // Powered by CP
  • Codeforces Round #712 (Div. 2)
    写在前面: 其实吧,作为菜鸡的我来说,这场比赛只把a打了出来,后面的b,c感觉实际上并不是很能想到;看了很多大神的讲解后;也感觉是比较巧妙,但是我感觉我是想不出来的 A. Déjà Vu 这题我的解法可能跟其他人不大一样 首先我们要时刻牢记回文串的定义 如果我们在这个字符串头上加了一个a,如果他不能构成一个回文串,那么我们就可以直接输出答案了;如果是,首先不考虑全部都是a的情况,我们把a放到这个字符串末尾那么他一定就不是一个回文串;同样的,如果字符串后面加上了一个a的它仍然是回文串的话,注意,加上一个字母a的话他的长度是改变的,这时候,如果前后都是能构成回文串的话,那么一定是一个全是a的串 // Problem: A. Déjà Vu // Contest: Codeforces - Codeforces Round #712 (Div. 2) // URL: https://codeforces.com/contest/1504/problem/A // Memory Limit: 256 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #include <iostream> #include <cstdio> #include <algorithm> #include
  • C. 思维 Pipes Codeforces Round #590 (Div. 3)
    Codeforces Round #590 (Div. 3) Example inputCopy 6 7 2323216 1615124 1 3 4 2 13 24 2 12 34 3 536 345 2 46 54 outputCopy YES YES YES NO YES NO Note The first query from the example is described in the problem statement. 很显然的是直的管只能横着放(无法衔接上下移动的方向接过来的管子)对于拐角管 如果之前是横着运动的 那么现在就得上移或者下移如果之前就是上下移动那么现在只可横着移动now所在类 y所在行 dir前面的方向 #include<bits/stdc++.h> using namespace std; char s[2][200010]; int main() { int tt;scanf("%d",&tt); while(tt--) { int n;scanf("%d",&n); scanf("%s%s",s[0],s[1]); int now=0,y=0,dir=0,f=0; while(now<n) { if(dir==0)//之前横 { if(s[y][now]=='1'||s[y][now]=='2') { now++; }else { y=!y
  • Codeforces Round #608 (Div. 2)
    题目链接:Codeforces Round #608 (Div. 2) A Suits 题目大意:给你 四种物品 A , B , C , D A,B,C,D A,B,C,D ,其数量为 a , b , c , d a,b,c,d a,b,c,d 你有两种选择搭配的方式: 1.一件A,一件D,产生 e e e 的贡献; 2.一件B,一件C,一件D,产生 f f f 的贡献; 最后求总贡献的最大值。 思路: 1.我的思路有点麻烦,直接比较主要选第一种方式和主要选择第二种方式,取最大值就好了。里面弯弯绕绕很多,被我写的很复杂。 #include<iostream> #include<cstdio> #include<cstring> #include<stack> #include<queue> #include<set> #include<map> #include<vector> #include<list> #include<cmath> #include<algorithm> #define lson node<<1,st,mid #define rson node<<1|1,mid+1,ed #define mem(a,x) memset(a,x,sizeof(a)) #define me(a) memset(a,0,sizeof(a)) #define IOS ios
  • Educational Codeforces Round 96 (Rated for Div. 2)C. Numbers on Whiteboard
    题目链接:https://codeforces.com/problemset/problem/1430/C 思路:(贪心) 1.一开始想的是头尾相加,结果是中间的值,后来发现不对,最优的方法应该是从后面最大的相加/2,最终答案都是2 AC代码: #include<bits/stdc++.h> using namespace std; const int N=2e5+10; int a[N]; int ans; int t,n; int main() { cin>>t; while(t--) { cin>>n; cout<<"2"<<endl; int last=n; for(int i=n-1;i>=1;i--) { cout<<last<<" "<<i<<endl; if((last+i)%2==0) last=(last+i)/2; else last=(last+i)/2+1; } } return 0; } 来源:https://blog.csdn.net/weixin_51670469/article/details/115374250
  • Codeforces Round #709 (Div. 2, based on Technocup 2021 Final Round) A - Prison Break
    A. Prison Break time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Michael is accused of violating the social distancing rules and creating a risk of spreading coronavirus. He is now sent to prison. Luckily, Michael knows exactly what the prison looks like from the inside, especially since it’s very simple. The prison can be represented as a rectangle a×b which is divided into ab cells, each representing a prison cell, common sides being the walls between cells, and sides on the perimeter being the walls leading to freedom. Before
  • Codeforces Round #589 (Div. 2) C. Primes and Multiplication (思维 + 容斥)
    链接:https://codeforces.com/contest/1228/problem/C 来源:Codeforces Round #589 (Div. 2)   题意:给出一些定义,对于一个 x ,prime(x) ={p1, p2…, pn},g(x, p) 表示 x 最大可以整除 p 的多少次幂,这个 pk 就是 g(x, p) ,f(x, n) = g(n, p1) × g(n, p2) ×···× g(n,pn),prime(x) ={p1, p2…, pn},p1, p2…, pn表示 x 的质因子。最后求出 f(x, 1) × f(x, 2) × ··· × f(x, n)。   思路: f(x, 1) × f(x, 2) × ··· × f(x, n) = g(1, p1) × g(1, p2) × ··· ×g(1, pn) × g(2, p1) × g(2, p2) × ··· ×g(1, pn) × ··· × g(n, p1) × g(n, p2) × ··· ×g(n, pn) ,从这个式子可以看出对于p1的贡献,在[1, n] 中有 p1,p1 × 某个数(这些数可以贡献一个p1),对于 p12 的贡献就是p12 × 某个数(这些数可以贡献出两个p1)···综上所述,我们反过来想这么一个过程其实就是在寻找对于[1, n]之间的数字能够贡献多少p1
  • Codeforces Round #674 (Div. 3) C. Increase and Copy
    Codeforces Round #674 (Div. 3) C. Increase and Copy 题目链接 Initially, you have the array a consisting of one element 1 (a=[1]). In one move, you can do one of the following things: Increase some (single) element of a by 1 (choose some i from 1 to the current length of a and increase ai by one); Append the copy of some (single) element of a to the end of the array (choose some i from 1 to the current length of a and append ai to the end of the array). For example, consider the sequence of five moves: You take the first element a1, append its copy to the end of the array and get a=[1,1]. You take
  • Codeforces Round #645 (Div. 2)D. The Best Vacation 前缀和+二分
    Codeforces Round #645 (Div. 2)D. The Best Vacation 假设:一年有n个月,第i个月有d[i]天,每个月是从1号开始到d[i]号,即1,2,3…d[i]号。设某月的某天是s号,就可以获得s个hug拥抱。 输入一个x,你需要从这中选出连续的x天,使得其获得的hug拥抱数量最大。 需要注意是的这连续的x天中可以有下一年的天数,也就是说这里可以构成一个环,故可以预处理第二年的月份天数,即d[i+n]=d[i]。 题解: 最有解的最后一天肯定某月份的月底。 前缀和预处理每个月份的天数, 找出连续的x天, 利用二分找出满足连续x的的月份,还需要考虑最开始的一个月只取了一部分。 再前缀和数组减出区间和,贪心比较每次的获得hug拥抱数量即可。 #pragma GCC optimize(2) #include <bits/stdc++.h> #define ll long long #define _for(i,a,b) for(int i = (a);i<(b);i++) #define endl '\n' #define inf 0x3f3f3f3f using namespace std; const int mod=1e9+7; const int MAX=1e6+7; ll a[MAX],sum_day[MAX],sum_hug[MAX]
  • 【codeforces题解】CodeCraft-21 and Codeforces Round #711 (Div. 2)
    A. GCD Sum 模拟即可,代码如下 #include<iostream> #include<stdio.h> #include<vector> #include<string> #include<algorithm> #include<queue> #include<stack> #include<unordered_set> #include<set> #include<map> #include<sstream> using namespace std; #define int long long const int INT = 0x3f3f3f3f; int gcd(int a, int b) { return (b == 0) ? a : gcd(b, a % b); } int getSum(int n) { int res = 0; while (n) { res += n % 10; n /= 10; } return res; } unsigned main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) { int n; cin >> n; int res = n; while (gcd(res, getSum(res))==1) {
  • Codeforces Round #676 (Div. 2) D. Hexagons
    Codeforces Round #676 (Div. 2) D. Hexagons (贪心&思维) 思路:对某一个范围的点的进行考虑,比如 C 1 , C 2 C_1,C_2 C1​,C2​ 夹角区域的点,显然 C 4 , C 5 C_4,C_5 C4​,C5​两种操作不用考虑,然后因为 C 3 , C 6 C_3,C_6 C3​,C6​相互抵消,肯定至多考虑一种,所以六个操作变成了三个操作,然后又因为 C 2 C_2 C2​操作等价于 C 1 + C 3 C_1+C_3 C1​+C3​,所 以只需比较两者花费,若 C 1 + C 3 C_1+C_3 C1​+C3​较小,则 C 2 C_2 C2​不用考虑了,否则只需考虑 C 2 C_2 C2​加上 C 1 C_1 C1​,其他区域同理。 综上只需考虑两个操作就行了。 然后就是特判一下 x , y x,y x,y在那个象限然后进行相应最少步数的操作即可。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a,b) memset(a,b,sizeof a) #define lx x<<1 #define rx x<<1|1
  • Codeforces Round #623 (Div. 2, based on VK Cup 2019-2020 - Elimination Round, Engine) C. Restoring
    C. Restoring Permutation time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output You are given a sequence b1,b2,…,bn. Find the lexicographically minimal permutation a1,a2,…,a2n such that bi=min(a2i−1,a2i), or determine that it is impossible. Input Each test contains one or more test cases. The first line contains the number of test cases t (1≤t≤100). The first line of each test case consists of one integer n — the number of elements in the sequence b (1≤n≤100). The second line of each test case consists of n different integers b1,…,bn — elements