首页 > 其他分享 >AtCoder Beginner Contest 359

AtCoder Beginner Contest 359

时间：2024-07-06 16:09:35浏览次数：22  
标签：AtCoder typedef Beginner Contest int long getchar 359 define

AtCoder Beginner Contest 359

这场我赛时打的非常不好，只做出了 \(2\) 题。

A - Count Takahashi

签到

// Problem: A - Count Takahashi
// Contest: AtCoder - UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359)
// URL: https://atcoder.jp/contests/abc359/tasks/abc359_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// https://codeforces.com/problemset/customtest

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
//# define int long long
# define rd(t) read <t> ()
# define mem(a, b) memset (a, b, sizeof (a))
# define fi first
# define se second
# define lc u << 1
# define rc u << 1 | 1
# define debug printf ("debug\n")

template <typename T> inline T read ()
{
    T s = 0; int w = 1; char c = getchar (); 
    for (; !isdigit (c); c = getchar ()) { if (c == '-') w = -1; }
    for (; isdigit (c); c = getchar ()) s = (s << 1) + (s << 3) + c - '0';
    return s * w;
}

signed main ()
{
	int n = rd (int); 
	int ans = 0; 
	for (int i = 1; i <= n; i ++ )
	{
		string s; cin >> s; 
		if (s == "Takahashi") ans ++ ; 
	}
	printf ("%d\n", ans); 
    return 0;
}

B - Couples

签到

// Problem: B - Couples
// Contest: AtCoder - UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359)
// URL: https://atcoder.jp/contests/abc359/tasks/abc359_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// https://codeforces.com/problemset/customtest

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
//# define int long long
# define rd(t) read <t> ()
# define mem(a, b) memset (a, b, sizeof (a))
# define fi first
# define se second
# define lc u << 1
# define rc u << 1 | 1
# define debug printf ("debug\n")
const int N = 105; 
template <typename T> inline T read ()
{
    T s = 0; int w = 1; char c = getchar (); 
    for (; !isdigit (c); c = getchar ()) { if (c == '-') w = -1; }
    for (; isdigit (c); c = getchar ()) s = (s << 1) + (s << 3) + c - '0';
    return s * w;
}

int n; 
vector <int> vec[N]; 
signed main ()
{
	n = rd (int); 
	for (int i = 1; i <= 2 * n; i ++ )
	{
		int x = rd (int); 
		vec[x].push_back (i); 
	}
	int ans = 0; 
	for (int i = 1; i <= n; i ++ ) ans += (vec[i][1] - vec[i][0] == 2); 
	printf ("%d\n", ans); 
    return 0;
}

C - Tile Distance 2

首先，如果起点坐标或终点坐标在一个砖块的右侧时，把他变为在这个砖块的左侧不影响最终答案。
计算横坐标和纵坐标需要移动的格子数，分别记为 \(a\)，\(b\)。
画图模拟可知：进行纵向运动时，可以免费向左或者向右移动一格。所以优先向上运动。
如果向上运动后，横坐标依旧没有达到目标值，那么就需要进行横向运动。可以发现，每花 \(1\) 块钱，可以横向移动 \(2\) 格，所以横向运动的花费为 \(\frac{\operatorname{max}(0,a-b)}{2}\)

// Problem: C - Tile Distance 2
// Contest: AtCoder - UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359)
// URL: https://atcoder.jp/contests/abc359/tasks/abc359_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// https://codeforces.com/problemset/customtest

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
# define int long long
# define rd(t) read <t> ()
# define mem(a, b) memset (a, b, sizeof (a))
# define fi first
# define se second
# define lc u << 1
# define rc u << 1 | 1
# define debug printf ("debug\n")

template <typename T> inline T read ()
{
    T s = 0; int w = 1; char c = getchar (); 
    for (; !isdigit (c); c = getchar ()) { if (c == '-') w = -1; }
    for (; isdigit (c); c = getchar ()) s = (s << 1) + (s << 3) + c - '0';
    return s * w;
}

int sx, sy, ex, ey; 
signed main ()
{
	sx = rd (int), sy = rd (int), ex = rd (int), ey = rd (int); 
	if ((sx + sy) % 2 == 1) sx -- ; 
	if ((ex + ey) % 2 == 1) ex -- ; 
	int a = abs (sx - ex), b = abs (sy - ey); 
	printf ("%lld\n", b + max (0ll, a - b) / 2); 
    return 0;
}

D - Avoid K Palindrome

把题目中的 A，B 转化为 \(0\)，\(1\)。
\(dp_{i,s}\) 表示前 \(i\) 个字符中，最后 \(k\) 个字符为 \(s\)，保证没有长度为 \(k\) 的方案数
转移显然

