lp2324 SCOI2005 骑士精神

一道\(IDA*\)的入门题。
首先我们发现移动空格比移动马更容易。
然后考虑如何移动。爆搜马的位置是一种有效的做法。
但是直接爆搜很容易出现一个问题:搜索可能会在一些劣的情况下搜很久,或者搜进死胡同不出来。
这时候我们设计一个东西叫做估价函数\(g_S\),如果当前局面的花费\(h_S\)加上估价函数大于花费上界\(f_S\)的话,这条选择支就是不优的。
然后我们可以枚举上界进行搜索。
由于随着上界的增长,花费的增长速度极快——每一层的花费都远大于上一层的花费。故而尽管上界具有单调性,但二分上界并不会更优。
(其实\(IDA*\)本质上就是玄学剪枝吧。)

#include<iostream>
#include<cstdio>

int nw[6][6];
const int mp[6][6]={
    {0,0,0,0,0,0},
    {0,1,1,1,1,1},
    {0,0,1,1,1,1},
    {0,0,0,-1,1,1},
    {0,0,0,0,0,1},
    {0,0,0,0,0,0},
};
const int dx[8]={-2,-2,-1,-1,1,1,2,2};
const int dy[8]={1,-1,2,-2,2,-2,1,-1};
inline int val(){
    int rt=0;
    for(int i=1;i<=5;++i){
        for(int j=1;j<=5;++j){
            if(mp[i][j]!=nw[i][j]){
                ++rt;
            }
        } 
    }
    return rt;
}

inline int Min(int A,int B){
    return A>B?A:B;
}

inline void Swap(int &X,int &Y){
    X^=Y^=X^=Y;
}

inline bool srch(int dp,int X,int Y,int dm,int lst){
    int Nval=val();
    if(!Nval){
        return 1;
    }
    if(dp>dm){
        return 0;
    }
    for(int i=0;i<8;++i){
        if(i+lst==7){
            continue;
        }
        int NX=X+dx[i],NY=Y+dy[i];
        if(NX<1||NY<1||NX>5||NY>5){
            continue;
        } 
        Swap(nw[X][Y],nw[NX][NY]);
        Nval=val();
        if(Nval+dp<=dm+1){
            if(srch(dp+1,NX,NY,dm,i)){
                return 1;
            }
        }
        Swap(nw[X][Y],nw[NX][NY]);
    }
    return 0;
}

void init(){
    char ch[6];
    int SX,SY;
    for(int i=1;i<=5;++i){
        std::cin>>ch+1;
        for(int j=1;j<=5;++j){
            nw[i][j]=ch[j]-'0';
            if(!isdigit(ch[j])){
                nw[i][j]=-1;
                SX=i,SY=j;
            }
        }
    }
    if(!val()){
        puts("0");
        return;
    }
    for(int i=1;i<=15;++i){
        if(srch(1,SX,SY,i,-1)){
            printf("%d\n",i);
            return;
        }
    }
    puts("-1");
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

 

博客搬迁

博客成功搬迁到了bwh8.net下的主机。服务器在美国,不过有针对中国的网络优化。
这样就可以用上域名辣!
SmokeyDays.top
搬迁的过程中遇到了两件尴尬的事情:
一是MySQL的密码一直不知道怎么重设。
事实上我已经忘了上次怎么重设的了,花了我一个多小时的时间折腾。现在把方案保存好待用。

MySQL密码重置方法:
首先进入/etc/目录,修改my.cnf,在[mysqld]下添加skip-grant-tables字样。
然后使用

mysql -u root -p 

登录MySQL。
接着输入命令


update mysql.user set password=PASSWORD(‘12345678‘) where user=‘root‘;
flush privileges;
quit;

即可。
二是首页无限重定向。这个发现之后另外写了一篇:
/nginx下wordpress循环重定向问题解决方案/

NOIP2018 旅行

题目大意:求一棵树的最小DFS序,和一张n条边的连通图删去任意一条边以后的最小DFS序。
话说这一题和我出过的某一道题非常神似,都是在求一些特定的DFS序。就连对DFS的描述也和我的描述非常相似。
所以在考场上我用了几分钟的时间概括出了简要题面,然后用了十分钟写掉了。
第一个子问题很简单,贪心地DFS即可,这是因为字典序的特性,使得,如果每一次拓展都选择的是当前最小的,那么总是不会更劣。
对于第二个子问题,它不再是求纯粹的DFS序了,但是看到\(n=5000\)的数据范围,可以想到暴力枚举删边,这就转化为第一个问题。
如果依然是一边DFS一边删边的话,最坏情况下可能会达到\(O(n^2*logn)\)的复杂度,尽管有32Gi7,也很难通过一些大数据。
我们考虑预处理。首先将读入的边排序,然后插入边表。这样遍历的顺序就是从小到大了。
注意对边进行预排序时,由于插入边表是倒序插入,所以应当让末端点从大到小排序。
这就做完了。

#include<iostream>
#include<cstdio>
#include<algorithm>
int n,m;
struct ee{
	int v;
	int nxt;
}e[10005];
int h[5005],et=0;
inline void add(int u,int v){
	e[++et]=(ee){v,h[u]};
	h[u]=et;
}
struct e0{
	int u;
	int v;
	bool operator<(const e0 &B)const{
		return (u==B.u)?(v>B.v):(u<B.u);
	}
}e0[10005],e00[5005];
int Du,Dv,ans[5005],Ans[5005],at=0;
bool vis[5005];
inline void dfs(int X){
	vis[X]=1,ans[++at]=X;
	for(int i=h[X];i;i=e[i].nxt){
		if(vis[e[i].v]||(e[i].v==Du&&X==Dv)||(e[i].v==Dv&&X==Du)){
			continue;
		}
		dfs(e[i].v);
	}
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d%d",&e0[i].u,&e0[i].v);
		e00[i].u=e0[i].u,e00[i].v=e0[i].v;
		e0[i+m].u=e0[i].v,e0[i+m].v=e0[i].u;
	}
	std::sort(e0+1,e0+(m<<1|1));
	for(int i=1;i<=(m<<1);++i){
		add(e0[i].u,e0[i].v);
	}
	if(m==n-1){
		Du=0,Dv=0;
		dfs(1);
		for(int i=1;i<=n;++i){
			printf("%d ",ans[i]);
		}
		return;
	}else if(m==n){
		for(int i=1;i<=n;++i){
			Ans[i]=0x3f3f3f3f;
		}
		for(int i=1;i<=m;++i){
			Du=e00[i].u,Dv=e00[i].v;
			at=0;
			for(int j=1;j<=n;++j){
				vis[j]=0;
			}
			dfs(1);
			if(at==n){
				for(int j=1;j<=n;++j){
					if(ans[j]==Ans[j]){
						continue;
					}else if(ans[j]>Ans[j]){
						break;
					}else{
						for(int k=1;k<=n;++k){
							Ans[k]=ans[k];
						}
						break;
					}
				}
			}
		}
		for(int i=1;i<=n;++i){
			printf("%d ",Ans[i]);
		}
	}
}
int main(){
	init();
	return 0;
}

 

