noip前夕的刷水记录

时间：持续1月(2018 10-11) 前言：

为准备期中考，初三快AFO的蒟蒻跟随机房神犇hjw的脚步旷掉了期中考，刷水找信心。

于是，不但中午、放学去机房，晚上也没怎么复习，QwQ。

正文：

P4779 【模板】单源最短路径（标准版） :

模板，练了下spfa堆优化

P2878 []保护花朵 the :

排序，贪心

P1186 玛丽卡 :

从最短路上枚举要删去的边。

P1113 杂务 ：

拓扑排序

题解更优做法：

简单来说，因为任务可以并发，所以一个任务如果有前驱的话，最优方案便是在它的最晚一个前驱结束后就立即开始，而且任务k的前驱节点一定小于k，所以读入时顺便从它的前驱里挑一个最大的转移即可。同时可以更新最终答案。

P1194 买礼物 :

最小生成树水题

​

P1993 小K的农场 :

差分约束（判环）

​

P1266 速度限制 :

分层最短路 / 复杂的拓扑

P1342 请柬 :

博客里有

P1491 集合位置 :

模板

P1830 轰炸III :

纯属无聊刷水

P1412 经营与开发 :

​ dp，有后效性，建议从后往前。

​ 直接贴题解好了：

​ 举个例子，第i个是资源型，我们可以搞出dpi+1的最大金钱数，钦定第i个开始选的系数为1，那么dp[i]=max(dp[i+1]/这个不选/, a[i]+dp[i+1](1-0.01k)/第i个选了，加上金钱，当前钻头能力系数变为原来的(1-0.01k)，那么后面的得到的最大金钱数也变为原来的(1-0.01k)/)

P1127 词链 :

欧拉回路

1.单词作点 可以拼在一起的单词连边。

2.先对单词排序，加边时注意顺序，使找到的第一个欧拉回路即为字典序最小的，后面直接跳出就好了。

3.dfs前初步判断一下是否有解（注意，是初步！！！） 用一些奇怪的方法

4.dfs后，若找到解则输出，否则***。（因为初步判断有解时可能将一些无解的情况放过了）

P2324 []骑士精神 :

毒瘤的bfs+hash，有点像八数码难题(模板)

P1462 通往奥格瑞玛的道路 :

二分(最大收取费用)+spfa

P1522 牛的旅行 Cow Tours :

P1346 电车 :

spfa水题

P2471 []降雨量 :

实在毒瘤 ， 博客里有写

P1816 忠诚 :

rmq模板

P1476 休息中的小呆 :

最长路并且结点个数+1

P1821 []银牛派对 Cow Party :

博客里有

P1629 邮递员送信 :

建正、反向图，跑一遍，把每个节点两次的和加起来

P1529 回家 Come Home :

水题，麻烦在输入的处理

P1656 炸铁路 :

,博客里有

P1726 上白泽慧音 :

博客里有

P2782 友好城市 :

排序后lis，但是要用nlogn的。

P2697 宝石串 :

水题，前缀和

P2872 []道路建设 Roads :

最小生成树水题。

P2434 []区间 :

博客里有

P2701 [.3]巨大的牛棚Big Barn :

博客里有

P1566 加等式 直接给洛谷题解吧：

看到这道题，我们首先注意到“找出其所有的加等式的个数”，自然地考虑运用计数DP求出若干数相加的和的个数

考虑将每个元素排序后DP处理若干数相加的和的个数

用f[i]表示

对于一个数a[i]，对于前i−1个元素选或不选的和j−a[i]，选a[i]后的和为j，则组成j−a[i]的方案数会对组成j的方案数做出大小为f[j−a[i]]的贡献，

所以枚举i,j像这样转移f[j]+=f[j−a[i]]

考虑加等式的统计：

对于一个整数集合，我们定义“加等式”如下：集合中的某一个元素可以表示成集合内其他元素之和。

对于一个数，我们已经得到它之前所有数选或不选的和等于它的方案数，为了避免漏记，考虑到对于i>j，i一定不会作为j的加等式中的元素出现，所以我们可以在输入时排序，从小到大DP，对于每个元素a[i]，统计它对答案f[a[i]]的贡献

P1929 迷之阶梯 dp

#define N 211
int a[N],n,t;
ll f[N];
int main(){io>>n;Fur(i,1,n)io>>a[i];f[1]=0;Fur(i,2,n){f[i]=1e9;if(a[i]-a[i-1]<=1)f[i]=f[i-1]+1;Fur(j,1,i-1){t=l2(a[i]-a[j]);if(j+t<=i)f[i]=MIN(f[i],f[j+t]+t+1);}}if(f[n]==1e9)f[n]=-1;io<

f[i][j]=MIN(f[i-1][j-1]+(a[i]!=b[j]),MIN(f[i-1][j],f[i][j-1])+1);

Fur(i,1,n)f[i][0]=i;
Fur(i,1,m)f[0][i]=i;

#include
using namespace std;
int main(){long long x,y,ans=0;cin>>x>>y;while(x&&y){                          //如果x,y中有一个为0，就结束了swap(x,y);                        //交换x和y，为什么？马上就知道了ans+=4*y*(x/y);              //种完剩下的所有最大的正方形。很像GCD是不是？x%=y;                             //然后x就只剩下x%y了，因为x%y

#define N 2001
#define mod (1000000007)
int n,m,f[N][N],ans=0;
int main(){cin>>n>>m;Fur(i,1,n)f[i][1]=1;Fur(i,1,m-1)Fur(j,1,n){int p=n/j;Fur(k,1,p)(f[j*k][i+1]+=f[j][i])%=mod;}Fur(i,1,n)(ans+=f[i][m])%=mod;cout<

#define N 111
int n,m,k,a[N][N],ans=0,b[N];
bool f[N][N][N];
int main(){cin>>n>>m>>k;Fur(i,1,n)Fur(j,1,m)scanf("%d",&a[i][j]),a[i][j]%=k;f[1][1][a[1][1]]=1;Fur(i,1,n)Fur(j,1,m)Fur(p,0,k-1)if(f[i][j][p]){f[i+1][j][p*a[i+1][j]%k]=1;f[i][j+1][p*a[i][j+1]%k]=1;}Fur(i,0,k-1)if(f[n][m][i])b[++ans]=i;cout<