。。。。

\(boom\)

不知道怎么的 \(T1\) 上来我就给跳过了，然后就开始先干\(T3\)，感觉并不是很简单，但是也不是能说是很难。

然后我就突然想到了一种可以过掉一半数据的 \(dp\)，之后居然一下子就成功了。

大样例一测，过了？！

之后感觉还行，然后回头管 \(T1\)，但是却没有发现那个极其显然的双指针，然后我人无，还在 \(l\) 和 \(r\) 输出之前就特判 \(l\),\(r\)，然后惨烈。。。。

\(T2\) 本以为有一些部分分数，然而一分也没有。。。。。

a

我们如果固定左上的那一个端点，就会发现这个对于接下来的 \(n-i+1\) 行，它的合法范围其实都是有关联的。

如果我们使用莫队的思想 \((two\;pointers)\)，就会每一行均摊一个 \(m\)，之后就是 \(\mathcal O(n^2m)\)

#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define asm(i,x) for(register signed i=head[x];i;i=edge[i].next)
namespace xin_io
{
	#define debug cout<<"debug"<<endl
	#define sb(x) cout<<#x" = "<<x<<' '
	#define jb(x) cout<<#x" = "<<x<<endl
	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
	#define scanf ak = scanf
	int ak;
}
#define int long long
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+7;
namespace xin
{
	#define calc(x1,y1,x2,y2) (he[x2][y2] - he[x2][y1-1] - he[x1-1][y2] + he[x1-1][y1-1])
	int n,m;
	int l,r,ans = 0;
	char s[maxn];
	int he[31][maxn/10];
	int los[maxn],ros[maxn];
	inline short main()
	{
		scanf("%lld%lld",&n,&m);
		try(i,1,n)
		{
			scanf("%s",s+1);
			try(j,1,m)
			{
				he[i][j] = he[i-1][j] + he[i][j-1] - he[i-1][j-1] + (s[j] == '1');//,cout<<he[i][j]<<' ';
		//		if(s[j] == '1') sp1 = 0;
			}
		}
		scanf("%lld%lld",&l,&r);
		if(l == 0 and r == n * m)
		{
			cout<<((n + 1) * n / 2) * ((m + 1) * m/ 2)<<endl;
			return 0;
		}
		try(i,0,n-1) 
		{
			memset(los,0,sizeof(int) * (n + 1));
			memset(ros,0,sizeof(int) * (n + 1));
			try(j,0,m-1)
			{	
				try(x,i+1,n)
				{
					try(y,los[x],m)
					{
						if(he[x][y] - he[i][y] - he[x][j] + he[i][j] >= l)
							{los[x] = y; break;}
						if(y == m) los[x] = m + 1;
					}
					try(y,ros[x]+1,m)
					{
						if(he[x][y] - he[i][y] - he[x][j] + he[i][j] > r)
							{ros[x] = y - 1; break;}
						if(y == m) ros[x] = m;
					}
					ans += ros[x] - los[x] + 1;
				}
			}
		}
		cout<<ans<<endl;
		return 0;
	}
}
signed main() {return xin::main();}

b

题解写的多好

#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define asm(i,x) for(register signed i=head[x];i;i=edge[i].next)
namespace xin_io
{
	#define debug cout<<"debug"<<endl
	#define sb(x) cout<<#x" = "<<x<<' '
	#define jb(x) cout<<#x" = "<<x<<endl
	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
	char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll; typedef unsigned long long ull;
	class xin_stream{public:template<typename type>inline xin_stream &operator >> (type &x)
	{
		register type s = 0; register int f = 1; register char ch = gc();
		while(!isdigit(ch)) {if(ch == '-') f = -1; ch = gc();}
		while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch  xor 48),ch = gc(); return x = s * f,*this;
	}}io;
}
#define int long long
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+7,mod = inf; const ll llinf = 1e18+7;
namespace xin
{
	int cnt[21][maxn/10],n,m,ans = 0,ton[21][maxn/10],s[maxn],maxx = -inf;
	inline short main()
	{
		io >> n >> m;
		try(i,1,n)try(j,1,m)
		{
			register int x; io >> x;
			ton[i][x]++; maxx = std::max(maxx,x);
		}
		try(i,1,n) try(j,1,maxx) for(register int k=1;k*j<=maxx;++k)
			cnt[i][j] += ton[i][j * k];	
		throw(j,maxx,1)
		{
			s[j] = 1; try(i,1,n) (s[j] *= (cnt[i][j] + 1) % mod) %= mod; s[j] --;
			if(!s[j]) continue;
			for(register int k=2;k * j <=maxx;++k) s[j] = (s[j] - s[k*j] + mod) % mod;
			(ans += s[j] * j % mod) %= mod;
		}
		cout<<ans<<endl;
		return 0;
	}
}
signed main() {return xin::main();}

c

这个虽然没有想出正解点分治，但是也是暴力分数中最大的想法了。

就是我们对于每次询问，遍历整张图，找到 \(x\) 到 \(y\) 经过的点的路径。

之后因为每两个点之间的边不止一条，而我们又要找到最大的价值，发现贪心不可，便开始 \(dp\)