NOIP2018 赛道修建

一道树形DP裸题。
因为部分分给得很足,所以我在考场上先打了一堆部分分,建了5个命名空间。
然后在打二叉树的部分分的时候想到了正解。(虽然可能二分写挂了)
题目大意:给定一棵带权树,将它的一部分拆成\(m\)条链,使得权值最短的链的权值最大。
最小的求最大,当然满足无后效性,所以我们考虑二分答案。
然后我们考虑检验。首先,很容易可以发现答案具有无后效性。换句话说,每个子树在计算出它对答案的贡献之后,就只需要计算出它对父节点的贡献。
这是因为,每一个父节点,它能使用的仅有子树的一条链,而不是整个子树的信息。
故而,我们只需要「可以提供给父节点的那条链」的值更新上去即可。我们用\(f_{x}\)表达这个上传的值。
并且,对于每棵子树是可以贪心地处理的——如果一棵子树中的一条链可以和另一条链组成一条合法的链,那就没必要把它上传了。
这是因为,如果不上传,一定可以对答案产生1的贡献;如果上传了,仅仅是有可能对答案产生1的贡献。
那么我们对每个子树分别考虑。这就转化为了一个新的问题:
「对于一个长度为\(n\)的序列,取出其中尽可能多的数对或数,使得数对的和或数的值大于给定值,并且在有遗留数的情况下使得遗留的数的值最大。」
这个问题要怎么做呢?将它们从小到大排序,那么对于大于给定值的数,单独选取是更优的。
然后处理剩下来的数。用双指针做。
如果右指针的数可以与左指针指的数组成合法数对就把右指针推入栈中,直到没有合法的右指针,就考虑栈中是否为空。
如果不为空就说明存在一个可以和左指针匹配的数,那么就将答案加一,否则左指针就找不到数和它匹配了,那么就用它来更新\(f{x}\)左指针往右推。一直到序列为空。
然后,对于剩下的数,它们一定都可以组成合法数对——这是因为所有被推入栈中的数,都可以和一个比栈中最小数还要小的数组成合法数对。
那么,我们考虑剩下的数的数量的奇偶性。如果是奇数个,那么就计算答案之后用最大值来更新\(f_{x}\)。
这就做完了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
struct ee{
	int v;
	int w;
	int nxt;
}e[50005];
int h[50005],et=0;
int n,m;
inline void add(int u,int v,int w){
	e[++et]=(ee){v,w,h[u]};
	h[u]=et;
}
int MN,rt=0,f[50005],nw;
int st[50005],tp=0,st2[50005],tp2=0;
inline void dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		dfs(e[i].v);
	}
	tp=0,tp2=0;
	for(int i=h[X];i;i=e[i].nxt){
		st[++tp]=f[e[i].v]+e[i].w;
	}
	std::sort(st+1,st+1+tp);
	while(tp&&st[tp]>=MN){
		--tp;
		++rt;
	}
	for(int i=1;i<=tp;++i){
		while(i<tp&&st[i]+st[tp]>=MN){
			st2[++tp2]=st[tp];
			--tp;
		}
		if(tp2){
			--tp2;
			++rt;
		}else{
			f[X]=st[i];
		}
	} 
	if(tp2&1){
		f[X]=st2[1];
	}
	rt+=(tp2>>1);
} 
inline bool chck(int X){
	std::memset(f,0,sizeof(f));
	MN=X;
	rt=0;
	dfs(1);
	if(rt>=m){
		return 1;
	}else{
		return 0;
	}
}
void init(){
	scanf("%d%d",&n,&m);
	int u,v,w;
	for(int i=1;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		if(u>v){
			u^=v^=u^=v;
		}
		add(u,v,w);
	}
	int l=0,r=0x3f3f3f3f,mid,ans=0;
	while(l<=r){
		mid=(l+r)>>1;
		if(chck(mid)){
			l=mid+1;
			ans=mid;
		}else{
			r=mid-1;
		}
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}

 

NOIP2018 货币系统

一道看起来像数论题的完全背包问题。
幸好我前一天没有仔细看数论,使得我想的是写暴力…要不然我可能真的会推一个小时的\(EXGCD\)或\(CRT\)或者高斯消元之类的东西。
总之是小凯的疑惑迷惑了我,以为是一道数论题,所以到最后我都以为自己写的是暴力。
结果发现其实是正解思路的,已经写到了正解的倒数第二步,随便一优化就通过了。
但是始终以为是打暴力。
果然还是太菜了。
题意简述:你有\(n\)个正整数,要求,确定一个最小的\(m\),使得用\(m\)种正整数数能够表示的数集与题目给出数能够表示的数集的完全一致。
首先我们证明一个定理:答案的\(m\)个数一定是原有数的子集。
下面我们分两类考虑这个问题。
如果新的数可以被原有数表示,那么显然它是没有意义的。
如果新的数不能被原有数表示,那么显然它是不合法的。
那么我们只需要考虑删除哪些数即可。
我们发现,一个数需要删除,当且仅当它可以被其他数表达出来。
反证法:如果它不可被其他数表示的话,那么删除它以后它就无法表示出来了。
并且,我们可以发现,这个问题满足最优子结构:如果一个数可以被当前的系统表达出来,那么删除当前系统中任意一些可以被表达出来的数,都不会导致这个数不能被表达出来。
故而,先删哪个其实都不影响答案的正确性。
因此我们可以从小往大删(可能可以节省时间)
暴力地考虑,我们需要枚举值域内每一个已经可以被表达出来的数,然后将这个数加上当前数的任意倍(值域范围内)
这么做最坏可能是\(O(T*n*a^2)\)的。
考虑优化。用欧拉筛的思想,对于每一个数,我们只需要加上当前数的一倍即可。
因为,如果加上当前数的两倍的话,就会在之后再一次访问到这个数,这时候就产生了访问次数上的浪费。
这样做是\(O(T*n*a)\)。
那就做完了。

#include<cstdio>
#include<iostream>
#include<algorithm> 
#include<cstring>

int n,a[105];
bool usf[25005];
void init(){
	std::memset(usf,0,sizeof(usf));
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	if(n==1){
		puts("1");
		return;
	}
	std::sort(a+1,a+1+n);
	int cnt=n;
	usf[0]=1;
	for(int i=1;i*a[1]<=25000;++i){
		usf[i*a[1]]=1;
	}
	for(int i=2;i<=n;++i){
		if(usf[a[i]]){
			a[i]=0;
			--cnt;
		}else{
			for(int j=0;j+a[i]<=25000;++j){
				if(!usf[j]){
					continue;
				}else{
					usf[j+a[i]]=1;
				}
			}
		}
	}
	printf("%d\n",cnt);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}

 

NOIP2018 铺设道路

题意简述:
有一个序列,你可以一次将一个连续的段-1,但是不能让一个段变成0,求最小变成全零的操作次数。
方法有很多,个人的做法是差分以后把所有正值加起来。
没有细节,NOIP2013原题,完全就是为了送分。
感谢良心出题人。

#include<iostream>
#include<cstdio>
int n,a[100010],da[100010];

void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	for(int i=1;i<=n;++i){
		da[i]=a[i]-a[i-1];
	}
	int sm=0;
	for(int i=1;i<=n;++i){
		da[i]=std::max(da[i],0);
		sm+=da[i];
	}
	printf("%d\n",sm);
}
int main(){
	init();
	return 0;
}

 

