AtCoder Beginner Contest 266「ABCDEF」

A - Middle Letter

题目描述：

给你一个长度为奇数的字符串，输出最中间的字符

思路：

水题

#include 
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];

void work(){
    string s;
    cin >> s;
    cout << s[s.size() / 2] << endl;
}


int main(){
    io;
    work();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

B - Modulo Number

题目描述：

给你一个n，求满足n-x是998244353的倍数的最小的非零数字x

思路：

直接对x取模即可，需要注意负数

#include 
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50

void work(){
    ll n;
    cin >> n;
    cout << (n % mod9 + mod9) % mod9<< endl;
}


int main(){
    io;
    work();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

C - Convex Quadrilateral

题目描述：

给你一个四边形判断是不是凸多边形

思路：

套板子

#include 
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
int x[10];
int y[10];

void work(){
    n = 4;
    for(int i = 1; i <= n; ++i)cin >> x[i] >> y[i];
    x[n+1]=x[1];
    y[n+1]=y[1];
    x[n+2]=x[2];
    y[n+2]=y[2];
    for(int i = 3; i <= n+2; ++i){
        if((x[i]-x[i-2])*(y[i-1]-y[i-2])-(x[i-1]-x[i-2])*(y[i]-y[i-2])>0){
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
}


int main(){
    io;
    work();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

D - Snuke Panic (1D)

题目描述：

现在存在五个坑，下标从0到4，你现在在0的位置，每秒能移动一个距离，也可以不移动

有n个物品，会在时间t[i]的时候出现在x[i]的位置，且价值是a[i]

问你最多能获得的价值最大是多少

思路：

考虑状态机dp

dp[i][j]表示时间为i的时候,位于j的位置能获得的最大价值

可以从三个状态转移过来

• dp[i][j]=dp[i-1][j]，即在第i秒不移动
• dp[i][j]=dp[i-1][j-1],即从j-1移动到j
• dp[i][j]=dp[i-1][j+1]即从j+1移动到j

需要注意的时候，从j+1移动的时候要看i的时候能不能到达j+1，即第二个样例

#include 
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
ll n, m, t, x, a;
ll tr[MAX][5];
ll dp[MAX][5];
void work(){
    cin >> n;
    m = 0;
    for(int i = 1; i <= n; ++i){
        cin >> t >> x >> a;
        tr[t][x] += a;
        m = max(m, t);
    }
    ll ans = 0;
    for(int i = 1; i <= m; ++i){
        for(int j = 0; j < 5; ++j){
            ll c = (i >= j ? tr[i][j] : 0);
            dp[i][j] = max(dp[i - 1][j] + c, dp[i][j]);
            if(j > 0)dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + c);
            if(j < 4)dp[i][j] = max(dp[i][j], dp[i - 1][j + 1] + c);
        }
    }
    for(int i = 0; i < 5; ++i)ans = max(ans, dp[m][i]);
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

E - Throwing the Die

题目描述：

你最多可以扔n次骰子(最大值是6)，得分是你最后一轮扔到的数字，你可以选择在某轮结束后停止游戏，问你的分数的期望值最大是多少

思路：

可以发现，如果你选择继续扔骰子，那前面投的结果不会影响你的分数，所以期望仅取决于你能进行的轮数

假设dp[i]，代表前i轮能得到的最大期望，则

$dp[i]=\frac{1}{6}(max(1,dp[i-1])+max(2,dp[i-1)+max(3,dp[i-1])+max(4,dp[i-1])+max(5,dp[i-1])+max(6,dp[i-1]))$

输出dp[n]即可

#include 
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
double dp[MAX];
void work(){
    cin >> n;
    dp[1] = 3.5;
    for(int i = 2; i <= n; ++i){
        for(int j = 1; j <= 6; ++j){
            if(dp[i-1] < j)dp[i] += j;
            else dp[i] += dp[i - 1];
        }
        dp[i] /= 6.0;
    }
    printf("%.8f\n",dp[n]);
}


int main(){
    io;
    work();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

F - Well-defined Path Queries on a Namori

题目描述：

给你n个点，n条边，进行Q次询问，问x和y之间是否存在两条不同的路径

思路：

n个点，n-1条边会形成一棵树，再此基础上再加一条边，则会形成一个环，我们把这个环扣出来，以环上的每个点为起点往周围非环的上的点去扩展，并用数组记录下来每个点是由环上的哪个点扩展而来的，判断的时候看两个点是否由同一个点扩展而来就行

可以用并查集来判是否联通，然后dfs去记录路径，扩展也可以用dfs

#include 
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 500000 + 50
int n, m, k, x, y;
struct node{
    int x, y;
}ar[MAX];

int tot;
int head[MAX];
struct ran{
    int to, nex;
}tr[MAX];
inline void add(int u, int v){
    tr[++tot].to = v;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int fa[MAX];
int getfa(int x){
    return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}

int lu[MAX];
void dfs(int u, int ff){
//    cout << u << ' ' << ff << endl;
    for(int i = head[u]; i; i = tr[i].nex){
        int v = tr[i].to;
        if(lu[v])continue;
        lu[v] = u;
        dfs(v, u);
    }
}
bool vis[MAX];
int dis[MAX];

void ddfs(int u, int x){
    dis[u] = x;
    for(int i = head[u]; i; i = tr[i].nex){
        int v = tr[i].to;
        if(dis[v])continue;
        ddfs(v, x);
    }
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)fa[i] = i;
    vector<int>v;
    for(int i = 1; i <= n; ++i){
        cin >> ar[i].x >> ar[i].y;
        x = getfa(ar[i].x);
        y = getfa(ar[i].y);
        if(x == y){
            dfs(ar[i].x, -1);
            int p = ar[i].y;
            while(p!=ar[i].x){
                v.push_back(p);
                vis[p] = 1;
                p = lu[p];
            }
            vis[ar[i].x] = 1;
            v.push_back(ar[i].x);
        }
        else fa[x] = y;
        add(ar[i].x, ar[i].y);
        add(ar[i].y, ar[i].x);
    }
    for(auto x : v)dis[x] = x;
    for(auto x : v)ddfs(x, x);
    cin >> m;
    while(m--){
        cin >> x >> y;
        if(dis[x] == dis[y])cout << "Yes\n";
        else cout << "No\n";
    }
}


int main(){
    io;
    work();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98