GVKun编程网logo

Nice Garland CodeForces - 1108C （思维 + 暴力）

20

此处将为大家介绍关于NiceGarlandCodeForces-1108C的详细内容，并且为您解答有关思维+暴力的相关问题，此外，我们还将为您介绍关于ANDGraphCodeForces-987F（思

此处将为大家介绍关于Nice Garland CodeForces - 1108C 的详细内容，并且为您解答有关思维 + 暴力的相关问题，此外，我们还将为您介绍关于AND Graph CodeForces - 987F（思维二进制dfs）、Array and Segments (Easy version) CodeForces - 1108E1 （暴力枚举）、B类-Codeforces Round #535 (Div. 3)C. Nice Garland、CF思维联系--CodeForces - 218C E - Ice Skating （并查集）的有用信息。

本文目录一览：

Nice Garland CodeForces - 1108C （思维 + 暴力）

Nice Garland CodeForces - 1108C （思维 + 暴力）

You have a garland consisting of nn lamps. Each lamp is colored red, green or blue. The color of the ii-th lamp is sisi (''R'', ''G'' and ''B'' — colors of lamps in the garland).

You have to recolor some lamps in this garland (recoloring a lamp means changing its initial color to another) in such a way that the obtained garland is nice.

A garland is called nice if any two lamps of the same color have distance divisible by three between them. I.e. if the obtained garland is tt, then for each i,ji,j such that ti=tjti=tj should be satisfied |i−j| mod 3=0|i−j| mod 3=0. The value |x||x| means absolute value of xx, the operation x mod yx mod y means remainder of xx when divided by yy.

For example, the following garlands are nice: "RGBRGBRG", "GB", "R", "GRBGRBG", "BRGBRGB". The following garlands are not nice: "RR", "RGBG".

Among all ways to recolor the initial garland to make it nice you have to choose one with the minimum number of recolored lamps. If there are multiple optimal solutions, print any of them.

Input

The first line of the input contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the number of lamps.

The second line of the input contains the string ss consisting of nn characters ''R'', ''G'' and ''B'' — colors of lamps in the garland.

Output

In the first line of the output print one integer rr — the minimum number of recolors needed to obtain a nice garland from the given one.

In the second line of the output print one string tt of length nn — a nice garland obtained from the initial one with minimum number of recolors. If there are multiple optimal solutions, print any of them.

Examples

Input 
3
BRB
Output 
1
GRB
Input 
7
RGBGRBB
Output 
3
RGBRGBR

题意：简单词汇，可以自行阅读。
思路：因为题目的限制，导致如果这个字符串的长度大于等于3的时候，一定是RBG这三个字符的某一个排列的循环。
那么RBG一共最多有6种排列方式,( A(3,3) )
我们手写出这6种全排列。
{
"RGB",
"RBG",
"GRB",
"BRG",
"GBR",
"BGR"};

 

然后以此每一种排列去和字符串进行匹配，找出让字符串为3字符循环的最小消耗即可，
中间开一个变量k来记录是哪个排列方式让消耗最小，然后最后输出他的循环节即可。
细节看代码。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), ''\0'', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
inline void getInt(int* p);
const int maxn=1000010;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int n;
char a[maxn];
char s[50][50]=
{
"RGB",
"RBG",
"GRB",
"BRG",
"GBR",
"BGR"};
int main()
{
    gg(n);
    scanf("%s",a);
    if(n==1)
    {
        printf("0\n");
        printf("%s",a);
    }else
    {
        int ans=inf;
        int cnt;
        int k;
        repd(i,0,5)
        {
            cnt=0;
            repd(j,0,n-1)
            {
                if(a[j]!=s[i][(j%3)])
                {
                    cnt++;
                }
            }
            if(cnt<ans)
            {
                ans=cnt;
                k=i;
            }
        }
        printf("%d\n",ans );
        repd(i,0,n-1)
        {
            putchar(s[k][(i%3)]);
        }
        printf("\n");
    }

    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == '' '' || ch == ''\n'');
    if (ch == ''-'') {
        *p = -(getchar() - ''0'');
        while ((ch = getchar()) >= ''0'' && ch <= ''9'') {
            *p = *p * 10 - ch + ''0'';
        }
    }
    else {
        *p = ch - ''0'';
        while ((ch = getchar()) >= ''0'' && ch <= ''9'') {
            *p = *p * 10 + ch - ''0'';
        }
    }
}

 


