T3 倒立数对

solution

首先枚举 $a$ ，然后令 $f_{x,y}$ 为第一位的数字为 $x$，第二位的数字为 $y$ 的数的个数，在枚举 $a$ 时可以标记 $f$ ，具体地：

1. 令 $s$ 为 $a$ 的首位数字，$t$ 为 $a$ 的末位数字，统计 $ans$，注意数对是无序的，要乘 $2$
2. 将 $f_{t,s}$ 加一，注意 $(s = t)$ 的时候 $ans++$

code

#include<bits/stdc++.h>
using namespace std;

const int N = 11;

int n , f[N][N] , ans;

int main(){
	freopen("number.in" , "r" , stdin);
	freopen("number.out" , "w" , stdout);
	
	cin >> n;
	
	for(int i = 1 ; i <= n ; i ++){
		int s = i , t = i % 10;
		while(s / 10 > 0) s /= 10;
		
		if(s == t) ans ++;
		ans += f[t][s] * 2;
		f[s][t] ++;
	}
	cout << ans;
	return 0;
}

T4 池塘

solution

注意到答案具有二段性，因此我们可以二分最小的中位数

考虑中位数的性质，当一个数在数组中有最多 $\bf[\frac{k^2}{2}]$ 数大于这个数时，这个数才有可能为中位数

因此我们可以在判断二段性质时枚举 $k * k$ 的矩阵，求里面有多少个元素的值大于二分的中位数，若矩阵中元素个数 $\leqslant [\frac{k^2}{2}]$ 则为 $true$ ，若找不到元素个数 $\leqslant [\frac{k^2}{2}]$ 的矩阵则为 $false$

可以用矩阵前缀和优化，具体地：将原矩阵转化为 0/1 矩阵，若原矩阵中元素值大于二分的中位数则为1，随后对 0/1 矩阵求前缀和即可

code

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 805;
const int MAX_N = 1e9;

int n , k , a[N][N] , s[N][N];

int query(int x1 , int y1 , int x2 , int y2){
	return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
}

bool check(int res){
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= n ; j ++){
			s[i][j] = (a[i][j] > res ? 1 : 0);
			
			s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
		}
	}
	for(int i = 1 ; i <= n - k + 1 ; i ++){
		for(int j = 1 ; j <= n - k + 1 ; j ++){
			int cnt = query(i , j , i + k - 1 , j + k - 1);
			if(cnt <= k * k / 2) return true;
		}
	}
	return false;
}

signed main(){
	freopen("water.in" , "r" , stdin);
	freopen("water.out" , "w" , stdout);
	
	cin >> n >> k;
	
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= n ; j ++){
			cin >> a[i][j];
		}
	}
	int l = 0 , r = MAX_N;
	while(l < r){
		int mid = (l + r) >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << l;
	return 0;
}