题解 P2468 【[SDOI2010]粟粟的书架】

2019-02-16

字数统计: 1.4k字 | 阅读时长: 7min

看了这道题的其他题解，本蒟蒻发现大部分都是将其分成两道题二分加主席树做的，本蒟蒻便来分享一波自己的蒟蒻做法–用主席树维护二维矩阵的信息。

这道题全程用主席树，不过要分情况讨论，对于r=1的情况，直接上裸的主席树，对于r=200，c=200的情况我们用主席树来维护矩阵(0,0)到(x,y)的信息，它由(x-1,y)到(0,0)的信息加上(x,0)到(x,y)的信息得到。代码如下

for(register int i=1;i<=r;i++)
for(register int j=1;j<=c;j++)
{
	build(1,tot,root[i-1][j],root[i][j],m[i][j],tmp[m[i][j]]);
	int tt=root[i][j];
	for(register int t=1;t<j;t++) 
	build(1,tot,tt,root[i][j],m[i][t],tmp[m[i][t]]),qu[++cnt]=tt,tt=root[i][j];
}

而对于查询，则像二维前缀和一样；

inline int ask(int l,int r,int a,int b,int c,int d,int v)
{
	if(l==r) 
	{
		int t=tr[a].size+tr[b].size-tr[c].size-tr[d].size;
		while((int)(t-1)*tmp[l]>=v) t--;
		return t;
	}
	int mid=(l+r)>>1,siz=tr[tr[a].ls].size+tr[tr[b].ls].size-tr[tr[c].ls].size-tr[tr[d].ls].size;
	int k=tr[tr[a].ls].sum+tr[tr[b].ls].sum-tr[tr[c].ls].sum-tr[tr[d].ls].sum;
	if(k>=v)    return ask(l,mid,tr[a].ls,tr[b].ls,tr[c].ls,tr[d].ls,v);
	else return ask(mid+1,r,tr[a].rs,tr[b].rs,tr[c].rs,tr[d].rs,v-k)+siz;
}

然而！这样写是过不了这道题的；

展开全文 >>

树链剖分

2019-01-04

字数统计: 4k字 | 阅读时长: 24min

P3384 【模板】树链剖分

这道是最基础的树链剖分题目。可以当做复习食用。。

其中维护字数操作：因为它是按照DSF序进行编号的，所以维护序列x到x+siz[x]-1便是维护以x为根的子树。

展开全文 >>

平衡树做题总结

2019-01-02

字数统计: 6.3k字 | 阅读时长: 36min

总结题前，先上三份平衡树代码

展开全文 >>

当小球遇上盒子

2018-11-08

字数统计: 756字 | 阅读时长: 3min

** 众所周知,小球和盒子是一对相爱相杀的好基友，他们的每一次出现都会让本蒟蒻十分痛苦。下面本蒟蒻将总结一下之前见过的类型 **

1.球相同，盒子不同，不能有空盒

这类题可以用隔板法来做，等价于在n个数,之间插入m-1个板，将其分为m组。
$ans=c_{n-1}^{m-1}$

2.球相同，盒子不同，可以有空盒

这个类型其实是上一个类型的翻版，由于隔板法不能有空盒，所以我们先在每一个盒子里放一个小球。然后就等价于将$n+m$各元素放到$m$个盒子里。
$ans=c_{n+m-1}^{m-1}$

展开全文 >>

黑科技——c++负值下标

2018-11-04

字数统计: 292字 | 阅读时长: 1min

有时我们会用vis数组来记录一些数的出现次数或是否被访问过，此时我们经常直接将这个数作为vis的下标，但对于负数怎么办呢？
F1：我们可以将负数加上一个数将其变成正数，然后储存。
那c++可不可以直接用负下标呢？其实是可以的
接下来用代码来解释这一黑科技。

展开全文 >>

哈希

2018-10-24

字数统计: 555字 | 阅读时长: 3min

哈希模板

typedef long long ll;
inline ll gethash(int *a)//a为你要哈希的数组（类型可以为char int） 
{
	ll rt=0;
	for(register int i=0;i<a.size();i++)
	{
		rt=(rt+a[i])*p%mod;//p为字符集大小，mod为模数； 
	}
	return rt; 
}

展开全文 >>

NOIp2017

2018-10-16

字数统计: 3.9k字 | 阅读时长: 22min

DAY1 T1

P3951 小凯的疑惑

题意：

对于两个互质的数$a,b$,求最小不能用$xa+yb (x>=0,y>=0)$表示的数。

题解：

不妨设$a<b$假设答案为$x$若
$x≡ma$ $mod(b)$ (1≤m≤b−1)
即
$x=ma+nb$ (1≤m≤b−1)
显然当 $n≥0$ 时 $x$可以用 $a, b$表示出来，不合题意。
因此当n=−1时$x$取得最大值，此时$x = ma - b $。
显然当$m$取得最大值$b - 1$时$x$最大，此时$x = (b - 1)a - b = ab - a - b$
因此$ a, b $所表示不出的最大的数是$ab-a-b$

展开全文 >>

树状数组总结

2018-10-10

字数统计: 2.5k字 | 阅读时长: 13min

写在前面：关于树状数组

首先，要灵活运用树状数组，必须要弄懂lowbit.
lowbit 计算的是一个数二进制的最低位。
lowbit(x)=x&-x;
这是为什么呢???
对于一个正数5，它的二进制为00000000 00000000 00000000 00000101 （longlong范围内）
它的负数的原码为 10000000 00000000 00000000 00000101 （在第64位+1）
（二进制的64位为符号位，0为正数，1为负数）
负数的二进制为它的原码的补码（除符号位按位取反后+1）
也就是11111111 11111111 11111111 11111011
所以x&-x就是x的最低位

插一幅图

展开全文 >>

搜索专题

2018-08-21

字数统计: 3.7k字 | 阅读时长: 19min

搜索专题

一.DFS

1.递归

小练手

**
输出1到n的所有排列，要求按照字典序从到
输出。**

输入

输出

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

#include<bits/stdc++.h>
using namespace  std;
int n,vis[10000000],b[10000000];
void qpl(int a,int tmp)
{
	for(int i=1;i<=n;i++)
	{
		if(tmp==n)
		{
			for(int j=1;j<=n;j++)
			cout<<b[j]<<" ";
			cout<<endl;
			return;
		}
		if(!vis[i])
		{
			vis[i]=1;
			b[a]=i;
			qpl(a+1,tmp+1);
			vis[i]=0;
		}
	}
	return;
}
int main()
{
	cin>>n;
	qpl(1,0);
	return 0; 
}

展开全文 >>

Day4

2018-08-21

字数统计: 847字 | 阅读时长: 4min

测试

1.nember

给定一个1~n的排列，每次可以对该排列进行这样的操作：
从排列中任意拿出一个数，放在该序列的最前面。
问至少经过多少次操作，可以使该排列变为1，2，3……n-1，n。

输入：

输出：

3
0

#include<bits/stdc++.h>
using namespace std;
int a[1000000];
int main()
{
	freopen("number.in","r",stdin);
	freopen("number.out","w",stdout);
	int opt;
	scanf("%d",&opt);
	int n;
	for(int i=1;i<=opt;i++)
	{
		scanf("%d",&n);
		int ans=n;
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&a[j]);
		}
		for(int j=n;j>=1;j--)
		{
			if(a[j]==n)
			{
				n--;
				ans--;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

n - 与 n 连续的最长长度就是答案。另可用next_permutation（a,a+n）来求全排列。

展开全文 >>