正文

[考试总结]noip模拟14

IP云
IP云V管理员/1 阅读
12/02
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

咕掉了好长时间，现在终于回来了。。

这次考试炸裂得很完蛋，直接分数上天。

\(T1\) 本来想打一个记忆化搜索，然而老是通过不了样例，然后就挂了，只剩下了垃圾的 \(30pts\) 部分分数。

然而到现在记忆化还是调不出来。。。。

好废啊。

然后 \(T2,T3\) 也只能是暴力收场，垃得一批。

T1:

这个题目就是一个显然的 \(dp\) （只是 \(dp\) 显然，而不是 \(dp\) 方程显然）。。。

然后我们开始疯狂地推 \(dp\) 式子。。。

然后推不出来。。。

你推不出来不会加元吗？？？？？？？？？

这就是推 \(dp\) 方程的真谛

唉

但是我想不出来还有什么状态怎么办呢

那就考虑那些不连续的东西。

虽然他们无法直接转移，但是我们可以 离散化

我们将值离散化，然后我们就可以将 \(dp\) 的第二维设置作为值。

我们再来分析问题的实质：

\(\huge{\text{实际上就是要求}min(A_{1\rightarrow i}>B_{i+1})}\)

然后就有了嘛。

然后线段树优化

我从一开始就垃了，巨佬们都想出了线段树优化，而我只能打打暴力维持一下生活这样子 

#include<bits/stdc++.h>

using std::cout; using std::endl;

#define debug cout<<"debug"<<endl

namespace xin_io

{

	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++

	#define scanf eat1 = scanf

	#define freopen eat2 = freopen

	int eat1; FILE *eat2; char buf[1<<20],*p1 = buf,*p2 = buf;

	inline void openfile() {freopen("t.txt","r",stdin);} inline void outfile() {freopen("o.txt","w",stdout);}

	template<class type>inline type get()

	{

		type s = 0,f = 1; register char ch = gc();

		while(!isdigit(ch)) {if(ch == '-') f = -1; ch = gc();}

		while(isdigit(ch))  {s = s * 10 + ch - '0'; ch = gc();}

		return s * f;

	}

}

using namespace xin_io; static const int maxn = 1e6+10,inf = 0x7f7f7f,mod = 998244353;

#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)

typedef long long ll;

namespace xin

{

	int da[maxn],db[maxn],pre_a[maxn],pre_b[maxn];

	int n,a[maxn],b[maxn];

	int ans = -inf;

	int lisan[maxn],zhi = 0;

	int tot;

	class xin_segment

	{

		private:

			#define ls(fa) (fa << 1)

			#define rs(fa) (fa << 1 | 1)

			#define up(fa) t[fa].s = std::max(t[ls(fa)].s,t[rs(fa)].s)

			inline void down(int fa,int l,int r)

			{

				if(!t[fa].debt) return ;

				t[ls(fa)].debt += t[fa].debt; t[rs(fa)].debt += t[fa].debt;

				t[ls(fa)].s += t[fa].debt; t[rs(fa)].s += t[fa].debt;

				t[fa].debt = 0;

			}

		public:

			class xin_tree{public:int s,debt;}t[maxn];

			void insert(int fa,int l,int r,int pos,int val)

			{

				if(pos > r or pos < l ) return ;

				if(l == r){t[fa].s = std::max(t[fa].s,val); return ;}

				register int mid = l + r >> 1;

				down(fa,l,r);

				insert(ls(fa),l,mid,pos,val); insert(rs(fa),mid+1,r,pos,val);

				up(fa);

			}

			void update(int fa,int l,int r,int ql,int qr,int val)

			{

				if(qr < l or ql > r) return ;

				if(qr >= r and ql <= l)

				{

					t[fa].s += val; t[fa].debt += val;

					return ;

				}

				register int mid = l + r >> 1;

				down(fa,l,r);

				update(ls(fa),l,mid,ql,qr,val); update(rs(fa),mid+1,r,ql,qr,val);

				up(fa);

			}

			int query(int fa,int l,int r,int ql,int qr)

			{

				if(qr < l or ql > r) return -inf;

				if(qr >= r and ql <= l) return t[fa].s;

				register int mid = l + r >> 1,ret = 0;

				down(fa,l,r);

				ret = std::max(ret,query(ls(fa),l,mid,ql,qr));

				ret = std::max(ret,query(rs(fa),mid+1,r,ql,qr));

				return ret;

			}

	}t;

