题解：CF1733E Conveyor

Solution

读完题发现因为每个史莱姆每秒都会往右或者往下走，所以不可能有相遇，所以那个合并是没用的。

第 $t$ 秒很不好考虑，可以转化成 前 $t$ 秒有没有史莱姆经过 $(x, y)$，比较第 $t$ 秒和第 $t - 1$ 秒。

那么前 $t$ 秒是好做的，考虑一个位置有 $x$ 个史莱姆经过时，因为方向是右下右下交替的，显然有 $\lceil \frac{x}{2} \rceil$ 个去了 $(x, y + 1)$，有 $\lfloor \frac{x}{2} \rfloor$ 个去了 $(x + 1, y)$。然后就可以递推模拟了，设 $f_{i, j}$ 是前 $t$ 秒有多少个点经过这个格子，$O(n ^ 2)$ 转移就行。

Code

// Problem: CF1733E Conveyor
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1733E
// Memory Limit: 250 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long 
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define rep(i, a, b) for(int (i) = (a); (i) <= (b); (i) ++)
#define per(i, a, b) for(int (i) = (a); (i) >= (b); (i) --)
#define REP(i, l, r, k) for (int i = (l); i <= (r); i += k)
#define PER(i, l, r, k) for (int i = (l); i >= (r); i -= k)
#define ls x << 1
#define rs x << 1 | 1
#define umap unordered_map
#define uset unordered_set
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define x1 Sun
#define y1 Jude
void ckmin(int &x, int y) { x = std::min(x, y) ; }
void ckmax(int &x, int y) { x = std::max(x, y) ; }
int lowbit(int x) { return x & -x ; }

using namespace std;

const int maxn = 125 ;
// const int inf = ;
// const int mod = ; 

int t, x, y ;

int f1[maxn][maxn], f2[maxn][maxn] ;

void solve(){
    cin >> t >> x >> y ;
    rep(i, 0, x) rep(j, 0, y) f1[i][j] = f2[i][j] = 0 ;
    f1[0][0] = t - x - y + 1, f2[0][0] = t - x - y ;
    rep(i, 0, x) {
        rep(j, 0, y) {
            f1[i][j + 1] += (f1[i][j] + 1) / 2 ;
            f1[i + 1][j] += f1[i][j] / 2 ;
            f2[i][j + 1] += (f2[i][j] + 1) / 2 ;
            f2[i + 1][j] += f2[i][j] / 2 ;
        }
    }
    if(f1[x][y] > f2[x][y]) cout << "YES\n" ;
    else cout << "NO\n" ;
    return ;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1 ; 
    cin >> T ;
    while(T -- ){
        solve() ;
    }
    return 0 ;
} 

---

• 分类： OI
• 标签： 无标签