[C++知识库]2022年寒假训练赛第2场

A:a碟的棋盘

• 题目描述

a碟家里有一副国际象棋，他发现国际象棋的棋盘是黑白相间的。
国际象棋的棋盘是8*8大小的，不过他现在想让你打印出一个n(n为偶数)的国际象棋棋盘。
我们用字符’1’表示黑格，'0’表示白格。
棋盘左上角的格子为白格
规定与白格相邻的格子全部为黑格，与黑格相邻的格子全部为白格。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    int n;
    while(~scanf("%d",&n)){
            string s1="",s2="";
        for(int i=1;i<=n/2;i++){
            s1+="01";
            s2+="10";
        }
 
        for(int i=1;i<=n;i++){
            if(i&1)cout<<s1<<endl;
            else cout<<s2<<endl;
        }
    }
    return 0;
}

B：X星人的福利

• 贪心，等待时间短的放前面

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    int n;
    int a[1005];
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    int ans=0;
    for(int i=1;i<n;i++)
        ans+=a[i]*(n-i);
    printf("%.2lf\n",1.0*ans/n);
 
}

C：递增三元组

• 题目描述

在一个无序且可能包含重复数字的正整数序列A中，如果存在三个数字A[i]、A[j]和A[k]，它们满足i<j<k（i、j和k为三个数字在序列A中出现的位置），且A[i]<A[j]<A[k]，则称这三个数为一个递增三元组。
需要注意的是递增三元组中的三个数字不要求连续出现，例如：在正整数序列{1,2,3,4,5}中，(1,3,5)是一个满足要求的递增三元组。
现在给出一个正整数序列，请你编写一个程序找出和最大的递增三元组，输出该三元组中三个数字的和。
如果在序列A中不存在递增三元组则输出0。

• 枚举前两个数，在找后面最大的一个，注意判断一下三个数不能连续
• 本来想搜索结果超时了，没想到暴力居然可以

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
int n;
int a[1005];
int ans;
int findmax(int d){
    int ma=0,z;
    for(int i=d;i<=n;i++)
    if(a[i]>ma){
        ma=a[i];
        z=i;
    }
    return z;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int x,y,z;
    for(int i=1;i<n;i++)
        for(int j=i+1;j<n;j++){
            if(a[j]<=a[i])continue;
            x=i,y=j;
            z=findmax(j+1);
            if(a[z]>a[j]&&(x!=y-1||y!=z-1))
            ans=max(ans,a[x]+a[y]+a[z]);
        }
    printf("%d\n",ans);
    return 0;
}

D：DNA序列拼接

• 题目描述

小明最近对由A、G、C、T组成的DNA序列产生了浓厚的兴趣。他想到这样一个问题，如果我们将一个长的DNA序列打散成一些小的DNA片段，能否通过这些小的DNA片段还原出原来的DNA序列。
假如一个DNA片段的最后三个或三个以上的字符和另一个DNA片段的前面三个或三个以上的字符一样，那么这两个DNA片段可以拼接到一起，例如“ACCGTA”和“GTACG”，它们可以拼接成更长的DNA片段“ACCGTACG”。
现在给你若干DNA片段，请问它们通过拼接可以得到的DNA序列的最大长度为多少？

• 搜索
• 每一个串可以连接到已经搜到的串前和串后
• 拼接字符串时，最长的相同片段拼接

