考试过程：先读题，然后觉得开题顺序1 4 2 3。

首先是T1，要是不考虑重复这题很简单，但是考虑重复就比较复杂了，我打完，对拍完差不多用了两个小时，然后就是忘了算内存，结果内存爆了，\(100pts ->30pts\),气炸我了。

然后是T4，我将题意化简为一个式子，\(\sum_{i=l}^{r}max(a_{i-k} -> a_i)\),但是我想了半天不会化简。

然后是T2，T3，我没什么思路，就打了个暴力。

期望得分：\(100+30+30+30=190\)

实际得分：\(30+0+30+30=90\)

考试总结：1.打完题后一定要算内存！！！尤其是花了一些时间想出的正解，不然时间就白费了。

2.打完题后可以想一些时间和空间的优化。

T1 F

思路：因为要让所有数异或出来的值相等，很容易想到求出交集，那么这道题的解题步骤分为两步：

1.求出所有数异或的交集

2.判断里面的数字是否合法

我们先从简单的问题入手，假设里面不存在相同的数字，那么只需要\(n^2\)扫一遍统计答案即可。

现在考虑如果有重复出现的数字，造成的影响。主要有三个方面：

1.类似于 \(A: 1,1,3\),\(B: 6,4,7\),那么\(1 xor 4=5,3xor7=5\),但是只有一个\(4\),也就是出现了一对多的情况

2.类似于\(A:1,2\),\(B: 2,2\) ,其中\(1xor2\)和\(2xor2\)都出现了两遍，但是却不是交集。

3..类似于\(A:1,1\),\(B: 2,2\),A数列和B数列出现了相同的数字，且可能合法的情况

首先解决问题1：我们对于一个\(i\)，利用一个\(set\)记录用当前\(A_i\)可以组成的值，如果出现过了就直接\(continue\)

那么其实解决了问题1，剩下两个问题就都解决了，证明是显然的。

最后注意，一定要算好内存！！！！

代码如下：

AC_code 



#include<bits/stdc++.h>

#define re register int

#define ii inline int

#define iv inline void

using namespace std;

const int N=2010;

struct node

{

	int val,sum;

}cun[N*N];

unordered_map<int,int> mp;

priority_queue<int,vector<int>,greater<int> > Q;

int n,cnt,ans,timi;

int a[N],b[N],hs[N*N];

unordered_set<int> S;

ii read()

{

	int x=0;char ch=getchar();bool f=1;

	while(ch<'0' or ch>'9')

	{

		if(ch=='-') f=0;

		ch=getchar();

	}

	while(ch>='0' and ch<='9')

	{

		x=(x<<1)+(x<<3)+(ch^48);

		ch=getchar();

	}

	return f?x:(-x);

}

int main()

{

	freopen("f.in","r",stdin),freopen("f.out","w",stdout);

	n=read();

	for(re i=1;i<=n;i++) a[i]=read();

	for(re i=1;i<=n;i++) b[i]=read();

	int tmp,p;

	for(re i=1;i<=n;i++)

	{

		S.clear();

		for(re j=1;j<=n;j++)

		{

			tmp=a[i]^b[j];

			if(S.find(tmp)==S.end())

			{

				S.insert(tmp);

				if(mp.find(tmp)==mp.end())

				{

					mp[tmp]=++timi;

					cun[timi].val=tmp;

					cun[timi].sum++;

					hs[timi]=i;

				}

				else

				{

					int p=mp[tmp];

					if(hs[p]!=i)

					{

						hs[p]=i;

						cun[p].sum++;

					}

				}

			}

			else continue;

		}

	}

	for(re i=1;i<=timi;i++) if(cun[i].sum>=n) Q.push(cun[i].val);

	if(!Q.size()) printf("0\n");

	else

	{

		printf("%d\n",(int)Q.size());

		while(!Q.empty())

		{

			printf("%d\n",Q.top());

			Q.pop();

		}

	}

	return 0;

}


T2 S

思路：看到数据范围，猜测应该是\(n^3\)的DP

