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\)扔进多重集即可。multiset的count()函数复杂度是线性的，可以用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;
}