eJOI2017~2019

ISIJ作业,所以来水了(

说句闲话:tzc来水什么水

UPD 2020.6.8:cnmd P6274是什么屑题啊/fn,都0202年了咋还有题考爆搜。。最后做吧,一晚上被这题毒害得什么也没干

UPD 2020.7.2:时隔30+天,终于除了一个毒瘤eJOI2019E和计几eJOI2017C其他都做完了/lh。接下来补题解。

eJOI2017

A - Magic

洛谷题目页面传送门

给定字符串\(a,|a|=n\),字符集为\(\Sigma\)。一个子串有魔法当且仅当它内部包含所有\(\Sigma\)种字符,且所有种类的字符数量相等。求有魔法的非空子串数量。

\(n\in\left[2,10^5\right],|\Sigma|\in[1,52]\)。

首先预处理出对于每种字符\(j\)的前缀计数\(Sum_{i,j}\),\(\mathrm O(n|\Sigma|)\)。

探索充要条件:一个子串\(a_{l\sim r}\)有魔法显然当且仅当\(\forall i\in\Sigma,Sum_{r,i}-Sum_{l-1,i}=\dfrac{r-l+1}{|\Sigma|}\Leftrightarrow |\Sigma|Sum_{r,i}-r=|\Sigma|Sum_{l-1,i}-(l-1)\)。设\(b_{i,j}=|\Sigma|Sum_{i,j}-i\),把\(b_i\)看成一个\(|\Sigma|\)元组,则上面那个充要条件即\(b_{l-1}=b_r\)。只要从左往右扫一遍,扫到\(i\)时,将多重集中\(b_i\)的数量贡献进答案,再将\(b_i\)扔进多重集即可。multisetcount()函数复杂度是线性的,可以用map实现多重集,\(\mathrm O(n|\Sigma|)+\mathrm O(n|\Sigma|\log n)=\mathrm O(n|\Sigma|\log n)\)。当然,这个\(b_i\)可以哈希,然后用哈希表实现多重集,这样扫描部分的时间复杂度为\(\mathrm O(n)\);前缀计数预处理部分也可以改为一边扫描一边线段树维护,\(\mathrm O(n\log k)\)。不过既然蒟蒻没有被卡常,就不写那么复杂了吧~

最后,蒟蒻忘记取模了,模数又抄错了\(2\)次,交了好几发才过……已加入sb错误列表(第\(4\)条)(

代码:

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int mod=1000000007;
const int N=100000,LET=52,ASCII=150;
int n;
char a[N+5];
vector<char> sigma;//字符集 
int pos[ASCII];//字符对应在sigma里的下标 
int Sum[N+1][LET];//前缀计数 
map<vector<int>,int> mp;//多重集 
int main(){
//	freopen("C:\\Users\\chenx\\Downloads\\P6273_12.in","r",stdin);
	cin>>n>>a+1;
	for(int i=1;i<=n;i++)sigma.pb(a[i]); 
	sort(sigma.begin(),sigma.end());
	sigma.resize(unique(sigma.begin(),sigma.end())-sigma.begin());//预处理sigma 
	for(int i=0;i<sigma.size();i++)pos[sigma[i]]=i;//预处理pos 
	int ans=0;
	mp[vector<int>(sigma.size(),0)]=1;//b[0] 
	for(int i=1;i<=n;i++){//扫描 
		for(int j=0;j<sigma.size();j++)Sum[i][j]=Sum[i-1][j];//计算前缀计数 
		Sum[i][pos[a[i]]]++;
		vector<int> v;//b[i]
		for(int j=0;j<sigma.size();j++)v.pb(sigma.size()*Sum[i][j]-i);
		(ans+=mp[v]++)%=mod;//贡献答案 
	}
	cout<<ans;
	return 0;
}

eJOI2018

A - Hills

洛谷题目页面传送门

题意见洛谷。

比较简单的DP。看到数据范围,基本可以确定时间复杂度\(\mathrm O\!\left(n^2\right)\)。于是\(2\)维确定了:考虑到的位置(\(\in[0,n]\))、建房子的山数(\(\in\left[0,\left\lceil\dfrac n2\right\rceil\right]\))。由于距离为\(2\)的\(2\)个建房子的山共享一个相邻山,情况需要特判,所以记录当前考虑的山们中倒数\(2\)个的建房子情况,即状态为\(dp_{i,j,k,o}\),其中\((k,o)\in\{(0,0),(0,1),(1,0)\}\)(\((1,1)\)不行,因为相邻\(2\)座山不可能都建房子)。边界\(dp_{0,j,k,o}=\begin{cases}0&j=k=o=0\\+\infty&\text{otherwise}\end{cases}\),目标\(\forall j\in\left[1,\left\lceil\dfrac n2\right\rceil\right],\min(dp_{n,j,0,0},dp_{n,j,0,1},dp_{n,j,1,0})\)。状态转移方程有点长不想列了/doge,注意一下\(k=0,o=1\)时要提前算第\(i+1\)座山要挖的时间,如果倒数第\(3\)座山建房子的话要撤销当时提前算的倒数第\(2\)座山要挖的时间,改成这\(2\)座建房子的山左右夹击时倒数第\(2\)座山要挖的时间。

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=5000;
int n;
int a[N+2];
int dp[N+1][N/2+1][2][2]; 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	memset(dp,0x3f,sizeof(dp));
	dp[0][0][0][0]=0;//边界 
	for(int i=1;i<=n;i++)for(int j=0;j<=n+1>>1;j++){//转移 
		dp[i][j][0][0]=min(dp[i-1][j][0][0],dp[i-1][j][1][0]);
		if(j){
			dp[i][j][0][1]=dp[i-1][j-1][0][0]+max(0,a[i-1]-(a[i]-1))+max(0,a[i+1]-(a[i]-1));
//			cout<<dp[i-1][j-1][0][0]<<" "<<max(0,a[i-1]-(a[i]-1))<<" "<<max(0,a[i+1]-(a[i]-1))<<" "<<dp[i][j][0][1]<<"\n";
			if(i>2)dp[i][j][0][1]=min(dp[i][j][0][1],dp[i-1][j-1][1][0]+max(0,a[i-1]-(min(a[i],a[i-2])-1))-max(0,a[i-1]-(a[i-2]-1))+max(0,a[i+1]-(a[i]-1)));
//			cout<<dp[i][j][0][1]<<"\n";
		}
		dp[i][j][1][0]=dp[i-1][j][0][1];
//		printf("dp[%d][%d]=%d %d %d\n",i,j,dp[i][j][0][0],dp[i][j][0][1],dp[i][j][1][0]);
	}
	for(int i=1;i<=n+1>>1;i++)cout<<min(min(dp[n][i][0][0],dp[n][i][0][1]),dp[n][i][1][0])<<" ";//目标 
	return 0;
}

D - Chemical table

洛谷题目页面传送门

题意见洛谷。

一眼就是个图论题。(咋是个紫题嘞)

考虑所有已有的元素张成的元素空间长啥样。显然,对于任意两行\(a,b\),若存在\(c\)使得位置\((a,c),(b,c)\)都有元素的话,那么\(a,b\)两行生死与共,即张成空间中\(a,b\)两行经过上下平移可以重合。(自证不难)

考虑基于行建图,将所有生死与共对连接起来,可以得到一些CC(连边操作可以对于每一列\(c\),将所有该行\(c\)列有元素的行们连接起来,从左到右线性连接即可保证连通性,不必连成完全图)。我们最后的目标是填一些元素使得张成空间为元素全集,此时显然等价于所有行生死与共,并且有元素的列集合为列全集。分别解决即可。

“所有行生死与共”:建图,DFS,答案为CC数量\(-1\);“有元素的列集合为列全集”:答案为\(m\)减去有元素的列集合的大小。最终答案为两个答案加起来。

代码:

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=200000,M=200000;
int n,m,s;
vector<int> bel[M+1],nei[N+1];
bool vis[N+1];
void dfs(int x){//DFS求CC 
	vis[x]=true;
	for(int i=0;i<nei[x].size();i++){
		int y=nei[x][i];
		if(!vis[y])dfs(y);
	}
}
int main(){
	cin>>n>>m>>s;
	while(s--){
		int x,y;
		scanf("%d%d",&x,&y);
		bel[y].pb(x);
	}
	int ans=-1;
	for(int i=1;i<=m;i++){
		ans+=bel[i].empty();//子任务2 
		for(int j=0;j+1<bel[i].size();j++)nei[bel[i][j]].pb(bel[i][j+1]),nei[bel[i][j+1]].pb(bel[i][j]);
	}//建图 
	for(int i=1;i<=n;i++)if(!vis[i])ans++,dfs(i);//子任务1 
	cout<<ans;
	return 0;
}

eJOI2019

A - XORanges

洛谷题目页面传送门

给定\(n\)个自然数,第\(i\)个为\(a_i\),支持\(2\)种\(q\)次操作:

  1. \(\texttt1\ x\ v\):令\(a_x=v\);
  2. \(\texttt2\ l\ r\):求区间\([l,r]\)的所有子区间的异或和的异或和。

\(n,q\in\left[1,2\times10^5\right]\)。

咋异或完粽子又来异或橙子/yiw

对于操作\(\texttt2\),考虑算贡献法,即考虑\([l,r]\)内所有数被异或进答案多少次。由于是异或,偶数次相当于没有,奇数次相当于\(1\)次。分成\(2\)种情况:

  1. \(l\bmod2=r\bmod2\):此时\(a_i\)会被算\((i-l+1)(r-i+1)\)次。因为\(l,r\)奇偶性相同,所以\(i-l+1,r-i+1\)奇偶性相同,那么\((i-l+1)(r-i+1)\)是奇数当且仅当\(i\bmod2=l\bmod2\)。由于还有单点修改操作,只需维护一个BIT,里面分别维护位置奇、偶\(2\)种的区间异或和即可;
  2. \(l\bmod2\neq r\bmod2\):此时\(a_i\)依然会被算\((i-l+1)(r-i+1)\)次。因为\(l,r\)奇偶性不同,所以\(i-l+1,r-i+1\)奇偶性不同,一奇一偶,乘积肯定偶,所以答案为\(0\)。

代码:

#include<bits/stdc++.h>
using namespace std;
int lowbit(int x){return x&-x;}
const int N=200000;
int n,qu;
int a[N+1];
struct bitree{//BIT 
	int xsm[N+1][2];//2种异或和 
	void init(){//预处理 
		static int Xsm[N+1][2]={};
		for(int i=1;i<=n;i++){
			Xsm[i][0]=Xsm[i-1][0];Xsm[i][1]=Xsm[i-1][1];
			Xsm[i][i&1]^=a[i];
			xsm[i][0]=Xsm[i][0]^Xsm[i-lowbit(i)][0];xsm[i][1]=Xsm[i][1]^Xsm[i-lowbit(i)][1];
		}
	}
	void chg(int x,int v){//单点修改 
		int p=x;
		while(x<=n)xsm[x][p&1]^=a[p]^v,x+=lowbit(x);
		a[p]=v;
	}
	int Xsm(int x,int p){//前缀异或和 
		int res=0;
		while(x)res^=xsm[x][p&1],x-=lowbit(x);
		return res;
	}
	int _xsm(int l,int r){return Xsm(r,l&1)^Xsm(l-1,l&1);}//区间异或和 
}bit;
int main(){
	cin>>n>>qu;
	for(int i=1;i<=n;i++)cin>>a[i];
	bit.init();//BIT初始化 
	while(qu--){
		int tp,x,y;
		cin>>tp>>x>>y;
		if(tp==1)bit.chg(x,y);
		else{
			if((x&1)==(y&1))cout<<bit._xsm(x,y)<<"\n";
			else puts("0");
		}
	}
	return 0;
}

B - Hanging Rack

洛谷题目页面传送门

题意见洛谷。(用\(m\)表示题目中的\(k\))

观察样例+冷静思考可以得出一个结论:第\(i(i\bmod2=1)\)次的挂钩往右平移\(2^{n-1}\)格就是第\(i+1\)次的挂钩。理由很显然,因为要保持最上面的那个连接杆平衡。这样一来,就可以将原问题转化为一个规模减\(1\)的问题,大概是这样的:

if(m%2==1)n--,(m+=1)>>=1;
else n--,m>>=1,(ans+=pw[n])%=mod;

其中pw[i]是\(2^i\)。直到\(n=0\)为止。初始时\(ans=1\)。

预处理\(pw\),复杂度\(\mathrm O(n)\)。

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1000000007;
const int N=1000000;
int pw[N+1];
signed main(){
	int n,m;
	cin>>n>>m;
	pw[0]=1;
	for(int i=1;i<=n;i++)pw[i]=(pw[i-1]<<1)%mod;
	int ans=1;
	while(n){
		if(m%2==1)n--,(m+=1)>>=1;
		else n--,m>>=1,(ans+=pw[n])%=mod;
	}
	cout<<ans;
	return 0;
}

D - Tower

洛谷题目页面传送门

有一个塔,从下往上数层数,初始有\(1\)层数字为\(1\)。每步可以选择已有的所有数字中\([l,r]\)层内所有的数字,计算它们的和并放在塔顶。给定\(n\),求最少需要多少步能构造出塔顶为\(n\)的塔,并给出方案(每次的\(l,r\))。本题多测。

\(n\in\left[1,10^{18}\right]\)。

既然要算最少多少步,不妨先算出步数的下限。每步都尽可能让塔顶大,即每步都选塔内所有数相加,这样第\(1\)步得\(1\),以后每步翻倍,这样至少需要\(ans=\lceil\log_2n\rceil+1\)步塔顶才能\(\geq n\)。

考虑尽可能逼近下限。我们先这样丧心病狂地每步最大化塔顶地建出一个塔,显然长这个样子:第\(i(i\geq2)\)层为\(2^{i-2}\)。此时塔顶是\(\geq n\)的,考虑减少一些塔内的数字使得塔顶\(=n\)。显然\(i\in[3,ans]\),都可以令第\(i\)步的\(l\)由原来的\(1\)变成\(2\),这样第\(i\)层减少\(1\),产生连锁反应,第\(i+1\)层减少\(1\),第\(i+2\)层减少\(2\),……,第\(i+x\)层减少\(2^{x-1}\),于是塔顶减少\(2^{ans-i}\)。\(\left\{2^{ans-i}\mid i\in[3,ans]\right\}=\left\{2^{i}\mid i\in[0,ans-3]\right\}\)。再考虑一共需要减少多少。显然\(2^{ans-1}-n<2^{ans-1}\),又\(n\)二进制下最高位一定为\(1\),则\(2^{ans-1}-n<2^{ans-2}\)。那么将它二进制分解,用集合\(\left\{2^{i}\mid i\in[0,ans-3]\right\}\)恰好永远存在方案凑出来。也就是说下限\(ans\)达得到。于是这题就做完了(这不是某数学老师hzj的名言么)

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
void mian(){
	int n;
	cin>>n;
	int ans=0;
	while(1ll<<ans<n)ans++;
	ans++;
	cout<<ans<<"\n1 1\n";//第1步 
	for(int i=ans-1;i>=2;i--)
		printf("%lld %lld\n",1ll+!!((1ll<<ans-1)-n&1ll<<i-2),ans-i+1);//凑 
	cout<<"1 "<<ans<<"\n";//塔顶 
}
signed main(){
	int testnum;
	cin>>testnum;
	while(testnum--)mian();
	return 0;
}

F - Awesome Arrowland Adventure

洛谷题目页面传送门

题意见洛谷。

看到这种网格题,就想DP,结果发现有环,果断最短路。

考虑对于每两个相邻网格有序对\(((a,b),(c,d))\),若\((a,b)\)处有箭头,那么从\((a,b)\)到\((c,d)\)连一条有向边,边权为从\((a,b)\)的初始箭头方向到\((a,b)\to(c,d)\)应该的方向需要转的次数。然后堆优化Dijkstra即可。\(\mathrm O(nm\log nm)\)。

代码:

#include<bits/stdc++.h>
using namespace std;
#define y0 sdfjaewjfwa
#define mp make_pair
#define X first
#define Y second
#define pb push_back
const int inf=0x3f3f3f3f;
const int N=500,M=500,ASCII=150;
int n,m;
char a[N+1][M+5];
int id[ASCII];const int ds[][4]={{0,1,2,3},{3,0,1,2},{2,3,0,1},{1,2,3,0}}/*方向与方向之间的距离*/,dx[]={-1,0,1,0},dy[]={0,1,0,-1};
bool vld(int x,int y){return 1<=x&&x<=n&&1<=y&&y<=m;}
vector<pair<int,int> > nei[N*M+1];//邻接矩阵 
int dis[N*M+1];
void dijkstra(){//Dijkstra
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
	memset(dis,0x3f,sizeof(dis));
	q.push(mp(dis[1]=0,1));
	while(q.size()){
		int x=q.top().Y;
		q.pop();
		for(int i=0;i<nei[x].size();i++){
			int y=nei[x][i].X,len=nei[x][i].Y;
			if(dis[x]+len<dis[y])q.push(mp(dis[y]=dis[x]+len,y));
		}
	}
//	for(int i=1;i<=n*m;i++)cout<<dis[i]<<" ";puts("");
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i]+1;
	id['N']=0;id['E']=1;id['S']=2;id['W']=3;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]!='X')//连边 
		for(int k=0;k<4;k++){
			int x=i+dx[k],y=j+dy[k];
			if(vld(x,y))nei[(i-1)*m+j].pb(mp((x-1)*m+y,ds[id[a[i][j]]][k]));
		}
	dijkstra();//求最短路 
	cout<<(dis[n*m]<inf?dis[n*m]:-1);
	return 0;
}