我们设\(f_{i,j,k,0/1/2}\),表示当前选了\(i\)个\(R\),\(j\)个\(G\),\(k\)个\(Y\),结尾为\(R/G/Y\)的最小步数。

\(g_{0/1/2,k}\)表示原序列第\(k\)个\(R/G/Y\)的位置

那么转移就是\(f_{i+1,j,k,0}=min(f_{i+1,j,k,0,min(f_{i,j,k,1},f_{i,j,k,2})+abs(g_{0,i+1}-(i+j+k+1)})\)

最后记得将\(ans/2\)

代码如下：

AC_code 



#include<bits/stdc++.h>

#define re register int

#define ii inline int

#define iv inline void

using namespace std;

const int N=210;

int n,ans;

char s[N*2];

int f[N][N][N][3],g[3][N*2];

ii read()

{

	int x=0;char ch=getchar();bool f=1;

	while(ch<'0' or ch>'9')

	{

		if(ch=='-') f=0;

		ch=getchar();

	}

	while(ch>='0' and ch<='9')

	{

		x=(x<<1)+(x<<3)+(ch^48);

		ch=getchar();

	}

	return f?x:(-x);

}

int main()

{

	freopen("s.in","r",stdin),freopen("s.out","w",stdout);

	n=read();

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

	for(re i=1;i<=n;i++)

	{

		if(s[i]=='R') g[0][++g[0][0]]=i;

		else if(s[i]=='G') g[1][++g[1][0]]=i;

		else if(s[i]=='Y') g[2][++g[2][0]]=i;

	}

	if(g[0][0]>n/2 or g[1][0]>n/2 or g[2][0]>n/2) {printf("-1\n");return 0;}

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

	for(re i=0;i<3;i++) f[0][0][0][i]=0;

	for(re len=0;len<=n;len++)

	{

		for(re i=0;i<=min(len,g[0][0]);i++)

		{

			for(re j=0;j<=g[1][0] and i+j<=len;j++)

			{

				if(len-i-j>g[2][0] ) continue;

				if(i+1<=g[0][0]) f[i+1][j][len-i-j][0]=min(f[i+1][j][len-i-j][0],min(f[i][j][len-i-j][1],f[i][j][len-i-j][2])+abs(len+1-g[0][i+1]));

				if(j+1<=g[1][0]) f[i][j+1][len-i-j][1]=min(f[i][j+1][len-i-j][1],min(f[i][j][len-i-j][0],f[i][j][len-i-j][2])+abs(len+1-g[1][j+1]));

				if(len-i-j+1<=g[2][0]) f[i][j][len-i-j+1][2]=min(f[i][j][len-i-j+1][2],min(f[i][j][len-i-j][0],f[i][j][len-i-j][1])+abs(len+1-g[2][len-i-j+1]));

			}

		}

	}

	for(re i=0;i<3;i++) ans=min(f[g[0][0]][g[1][0]][g[2][0]][0],min(f[g[0][0]][g[1][0]][g[2][0]][1],f[g[0][0]][g[1][0]][g[2][0]][2]))>>1;

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

	return 0;

}


T3 Y

咕咕咕

T4 O

思路：这里有一个结论，对于随机数据，一个单调栈里的元素个数为\(log2(n)\)个。

那么对于这道题，我们对于每个点维护一个单调递减的单调栈，栈里维护两个信息，一个是权值，另一个是时间。

这样我们在开一个\(vector\)数组记录每个时刻要在线段树更新的值，然后计算答案即可。

代码如下：

AC_code 



#include<bits/stdc++.h>

#define ll long long

#define re register int

#define ii inline int

#define iv inline void

#define f() cout<<"fuck"<<endl

#define head heeead

#define next neet

using namespace std;

const int N=2e5+10;

struct CUN

{

	int id,t,l,r;

}cun[N];

struct node

{

	int val,timi;

	friend bool operator < (node x,node y){return x.timi<y.timi;}

};

int cnt,sta[N];

vector<pair<int,int> >v[N];

int n,q;

int a[N];

long long ans[N];

ii read()

{

	int x=0;char ch=getchar();bool f=1;

	while(ch<'0' or ch>'9')

	{

		if(ch=='-') f=0;

		ch=getchar();

	}

	while(ch>='0' and ch<='9')

	{

		x=(x<<1)+(x<<3)+(ch^48);

		ch=getchar();

	}

	return f?x:(-x);

}

inline bool com(CUN x,CUN y) {return x.t<y.t;}

struct Segment_Tree

{

	#define lc (rt<<1)

	#define rc (rt<<1|1)

	#define mid ((l+r)>>1)

	ll sum[N<<2];

	//iv pp(int rt) {sum[rt]=sum[lc]+sum[rc];}

	iv build(int rt,int l,int r)

	{

		if(l==r)

		{

			sum[rt]=a[l];

			return;

		}

		build(lc,l,mid),build(rc,mid+1,r);

		sum[rt]=sum[lc]+sum[rc];

	}

	iv change(int rt,int l,int r,int p,int z)

	{

		if(l==r)

		{

			sum[rt]=z;

			return;

		}

		if(mid>=p) change(lc,l,mid,p,z);

		else change(rc,mid+1,r,p,z);

		sum[rt]=sum[lc]+sum[rc];

	}

	ll query(int rt,int l,int r,int L,int R)

	{

		if(L<=l and r<=R) return sum[rt];

		if(mid>=R) return query(lc,l,mid,L,R);

		if(mid<L) return query(rc,mid+1,r,L,R);

		return query(lc,l,mid,L,R)+query(rc,mid+1,r,L,R);

	}

	#undef lc

	#undef rc

	#undef mid

}T;

signed main()

{

	freopen("o.in","r",stdin),freopen("o.out","w",stdout);

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

	for (re i=1;i<=n;++i)

	{

		a[i] = read ();

		while (cnt && a[i] >= a[sta[cnt]]) cnt -- ;

		for (re j=1;j <= cnt; ++ j) v[i - sta[j]].push_back (make_pair(i,a[sta[j]]));

		sta[++cnt] = i;

	}

	T.build (1,1,n);

	for(re i=1;i<=q;i++) cun[i]=(CUN){i,read(),read(),read()};

	sort(cun+1,cun+q+1,com);

	int now=1;

	for(re i=0;i<=n;i++)

	{

		for(re j=0;j<v[i].size();j++) T.change(1,1,n,v[i][j].first,v[i][j].second);

		while(cun[now].t==i) {ans[cun[now].id]=T.query(1,1,n,cun[now].l,cun[now].r);++now;}

	}

	for(re i=1;i<=q;i++) printf("%lld\n",ans[i]);

	return 0;

}


最新文章

  1. sping注解
  2. //解决validator验证插件多个name相同只验证第一的问题
  3. sizzle源码分析 （1）sizzle架构
  4. HTML统一资源定位器
  5. 关于myeclipse中导入的项目修改项目名使得发布到tomcat访问路径正确
  6. Spring boot将配置属性注入到bean类中
  7. MVC应用程序显示上传的图片
  8. openstack第六章：dashboard
  9. bzoj3718 树状数组
  10. linux kill 命令【待完善】【转】
  11. MYSQL在centos上主从配置
  12. 《mysql从入门到精通》提高
  13. javascript进阶笔记(3)
  14. django模板中的自定义过滤器
  15. 《学习R》
  16. gitlab启用https的配置
  17. 【java 类加载的深入研究1】loadClass()的研究
  18. Servlet路径
  19. canvas绘制经典星空连线效果
  20. 【Python】python基础语法 编码

热门文章

  1. 1day漏洞反推技巧实战(2)
  2. Linux内核学习之2号进程kthreadd
  3. IO流实现GBK写入文件然后转换UTF-8
  4. windows 下使用 mingw编译器 调试时 无法跟进源码
  5. Linux系列（11） - PATH环境变量
  6. Shell系列（6）- 管道符
  7. 送你一个Python 数据排序的好方法
  8. 常用的ppt技巧
  9. Windows下升级Python3.7.7后（原Python3.6.2版本）如何切换Python版本
  10. spl_autoload_register 实现自动加载