为啥根本签不上到啊

考试经过

开题T1不太会基础dp，耗了一段时间，旁边JYF20min开T2委实吓不轻，最终决定打暴力
T2目测神题先过，先写了T4的暴力，发现可以小优化一下就写了虽然依旧是暴力，T340分模拟很香也就写了，认为比较满
已经11点多看T2，写了个假贪心然后试图胡正解，发现失败了就去检查文件了
18+19+40+60=137 貌似T4的暴力还挺优秀？
T3没想到倍增，被一车人碾压，枯了

T1.暴雨

先咕

T2.AVL

贪心，细节多，咕

T3.挖掘机

这文件名什么鬼啊
显然行独立，每次贪心从第一个X开始一定不劣，考虑倍增
先预处理出每个点前、后第一个X在哪里，然后倍增预处理出跳\(2^k\)能到哪里
然后每次就\(log\)计算就好了，判一下根本不用跳的

#include <bits/stdc++.h>
using namespace std;
const int N=100050;
char a[14][N];
inline int read()
{
	char ch=getchar();int x=0;
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
int f[14][N][20],from[14][N],to[14][N],bit[20];
signed main()
{
	freopen("blueshit.in","r",stdin);
	freopen("blueshit.out","w",stdout);
	int h,w,k,q;cin>>h>>w>>k>>q;
	for(int i=1;i<=h;i++)scanf("%s",a[i]+1);
	bit[0]=1;for(int i=1;i<20;i++)bit[i]=bit[i-1]*2;
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=w;j++)if(a[i][j]=='X')
		{
			to[i][j]=from[i][j]=j;
			for(int p=j-1;p>=1;p--)
			{
				if(a[i][p]=='X')break;
				to[i][p]=j;
			}
			for(int p=j+1;p<=w;p++)
			{
				if(a[i][p]=='X')break;
				from[i][p]=j;
			}
		}
		for(int j=w;j>=1;j--)
		{
			int t=(double)log(w-j+1)/log(2)+1;
			f[i][j][0]=to[i][j+k];
			for(int p=1;p<=t;p++)
			 f[i][j][p]=f[i][f[i][j][p-1]][p-1];
		}
	}
	for(int i=1;i<=q;i++)
	{
		int d=read(),l=read(),r=read();
		int ans=0;
		for(int j=1;j<=d;j++)
		{
			int ed=from[j][r],x=to[j][l];if(ed<l)continue;
			if(ed-x+1<k){ans++;continue;}
			int t=(double)log(ed-x+1)/log(2)+1;
			for(int p=t;p>=0;p--)
			{
				if(f[j][x][p]>ed)continue;
				if(!f[j][x][p])continue;
				x=f[j][x][p];ans+=bit[p];
			}
			ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}

T4.游戏

后缀数组+线段树维护矩阵乘法，听名字就不友好，咕

考试总结

这一场暴力比较满，主要是心态调整的比较快
打暴力之前先把学过的东西想一遍，看有没有什么能套的没有，一直签不上到可不太行