T1 铺地毯

模拟 + 枚举

solution

我们可以枚举每一个地毯，看 $(x , y)$ 坐标是否在地毯上，在就更新答案

code

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

const int N = 1e4 + 5;

int n , a[N] , b[N] , x[N] , y[N];
int x1 , y1 , ans;

int main(){
	cin >> n;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i] >> b[i] >> x[i] >> y[i];
	}
	cin >> x1 >> y1;
	
	for(int i = 1 ; i <= n ; i ++){
		if(x1 >= a[i] && x1 <= a[i] + x[i] && y1 >= b[i] && y1 <= b[i] + y[i]) ans = i;
	}
	cout << (ans == 0 ? -1 : ans);
	return 0;
}

T2 选择客栈

枚举

solution

可以选择枚举每个客栈统计贡献

我们可以枚举右端点，找每一个客栈前面的（包括当前客栈）价格 $\leqslant p$ 的第一个客栈的位置 $pos$，容易得出，当前客栈产生的贡献就为 $pos$ 之前的（包括 $pos$）与客栈相同色调的客栈个数

我们可以用 $cnt_i$ 表示当前色调为 $i$ 的客栈有多少个，$sum_i$ 表示在 $pos$ 位置之前色调为 $i$ 的客栈有多少个

维护方式即枚举到 $i$ 时更新 $pos$ 和 $cnt$，设当前客栈上一个色调相同的客栈为 $pre_{a_i}$，如果 $pre_{a_i} < pos$ 的话就更新 $sum_i$，否则不更新。注意最后还要更新 $pre_{a_i} = i$

最后 $ans$ 即为 $sum_i$ 之和，即

$$ans = \sum_{i = 1}^nsum_i$$

时间复杂度 ：$O(n)$

code

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

const int N = 2e5 + 5;

int n , k , p , ans;
int a[N] , b[N] , pos , pre[N] , sum[N] , cnt[N];

int main(){
	cin >> n >> k >> p;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i] >> b[i];
	}
	
	for(int i = 1 ; i <= n ; i ++){
		if(b[i] < p) pos = i;
		if(pre[a[i]] <= pos) sum[a[i]] = cnt[a[i]];
		cnt[a[i]] ++;
		ans += sum[a[i]];
		pre[a[i]] = i;
	}
	cout << ans;
	return 0;
}

T3 Mayan游戏

搜索 + 模拟

solution

首先我们看到题目显然要搜索，搜索的伪代码如下：

void dfs(step){
	if(剪枝) return;
	
	if(step > n){
		输出方案
		return;
	}
	记录当前数组 (需要回溯)
	for(...){
		for(枚举每个位置){
			向右移动
			处理移动后的局面 (solve)
			dfs(step + 1);
			回溯
			
			向左移动
			处理移动后的局面 (solve)
			dfs(step + 1);
			回溯
		}
	}
}

• solve 的部分：

  solve 分为三个部分：处理掉落，处理消除方块，记录方案

  处理掉落：枚举每一个方块，看方块下面是否为 $0$，为 $0$ 则交换位置，直到其不为 $0$

  处理消除方块：枚举每一个方块，看方块的左右 / 上下是否有相同的方块，如果左右 / 上下都有相同的方块就标记，后面再把标记的方块消除即可

  注意：这里消除后可能还有方块掉落引起新的方块消除，所以处理消除方块和处理掉落要重复执行

  记录方案：就记录就可以了 qwq

• 剪枝的部分：

  可行性剪枝：如果有颜色的数量 $\leqslant 2$ 并且 $> 0$ 则可以剪枝，如果没按指定步数清空也不行

  优化搜索过程：注意到如果有方块的话左边和右边其实是一样的，可以只搜索右边，如果左边没有方块再来搜索左边

code

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

const int N = 15;

struct node{
	int x , y , g;
}st[N];

int n , a[N][N] , to[N];

bool check(){
	for(int i = 1 ; i <= 10 ; i ++){
		if(to[i] != 0 && to[i] <= 2) return true;
	}
	return false;
}

bool clear(){
	for(int i = 1 ; i <= 5 ; i ++){
		for(int j = 1 ; j <= 7 ; j ++){
			if(a[i][j] != 0) return false;
		}
	}
	return true;
}

bool resolve(){
	bool flag = 0;
	
	for(int i = 1 ; i <= 5 ; i ++){
		for(int j = 1 ; j <= 7 ; j ++){
			int p = j;
			while(a[i][p] != 0 && a[i][p - 1] == 0 && p != 1){
				swap(a[i][p] , a[i][p - 1]); flag = 1; p --;
			}
		}
	}
	return flag;
}

void _solve(){
	int p[10][10];
	
	for(int i = 1 ; i <= 8 ; i ++){
		for(int j = 1 ; j <= 8 ; j ++){
			p[i][j] = 0;
		}
	}
	for(int i = 1 ; i <= 5 ; i ++){
		for(int j = 1 ; j <= 7 ; j ++){
			if(a[i][j] == a[i - 1][j] && a[i][j] == a[i + 1][j]) p[i][j] = 1 , p[i - 1][j] = 1 , p[i + 1][j] = 1;
			if(a[i][j] == a[i][j - 1] && a[i][j] == a[i][j + 1]) p[i][j - 1] = 1 , p[i][j + 1] = 1 , p[i][j] = 1;
		}
	}
	for(int i = 1 ; i <= 5 ; i ++){
		for(int j = 1 ; j <= 7 ; j ++){
			if(p[i][j]) a[i][j] = 0 , to[a[i][j]] --;
		}
	}
}

