AtCoder Beginner Contest 266 「A」「B 取模」「C 凸多边形」「D 状态机dp」「E 概率dp」「F 思维+dfs」
admin
|
|
258
|
Atcoder

941 字
|
17 分钟

A – Middle Letter

题目描述：

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

思路：

水题

#include <bits/stdc++.h>
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;
}

B – Modulo Number

题目描述：

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

思路：

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

#include <bits/stdc++.h>
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;
}

C – Convex Quadrilateral

题目描述：

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

思路：

套板子

#include <bits/stdc++.h>
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;
}

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 <bits/stdc++.h>
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;
}

E – Throwing the Die

题目描述：

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

思路：

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

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

输出dp[n]即可

#include <bits/stdc++.h>
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;
}

F – Well-defined Path Queries on a Namori

题目描述：

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

思路：

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

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

#include <bits/stdc++.h>
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;
}

 

博客内容均系原创，未经允许严禁转载！
Atcoder
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
AtCoder Beginner Contest 238 F – Two Exams「dp + 二维偏序」

							
							

							
AtCoder Beginner Contest 215  F – Dist Max 2「二分答案」「二维偏序」「逆向思维」

							
							

							
AtCoder Beginner Contest 278「A」「B」「C」「D」「E」「F 对抗博弈」

							
							

							
ABC 216 G – 01Sequence「差分约束 」

							
							

							
AtCoder Beginner Contest 214 D – Sum of Maximum Weights「带权并查集」「思维」