考场

T1 没看懂

T4 一眼回滚莫队，但忘记怎么写了，小慌

模拟 T1 题意的时候教练让 zsy 澄清了一下，确定了我不会做。。。

T2 一看就是毒瘤题，T3 感觉比较可做

T4 确定了回滚的细节，除了板子不会写其他都会了

7.40 开写，1h 后写完前三题暴力

先回想了一下普通莫队和回滚的思想，结合题目具体确定了实现方法，9.00 开写，比想象中顺利多了，9.40 过样例，10.00 过拍

剩下的时间没事干，先把 T3 的两个部分分写了，然后给 T1 加了个记忆化，对着数据卡常（一开始要 7s），随机的极限数据能在 0.8~1.1s 内跑过，记忆化后有点像状压 DP，但没啥时间了，就没细想。（卡常期间想起 T4 就是区间 mex，貌似可以主席树，感觉要被全场切了）

交题的时候发现 T1 还有个地方可以卡，但想着不差这点，且最后 10min 不想再改，就放弃了

res

rk1 95+65+70+100

T1 真被卡了 5ms

rk2 gjy 50+100+50+50

rk3 付文暄 50+65+100+20

总结

学东西的时候一定要注重思想，并想清楚代码为什么这么实现，这样即使忘了也能现推

发现自己心态还是不太好，如果有会做的非一眼题就比较正常，该拼部分分拼部分分，该卡常卡常；但如果一个题都不会，就很烦，暴力懒得想优化，部分分稍微想想就丢了，然后肝题到快结束，最后打 tetris。

最近倒是不打 tetris 了，但还是会心态爆炸，考场不是自闭的地方，即使啥都不会也要打满暴力，想不出题就优化暴力，卡常，不要把考场的时间用来发呆。

改题时发现对于拼接 hash 这种细节很多的东西很容易调不出来，以后遇到这类问题先在草稿纸上列好，尤其是边界，不要写完之后再改，效率太低。

打表

考场做法：考虑先枚举出每次由哪个 CPU 决策（称为 CPU 的决策顺序），在 dfs 出它当前这位填 \(0\) 还是 \(1\)，记忆化未决策的 CPU 和当前已填位状态即可。

正确性：显然不论哪个 CPU 做决策，选择的是同一位，但填的数相反（可以用反证法证明），因此被选择的位的顺序是固定的（称为最优顺序）。先强制令每次决策时决策剩下的最高位，那么对于一个 CPU 的决策序列，可以将它的顺序掉换成最优顺序，由于所有 CPU 的决策顺序都会被枚举到，那么这么做是等价的。

（其实到这里就很接近正解了， 但考场上没多想）

code 
const int mod = 1e9+7;

int n,m,a[1<<18];

int all,ans;

unordered_map<int,int> f[1<<19];

int Pow(int x,int y=mod-2)

	{ int res=1; for(;y;y>>=1,x=(LL)x*x%mod)if(y&1)res=(LL)res*x%mod; return res; }

int dfs(int u,int cpu,int p) {

	if( u > n ) return abs(a[p]-a[m]);

	if( f[cpu].count(p) ) return f[cpu][p];

	int res0 = dfs(u+1,cpu>>1,p<<1), res1 = dfs(u+1,cpu>>1,p<<1|1);

	return f[cpu][p] = cpu&1 ? min(res0,res1) : max(res0,res1);

}

signed main() {

	read(n,m); all = (1<<n--)-1;

	For(i,0,all) read(a[i]);

	for(int i = 1<<n+1, ii = i|all; i <= ii; ++i) ans = (ans + dfs(0,i,0)) %mod;

	write((LL)ans*Pow(1<<n+1)%mod);

	return iocl();

}

蛇

只考虑蛇向右的情况，它的路径一定是先向左走一段（可能为 \(0\)），再调头向右，然后上下扭动地走，最后再调头向左。

考虑 hash 求出路径的左右的部分，然后中间的路径数可以 DP。（需要特判 \(|S|\le2\) 的情况）

细节很多。

code 
const int N = 2e3+5, mod = 1e9+7, dx[]={0,-1,0,1}, dy[]={-1,0,1,0};

char s[2][N],t[N];

const LL P = 999999001;

int n,m;

LL ans,f[2][N][N];

LL base[N],hs[4][N],ht[2][N];

void ckadd(LL &x,LL y) { x+=y; if(x>=mod) x-=mod; }