lp1486 NOI2004 郁闷的出纳员

(似乎很少看见权值线段树的做法的样子。但是权值线段树如果动态开点、大胆卡常的话,是可以跑得飞快的。)
首先看一下题面,发现值域很小,很容易就可以想到用权值线段树维护。
支持:单点加,区间清零,查询第k大的权值线段树。
当然这题有一些细节。
一:如果初始工资低于工资下限,那么这个人就不存在。
二:维护的是第\(k\)大的而非第\(k\)小的。
三:由于是严格小于工资下限,要注意边界的开闭性。最好将公式写出来。

#include<iostream>
#include<cstdio>
using namespace std;
#define LS (X<<1)
#define RS (X<<1|1)
#define LEN (R-L+1)
#define MID ((L+R)>>1)
#define LLEN (MID-L+1)
#define RLEN (R-MID) 
//支持:单点加,区间清零,查询第k大的权值线段树。
int tr[2000005],cnt=0; 
inline void updt(int X){
	tr[X]=tr[LS]+tr[RS];
}
inline void pshd(int X,int L,int R){
	if(!tr[X]){
		tr[LS]=tr[RS]=0;
	}
}
inline void add(int X,int L,int R,int A){
	if(L==R){
		++tr[X];
		return;
	}
	pshd(X,L,R);
	if(A<=MID){
		add(LS,L,MID,A);
	}else{
		add(RS,MID+1,R,A);
	}
	updt(X);
}
inline void clr(int X,int L,int R,int A,int B){
	if(A<=L&&R<=B){
		cnt+=tr[X];
		tr[X]=0;
		return;
	}
	pshd(X,L,R);
	if(A<=MID){
		clr(LS,L,MID,A,B);
	}
	if(B>MID){
		clr(RS,MID+1,R,A,B);
	}
	updt(X);
}
inline int srch(int X,int L,int R,int K){
	if(L==R){
		return L;
	}
	pshd(X,L,R);
	if(tr[RS]<K){
		return srch(LS,L,MID,K-tr[RS]);
	}else{
		return srch(RS,MID+1,R,K);
	}
}
inline int qry(int X,int L,int R,int A,int B){
	if(A<=L&&R<=B){
		return tr[X];
	}
	pshd(X,L,R);
	int rt=0;
	if(A<=MID){
		rt+=qry(LS,L,MID,A,B);
	}
	if(B>MID){
		rt+=qry(RS,MID+1,R,A,B);
	}
	updt(X);
	return rt;
}
//1 k 插入大小为k的点
//2 k 全部数加上k
//3 k 全部数减去k
//4 k 查询第k大的值 
int n,m,tg=0,k;
char op[4];
void init(){
	scanf("%d%d",&n,&m);
	--m;
	for(int i=1;i<=n;++i){
		cin>>op;
		scanf("%d",&k);
		if(op[0]=='I'){
			//注意大于与大等于。 
			if(k>m){
				add(1,1,300001,k+100001+tg);
			}
		}else if(op[0]=='A'){
			tg-=k; 
		}else if(op[0]=='S'){
			tg+=k;
			clr(1,1,300001,1,m+100001+tg);
		}else if(op[0]=='F'){
			if(qry(1,1,300001,1,300001)<k){
				puts("-1");
			}else{
				printf("%d\n",srch(1,1,300001,k)-100001-tg);
			}
		}
	}
	printf("%d",cnt);
}
int main(){
	init();
	return 0;
}

 

线性求逆元

