代码编织梦想

A.Three Threes(循环)

题意:

给出一个正整数 N N N,要求输出 N N N N N N

分析:

按要求输出即可

代码:

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cout << n;
    }
    cout << endl;
}

int main() {
    solve();
    return 0;
}

B.Pentagon(判断)

题意:

给出正五边形上四个顶点 S 1 , S 2 , T 1 , T 2 ( S 1 ≠ S 2 , T 1 ≠ T 2 ) S_1,S_2, T_1,T_2(S_1 \ne S_2, T_1 \ne T2) S1,S2,T1,T2(S1=S2,T1=T2),问 S 1 S_1 S1 S 2 S_2 S2连成的线端长度与 T 1 T_1 T1 T 2 T_2 T2之间连成的线段长度是否相等。

分析:

正五边形任意两点之间的距离分以下两种:

  • 两点相邻

  • 两点不相邻

判断两条线段是否属于同一类型即可。

代码:

#include <bits/stdc++.h>
using namespace std;

void solve() {
    string s, t;
    cin >> s >> t;
    int s1 = s[0] - 'A';
    int s2 = s[1] - 'A';
    int t1 = t[0] - 'A';
    int t2 = t[1] - 'A';
    int len1 = 0, len2 = 0;
    if (abs(s2 - s1) != 1 && abs(s2 - s1) != 4) len1 = 1;
    if (abs(t2 - t1) != 1 && abs(t2 - t1) != 4) len2 = 1;
    if (len1 == len2) {
        cout << "Yes" << endl; 
    } else {
        cout << "No" << endl;
    }
}

int main() {
    solve();
    return 0;
}

C.Repunit Trio(预处理)

题意:

有一个序列,里面每个数字均由若干个 1 1 1组成,如 1 , 11 , 111 , . . . 1, 11, 111,... 1,11,111,...,问任取该序列中的三个数字(每个数字可重复取)加在一起组成的所有数字中第 N N N小的数字是多少?

分析:

先预处理由 1 1 1组成的数字。

然后使用三场循环枚举能组成的数字。

枚举结束后排序去重,并输出第 N N N小的数字即可。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

vector<LL> ans, num;

void solve() {
    LL val = 0;
    for (int i = 1; i <= 15; i++) {
        val = val * 10 + 1;
        num.push_back(val);
    }
    for (int i = 0; i <= 14; i++) {
        for (int j = 0; j <= 14; j++) {
            for (int k = 0; k <= 14; k++) {
                ans.push_back(num[i] + num[j] + num[k]);
            }
        }
    }
    ans.push_back(0);//加个0,把存储答案的下标修改为从1开始
    sort(ans.begin(), ans.end());
    int len = unique(ans.begin(), ans.end()) - ans.begin();
    int n;
    cin >> n;
    cout << ans[n] << endl;
}

int main() {
    solve();
    return 0;
}

D.Erase Leaves(贪心)

题意:

给出一棵树,允许进行若干次如下操作:

  • 选择一个叶节点,并将该叶节点删除

问:至少需要操作多少次,才能将节点 1 1 1删除。

分析:

想要让 1 1 1成为叶节点,那么必然需要将1连着的边删除到只剩一条。而想要删除每一条边实际上需要将该边连接的整棵子树全部删除才行,那么最后留下的那条边连接的子树一定为 1 1 1的最大子树。

1 1 1为根节点进行遍历,记录每个节点的子树大小,最后的答案就是连接 1 1 1 k k k棵子树中除最大的子树外的所有子树节点之和,再加上最后删除节点 1 1 1的操作次数。

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 3e5 + 5e2;

vector<int> G[N];
int sz[N];

void dfs(int root, int pre) {
    sz[root] = 1;
    int len = G[root].size();
    for (int i = 0; i < len; i++) {
        int v = G[root][i];
        if (v != pre) {
            dfs(v, root);
            sz[root] += sz[v];
        }
    }
}

vector<int> child;

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, -1);
    int len = G[1].size();
    for (int i = 0; i < len; i++) {
        child.push_back(sz[G[1][i]]);
    }
    sort(child.begin(), child.end());
    int ans = 0;
    for (int i = 0; i < len - 1; i++) {
        ans += child[i];
    }
    cout << ans + 1 << endl;
}

int main() {
    solve();
    return 0;
}

E.Takahashi Quest(贪心)

题意:

冒险家在冒险过程中,将遇到 N N N个事件。第 i i i个事件 ( 1 ≤ i ≤ N ) (1≤i≤N) 1iN用一对整数 ( t i , x i ) (t_i,x_i) ti,xi表示 ( 1 ≤ t i ≤ 2 , 1 ≤ x i ≤ N ) (1≤t_i≤2,1≤x_i≤N) (1ti2,1xiN)

每个事件的含义如下:

  • 如果 t i = 1 t_i=1 ti=1,他找到了 x i x_i xi类型的药剂。他可以选择捡起它或丢弃它。
  • 如果 t i = 2 t_i=2 ti=2,他会遇到一个 x i x_i xi类型的怪物。

