天津哪里能做网站,焊接球网架公司,网站建设包括哪些方面选择题,h5长图模板Codeforces Round #702 (Div. 3) 全部题解
读错题意#xff0c;写了半天真是心态爆炸#xff0c;总的来看这次题目不难的。
A. Dense Array
http://codeforces.com/contest/1490/problem/A 解题思路 相邻的数字必然是倘若不满足的话是需要插入数据的#xff0c;那么我们…Codeforces Round #702 (Div. 3) 全部题解
读错题意写了半天真是心态爆炸总的来看这次题目不难的。
A. Dense Array
http://codeforces.com/contest/1490/problem/A 解题思路 相邻的数字必然是倘若不满足的话是需要插入数据的那么我们模拟插入数据即可. xmin(ai,ai1),ymax(ai,ai1)x min(a_i, a_{i1}), y max(a_i, a_{i1})xmin(ai,ai1),ymax(ai,ai1)
倘若2∗x≤y2 * x \leq y2∗x≤y不需要操作否则需要插入数据。不断的贪心插入 2⋅x2\cdot x2⋅x直到满足条件。 其实这有一个公式的推导与公式如下所示。 模拟乘以2
#include bits/stdc.h
using namespace std;typedef long long LL;
typedef pairint, int PII;
const int N 1010, INF 0x3f3f3f3f;
int n, a[N];
PII b[N];
bool st[N];int cal(int t1, int t2)
{int ret 0;while (2 * t1 t2){ret ;t1 * 2;}return ret;
}int main()
{int t; cin t;while (t -- ){cin n;LL x 0;for (int i 1; i n; i ){scanf(%d, a[i]);}double cnt;for (int i 1, t1, t2; i n; i ){t1 min(a[i], a[i 1]), t2 max(a[i], a[i 1]);if (t1 * 2 t2) continue;else{x cal(t1, t2);}}cout x endl;}return 0;
}直接上公式没有过应该是小数精度会被卡
#include bits/stdc.h
using namespace std;typedef long long LL;
typedef pairint, int PII;
const int N 1010, INF 0x3f3f3f3f;
int n, a[N];int main()
{int t; cin t;while (t -- ){cin n;LL x 0;for (int i 1; i n; i ){scanf(%d, a[i]);}double cnt;for (int i 1, t1, t2; i n; i ){t1 min(a[i], a[i 1]), t2 max(a[i], a[i 1]);if (t1 * 2 t2) continue;else{x ceil(log(t2 * 1.0 / t1) / log(2)) - 1;}}cout x endl;}return 0;
}
B. Balanced Remainders
http://codeforces.com/contest/1490/problem/B 先统计出来%3\%3%3余数为0,1,20,1, 20,1,2数字的数量c0,c1,c2c_0, c_1, c_2c0,c1,c2根据倘若多那么一定会送走倘若少一定会挪进行这个性质进行模拟而且对于特定的cic_ici他给别人或者是别人给他的交易对象是一样的即操作是固定的。
#include bits/stdc.h
using namespace std;typedef long long LL;
typedef pairint, int PII;
const int N 100010, INF 0x3f3f3f3f;
int n, a[N];
int c[5] {0, 0, 0};int opt(int idx, int ave)
{int idx2 (idx 1) % 3, idx0 (idx - 1 3) % 3;int need 0;if (c[idx] ave) // 过少需要向前一个索要{need ave - c[idx];c[idx0] - need;c[idx] need;}else // 太多需要给下一个{need c[idx] - ave;c[idx2] need;c[idx] - need;}return need;
}int main()
{int t; cin t;while (t -- ){cin n;int ave n / 3;memset(c, 0, sizeof c);for (int i 1; i n; i ){scanf(%d, a[i]);c[a[i] % 3] ;}int res 0;for (int i 0; i 3; i ){res opt(i, ave);}printf(%d\n, res);}return 0;
}
C. Sum of Cubes
http://codeforces.com/contest/1490/problem/C 直接就是 将 i3i^3i3在map上进行打表就可以了。 很关键的是预处理多处理几个不然很容易被卡
#include bits/stdc.h
using namespace std;typedef long long LL;
const int N 100010;
LL n;
LL a[N];
mapLL, bool m;int main()
{int t; cin t;for (LL i 1; i 10010; i ) // 这里仅仅写到 10000就会 WA主要是怕他多往后走了一步查询到了0{a[i] i * i * i;m[a[i]] true;}// cout m[0] endl;while (t -- ){scanf(%lld, n);bool flag false;LL surp;for (int i 1; !flag a[i] n; i ){surp n - a[i];if (m[surp] true){flag true;}}if (flag) puts(YES);else puts(NO);}return 0;
}
D. Permutation Transformation
http://codeforces.com/contest/1490/problem/D 一个简单的模拟dfs每次在区间找最大值作为 root 即可
#include bits/stdc.h
using namespace std;const int N 110;
int a[N], n, depth[N];void build(int fa, int l, int r)
{if (l r) return;int u -1, v -1;// 左子树for (int i l; i fa; i ){if (u -1 || a[u] a[i])u i;}depth[u] depth[fa] 1;build(u, l, fa - 1);// 右子树for (int i fa 1; i r; i ){if (v -1 || a[v] a[i])v i;}depth[v] depth[fa] 1;build(v, fa 1, r);
}int main()
{int t; cin t;while (t -- ){scanf(%d, n);for (int i 1; i n; i )scanf(%d, a[i]);memset(depth, -1, sizeof depth);int v;for (int i 1; i n; i ){if (a[i] n){v i;break;}}depth[v] 0;build(v, 1, n);cout depth[1];for (int i 2; i n; i )printf( %d, depth[i]);cout endl;}return 0;
}
E. Accidental Victory
http://codeforces.com/contest/1490/problem/E 说白了就是看谁可以赢。 首先我们先将他们按照各自的数值排序得到数组a1,a2⋅⋅⋅,ana_1,a_2\cdot\cdot\cdot,a_na1,a2⋅⋅⋅,an对应编号为idx1,idx2,⋅⋅⋅,idxnidx_1, idx_2, \cdot\cdot\cdot,idx_nidx1,idx2,⋅⋅⋅,idxn我们对数组求取前缀和sum1,sum2,⋅⋅⋅,sumnsum_1, sum_2,\cdot\cdot\cdot,sum_nsum1,sum2,⋅⋅⋅,sumn 我们从后往前看
第nnn个是最大的肯定有机会成为winner第n−1n-1n−1倘若可以成为winnerwinnerwinner当且仅当他赢过1n−21~n-21 n−2个人然后和ana_nan比较倘若他成不了winnerwinnerwinner那么直接算法结束比他小的人更成为不了winnnerwinnnerwinnner不断这样算下去即可
#include bits/stdc.h
using namespace std;typedef long long LL;
typedef pairLL, int PII;
const int N 200010;
vectorint res;
LL a[N];
LL b[N];
PII c[N];
int n;bool cmp(const PII t1, const PII t2)
{return t1.first t2.first;
}
int main()
{int t; cin t;while (t -- ){scanf(%d, n);for (int i 1; i n; i ){scanf(%lld, a[i]);c[i].first a[i];c[i].second i;}sort(c 1, c n 1, cmp);for (int i 1; i n; i )b[i] b[i - 1] c[i].first;res.clear();res.push_back(c[n].second);for (int i n - 1; i 1; i -- ){if (b[i] c[i 1].first)res.push_back(c[i].second);elsebreak;}sort(res.begin(), res.end());cout res.size() endl;cout res[0];for (int i 1; i res.size(); i )printf( %d, res[i]);cout endl;}return 0;
}
F. Equalize the Array
http://codeforces.com/contest/1490/problem/F 具体思路 先用map将出现次数存储起来统计出出现次数为iii的数字一共有cnticnt_icnti个 那么我们首先模拟一下想让所有数字出现的次数为iii或者是000那么我们需要将出现次数小于等于iii的数字全部移除需要的次数为cnt1⋅1⋅⋅⋅cnti−1⋅(i−1)cnt_1\cdot1\cdot\cdot\cdot cnt_{i-1}\cdot{(i-1)}cnt1⋅1⋅⋅⋅cnti−1⋅(i−1) 需要将出现次数大于iii的数字次数缩减为iii 需要的操作次数为$$ ⟹(i1)⋅cnti1(i2)⋅cnti2⋅⋅⋅(n)⋅cntn−i⋅(cnti1cnti2⋅⋅⋅cntn)\Longrightarrow(i1)\cdot cnt_{i1} (i2)\cdot cnt_{i2}\cdot\cdot\cdot(n)\cdot cnt_n -i\cdot(cnt_{i1}cnt_{i2}\cdot\cdot\cdotcnt_n)⟹(i1)⋅cnti1(i2)⋅cnti2⋅⋅⋅(n)⋅cntn−i⋅(cnti1cnti2⋅⋅⋅cntn) 因此我们直接预处理出来 cnticnt_icnti的前缀数组和他们的加权成前缀数组即可
#include bits/stdc.h
using namespace std;typedef pairint, int PII;
typedef long long LL;
const int INF 0x3f3f3f3f;
const int N 200010;
int a[N 5];
int n;
mapint, int m;
int cnt[N 5];
int sum[N 5];
LL addval[N 5];int main()
{int t; cin t;while (t -- ){m.clear();scanf(%d, n);for (int i 1; i n; i ){scanf(%lld, a[i]);m[a[i]] ;}memset(cnt, 0, sizeof cnt);memset(sum, 0, sizeof sum);memset(addval, 0, sizeof addval);mapint, int::iterator it;for (it m.begin(); it ! m.end(); it ) // 出现it-second 次数的数字进行统计{/// printf(IT: %d, %d\n, it-first, it-second);cnt[it-second] ;}// 计算前缀数组和累加和数组for (int i 1; i n; i ) // 最多出现 n 次{sum[i] sum[i - 1] cnt[i];addval[i] addval[i - 1] LL(cnt[i]) * i;}
/*printf(CNT:\n\t);for (int i 1; i n; i ){printf(%d , cnt[i]);}cout endl;
*/LL res 1e16;LL up, down;for (int i 1; i n; i ){down addval[i - 1];up (addval[n] - addval[i - 1]) - (sum[n] - sum[i - 1]) * i;res min(res, up down);}cout res endl;}return 0;
}
G. Old Floppy Drive
http://codeforces.com/contest/1490/problem/G 本题是一个较为隐蔽的二分题目需要我们贪心预处理出来可以二分的数组。 首先我们先将前缀数组给求出来 并且贪心得到 cnt不断增加而且前缀和也增加的数字将其放入数组v, 具体见代码max_val部分。 那么数组 v 是一个数值无论是val还是opt_cnt都不断增加的数据
倘若 xix_ixi在 数组 v 最大值的范围之内那么直接二分找最小的cnt否则需要判断一下整个原数组 a 的累加和是否大于零倘若小于等于0无解否则是可以经过不断的循环找到这个数的首先我们根据max(v)找到最小的循环次数然后二分即可。 本题最坑的点就是 long long 开的地方很多几乎所有的数据都要开long long
#include bits/stdc.h
using namespace std;typedef long long LL;
const LL INF 0x3f3f3f3f3f3f3f3f;
const int N 200010;
int n, m;
LL a[N], x[N];
LL sum[N];
class Node
{
public:LL val, cnt;Node(LL _val 0, LL _cnt 0){val _val, cnt _cnt;}
}b[N];int main()
{int t; cin t;while (t -- ){cin n m;LL cur_max -INF;b[1] Node(-INF, -1);int n2 1;sum[0] 0LL;for (int i 1; i n; i ){scanf(%lld, a[i]);sum[i] sum[i - 1] a[i];if (sum[i] cur_max){cur_max sum[i];b[ n2] Node(cur_max, i - 1); // 注意在这里的 - 1}}for (int i 1; i m; i )scanf(%lld, x[i]);// 当前的 b 数字 是 1~n val 增加 cnt增加的递增数组下面我们的 x 仅仅只需要二分即可;/// printf(RES:\n\t);LL loop sum[n];for (int i 1; i m; i ){if (b[n2].val x[i]) // 可以直接二分找 x[i] 的最小值{int l 1, r n2, mid;while (l r){mid l r 1;if (b[mid].val x[i])r mid;elsel mid 1;}printf(%lld , b[l].cnt);}else // 查看他的 loop{if (loop 0) // 无法达到{printf(-1 );}else{LL loopcnt (x[i] - b[n2].val) / loop ((x[i] - b[n2].val) % loop ! 0);x[i] - loopcnt * loop;int l 1, r n2, mid;while (l r){mid l r 1;if (b[mid].val x[i])r mid;elsel mid 1;}printf(%lld , b[l].cnt loopcnt * n); // loopcnt 是乘以 n 的}}}puts();}return 0;
}
