2022.11.16 模擬賽總結(jié)
2022.11.16 模擬賽總結(jié)
\(T1\) 看起來對于我不是很可做，就大概看了一下 \(50\) 的做法，然后光速跳到 \(T2\), \(T2\) 打了個表把規(guī)律看出來了，然后又套了個組合意義，大概 \(15min\) 就切了，不過沒注意 \(2\) 倍空間，掛了 \(60pts\)。\(T3\)，\(T4\)感覺暴力都不可打，就去看的 \(T1\)，想了大概一個小時，沒思路，就去打的后面的暴力。還是要注意到細節(jié)，數(shù)組空間要給夠，但是不要 \(MLE\)，不要壓著上線開空間，寫代碼注意到細節(jié)，不要一處改了，另一處不改。
\(T1\)
題目大意：在二維平面上有 \(n\) 個點，每個點的范圍開始都是半徑為 \(1\) 的圓，并且每秒以 \(1\) 個單位長度的速度增長，給定起始點，終點，問最晚什么時候出發(fā)，在到達終點時，不碰到任何一個圓。
我們不難發(fā)現(xiàn)因為移動速度和增長速度是一樣的，并且只能上下左右移動，那么我們當(dāng)且僅當(dāng)在終點時碰到，那么一定就不行，所以只需要找到起點與終點的哈密頓距離然后進行判斷即可。
\(T2：40pts\)
貼個鏈接吧
\(40pts\) 的做法還是很好想的，我們可以 \(O(n^2)\) 的做法求出 \((1,1)\) 到所有點的方案數(shù)，對于路徑的花費我們打一個表可以不難發(fā)現(xiàn)到每個點的花費是固定的。所以不難求出到每個點的所有方案的花費。那么我們?nèi)绾芜M行優(yōu)化呢？我們想到將求方案數(shù)降到 \(O(nlogn)\) 或者 \(O(n)\)。我們考慮組合意義，我們到 \((n,m)\) 的步數(shù)是固定的，我們考慮第幾步在 \(x\) 軸走，就轉(zhuǎn)化成在 \((n + m - 2)\) 個數(shù)里選 \((n - 1)\) 個數(shù)的組合數(shù)。
點擊查看代碼
#include<bits/stdc++.h>
#define int long long
const int M = 1e6 + 7 , mod = 1e9 + 7;
int fac[M] , inv[M];
inline int Pow(int a , int b) {
int ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans ;
}
inline int C(int n , int m) {
if(n < 0 || m < 0 || n < m) return 0;
return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
inline void swap(int &a , int &b) {
int t = a;
a = b , b = t;
}
signed main () {
// freopen("count.in","r",stdin);
// freopen("count.out","w",stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr),std::cout.tie(nullptr);
fac[0] = inv[0] = 1;
for(int i = 1; i <= 1e6; ++ i) fac[i] = fac[i - 1] * i % mod;
for(int i = 1; i <= 1e6; ++ i) inv[i] = Pow(fac[i] , mod - 2);
int t; std::cin >> t;
while(t --) {
int n , m; std::cin >> n >> m;
if(n > m) swap(n , m);
int ans = (m - 1 + (n - 1) * m % mod + mod) % mod * C(n + m - 2 , n - 1) % mod;
std::cout << ans << '\n';
}
}
\(T3 , T4\) 壓根不會，潤了……
浙公網(wǎng)安備 33010602011771號