• 2021CCPC 哈尔滨(B D E I J)

    2021CCPC 哈尔滨(B D E I J)

    Dashboard - The 2021 China Collegiate Programming Contest (Harbin) - Codeforces

    B. Magical Subsequence(贪心 + dp)

    对于本题 ， 可以注意到可以组成的数的值域非常小 ， 只有 [2 , 200] , 我们不妨从可以组成的数下手 ， 枚举每一个可以组成的数 ， 确定组成当前数的最大贡献。如何确定这个最大贡献呢 ， 考虑一个经典 dp

    d p [ i ] [ j ] 表示组成数字 i ，数列前 j 位的最大贡献。 dp[i][j] 表示组成数字 i ， 数列前 j 位的最大贡献。 dp[i][j]表示组成数字i，数列前j位的最大贡献。

    考虑状态转移 ， 不难想出 ， 第 j 位有两种选择

    1: 第 j 位不参与组成 i

    d p [ i ] [ j ] = m a x ( d p [ i ] [ j ]   ,   d p [ i − 1 ] [ j ] ) dp[i][j] = max(dp[i][j]~,~dp[i - 1][j]) dp[i][j]=max(dp[i][j] , dp[i−1][j])

    2. 第 j 位参与组成 i

    d p [ i ] [ j ] = m a x ( d p [ i ] [ j ]   ,   d p [ i ] [ p o s [ i − a [ j ] ] − 1 ] + 2 ) dp[i][j] = max(dp[i][j]~,~dp[i][pos[i-a[j]]-1]+2) dp[i][j]=max(dp[i][j] , dp[i][pos[i−a[j]]−1]+2)

    这里的 pos[i - a[j]] 指的是当前位可以从前面所有等于 i - a[j]的位置转移过来 ， 但是显然这么写时间复杂度是 n^2 的 ， 不能接受。考虑贪心 ， 我们只从前面等于 i - a[j] 的最后一个位置转移 ， 因为前面位置的贡献是一定不可能有最后一个位置优的 ， 这样就能做到线性复杂度。

    时间复杂度 O ( 200 n ) 时间复杂度O(200n) 时间复杂度O(200n)

    #include
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

int n , a[N] , maxx;

int pos[310] , dp[210][N];

/*
和为 i 前 j 个数的最大贡献
*/

