Consonant Fencity Gym - 101612C 暴力二进制枚举 Intelligence in Perpendicularia Gym

题意1：

给你一个由小写字母构成的字符串s，你可以其中某些字符变成大写字母。如果s中有字母a，你如果想把a变成大写，那s字符串中的每一个a都要变成A

最后你需要要出来所有的字符对，s[i]和s[i-1]需要是辅音字母，且s[i]和s[i-1]中需要一个字母大写另一个小写。a、e、i、o、u、w、y这七个字母是元音

输出最大字符对数量

题解1：

首先预处理一下s字符串中字符相邻的数量，就是记录w[s[i-1]][s[i]]的数量

之后二进制枚举所有字母变成大写的情况。

然后枚举这个字母变成大写之后和其他字母组成成为字符对的数量。也就是结果加上w[x][k]（x是变成大写的字母，k是枚举x和那个字母组成字符对）

那么如果b和c在s字符串中相邻了，然后b和c都变成大写怎么处理？

枚举到b变成大写的时候，x='b'，当k='c'这个时候需要加上w[x][k]。

到下一次枚举到c的时候，x='c'，当k='b'我们判断k是否变成了大写，如果变了，就减去w[x][k]

AC代码：

#include <algorithm>

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <iostream>

#include <map>

#include <queue>

#include <set>

#include <vector>

using namespace std;

typedef long long ll;

const int maxn = 1e6 + 5;

const int mod = 1000000007;

char s[maxn];

int w[150][150],que[150],vis[150];

int main()

{

    freopen("consonant.in","r",stdin);

    freopen("consonant.out","w",stdout);

    scanf("%s",s);

    int len=strlen(s);

    if(len==1)

    {

        printf("%s\n",s);

        return 0;

    }

    for(int i=1;i<len;++i)

    {

        w[s[i-1]][s[i]]++;

    }

    int pos=0;

    for(int i='a';i<='z';++i)

    {

        if(i=='a' || i=='e' || i=='o' || i=='u' || i=='i' || i=='w' || i=='y')

            continue;

        que[pos++]=i;

    }

    //printf("%d***\n",pos);

    int ans=0,flag=0;

    for(int i=0;i<(1<<pos);++i)

    {

        int sum=0;

        memset(vis,0,sizeof(vis));

        for(int j=0;j<pos;++j)

        {

            if((1<<j)&i)

            {

                for(int k='a';k<='z';++k)

                {

                    if(k=='a' || k=='e' || k=='o' || k=='u' || k=='i' || k=='w' || k=='y' || k==que[j])

                        continue;

                    if(vis[k])

                    {

//                        if(i==1026)

//                        {

//                            printf("********%c %c %d %d\n",k,que[j],w[k][que[j]],w[que[j]][k]);

//                        }

                        sum-=w[k][que[j]];

                        sum-=w[que[j]][k];

                    }

                    else

                    {

//                        if(i==1026)

//                        {

//                            printf("%c %c %d %d\n",k,que[j],w[k][que[j]],w[que[j]][k]);

//                        }

                        sum+=w[k][que[j]];

                        sum+=w[que[j]][k];

                    }

                }

                vis[que[j]]=1;

            }

        }

        if(ans<sum)

        {

            ans=sum;

            flag=i;

        }

//        printf("%d***\n",sum);

//        system("pause");

    }

    memset(vis,0,sizeof(vis));

    for(int i=0;i<pos;++i)

    {

        if((1<<i)&flag)

        {

            vis[que[i]]=1;

        }

    }

    for(int i=0;i<len;++i)

    {

        if(vis[s[i]])

            printf("%c",s[i]-32);

        else printf("%c",s[i]);

    }

    printf("\n");

    return 0;

}

题意2：

按顺序给你n个点，表示第i个点和第i-1个点相连，第1个点和第n个点相连。

题目保证所有连线和x或者y轴平行。让你输出n个点构成的图形看不到区域的长度

题解：

首先设这n个点构成的图形周长为x，后面使用x-大矩形周长就是答案

大矩形周长：就是把图形补全之后的外层大矩形的周长

代码：

#include <algorithm>

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <iostream>

#include <map>

#include <queue>

#include <set>

#include <vector>

using namespace std;

typedef long long ll;

const int maxn = 1e3 + 5;

const int INF=0x3f3f3f3f;

const int mod = 1000000007;

struct Node

{

    int x,y;

}node[maxn];

int main()

{

    freopen("intel.in","r",stdin);

    freopen("intel.out","w",stdout);

    int n;

    scanf("%d",&n);

    for(int i=1;i<=n;++i)

    {

        scanf("%d%d",&node[i].x,&node[i].y);

    }

    int ans=0,minnx=INF,minny=INF,maxxx=0,maxxy=0;

    node[n+1]=node[1];

    for(int i=2;i<=n+1;++i)

    {

        minnx=min(minnx,node[i].x);

        minny=min(minny,node[i].y);

        maxxx=max(maxxx,node[i].x);

        maxxy=max(maxxy,node[i].y);

        if(node[i-1].x==node[i].x)

        {

            ans+=abs(node[i].y-node[i-1].y);

        }

        else if(node[i-1].y==node[i].y)

        {

            ans+=abs(node[i].x-node[i-1].x);

        }

    }

    printf("%d\n",ans-((maxxx-minnx)*2+(maxxy-minny)*2));

    return 0;

}

/*

10

1 1

6 1

6 4

3 4

3 3

5 3

5 2

2 2

2 3

1 3

*/

巴特西

Consonant Fencity Gym - 101612C 暴力二进制枚举 Intelligence in Perpendicularia Gym - 101612I 思维

最新文章

热门文章