锐客网

  1. 首页 > it技术 > >

Codeforces|Codeforces Round #531 (Div. 3) ABCDEF题解

Codeforces Round #531 (Div. 3)
题目总链接：https://codeforces.com/contest/1102
A. Integer Sequence Dividing
题意：
给一个数n，然后要求你把1,2.....n分为两个集合，使得两个集合里面元素的和的差的绝对值最小。

题解：
分析可以发现，当n%4==0 或者 n%3==0，答案为0；其余答案为1。之后输出一下就好了。
代码如下：
Codeforces|Codeforces Round #531 (Div. 3) ABCDEF题解
文章图片
Codeforces|Codeforces Round #531 (Div. 3) ABCDEF题解
文章图片

#include using namespace std; typedef long long ll; ll n; int main(){ cin>>n; int x = (n+1)/2; if(x%2) cout<<1; else cout<<0; return 0; }

View Code
B. Array K-Coloring
题意：
给出n个数，k种颜色(编号为1-k)，现在要求给每个数上色，并且每种颜色都要被用到，以及相同的数不能上相同的颜色。
如果最终没有可行方案就输出NO，否则将一种上色方案输出出来。

题解：
先判断可行性，如果存在一种上色方案的话再往后面考虑。
我的做法是先给每个数上色，颜色为该数第几次出现。然后记录下出现最多的那个数，对于其它的数，就先从k开始上色。如果k种颜色已经用完，就直接输出其余数对应出现的次数。
这种上色方案可以保证同样的数不会被染为相同的颜色。
还有种更简单的方案，记录每个数出现的位置，然后对于每个数的每个位置，不断染色就好了。当数不同时，染色的起点不会重置。这样也满足题中条件。
给出更加简洁的代码吧...
Codeforces|Codeforces Round #531 (Div. 3) ABCDEF题解
文章图片
Codeforces|Codeforces Round #531 (Div. 3) ABCDEF题解
文章图片
#include using namespace std; typedef long long ll; const int N = 5005; int n,k; int a[N],cnt[N],ans[N]; int main(){ cin>>n>>k; vector vec[N]; int ok = 0; if(nk) ok =1; vec[a[i]].push_back(i); } if(ok) cout<<"NO"; else{ puts("YES"); int col = 1; for(int i=1; i<=5000; i++){ if(vec[i].size()<=0) continue ; for(auto pos : vec[i]){ ans[pos]=col++; if(col>k) col=1; } } for(int i=1; i<=n; i++) cout<" "; } return 0; }

View Code
C. Doors Breaking and Repairing
题意：
两个人玩游戏，一共玩10^100轮。A先手，他可以让一个门的耐久度减少x; B可以让一个门的耐久度加上y，但是他不能对耐久度已经为0的门进行操作。
如果一个玩家不能再进行操作，那么他就直接跳过。
现在想知道，最多可以留下多少扇耐久度大于0的门。

题解：
博弈问题。我们对于x,y的大小进行判断，因为轮数太多，我们就假设会玩无限轮。
当x<=y时，A如果破坏一个门，假设耐久度依然大于0，那么B会去修复它，这样A就永远破坏不了这个门。所以A只能破坏一开始耐久度<=x的门。
A破坏一个门，B可以选择另外一个耐久度低的门，之后A也是不能破坏这个门的，道理同上。
所以这种情况，假设耐久度小于等于x的门为cnt个，A最多破坏(cnt+1)/2扇门就不行了。
当x>y时，这种情况比较好分析，A总能把所有的门都给破坏。

所以代码如下：
Codeforces|Codeforces Round #531 (Div. 3) ABCDEF题解
文章图片
Codeforces|Codeforces Round #531 (Div. 3) ABCDEF题解
文章图片
#include using namespace std; typedef long long ll; const int N = 1e5+5; int n,x,y; int a[N]; int main(){ scanf("%d%d%d",&n,&x,&y); int cnt= 0; for(int i=1; i<=n; i++){ scanf("%d",&a[i]); if(a[i]<=x) cnt++; } if(x>y) cout<
View Code
D. Balanced Ternary String
题意：
给一个长度为3的倍数的字符串，里面只含有0,1,2三种字符。
现在要求你用最少的操作使得三种字符的数量相等，并且字典序要最小。

