时间戳

首页 > 技术文章 > [考试总结]noip模拟5

[考试总结]noip模拟5

NP2Z 2021-06-07 21:18 原文

T1：

看到这个题目，又短，又简单，一看就是 暴力，然后开始码，暴力很好打，会语言就行，唯一一点遗憾就是没有在 2min 之内打出来这个题目的暴力

但是在打完 laji nb 的T1暴力之后，心中首先是一阵小窃喜，之后突然想到 这个题目不会有人打不出来的，所以40pts一点作用没有，之后开始想 伪正解

\(n,m<=10^5\)

如果使用 \(sort\) 的话，那么一定就是严格的 \(\mathcal O(nlog_2n)\)，那么一定只会拿到 \(40pts\)，但是，如果使用桶排序，那么最优的复杂度就可以达到 \(\mathcal O(26nk)\)

但是，事实证明，我错了

\(k\)最多可以退化成 \(n\)，然而这些数据对于桶排，全部会变成\(n\)

我枯了

但是，桶排并不是一无是处，正解便就是使用线段树优化桶排，对于每一个线段树上的节点，我们维护：

s[26] l r debt

然后复杂度就是 \(\mathcal O(26^2 n)\)

\(\huge{\text{完全可过}}\)

\(code\):

#include<cmath>
#include<queue>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
//#define int long long
#define m(c,num) memset(c,num,sizeof c)
#define inf 0x7f7f7f7f
#define debug cout<<"debug"<<endl
#define freopen eat = freopen
#define scanf a14 = scanf
#define eps (1e-8)
namespace xin_io
{
	#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; FILE *eat; int a14;
	inline void openfile() {freopen("t.txt","r",stdin);}
	inline void outfile()  {freopen("com.txt","w",stdout);}
	inline int get()
	{
		int 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;
	}
}
const int maxn = 1e6+10;
using namespace xin_io;
namespace xin
{
	class xin_tree{public:int l,r;int debt,s[27];}t[maxn]; //there I use a class to store my segment_tree
	int n;
	char s[maxn];
	#define ls(fa) (fa << 1)
	#define rs(fa) (fa << 1 | 1)
	inline void up(int fa)
	{for(register int i=0;i<26;++i) t[fa].s[i] = t[ls(fa)].s[i] + t[rs(fa)].s[i];} //this is pushup
	void build(int fa,int l,int r) //first build the segment
	{
		t[fa].l = l; t[fa].r = r; t[fa].debt = -1;
		if(l == r) {t[fa].s[s[l] - 'a']++;return ;}
		register int mid = l + r >> 1;
		build(ls(fa),l,mid); build(rs(fa),mid+1,r);
		up(fa);
	}
	int sum[27];
	inline void down(int fa) //lazytag is here
	{
		if(t[fa].debt == -1) return;
		for(register int i=0;i<26;++i) t[ls(fa)].s[i] = t[rs(fa)].s[i] = 0;
		t[ls(fa)].debt = t[rs(fa)].debt = t[fa].debt;
		t[ls(fa)].s[t[fa].debt] = t[ls(fa)].r - t[ls(fa)].l + 1;
		t[rs(fa)].s[t[fa].debt] = t[rs(fa)].r - t[rs(fa)].l + 1;
		t[fa].debt = -1;
	}
	void modify(int fa,int l,int r,int val) //to modify the data in the segment_tree
	{
		if(r < t[fa].l or l > t[fa].r )return; //use another method to stop the illegal branch
		if(t[fa].l >= l and t[fa].r <= r)
		{
			for(register int i=0;i<=26;++i) t[fa].s[i] = 0;
			t[fa].s[val] = t[fa].r - t[fa].l + 1;
			t[fa].debt = val;return;
		}
		down(fa);
		modify(ls(fa),l,r,val); modify(rs(fa),l,r,val);
		up(fa);
	}
	void query(int fa,int l,int r,int *ans)
	{
		if(r < t[fa].l or l > t[fa].r) return ;
		if(t[fa].l >= l and t[fa].r <= r) 
		{
			for(register int i=0;i<=25;++i)
				ans[i] += t[fa].s[i];
			return ;
		}
		down(fa);
		query(ls(fa),l,r,ans); query(rs(fa),l,r,ans);
	}
	inline void do_sort(int l,int r,int op)
	{
		memset(sum,0,sizeof(sum));
		query(1,l,r,sum);
		if(op)
		{
			for(register int i=0;i<=25;++i)
			{
				if(!sum[i]) continue;
				modify(1,l,l+sum[i]-1,i);
				l += sum[i];
			}
		}
		else
		{
			for(register int i=25;i>=0;--i)
			{
				if(!sum[i]) continue;
				modify(1,l,l+sum[i]-1,i);
				l += sum[i];
			}
		}
	}
	void output(int fa)
	{
		if(t[fa].l == t[fa].r)
		{
			for(register int i=0;i<=25;++i)
				if(t[fa].s[i])	
					putchar(i + 'a');
			return ;
		}
		down(fa);
		output(ls(fa)); output(rs(fa));
	}
	inline short main()
	{
	#ifndef ONLINE_JUDGE
		openfile();
	#endif
		int m;
		scanf("%d%d%s",&n,&m,s+1);
		build(1,1,n);
		for(register int i=1;i<=m;++i)
		{
			register int l,r,op;
			scanf("%d%d%d",&l,&r,&op);
			do_sort(l,r,op);
		}
		output(1);
		return 0;
	}
}
signed main() {return xin::main();}