然后看到神仙ymx的题解,发现有\(\mathrm O(nm)\)的做法(orzymxtqlddw)。这里需要用到一个小trick。对于一个边权只有\(0,1\)两种的图求最短路时,我们可以把Dijkstra里的堆换成双端队列,松弛成功时若连接边为\(0\)则从队首加入,否则从队尾加入,正确性显然。就去掉了\(\log\)。至于这题,可以将每个格子拆成\(4\)个点,每个点代表一个方向,方向到方向之间连\(1\)边,相邻格子之间连\(0\)边,然后跑上述trick即可。

代码:

#include<bits/stdc++.h>
using namespace std;
#define y0 sdfjaewjfwa
#define mp make_pair
#define X first
#define Y second
#define pb push_back
#define pf push_front
#define ppf pop_front
const int inf=0x3f3f3f3f;
const int N=500,M=500,ASCII=150;
int n,m;
char a[N+1][M+5];
int id[ASCII];const int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
bool vld(int x,int y){return 1<=x&&x<=n&&1<=y&&y<=m;}
vector<pair<int,bool> > nei[4*N*M+1];//邻接矩阵 
int dis[4*N*M+1];
void dijkstra(){//Dijkstra 
	deque<int> q;//双端队列 
	memset(dis,0x3f,sizeof(dis));
	dis[4-id[a[1][1]]]=0;q.pb(4-id[a[1][1]]);
	while(q.size()){
		int x=q[0];
		q.ppf();
		for(int i=0;i<nei[x].size();i++){
			int y=nei[x][i].X;bool len=nei[x][i].Y;
			if(dis[x]+len<dis[y]){
				dis[y]=dis[x]+len;
				if(len)q.pb(y);//队尾加 
				else q.pf(y);//队首加 
			}
		}
	}
//	for(int i=1;i<=4*n*m;i++)cout<<dis[i]<<" ";puts("");
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i]+1;
	id['N']=0;id['E']=1;id['S']=2;id['W']=3;id['X']=0;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j]!='X')//连边 
		for(int k=0;k<4;k++){
			int x=i+dx[k],y=j+dy[k];
			nei[4*((i-1)*m+j)-k].pb(mp(4*((i-1)*m+j)-(k+1)%4,1));
			if(vld(x,y))nei[4*((i-1)*m+j)-k].pb(mp(4*((x-1)*m+y)-id[a[x][y]],0));
		}
	dijkstra();//求最短路 
	cout<<(dis[4*n*m-id[a[n][m]]]<inf?dis[4*n*m-id[a[n][m]]]:-1);
	return 0;
}
上一篇:LeetCode算法刷题记录


下一篇:奇异值分解SVD