$\color{Orange}{题目1：字符串匹配}$

题目标签

水题不多叭叭

题目描述

题目描述：对于主串M和模式串P，找到P在M中出现的所有子串
的第一个字符在P中的位置。P中第一个字符所在的位置为0。
首行的数字表示有多少组字符串。

输入样例：

2
ababababa
ababa
aaa
aa

输出样例：

0 2 4
0 1

原题链接

参考代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char str1[100],str2[100];
int main()
{
    int n;
    scanf("%d",&n);
    while(n--){
        memset(str1,0,sizeof(str1));
        memset(str2,0,sizeof(str2));
        scanf("%s",str1);
        scanf("%s",str2);
        int len1=strlen(str1);
        int len2=strlen(str2);
        int idx;
        for(int i=0;i<len1;i++){
            if(str1[i]!=str2[0])
              continue;
            idx=i;
            if(len1-i<len2)break;
            for(int j=0;j<len2;j++){
                if(str1[i]!=str2[j])
                    break;
                i++;
                if(j=len2-1)
                    printf("%d ",idx);
            }
            i=idx;
        }
    }
    system("pause");
    return 0;
}

$\color{Orange}{题目2：A Famous ICPC Team}$

题目标签

希望2023也这么简单

题目描述

给出四个正方体箱子的边长，问能装下这四个正方体箱子
的大正方体边长最小要多大，要求边长最小且必须能装下四个箱子。

输入样例：

2 2 2 2

输出样例：

4

原题链接

参考代码

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int main()
{
    int a[4],cas = 1;
    int x,y,ans;
    while(~scanf("%d%d%d%d",&a[0],&a[1],&a[2],&a[3]))
    {
        sort(a,a+4);
        printf("Case %d: %d\n",cas++,a[2]+a[3]);
    }
    return 0;
}

$\color{Orange}{题目3：A Famous Grid.}$

题目标签

记得复习图兄弟，我仍了这题，题解来自网络

题目描述

Mr. B has recently discovered the grid named “spiral grid”.
Construct the grid like the following figure. (The grid is ac
tually infinite. The figure is only a small part of it.)
Considering traveling in it, you are free to any cell containing 
a composite number or 1, but traveling to any cell containing a
prime number is disallowed. You can travel up, down, left or right,
but not diagonally. Write a program to find the length of the shortest 
path between pairs of nonprime numbers, or report it’s impossible.
大概意思给一个表，问两个位置之间的最短距离是多少，其中素数位置不能经过。

图片贴在评论区

输入样例：

3
1 4
9 32
10 12

输出样例：

Case 1: 1
Case 2: 7
Case 3: impossible

原题链接

参考代码

#include <iostream>
#include <string>
#include <cstring>
#include <cctype>
#include <cstdio>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <algorithm>
#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3
using namespace std;
const int maxn=410;
int g[maxn][maxn];
int vis[maxn][maxn];
const int mov[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};
bool isPrime(int v)
{
    int ed=sqrt(v);
    for(int i=2; i<=ed; ++i)
        if(v%i==0) return false;
    return true;
}
int nextDir(int d)
{
    if(d==RIGHT) return UP;
    else if(d==UP) return LEFT;
    else if(d==LEFT) return DOWN;
    else if(d==DOWN) return RIGHT;
}
pair<int,int> pos[10005];
void init()
{

    int val=0;
    int x=200,y=200;
    g[x][y]=++val;
    pos[val]=make_pair(x,y);
    int d=RIGHT;
    int len=2;
    while(len<=105)
    {
        for(int i=1; i<len; ++i)
        {
            x=x+mov[d][0];
            y=y+mov[d][1];
            ++val;
            if(isPrime(val)) g[x][y]=0;
            else
            {
                g[x][y]=val;
                if(val<=10000)
                    pos[val]=make_pair(x,y);
                }
        }
        d=nextDir(d);
        for(int i=1; i<len; ++i)
        {
            x=x+mov[d][0];
            y=y+mov[d][1];
            ++val;
            if(isPrime(val)) g[x][y]=0;
            else
            {
                g[x][y]=val;
                if(val<=10000)
                    pos[val]=make_pair(x,y);
                }

        }
        d=nextDir(d);
        ++len;
    }

}

int bfs(int st,int ed)
{

    memset(vis,0,sizeof(vis));
    queue<pair<int,int> > que;
    que.push(pos[st]);
    while(!que.empty())
    {
        pair<int,int> p=que.front();
        que.pop();
        for(int i=0; i<4; ++i)
        {
            int nx=p.first+mov[i][0],ny=p.second+mov[i][1];
            if(vis[nx][ny]||g[nx][ny]==0) continue;
            vis[nx][ny]=vis[p.first][p.second]+1;
            if(g[nx][ny]==ed) return vis[nx][ny];
            que.push(make_pair(nx,ny));
        }
    }
    return -1;
}
int main()
{
    init();
    int x,y,kase=0;
    while(scanf("%d%d",&x,&y)!=EOF)
    {
        printf("Case %d: ",++kase);
        if(x==y) printf("0\n");
        else
        {
            int ans=bfs(x,y);
            if(ans==-1) puts("impossible");
            else printf("%d\n",ans);
        }
    }
    return 0;
}