$$我们有一个质数p$$
$$\forall i\in Z,def\ q_{i}=[\frac{p}{i}],r_{i}=p\%i\ st:\ p = iq_{i}+r_{i} \ (1)$$
$$def\ i^{-1}*i≡1\ (mod\ p)$$
$$(1)*i^{-1}$$
$$=>p*i^{-1}≡q_{i}+r_{i}*i^{-1}\ (mod\ p)$$
$$∵(p*i^{-1})\%p≡0\ (mod\ p)$$
$$∴r_{i}*i^{-1}≡-q_{i}\ (mod\ p)$$
$$i^{-1}≡-q_{i}*r_{i}^{-1}\ (mod\ p)$$
$$i^{-1}≡(p-[\frac{p}{i}])*(p\%i)^{-1}\ (mod\ p)$$
代码非常简短:

#include<iostream>
#include<cstdio>
int MOD;
int inv[1000005],n;
int main(){
	scanf("%d%d",&n,&MOD);
	inv[1]=1;
	for(int i=2;i<=n;++i){
		inv[i]=(MOD-(MOD/i))*inv[MOD%i]%MOD;
	}
	for(int i=1;i<=n;++i){
		printf("%d ",inv[i]); 
	}
}

 

NOIP2018游记

\(Day0\):
今天应该是要看考场的。
早上没有训练。在机房趴着睡到了九点多。然后起来划水到了十一点多。
中午吃完饭回来在机房和两个同学一起刷知乎,然后补番到一半又开始复习数论。接着看到了一道“好”题,就和同学一起口胡了一下。
然后上去试机,开始打之前看到的那道题,但是没打完试机就结束了。然后下楼以后继续开心debug,但是还是没有弄出来。回到宿舍以后继续开心debug,终于调出来了。真是一道丧题。
对,我说的就是NOI2004 郁闷的出纳员
(话说调到一半调不下去了,看了一集「黄金拼图」,然后回来就调出来了,愿吉老师赐予我力量(大雾))

\(Day1\):
T1大水题,T2有点小坑,以为是数论结果写了正解思路自己以为是暴力,T3给了很多部分分然后拿部分分的时候想到正解来不及打(也打不出来)。
感觉这场有点水,大家都考得很高,我估分好像也比较高,我觉得有点方。主场作战也是有优势的,上厕所调整思路真是超有用的。
大概就是这样。
今天并没有见到某个喜欢做很多事情的女孩子,希望明天也不要见到。(大雾)
话说打开空间才发现明天竟然是双十一。虽然在广告中有看到但是好像没有实感的样子。

\(Day2\):
令人欣慰的是,今年真的没有那位女孩子。而且本人在群里说了并没有参与出题,太爽了。
今天的题比昨天不知道丧到哪里去了。传说今年的题存在一个叫做时间-难度不等式的东西,居然是真的——
$$ D_{1}T_{1}<D_{1}T_{2}<D_{1}T_{3}<D_{2}T_{1}<D_{2}T_{2}<D_{2}T_{3} $$
试卷的解压密码是「笑书神侠」,仔细想想昨天的解压密码是「飞雪连天」。莫名间一阵伤感。
T1和我出过的某一道题非常神似,都是在求一些特定的\(DFS\)序。就连对\(DFS\)的描述也和我的描述非常相似。
所以在考场上我用了几分钟的时间概括出了简要题面,然后用了十分钟写掉了。
T2和T3简直丧心病狂。
T2我一开始以为是一道结da论biao题,然后就写了个暴力硬上。打了一张5*6的表格,然后找规律推了\(65\)分的公式出来;
很容易可以发现两个定理:
一:对于一个点,如果它的左下方是0,那么它就不可能是一。
二:对于一条左下-右上的斜线段,如果它的颜色一样,那么位于它右下方的所有斜线段颜色都必须一样。
那么我们就可以考虑\(DP\),具体来说,就是,记每一条斜线的\(0-1\)分界,然后从左上往右下转移。
T3先是写了链的部分,一开始思路错了,是把序列拆成三个部分然后分别处理并且合并,写了一个三十多行的转移。然后上了一下厕所回来发现自己简直是智障,其实就是,把「要求放的地方的花费设0,不要求放的地方花费设无穷大」。然后其实就变成求带权树上覆盖集。这种做法的复杂度是\(O(n*m)\)的。如果足够聪明你就会发现,其实在求出初始花费之后,每一次询问造成的影响只会影响从这一个点到根的一整条链。所以找到树的重心之后用这种方法更新,可能可以缩小常数。
总之T2、T3我到现在都不会写正解。
考试剩下五分钟的时候感觉还不错,可能今天可以拿\(233\)分。结果测一下大样例发现我T3的暴力写挂了。所以就不知道会炸成什么样了。
出来以后在考场门口合了个影,然后就开始愉快划水了。
(尽管明天需要期中考qwq)
题目解析:
解析什么的…不存在的23333
祝大家RP++

NOIP2018 D1T1铺设道路
NOIP2018 D1T2货币系统
NOIP2018 D1T3赛道修建
NOIP2018 D2T1旅行

CF799C Fountains

CF799C Fountains
可以上数据结构维护,当然也可以大力分类讨论。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,A,B,Ct=0,Dt=0;
struct data{
    int b;
    int p;
    bool operator <(const data &_B)const{
        return p<_B.p;
    }
}C[100005],D[100005];
inline int slv1(){
    if((!Ct)||(!Dt)){
        return 0;
    }
    if(C[1].p>A||D[1].p>B){
        return 0;
    }
    int rtC=0,rtD=0,pC=1,pD=1;
    while(pC<=Ct&&C[pC].p<=A){
        rtC=max(rtC,C[pC].b);
        ++pC;
    }
    while(pD<=Dt&&D[pD].p<=B){
        rtD=max(rtD,D[pD].b);
        ++pD;
    }
    return rtC+rtD;
}
//AC[i]表示,剩余为i时的最大收益,rAC[i]表示,剩余大于等于i时的最大收益。 sAC与srAC分别表示它们的位置。 
int AC[100005],rAC[100005],sAC[100005],srAC[100005],sbAC[100005];
inline int slv2(){
    if(Ct<2){
        return 0;
    }
    if(C[1].p+C[2].p>A){
        return 0;
    }
    int rtC=0;
    for(int i=1;i<=Ct&&C[i].p<=A;++i){
        if(AC[A-C[i].p]<C[i].b){
            AC[A-C[i].p]=C[i].b,sAC[A-C[i].p]=i;
        }
    }
    for(int i=A;i>=1;--i){
        if(rAC[i+1]>AC[i]){
            rAC[i]=rAC[i+1];
            srAC[i]=srAC[i+1]; 
        }else{
            rAC[i]=AC[i];
            srAC[i]=sAC[i]; 
        }
    }
    for(int i=1;i<=Ct;++i){
        if(i!=srAC[C[i].p]&&rAC[C[i].p]){
            rtC=max(rtC,C[i].b+rAC[C[i].p]);
        }else{
        	//rtC=max(rtC,C[i].b+C[i-1].b);
		}
    }
    return rtC;
}