我们考虑 \(f_{i,j}\) 为处理到 \(i\) 点，然后并且选择了这个点的颜色为 \(j\)

转移显然:

\[f_{i,j} = max_{k \ne }(f_{i-1,k})+1\\ f_{i,j} = max_{k = j}(f_{i-1,k}) \]

然后就是 \(\mathcal O(nq)\)，只能过前 \(5\) 点。。。

#include<bits/stdc++.h>
using std::cout; using std::endl;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
#define asm(i,x) for(register signed i=head[x];i;i=edge[i].next)
namespace xin_io
{
	#define debug cout<<"debug"<<endl
	#define sb(x) cout<<#x" = "<<x<<' '
	#define jb(x) cout<<#x" = "<<x<<endl
	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
	char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll; typedef unsigned long long ull;
	class xin_stream{public:template<typename type>inline xin_stream &operator >> (type &x)
	{
		register type s = 0; register int f = 1; register char ch = gc();
		while(!isdigit(ch)) {if(ch == '-') f = -1; ch = gc();}
		while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch  xor 48),ch = gc(); return x = s * f,*this;
	}}io;
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+7; const ll llinf = 1e18+7;
namespace xin
{
	class xin_edge{public:int next,ver,w;}edge[maxn];
	int head[maxn],ced = 0;
	inline void add(int x,int y,int z) {edge[++ced].ver = y;edge[ced].w = z; edge[ced].next = head[x]; head[x] = ced;}
	int n,m,qnum;
	bool vis[maxn];
	int pre[maxn];
	void dfs(int x,int goal)
	{
		vis[x] = 1;
		if(x == goal) return;
		asm(i,x)
		{
			register int y = edge[i].ver;
			if(!vis[y])
			{
				pre[y] = x;
				dfs(y,goal);
			}
		}
	}
	void outp(int x)
	{
		if(!x) return;
		cout<<x<<' ';
		outp(pre[x]);
	}
	std::vector<int>vec[501][501];
	int f[501][10001];
	int maxx = 0,ans = -inf;
	void dp(int x,int i)
	{
		if(!x)
		{
			return ;
		}
		for(auto j : vec[x][pre[x]])
		{
			try(k,1,maxx)
				if(k xor j)
					f[i][j] = std::max(f[i-1][k] + 1,f[i][j]),ans = std::max(ans,f[i][j]);
				else 
					f[i][j] = std::max(f[i-1][k],f[i][j]),ans = std::max(ans,f[i][j]);
		}
		dp(pre[x],i+1);
	}
	class xin_data
	{
		public:
			int x,y,z;
	}d[maxn];
	int lisan[maxn],cnt;
	bool sp1 = 1;
	int top[maxn],hson[maxn],dep[maxn],fa[maxn],siz[maxn];
	void dfs1(int x,int f)
	{
		siz[x] = 1; dep[x] = dep[f] + 1; fa[x] =f;
		asm(i,x)
		{
			register int y = edge[i].ver;
			if(y == f) continue;
			dfs1(y,x);
			siz[x] += siz[y];
			if(siz[y] > siz[hson[x]]) hson[x] = y;
		}
	}
	void dfs2(int x,int t)
	{
		top[x] = t; 
		if(hson[x]) dfs2(hson[x],t);
		asm(i,x)
		{
			register int y = edge[i].ver;
			if(y == hson[x] or y == fa[x]) continue;
			dfs2(y,y);
		}
	}
	inline int lca(int x,int y)
	{
		while(top[x] xor top[y])
		{
			if(dep[top[x]] < dep[top[y]]) std::swap(x,y);
			x = fa[top[x]];
		}
		if(dep[x] > dep[y]) return y; return x;
	}
	inline short main()
	{
		io >> n >> m;
		try(i,1,m)
		{
			io >> d[i].x >> d[i].y >> d[i].z;
			lisan[++cnt] = d[i].z;
		}
		io >> qnum; if(!qnum) {return 0;}
		std::sort(lisan+1,lisan+cnt+1);
		maxx = std::unique(lisan+1,lisan+cnt+1) - (lisan + 1);
		try(i,1,m)
		{
			d[i].z = std::lower_bound(lisan+1,lisan+maxx+1,d[i].z) - lisan;
			add(d[i].x,d[i].y,d[i].z); add(d[i].y,d[i].x,d[i].z);
			if(n <= 500 and vec[d[i].x][d[i].y].size()) sp1 = 0;
			if(n <= 500 )vec[d[i].x][d[i].y].push_back(d[i].z),vec[d[i].y][d[i].x].push_back(d[i].z);
		}
		try(que,1,qnum)
		{
			register int x,y; io >> x >> y;
			memset(vis,0,sizeof(bool) * (n + 1));
			memset(pre,0,sizeof(int ) * (n + 1));
			try(i,1,n) try(j,1,maxx) f[i][j] = 0;
			ans = 0;
			dfs(x,y);
//			outp(y);cout<<endl;
			dp(y,1);
			cout<<ans<<endl;
		}
		return 0;
	}
}
signed main() {return xin::main();}