signed main(){

	IOS
	cin >> n;
	for(int i = 1 ; i <= n ; i ++ ) cin >> a[i];
	for(int i = 2 ; i <= 200 ; i ++) {
		for(int j = 1 ; j <= 100 ; j ++) pos[j] = 0;
		for(int j = 1 ; j <= n ; j ++) {
			if(a[j] >= i || !pos[i - a[j]]) dp[i][j] = dp[i][j - 1];
			else dp[i][j] = max(dp[i][j - 1] , dp[i][pos[i - a[j]] - 1] + 2);
			pos[a[j]] = j;
		}
	}
	for(int i = 2 ; i <= 200 ; i ++) maxx = max(maxx , dp[i][n]);
	
	cout << maxx << "\n";

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41

    D. Math master(枚举子集 ， meet in the middle)

    思路：可以注意到每一个数字最多只有 18 位 ， 考虑枚举子集 。先枚举分子的子集 ， 把枚举出来的所有需要删的数和剩余的分子存起来 ， 然后对分母枚举子集 ， 可以得到要删去的数和剩余的分母 ， 用分母求出分子 ， 然后查询即可。

    时间复杂度 O ( n 2 n l o g ( 2 n ) ) 时间复杂度O(n2^nlog(2^n)) 时间复杂度O(n2nlog(2n))

    由于比标程复杂度多个log ，复杂度比较极限，所以需要实现的精细一点。

    用分母求分子的时候会爆 ll ， 用 __int128 转化即可

    #include
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 30 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

int t , a[N] , b[N] , n , m , st , ed;
string s1 , s2;

signed main(){

	IOS
	cin >> t;
	
	while(t --){
		cin >> s1 >> s2;
		n = s1.size();
		m = s2.size();
		st = ed = 0;
		for(int i = 0 ; i < n ; i ++) a[i] = s1[i] - '0' , st = st * 10 + a[i];
		for(int i = 0 ; i < m ; i ++) b[i] = s2[i] - '0' , ed = ed * 10 + b[i];
		
		set<pair<string , int>>st1;
		
		for(int i = 1 ; i <= (1ll << n) ; i++){
			int now = 0;
			string del;
			for(int j = 0 ; j < n ; j ++){
				if((i >> j) & 1){
					del += a[j] + '0';
				}else{
					now = now * 10 + a[j];
				}	
			}
			sort(del.begin() , del.end());
			st1.insert({del , now});
		}
		
		int ans = 9e18 , els = 0;
		
		for(int i = 1 ; i <= (1ll << m) ; i++){
			int now = 0;
			string del;
			for(int j = 0 ; j < m ; j ++){
				if((i >> j) & 1){
					del += b[j] + '0';
				}else{
					now = now * 10 + b[j];
				}	
			}
			sort(del.begin() , del.end());
			if(!now) continue;
			if((__int128) st * now % (__int128) ed) continue;
			int pre = (__int128) st * now / ed;
			if(st1.find({del , pre}) != st1.end()){
				if(pre < ans){
					ans = pre;
					els = now;
				}
			}
		}	
		cout << ans << " " << els << "\n";
	}

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72

    E. Power and Modulo(思维)

    思路：不难发现一个小性质 ， 那就是

    A i = ( A i − 1 ∗ 2 ) % M （ A 1 = 0 ∣ ∣ A 1 = 1 ） A_i = (A_{i-1}*2)\%M（A_1=0||A_1 = 1） Ai​=(Ai−1​∗2)%M（A1​=0∣∣A1​=1）

    这个 M 应该是唯一确定的. 那我们只需要判断 M 是否存在且唯一即可 ， 注意特判 M = 1 ， 即 A 数组全为 0 的情况。

    时间复杂度 O ( n l o g n ) 时间复杂度O(nlogn) 时间复杂度O(nlogn)

    #include
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

int t , n;
int a[N] , res;

bool judge(){
	
	int cnt = 0;
	for(int i = i = 1 ; i <= n ; i ++) if(!a[i]) cnt += 1;
	if(cnt == n) {
		res = 1;
		return 1;
	}
	
	set<int>ans;
	if(a[1] < 0 || a[1] > 1) return 0;
	for(int i = 2 ; i <= n ; i ++){
		if(a[i] >= a[i - 1]){
			if(a[i - 1] * 2 != a[i]) return 0;
		}else{
			res = a[i - 1] * 2 - a[i];
			ans.insert(a[i - 1] * 2 - a[i]);
		}
	}
	if(ans.size() != 1) return 0;
	else return 1;
	
}

signed main(){

	IOS
	cin >> t;
	
	while(t --){
		
		cin >> n;
		for(int i = 1 ; i <= n ; i ++) cin >> a[i];
		if(judge()){
			cout << res << "\n";
		}else{
			cout << "-1\n";
		}
	}

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57

    I. Power and Zero（贪心）

    思路：不难想到需要计算二进制每一位的数量 ，所以问题转化成 需要把二进制的数量数组变成 低位大 ， 高位小的阶梯型数组 ， 而且需要最低位的最大值最小 ， 这个值即是我们需要的答案 。不难发现 ， 对于数组的转换 ， 一个高位可以转化成两个相邻的低位 ， 即 cnt[i] → 2 * cnt[i - 1] , 反过来却不行 ， 即只能由高位补低位 ， 我们考虑贪心的去补位 ， 对于每一位 ， 只要比低位大就向低位补位 ， 补到阶梯型为止。

    时间复杂度不太会算，但是跑的飞快 时间复杂度不太会算 ， 但是跑的飞快 时间复杂度不太会算，但是跑的飞快

    #include
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

int t , n;
int a[N] , bit[32];

signed main(){

	IOS
	cin >> t;
	
	while(t --) {
		cin >> n;
		
		for(int i = 0 ; i <= 30 ; i ++) bit[i] = 0;
		
		for(int i = 1 ; i <= n ; i ++) {
			cin >> a[i];
			for(int j = 0 ; j <= 30 ; j ++) {
				if(a[i] >> j & 1) bit[j] += 1;
			}
		}
		
		bool tag = true;
		
		while(tag) {
			
			tag = false;
			
			for(int i = 30 ; i >= 1 ; i --) {
				if(bit[i] > bit[i - 1]) {
					int need = (bit[i] - bit[i - 1] - 1) / 3 + 1;
					bit[i] -= need;
					bit[i - 1] += need * 2;
					tag = true;
				}
			}
		}
		

		cout << bit[0] << "\n";
		
	}

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55

    J. Local Minimum（签到）

    计算即使行最值又是列最值的元素个数即可。

    时间复杂度 O ( n m ) 时间复杂度O(nm) 时间复杂度O(nm)

    #include
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 1e3 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

int a[N][N] , n , m , res;
bool vis[N][N];

signed main(){

	IOS
	cin >> n >> m;
	for(int i = 1 ; i <= n ; i ++) {
		for(int j = 1 ; j <= m ; j ++) {
			cin >> a[i][j];
		}
	}
	for(int i = 1 ; i <= n ; i ++) {
		int minn = 9e18;
		for(int j = 1 ; j <= m ; j ++) minn = min(minn , a[i][j]);
		for(int j = 1 ; j <= m ; j ++) if(a[i][j] == minn) vis[i][j] = 1;
	}
	
	for(int j = 1 ; j <= m ; j ++) {
		int minn = 9e18;
		for(int i = 1 ; i <= n ; i ++) minn = min(minn , a[i][j]);
		for(int i = 1 ; i <= n ; i ++) if(a[i][j] == minn) {
			if(vis[i][j]) res += 1;
		}
	}
	
	cout << res << "\n";

	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42

    算法讨论小群 ： 545214567(QQ)

  • 相关阅读:
    Tensorflow笔记（二）：激活函数、优化器等、神经网络模型实现（商品销量预测）
    SpringBoot: Controller层的优雅实现
    学习笔记-OS - Exploits
    探讨基于IEC61499 的分布式 ISA Batch 控制系统
    进程的基本概念（操作系统）
    【21天学习挑战】经典算法之【选择排序】
    debian设置允许ssh连接
    [SpringMVC]第三篇:作用域传参
    Go：模幂算法(附完整源码)
    07MCM一位评委老师的意见及MIT取得特等奖的历程描述
  • 原文地址：https://blog.csdn.net/woshilichunyang/article/details/132884126