int BD[100005],rBD[100005],sBD[100005],srBD[100005];
inline int slv3(){
    if(Dt<2){
        return 0;
    }
    if(D[1].p+D[2].p>B){
        return 0;
    }
    int rtD=0;
    for(int i=1;i<=Dt&&D[i].p<=B;++i){
        if(BD[B-D[i].p]<D[i].b){
            BD[B-D[i].p]=D[i].b,sBD[B-D[i].p]=i;
        }
    }
    for(int i=B;i>=1;--i){
        if(rBD[i+1]>BD[i]){
            rBD[i]=rBD[i+1];
            srBD[i]=srBD[i+1]; 
        }else{
            rBD[i]=BD[i];
            srBD[i]=sBD[i]; 
        }
    }
    for(int i=1;i<=Dt;++i){
        if(i!=srBD[D[i].p]&&rBD[D[i].p]){
            rtD=max(rtD,D[i].b+rBD[D[i].p]);
        }
    }
    return rtD;
}
void init(){
    scanf("%d%d%d",&n,&A,&B);
    char ch[5];
    int x,y;
    for(int i=1;i<=n;++i){
        scanf("%d%d",&x,&y);
        cin>>ch;
        if(ch[0]=='C'){
            C[++Ct]=(data){x,y};
        }else{
            D[++Dt]=(data){x,y};
        }
    }
    sort(C+1,C+1+Ct);
    sort(D+1,D+1+Dt);
    int ans=0;
    ans=max(ans,slv1());
    ans=max(ans,slv2());
    ans=max(ans,slv3());
    printf("%d\n",ans);
}
int main(){
    init();
    return 0;
}

 

lp2572 SCOI2010 序列操作

操作要求:
0 a b 把[a, b]区间内的所有数全变成0
1 a b 把[a, b]区间内的所有数全变成1
2 a b 把[a,b]区间内的所有数全部取反,也就是说把所有的0变成1,把所有的1变成0
3 a b 询问[a, b]区间内总共有多少个1
4 a b 询问[a, b]区间内最多有多少个连续的1
我们考虑维护线段树来处理这些询问。
考虑线段树的基本性质。线段树的特性决定了它能够\(O(nlogn)\)来处理各种能够\(O(1)\)合并两个子区间信息的信息。
上述询问中,总共有多少个1是很容易可以维护的。最大的问题在于维护“最多有多少个连续的1”
实际上,对于这里的每一种信息,我们都需要对称地维护它们——即,在维护1的信息的同时也要维护0的信息。这是操作\(2\)导致的。
我们考虑对于两种询问分别考虑。
首先是\(3\),这个很好维护,直接维护\(1\)的个数即可。合并的时候简单相加即可。
对于\(4\),第一个想到的肯定是可以维护区间的最长连续1。
但是我们发现,仅仅维护这个信息还是不够的。因为这样是无法把子区间的信息合并的。
我们反过来考虑,对于一个区间,它的最长连续1有可能怎样从两个子区间转移过来。
首先,可能是完全被包含在两个区间之一。这种情况的话,只需要维护区间的最长连续1,然后取Max即可。
但是,还有可能这个区间是跨越了两个区间的。这时候我们需要维护,子区间左起最长连续1与右起最长连续1。
然后,在转移区间信息的时候,我们只需要再考虑两个子区间的左起最长连续1与右起最长连续1即可。
接着我们考虑对于端点起最长连续1的转移——这种转移存在一种特殊情况,也就是,这个区间的端点起最长连续1的长度超过了中点。
这时候需要特殊判定。
这样就做完了。
写了5k,的确是一道麻题。

另,我莫名其妙RE了,估计是不知道哪里边界判挂了。考试的时候要注意在不MLE的情况下多开几倍的数组保险。

#include<iostream>
#include<cstdio>