AND Graph CodeForces - 987F（思维二进制dfs）

AND Graph CodeForces - 987F（思维二进制dfs）

题意：给出n
（0≤n≤22）和m，和m个数ai，1 ≤ m ≤ 2n ，0≤ai<2n ，把ai & aj == 0 的连边，求最后有几个连通块

解析：一个一个去找肯定爆，那么就要转换一下思维，想一下什么样的数才能按位与ai为0

那么肯定是ai ^ ((1<<n)-1)的子集，所以去找它的所有子集即可

例1010  变成0101  子集有 0101  0100  0001

然后只有x是给出的那m个数种的时候 才能 ^ ,其他情况消1取子集

#include <bits/stdc++.h>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
const int maxn = (1<<22) + 5, INF = 0x7fffffff;
int n, m, res;
int a[maxn], vis[maxn], inc[maxn];

void dfs(int x)
{
    if(vis[x]) return;
    vis[x] = 1;
    if(inc[x])
    {
        dfs(x^((1<<n)-1));
    }
    for(int i=0; i<n; i++)
    {
        if(x&(1<<i))
        {
            int temp = x^(1<<i);
            if(!vis[temp])
            {
                dfs(temp);
            }
        }
    }
}

int main()
{
    mem(vis, 0);
    mem(inc, 0);
    scanf("%d%d", &n, &m);
    res = 0;
    for(int i=0; i<m; i++)
    {
        scanf("%d", &a[i]);
        inc[a[i]] = 1;
    }
    for(int i=0; i<m; i++)
        if(!vis[a[i]])
        {
            vis[a[i]] = 1;
            res++;
            dfs(a[i]^((1<<n)-1));
        }

    cout<< res <<endl;


    return 0;
}

 

 

 

Array and Segments (Easy version) CodeForces - 1108E1 （暴力枚举）

Array and Segments (Easy version) CodeForces - 1108E1 （暴力枚举）

The only difference between easy and hard versions is a number of elements in the array.

You are given an array aa consisting of nn integers. The value of the ii-th element of the array is aiai.

You are also given a set of mm segments. The jj-th segment is [lj;rj][lj;rj], where 1≤lj≤rj≤n1≤lj≤rj≤n.

You can choose some subset of the given set of segments and decrease values on each of the chosen segments by one (independently). For example, if the initial array a=[0,0,0,0,0]a=[0,0,0,0,0] and the given segments are [1;3][1;3] and [2;4][2;4] then you can choose both of them and the array will become b=[−1,−2,−2,−1,0]b=[−1,−2,−2,−1,0].

You have to choose some subset of the given segments (each segment can be chosen at most once) in such a way that if you apply this subset of segments to the array aaand obtain the array bb then the value maxi=1nbi−mini=1nbimaxi=1nbi−mini=1nbi will be maximum possible.

Note that you can choose the empty set.

If there are multiple answers, you can print any.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.

Input

The first line of the input contains two integers nn and mm (1≤n≤300,0≤m≤3001≤n≤300,0≤m≤300) — the length of the array aa and the number of segments, respectively.

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (−106≤ai≤106−106≤ai≤106), where aiai is the value of the ii-th element of the array aa.

The next mm lines are contain two integers each. The jj-th of them contains two integers ljlj and rjrj (1≤lj≤rj≤n1≤lj≤rj≤n), where ljlj and rjrj are the ends of the jj-th segment.

Output

In the first line of the output print one integer dd — the maximum possible value maxi=1nbi−mini=1nbimaxi=1nbi−mini=1nbi if bb is the array obtained by applying some subset of the given segments to the array aa.

In the second line of the output print one integer qq (0≤q≤m0≤q≤m) — the number of segments you apply.

