• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

[考试总结]noip模拟50

开发技术 开发技术 4小时前 1次浏览

第零题

发现一个结论,就是说这个道路怎么走答案其实是一样的。

然后就能愉快暴力了。。。

话说为何班长每次暴力都能 (Ac)

但是我们要倍增!!!

然后就行了。。。



#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 go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
	#define sb(x) cout<<#x" = "<<x<<' '
	#define jb(x) cout<<#x" = "<<x<<endl
	#define debug cout<<"debug"<<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 &s)
	{
		register int f = 0;s = 0; register char ch = gc();
		while(!isdigit(ch)) {f |= ch == '-'; ch = gc();}
		while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch  xor 48),ch = gc(); return s = f ? -s : s,*this;
	}}io;
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+7; const ll llinf = 1e18+7;
#define int long long
namespace xin
{
	class xin_edge{public:int next,ver,w;}edge[maxn];
	int head[maxn],rp;
	auto add = [](int x,int y,int z) -> void {edge[++rp].ver = y; edge[rp].w = z; edge[rp].next = head[x]; head[x] = rp;};

	int siz[maxn],d[maxn],fa[maxn],top[maxn],hson[maxn],mi[23],he[maxn],c[maxn],sum[maxn],f[maxn][23],ton[maxn];
	int n,k,m,tot,logms;

	void dfs1(int x,int f)
	{
		d[x] = d[f] + 1; siz[x] = 1; fa[x] = f;
		go(i,x)
		{
			if(y == f) continue;
			c[y] = edge[i].w; 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);
		go(i,x)
		{
			if(y == hson[x] or y == fa[x]) continue;
			dfs2(y,y);
		}
	}
	
	void dfs(int x)
	{
		auto find = []() -> int 
		{
			register int lim = sum[tot] + k,l = 0,r = tot,ret = 0;
			while(l <= r)
			{
				register int mid = l + r >> 1;
				if(sum[mid] >= lim) ret = mid,l = mid + 1;
				else r = mid - 1;
			}
			return ton[ret];
		};
		ton[++tot] = x; sum[tot] = sum[tot - 1] - c[x];

		f[x][0] = find();// jb(f[x][0]); 
		try(i,1,logms) f[x][i] = f[f[x][i-1]][i-1];

		go(i,x)
		{
			if(y == fa[x]) continue;
			he[y] = he[x] + c[y];
			dfs(y);
		}

		tot --;
	}

	inline short main()
	{
		io >> n >> k; logms = log2(n) + 1ll;
//		jb(logms);

		try(i,1,n-1)
		{
			register int x,y,z; io >> x >> y >> z;
			add(x,y,z); add(y,x,z);
		}

		auto prework = [=]() -> void {mi[0] = 1; try(i,1,logms) mi[i] = mi[i-1] << 1;sum[0] = llinf;}; prework();
	
		dfs1(1,0); dfs2(1,1);
		dfs(1);
		
//		try(i,1,n) try(j,0,logms) sb(i),sb(j),jb(f[i][j]);

		auto query = [=](int s,int t)mutable -> int
		{
			auto lca = [s,t]()mutable -> int
			{
				while(top[s] xor top[t]) 
				{
					if(d[top[s]] < d[top[t]]) s ^= t ^= s ^= t;
					s = fa[top[s]];
				}
				return d[s] > d[t] ? t : s;
			};
			register int ans = 0,allca = lca();
			throw(i,logms,0) if(d[f[s][i]] >= d[allca]) s = f[s][i],ans += mi[i];
			throw(i,logms,0) if(d[f[t][i]] >= d[allca]) t = f[t][i],ans += mi[i];
			if(he[t] - he[allca] >= k - (he[s] - he[allca])) return ans + 1; return ans;
		};

		io >> m;
		try(i,1,m){register int s,t; io >> s >> t;printf("%lldn",query(s,t));}

		return 0;
	}
}
signed main() {return xin::main();}

第负一题

首先想到垃圾基础 (dp)

就是:

[f_{i,0} = max(f_{i-1,0},f_{i-1,1})\
f_{i,1} = max(f_{i-2,1},f_{i-1,0})
]

然后愉快 (mathcal O(n^2))

然后这就是暴力。。

但是为啥只给 (20pts)

靠。。。。

然后正解我们加一个分治。