#define LS (X<<1)
#define RS (X<<1|1)
#define MID ((L+R)>>1)
#define LEN (R-L+1)
#define LLEN (MID-L+1)
#define RLEN (R-MID)
int n,m,a[100005],A,B,op;
inline int Max(int AA,int BB){
    return AA>BB?AA:BB;
}
struct data{ 
    int sm0;int sm1;
    int mx0;int mx1;
    int lmx0;int lmx1;
    int rmx0;int rmx1;
    //有翻转标记为1,否则为0;没有赋值为-1,有为0或1; 
    int lzy;int st;
    data(int sm0=0,int sm1=0,int mx0=0,int mx1=0,int lmx0=0,int lmx1=0,int rmx0=0,int rmx1=0,int lzy=0,int st=-1):
        sm0(sm0),sm1(sm1),mx0(mx0),mx1(mx1),lmx0(lmx0),lmx1(lmx1),rmx0(rmx0),rmx1(rmx1),lzy(lzy),st(st){}
}tr[300005];//262144
inline data mrg(const data &X,const data &Y,const data BS){
    data RT;
    RT.mx0=Max(X.mx0,Y.mx0);
    RT.mx0=Max(RT.mx0,X.rmx0+Y.lmx0);
    RT.sm0=X.sm0+Y.sm0;
    //一个巧妙的技巧,如果存在1,那么肯定不是全0,反之亦然。 
    RT.lmx0=X.sm1?X.lmx0:X.lmx0+Y.lmx0;
    RT.rmx0=Y.sm1?Y.rmx0:Y.rmx0+X.rmx0;
    
    RT.mx1=Max(X.mx1,Y.mx1);
    RT.mx1=Max(RT.mx1,X.rmx1+Y.lmx1);
    RT.sm1=X.sm1+Y.sm1;
    RT.lmx1=X.sm0?X.lmx1:X.lmx1+Y.lmx1;
    RT.rmx1=Y.sm0?Y.rmx1:Y.rmx1+X.rmx1;
    RT.lzy=BS.lzy;RT.st=BS.st;
    return RT;
}
inline void updt(int X){
    tr[X]=mrg(tr[LS],tr[RS],tr[X]);
}
inline void rnw1(int X,int L,int R){
    std::swap(tr[X].lmx0,tr[X].lmx1);
    std::swap(tr[X].rmx0,tr[X].rmx1);
    std::swap(tr[X].mx0,tr[X].mx1);
    std::swap(tr[X].sm0,tr[X].sm1);
}
inline void rnw20(int X,int L,int R){
    tr[X].lmx0=LEN;tr[X].lmx1=0;
    tr[X].rmx0=LEN;tr[X].rmx1=0;
    tr[X].mx0=LEN;tr[X].mx1=0;
    tr[X].sm0=LEN;tr[X].sm1=0;
}
inline void rnw21(int X,int L,int R){
    tr[X].lmx0=0;tr[X].lmx1=LEN;
    tr[X].rmx0=0;tr[X].rmx1=LEN;
    tr[X].mx0=0;tr[X].mx1=LEN;
    tr[X].sm0=0;tr[X].sm1=LEN;
}
inline void rnw(int X,int L,int R,int TYP){
    if(TYP==0){
        tr[X].lzy=0;tr[X].st=0;
        rnw20(X,L,R);
    }else if(TYP==1){
        tr[X].lzy=0;tr[X].st=1;
        rnw21(X,L,R);
    }else{
        tr[X].lzy^=1;
        rnw1(X,L,R);
    }
}
inline void pshd(int X,int L,int R){
    if(tr[X].st>-1){
        rnw(LS,L,MID,tr[X].st);rnw(RS,MID+1,R,tr[X].st);
        tr[X].st=-1;
    }
    if(tr[X].lzy){
        rnw(LS,L,MID,2);rnw(RS,MID+1,R,2);
        tr[X].lzy=0;
    }
}
inline void chg(int X,int L,int R,int TYP){
    if(A<=L&&R<=B){
        //如果完全被包含则直接更新。 
        rnw(X,L,R,TYP);
        return;
    }
    pshd(X,L,R);
    if(A<=MID){
        chg(LS,L,MID,TYP);
    }
    if(B>MID){
        chg(RS,MID+1,R,TYP);
    }
    updt(X);
}
inline data qry(int X,int L,int R){
    if(A<=L&&R<=B){
        pshd(X,L,R);
        return tr[X];
    }
    pshd(X,L,R);
    if(A<=MID){
        if(B>MID){
            return mrg(qry(LS,L,MID),qry(RS,MID+1,R),data());
        }else{
            return qry(LS,L,MID);
        }
    }else{
        if(B>MID){
            return qry(RS,MID+1,R);
        }else{
            return data();
        }
    }
}

inline void build(int X,int L,int R){
    if(L==R){
        tr[X]=(data){a[L]^1,a[L],a[L]^1,a[L],a[L]^1,a[L],a[L]^1,a[L],0,-1};
        return;
    }
    build(LS,L,MID);
    build(RS,MID+1,R);
    updt(X);
}
void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    data ans;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&op,&A,&B);
        ++A,++B;
        if(op<3){
            chg(1,1,n,op);
        }else if(op==3||op==4){
            ans=qry(1,1,n);
            if(op==3){
                printf("%d\n",ans.sm1);
            }else if(op==4){
                printf("%d\n",ans.mx1);
            }
        }
    }
}
int main(){
    init();
    return 0;
}

 

LUOGU T12607

lt2025 攀爬者
排序以后大力模拟即可,水题,没什么好讲的。

lt2027 蜈蚣
暴力的做法是维护前缀异或和然后大力DP
注意\(f_{i}{0}\)是不可选取的。
还有注意卡常。

lt2005 区间方差
简单于lp1471 方差,注意多膜。
传参数的时候注意参数的位置。

lt2061 最大差值
找到后缀最大值,找到前缀最小值,扫一遍求差。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
/*
lt2025 攀爬者
*/
struct data{
	int x;
	int y;
	int z;
	bool operator<(const data &B)const{
		return z<B.z;
	}
}a[50005];
inline double calc(int A,int B){
	return sqrt((a[A].x-a[B].x)*(a[A].x-a[B].x)+(a[A].y-a[B].y)*(a[A].y-a[B].y)+(a[A].z-a[B].z)*(a[A].z-a[B].z));
}
int n;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
	}
	sort(a+1,a+1+n);
	double ans=0;
	for(int i=1;i<n;++i){
		ans+=calc(i,i+1);
	}
	printf("%.3lf",ans);
}

 

#include<iostream>
#include<cstdio>
using namespace std;
#define INF 1000000000
/*
lp2027 蜈蚣
*/
int n,m,a[1005],f[1005][105],sm[1005];
inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	sm[0]=0;
	for(int i=1;i<=n;++i){
		sm[i]=sm[i-1]^a[i];
		f[i][0]=-INF;
	}
	int mn;
	for(register int i=1;i<=n;++i){
		mn=Min(i,m);
		for(register int j=1;j<=mn;++j){
			for(register int k=j-1;k<i;++k){
				f[i][j]=Max(f[i][j],f[k][j-1]+(sm[i]^sm[k]));
				//printf("[%d,%d,%d]%d ",i,j,k,f[i][j]);
			}
			//printf(",");
		}
		//puts("");
	}
	printf("%d\n",f[n][m]);
}
int main(){
	init();
	return 0;
}
#include<iostream>
#include<cstdio>
using namespace std;
#define LEN (R-L+1)
#define MID ((L+R)>>1)
#define LLEN (MID-L+1)
#define RLEN (R-MID)
#define LS (X<<1)
#define RS (X<<1|1)
#define cIz 1000000007
/*
lt2005 区间方差
*/ 
typedef long long ll;
struct data{
	ll sm;
	ll sm2;
}tr[270005];//262141

