头像

不得不说




离线:4小时前


最近来访(10)
用户头像
Sundae
用户头像
maodi198911
用户头像
savvym
用户头像
獨孤求敗
用户头像
Phanhom
用户头像
李京泽
用户头像
AcWing2AK
用户头像
不知道吃什么
用户头像
Viator
用户头像
OK_02

活动打卡代码 AcWing 4276. 擅长C


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

char t[26][7][6];
bool is_first = true; // 判断第一个是否为单词,即要不要输出空行

void output(string word)
{
    if(word.empty()) return;

    if(is_first) is_first = false;
    else cout << endl;

    char str[7][60] = {0};
    for(int i = 0;i < word.size();i ++)
        for(int j = 0;j < 7;j ++)
            for(int l = 0; l < 5;l ++)
                str[j][i * 6 + l] = t[word[i] - 'A'][j][l];

    for(int i = 1;i < word.size();i ++)
        for(int j = 0;j < 7;j ++)
            str[j][i * 6 -1] = ' '; // 每第六列添加一个空格
    for(int i = 0;i < 7;i++)
        cout << str[i] << endl;
}


int main()
{
    for(int i = 0; i< 26;i ++)

        for(int j = 0; j<7;j ++)
            scanf("%s",&t[i][j]); 

    string word;
    char p;
    while((p = getchar()) != -1)
    {
        if(p >= 'A' && p <= 'Z') word += p;// 判断输入是否为字母 不是字母就代表结束
        else 
        {
            output(word);
            word = "";
        }
    }
    output(word);
    return 0;
}




(1)首先是找到模式串本身所具有的重复性
(2)根据模式串求出next数组,进而优化成nextval数组
(3)把优化后的nextval数组应用到匹配字符串中去

无标题11.png



活动打卡代码 AcWing 4275. Dijkstra序列

#include<iostream>
#include<cstring>
using namespace std;

const int N = 1010,INF = 0x3f3f3f3f;

int n,m;

int dist[N],g[N][N];

bool s[N];
int q[N];

bool dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    memset(s,0,sizeof s);
    dist[q[0]] = 0;
    for(int i = 0;i < n;i ++)
    {
        int t = q[i];
        for (int j = 1; j <= n; j ++ )
            if (!s[j] && dist[j] < dist[t])
                return false;
        s[t] = true;
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j],dist[t] + g[t][j]);
    }
    return true;
}
int main()
{
    scanf("%d%d",&n,&m);
    memset(g,0x3f,sizeof g);
    while (m -- )
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b] = g[b][a] = c;

    }
    int k;
    scanf("%d",&k);
    while (k -- )
    {
        for(int i = 0;i < n;i ++) scanf("%d",&q[i]);
        if(dijkstra()) puts("Yes");
        else puts("No");

    }
    return 0;
}


活动打卡代码 AcWing 4274. 后缀表达式

#include<iostream>
#include<cstring>
using namespace std;

const int N = 25;

int n;
string v[N];
int l[N],r[N];
bool s[N];
void dfs(int u)
{
    cout << '(';
    if(l[u] != -1 && r[u] != -1)
    {
        dfs(l[u]);
        dfs(r[u]);
        cout << v[u];
    }
    else if (l[u] == -1 && r[u] == -1)
    {
        cout << v[u];
    }
    else 
    {
        cout << v[u];
        dfs(r[u]);
    }
    cout << ')';
}

int main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++)
    {
        cin >> v[i] >> l[i] >> r[i];
        if(l[i] != -1) s[l[i]] = true;
        if(r[i] != -1) s[r[i]] = true;

    }
    int r;
    for(int i = 1;i <= n;i ++)
    {
        if(!s[i])
            r = i;
    }
    dfs(r);
    return 0;
}


活动打卡代码 AcWing 4273. 链表合并

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int h1, h2, n;
int v[N], ne[N];

