CF1209

A B

水题不管

C

因为要求最终整个序列是要单调的

所以我们就考虑枚举断点\(x\)

之后把\(<x\)的数放到第一个集合

把\(> x\)的数放到第二个集合

至于\(=x\)的数

他能放到第一个集合当且仅当后面没有\(<x\)的数

否则就必须放到第二个集合

在放的时候判断合法性即可

（枚举把\(0-9\)写成了\(1 - 10\)就没了QAQ

#include<cstdio>

#include<iostream>

#include<queue>

#include<algorithm>

#include<cstring>

#include<cctype>

#include<vector>

#include<ctime>

#include<cmath>

#define LL long long

#define pii pair<int,int>

#define mk make_pair

#define fi first

#define se second

using namespace std;

const int N = 5e5 + 3;

char s[N];

int a[N];

int sum[N][11];

int belong[N];

int n;

inline int read(){

	int v = 0,c = 1;char ch = getchar();

	while(!isdigit(ch)){

		if(ch == '-') c = -1;

		ch = getchar();

	}

	while(isdigit(ch)){

		v = v * 10 + ch - 48;

		ch = getchar();

	}

	return v * c;

}

inline bool check(int x){

//	printf("x::%d\n",x);

	int now1 = -1,now2 = -1;

	for(int i = 1;i <= n;++i){

	//	printf("%d %d %d\n",i,now1,now2);

		if(a[i] < x && a[i] < now1) return 0;

		if(a[i] > x && a[i] < now2) return 0;

		if(a[i] != x){

			if(a[i] < x) now1 = max(now1,a[i]),belong[i] = 1;

			else if(a[i] > x) now2 = max(now2,a[i]),belong[i] = 2;

		}

		if(a[i] == x){

			bool flag = 0;

			for(int j = 0;j <= x - 1;++j) if(sum[i][j]) flag = 1;

			if((!flag) && (a[i] >= now1)) {

				now1 = a[i],belong[i] = 1;

			}

			else{

				if(now2 > a[i]) return 0;

				now2 = max(now2,a[i]),belong[i] = 2;

			}

		}

	}

	return 1;

}

int main(){

	int T = read();

	while(T--){

		bool flag = 0;

		n = read();

		scanf("%s",s + 1);

		for(int i = 1;i <= n;++i) a[i] = s[i] - '0';

		for(int i = n;i >= 1;--i){

			for(int j = 0;j <= 9;++j) sum[i][j] = sum[i + 1][j];

			sum[i][a[i]]++;

		}

		for(int i = 0;i <= 9;++i){

			if(check(i)){

				for(int j = 1;j <= n;++j) printf("%d",belong[j]);

				printf("\n");

				flag = 1;

				break;

			}

		}

		if(!flag) printf("-\n");

		for(int i = 1;i <= n;++i){

			for(int j = 0;j <= 9;++j) sum[i][j] = 0;

		}

	}

	return 0;

}

 

D

首先我们发现把\(a_i\)向\(b_i\)连边最后会形成若干个连通块

每个连通块的大小 - 1就是这个连通块的贡献

#include<cstdio>

#include<iostream>

#include<queue>

#include<algorithm>

#include<cstring>

#include<cctype>

#include<vector>

#include<ctime>

#include<cmath>

#define LL long long

#define pii pair<int,int>

#define mk make_pair

#define fi first

#define se second

using namespace std;

const int N = 5e5 + 3;

struct node{

	int ai;

	int bi;

}a[N];

vector <int> G[N];

int n,k;

bool flag1[N],flag2[N];

inline int read(){

	int v = 0,c = 1;char ch = getchar();

	while(!isdigit(ch)){

		if(ch == '-') c = -1;

		ch = getchar();

	}

	while(isdigit(ch)){

		v = v * 10 + ch - 48;

		ch = getchar();

	}

	return v * c;

}

queue <int> q;

int ans = 0;

inline void dfs(int x){

	flag1[x] = 1;ans++;

	for(int i = 0;i < (int)G[x].size();++i){

		int y = G[x][i];

		if(!flag1[y]) dfs(y);

	}

}