如果他有 x i x_i xi类型的药剂,他可以使用一个打败怪物。如果他不打败怪物,他就会被打败。

判断他是否能够打败所有的怪物。

如果他不能打败所有的怪物,输出 − 1 -1 1

若可以打败所有的怪物,设 K K K为他在冒险过程中所拥有的药剂的最大数量。设 K m i n {K_{min}} Kmin为在冒险家采取的所有可以打败所有怪物的策略中 K K K的最小值。输出 K m i n K_{min} Kmin的值和该策略下冒险家每次找到药剂时的动作,若他捡起药剂,输出 1 1 1,若他丢弃药剂,输出 0 0 0

分析:

本题采用贪心的思想,遍历事件,使用一个 V e c t o r Vector Vector数组记录每种类型的药水出现的位置,并通过一个 v i s vis vis数组记录这个位置的药水是否被使用,当需要使用药水时,由近到远遍历该种药水对应的 V e c t o r Vector Vector数组中此种药水的所有位置,若没有被使用,则在 v i s vis vis数组中将其标记为已使用,若没有未使用的药水,则表明无法满足要求,冒险家被打败。遍历 N N N个事件,若该位置的药水被使用,则将手中药水数目加 1 1 1,若该位置需要使用药水,则手中药水数目 − 1 -1 1,不断更新 K K K直至完全遍历。最后根据 v i s vis vis数组输出每次找到药剂时的动作。

代码:

#include<bits/stdc++.h>

using namespace std;
const int MAXN = 2 * 1e5;
int n;
int t[MAXN], x[MAXN], vis[MAXN];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> t[i] >> x[i];
    vector<vector<int>> a(n + 5);
    for (int i = 0; i < n; i++) {
        if (t[i] == 1) {
            a[x[i]].push_back(i);
        } else {
            int index = a[x[i]].size() - 1;
            while (index >= 0 && vis[a[x[i]][index]]) {
                index--;
            }
            if (index < 0) {
                cout << "-1" << endl;
                return 0;
            }
            vis[a[x[i]][index]] = 1;
        }
    }

    int ans, tmp;
    ans = tmp = 0;
    for (int i = 0; i < n; i++) {
        if (vis[i])
            tmp++;
        if (t[i] == 2)
            tmp--;
        ans = max(ans, tmp);
    }
    cout << ans << endl;
    for (int i = 0; i < n; i++) {
        if (t[i] == 1) {
            if (i == 0) {
                cout << vis[i];
            } else {
                cout << " " << vis[i];
            }
        }
    }
    cout << endl;
    return 0;
}

F.Bomb Game 2(概率DP)

题意:

N N N个人站在一条线上,第 i i i个人站在第 i i i个位置。

重复以下操作,直到队伍中只剩下一个人:

1 2 \frac{1}{2} 21的概率将排在队伍最前面的人移走,否则将他们移到队伍的末尾。

对于每个编号为 i = 1 , 2 , … , N i=1,2,…,N i=1,2,,N的人,求 i i i是队列中最后一个人的概率,结果对 998244353 998244353 998244353取模。

分析:

本题为概率DP。设 f i , j f_{i,j} fi,j表示长度为 i i i时,第 j j j个的概率,以 1 , 2 , 3 1,2,3 1,2,3为例,可以列出 f i , 1 = 1 4 f i − 1 , 2 + 1 8 f i − 1 , 1 + 1 8 f i , 1 f_{i,1}=\frac{1}{4}f_{i-1,2}+\frac{1}{8}f_{i-1,1}+\frac{1}{8}f_{i,1} fi,1=41fi1,2+81fi1,1+81fi,1 ,对此式子解方程得 7 8 f i , 1 = 1 4 f i − 1 , 2 + 1 8 f i − 1 , 1 \frac{7}{8}f_{i,1}=\frac{1}{4}f_{i-1,2}+\frac{1}{8}f_{i-1,1} 87fi,1=41fi1,2+81fi1,1,化简得 f i , 1 = 8 7 ( 1 4 f i − 1 , 2 + 1 8 f i − 1 , 1 ) f_{i,1}=\frac{8}{7}(\frac{1}{4}f_{i-1,2}+\frac{1}{8}f_{i-1,1}) fi,1=78(41fi1,2+81fi1,1)

可以发现,对于 f i , 1 f_{i,1} fi,1,其递推公式为 f i , 1 = 2 i 2 i − 1 ( ∑ j = 2 i f i − 1 , i − j + 1 ) f_{i,1}=\frac{2^i}{2^i-1}(\sum\limits_{j=2}^{i}f_{i-1,i-j+1}) fi,1=2i12i(j=2ifi1,ij+1),使用相同方法可以推出 f i , 2 f_{i,2} fi,2的表达式,进一步递推得出转移方程 f i , j = 1 2 f i − 1 , j − 1 + 1 2 f i , j − 1 f_{i,j}=\frac{1}{2}f_{i-1,j-1}+\frac{1}{2}f_{i,j-1} fi,j=21fi1,j1+21fi,j1