int main()
{
    scanf("%d%d%d", &h1, &h2, &n);
    while (n -- )
    {
        int addr, val, next;
        scanf("%d%d%d", &addr, &val, &next);
        v[addr] = val, ne[addr] = 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(); 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;
}



活动打卡代码 AcWing 4269. 校庆

#include<iostream>
#include<unordered_set>

using namespace std;

int main()
{
    int n,m;
    cin >> n;
    char str[20];

    unordered_set<string> hash;

    while (n --)
    {
        cin >> str;
        hash.insert(str);

    }
    cin >> m;
    string a,b;
    int cnt = 0;
    while (m --)
    {
        cin >> str;
        string name = str;
        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.c_str();
    else cout << b.c_str();
    return 0;
}


活动打卡代码 AcWing 4268. 性感素数

#include<iostream>
#include<cstring>
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;
}


分享 BFS与DFS

//图的深度优先遍历:从根结点沿着某条路径一直走到底,然后回溯到还能在次遍历的结点
//遍历到一个结点就打印出,然后找到与该结点相邻的下一个结点一直走到底,

int visited[MAX] = { 0 };
void DFS(AdjGraph* G, int v) // v是初始点
{
    ArcNode* p;
    visited[v] = 1; // 置已访问标记
    printf("%d", v);
    p = G->adjlist[v].firdtarc; //p 指向顶点v的第一个邻接点
    while (p != NULL)
    {
        if (visited[p->adjves] == 0) // 若 p -> adjvex 顶点未被访问,递归访问
        {
            DFS(G, p->adjvex);
            p = p->nextarc;   //p 指向顶点v 的下一个邻接点
        }
    }
}


// BFS 宽度优先遍历:从根结点出发,先遍历图中所有和初始点v有路径相通的顶点,然后在进行深一层的遍历

void BFS(AdjGraph* G, int v)
{
    int w, i;
    ArcNode* p;
    SqQueue* qu;   //定义循环队列
    InitQueue(qu);
    int visited[MAXV];// 定义顶点访问标记数组
    for (i = 0; i < G->n; i++) visited[i] = 0; // 把全部数据初始化
    printf("%2d", v);
    visited[v] = 1;//标记已被访问数据
    enQueue(qu, v);
    while (!= QueueEmtype(qu))
    {
        deQueue(qu, w);  // 出队顶点w
        p = G->adhlist[w].firstrac; // 指向w 的第一个邻结点
        while (p != NULL)//找出与w 所有相邻点
        {
            if (visited[p->adjvex] == 0) //若当前结点未被访问
            {
                printf("%2d", p->adjvex);// 访问该结点
                visited[p->adjvex] = 1;// 标记被访问元素
                enQueue(qu, p->adjvex);// 进队
            }
            p = p->nextarc; // 找下一个邻接点
        }
    }
    printf("\n");


}


分享 归并排序

思路:
1.先取中间值 mid = l + r >> 1;
2.merge_sort(q,l,mid), merge_sort(q.mid + 1,r),先递归排序
3.合并两边排序的结果**

c++ 版

#include <iostream>

using namespace std;

const int N = 100010;

int q[N],tmp[N];

void merge_sort(int q[],int l,int r)
{
    if (l>=r) return;

    int mid = l + r >> 1;

    merge_sort(q,l,mid),merge_sort(q,mid+1,r);

    int i=l,j=mid +1,k=0;

    while (i<=mid && j<=r)

        if (q[i]<= q[j]) tmp[k++]=q[i++];

        else  tmp[k++] = q[j++];

    while (i<=mid ) tmp[k++] = q[i++];

    while(j<=r) tmp[k++] =q[j++];

    for (i=l,j=0;i<=r;i++,j++) q[i]= tmp[j];
}

int main()
{
    int n;

    scanf("%d",&n);

    for (int i= 0;i<n;i++) scanf("%d",&q[i]);

    merge_sort (q,0,n-1);

    for (int i=0 ;i<n;i++) printf("%d ",q[i]);

    return 0;

}

c 版

#include<stdio.h>
#include <stdlib.h>
#define N 100010

typedef int ElemType;
int q[N],tmp[N];

int n;
void Merge(ElemType A[],int low,int mid,int high)
{
    ElemType B[N];
    int i,j,k;
    for(k=low;k<=high;k++)//复制元素到B中
        B[k]=A[k];
    for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++)//合并两个有序数组
    {
        if(B[i]<=B[j])
            A[k]=B[i++];
        else
            A[k]=B[j++];
    }
    while(i<=mid)//如果有剩余元素,接着放入即可
        A[k++]=B[i++];
    while(j<=high)
        A[k++]=B[j++];
}
//归并排序不限制是两两归并,还是多个归并
// 1 3 5 7 9
// 2 4
// 1 2 3 4 5 7 9  主要的代码逻辑
void MergeSort(ElemType A[],int low,int high)//递归分割
{
    if(low<high)
    {
        int mid=(low+high)/2;
        MergeSort(A,low,mid);
        MergeSort(A,mid+1,high);
        Merge(A,low,mid,high);
    }
}

int main()
{
    scanf("%d",&n);

    for(int i =0;i < n;i ++) scanf("%d",&q[i]);

    MergeSort(q,0,n - 1);

    for(int i = 0;i < n;i ++) printf("%d ",q[i]);

    return 0;
}



简单选择排序思想 : 一共进行n - 1 趟排序,每趟排序找出最小的一个元素,然后与第k 个元素交换


void swap(int& a, int& b)
{
    int tmp;
    tmp = a;
    a = b;
    b = tmp;
}
void Selectsort(int q[], int n)
{
    int i, j, k; //k 为最小关键字的下标

    for (i = 0; i < n - 1; i++)  // 循环遍历 
    {
        k = i;                   
        for (j = i + 1; j < n; j++) // 在当前无序区 q[i....n -1] 中选出最小的 q[k]
        {
            if (q[j] < q[k])
                k = j;

        }
        if (k != i)
        {
            swap(q[i], q[k]);

        }
    }

}

堆排序(以大根堆为例)的思想 : 根据层次构建二叉树,然后利用大根堆的特性改变二叉树,将根节点变成每颗子树中最大的一个数

222.png

void swap(int& a, int& b)
{
    int tmp;
    tmp = a;
    a = b;
    b = tmp;
}
void Heapsort(int q[], int low, int height)
{
    int i = low, j = 2 * i;// q[j]  为 q[i] 的左孩子
    int tmp = q[i];         //tmp 表示根节点
    while (j <= height)
    {
        if (j < height && q[j] < q[j + 1])  //  若右孩子较大,则把j指向右孩子;
        {
            j++;
        }
        if (tmp < q[j])// 将比根节点大的左孩子或者右孩子移到根节点的位置
        {
            q[i] = q[j];
            i = j;
            j = 2 * i;
        }
        else break;  //若根节点是最大的则退出循环
    }
    q[i] = tmp; //将筛选出的结点放入根节点

}

void HeapSort(int q[], int n)
{
    int i;
    for (i = n / 2; i >= 1; i--) // 循环建立初始堆
        Heapsort(q, i, n);
    for (i = n; i >= 2; i--) // 进行 n -1 趟堆排序,每一趟堆中元素减一
    {
        swap(q[1], q[i]); // 将堆中最后一个元素与根相交换
        Heapsort(q, 1, i - 1);
    }
}