T3 重复重复重复...重复重复

solution

直接暴力去求肯定不行，考虑用数学的方法：

注意到对于取模有如下性质：

$$(a + b)\mod p = a\mod p + b\mod p$$

跟据此性质，注意到一个十进制数可以拆为多个数的和，因此可以一边去累加一边去取模。

枚举 X 的位数以及相同的数字，判断取模为 0 时统计答案即可

code

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

const int N = 1e5 + 5;

int n , m , cnt , resd;

signed main(){
	freopen("repeat.in" , "r" , stdin);
	freopen("repeat.out" , "w" , stdout);
	
	cin >> n >> m;
	
	for(int d = 1 ; d <= 9 ; d ++){
		int tmp = 0;
		for(int i = 1 ; i <= n ; i ++){
			tmp = (tmp * 10 + d) % m;
			if(tmp == 0 && i >= cnt){
				cnt = i , resd = d;
			}
		}
	}
	if(!cnt){
		cout << -1;
		return 0;
	}
	for(int i = 1 ; i <= cnt ; i ++){
		cout << resd;
	}
	return 0;
}

T5 最大曼哈顿距离

直接暴力显然不行

solution

考虑拆式子

$$|x_i - x_j| + |y_i - y_j|$$

1. 当 $x_i > x_j \& y_i > y_j$ 时 原式为:

$$(x_i + y_i) - (x_j + y_j)$$

2. 当 $x_i < x_j \& y_i > y_j$ 时 原式为:

$$(x_j - y_j) - (x_i - y_i)$$

其余两种情况和上面的两种情况是对称的，不难发现，此时括号内下标相同，所有可以直接对减数取最大值，被减数取最小值，统计 $ans$ 即可

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

const int N = 2e5 + 5;
const int inf = 0x3f3f3f3f;

int n , ans , a = -inf , b = inf , c = -inf , d = inf, x , y;

signed main(){
	freopen("lenth.in" , "r" , stdin);
	freopen("lenth.out" , "w" , stdout);
	
	cin >> n;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> x >> y;
		
		a = max(a , x + y);
		b = min(b , x + y);
		c = max(c , x - y);
		d = min(d , x - y);
	}
	cout << max(a - b , c - d);
	return 0;
}

T6 简单 dp

solution

题目要求对于 {$1,2,...,n$} 的所有子集求出特定集合 $T$ 的数量，满足:

$$\sum_{i \in T} a_i = S$$

考虑 dp , 设 $dp_{i,j}$ 为考虑前 $i$ 个数字，特定集合 $T$ 的和为 $j$ 的数量，不难发现若有集合 T 满足性质，则集合 T 对答案的贡献为 $2^{|S| - |T|}$

1. 初始化：$dp_{0,0} = 2^n$ 因为集合初始中有 $2^n$ 个子集
2. 状态转移方程：

$$dp_{i,j} = dp_{i - 1 , j} + {dp_{i,j - a_i} \above 1pt 2}$$

表示选第 $i$ 个元素后集合中元素个数多一，所以对答案的贡献就要少 $\frac 12$

3.取模由于大数不好做除法，所以将除 $2$ 转化为 $2$ 模 $mod$ 意义下的乘法逆元后在乘，求乘法逆元有两种常用的方式：快速幂和递推法

code

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

const int N = 3e3 + 5;
const int mod = 998244353;

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

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

signed main(){
	freopen("sample.in" , "r" , stdin);
	freopen("sample.out" , "w" , stdout);
	
	cin >> n >> s;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
	}
	
	dp[0] = kmi(2 , n);
	for(int i = 1 ; i <= n ; i ++){
		for(int j = s ; j >= a[i] ; j --){
			dp[j] = (dp[j] + dp[j - a[i]] * kmi(2 , mod - 2)) % mod;
		}
	}
	cout << dp[s] % mod;
	return 0;
}