2020/10/3 天梯赛训练

7-10 最长对称子串 (25分)

题意：给你一行字符串（含空格），求这个字符串里面最长的回文串的长度；

我的思路：先从一个位置出发，向两边便利，如果相等那就加二。

这样有个问题，就是如果是偶数个的话，答案就不对了；

正确思路：从头和尾部同时遍历，然后碰到相同的就通过一个函数来判断中间的字符串是不是回文，是的话就判断这个字符串的长度与当前最大值的大小关系。

#include
using namespace std;
bool check(string &s)
{
    for(int i = 0;i < s.length();i++)
    {
        if(s[i]==s[s.length()-1-i])
            continue;
        else return false;
    }
    return true;
}
int main()
{
    string s1,s2;
    getline(cin,s1);
    int len = s1.length();
    int tans = 0;
    int finans = 0;
    for(int i = 0;i < len;i++)
    {
        for(int j = len-1;j>=i;j--)
        {
            s2 = s1.substr(i,j-i+1);
            if(check(s2))
            {
                tans = s2.length();
            }
            if(tans>finans)
            {
                finans = tans;
            }
        }
    }
    cout<<finans<<endl;
}

7-12 分而治之 (25分)
题意：有n个城市，m个桥，然后给你m行数字，表示两个城市之间已经连桥，然后给你一个数字np表示方案数目，然后就是np行，第一个是要摧毁城市的数量，紧接着就是城市，问摧毁这些城市之后，有没有摧毁所有的桥。
思路：用结构体表示城市，用map来表示城市之间的关系，1为连接，0为未连接。然后遍历一遍map如果有存在等于1的那这个方案就不行。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
struct node
{
    int x,y;
}a[maxn];
int b[maxn];
int main()
{
    int n,m;
    cin>>n>>m;
    int i,j;
    for(i = 0;i < m;i++)
    {
        cin>>a[i].x>>a[i].y;
    }
    int k;
    cin>>k;
    while(k--)
    {
        int np;
        cin>>np;
        map<int ,int > mp;
        for(i = 0;i < np;i++)
        {
            cin>>b[i];
            mp[b[i]] = 1;
        }
        int flag = 1;
        for(i = 0;i < m;i++)
        {
            if(mp[a[i].x] != 1&&mp[a[i].y] != 1)
            {
                cout<<"NO\n";
                flag = 0;
                break;
            }

        }
        if(flag)
            cout<<"YES\n";
    }

}

题意：先给一个节点的初始地址，然后给一个数字，表示结点的数量，然后是n行数据分别是地址，数据和下一个结点的地址，然后从两头输出。
思路：暴力结构体，输入之后进行排序，然后输出

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;

struct Node{
    int ad,next,data;
}mes[maxn],ans[maxn];

int main(){
    int f,n,a;
    scanf("%d%d",&f,&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a);
        scanf("%d%d",&mes[a].data,&mes[a].next);
    }
    int r=1;
    while(f!=-1){
        ans[r].ad=f;
        ans[r++].data=mes[f].data;
        f=mes[f].next;
    }
    for(int i=1;i<r;i++){//调整顺序
        if(i%2==1)
            mes[i]=ans[r-1-i/2];
        else
            mes[i]=ans[i/2];
    }
    for(int i=1;i<r-1;i++){//疯狂输出
        printf("%05d %d %05d\n",mes[i].ad,mes[i].data,mes[i+1].ad);
    }
    printf("%05d %d -1\n",mes[r-1].ad,mes[r-1].data);
    return 0;
}