#include<bits/stdc++.h>
using namespace std;
string s[15];
int n;
int ans;
string turn(string s1,string s2)//s1串后连s2前
{
    if(s1=="")return s2;
    else if(s2=="")return s1;
    int len=min(s1.size(),s2.size());
    while(len>=3){
        string str="";
        string sub1=s1.substr(s1.size()-len);//截取s1串后len长的子串
        string sub2=s2.substr(0,len);//截取s2串前len长的子串
        if(sub1==sub2){//可以拼接
            str=s1;
            str+=s2.substr(len,s2.size()-len);
            return str;
        }
        len--;
    }
    return "";
}
void dfs(string str,int dis[]){
    int len=str.size();
    ans=max(ans,len);
    for(int i=1;i<=n;i++){
        if(dis[i])continue;
        string s1=turn(str,s[i]);//s[i]拼在str后
        string s2=turn(s[i],str);//s[i]拼在str前
        dis[i]=1;
        if(s1!="")dfs(s1,dis);//不为空说明可以拼接
        if(s2!="")dfs(s2,dis);
        dis[i]=0;
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>s[i];
    int dis[15]={0};
    dfs("",dis);
    printf("%d\n",ans);
    return 0;
}

E：9的个数

• 题目描述

小明最近遇到一个这样的问题：随机生成n个1-9之间的数字（数字可能有重复），每次可以从中选取若干个数字，使得这些数字的和等于9，每一个随机生成的数字只能选取一次。
请问如何选取可以使得组成的9的个数最多，请输出最多可以得到的9的个数。

• 迭代加深搜索
• 每次搜索length个数可以组成9，length++，直到剩余可选个数小于length
• 数据大不适用

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define mem(a) memset(a,0,sizeof(a))
int n;
int k;
int ans;
int a[25];
bool vis[25];
int length;
bool dfs(int num,int sum,bool dis[]){
    if(num==length){
        if(sum==9){
            k-=length;
            ans++;
            return 1;
        }
        else return 0;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]&&!dis[i]){
            dis[i]=1;
            if(dfs(num+1,sum+a[i],dis)){
                vis[i]=1;
                if(num!=0)return 1;
            }
            dis[i]=0;
        }
    }
    return 0;
}
int main(){
    while(~scanf("%d",&a[++n])){
        if(a[n]==9){//存在9个数加一
            ans++;
            n--;}
    }
    length=2;
    bool dis[25];
    k = n;
    while(k>=length){
        memcpy(dis,vis,sizeof(vis));
        dfs(0,0,dis);
        ++length;
    }
    printf("%d\n",ans);
    return 0;
}

F：扑克牌接龙游戏

• 题目描述

小明最近喜欢上了一种非常简单的扑克牌接龙游戏。
游戏的玩法是这样的：
将扑克牌洗牌后平均分为两堆，每人轮流出一张牌进行接龙。如果某个人出的牌的大小和接龙牌堆中一张已有牌的大小相同（不考虑花色），那么他可以将这两张牌以及中间所有的牌全部收走并据为己有。例如：如果在接龙的牌堆中有一个3，你再出一个3，那么这两个3以及它们中间的牌都归你所有。
两个人依次出牌，最后比谁收到的牌最多即可获胜。
我们把这个问题稍作简化，如果是一个人在玩这个游戏。现在给你一串数字和字母表示扑克牌的次序，请问最多的一次可以收走多少张牌。

• 模拟
• t表示现在的位置，pos数组记录牌第一次出现的位置，dis数组记录某个位置牌的种类

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int pos[100005],dis[100005];
char c[5];
int main(){
    int n;
    scanf("%d",&n);
    int t=1,ans=0,x;
    for(int i=1;i<=n;i++){
        scanf("%s",&c);
        x=dis[t]=c[0]-'0';
        if(pos[x]&&t>pos[x]&&dis[pos[x]]==x){
            ans=max(ans,t-pos[x]+1);
            t=pos[x];
        }
        else pos[x]=t++;
    }
    printf("%d\n",ans);
    return 0;
}

G：重复单词

• 题目描述

小米的电脑这几天出了一点问题：在输入英文的时候，有一些单词会莫名其妙地在单词的后面重复一次。
例如：输入“Who are you”，有时候会变成“Who are are you”。
你能否编写一个程序帮助小米去掉那些相邻的、重复出现的单词中的第二个单词？
注意：(1) 为了对问题进行简化，在输入数据中均不包含标点符号；(2) 单词之间统一用一个英文的空格隔开；(3) 单词不区分大小写，即"Who"和"who"当做同一个单词看待；(4) 不需要考虑输入数据中本身存在两个单词重复的情况，即只要出现单词重复都需要去掉第二个；(5)对于多个连续出现的重复单词，只需要保留第一个。

• 模拟
• 将输入的每一个单词转换成全小写，字符串str记录上一个单词，如果输入单词s与str相同则continue