inline ll pw(ll X,ll A){
	ll rt=1;
	while(X){
		if(X&1){
			rt*=A;
			rt%=cIz;
		}
		X>>=1;
		A*=A;
		A%=cIz;
	}
	return rt;
}
inline ll inv(ll X){
	return pw(cIz-2,X);
}
inline void updt(int X){
	tr[X].sm2=(tr[LS].sm2+tr[RS].sm2)%cIz;
	tr[X].sm=(tr[LS].sm+tr[RS].sm)%cIz;
}
inline void chg(int X,int L,int R,int A,ll K){
	if(L==R){
		tr[X].sm=K;
		tr[X].sm2=K*K%cIz;
		return;
	}
	if(A<=MID){
		chg(LS,L,MID,A,K);
	}else{
		chg(RS,MID+1,R,A,K);
	}
	updt(X);
}
inline ll qrySm(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return tr[X].sm;
	}
	ll rt=0;
	if(A<=MID){
		rt+=qrySm(LS,L,MID,A,B);
	}
	if(B>MID){
		rt+=qrySm(RS,MID+1,R,A,B);
	}
	return rt%cIz;
}
inline ll qrySm2(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return tr[X].sm2;
	}
	ll rt=0;
	if(A<=MID){
		rt+=qrySm2(LS,L,MID,A,B);
	}
	if(B>MID){
		rt+=qrySm2(RS,MID+1,R,A,B);
	}
	return rt%cIz;
}
int n,m;
ll a[100005];
inline void build(int X,int L,int R){
	if(L==R){
		tr[X].sm=a[L];
		tr[X].sm2=(a[L]*a[R])%cIz;
		return;
	}
	build(LS,L,MID);build(RS,MID+1,R);
	updt(X);
}
void init(){
	scanf("%d%d",&n,&m);
	ll x;
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	build(1,1,n);
	int op,loc,l,r;
	while(m--){
		scanf("%d",&op);
		if(op==1){
			scanf("%d%lld",&loc,&x);
			chg(1,1,n,loc,x);
		}else if(op==2){
			scanf("%d%d",&l,&r);
			x=qrySm(1,1,n,l,r);
			printf("%lld\n",(qrySm2(1,1,n,l,r)-x*x%cIz*inv(r-l+1)%cIz+cIz)*inv(r-l+1)%cIz);
		}
	}
}
int main(){
	init();
	return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
/*
lt2061 最大差值 
*/
inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
int n,a[1000005],mx[1000005],mn[1000005],ans=0;
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	memset(mn,0x3f,sizeof(mn));
	for(int i=1;i<=n;++i){
		mn[i]=Min(mn[i-1],a[i]);
	}
	for(int i=n;i>=1;--i){
		mx[i]=Max(mx[i+1],a[i]); 
	}
	for(int i=1;i<=n;++i){
		ans=Max(mx[i]-mn[i],ans);
	}
	printf("%d",ans);
}
int main(){
	init();
	return 0;
}

 

lp1471 方差

大力上一个线段树。
将方差展开为由区间平方的和与区间和两项构成的多项式,然后维护区间平方的和与区间和。
具体来说,通过将二项式展开可以得到公式:
$$ \sum_{i=l}^{r}(a_{i}+k)^2=\sum_{i=l}^{r}a_{i}^2+\sum_{i=l}^{r}*k*2+(r-l+1)*k^2 $$
套用这个公式,就可以用与维护普通的线段树相似的方法来维护这个数据结构。

#include<iostream>
#include<cstdio>
using namespace std;
#define LEN (R-L+1)
#define MID ((L+R)>>1)
#define LLEN (MID-L+1)
#define RLEN (R-MID)
#define LS (X<<1)
#define RS (X<<1|1)
struct data{
	double sm;
	double sm2;
	double lzy;
}tr[270005];//262141
inline void rnw(int X,int Len,double K){
	tr[X].sm2+=(tr[X].sm*2*K+K*K*Len);
	tr[X].sm+=(K*Len);
	tr[X].lzy+=K;
}
inline void pshd(int X,int L,int R){
	rnw(LS,LLEN,tr[X].lzy);rnw(RS,RLEN,tr[X].lzy);
	tr[X].lzy=0;
}
inline void updt(int X){
	tr[X].sm2=tr[LS].sm2+tr[RS].sm2;
	tr[X].sm=tr[LS].sm+tr[RS].sm;
}
inline void add(int X,int L,int R,int A,int B,double K){
	if(L>=A&&R<=B){
		rnw(X,LEN,K);
		return;
	}
	pshd(X,L,R);
	if(A<=MID){
		add(LS,L,MID,A,B,K);
	}
	if(B>MID){
		add(RS,MID+1,R,A,B,K);
	}
	updt(X);
}
inline double qrySm(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return tr[X].sm;
	}
	pshd(X,L,R);
	double rt=0;
	if(A<=MID){
		rt+=qrySm(LS,L,MID,A,B);
	}
	if(B>MID){
		rt+=qrySm(RS,MID+1,R,A,B);
	}
	return rt;
}
inline double qrySm2(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return tr[X].sm2;
	}
	pshd(X,L,R);
	double rt=0;
	if(A<=MID){
		rt+=qrySm2(LS,L,MID,A,B);
	}
	if(B>MID){
		rt+=qrySm2(RS,MID+1,R,A,B);
	}
	return rt;
}
int n,m;
double a[100005];
inline void build(int X,int L,int R){
	if(L==R){
		tr[X].sm=a[L];
		tr[X].sm2=a[L]*a[R];
		return;
	}
	build(LS,L,MID);build(RS,MID+1,R);
	updt(X);
}
void init(){
	scanf("%d%d",&n,&m);
	double x;
	for(int i=1;i<=n;++i){
		scanf("%lf",a+i);
	}
	build(1,1,n);
	int op,l,r;
	while(m--){
		scanf("%d%d%d",&op,&l,&r);
		if(op==1){
			scanf("%lf",&x);
			add(1,1,n,l,r,x);
		}else if(op==2){
			printf("%.4lf\n",qrySm(1,1,n,l,r)/(r-l+1));
		}else{
			x=qrySm(1,1,n,l,r);
			printf("%.4lf\n",(qrySm2(1,1,n,l,r)-x*x/(r-l+1))/(r-l+1));
		}
	}
}
int main(){
	init();
	return 0;
}

 

