2022年寒假训练赛第2场

A:a碟的棋盘

题目描述

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

#include
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< 
B：X星人的福利
 
贪心，等待时间短的放前面 
#include
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 
C：递增三元组
 
题目描述 
 
 
在一个无序且可能包含重复数字的正整数序列A中，如果存在三个数字A[i]、A[j]和A[k]，它们满足i 现在给出一个正整数序列，请你编写一个程序找出和最大的递增三元组，输出该三元组中三个数字的和。
 如果在序列A中不存在递增三元组则输出0。
 
 
枚举三元组中间的数，从该数开始，向前查找小于该数最大的数，向后查找大于该数最大的数 
#include 
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
int n;
int a[1005];
int ans;
int findmax1(int d,int pos){//找三元组第一个数
    int ma=0,z=0;
    for(int i=1;ima&&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,z;
    for(int i=2;ia[i]&&x&&z)
        ans=max(ans,a[x]+a[i]+a[z]);
    }
    printf("%dn",ans);
    return 0;
}

 
D：DNA序列拼接
 
题目描述 
 
 
小明最近对由A、G、C、T组成的DNA序列产生了浓厚的兴趣。他想到这样一个问题，如果我们将一个长的DNA序列打散成一些小的DNA片段，能否通过这些小的DNA片段还原出原来的DNA序列。
 假如一个DNA片段的最后三个或三个以上的字符和另一个DNA片段的前面三个或三个以上的字符一样，那么这两个DNA片段可以拼接到一起，例如“ACCGTA”和“GTACG”，它们可以拼接成更长的DNA片段“ACCGTACG”。
 现在给你若干DNA片段，请问它们通过拼接可以得到的DNA序列的最大长度为多少？
 
 
搜索每一个串可以连接到已经搜到的串前和串后拼接字符串时，最长的相同片段拼接 
#include
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("%dn",ans);
    return 0;
}
 
E：9的个数
 
题目描述 
 
 
小明最近遇到一个这样的问题：随机生成n个1-9之间的数字（数字可能有重复），每次可以从中选取若干个数字，使得这些数字的和等于9，每一个随机生成的数字只能选取一次。
 请问如何选取可以使得组成的9的个数最多，请输出最多可以得到的9的个数。
 
 
迭代加深搜索每次搜索length个数可以组成9，length++，直到剩余可选个数小于length数据大不适用 
#include 
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("%dn",ans);
    return 0;
}
 
F：扑克牌接龙游戏
 
题目描述 
 
 
小明最近喜欢上了一种非常简单的扑克牌接龙游戏。
 游戏的玩法是这样的：
 将扑克牌洗牌后平均分为两堆，每人轮流出一张牌进行接龙。如果某个人出的牌的大小和接龙牌堆中一张已有牌的大小相同（不考虑花色），那么他可以将这两张牌以及中间所有的牌全部收走并据为己有。例如：如果在接龙的牌堆中有一个3，你再出一个3，那么这两个3以及它们中间的牌都归你所有。
 两个人依次出牌，最后比谁收到的牌最多即可获胜。
 我们把这个问题稍作简化，如果是一个人在玩这个游戏。现在给你一串数字和字母表示扑克牌的次序，请问最多的一次可以收走多少张牌。
 
 
模拟t表示现在的位置，pos数组记录牌第一次出现的位置，dis数组记录某个位置牌的种类 
#include 
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("%dn",ans);
    return 0;
}
 
G：重复单词
 
题目描述 
 
 
小米的电脑这几天出了一点问题：在输入英文的时候，有一些单词会莫名其妙地在单词的后面重复一次。
 例如：输入“Who are you”，有时候会变成“Who are are you”。
 你能否编写一个程序帮助小米去掉那些相邻的、重复出现的单词中的第二个单词？
 注意：(1) 为了对问题进行简化，在输入数据中均不包含标点符号；(2) 单词之间统一用一个英文的空格隔开；(3) 单词不区分大小写，即"Who"和"who"当做同一个单词看待；(4) 不需要考虑输入数据中本身存在两个单词重复的情况，即只要出现单词重复都需要去掉第二个；(5)对于多个连续出现的重复单词，只需要保留第一个。
 
 
模拟将输入的每一个单词转换成全小写，字符串str记录上一个单词，如果输入单词s与str相同则continue 
#include
using namespace std;
#define ll long long
string turn(string s){
    string s1="";
    for(int i=0;i>s){
        char c = getchar();
        if(str==turn(s))continue;
        else{
            cout< 
H：火烧赤壁
 
题目描述 
 
 
程序员小米同学这几天在看《三国演义》。今天他看到了“火烧赤壁”这一回：诸葛亮在七星坛终于祭来了东南风，老将黄盖带着火药准备对曹 *** 发动火攻。因为曹 *** 的船都用铁链相连，如果其中一条船被火烧着，其他的船都会起火。最终，曹 *** 大败，死伤无数。
 小米看着看着突然想到一个问题：如果当时曹 *** 的船并没有全部连在一起，而只是部分船用铁链连在一起。如果一条船着火，所有与这条船连在一起的船也会着火。假定一共有N条船，这些船的编号分别为1、2、3、…、N。如果1号船着火，并且告诉你哪些船是相连的，请问一共会有多少条船着火？
 
 
图论，连通图vector数组记录每一条无向边 
#include
using namespace std;
#define ll long long
int n,m;
vector g[1005];
bool vis[1005];
int ans;
void dfs(int v){
    vis[v] = true;
    ans++;//每dfs到一个点ans++
    for(int i=0 ;i 
I：X星救援站
 
题目描述 
 
 
X星是宇宙中一个非常敬畏生命和热爱生命的星球。在X星上建有一个规模很大而且设备很先进的救援站。
 为了方便救援工作的开展，X星规定，任意两点之间的一条道路出现问题，都不会完全切断救援站和居民点的通路。也是说救援站到其他顶点都有两条或者两条以上的路线，而且其中某条路线中的一条边出现断开时，至少还可以找到另一条完整的通路。这样在救援过程中，即使某一条路线出现问题，还可以通过其他路线到达目的地。
 已知救援站和部分居民点之间，以及某些居民点之间有直接的道路相连（所有的道路都是双向的）。
 现在请你编写一个程序，根据给出的救援站和居民点之间，以及某些居民点之间的连接信息，判断每一组输入数据是否满足X星的规定。如果满足规则请输出“Yes”，否则输出“No”。
 
 
图论，割边的判断割边: 无向联通图中，去掉一条边，图中的连通分量数增加，也就是说该图不再是连通图，则这条边称为割边关于割点割边的算法详见Tarjan算法 
#include
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("Non");
         else printf("Yesn");
     }
     return 0;
 }
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5710464.html