代码:

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int MOD = 998244353;
const int MAXN = 3005;
LL n, F[MAXN][MAXN];

LL pow_mod(LL a, LL b, LL p) { //a的b次方求余p
    LL ret = 1;
    while (b) {
        if (b & 1) ret = (ret * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return ret;
}

int main() {
    cin >> n;
    F[1][1] = 1;
    for (int i = 2; i <= n; i++) {
        int tmp = pow_mod(2, i, MOD);
        for (int j = i - 1, k = 2; j >= 1; j--, k++) {
            F[i][1] = (F[i][1] + pow_mod(pow_mod(2, k, MOD), MOD - 2, MOD) * F[i - 1][j] % MOD) % MOD;
        }
        F[i][1] = F[i][1] * tmp % MOD * pow_mod(tmp - 1, MOD - 2, MOD) % MOD;
        for (int j = 2; j <= i; j++) {
            F[i][j] = (pow_mod(2, MOD - 2, MOD) * F[i - 1][j - 1] % MOD + pow_mod(2, MOD - 2, MOD) * F[i][j - 1] % MOD) % MOD;
        }
    }
    for (int i = 1; i <= n; i++)
        cout << F[n][i] << " ";
    cout << endl;
    return 0;
}

学习交流

以下为学习交流QQ群,群号: 546235402,每周题解完成后都会转发到群中,大家可以加群一起交流做题思路,分享做题技巧,欢迎大家的加入。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Code_Shark/article/details/135085821

AtCoder Beginner Contest 196 A~E题解-爱代码爱编程

ABC196 A~E [A - Difference Max](https://atcoder.jp/contests/abc196/tasks/abc196_a)题目大意输入格式输出格式样例分析代码[B - Round Down](https://atcoder.jp/contests/abc196/tasks/abc196_b)题目大意输入格式

AtCoder Beginner Contest 245 A~E 题解-爱代码爱编程

ABC245 A~E [A - Good morning](https://atcoder.jp/contests/abc245/tasks/abc245_a)题目大意输入格式输出格式样例分析代码[B - Mex](https://atcoder.jp/contests/abc245/tasks/abc245_b)题目大意输入格式输出格式样例分析代

AtCoder Beginner Contest 244 D~F 题解-爱代码爱编程

本文同步发布于:https://goodcoder666.github.io/post/abc244/ ABC244 D~F [D - Swap Hats](https://atcoder.jp/contests/abc244/tasks/abc244_d)题目大意输入格式输出格式样例样例输入样例输出分析代码[E - King Bombee](htt

atcoder beginner contest 278 a~e题详细讲解_逍遥zxq的博客-爱代码爱编程

这次比赛非常水,也许是因为上一场比赛出得太难了,有兴趣的可以点击这里。 赛时:A,B,C,D,E,取得历史新高。 话不多说,本题解现在开始。 目录 A - Shift B - Misjudge the Time C - FF  D - All Assign Point Add  E - Grid Filling A - Shift A

23.3.6打卡 atcoder beginner contest 277 a~d-爱代码爱编程

E题最短路有点生疏了先不写, 之后再补 A 题意 给出一个排列和X 问X在排列中出现的下标是多少 代码 void solve() { cin>>n>>m; for(ll

atcoder contest 300 a~c-爱代码爱编程

鼠鼠第一次打这个Atcoder,但是一边挂着视频一边写代码效率是真的低,只写了三道题 A 在一个序列中找出一个A+B的元素 # include <bits/stdc++.h> # define int lo

atcoder beginner contest 301 a~e-爱代码爱编程

鼠鼠我又来了,这次知道D题思路,但是老是wa,同时有事也就没写完DE题,现在补了补 A - Overall Winner 给一个字符串s,包含了两个人比赛的结果,输出最终的结果 需要注意的是,如果两个人赢的场数一

atcoder beginner contest 304 a~e题解-爱代码爱编程

文章目录 A - First PlayerB - SubscribersC - VirusD - A Piece of CakeE - Good Graph A - First Player 题目链

atcoder beginner contest 306 a~e题解-爱代码爱编程

文章目录 A - EchoB - Base 2C - CentersD - Poisonous Full-CourseE - Best Performances 这次感觉比之前简单一些 A

atcoder beginner contest 253 a~e 题解_abc253e-爱代码爱编程

ABC253 A~E [A - Median?](https://atcoder.jp/contests/abc253/tasks/abc253_a)题目大意输入格式输出格式样例分析代码 [B - Dis

atcoder beginner contest 274 a~e 题解_e -爱代码爱编程

ABC274 A~E [A - Batting Average](https://atcoder.jp/contests/abc274/tasks/abc274_a)题目大意分析代码 [B - Line