int main(){

	n = read(),k = read();

	for(int i = 1;i <= k;++i){

		a[i].ai = read();

		a[i].bi = read();

		G[a[i].ai].push_back(a[i].bi);

		G[a[i].bi].push_back(a[i].ai);

	}

	for(int i = 1;i <= n;++i) if(!flag1[i]) ans--,dfs(i);

	cout << k - ans;

}

E1E2

首先观察发现\(n\)特别小,当一个数小于等于\(20\)的时候第一反应就是要考虑状压

一个特别重要的性质

我们把所有的列按照这一列的最大值从大到小跑徐之后

最多只有前\(n\)列有用

也就是说

$n\times m \(的矩阵变成了\)n \times n$的

我们设\(f_{i,S}\)表示前\(i\)列,\(S\)这个状态对应的行的最大值已经确定的最大贡献,

\(g_{i,S}\)表示从第\(i\)列取出能够表示\(S\)这个集合的最大值

转移

\[f_{i,S} = \max_{T\subseteq S} f_{i - 1,S - T}+g_{i,T}
\]

记下来考虑怎么求\(g\)

由于存在轮换的存在

我们枚举一个集合,然后把这个集合能够表示的所有的状态都尝试用这个集合的值去更新

比如

\(1101\)能够表示\(1101\),\(1110\),\(1011\),\(0111\)

#include<cstdio>

#include<iostream>

#include<queue>

#include<algorithm>

#include<cstring>

#include<cctype>

#include<vector>

#include<ctime>

#include<cmath>

#define LL long long

#define pii pair<int,int>

#define mk make_pair

#define fi first

#define se second

using namespace std;

const int M = 21;

const int N = 2003;

int a[M][N];

int b[M][M];

int n,m;

int f[13][(1 << 13) + 5];

int g[13][(1 << 13) + 3];

struct node{

	int maxx;

	int id;

}row[N];

inline bool cmp(node x,node y){

	return x.maxx > y.maxx;

}

inline int read(){

	int v = 0,c = 1;char ch = getchar();

	while(!isdigit(ch)){

		if(ch == '-') c = -1;

		ch = getchar();

	}

	while(isdigit(ch)){

		v = v * 10 + ch - 48;

		ch = getchar();

	}

	return v * c;

}

int main(){

	int T = read();

	while(T--){

		memset(g,0,sizeof(g));

		memset(f,0,sizeof(f));

		memset(row,0,sizeof(row));

		n = read(),m = read();

		for(int i = 1;i <= n;++i){

			for(int j = 1;j <= m;++j){

				a[i][j] = read();

				row[j].maxx = max(row[j].maxx,a[i][j]);

				row[j].id = j;

			}

		}

		sort(row + 1,row + m + 1,cmp);

		m = min(n,m);

		for(int i = 1;i <= n;++i){

			for(int j = 1;j <= m;++j)

				b[i][j] = a[i][row[j].id];

		}

		for(int j = 1;j <= m;++j){

			for(int i = 1;i < (1 << n);++i){

				int res = i;

				int sum = 0;

				for(int h = 0;h < n;++h) if(res & (1 << h)) sum += b[h + 1][j];

				for(int k = 0;k < n;++k){

					g[j][res] = max(g[j][res],sum);

					int nn = res;

					res = ((nn >> (n - 1)) & 1) | ((nn << 1) & ((1 << n) - 1));

				}

			}

		}

		for(int i = 0;i < m;++i){

			for(int j = 0;j < (1 << n);++j){

				int S = ((1 << n) - 1) ^ j;

				f[i + 1][j] = max(f[i + 1][j],f[i][j]);

				for(int son = S;son;son = (son - 1) & S){

					f[i + 1][j | son] = max(f[i + 1][j | son],f[i][j] + g[i + 1][son]);

				}

			}

		}

		printf("%d\n",f[m][(1 << n) - 1]);

	}

	return 0;

}

G1

我们发现,如果存在这种东西

3 1 3 1 3

那么整个区间最终都会是同一个数

也就是说

我们设\(l_i\)表示\(i\)的第一次出现的位置,\(r_i\)表示\(i\)最后一次出现的位置

最后会出现这种情况