namespace sub {

bool vis[2][N];

void dfs(int x,int y,int u) {

	if( u == m ) return ++ans, void();

	For(i,0,3) {

		int xx = x+dx[i], yy = y+dy[i];

		if( xx<0||xx>1||yy<1||yy>n || vis[xx][yy] || s[xx][yy] != t[u+1] )

			continue;

		vis[xx][yy] = 1, dfs(xx,yy,u+1), vis[xx][yy] = 0;

	}

}

void main() {

	if( m > 2 ) return; cerr<<"sub"<<endl;

	For(i,0,1) For(j,1,n) if( s[i][j] == t[1] )

		vis[i][j] = 1, dfs(i,j,1), vis[i][j] = 0;

	write(ans%mod);

	iocl(), exit(0);

}

}

LL hsh(LL *h,int l,int r) { return (h[r] - h[l-1]*base[r-l+1] %P+P)%P; }

LL rhsh(LL *h,int l,int r) { return (h[l] - h[r+1]*base[r-l+1] %P+P)%P; }

void work() {

	memset(f,0,sizeof f);

	For(i,1,n) hs[0][i] = (hs[0][i-1] * 997 + s[0][i]) %P, // 1为高位

			   hs[1][i] = (hs[1][i-1] * 997 + s[1][i]) %P;

	rFor(i,n,1) hs[2][i] = (hs[2][i+1] * 997 + s[0][i]) %P, // n为高位

				hs[3][i] = (hs[3][i+1] * 997 + s[1][i]) %P;

	For(i,1,m) ht[0][i] = (ht[0][i-1] + t[i] * base[i-1]) %P;

	rFor(i,m,1) ht[1][i] = (ht[1][i+1] * 997 + t[i]) %P;

	For(i,1,n) {

		f[0][i][1] = s[0][i]==t[1], f[1][i][1] = s[1][i]==t[1];

		For(j,1,i) {

			int len = i-j+1;

			f[1][i][len*2] =

					(hsh(hs[0],j,i)+rhsh(hs[3],j,i)*base[len])%P == ht[0][len*2];

			f[0][i][len*2] =

					(hsh(hs[1],j,i)+rhsh(hs[2],j,i)*base[len])%P == ht[0][len*2];

		}

	}

	For(i,1,n) For(j,2,m) {

		if( s[0][i] == t[j] ) {

			ckadd(f[0][i][j],f[0][i-1][j-1]);

			if( s[1][i] == t[j-1] ) ckadd(f[0][i][j],f[1][i-1][j-2]);

		}

		if( s[1][i] == t[j] ) {

			ckadd(f[1][i][j],f[1][i-1][j-1]);

			if( s[0][i] == t[j-1] ) ckadd(f[1][i][j],f[0][i-1][j-2]);

		}

	}

	For(i,1,n) ckadd(ans,f[0][i][m]), ckadd(ans,f[1][i][m]);

	For(i,1,n) rFor(j,i-1,1) {

		int len = i-j+1; if( len*2 > m ) break;

		if( (hsh(hs[0],j,i)*base[len]+rhsh(hs[3],j,i))%P == ht[1][m-len*2+1] )

			ckadd(ans,f[1][j-1][m-len*2]);

		if( (hsh(hs[1],j,i)*base[len]+rhsh(hs[2],j,i))%P == ht[1][m-len*2+1] )

			ckadd(ans,f[0][j-1][m-len*2]);

	}

}

signed main() {

	base[0] = 1; For(i,1,2e3) base[i] = base[i-1] * 997 %P;

	scanf("%s%s%s",s[0]+1,s[1]+1,t+1); n = strlen(s[0]+1), m = strlen(t+1);

	sub::main();

	work(), reverse(s[0]+1,s[0]+n+1), reverse(s[1]+1,s[1]+n+1), work();

	write(ans);

	return iocl();

}

购物

显然如果 \(a_i\) 能凑出 \(x\)，那么区间 \([\lceil\frac x2\rceil,x]\) 中的 \(k\) 都合法。

结论：将 \(a\) 排序，记 \(s_i\) 为 \(a_i\) 前缀和，那么 \((1,s_n)\) 中不合法的 \(k\) 就是 \([s_{i-1},\frac{a_i}2]\)（这个区间如果为空则不考虑）的并集。

证明：

已处理完了 \([1,s_{i-1}]\)，当前处理的区间 \((s_{i-1},\frac{a_i}2)\)。如果这个区间为空显然正确；如果不为空，则前 \(i-1\) 个数最多只能凑到 \(s_{i-1}\)，而第 \(i\) 个数之后的数都 \(\ge a_i\)，最少也是 \(\frac{a_i}2\)，因此这个区间是不可能被补上的。