T2:

一眼暴力，可以 \(20pts\)，但是我以为会全部暴掉。。。。

\(\huge{\text{我大意了}}\)

\(\huge{\text{没有闪}}\)

所以正解是 \(\mathcal O(n)\) \(dp\)，

\[f_{i+1,j+1}+=f_{i,j}* (r_{i+1} - j) \]

\[f_{i,j} = f_{i,j} * A(l_i-l_{i-1},i-j-l_{i-1}) \]

这方程我暂时是想不出来

T3:

首先 (⌊2x2n⌋+2x)mod2n是什么呢？我们先看，⌊2x2n⌋=⌊x2n−1⌋，当 x≥2n−1的二进制取后 n 位，第 1 位一定为 1.（比如 n=2，则 3 的二进制是 11，2 的二进制是 10）。否则第 1 位为 0. 然后 2x显然是把 x 左移 1 位，再模一下 2n

就是取后面 n 位。所以整个流程出来就是把 x 二进制下的第一位移到最后一位。

这说明了什么？原来 x 的取值范围是 [0,2n)
，在被你的对手搞事之后的数取值范围还是 [0,2n)

。

现在你的对手很心急，他决定在你异或 i 个数后再对你的 x 搞事，可是你还没开始异或他就要搞事了。怎么办？前 i 个数也只能做同样的操作（即将二进制下第一位移到最后一位），这样你在异或前 i 个数的时候二进制数位和搞事后的 x 是一一对应的。

我们令 a[i] 为异或的第 i 个数，b[i] 为 a[i] 被搞事的结果。那么我们求出 suf[i] 为 a 的后缀异或和，pre[i] 为 b 的前缀异或和。因为异或具有结合率和交换率，所以我们可以看作是你的 x 被搞事后异或上某个 (pre[i]^suf[i+1])，这样的 (pre[i]^suf[i+1]) 一共有 m+1 个。

我们以这 m+1 个数的二进制建立一棵 trie 树。然后 dfs 这棵 trie 树，如果某个节点有两个子节点：0 和 1，那么你开始选的（被搞事了的）x 这一位无论是 0 还是 1，你的对手都有选择的方法使这一位异或后变成 0. 但是如果这个节点只有一个子节点，那么聪明的你就可以做出选择，使得异或后这一位还是 1，统计答案就变得 easy 啦！

当然了，trie 树应该是每一个二进制数从前往后每一位去建立。因为你的对手想要让你选的数某一位异或后为 0，一定先考虑前面的几位，再考虑后面的几位。（因为 ∑ni=02i=2n+1−1
（应该没写错吧？）

大佬讲解，现在还没有调出来，所以先不说了

T4:

考场上唯一一道过掉的题

一眼 \(tarjan\)，再一眼 \(Atm\)

然后就可以 (\(tarjan\)+XIN算法) 建 议 学 习

然后就是很套路很套路很套路的 \(tarjan\) 缩点。

只不过我的常数炸天

\(long\;long\) + \(STL\)

\(\huge{\text{险些没过}}\)

\(code\)