In the third line print qq distinct integers c1,c2,…,cqc1,c2,…,cq in any order (1≤ck≤m1≤ck≤m) — indices of segments you apply to the array aa in such a way that the value maxi=1nbi−mini=1nbimaxi=1nbi−mini=1nbi of the obtained array bb is maximum possible.

If there are multiple answers, you can print any.

Examples

Input 
5 4
2 -2 3 1 2
1 3
4 5
2 5
1 3
Output 
6
2
1 4
Input 
5 4
2 -2 3 1 4
3 5
3 4
2 4
2 5
Output 
7
2
2 3
Input 
1 0
1000000
Output 
0
0

Note

In the first example the obtained array bb will be [0,−4,1,1,2][0,−4,1,1,2] so the answer is 66.

In the second example the obtained array bb will be [2,−3,1,−1,4][2,−3,1,−1,4] so the answer is 77.

In the third example you cannot do anything so the answer is 00.

 

题意：

一个包含N个元素的数组，和M个区间

你可以选择这M个区间中的某些个使用，每使用一个 区间可以使区间对应数组中的元素值减去1，每一个区间最多使用一次。

让求出使用某些个（可以是0个）区间后，数组的最大值减去最小值最大。并输出选择了哪些区间。

思路：

由于数据量亲民，我们只需要枚举1~n的每一个位置，以那个位置不我们数组渴望的不变值，即选择的区间不应该包括他，

然后把不包括他的区间都使用，然后暴力的求最大差值，中间维护下最值信息和对应选择的点即可。

数据量比较小，任意暴力出答案就可以了。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), ''\0'', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
inline void getInt(int* p);
const int maxn=1000010;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int n;
int q;
int a[maxn];
struct node
{
    int l,r;
}qj[maxn];
int ji[305];
int main()
{
    gg(n);
    gg(q);
    int d=-1*inf;
    int did;
    std::vector<int> v;
    int jr=inf;
    repd(i,1,n)
    {
        gg(a[i]);
        if(a[i]>d)
        {
            v.clear();
            did=i;
            d=a[i];
            v.push_back(i);
        }else if(a[i]==d)
        {
            v.push_back(i);
        }
        jr=min(jr,a[i]);
    }
    repd(i,1,q)
    {
        gg(qj[i].l);
        gg(qj[i].r);
    }
    int ans=d-jr;
    std::vector<int> aa;
    std::vector<int> fu;
    for(int i=1;i<=n;i++)
    {
        int id=i;
        MS0(ji);
        fu.clear();
        repd(j,1,q)
        {
            if(qj[j].l<=id&&qj[j].r>=id)
            {
                continue;
            }else
            {
                repd(p,qj[j].l,qj[j].r)
                {
                    ji[p]--;
                }
                fu.push_back(j);
            }
        }
        int jjr=inf;
        int da=-1*inf;
        repd(i,1,n)
        {
            da=max(da,a[i]+ji[i]);
            if((a[i]+ji[i])<jjr)
            {
                jjr=(a[i]+ji[i]);
            }
        }
        if(da-jjr>ans)
        {
            ans=da-jjr;
            aa=fu;
        }
    }
    printf("%d\n",ans );
    printf("%d\n",sz(aa));
    for(auto w:aa)
    {
        printf("%d ", w);
    }
    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == '' '' || ch == ''\n'');
    if (ch == ''-'') {
        *p = -(getchar() - ''0'');
        while ((ch = getchar()) >= ''0'' && ch <= ''9'') {
            *p = *p * 10 - ch + ''0'';
        }
    }
    else {
        *p = ch - ''0'';
        while ((ch = getchar()) >= ''0'' && ch <= ''9'') {
            *p = *p * 10 + ch - ''0'';
        }
    }
}

 

B类-Codeforces Round #535 (Div. 3)C. Nice Garland

B类-Codeforces Round #535 (Div. 3)C. Nice Garland

Codeforces Round #535 (Div. 3)C. Nice Garland

题意：

由‘R‘,‘G‘ and ‘B‘ 三个字母组成的一个字符串，每两个相同的字母需要相差3，找出最小需要交换次数。

分析：

