2023年9月4日

第一次！第一次！第一次！AK,ACWING周赛

ACWING5143 字符串还原

题目理解

第一个输出，第二个开始，一个输出一个不输出。

代码实现

#include<iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;
    string s;

    while(n -- )
    {
        cin >> s;

        cout << s[0];

        int flag = 1;
        for(int i = 1; i < s.size(); i++)
            if(flag)
            {
                cout << s[i];
                flag = 0;
            }
            else
                flag = 1;
        cout << endl;
    }

    return 0;
}

ACWING5144 英文数字

题目理解

就是翻译题，hhh

代码实现

#include<iostream>
using namespace std;

const int N = 100;
string a[N] = {"ten", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine",
};

string b[N] = {"", "ten", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety"};
string c[N] = {"twenty", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen",
                "seventeen", "eighteen", "nineteen"};



int main()
{

    int n;
    cin >> n;

    if(n >= 1 && n <= 10) cout << a[n % 10];
    else if(n >= 11 && n <= 20) cout << c[n % 10];
    else if(n % 10 == 0 && n != 0) cout << b[n / 10];
    else if(n >= 21)cout << b[n  / 10] << "-" << a[n % 10];
    else if(n == 0) cout << "zero";
    return 0;
}

ACWING5145 同色环

题目理解

dfs，上下左右进行走，只要能回到起点就行！！！！
减枝思路：

越界剪掉
回头路剪掉
不相等不让走
小于4步回到起点

代码实现

#include<iostream>
#include<cstring>

using namespace std;

int n, m;
const int N = 60;
int a[N][N];
bool st[N][N];
string s;
int flagi = 1, flagj = 1, flag = 0;

void dfs(int i, int j, int step)
{
    st[i][j] = true;
     
    if(i == flagi && j == flagj && step >= 4)
        flag = 1;
    
    if(i == flagi && j == flagj && step != 1)   // 回到起点也得
        return;
    
    if(i < 1 || i > n || j < 1 || j > m) //越界了
        return;
    
    //往上走
    if( a[i - 1][j] == a[flagi][flagj] && !st[i-1][j] || i - 1 == flagi && j == flagj)
        dfs(i - 1, j, step + 1);
    
    //往下走
    if( a[i + 1][j] == a[flagi][flagj] && !st[i+1][j] || i + 1 == flagi && j == flagj)
        dfs(i + 1, j, step + 1);
    
    //往左走
    if( a[i][j - 1] == a[flagi][flagj] && !st[i][j-1] || i == flagi && j - 1 == flagj)
        dfs(i, j - 1, step + 1);
    
    //往右走
    if( a[i][j + 1] == a[flagi][flagj] && !st[i][j+1] || i == flagi && j + 1 == flagj)
        dfs(i, j + 1, step + 1);
    
}

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i++)
    {
        cin >> s;
        for(int j = 0; j < m; j++)
            a[i][j + 1] = (int)(s[j]) - 64;
    }
    
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
           memset(st, 0, sizeof st);
            flagi = i, flagj = j;
            dfs(i, j, 1);
        }

    
    if(flag)
        cout << "Yes";
    else
        cout << "No";
    return 0;
}