	inline short main()

	{

	#ifndef ONLINE_JUDGE

		openfile();

	#endif

		n = get<signed>();

		try(i,1,n) pre_a[i] = da[i] = get<signed>(),pre_b[i] = db[i] = get<signed>(),lisan[++zhi] = da[i],lisan[++zhi] = db[i];

		std::sort(lisan+1,lisan+zhi+1);

		int len = std::unique(lisan+1,lisan+zhi+1) - lisan - 1;

		try(i,1,n)

		{

			a[i] = std::lower_bound(lisan+1,lisan+len+1,pre_a[i]) - lisan;

			b[i] = std::lower_bound(lisan+1,lisan+len+1,pre_b[i]) - lisan;

//			cout<<a[i]<<' '<<b[i]<<endl;

		}

		try(i,1,n)

		{

			if(a[i] <= b[i])

			{

				register int temp = t.query(1,1,len,b[i]+1,len) + 1;

				ans = std::max(ans,temp);

				t.insert(1,1,len,a[i],temp);

			}

			else

			{

				register int temp = t.query(1,1,len,a[i]+1,len) + 1;

				ans = std::max(ans,temp);

				int zhuan = temp;

				temp = t.query(1,1,len,b[i]+1,a[i]) + 1;

				ans = std::max(ans,temp);

				t.update(1,1,len,b[i]+1,a[i],1);

				t.insert(1,1,len,a[i],zhuan);

			}

		}

		cout<<ans<<endl;

		return 0;

	}

}

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

T2:

还没改出来，现在只能拿个 \(40pts\) 暴力分。。。 

#include<bits/stdc++.h>

using std::cout; using std::endl;

#define debug cout<<"debug"<<endl

namespace xin_io

{

	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++

	#define scanf eat1 = scanf

	#define freopen eat2 = freopen

	int eat1; FILE *eat2; char buf[1<<20],*p1 = buf,*p2 = buf;

	inline void openfile() {freopen("t.txt","r",stdin);} inline void outfile() {freopen("o.txt","w",stdout);}

	template<class type>inline type get()

	{

		type s = 0,f = 1; register char ch = gc();

		while(!isdigit(ch)) {if(ch == '-') f = -1; ch = gc();}

		while(isdigit(ch))  {s = s * 10 + ch - '0'; ch = gc();}

		return s * f;

	}

}

using namespace xin_io; static const int maxn = 1e6+10,inf = 0x7f7f7f7f,mod = 998244353;

#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)

typedef long long ll;

int n,m;

class xin_edge{public:int ver,next;}edge[maxn];

int head[maxn],zhi = 0;

inline void add(int x,int y) {edge[++zhi].ver = y; edge[zhi].next = head[x]; head[x] = zhi;}

int c[maxn];

int d[maxn];

namespace subtask1

{

	bool vis[maxn],col[maxn];

	void dfs1(int x,int f)

	{

		d[x] = d[f] + 1;

		for(register int i=head[x];i;i=edge[i].next)

		{

			register int y = edge[i].ver;

			dfs1(y,x);

		}

	}

	int q[maxn],zhi = 0;

	inline int query(int pos,int len)

	{

		int ans = 0;

		if(!len) return 1;

		memset(vis,0,sizeof(bool) * (n + 1)); memset(col,0,sizeof(bool) * (n + 1));

		q[++zhi] = pos; vis[pos] = col[c[pos]] = 1; ans = 1;

		while(zhi)

		{

			register int x = q[zhi--];

			for(register int i=head[x];i;i=edge[i].next)

			{

				register int y = edge[i].ver;

				if(d[y] - d[pos] > len) continue;

				if(!vis[y])

				{

					vis[y] = 1;

					if(!col[c[y]]) col[c[y]] = 1,ans++;

					q[++zhi] = y;

				}

			}

		}

		return ans;

	}

	inline short main()

	{

		try(i,1,n) c[i] = get<signed>();

		try(i,2,n)

		{

			register int x = get<signed>();

			add(x,i);

		}

		dfs1(1,0);

		try(que,1,m)

		{

			register int x = get<signed>(),len = get<signed>();

			printf("%d\n",query(x,len));

		}

		return 0;

	}

}

signed main()

{

#ifndef ONLINE_JUDGE

	openfile();

#endif

	n = get<signed>(); m = get<signed>();

	subtask1::main();

	return 0;

}