// Problem: D - Avoid K Palindrome
// Contest: AtCoder - UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359)
// URL: https://atcoder.jp/contests/abc359/tasks/abc359_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// https://codeforces.com/problemset/customtest

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
//# define int long long
# define rd(t) read <t> ()
# define mem(a, b) memset (a, b, sizeof (a))
# define fi first
# define se second
# define lc u << 1
# define rc u << 1 | 1
# define debug printf ("debug\n")
const int N = 1005, M = (1 << 10) + 5, mod = 998244353; 
template <typename T> inline T read ()
{
    T s = 0; int w = 1; char c = getchar (); 
    for (; !isdigit (c); c = getchar ()) { if (c == '-') w = -1; }
    for (; isdigit (c); c = getchar ()) s = (s << 1) + (s << 3) + c - '0';
    return s * w;
}

int n, k; 
string S; 
int dp[N][M]; 
bool checkpalin (int state)
{
	for (int i = 0; i < k / 2; i ++ )
	{
		if (((state >> i) ^ (state >> k - i - 1)) & 1)
			return 0;
	}
	return 1;
}
signed main ()
{
	cin >> n >> k >> S; 
	dp[0][0] = 1; 
	int ans = 0; 
	for (int i = 1; i <= n; i ++ )
	{
		for (int s = 0; s < (1 << k); s ++ )
		{
			if (i >= k && checkpalin (s)) continue;
			if ((S[i - 1] == 'A' || S[i - 1] == '?') && s % 2 == 0)
				dp[i][s] = (dp[i][s] + (dp[i - 1][(s >> 1) + (1 << (k - 1))] + 
										dp[i - 1][s >> 1])) % mod;
			if ((S[i - 1] == 'B' || S[i - 1] == '?') && s % 2 == 1)
				dp[i][s] = (dp[i][s] + (dp[i - 1][(s >> 1) + (1 << (k - 1))] + 
										dp[i - 1][s >> 1])) % mod;
			if (i == n) ans = (ans + dp[i][s]) % mod;
		}
	}
	printf ("%d\n", ans); 
	return 0; 
}

E - Water Tank

题目意思感觉有点抽象
对于每个挡板 \(i\)，找到在他前面第一个比他高的挡板 \(pos_i\)（用单调栈），那么答案 \(ans_i\) 就可以从这个挡板继承过来。

\[ans_i=ans_{pos_i}+(i-pos_i)\times a_i \]

// Problem: E - Water Tank
// Contest: AtCoder - UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359)
// URL: https://atcoder.jp/contests/abc359/tasks/abc359_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// https://codeforces.com/problemset/customtest

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
# define int long long
# define rd(t) read <t> ()
# define mem(a, b) memset (a, b, sizeof (a))
# define fi first
# define se second
# define lc u << 1
# define rc u << 1 | 1
# define debug printf ("debug\n")
const int N = 200005; 
template <typename T> inline T read ()
{
    T s = 0; int w = 1; char c = getchar (); 
    for (; !isdigit (c); c = getchar ()) { if (c == '-') w = -1; }
    for (; isdigit (c); c = getchar ()) s = (s << 1) + (s << 3) + c - '0';
    return s * w;
}

int n; 
int a[N], pos[N]; 
int ans[N]; 
signed main ()
{
	n = rd (int); 
	stack <pii> stk; 
	for (int i = 1; i <= n; i ++ )
	{
		a[i] = rd (int); 
		while (!stk.empty () && stk.top ().fi < a[i]) stk.pop (); 
		if (!stk.empty ()) pos[i] = stk.top().se; 
		stk.push ({a[i], i});
	}
	for (int i = 1; i <= n; i ++ )
	{
		ans[i] = ans[pos[i]] + (i - pos[i]) * a[i]; 
		printf ("%lld ", ans[i] + 1); 
	}
	return 0; 
}

F - Tree Degree Optimization

首先，因为这是一棵树，所以每个点的度数至少为 \(1\)
总度数为 \(2\times n - 2\)
我们可以进行贪心。在每个节点的度数都是 \(1\) 的基础上，考虑去动态安排度数，使得最终答案最小
对 \(i\) 号点考虑，如果度数从 \(d_i\) 变为 \(d_i+1\)：
原本贡献 \(d_i^2 \times a_i\)；
新的贡献： \((d_i+1)^2\times a_i=(d_i^2+2\times d_i+1)\times a_i\)
如果给 \(i\) 号点增加一个度数，造成的增量为 \((2\times d_i+1)\times a_i\)
每次选取最小的增量，加入答案。这一步可以使用 priority_queue 来实现

// Problem: F - Tree Degree Optimization
// Contest: AtCoder - UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359)
// URL: https://atcoder.jp/contests/abc359/tasks/abc359_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// https://codeforces.com/problemset/customtest

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
# define int long long
# define rd(t) read <t> ()
# define mem(a, b) memset (a, b, sizeof (a))
# define fi first
# define se second
# define lc u << 1
# define rc u << 1 | 1
# define debug printf ("debug\n")
const int N = 200005; 
template <typename T> inline T read ()
{
    T s = 0; int w = 1; char c = getchar (); 
    for (; !isdigit (c); c = getchar ()) { if (c == '-') w = -1; }
    for (; isdigit (c); c = getchar ()) s = (s << 1) + (s << 3) + c - '0';
    return s * w;
}