题解：
似乎就是贪心+模拟...
首先可以统计出三种字符串的数目，然后如果0的数目比要求的小，那么说明要将一些1，2换为0。
【Codeforces|Codeforces Round #531 (Div. 3) ABCDEF题解】这里肯定是尽量从前往后换，因为要求操作次数最小，所以我们先换数量多的就行了。
如果0的数量比要求的多，那么就尽量从后往前换0，因为是从后往前，如果cnt[2]>=cnt[1]，我们就优先将0换为2；否则就换为1。
注意不能一直换下去，中途判断一下是否0，1，2的数量达到了要求。
当0的数量达到要求后，再来换1或者2，这种情况就比较简单了，分析类似上面。

代码如下：
Codeforces|Codeforces Round #531 (Div. 3) ABCDEF题解
文章图片
Codeforces|Codeforces Round #531 (Div. 3) ABCDEF题解
文章图片
#include using namespace std; typedef long long ll; const int N = 3e5+5; int n; char s[N]; int cnt[N],a[N]; int main(){ scanf("%d",&n); scanf("%s",s); for(int i=0; ilev){ int fir; if(cnt[1]>=cnt[2]) fir=2; else fir=1; for(int i=n; i>=1; i--){ if(cnt[0]==lev) break ; if(!a[i]){ cnt[fir]++; cnt[0]--; a[i]=fir; if(cnt[fir]>=lev) fir = 3-fir; } } }else if(cnt[0]cnt[2]) fir=1; else fir = 2; for(int i=1; i<=n; i++){ if(cnt[0]==lev) break ; if(a[i]==fir){ cnt[fir]--; cnt[0]++; a[i]=0; if(cnt[fir]<=lev) fir=3-fir,i=0; } } } if(cnt[1]=lev) break; if(a[i]==2){ cnt[2]--; cnt[1]++; a[i]=1; } } }else if(cnt[1]>lev){ for(int i=n; i>=1; i--){ if(cnt[1]<=lev) break ; if(a[i]==1){ cnt[1]--; cnt[2]++; a[i]=2; } } } for(int i=1; i<=n; i++) cout<
View Code
E. Monotonic Renumeration
题意：
给出一个a数组，现在要求构造一个b数组满足如下条件：
1.b1=0 ;
2.对于所有的1<=i,j<=n且i!=j，如果ai=aj，那么bi=bj;
3.对于所有的1<=i
题解：
如果al=ar，那么我们知道区间[l,r]中，b数组的值都是一样的。
根据这点找区间覆盖即可：将重合的区间看作一个区间，然后对于每个区间，除开第一个区间对答案的贡献是1，其余区间对答案的贡献都为2。
寻找重合区间可以利用一个指针，o(n)就可以完成。

代码如下：
Codeforces|Codeforces Round #531 (Div. 3) ABCDEF题解
文章图片
Codeforces|Codeforces Round #531 (Div. 3) ABCDEF题解
文章图片
#include using namespace std; typedef long long ll; const int N = 2e5+5,MOD = 998244353 ; map r; int n; int a[N]; int main(){ cin>>n; for(int i=1; i<=n; i++){ scanf("%d",&a[i]); r[a[i]]=i; } ll ans = 1; for(int i=1; i<=n; i++){ int cur = r[a[i]]; if(i>1){ ans*=2; if(ans>=MOD) ans-=MOD; } while(i
View Code
F题题解请移步：https://www.cnblogs.com/heyuhhh/p/10252277.html
转载于:https://www.cnblogs.com/heyuhhh/p/10249252.html

    推荐阅读


    上一篇：紫海香田

    下一篇：jquery ui（四）进度条 progressbar