noip前夕的刷水记录

举个例子，第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 [SCOI2005]骑士精神 :

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

P1462 通往奥格瑞玛的道路 :

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

P1522 牛的旅行 Cow Tours :

　　　floyed

P1346 电车 :

　　　spfa水题

P2471 [SCOI2007]降雨量 :

　　　实在毒瘤，博客里有写

P1816 忠诚 :

　　　rmq模板

P1476 休息中的小呆 :

　　　最长路并且结点个数+1

P1821 [USACO07FEB]银牛派对Silver Cow Party :

　　　博客里有

P1629 邮递员送信 :

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

P1529 回家 Bessie Come Home :

　　　水题，麻烦在输入的处理

P1656 炸铁路 :

　　　tarjan,博客里有

P1726 上白泽慧音 :

　　　博客里有

P2782 友好城市 :

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

P2697 宝石串 :

　　　水题，前缀和

P2872 [USACO07DEC]道路建设Building Roads :

　　　最小生成树水题。

P2434 [SDOI2005]区间 :

　　　博客里有

P2701 [USACO5.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[n];
}

不知道为什么总是wa1个点

P2758 编辑距离还是dp

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

a，b指两个字符串

记得要先初始化

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

P1444 [USACO1.3]虫洞wormhole :

　　　图论

P1649 [USACO07OCT]障碍路线Obstacle Course :

　　　bfs

P1653 猴子 :

　　　反向并茶几

P1692 部落卫队 :

　　　dfs剪枝

P4017 最大食物链计数 P3183 [HAOI2016]食物链：:

　　　双倍经验，拓扑

P1016 旅行家的预算 :

　　　贪心，贴洛谷题解吧

这道题目应该算是妥妥的贪心+模拟吧……

算法原理如下：

1.枚举途中经过的加油站，每经过一个加油站，计算一次花费；

2.在一个加油站所需要加的油，就是能够支持它到达下一个油价比它低的加油站的量；

3.如果在这个加油站即使加满油，都不能到达一个比它油价低的加油站，就把油箱加满，前往能够到达的加油站中油价最低的那个；

4.如果在这个加油站即使加满油，都不能到达任意一个加油站，也不能到达终点城市，说明无解；

第三点：为什么要加满油？因为这样可以减少在下一个加油站（价格更贵）所需要加的油量。

P1021 邮票面值设计 :

　　　还是不大能推的dp 贪心？

P1205 [USACO1.2]方块转换 Transformations :

　　　恶心模拟(在同学的怂恿下写的,虽说2次就过了,但是1个中午没了)

P1650 田忌赛马：按题意二分图

其实是dp

P3912 素数个数 :

　　　欧筛/挨筛

P3395 路障 :

　　　bfs

P3478 [POI2008]STA-Station :

　　　树形dp，洛谷换评测机后不会re了

P4086 [USACO17DEC]My Cow Ate My Homework :

　　　前缀和

P3392 涂国旗 :

　　　模拟

P2660 zzc 种田 :

　　　数论，贪心，gcd

结论就不讲了，直接搬题解：

#include<bits/stdc++.h>
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<y，所以之前需要交换
    }
    cout<<ans;
    return 0;
}

P2695 骑士的工作 :

　　　排序贪心

P2193 HXY和序列 dp

#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<<ans;
}

P3047 [USACO12FEB]附近的牛Nearby Cows树形动规

常规操作：f[i][j]表示到iii的距离为j的奶牛有多少只，但注意这只是在第二遍dfs之后

在我的第一遍dfs中(就是下面那个叫build的函数）,f[i][j]的含义是在i这课子树中到iii的距离为j的奶牛有多少只，所以在第一遍dfs的时候，f[i][j]的状态只会来自它的儿子们

于是在第一遍dfs就有一个异常简单的方程

f[i][j]=∑f[k][j−1]

其中k是i的儿子

如果我们钦定以1为根建树的话，那么1的子树就是整棵树，于是这个时候的f[1]就是全树意义下的答案了

而这个时候第二遍dfs就要登场了，第二遍dfs的意义就是利用父亲去更新儿子，于是我们就又有一个简单的方程了

f[k][j]=∑f[i][j−1]

其中k是i的儿子

这样的话肯定会有重复的，因为到iii的距离为2的点包含到kkk距离为1的k的儿子们,而这些点位于kkk的子树中的点已经在第一遍dfs的时候被加上了，于是我们在这里简单容斥就好了

P3360 偷天换日 :

　　　树形动规（访问美术馆+背包）

P1105 平台 :

　　　排序，模拟

P1208 [USACO1.3]混合牛奶 Mixing Milk:

　　　排序，贪心

P1219 八皇后 :

　　　dfs模板

P2190 小Z的车厢 :

　　　差分

P2191 小Z的情书 :

　　　模拟

P2142 高精度减法 P1480 A/B Problem P2005 A/B Problem II:

　　　人生苦短，我用Python

P2049 魔术棋子 dp

#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<<ans<<endl;
    Fur(i,1,ans)printf("%d ",b[i]);
}

P1972 [SDOI2009]HH的项链：

　　　莫队

P1833 樱花：

　　　背包，麻烦在输入处理

P1475 控制公司 Controlling Companies：

　　　dfs

　　　bfs模板题

　　　数位dp/奇技淫巧