【題解】Atcoder ABC 315, 317

315 D

每個回合會刪除至少一行或一列，因此刪除最多

$O(H+W)$ 次。每次的刪除，可以用

$O(HW)$ 的時間找到可以刪除的行列，但複雜度會爆炸。

考慮到元素種類只有

$\rho =26$ 種，我們可以對每一行、每一列維護一個每個元素對應數量的表，如

$rowCnt[i][c]$ 代表第

$i$ 行有幾種

$c$ 元素。對於一個行、列，只要用

$O(\rho )$ 即可檢查是否可以刪除該行列。那麼每個回合的複雜度將為

$O(\rho (H+W)))$。

要注意的是，在統計完可刪除行列前，如果就移除字符，會對後續統計產生影響。

#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\sqrt{2}$ 的移動距離（對角線）。但隨著省略次數增加，花費會快速增長。當

$2^{c-1}$ 已經超過可以省掉的最長移動距離，那麼就省掉一定是不划算的。我們可以取最大的可能

$c$ 在

$log({10}^5)$ 。

當知道

$c$ 的範圍很小，我們可以嘗試 DP。列出狀態

$dp[i][j]$ 代表現在人在

$i$，還可以跳過

$j$ 次。轉移只要枚舉這一步要跳過幾個就好了，複雜度

$O(N{C}^2)$。

#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)$ 也是一組解。 可以用這個方式找到所有合法的解。直接帶入不等式即可。

#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\mathrm{\%}{A}_i=r_i$。

#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';
}