我们发现有交集的区间最终都会变成同一个数,变成那个数取决于这个区间中那个数出现次数最多

我们把所有的区间搞出跑一跑贪心

#include<cstdio>

#include<iostream>

#include<queue>

#include<algorithm>

#include<cstring>

#include<cctype>

#include<vector>

#include<ctime>

#include<cmath>

#define LL long long

#define pii pair<int,int>

#define mk make_pair

#define fi first

#define se second

using namespace std;

const int N = 5e5 + 3;

int a[N];

int fir[N],las[N];

int sum[N];

int n,q;

bool flag1 = 1,flag2 = 1;

inline int read(){

	int v = 0,c = 1;char ch = getchar();

	while(!isdigit(ch)){

		if(ch == '-') c = -1;

		ch = getchar();

	}

	while(isdigit(ch)){

		v = v * 10 + ch - 48;

		ch = getchar();

	}

	return v * c;

}

int ans = 0x3f3f3f3f;

struct node{

	int li;

	int ri;

	int id;

};

vector <node> G;

inline bool cmp(node x,node y){

	return x.li < y.li || (x.li == y.li && x.ri > y.ri);

}

int main(){

	n = read(),q = read();

	for(int i = 1;i <= n;++i){

		a[i] = read();

		if(!fir[a[i]]) fir[a[i]] = i;

		las[a[i]] = i;

		sum[a[i]]++;

 	}

 	for(int i = 1;i <= 200000;++i){

 		if(!fir[i]) continue;

 		if(!las[i]) G.push_back((node){fir[i],fir[i],i});

 		else G.push_back((node){fir[i],las[i],i});

 	}

 	sort(G.begin(),G.end(),cmp);

 	int ans = 0;

 	int now = 0;

 	int nowr = -1;

 	int len = 0;

 	int from = 1;

 	int maxx = 0;

 //	for(int i = 0;i < (int)G.size();++i){

 //		printf("%d %d %d\n",G[i].id,G[i].li,G[i].ri);

 //	}

 	while(now < G.size()){

 		if(G[now].li > nowr){

 			ans += nowr - from + 1 - maxx;

 			from = nowr + 1;

 			maxx = 0;

 			maxx = max(maxx,sum[G[now].id]);

			nowr = G[now].ri;

		}

		else{

			nowr = max(nowr,G[now].ri);

			maxx = max(maxx,sum[G[now].id]);

		}

		now++;

 	}

 	ans += nowr - from + 1 - maxx;

 	printf("%d\n",ans);

	return 0;

}

 

最新文章

  1. WebSocket与消息推送
  2. 前端面试那些坑之HTML篇
  3. 数据库 MySQL安装图解
  4. AFNetworking到底做了什么
  5. [Gnu]Centos7 解决 gdb 提示 Missing separate debuginfos
  6. TestLink测试软件安装条件检查不通过的解决方案
  7. leetcode 组合题
  8. Setup FTP Server On CentOS, RHEL, Scientific Linux 6.5/6.4/6.3
  9. spring的IOC，DI及案例详解
  10. HQL查询——查询返回对象类型分析
  11. React+webpack开发环境的搭建
  12. 学习TensorFlow，生成tensorflow输入输出的图像格式
  13. Nginx 配置https 服务
  14. 那些年我们没能bypass的xss filter[from wooyun]
  15. 在 python3.x中安装 Crypto 库
  16. asp.net控件中的reportview不显示
  17. ucore-lab1-练习4report
  18. 移动端采坑：Position: fixed 在Safari上的Bug
  19. 转：如何解决“My mac 64-bit”问题
  20. SSH电力项目二

热门文章

  1. iOS 停止不必要的UI动效设计
  2. PHPCMS快速建站系列之类别调用及类别显示页面
  3. MongoDB sharding 集合不分片性能更高？
  4. hdu5289 RMQ+二分
  5. hdu4324 dfs
  6. KiCad EDA 5.1.3 正式发布了
  7. qt 利用Qtimer 定时器实现定时消息发送
  8. 是时候了解React Native了
  9. @codeforces - 117C@ Cycle
  10. vue3——vue数据循环渲染