#include<map>
#include<cmath>
#include<queue>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
#define int long long
#define m(c,num) memset(c,num,sizeof c)
#define inf 0x7f7f7f7f
#define debug cout<<"debug"<<endl
#define freopen eat = freopen
#define scanf a14 = scanf
#define eps (1e-8)
namespace xin_io
{
	#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; FILE *eat; int a14;
	inline void openfile() {freopen("t.txt","r",stdin);}
	inline void outfile()  {freopen("o.txt","w",stdout);}
	inline int get()
	{
		int 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;
	}
}
const int maxn = 1e6+10;
using namespace xin_io;
namespace xin
{
	class xin_edge{public:int next,ver;} edge[maxn],edge_new[maxn];
	int zhi,zhi_new,head[maxn],head_new[maxn];
	void add(int u,int v) {if(u==v) return;edge[++zhi].next=head[u]; head[u]=zhi; edge[zhi].ver=v;}
	void add_new(int u,int v) {edge_new[++zhi_new].next=head_new[u]; head_new[u]=zhi_new; edge_new[zhi_new].ver=v;}
	int num[maxn],scc[maxn],f[maxn];
	stack<int>st;
	bool vis[maxn];
	int n,r,c;
	int scc_num,ans;
	int x[maxn],y[maxn],t[maxn];
	vector<int>h[maxn],s[maxn];
	map<pair<int,int>,int>hash;
	void build()
	{
		for(register int i=1;i<=r;++i) 
	    {    
	        register int u = 0;
	        for(register int j = 0;j<h[i].size();++j) 
	        	if(t[h[i][j]] == 1) {u = h[i][j]; break;}
//	        cout<<" i ="<<i<<endl;
	        for(register int j=0;j < h[i].size();++j) 
	        {add(u,h[i][j]); if(t[h[i][j]] == 1) add(h[i][j],u);}
	    }
		for(register int i=1;i<=c;++i)
	    {
	        register int u=0;
	        for(register int j=0;j<s[i].size();++j) 
	        if(t[s[i][j]] == 2) {u = s[i][j]; break;}
	        for(register int j=0;j<s[i].size();++j) 
	        {
	        	add(u,s[i][j]); 
	        	if(t[s[i][j]] == 2) add(s[i][j],u);
	        }
	    }
        int dx[8]={-1,-1,0,0,1,1,1,-1},dy[8]={1,-1,1,-1,0,1,-1,0};
		for(register int i=1;i<=n;++i)
	    if(t[i]==3)
		    for(register int j=0;j<8;++j)
		    {
		        register int nowx = x[i]+dx[j],nowy = y[i]+dy[j];
		        if(hash[make_pair(nowx,nowy)]) add(i,hash[make_pair(nowx,nowy)]);
		    }
	}
	int dfn[maxn],low[maxn],tim = 0;
	void tarjan(int x) 
	{ 
		dfn[x] = low[x] = ++tim; vis[x]=1; st.push(x); 
		for(register int i=head[x];i;i=edge[i].next) 
	    { 
	        if(!dfn[edge[i].ver]) 
            { 
                tarjan(edge[i].ver); 
                if(low[edge[i].ver]<low[x]) low[x] = low[edge[i].ver]; 
            } 
	        else 
	            if(vis[edge[i].ver] and dfn[edge[i].ver]<low[x]) 
	                low[x]=dfn[edge[i].ver]; 
	    }
		if(dfn[x]==low[x]) 
	    { 
	        int temp=0; scc_num++; 
	        while (x!=temp) 
	            temp = st.top(),st.pop(),num[scc_num]++,vis[temp]=0,scc[temp]=scc_num;  
	    } 
	} 
	inline void build_new_map()
	{
		for(register int i=1; i<=n;++i) 
		    for(register int j=head[i]; j; j=edge[j].next) 
		        if(scc[i]!=scc[edge[j].ver]) 
		            add_new(scc[i],scc[edge[j].ver]);//,cout<<scc[i]<<' '<<scc[edge[j].ver]<<endl; 
	}
	void dfs(int u)
	{
		vis[u]=1;
		for(register int i=head_new[u];i;i=edge_new[i].next)
	    {
	        if(!vis[edge_new[i].ver]) dfs(edge_new[i].ver);
	        f[u] = max(f[u],f[edge_new[i].ver]);
	    }
		f[u] += num[u];
		ans = max(ans,f[u]);
	}
	inline short main()
	{
	#ifndef ONLINE_JUDGE
		openfile();
	#endif
		n = get(); r = get(); c = get();
		for(register int i=1;i<=n;++i)
	    {
	        x[i] = get(),y[i] = get(),t[i] = get();
	        hash[make_pair(x[i],y[i])] = i; 
	        h[x[i]].push_back(i); s[y[i]].push_back(i);
//	        cout<<x[i]<<' '<<y[i]<<' '<<t[i]<<endl;
	    }
		build();
		for(register int i=1;i<=n;++i) 
			if(!dfn[i]) 
				tarjan(i);
		build_new_map();
//		cout<<scc_num<<endl;
		for(register int i=1;i<=scc_num;++i) 
			if(!vis[i]) dfs(i);//,cout<<"f[scc_num] = "<<f[scc_num]<<endl;
		printf("%lld\n",ans); 
		return 0;
	}
}
signed main() {return xin::main();}

推荐阅读