【題解】Atcoder ABC 315, 317
===
## 315 D
每個回合會刪除至少一行或一列，因此刪除最多 $O(H+W)$ 次。每次的刪除，可以用 $O(HW)$ 的時間找到可以刪除的行列，但複雜度會爆炸。
考慮到元素種類只有 $\rho = 26$ 種，我們可以對每一行、每一列維護一個每個元素對應數量的表，如 $rowCnt[i][c]$ 代表第 $i$ 行有幾種 $c$ 元素。對於一個行、列，只要用 $O( \rho )$ 即可檢查是否可以刪除該行列。那麼每個回合的複雜度將為 $O(\rho(H+W)))$。
要注意的是，在統計完可刪除行列前，如果就移除字符，會對後續統計產生影響。
```cpp
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define V vector
#define sz(a) ((int)a.size())
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pb push_back
#define rsz resize
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define FOR(i,j,k) for (int i=(j); i<=(k); i++)
#define F0R(i,j,k) for (int i=(j); i<(k); i++)
#define REP(i) FOR(_,1,i)
#define foreach(a,x) for (auto& a: x)
template<class T> bool cmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; } // set a = min(a,b)
template<class T> bool cmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; } // set a = max(a,b)
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); }
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); }
#define roadroller ios::sync_with_stdio(0), cin.tie(0);
#define de(x) cerr << #x << '=' << x << ", "
#define dd cerr << '\n';
signed main() {
int n, m; cin >> n >> m;
V<string> a(n);
F0R(i,0,n) cin >> a[i];
V<vi> rcnt(n, vi(128)), ccnt(m, vi(128));
V<V<vi>> rpos(n, V<vi>(128, vi())), cpos(m, V<vi>(128, vi()));
F0R(i,0,n){
F0R(j,0,m){
auto c = a[i][j];
rcnt[i][c]++, ccnt[j][c]++;
rpos[i][c].pb(j);
cpos[j][c].pb(i);
}
}
auto ckrow = [&](int i){
int ans = 0;
FOR(j,'a','z'){
if (rcnt[i][j] > 0){
if (!ans) ans = j;
else return 0;
}
}
if (rcnt[i][ans] <= 1) return 0;
return ans;
};
auto ckcol = [&](int i) {
int ans = 0;
FOR(j,'a','z'){
if (ccnt[i][j] > 0){
if (!ans) ans = j;
else return 0;
}
}
if (ccnt[i][ans] <= 1) return 0;
return ans;
};
while(1){
int flag = 0;
V<pair<int, char>> drow;
F0R(i,0,n){
char x = ckrow(i);
if (x){
drow.pb(mp(i, x));
flag = 1;
}
}
F0R(j,0,m){
char x = ckcol(j);
if (x){
flag = 1;
foreach(p, cpos[j][x]){
rcnt[p][x]--;
}
ccnt[j][x] = 0;
}
}
foreach(r,drow){
auto [i, x] = r;
foreach(p, rpos[i][x]) ccnt[p][x]--;
rcnt[i][x] = 0;
}
if (!flag) break;
}
int ans = 0;
F0R(i,0,n){
FOR(c,'a','z'){
ans += rcnt[i][c] * (rcnt[i][c]>0);
}
}
cout << ans << '\n';
}
```
## 315 F
省略一個點位，最多可以省掉 $10^4 \sqrt2$ 的移動距離（對角線）。但隨著省略次數增加，花費會快速增長。當 $2^{c-1}$ 已經超過可以省掉的最長移動距離，那麼就省掉一定是不划算的。我們可以取最大的可能 $c$ 在 $log(10^5)$ 。
當知道 $c$ 的範圍很小，我們可以嘗試 DP。列出狀態 $dp[i][j]$ 代表現在人在 $i$，還可以跳過 $j$ 次。轉移只要枚舉這一步要跳過幾個就好了，複雜度 $O(NC^2)$。
```cpp
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define V vector
#define sz(a) ((int)a.size())
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pb push_back
#define rsz resize
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define FOR(i,j,k) for (int i=(j); i<=(k); i++)
#define F0R(i,j,k) for (int i=(j); i<(k); i++)
#define REP(i) FOR(_,1,i)
#define foreach(a,x) for (auto& a: x)
template<class T> bool cmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; } // set a = min(a,b)
template<class T> bool cmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; } // set a = max(a,b)
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); }
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); }
#define roadroller ios::sync_with_stdio(0), cin.tie(0);
#define de(x) cerr << #x << '=' << x << ", "
#define dd cerr << '\n';
#define int long long
int qpow(int i, int j){
j--;
if (j < 0) return 0;
int ans = 1;
for (; j; j>>=1, i*=i){
if (j&1)
ans *= i;
}
return ans;
}
signed main(){
roadroller
int n; cin >> n;
V<pii> a(n+5); FOR(i,1,n) cin >> a[i].ff >> a[i].ss;
int m = 31;
V<V<double>> dp(n+5, V<double>(m, 1e18));
auto cost = [&](int i, int j){
return sqrt( (a[i].ff-a[j].ff)*(a[i].ff-a[j].ff) + (a[i].ss-a[j].ss)*(a[i].ss-a[j].ss) );
};
F0R(j, 0, m) dp[1][j] = 0;
FOR(i,2,n){
F0R(j,0,m){
double c = 0;
int src = 0;
FOR(k,0,min(j, i-2)){
cmin(dp[i][j], dp[i-1-k][j-k] + cost(i-1-k, i));
}
}
}
double ans = 1e18;
F0R(i, 0, m){
ans = min(ans, dp[n][i] + qpow(2, i) );
}
cout << fixed << setprecision(10) << ans << '\n';
}
```
## 315 G
枚舉 $i$，那麼 $Bj + Ck = X-Ai$ 就可以用擴展歐幾里德解出 $j, k$。用擴展歐幾里德獲得一組 $Ax+By=C$ 的解 $x, y$，那麼 $(x + i \frac B g, y - i \frac A g),\, g=gcd(A,B)$ 也是一組解。 可以用這個方式找到所有合法的解。直接帶入不等式即可。
```cpp
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef __int128 ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define V vector
#define sz(a) ((int)a.size())
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pb push_back
#define rsz resize
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define FOR(i,j,k) for (int i=(j); i<=(k); i++)
#define F0R(i,j,k) for (int i=(j); i<(k); i++)
#define REP(i) FOR(_,1,i)
#define foreach(a,x) for (auto& a: x)
template<class T> bool cmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; } // set a = min(a,b)
template<class T> bool cmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; } // set a = max(a,b)
ll ccdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); }
ll ffdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); }
#define roadroller ios::sync_with_stdio(0), cin.tie(0);
#define de(x) cerr << #x << '=' << x << ", "
#define dd cerr << '\n';
pair<ll, ll> euclid(ll A, ll B) {
if (!B) return {1,0};
auto p = euclid(B,A%B); return {p.second,p.first-A/B*p.second}; }
ll solve(ll a, ll b, ll c, ll n){
ll g = __gcd(a, b);
if (c % g) return 0;
auto [x0, y0] = euclid(a, b);
ll x = c/g * x0, y = c/g * y0;
ll dx = b/g, dy = a/g;
ll l1 = ccdiv(1-x, dx), u1 = ffdiv(n-x, dx);
ll l2 = ccdiv(y-n, dy), u2 = ffdiv(y-1, dy);
return max(__int128(0), min(u1,u2) - max(l1, l2) + 1);
}
signed main() {
long long n, a, b, c, X; cin >> n >> a >> b >> c >> X;
long long ans = 0;
FOR(i,1,n){
ans += solve(b, c, X - a*i, n);
}
cout << ans << '\n';
}
```
## 317 F
由於該題位數很大，我們考慮用數位 DP。由於規定 XOR，因此在二進制上數位 DP。訂定狀態 $dp[n][l_1][l_2][l_3][w_1][w_2][w_3][r_1][r_2][r_3]$， $n$ 代表要決定 $Xi$ 的前 $n-1$ 位， $l_i$ 代表 $X_i$ 接下來需不需要小於 $N$ 的對應位數， $w_i$ 代表 $X_i$ 目前是否 $>0$， $r_i$ 代表 $X_i$ 接下來使得 $X_i \% A_i = r_i$。
```cpp
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define V vector
#define sz(a) ((int)a.size())
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pb push_back
#define rsz resize
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define FOR(i,j,k) for (int i=(j); i<=(k); i++)
#define F0R(i,j,k) for (int i=(j); i<(k); i++)
#define REP(i) FOR(_,1,i)
#define foreach(a,x) for (auto& a: x)
template<class T> bool cmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; } // set a = min(a,b)
template<class T> bool cmax(T& a, const T& b) {
return a < b ? a = b, 1 : 0; } // set a = max(a,b)
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); }
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); }
#define roadroller ios::sync_with_stdio(0), cin.tie(0);
#define de(x) cerr << #x << '=' << x << ", "
#define dd cerr << '\n';
#define int long long
const int M = 998244353;
int N, a1, a2, a3;
int dp[65][2][2][2][2][2][2][15][15][15];
int f (int n, int l1, int l2, int l3, int w1, int w2, int w3, int r1, int r2, int r3) {
auto &dpnow = dp[n][l1][l2][l3][w1][w2][w3][r1][r2][r3];
if (dpnow < 0){
if (n == 0) {
dpnow = !(r1 || r2 || r3) && w1 && w2 && w3;
return dpnow;
}
V<V<pii>> can(4);
auto gen = [&](V<pii> &can, int l, int r, int a) {
if (l){
if ( N & (1LL<<(n-1)) ) {
can.pb( mp(0, r) );
can.pb( mp(1, ((r - (1LL<<(n-1)))%a+a)%a) );
}
else {
can.pb( mp(1, r));
}
}
else {
can.pb( mp(0, r) );
can.pb( mp(0, ((r - (1LL<<(n-1)))%a+a)%a) );
}
};
gen(can[1], l1, r1, a1);
gen(can[2], l2, r2, a2);
gen(can[3], l3, r3, a3);
dpnow = 0;
F0R(i,0,sz(can[1])){
F0R(j,0,sz(can[2])){
F0R(k,0,sz(can[3])){
if (i ^ j ^ k) continue;
dpnow = (dpnow +
f(n-1, can[1][i].ff, can[2][j].ff, can[3][k].ff,
w1 || i, w2 || j, w3 || k,
can[1][i].ss, can[2][j].ss, can[3][k].ss))%M;
}
}
}
}
return dpnow;
}
signed main() {
roadroller
memset(dp, -1, sizeof(dp));
cin >> N >> a1 >> a2 >> a3;
cout << f(61, 1, 1, 1, 0, 0, 0, 0, 0, 0) << '\n';
}
```
Sign in with Wallet
Connect another wallet