这个字符串的长度大于等于3的时候，一定是RBG这三个字符的某一个排列的循环。
RBG一共最多有6种排列方式{"RGB","RBG","BGR","BRG","GRB","GBR"};

所以直接暴力循环6次即可。

代码：

#include<iostream>
using namespace std;
string dir[6]={"RGB","RBG","BGR","BRG","GRB","GBR"};
int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    int minn=100000000;
    int flag=0;
    //cout<<dir[5][1];
    for(int j=0;j<6;j++){
        int count=0;
        for(int i=0;i<n;i+=3){
            if(s[i]!=dir[j][0]) count++;
            if(i+1 >= n)
            break;
            else if(s[(i+1)]!=dir[j][1]) count++;
            if(i+2 >= n)
            break;
            else if(s[(i+2)]!=dir[j][2]) count++;
        }
        if(count<minn){
            minn=count;
            flag=j;
        }
    }
    cout<<minn<<endl;
    int i;
    for(i=0;i + 3 <n;i+=3){
        cout<<dir[flag];
    }
    int j = 0;
    for(i;i < n;i++)
    cout << dir[flag][j++];
    
    //if(n%3==)
    return 0;
}//比赛结束了几分钟才改好，emmmmmmm，笨死啦。

CF思维联系--CodeForces - 218C E - Ice Skating （并查集）

CF思维联系--CodeForces - 218C E - Ice Skating （并查集）

题目地址：24道CF的DIv2 CD题有兴趣可以做一下。
ACM思维题训练集合
Bajtek is learning to skate on ice. He’s a beginner, so his only mode of transportation is pushing off from a snow drift to the north, east, south or west and sliding until he lands in another snow drift. He has noticed that in this way it’s impossible to get from some snow drifts to some other by any sequence of moves. He now wants to heap up some additional snow drifts, so that he can get from any snow drift to any other one. He asked you to find the minimal number of snow drifts that need to be created.

We assume that Bajtek can only heap up snow drifts at integer coordinates.

Input
The first line of input contains a single integer n (1 ≤ n ≤ 100) — the number of snow drifts. Each of the following n lines contains two integers xi and yi (1 ≤ xi, yi ≤ 1000) — the coordinates of the i-th snow drift.

Note that the north direction coinсides with the direction of Oy axis, so the east direction coinсides with the direction of the Ox axis. All snow drift’s locations are distinct.

Output
Output the minimal number of snow drifts that need to be created in order for Bajtek to be able to reach any snow drift from any other one.

Examples
Input
2
2 1
1 2
Output
1
Input
2
2 1
4 1
Output
0

这道题做过但是不记得当时怎么做的了，每次做都有新的感受。

并查集，一般的并查集不太行，如图因为
代码

#include <bits/stdc++.h>
using namespace std;
int fa[105];
int  find(int n)
{
    if(fa[n]==n) return n;
    else return fa[n]=find(fa[n]);
}
struct Node{
    int x,y;
}node[105];
bool check(Node a,Node b)
{
    if(a.x==b.x) return 1;
    else if(a.y==b.y)return 1;
    else return 0;
}
set<int> cnt;
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        fa[i]=i;
        cin>>node[i].x>>node[i].y;
        for(int j=0;j<i;j++)
        {
            if(check(node[i],node[j])){
              
                fa[find(j)]=find(i);
               // cout<<fa[j]<<endl;
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        //cout<<find(fa[i])<<endl;
        cnt.insert(find(i));
    }
    cout<<cnt.size()-1<<endl;
}

今天关于Nice Garland CodeForces - 1108C 和思维 + 暴力的讲解已经结束，谢谢您的阅读，如果想了解更多关于AND Graph CodeForces - 987F（思维二进制dfs）、Array and Segments (Easy version) CodeForces - 1108E1 （暴力枚举）、B类-Codeforces Round #535 (Div. 3)C. Nice Garland、CF思维联系--CodeForces - 218C E - Ice Skating （并查集）的相关知识，请在本站搜索。

本文标签：

上一篇生产redis client 连接无法释放（redission连接无法释放）

下一篇pyemd资料学习 2019.1.24 https://media.readthedocs.org/pdf/pyemd/latest/pyemd.pdf

相关文章