#include<bits/stdc++.h>
using namespace std;
#define ll long long
string turn(string s){
    string s1="";
    for(int i=0;i<s.size();i++)
        if(isupper(s[i]))s1+=s[i]+32;
        else s1+=s[i];
    return s1;
}
int main(){
    string s;
    string str="";
    while(cin>>s){
        char c = getchar();
        if(str==turn(s))continue;
        else{
            cout<<s;
            if(c=='\n'){
                cout<<endl;
                break;
            }
            else cout<<" ";
        }
        str=turn(s);//更新上一个单词
    }
    return 0;
}

H：火烧赤壁

• 题目描述

程序员小米同学这几天在看《三国演义》。今天他看到了“火烧赤壁”这一回：诸葛亮在七星坛终于祭来了东南风，老将黄盖带着火药准备对曹操发动火攻。因为曹操的船都用铁链相连，如果其中一条船被火烧着，其他的船都会起火。最终，曹操大败，死伤无数。
小米看着看着突然想到一个问题：如果当时曹操的船并没有全部连在一起，而只是部分船用铁链连在一起。如果一条船着火，所有与这条船连在一起的船也会着火。假定一共有N条船，这些船的编号分别为1、2、3、…、N。如果1号船着火，并且告诉你哪些船是相连的，请问一共会有多少条船着火？

• 图论，连通图
• vector数组记录每一条无向边

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
vector<int> g[1005];
bool vis[1005];
int ans;
void dfs(int v){
    vis[v] = true;
    ans++;//每dfs到一个点ans++
    for(int i=0 ;i<g[v].size();i++)
        {
            if(!vis[g[v][i]])
                dfs(g[v][i]);
        }
}
int main(){
    scanf("%d%d",&n,&m);
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1);
    printf("%d\n",ans);
    return 0;
}

I：X星救援站

• 题目描述

X星是宇宙中一个非常敬畏生命和热爱生命的星球。在X星上建有一个规模很大而且设备很先进的救援站。
为了方便救援工作的开展，X星规定，任意两点之间的一条道路出现问题，都不会完全切断救援站和居民点的通路。也是说救援站到其他顶点都有两条或者两条以上的路线，而且其中某条路线中的一条边出现断开时，至少还可以找到另一条完整的通路。这样在救援过程中，即使某一条路线出现问题，还可以通过其他路线到达目的地。
已知救援站和部分居民点之间，以及某些居民点之间有直接的道路相连（所有的道路都是双向的）。
现在请你编写一个程序，根据给出的救援站和居民点之间，以及某些居民点之间的连接信息，判断每一组输入数据是否满足X星的规定。如果满足规则请输出“Yes”，否则输出“No”。

• 图论，割边的判断
• 割边: 无向联通图中，去掉一条边，图中的连通分量数增加，也就是说该图不再是连通图，则这条边称为割边
• 关于割点割边的算法详见Tarjan算法

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=100005;
int n,m,h,firs[maxn],low[maxn],id[maxn],cnt,x,y,ed;
struct edge{
    int too,nex;
}g[maxn<<1];

void dfs (int x,int las){
    int j;
    low[x]=id[x]=++cnt;
     for (int i=firs[x];i;i=g[i].nex){
         j=g[i].too;
         if(i==(las^1)) continue;
        if(!id[j]) dfs(j,i);
        low[x]=min(low[x],low[j]);
        if(low[j]>id[x]) ed++;
     }
 }

void add (int x,int y){
   g[++h].nex=firs[x];
    firs[x]=h;
     g[h].too=y;
 }

int main(){

    int T;
    scanf("%d",&T);
     while(T--){
        scanf("%d%d",&n,&m);
         h=1;
         cnt=ed=0;
         memset(firs,0,sizeof(firs));
         memset(id,0,sizeof(id));
         memset(low,0,sizeof(low));
         for (int i=1;i<=m;++i){
             scanf("%d%d",&x,&y);
             add(x,y);
            add(y,x);
         }
         for (int i=1;i<=n;++i)
             if(!id[i]) dfs(i,-1);
         if(ed)printf("No\n");
         else printf("Yes\n");
     }
     return 0;
 }