2022夏每日一题（一）

---

一、校庆（哈希）

4269
题意：首先给校友的身份证，再给来宾的身份证，在来宾的身份证里面找校友的身份证，如果有校友，那么输出最年长的，否则，输出来宾中最年长的。

做法：哈希！熟练掌握！
输入样例：

5
372928196906118710
610481197806202213
440684198612150417
13072819571002001X
150702193604190912
6
530125197901260019
150702193604190912
220221196701020034
610481197806202213
440684198612150417
370205198709275042

输出样例：

3
150702193604190912

#include<bits/stdc++.h>

using namespace std;

int main()
{
    
    int n,m;
    cin>>n;
    unordered_set<string>hash;
    while(n--)
    {
    
        string name;
        cin>>name;
        hash.insert(name);
    }
    cin>>m;
    string a,b;
    int cnt=0;
    while(m--)
    {
    
        string name;
        cin>>name;
        if(hash.count(name))
        {
    
            cnt++;
            if(a.empty()||a.substr(6,8)>name.substr(6,8))a=name;
        }
        if(b.empty()||b.substr(6,8)>name.substr(6,8))b=name;
    }
    cout<<cnt<<endl;
    if(cnt)cout<<a<<endl;
    else cout<<b<<endl;
    
    return 0;
}

y总评价非常简单的一道题！

二、性感素数（素数）

4268
题意：给一个数N，如果他是性感素数，那我输出比他小于6的一个数，如果不是的话，那就找到一个比他大的最小性感素数并输出。

线性筛

#include<bits/stdc++.h>

using namespace std;
const int N=100000010;

int n;
int primes[N],cnt;
bool st[N];

void get_primes(int n)//线性筛
{
    
    for(int i=2;i<=n;i++)
    {
    
        if(!st[i])primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++)
        {
    
            st[primes[j]*i]=true;
            if(i%primes[j]==0)break;
        }
    }
}

int main()
{
    
    scanf("%d",&n);
    get_primes(n);
    printf("%d\n",cnt);//输出的是线性筛筛到的最大的素数
    return 0;
}

最后AC代码。

#include<bits/stdc++.h>

using namespace std;

bool is_prime(int x)//判断是否是素数
{
    
    if(x<2)return false;
    for(int i=2;i<=x/i;i++)
        if(x%i==0)
        return false;
    return true;    
}

int main()
{
    
    int n;
    cin>>n;
    for(int i=n-6;i<=n+6;i+=12)
        if(is_prime(i)&&is_prime(n))
    {
    
        cout<<"Yes"<<endl;
        cout<<i<<endl;
        return 0;
    }
    for(int i=n+1;;i++)
        if(is_prime(i)&&(is_prime(i+6)||is_prime(i-6)))
    {
    
        cout<<"No"<<endl;
        cout<<i<<endl;
        return 0;
    }
    
    return 0;
}

三、链表合并（单链表、模拟）

4273
我们当然是转化为数组来做。
题意：就是一个长的链表和一个短的链表，我们将短的链表翻转，然后将短的链表从前往后隔两个插入长的链表。

#include<bits/stdc++.h>

using namespace std;
const int N=100010;
#define x first
#define y second

int h1,h2,n;
typedef pair<int,int>PII;
int v[N],ne[N];

int main()
{
    
    cin>>h1>>h2>>n;
    int add,data,next;
    for(int i=0; i<n; i++)
    {
    
        cin>>add>>data>>next;
        v[add]=data;
        ne[add]=next;
    }

    vector<PII> a,b;
    for(int i=h1; i!=-1; i=ne[i])
    {
    
        a.push_back({
    i,v[i]});
    }
    for(int i=h2; i!=-1; i=ne[i])
    {
    
        b.push_back({
    i,v[i]});
    }
    if(a.size()<b.size())swap(a,b);
    vector<PII>c;
    for(int i=0,j=b.size()-1; i<a.size()||j>=0; i+=2,j--)
    {
    
        c.push_back(a[i]);
        if(i+1<a.size())c.push_back(a[i+1]);
        if(j>=0)c.push_back(b[j]);
    }
    for(int i=0; i<c.size(); i++)
    {
    
        printf("%05d %d ",c[i].x,c[i].y);
        if(i+1<c.size())printf("%05d\n",c[i+1].x);
        else puts("-1");
    }
    return 0;
}

四、后缀表达式（树的遍历）

4274
题意：后序遍历啦！递归调用

#include<bits/stdc++.h>

using namespace std;
const int N=25;
string v[N];
int l[N],r[N],n;
bool st[N];//来判断这个点有没有父节点

void dfs(int rt)
{
    
    cout<<"(";
    if(l[rt]!=-1&&r[rt]!=-1)
    {
    
        dfs(l[rt]);
        dfs(r[rt]);
       cout<<v[rt];
    }
    else if(l[rt]==-1&&r[rt]==-1)
    {
    
        cout<<v[rt];
    }
    else {
    
        cout<<v[rt];
        dfs(r[rt]);
    }
    cout<<")";
}

int main()
{
    
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    
        cin>>v[i]>>l[i]>>r[i];
        if(l[i]!=-1)st[l[i]]=true;
        if(r[i]!=-1)st[r[i]]=true;
    }
    int root;//来记录根节点
    for(int i=1;i<=n;i++)
        if(!st[i])
        root=i;
    dfs(root);

    return 0;
}

五、Dijkstra序列（最短路）

4275
dijstra：每次取得当前距离原点最近的点。即dist[i]最小的的点。那么它的dist序列是递增序列。

这道题目的开头每一次都不一样，所以每一次都要重新算一下。

#include<bits/stdc++.h>

using namespace std;
const int N=1010;
int g[N][N],dist[N];
int n,m;
bool st[N];
int q[N];
bool dijkstra()
{
    
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[q[0]] = 0;
    for (int i = 0; i < n; i ++ )
    {
    
        int t = q[i];
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && dist[j] < dist[t])
                return false;
        st[t] = true;
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }

    return true;
}


int main()
{
    
    cin>>n>>m;
    int a,b,c;
    memset(g,0x3f,sizeof g);
    for(int i=0;i<m;i++)
    {
    
        cin>>a>>b>>c;
        g[a][b]=g[b][a]=c;
    }
    int k;
    cin>>k;
    while(k--)
    {
    
        
        for(int i=0;i<n;i++)
            cin>>q[i];
        if(dijkstra())puts("Yes");
        else puts("No");
    }
    return 0;
}

六、最长算数（双指针、差分）

任意门
题意：给你一个数组，要求你在这个数组找到一个子数组，然后这个要求这个子数组的每相邻的两个数之间的差值是相等的。

双指针可以将我们O(n2)的枚举优化到O(n)

#include<bits/stdc++.h>

using namespace std;
const int N=200010;
int a[N];
int n,t;

int main()
{
    
    cin>>t;
for(int cse=0;cse<t;cse++)
    {
    
        cin>>n;
        for(int i=0;i<n;i++)cin>>a[i];
        int res=0;
        for(int i=0;i<n;i++)
        {
    
            int j=i+2;
            while(j<n&&a[j]-a[j-1]==a[j-1]-a[j-2])j++;
            res=max(res,j-i);
            i=j-2;
        }
        printf("Case #%d: %d\n",cse+1,res);
    }



    return 0;
}