网站建设及推广,邵阳建设局网站,网站水军怎么做,中老年适合在哪个网站做直播Codeforces Round #700 (Div. 2)A~D2解题报告
A Yet Another String Game
原题链接
http://codeforces.com/contest/1480/problem/A 解题思路
Alice想让更小#xff0c;先手Bob想让其更大#xff0c;后手解决方案当然是贪心#xff0c;从第一个排到最后一个如果不是选择…Codeforces Round #700 (Div. 2)A~D2解题报告
A Yet Another String Game
原题链接
http://codeforces.com/contest/1480/problem/A 解题思路
Alice想让更小先手Bob想让其更大后手解决方案当然是贪心从第一个排到最后一个如果不是选择当前未更改的第一个那么被别人修改那么就会往反方向走了
AC代码
#include bits/stdc.h
using namespace std;const int N 110;
char s[N];int main()
{int t; cin t;while (t -- ){scanf(%s, s);for (int i 0; s[i]; i ){if (i 1) // bigger{if (s[i] ! z)putchar(z);elseputchar(y);}else // smaller{if (s[i] ! a)putchar(a);elseputchar(b);}}puts();}return 0;
} B The Great Hero
原题链接
http://codeforces.com/contest/1480/problem/B
解题思路
就是一个英雄和一群小怪兽打机制和洛克王国一样问自己安排小怪兽出厂顺序是否可以打死所有小怪兽包括同归于尽。 我们一直英雄的伤害为AAA,血量为BBB,nnn个小怪兽的伤害为aia_iai,血量为bib_ibi,可以计算出他可以承受的伤害为ci⌈bi/A⌉c_i\lceil b_i/A\rceilci⌈bi/A⌉ 英雄可以打过的充要条件是: Ac1∗a1...ci∗ai...((cn−1)∗an)A c_1*a_1 ...c_i * a_i ... ((c_n - 1)* a_n)Ac1∗a1...ci∗ai...((cn−1)∗an) 注意这里是大于因为保证最后一下可以打出去就行 ⟹\Longrightarrow⟹ Aanc1∗a1...ci∗ai...(cn∗an)A a_n c_1*a_1 ...c_i * a_i ... (c_n * a_n)Aanc1∗a1...ci∗ai...(cn∗an) 右边是常数左面越大越好也就是攻击力最大的放在最后即可 O(N)O(N)O(N)
AC代码
#include bits/stdc.h
using namespace std;typedef long long LL;
const int N 100010;
int n;
LL A, B;
class Node
{
public:int a, b;
}q[N];int main()
{int t; cin t;while (t -- ){scanf(%lld%lld, A, B);scanf(%d, n);int tmp;int max_a 0;for (int i 1; i n; i ){scanf(%d, q[i].a);max_a max(max_a, q[i].a);}LL sum 0;for (int i 1; i n; i ){scanf(%d, tmp);q[i].b tmp / A (tmp % A ! 0); // 可以几回合sum sum LL(q[i].a) * q[i].b;}if (B max_a sum)puts(YES);elseputs(NO);}return 0;
} C Searching Local Minimum
原题链接
http://codeforces.com/contest/1480/problem/C
解题思路 二分题目 这个题目二分特性很难一眼看出平时的二分基本是左侧为满足不满足右侧是不满足满足然后进行二分有意思的地方就是在于满足的是什么特性!! 本题这个特性和平时遇到的特性不同 特性是区间[l,r]中至少含有一个local_min至少含有一个是精髓 因为对于本体而言局部最小值可能有很多而且还很分散我们需要找任意一个局部最小值直接按照这个性质来找就可以二分。 需要注意的一点是被我们舍弃的另一部分不是说不含有local_min而是在我们未询问的前提下可能不含有local_min而选中的那个区间一定含有。
AC代码
#include bits/stdc.h
using namespace std;typedef long long LL;
const int N 100010, INF 0x3f3f3f3f;
int a[N];void query(int idx)
{if (a[idx] ! -1) // 之前已经是有数字了return;printf(? %d\n, idx);cout.flush();scanf(%d, a[idx]);
}
int n;int main()
{cin n;memset(a, -1, sizeof a);a[0] INF, a[n 1] INF;int l 1, r n, mid;while (l r){mid (l r) / 2;query(mid);query(mid 1);if (a[mid] a[mid 1]){r mid;}else{l mid 1;}}printf(! %d\n, l);return 0;
} D1 Painting the Array I
原题链接
http://codeforces.com/contest/1480/problem/D1
解题思路
题目大概描述为将原本的数组a1,a2,...,ana_1, a_2, ..., a_na1,a2,...,an通过染色分成两个子数组a1(0),a2(0),...,an1(0)a_1^{(0)}, a_2^{(0)}, ..., a_{n1}^{(0)}a1(0),a2(0),...,an1(0)和a1(1),a2(1),...,an1(1)a_1^{(1)}, a_2^{(1)}, ..., a_{n1}^{(1)}a1(1),a2(1),...,an1(1)使得合并数组毗邻相同的元素后两个数组的长度和尽可能的大。 下面我们对原数组变形形成以下形式 a0,⋅⋅⋅,a0⏟n0,a1,⋅⋅⋅,a1⏟n1,⋅⋅⋅ai,⋅⋅⋅,ai⏟ni,⋅⋅⋅,aed,⋅⋅⋅,aed⏟ned\underbrace{a_0, \cdot\cdot\cdot, a_0}_{n_0},\underbrace{a_1, \cdot\cdot\cdot, a_1}_{n_1},\cdot\cdot\cdot\underbrace{a_i, \cdot\cdot\cdot, a_i}_{n_i},\cdot\cdot\cdot,\underbrace{a_{ed}, \cdot\cdot\cdot, a_{ed}}_{n_{ed}}n0a0,⋅⋅⋅,a0,n1a1,⋅⋅⋅,a1,⋅⋅⋅niai,⋅⋅⋅,ai,⋅⋅⋅,nedaed,⋅⋅⋅,aed。\quad其中∀i,ai̸ai1\forall i, a_i \not a_{i1}∀i,aiai1 假设我们当前正要处理ai,⋅⋅⋅,ai⏟ni,\underbrace{a_i, \cdot\cdot\cdot, a_i}_{n_i},niai,⋅⋅⋅,ai,部分时分配的两个数组当前为b1,b2,⋅⋅⋅,bcur1b_1,b_2,\cdot\cdot\cdot,b_{cur1}\quadb1,b2,⋅⋅⋅,bcur1和c1,c2,⋅⋅⋅,ccur2\quad c_1,c_2,\cdot\cdot\cdot,c_{cur2}c1,c2,⋅⋅⋅,ccur2 下面我们对当前处理的情况进行讨论
ni1n_i1ni1 bcur1和ccur2至少存在一个不等于aib_{cur1}和c_{cur2}至少存在一个不等于a_{i}bcur1和ccur2至少存在一个不等于ai那么直接放在不等于的后面res1res 1res1ni≥2n_i\geq 2ni≥2 bcur1和ccur2存在一个等于ai另一个不等于ai\quad b_{cur1}和c_{cur2}存在一个等于a_{i}另一个不等于a_{i}bcur1和ccur2存在一个等于ai另一个不等于ai那么直接放在不等于的后面(两边都放也行)res1\quad \quad res 1res1 bcur1和ccur2都不等于ai\quad b_{cur1}和c_{cur2}都不等于a_{i}bcur1和ccur2都不等于ai那么两边都放至少一个res2\quad res 2res2 那么为什么这样做是对的 补证明:
AC代码
#include bits/stdc.h
using namespace std;const int N 100010;
const int INF 0x3f3f3f3f;
int a[N];
int n;
int main()
{cin n;for (int i 1; i n; i )scanf(%d, a[i]);int pre 1, ed 0, cnt;a[0] a[n 1] a[n 2] a[n 3] INF;int res 0;int surp1 -INF, surp2 -INF;int tmp1;for (int i 1; i n 1; i ){if (a[i] a[i - 1]){ed i;}else{cnt ed - pre 1;if (cnt 0){pre ed i;continue;}if (surp1 a[i - 1] || surp2 a[i - 1]){surp1 surp2 a[i - 1];res 1;}else if (cnt 2){res 2;surp1 surp2 a[i - 1];}else if (cnt 1) // 帮忙遮掩{tmp1 a[i];if (surp1 a[i])surp1 a[i - 1];else if (surp2 a[i])surp2 a[i - 1];elsesurp1 a[i - 1];res 1;}pre ed i;}}cout res endl;return 0;} D2 Painting the Array II
原题链接 待补
http://codeforces.com/contest/1480/problem/D2
解题思路
该题目也是贪心 首先原数组a0,⋅⋅⋅,a0⏟n0,a1,⋅⋅⋅,a1⏟n1,⋅⋅⋅ai,⋅⋅⋅,ai⏟ni,⋅⋅⋅,aed,⋅⋅⋅,aed⏟ned\underbrace{a_0, \cdot\cdot\cdot, a_0}_{n_0},\underbrace{a_1, \cdot\cdot\cdot, a_1}_{n_1},\cdot\cdot\cdot\underbrace{a_i, \cdot\cdot\cdot, a_i}_{n_i},\cdot\cdot\cdot,\underbrace{a_{ed}, \cdot\cdot\cdot, a_{ed}}_{n_{ed}}n0a0,⋅⋅⋅,a0,n1a1,⋅⋅⋅,a1,⋅⋅⋅niai,⋅⋅⋅,ai,⋅⋅⋅,nedaed,⋅⋅⋅,aed。\quad其中∀i,ai̸ai1\forall i, a_i \not a_{i1}∀i,aiai1。因为是要求最小我们将数组改造为a0,a1,⋅⋅⋅,ai,⋅⋅⋅,aeda_0, a_1, \cdot \cdot \cdot,a_i, \cdot \cdot \cdot,a_{ed}a0,a1,⋅⋅⋅,ai,⋅⋅⋅,aed 假设我们当前构造的两行line1,line2line1, line2line1,line2是正确的现在查看a[i]a[i]a[i]应该放在哪个队列之后。
line1_back()line2_back()line1\_back() line2\_back()line1_back()line2_back()那么我们将a[i]a[i]a[i]放在那里都是可以的。line1_back()̸line2_back()line1\_back() \notline2\_back()line1_back()line2_back()时候进行下列分析 倘若line1_back()a[i]line1\_back() a[i]line1_back()a[i]那么直接放在line1line1line1即可因为可以直接抵消掉 同理倘若line2_back()a[i]line2\_back() a[i]line2_back()a[i]那么直接放在line2line2line2即可。 最后 一种情况line1_back()̸a[i]而且line2_back()̸a[i]line1\_back() \not a[i] 而且 line2\_back() \not a[i]line1_back()a[i]而且line2_back()a[i]那么我们考虑line1line1line1和line2line2line2的末尾谁可以最近的匹配放入较远的一方即可。因为最近匹配优先不可被中断。
AC代码
#include bits/stdc.h
using namespace std;const int N 100010, INF 0x3f3f3f3f;
int a[N], b[N];
int n;
vectorint pos[N];
int cur[N];int nxt(int x)
{if (x INF || cur[x] pos[x].size()) // 已经到达了最后一个return INF;elsereturn pos[x][cur[x]];
}int main()
{cin n;for (int i 1; i n; i ) scanf(%d, a[i]);int n2 1;b[1] a[1];for (int i 2; i n; i )if (a[i] ! a[i - 1])b[ n2] a[i];n n2;memset(cur, 0, sizeof cur);for (int i 1; i n; i ){// printf(%d , b[i]);pos[b[i]].push_back(i);}// puts();int res n;vectorint v[2];int tar INF, cur_tar, tar_line 1;v[0].push_back(INF), v[1].push_back(INF);for (int i 1; i n; i ){cur[b[i]] ;if (v[0].back() v[1].back()) // 情况一line1 line2{if (v[0].back() b[i])res --;v[0].push_back(b[i]);}else if (v[0].back() b[i]){res --;v[0].push_back(b[i]);}else if (v[1].back() b[i]){res --;v[1].push_back(b[i]);}else{static int nxt0, nxt1;nxt0 nxt(v[0].back());nxt1 nxt(v[1].back());if (nxt0 nxt1){v[0].push_back(b[i]);}else{v[1].push_back(b[i]);}}}cout res endl;return 0;
}
/*
15
1 1 1 2 2 1 3 2 1 1 1 2 3 3 1
*/