再考虑证明 \([\frac{a_i}2,s_i]\) 一定合法。如果前面没有空隙显然合法；如果有，那么空隙大小一定 \(\le\frac{a_i}2\)（前面的总长只有 \(\frac{a_i}2\)），设空隙为 \((l,r)\)，则将 \(l\) 左边、\(r\) 右边的区间加 \(a_i\) （总和加 \(a_i\)，左端点加 \(\frac{a_i}2\)，右端点加 \(a_i\)）后这个区间变为 \((l+a_i,r+\frac{a_i}2)\)，一定为空。

code 
const int N = 1e5+5;

int n,a[N];

LL ans,s[N];

signed main() {

	read(n);

	For(i,1,n) read(a[i]); sort(a+1,a+n+1);

	For(i,1,n) {

		s[i] = s[i-1] + a[i];

		ans -= max((a[i]+1)/2-s[i-1]-1,0ll);

	}

	write(ans+s[n]);

	return iocl();

}

ants

裸的回滚莫队

值域上每个点维护它向左、向右能连续到哪，插入 \(x\) 时与 \(x-1,x+1\) 合并，每次有三个点需要回滚。

考场代码 
const int N = 1e5+5;

int n,m,a[N];

struct Q { int l,r,id; } q[N];

int size,mm,now,be[N],le[N],ri[N],ans[N];

bool vis[N];

int tp; struct Node { int p,v,l,r; } stk[N*3];

bool operator < (const Q &x,const Q &y)

	{ return be[x.l]!=be[y.l] ? x.l<y.l : x.r<y.r; }

void push(int x) { stk[++tp] = Node{x,vis[x],le[x],ri[x]}; }

void add(int x,bool op) {

	int l = le[x-1], r = ri[x+1];

	if( vis[x-1] ) { if( op ) push(l); } else l = x;

	if( vis[x+1] ) { if( op ) push(r); } else r = x;

	if( op ) push(x);

	vis[x] = 1, le[x] = l, ri[x] = r, ri[l] = r, le[r] = l;

	ckmax(now,ri[x]-le[x]+1);

}

void clear() {

	while( tp ) {

		auto u = stk[tp--];

		vis[u.p] = u.v, le[u.p] = u.l, ri[u.p] = u.r;

	}

}

int bf(int l,int r) {

	For(i,l,r) add(a[i],1);

	int res = now;

	now = 0, clear();

	return res;

}

signed main() {

//	freopen("d.in","r",stdin);

//	freopen("d.out","w",stdout);

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

	For(i,1,n) read(a[i]), be[i] = (i-1)/size+1, le[i] = ri[i] = i;

	For(i,1,m) {

		int l,r; read(l,r);

		if( be[l] == be[r] ) ans[i] = bf(l,r);

		else q[++mm] = Q{l,r,i};

	}

	sort(q+1,q+mm+1);

	for(int i = 1, r; i <= mm; ++i) {

		if( be[q[i].l] != be[q[i-1].l] ) {

			now = 0, r = size * be[q[i].l];

			For(i,1,n) vis[i] = 0, le[i] = ri[i] = i;

		}

		while( r < q[i].r ) add(a[++r],0);

		int l = size * be[q[i].l] + 1, old = now;

		while( l > q[i].l ) add(a[--l],1);

		ans[q[i].id] = now;

		now = old, clear();

	}

	For(i,1,m) write(ans[i]);

	return iocl();

}

最新文章

  1. 04. Web大前端时代之：HTML5+CSS3入门系列~HTML5 表单
  2. 关于网络-get/post
  3. Android源码编译出错解决办法
  4. oracle创建表相关
  5. h5上传图片
  6. Python开发简单爬虫 - 慕课网
  7. uva 10534
  8. C语言--const修饰指针解析
  9. VBA怎样统计同一类型的数据的总和
  10. jQuery trigger one用法
  11. 【Web开发】Mean web开发 01-Express实现MVC模式开发
  12. 学会数据库读写分离、分表分库——用Mycat，这一篇就够了！
  13. 使用 Skeleton Screen 提升用户感知体验
  14. C#递归查询
  15. kotlin 语法跟 java 的不同
  16. Bootstrap如何禁止响应式布局 不适配
  17. 谈谈 JavaScript 的正则表达式
  18. MXNet 中的 hybird_forward 的一个使用技巧
  19. zabbix 利用python脚本实现短信告警
  20. html复习之标签整理

热门文章

  1. 一文带你搞定AOP切面
  2. 5G时代，视频会议的未来
  3. jmeter正则表达式介绍
  4. goproxy.io
  5. 使用Windows客户端连接Linux系统中的MySQL时产生的错误已经解决
  6. 前端 | Nuxt.js axios baseURL，proxy 代理
  7. 【设计模式】DDD 设计理念
  8. DLL-使用DLL
  9. 浅谈 asp.net core web api
  10. linux下静态库的制作