从中间断开。

然后 (f_{i,1/0,1/0}) 表示第 (i) 个,然后 (mid) 能不能选,然后是选了没选。

转移也很简单。。

			l[i][1][1] = l[i+1][1][0] + a[i]; l[i][1][0] = max(l[i+1][1][1],l[i+1][1][0]);
			l[i][0][1] = l[i+1][0][0] + a[i]; l[i][0][0] = max(l[i+1][0][1],l[i+1][0][0]);
			l[i][1][1] = max(l[i][1][1],l[i][1][0]),l[i][0][1] = max(l[i][0][0],l[i][0][1]);
			r[i][1][1] = r[i-1][1][0] + a[i]; r[i][1][0] = max(r[i-1][1][1],r[i-1][1][0]);
			r[i][0][1] = r[i-1][0][0] + a[i]; r[i][0][0] = max(r[i-1][0][1],r[i-1][0][0]);
			r[i][1][1] = max(r[i][1][1],r[i][1][0]),r[i][0][1] = max(r[i][0][0],r[i][0][1]);

然后代码:



#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 go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
	#define sb(x) cout<<#x" = "<<x<<' '
	#define jb(x) cout<<#x" = "<<x<<endl
	#define debug cout<<"debug"<<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 &s)
	{
		register int f = 0;s = 0; register char ch = gc();
		while(!isdigit(ch)) {f |= ch == '-'; ch = gc();}
		while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch  xor 48),ch = gc(); return s = f ? -s : s,*this;
	}}io;
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+7; const ll llinf = 1e18+7;
#define int long long
namespace xin
{
	const int mod = 998244353;
	int a[maxn],l[maxn][2][2],r[maxn][2][2],tl[maxn],tr[maxn];
	int n,ans = 0;

	auto max = [](int x,int y) -> int {return x > y ? x : y;};

	void dfs(int ql,int qr)
	{
		if(qr - ql == 0) return (ans += a[qr]) %= mod,void();
		if(qr - ql == 1) return (ans += max(a[ql],a[qr]) + a[ql] + a[qr]) %= mod,void();
		register int mid = ql + qr >> 1;
		dfs(ql,mid); dfs(mid+1,qr);
		l[mid][1][1] = a[mid]; r[mid+1][1][1] = a[mid+1];
		l[mid][1][0] = l[mid][0][0] = r[mid+1][1][0] = r[mid+1][0][0] = 0;
		throw(i,mid-1,ql)
		{
			l[i][1][1] = l[i+1][1][0] + a[i]; l[i][1][0] = max(l[i+1][1][1],l[i+1][1][0]);
			l[i][0][1] = l[i+1][0][0] + a[i]; l[i][0][0] = max(l[i+1][0][1],l[i+1][0][0]);
		}
		throw(i,mid-1,ql)
			l[i][1][1] = max(l[i][1][1],l[i][1][0]),l[i][0][1] = max(l[i][0][0],l[i][0][1]);
		try(i,mid+2,qr)
		{
			r[i][1][1] = r[i-1][1][0] + a[i]; r[i][1][0] = max(r[i-1][1][1],r[i-1][1][0]);
			r[i][0][1] = r[i-1][0][0] + a[i]; r[i][0][0] = max(r[i-1][0][1],r[i-1][0][0]);
		}
		try(i,mid+2,qr)
			r[i][1][1] = max(r[i][1][1],r[i][1][0]),r[i][0][1] = max(r[i][0][0],r[i][0][1]);
		
		try(i,ql,mid) tl[i] = max(l[i][1][1] - l[i][0][1],0);
		try(i,mid+1,qr) tr[i] = max(r[i][1][1] - r[i][0][1],0);
		std::sort(tl+ql,tl+mid+1); std::sort(tr+mid+1,tr+qr+1);
		
		register int temp = 0;
		try(i,ql,mid) (temp += l[i][0][1]) %= mod; (temp *= (qr - mid)) %= mod; 
		(ans += temp) %= mod; temp = 0;
		try(i,mid+1,qr) (temp += r[i][0][1]) %= mod;
		(ans += temp * (mid - ql + 1) % mod) %= mod;
		
		register int zhi = mid;
		
		try(i,ql,mid)
		{
			while(zhi < qr and tr[zhi+1] <= tl[i]) zhi ++;
			(ans += (zhi - mid) * tl[i] % mod) %= mod;
		}
		
		zhi = ql-1;

		try(i,mid+1,qr)
		{
			while(zhi < mid and tl[zhi+1] < tr[i]) zhi ++;
			(ans += (zhi - ql + 1) * tr[i] % mod) %= mod;
		}

	}

