AtCoder ABC 244

A - Last Letter(语法)

Description:

? 输出给定字符串的最后一个字符

Resolution

? 过水

Code:

void solve()
{
	int n;
    string s;
    cin >> n;
    cin >> s;
    cout << s[n - 1];
}

B - Go Straight and Turn Right(模拟)

Description:

? 对于给定操作序列 S向前走一步 R顺时针转向初始坐标是0 0 输出操作序列结束时的坐标

Resolution

? 写出方向偏移量然后模拟注意的是使转向环形进行

Code:

int dx[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}}; //0 1 2 3
char s[100010];
 
void solve()
{
	int n;
    cin >> n;
    cin >> s;
    int st = 0;
    PII res = {0, 0};
    for(int i = 0; i < n; i++)
    {
        if(s[i] == 'S')     res.first += dx[st][0], res.second += dx[st][1];
        else if(s[i] == 'R')  st = (st == 3) ? 0 : st + 1;
    }
    cout << res.first << " " << res.second;
}

C - Yamanote Line Game(交互 + 简单模拟)

Description:

? 首先 A会给你一个数n 然后B和A交替输出一个[1， 2 * n + 1]之间未被输出过的数

? 最后一个没有数输出的人只能输出0

? 题目告诉你 B 一定获胜所以请你模拟B的输出来完成这个game (A是一个编写好的程序他会随机应变)

? 切记当最后A输出0之后要记得return 0 不然会TLE

Resolution

? 读题卡了好久应该抓住重点确定比如循环次数的次数

? 因为2 * n + 1是奇数又因为B先输出所以B一定能获胜

? 策略：B每次直接找[1, 2 * n + 1]中没有被输出的数输出即可

Code:

bool st[1010];
 
void solve()
{
	int n, x;
    cin >> n;
    cout << 1 << '\n';
    st[1] = 1;
    
    for(int i = 1; i <= n + 1; i++)
    {
        cin >> x;
        if(x == 0)  return;
 
        st[x] = 1;
        for(int i = 1; i <= 2 * n + 1; i++)
        {
            if(st[i] == false)
            {
                st[i] = 1;
                cout << i << '\n';
                break;
            }
        }
    }
}

D - Swap Hats(思维)

Description:

? 给定3个字母R G B组成的序列为标准排列

? 再给定3个字母R G B组成的序列为当前排列

? 请问是否能够经过1e18的交换次数使当前排列恢复成标准排列交换可以任意位置互换

Resolution

? 简化问题为经过偶数次排序能还原的都没问题经过奇数次还原的不行

? 想到这里就很容易实现了

Code:

void solve()
{
    char c;
	for(int i = 0; i < 3; i++)
    {
        cin >> c;
        mp[c] = i;
    }
 
    int res = 0;
    for(int i = 0; i < 3; i++)
    {
        cin >> c;
        if(i != mp[c])     res ++;
    }
    if(res == 2)    puts("No"); //奇数次交换
    else puts("Yes");
}

E - King Bombee(图论 + DP)

Description:

? 给出一张无向图请问起点为编号s 终点为编号t 且长度为len 含有奇数个数个X的路径有多少个

Resolution

? 可以想到计数DP的思路然后用记忆化搜索根据题意爆搜就可以过了

Code:

const int mod = 998244353;
int n, m, k, s, t, x;
vector<int> edge[2010];
int dp[2010][2010][2]; //长度 当前节点 X出现次数奇偶
 
int dfs(int step, int u, int is_even) //长度 当前节点 是奇数1 偶数0
{
    if(step == k)   return u == t && is_even; //满足条件就返回1
    if(dp[step][u][is_even] != -1)   return dp[step][u][is_even]; //记忆化搜索
    int res = 0;
    
    for(auto v : edge[u])
        res = (res + dfs(step + 1, v, is_even ^ (v == x))) % mod; //0 变 1 1 变 0 
        
    dp[step][u][is_even] = res;
    return res;
}
 
void solve()
{
    cin >> n >> m >> k >> s >> t >> x;
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v; //无向图
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
 
    memset(dp, -1, sizeof dp);
    cout << dfs(0, s, 1) << '\n';
}