NOIP前-小题解合集
i207M
2018-10-12 14:17:23
## 空荡荡的摊位Empty Stalls
扫两遍即可；
## BAJ-Bytecomputer
一个性质是数列最终只会变成-101；
于是$dp[i][-1,0,1]$，转移要注意，仔细讨论，不一定完全依赖上一个数字，要用f转移；
```
if(a[i]==-1)
{
f[i][0]=f[i-1][0];
f[i][1]=(a[i-1]==1?min(f[i-1][0],f[i-1][1])+1:f[0][0]);
f[i][2]=(a[i-1]==1?min(f[i-1][0],min(f[i-1][1],f[i-1][2]))+2:f[i-1][2]+2);
}
else if(a[i]==0)
{
f[i][0]=f[i-1][0]+1;
f[i][1]=min(f[i-1][0],f[i-1][1]);
f[i][2]=(a[i-1]==1?min(f[i-1][0],min(f[i-1][1],f[i-1][2]))+1:f[i-1][2]+1);
}
else if(a[i]==1)
{
f[i][0]=f[i-1][0]+2;
f[i][1]=(a[i-1]==-1?min(f[i-1][0],f[i-1][1])+1:f[i-1][0]+1);
f[i][2]=min(f[i-1][0],min(f[i-1][1],f[i-1][2]));
}
```
## 同谋者 Conspiracy
给定一张无向图，求将此图的点分成两部分，一部分形成团，另一部分形成独立集的方案数；
2-Sat求出任意一组方案；然后，所有其他方案和此方案的区别，只能是 交换了不同集合的两个点；预处理出如果一个点改变集合，那么有几个点和它冲突（冲突数>1就没用了）
分情况讨论：一个点单独过去；两个相互指的点交换；一个有一个矛盾和没有矛盾的交换；
注意去重，注意集合不能为空；
## 染色
query时注意区分左右端点
## 牛的阵容Cow Lineup
直接尺取法就行，然而我写了树状数组（线段树）求区间不同的数的个数；
## 定价
不要总想着让数字最小，可能为了5，要给这个数多一位
## 解方程
a×b=(a&b)×(a|b)在[0,31]内的解；
可以发现，只有当一个数被另一个数完全包含才可以；$\sum C^i_5 2^i$；计算完之后记得要×2再－31，因为是有序的；
科学的解释是：设a and b=x,a xor x=y,b xor x=z，则(x+y)(x+z)=x(x+y+z)，即yz=0，即a and b=a或a and b=b
## 红球蓝球
一个人摸球，有相同概率得到蓝球和红球，得到红球立即停止，得到蓝球继续摸，问期望得到的红球蓝球数量比？
1:1；红球为1；蓝球为$\sum i 2^{i+1}$，因为要在这里停止；
概率好题；
## 数位平方和
注意到最大的数才3e6左右，将hn是为一个出边，则n个点n条边，形成了基环树森林；于是可以tarjan缩点双，反向建边拓扑排序；但是有更简单的方法，直接dfs，当一个点被第三次遍历时，这个环就被覆盖两遍，递归回去时就能得到正解；
## Forest ATC 001D
特判已经联通的情况；对于其他情况，我们需要选出一共$2n-2$个点，并且每个联通块都要选至少一个；
## 假期绘画Holiday Painting
看到列数很少，对每一列维护一棵线段树即可；
## CF912E Prime Gift
看到求第k大，k还很大，一定就要二分数字大小；
现在就变成了，如何统计小于它的，由那些因数构成的数字的个数；
我们可以像某道考试题一样，将n分成两半，爆搜用这两半的质数构成的数字，然后统计答案时维护双指针扫一下；
## CF888E
折半爆搜
## 计蒜客 百度地图的实时路况
其实是一个cdq分治，但是很好写；
题意：依次求出不经过1...n的每个点，求一遍每个点对的最短路；
自己最开始想的是维护前缀后缀，然后拼在一起什么的，但是发现不行；
其实这个分治，就类似一种DFS，或者线段树一样的操作；
Floyd的本质其实就是一个DP ，其中中介点k是DP的阶段，表示已经取了[1.k][1.k]的点作为中介点 ；当然，也**可以改变枚举k的顺序，以获得想要的阶段**。
考虑分治算法。 对于区间[l,r]，分成[l,mid]和[mid+1,r]两段，利用Floyd算法，将[mid+1,r]作为中介点加入，然后往[l,mid]分治下去；另一半同理。 记得像DFS一样回溯时，要恢复原数组；
这样，当l==r时，只有1个点没有作为中介点，累计答案即可
```
LL sol(int l,int r)
{
LL res=0;
if(l==r)
{
for(ri i=1;i<=n;++i)
if(i!=l) for(ri j=1;j<=n;++j)
if(j!=l) res+=(f[i][j]>=inf?-1:f[i][j]);
return res;
}
int tmp[N][N],mid=(l+r)>>1;
memcpy(tmp,f,sizeof f);
for(ri k=mid+1;k<=r;++k)
for(ri i=1;i<=n;++i)
if(i!=k&&f[i][k]<inf) for(ri j=1;j<=n;++j)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
res+=sol(l,mid);
memcpy(f,tmp,sizeof f);
for(ri k=l;k<=mid;++k)
for(ri i=1;i<=n;++i)
if(i!=k&&f[i][k]<inf) for(ri j=1;j<=n;++j)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
res+=sol(mid+1,r);
memcpy(f,tmp,sizeof f);
return res;
}
```
## LG2651 添加括号III
根据观察，a1肯定是分子，a2肯定是分母，那么尽可能多的是a3以后的变为分子，怎么办呢？
很简单
a1/(a2/a3/a4/...)=a1a3a4.../a2
所以我们只要确认a1a3a4.../a2是否是整数。
## 牛的照片Cow Photographs
看似是用树状数组动态求逆序对，实际上分析一下，维护一些数组就可以；
## [六省联考2017]期末考试
数据范围较小，可以直接枚举暴力；但是，更优雅的做法是发现一个单谷函数，然后三分法；
每次把一个数放在最后等于把它+n；
## [POI2006]PRO-Professor Szu
先Tarjan判强联通分量，然后拓扑排序；
这道题很坑啊，有很多地方需要注意：
1.最大值的限制；2.自环要把所在块设为有环；3.设为正无穷之前先看有没有方案；
## PUS
线段树优化建图+拓扑排序；注意数字的上下界限制；
## BZOJ2131免费的馅饼
可以拆开绝对值得到两个式子，然后？？？上高级数据结构？并不是；
首先发现这两个条件一定会同时被满足；如果这两个条件同时被满足，根据**同向可加性**，一定满足$t_j<=t_i$，这也解决了我一直的疑问；
## 基因匹配
看到位置只有5个，枚举；
## 航线规划
找出一棵以时间排序的最大生成树；对于一条非树边，它的作用就是把链赋值为0；
SB错误：建边没建双向边；线段树开小了；
## [Jsoi2015]salesman
比较水的树形DP，就是统计解数那里出问题了；
应该是：选择的数字有多解，选择的最后一个数字有多个，或者有0，就是多解；
但其实数据还有待加强：1.根节点要和0特判一下；2.如果有两个小数字可以代替一个大数字，理论上也是多解；
## Censoring 审查
字符串花式题；做法多种多样：KMP+链表/并查集、AC自动机+栈、Hash；
## [POI2017]Sab
BZOJ怎么T了，不管了，钉子上A了；
二分mid，树形DP判定，记得清空数组；
## POI2017Kontenery (kon)
给定数组，每次操作每隔d个+k，问最终数列；
对d分块，大的暴力，小的差分一下；
## 成绩调研
这⼀次的考试，学⽣的成绩分为k等，成绩单上按照学⽣的学号排序。此外，学校要抽⼀些同学的考卷去调研，⽯神将这个任务委派给了你。 抽取的样本有如下要求：
学号连续的学⽣
得到1等的学⽣数量在[l_1,r_1]区间内
得到2等的学⽣数量在[l_2,r_2]区间内
…
现在请问有多少种抽取样本的⽅法。
这道题有单调性，可以双指针做，但是有更好的方法：对每个k考虑，然后把区间取一个交集就好；处理出每个点的等级的左右边界，然后左端点和上一个点的左端点，自己的限制取max；右端点同理取min；
## [HNOI/AHOI2018]道路
可能是普及组的树形DP：暴力状态$f[i][j][k]$表示考虑完i的子树，向上有j条旧公路k条旧铁路的最小代价；
## CF859E
有 m 个人，n 张椅子，第 i 个人只能坐在第 ui 或第 vi 张椅子上。求有多少种方案满足没有人坐在同一张椅子上。
把椅子作为点，人作为边，变成一个图。
每个连通块可以分开考虑。
假设某个连通块中有 v 个点，e 条边，由于连通，有 v − 1 ≤ e，并且若 e > v 则无解，所以 e 只有 v − 1 和 v 两种取值。
假如 e = v − 1，那么该连通块有 v 种方案：考虑枚举每个点不放的情况，其他的点都可以唯一确定。
假如 e = v 且环长 > 1，那么该连通块有 2 种方案：考虑环上的一条边，这条边的放法确定后其他的都可以唯一确定。
## [SCOI2012]滑雪
特殊的最小生成树，先按高度排序，再按距离排序；
为什么？转移的过程中，只能从高度高的向高度低的转移。所以我们对于所有可以拓展的点，先拓展高度更高的，最终答案不会更劣。
## POI2012-ROZ
贪心的每次选择最大的斐波那契数；
## [POI2015]PIE
~~真的是睿智了~~
时间复杂度感觉不对，原来是想的不够机智；
对印章，求出每个黑点的相对最左上的黑点的位置，这样染色的话，一个黑点只会被遍历一次！
## [SCOI2005]栅栏
记录浪费了多少和前缀和，这个剪枝超快；