NOIP2018 Day -1

NOIP2018 Day -1
午时已到(雾)
(话说扰乱初赛秩序竞赛一年,那“扰乱复赛秩序”是不是要禁赛三年啊?)

lp2831 NOIP2016 愤怒的小鸟

看到\(n<=18\),很容易可以想到状压\(DP\)。
最大力的做法就是,枚举原集合和转移的目的集合,然后考虑一条抛物线能否穿过其中的所有点。
但是这样的复杂度显然是不可接受的,考虑优化。
易知,三点确定一条抛物线,故而在给定\(c=0\)的时候,确定两点即可确定第三点。具体的方程组是:
$$a=\frac{x_{j}*y_{i}-x_{i}*y{j}}{x_{i}*x_{j}*(x_{i}-x_{j})}$$
$$b=\frac{y_{i}}{x_{i}}-a*x_{i}$$
从而我们可以预处理出,通过某两个点的抛物线通过的点的集合,然后对于每一个状态,选择哪两个点拓展即可。
但这个时候的时间复杂度是\(O(T*n^2*2^n)\),对于较大的数据还是很难通过的。
这时候我们可以发现,第一个选择的点是可以固定的,也就是第一个可选择的点。因为如果选择其他点开始拓展的话,到最后依然要拓展那个点。
那么就成功地将复杂度压缩到了\(O(T*n*2^n)\),这时候就可以通过了。
PS:凡是Double的题都应该注意精度。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define eps 1E-6
int n,m;
int f[1<<18],A[20][20];
double x[20],y[20];
inline int lwbt(const int &_X){
    return _X&-_X;
}
inline int Min(const int &_X,const int &_Y){
    return _X<_Y?_X:_Y;
}
inline int cnt(int _X){
    int rt=0;
    while(_X&1){
        ++rt;
        _X>>=1;
    }
    return rt;
}
void init(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;++i){
        scanf("%lf%lf",&x[i],&y[i]);
    }
    double a,b;
    for(int i=0;i<n;++i){
        for(int j=i;j<n;++j){
            if(x[i]-x[j]<=eps&&x[i]-x[j]>=-eps){
                if(!(y[i]-y[j]<=eps&&y[i]-y[j]>=-eps)){
                    A[i][j]=0;
                    continue;
                }else{
                    A[i][j]=(1<<i)|(1<<j);
                    continue;
                }
            }
            a=(x[j]*y[i]-x[i]*y[j])/(x[i]*x[j]*(x[i]-x[j]));
            b=y[i]/x[i]-a*x[i];
            A[i][j]=0;
            if(a>=-eps){
                continue;
            }
            for(int k=0;k<n;++k){
                if(a*x[k]*x[k]+b*x[k]-y[k]<=eps&&a*x[k]*x[k]+b*x[k]-y[k]>=-eps){
                    A[i][j]|=(1<<k);
                }
            }
        }
    }
    /*
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            printf("%d ",A[i][j]);
        }
        puts("");
    }
    */
    const int MAX=1<<n;
    int loc;
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    
    for(int i=0;i<MAX;++i){
        loc=cnt(i);
        for(int j=loc;j<n;++j){
            f[i|A[loc][j]]=Min(f[i|A[loc][j]],f[i]+1);
        }
    }
    printf("%d\n",f[MAX-1]);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

 

lp3605 USACO Promotion Counting晋升者计数

题意是求树上逆序对。
统计方式基本和序列逆序对相同。但是需要注意的是,由于树上逆序对需要求的是,一个节点的「子孙节点」中权值比它大的个数,故而可以求差:
具体地来说,在每一次搜索到一个节点之前,把已有的比它大的个数先记录下来,然后往下搜索。在搜索完毕之后将比它大的个数的结果减去原有的比它大的数量,这就是答案。
很容易可以知道这个增量一定是在搜索它的子孙节点的时候增加的。
记住填写的变量到底是\(X\)还是\(b_{X}\).

lp2822 NOIP2016 组合数问题

基础数论题。
首先我们知道,任何数的逆元模k,都不可能等于零。
故而我们不必考虑k是否是质数。
然后我们考虑先预处理出哪些\(n,m\)满足\(C_{n}^{m}≡0(mod\ k)\)
接着前缀和即可。
由于\(n,m\)较小,可以考虑用递推。

#include<iostream>
#include<cstdio> 
#include<cstring>
using namespace std;
int sm[2005][2005],C[2005][2005];
int n,m,k;
void prpr(){
    memset(sm,0,sizeof(sm));
    C[0][0]=C[1][1]=1;
    for(int i=1;i<=2000;++i){
        C[i][0]=1,C[i][i]=1;
    }
    for(int i=2;i<=2000;++i){
        for(int j=1;j<=i;++j){
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%k;
        }
    }
    for(int i=2;i<=2000;++i){
        for(int j=1;j<=i;++j){
            sm[i][j]=sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1];
            if(C[i][j]==0){
                ++sm[i][j];
            }
        }
        sm[i][i+1]=sm[i][i];
    }
}
void init(){
    scanf("%d%d",&n,&m);
    printf("%d\n",(m>n)?(sm[n][n]):(sm[n][m]));
}
int main(){
    int T;
    scanf("%d%d",&T,&k);
    prpr();
    while(T--){
        init();
    }
    return 0;
}