void solve(int x , int y , int op , int p){
	resolve(); _solve();
	while(resolve()) _solve();
	
	st[p] = {x , y , op};
}

void dfs(int t){
	if(check() || (t <= n && clear())) return;
	
	if(t > n){
		if(!clear()) return;
		for(int i = 1 ; i <= n ; i ++) cout << st[i].x << " " << st[i].y << " " << st[i].g << endl;
		exit(0);
		return;
	}
	int hya[N][N] , hyto[N];
	memcpy(hya , a , sizeof a);
	memcpy(hyto , to , sizeof to);
	
	for(int i = 1 ; i <= 5 ; i ++){
		for(int j = 1 ; j <= 7 ; j ++){
			if(a[i][j] == 0) continue;
			if(i != 1 && a[i - 1][j] == 0){
				swap(a[i][j] , a[i - 1][j]);
				solve(i - 1 , j - 1 , -1 , t);
				dfs(t + 1);
				memcpy(a , hya , sizeof hya);
				memcpy(to , hyto , sizeof hyto);
			}                                          // 向左移动 -1 （上）
			if(i != 5){
				swap(a[i][j] , a[i + 1][j]);
				solve(i - 1 , j - 1 , 1 , t);
				dfs(t + 1);
				memcpy(a , hya , sizeof hya);
				memcpy(to , hyto , sizeof hyto);
			}                                          // 向右移动 1  （下）
		}
	}
}

void print(){
	cout << endl;
	for(int i = 1 ; i <= 5 ; i ++){
		for(int j = 1 ; j <= 7 ; j ++){
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

int main(){
	cin >> n;
	
	for(int i = 1 ; i <= 5 ; i ++){
		int j = 0;
		while(1){
			int x;
			cin >> x;
			if(x == 0) break;
			
			a[i][++ j] = x;
			to[x] ++;
		}
	}
	
	dfs(1);
	cout << -1;
	return 0;
}

T4 计算系数

组合数学

solution

首先我们要知道二项式定理：

$$(x + y)^k = \sum_{i = 0}^k{\binom{k}{i}}x^iy^{k - i}$$

所以容易得出题目中 $x^n \times y^m$ 项的系数为 $\binom{k}{n}$ 由于 $x , y$ 前有系数 $a , b$ 代入得：

$$ans = \binom{k}{n}a^nb^m$$

直接求即可，注意递推组合数： $\binom{n}{m} = \binom{n - 1}{m - 1} + \binom{n - 1}{m}$ 初始化为 $\binom{i}{0} = \binom{i}{i} = 1$

code

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

const int N = 1e3 + 5;
const int mod = 1e4 + 7;

int a , b , k , n , m;
int c[N][N];

int kmi(int a , int b){
	int res = 1;
	
	while(b){
		if(b % 2) res = (res * a) % mod;
		a = (a * a) % mod;
		b /= 2;
	}
	return res % mod;
}

signed main(){
	cin >> a >> b >> k >> n >> m;
	
	for(int i = 1 ; i <= k ; i ++){
		c[i][0] = c[i][i] = 1;
	}
	for(int i = 1 ; i <= k ; i ++){
		for(int j = 1 ; j < i ; j ++){
			c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
		}
	}
	cout << (c[k][n] % mod * kmi(a , n) * kmi(b , m)) % mod;
	return 0;
}

T5 聪明的质监员

二分 + 前缀和

solution

由题可知，$y$ 是随 $w$ 的增大而减小的，因为随 $w$ 的增大满足条件的 $w_i$ 肯定变少，所以 $y_i$ 减少 $y$ 也变少

所以我们可以二分 $w$，看是否 $y \leqslant s$ ，最后再判断一下 $f(l + 1)$ 和 $f(l)$ 和 $s$ 谁更接近即可

如何快速求出 $y$ 呢，可以用前缀和解决，具体见代码，随后对于每个区间求答案即可

时间复杂度：$O((n + m)\log n)$

code

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

const int N = 2e5 + 5;
const int MAX_N = 1e6 + 5;

int n , m , s;
int w[N] , v[N] , l[N] , r[N] , sw[N] , sv[N];

int check(int wi){
	for(int i = 1 ; i <= n ; i ++){
		int e = (w[i] >= wi);
		
		sw[i] = sw[i - 1] + e;
		sv[i] = sv[i - 1] + e * v[i];
	}
	
	int cnt = 0;
	for(int i = 1 ; i <= m ; i ++){
		cnt += (sw[r[i]] - sw[l[i] - 1]) * (sv[r[i]] - sv[l[i] - 1]);
	}
	return cnt;
}

signed main(){
	cin >> n >> m >> s;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> w[i] >> v[i];
	}
	for(int i = 1 ; i <= m ; i ++){
		cin >> l[i] >> r[i];
	}
	
	int l1 = 0 , r1 = MAX_N;
	while(l1 < r1){
		int mid = (l1 + r1) >> 1;
		if(check(mid) <= s) r1 = mid;
		else l1 = mid + 1;
	}
	cout << min(abs(check(l1) - s) , abs(check(l1 - 1) - s));
	return 0;
}