	inline short main()
	{
		io >> n;
		try(i,1,n) io >> a[i];
		
		dfs(1,n);

		cout<<ans<<endl;


		return 0;
	}
}
signed main() {return xin::main();}

题目自己推。。。

我只会 (90pts) 算法

就是一个时间一个时间的看。

然后统计,



#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 go(i,x) for(register signed i=head[x],y=edge[i].ver;i;i=edge[i].next,y=edge[i].ver)
namespace xin_io
{
	#define sb(x) cout<<#x" = "<<x<<' '
	#define jb(x) cout<<#x" = "<<x<<endl
	#define debug cout<<"debug"<<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 &s)
	{
		register int f = 0;s = 0; register char ch = gc();
		while(!isdigit(ch)) {f |= ch == '-'; ch = gc();}
		while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch  xor 48),ch = gc(); return s = f ? -s : s,*this;
	}}io;
}
using namespace xin_io; static const int maxn = 1e7+10,inf = 1e9+7; const ll llinf = 1e18+7;
#define int long long
namespace xin
{
	const int mod = 998244353;
	typedef unsigned long long u64;
	  
	auto ksm = [](int x,int y,int ret = 1) -> int 
	{
		while(y)
		{
			if(y & 1) ret = ret * x  % mod;
			x = x * x % mod; y >>= 1;
		}
		return ret;
	};
	u64 xorshift128p(u64 &A, u64 &B) { 
		u64 T = A, S = B; 
		A = S; 
		T ^= T << 23; 
		T ^= T >> 17; 
		T ^= S ^ (S >> 26); 
		B = T; 
		return T + S; 
	} 
	   
	void gen(int n, int L, int X, int Y, u64 A, u64 B, int l[], int r[]) { 
		for (int i = 1; i <= n; i ++) { 
			l[i] = xorshift128p(A, B) % L + X; 
			r[i] = xorshift128p(A, B) % L + Y; 
			if (l[i] > r[i]) std::swap(l[i], r[i]); 
		} 
	}
	int l[maxn],r[maxn],nl[maxn],nr[maxn];
	int n,L,X,Y;
	u64 A,B; 
	int ans = 0;

	bool vis[maxn];	

	int f[maxn];
	int q1[maxn],q2[maxn],zhi1 = 0,zhi2 = 0;
	int tim = 0,wan = 0;

	inline short main()
	{
		io >> n >> L >> X >> Y >> A >> B;
		gen(n,L,X,Y,A,B,l,r);
		
		try(i,1,n) q1[++zhi1] = i;

//		try(i,1,n) sb(l[i]),jb(r[i]);

		while(1)
		{
			tim++;
			while(zhi1)
			{
				register int x = q1[zhi1 --];
				q2[++zhi2] = x;
				auto max = [](int x,int y) -> int {return x > y ? x : y;};
				auto min = [](int x,int y) -> int {return x < y ? x : y;};
				register int newl = max(l[x],max(l[x-1],l[x+1])),newr = min(r[x],min(r[x+1],r[x-1]));
				if(newl == l[x]) newl ++;
				if(newr == r[x]) newr --;
//				sb(newl); jb(newr); 
				if(newr < newl or !newr or !newl)
				{
					vis[x] = 1;
					wan ++;
					f[x] = tim;
					nl[x] = nr[x] = 0;
				}
				else nl[x] = newl,nr[x] = newr;
			}
			while(zhi2)
			{
				register int x = q2[zhi2 --];
				l[x] = nl[x]; r[x] = nr[x];
				if(!vis[x]) q1[++zhi1] = x;
			}
			if(n == wan) break;
		}
		
//		try(i,1,n) sb(i),jb(f[i]);

		try(i,1,n) (ans += ksm(3,i-1) * f[i] % mod) %= mod;
		cout<<ans<<endl;

		return 0;
	}
}
signed main() {return xin::main();}


程序员灯塔
转载请注明原文链接:[考试总结]noip模拟50
喜欢 (0)