垃圾的我在考场上莫队还打垃了。

T3:

暴力极度好想，就是暴力搜索，然后就愉快有 \(50pts\) 



#include<bits/stdc++.h>

using std::cout; using std::endl;

#define debug cout<<"debug"<<endl

namespace xin_io

{

	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++

	#define scanf eat1 = scanf

	#define freopen eat2 = freopen

	int eat1; FILE *eat2; char buf[1<<20],*p1 = buf,*p2 = buf;

	inline void openfile() {freopen("t.txt","r",stdin);} inline void outfile() {freopen("o.txt","w",stdout);}

	template<class type>inline type get()

	{

		type s = 0,f = 1; register char ch = gc();

		while(!isdigit(ch)) {if(ch == '-') f = -1; ch = gc();}

		while(isdigit(ch))  {s = s * 10 + ch - '0'; ch = gc();}

		return s * f;

	}

}

using namespace xin_io; static const int maxn = 1e6+10,inf = 0x7f7f7f7f,mod = 998244353;

#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)

typedef long long ll;

namespace xin

{

	std::string s;

	int len,l;

	bool ok = 0;

	std::vector<char> a; int zhi = 0,ans = 0;

	std::map<std::vector<char>,int>vis;

	void dfs(int ms,int pos)

	{

		if(a.size() == ms)

		{

			if(!vis[a]) vis[a] = 1,ans++;

			return ;

		}

		for(register int i=pos+1;i<l;++i)

		{

			a.push_back(s[i]);

			dfs(ms,i);

			a.pop_back();

		}

	}

	inline short main()

	{

	#ifndef ONLINE_JUDGE

		openfile();

	#endif

		std::cin>>s>>len;

		l = s.size();

		for(register int i=1;i<l;++i)

			if(s[i] != s[i-1]) ok = 1;

		if(!ok){cout<<1<<endl;return 0;}

		dfs(len,-1);

		cout<<ans<<endl;

		return 0;

	}

}

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

老 \(STL\) 人了

然后考虑正解。。

这就是一道luogu上绿色的模板题嘛 ---赵sir

我又垃了。

好吧，方程就是：

\[f_{i,j} = f_{i-1,j} + f_{i,j-1} - f{p-1,j-1}
\]

表示处理前 \(i\) 个位置，然后长度为 \(j\),\(p\) 就是这个字母上一个出现的位置。

然后就有了： 

#include<bits/stdc++.h>

using std::cout; using std::endl;

#define debug cout<<"debug"<<endl

#define int long long

namespace xin_io

{

	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++

	#define scanf eat1 = scanf

	#define freopen eat2 = freopen

	int eat1; FILE *eat2; char buf[1<<20],*p1 = buf,*p2 = buf;

	inline void openfile() {freopen("t.txt","r",stdin);} inline void outfile() {freopen("o.txt","w",stdout);}

	template<class type>inline type get()

	{

		type s = 0,f = 1; register char ch = gc();

		while(!isdigit(ch)) {if(ch == '-') f = -1; ch = gc();}

		while(isdigit(ch))  {s = s * 10 + ch - '0'; ch = gc();}

		return s * f;

	}

}

using namespace xin_io; static const int maxn = 3e3+10,inf = 0x7f7f7f7f,mod = 998244353;

#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)

typedef long long ll;

namespace xin

{

	int f[maxn][maxn];

	char s[maxn];

	int l,len;

	int p[maxn];

	int dfs(int i,int j)

	{

		if(i < j) return 0;

		if(f[i][j]) return f[i][j];

		if(!i or !j) return 1;

		if(p[i]) f[i][j] = (dfs(i-1,j) + dfs(i-1,j-1) - dfs(p[i]-1,j-1) + mod) % mod;

		else f[i][j] = (dfs(i-1,j) + dfs(i-1,j-1)) % mod;

		return f[i][j] % mod;

	}

	inline void do_prework()

	{

		try(i,1,l)

			try(j,i+1,l)

				if(s[j] == s[i])

					{p[j] = i;break;}

	}

	inline short main()

	{

	#ifndef ONLINE_JUDGE

		openfile();

	#endif

		scanf("%s%lld",s+1,&len); l = strlen(s+1);

		try(i,0,len) f[i][i] = 1;

		do_prework();

		f[l][len] = dfs(l,len) % mod;

		cout<<f[l][len] % mod<<endl;

		return 0;

	}

}

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

相关阅读

目录[+]