int n; 
int a[N]; 
struct node
{
	int x, y;
	bool operator < (const node &t) const
	{
		return (2 * x + 1) * y > (2 * t.x + 1) * t.y;
	}
}; 
signed main ()
{
	n = rd (int); 
	int ans = 0; 
	for (int i = 1; i <= n; i ++ )
	{
		a[i] = rd (int); 
		ans += a[i]; 
	}
	priority_queue <node> q; 
	for (int i = 1; i <= n; i ++ ) q.push ({1, a[i]});
	for (int i = 1; i < n - 1; i ++ )
	{
		node u = q.top (); q.pop (); 
		ans += (u.x * 2 + 1) * u.y;
		if (u.x < n - 1) q.push ({u.x + 1, u.y});
	}
	printf ("%lld\n", ans); 
	return 0;
}

G - Sum of Tree Distance

不会

标签：AtCoder,typedef,Beginner,Contest,int,long,getchar,359,define
From： https://www.cnblogs.com/legendcn/p/18287358

相关文章

  • Solution - Atcoder AGC034F RNG and XOR
    考虑到这个边权是\(\oplus\)，那么说明对于\((u,v)\)，\(u\tov\)和\(v\tou\)的边权实质是相同的。那么对于\(0\tox\)，就可以反过来，记录下对应的路径，从\(x\)开始走，那么第一次走到\(0\)的时候也就是从\(0\)第一次走到\(x\)的时候。于是就转化为了\(x\)为起点，第一次......
  • AtCoder Beginner Contest 043
    D-Unbalanced只需要找到形如\(XX\)、\(XYX\)的字串即可。即两个相同字符之间最多间隔一个字符。证明：若不然，\(AXYA\)，每加一个字符\(A\)，都要增加多余字符\(XY\)，不可能符合要求。#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ ios......
  • AtCoder Beginner Contest 042
    C-Iroha'sObsession用一个\(\rmst\)数组把每一位标记，然后枚举大于\(n\)的数，一旦有各位都满足要求的数出现就\(\rmbreak\)。#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;boolst[10];boolcheck(intx){ while(x){ intb=x%1......
  • Atcoder ABC091D Two Sequences
    首先根据\(\operatorname{xor}\)，就想到拆成二进制的\(a_{i,w},b_{i,w}\)来处理。类似竖式加法，考虑把得到的结果\(c_{w}\)分为\(a_{i,w}+b_{j,w}+x\)，其中\(x\)就是上一位的进位。进一步的，发现对于总的\(c_{w}\)，\(a_{i,w},b_{j,w}\)肯定都在这个位置加了\(......
  • Atcoder ARC090F Number of Digits
    记\(n\)为题面的\(S\)。能发现对于\(f(l)=8\)，共有\(9\times10^7\)个数。此时就已经有\(8\times9\times10^7>10^8=n_{\max}\)了，就说明不存在\(f\ge8\)的情况，还满足这部分对应的数能全被选满。所以可以知道对于\(f(l)\ge8\)的情况，只存在\(f(r)-f(l)=......
  • AtCoder Beginner Contest 359 (A ~F)
    A-CountTakahashiQuestion：给你n个单词，要么是Takahashi，要么是Aoki；输出有几个Takahashi即可。Code：#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'#defineintlonglongtypedeflonglongll;typedefunsignedlonglongull;typedefpair<......
  • Atcoder ABC 360 全题解
    致歉对不起，我不应该在全题解的编写上咕咕咕两个月，导致流量大量流失。我知错了，下次还犯。AB无C考虑一个箱子里的所有球，我们需要把这些球放进互不相同的一些箱子里。然而我们可以留一个球在箱子里，显然留重量最大的最好，所以答案就是$\sum_{i=1}^{N}W_i$减去每个箱子里的最......
  • AtCoder Beginner Contest 360
    A-AHealthyBreakfast(abc360A)题目大意给定一个字符串包含RMS，问R是否在S的左边。解题思路比较R和S的下标，谁小即谁在左边。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with_stdio(false);......
  • AtCoder Beginner Contest 359
    https://atcoder.jp/contests/abc359/tasksA-CountTakahashivoidsolve(){ intn; cin>>n; intans=0; while(n--){ strings; cin>>s; if(s=="Takahashi"){ ans++; } } cout<<ans<<endl;}B-......
  • ABC 359
    submissionsA,B直接模拟即可。C纵向的距离很好算。有两种情况：横向距离更小。这个直接输出纵向距离。更大。减去纵向的步数。横向距离怎么算？我们考虑把\(s,e\)都移动到方块靠左，然后就是横坐标之和。D简单的dp。设\(dp_{i,msk}\)为到了第\(i\)为，目前前面的状......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99