首页 > 其他分享 >CodeForces 1733E Conveyor

CodeForces 1733E Conveyor

时间:2023-01-12 15:57:03浏览次数:76  
标签:typedef txdy Conveyor 1733E CodeForces long 史莱姆 ll define

洛谷传送门

CodeForces 传送门

考虑差分,如果 \(t-1\) 时刻经过 \((x,y)\) 的史莱姆个数等于 \(t\) 时刻经过 \((x,y)\) 的史莱姆个数,答案为 NO,否则为 YES

发现两只史莱姆一定不会相遇,并且若 \(k\) 只史莱姆经过了 \((a,b)\),则有 \(\left\lceil\frac{k}{2}\right\rceil\) 只史莱姆经过 \((a,b+1)\),有 \(\left\lfloor\frac{k}{2}\right\rfloor\) 只史莱姆经过 \((a+1,b)\)。

递推一下即可,时间复杂度 \(O(Tn^2)\),其中 \(n = 120\)。

code
/*

p_b_p_b txdy
AThousandSuns txdy
Wu_Ren txdy
Appleblue17 txdy

*/

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 125;

ll f[maxn][maxn];

inline ll calc(ll t, ll x, ll y) {
	if (t < x + y) {
		return 0;
	}
	mems(f, 0);
	f[0][0] = t - x - y + 1;
	for (int i = 0; i <= x; ++i) {
		for (int j = 0; j <= y; ++j) {
			f[i + 1][j] += f[i][j] / 2;
			f[i][j + 1] += (f[i][j] + 1) / 2;
		}
	}
	return f[x][y];
}

void solve() {
	ll t, x, y;
	scanf("%lld%lld%lld", &t, &x, &y);
	puts(calc(t - 1, x, y) == calc(t, x, y) ? "NO" : "YES");
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

标签:typedef,txdy,Conveyor,1733E,CodeForces,long,史莱姆,ll,define
From: https://www.cnblogs.com/zltzlt-blog/p/17046897.html

相关文章

  • Codeforces Round #843 (Div. 2)(B,C,D,E)
    CodeforcesRound#843(Div.2)(B,C,D,E)23年的第一场比赛(现场的),结果还是只是做出了两个题B想起这道题就好笑,我又又又看错题了,这个题里面讲的一直是或,我在比赛全程都以为是......
  • Codeforces Round #843 (Div. 2)ACE 补D
    A.GardenerandtheCapybaras题意:给定一个由ab串,将该字符串拆分成3个部分,使中间部分的字典序最大或者最小。分析:考虑简单的最小情况:中间只有一个a,两边总会\(......
  • Codeforces Edu Round 106 Div2
    解题A.DominoonWindowsill这个题给一个2xn的方格,一个行有k1个白块,第二行有k2个白块,那么现在有w个2x1的白块和b个2x1黑块,白对白,黑对黑,问能不能全放下这个就是判断下白......
  • [Codeforces Round #822 (Div. 2)](https://codeforces.com/contest/1734)
    CodeforcesRound#822(Div.2)ProblemF.ZerosandOnes解法定义:\(f(x)\)为在\(S\)串中位置为\(x\)的值。显然\(f(x)\in0,1\)有一重要性质:若\(f(x)\)为1,那么二进制......
  • Codeforces Round #843 (Div. 2)
    Preface难得的7点场CF,结果反而遇上了我最困的时候(吃完晚饭血糖上来就贼困,我一般反而凌晨场比较清醒)但是这场表现还可以,写的题基本都是一发入魂而且速度也比较快比较可惜......
  • 【Codeforces 173B】 B. Chamber of Secrets
    【Codeforces173B】B.ChamberofSecretshttps://codeforces.com/problemset/problem/173/B题意+分析来自\(OI-wiki\)这题主要难度就是读题...还有注意初始方向......
  • Codeforces Round #843 (Div. 2)
    A-GardenerandtheCapybaras题意给出字符串S,S只由字符a,b组成,问怎么切分可以使字符串分为小大小,大小大这种的三段。思路在2~n-1的范围内找到字符a的位置,如果里......
  • Codeforces Round #843 (Div. 2)
    题目链接Atag:构造,分类讨论核心思路我们其实可以发现我们要是分很多情况去讨论abc,这题就不好做。所以我们可以假设a和b就是我们字符串的两个端点,这样题目就很好做了......
  • Codeforces Round #843 (Div. 2) Problem C
    C.InterestingSequencetimelimitpertest1secondmemorylimitpertest256megabytesinputstandardinputoutputstandardoutput  Petyaandhisfr......
  • Codeforces 1278 F Cards 增强版 题解 (斯特林数,推式子)
    原题链接增强版链接增强版中k=1e7为啥网上题解的式子都那么长啊.jpg首先令\(p=\frac1m\)。求某个数的次幂的题通常都是无脑转下降幂:\(x^k=\sum_{i=0}^kS_2(k,i)x^{\u......