maya终于有填坑计划了

主要是最近不知道做什么题好

看到*利去年同期的刷题节奏感觉很带感的样子于是跟着进度做一做好了。虽然那种效率肯定是跟不上的

话说Silver的题好像确实都不是很难的样子反正按记录一路扫过去好了

[upd 9.11] 差不多都搞完了，刷水真是刷的人好虚。里面有的比较卡的题目要不就是比较神的贪心要不就是复杂度不科学但还是能过的题。

BZOJ1613 直接DP

BZOJ1622 我反正是乱搞，先建出一棵trie数然后每次维护一些还可以往下扩展的节点。但是复杂度算起来并不很科学，不过还是过了。

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
#define N 3050
#define M 105
queue <int> a[N],empty;
int n,m,s[N],ne[N][M],li[N],ans,len,st=1,sg[N];
char b[N],qu[N][N];

int main()
 {
 	cin >>n>>m;
 	for (int i=1;i<=n;i++)
 	  scanf("%s",qu[i]);
 	for (int i=1;i<=m;i++)
 	 {
 	 	scanf("%s",b);len=strlen(b);
 	 	for (int j=0;j<len;j++)
 	 	 if (b[j]<'a') b[j]=b[j]-'A'+'a';
 	 	int now=1;
 	 	for (int j=0;j<len;j++)
 	 	 if (!ne[now][b[j]-'a'])
 	 	   ne[now][b[j]-'a']=++st,now=st;else
 	 	   now=ne[now][b[j]-'a'];
 	 	s[now]++;
 	 }
 	for (int i=1;i<=n;i++)
 	 {
 	 	len=strlen(qu[i]);ans=0;
 	 	for (int j=0;j<len;j++)
 	 	 if (qu[i][j]<'a') qu[i][j]=qu[i][j]-'A'+'a';
 	 	for (int j=0;j<26;j++)
 	 	 {
 	 	 	a[j]=empty;
 	 	 	if (ne[1][j]) a[j].push(1);
 	 	 }
 	 	for (int j=0;j<len;j++)
 	 	 {
 	 	 	int k=qu[i][j]-'a',ss=0;
 	 	 	while (a[k].size())
 	 	 	  li[++ss]=a[k].front(),a[k].pop();
 	 	 	while (ss--)
 	 	 	 {
 	 	 	 	int l=ne[li[ss+1]][k];
 	 	 	 	for (int q=0;q<26;q++)
 	 	 	 	 if (ne[l][q])
 	 	 	 	   a[q].push(l);
 	 	 	 	ans+=s[l];
 	 	 	 }
 	 	 }
 	 	printf("%d\n",ans);
 	 }
 	return 0;
 }

BZOJ1623 一个比较显然的贪心

BZOJ1628 用个set维护下现在还存在的矩形的高度然后从左往右扫一遍就好了

BZOJ1633 也是DP

BZOJ1634 按照Di/Ti排个序就是顺序，至于证明可以考虑交换两个相邻的牛的顺序对答案的影响

BZOJ1635 Get差分序列，感觉神神的，贪心也神神的。

BZOJ1636 直接倍增搞

BZOJ1637 值化成1和-1前缀和一下然后排个序求出同一前缀和的最大区间最后倍增统计答案

BZOJ1638 两次拓扑排序

BZOJ1639 二分答案

BZOJ1640 贪心，两端不同就取小的，否则往中间一直找不同的。这样可以搞成O(n)的。有人用后缀数组真是不明觉厉，不过本质还是一样的。

BZOJ1641 Floyd

BZOJ1642 排序扫一遍

BZOJ1643 DP

BZOJ1644 BFS

BZOJ1645 刚看题还以为是扫描线，结果sort一遍扫一遍就好了

BZOJ1646 BFS

BZOJ1648 BFS

BZOJ1649 背包

BZOJ1650 二分答案+贪心

BZOJ1651 二分答案

BZOJ1652 DP

BZOJ1653 爆搜

BZOJ1654 Tarjan求LCC

BZOJ1655 高J度+DP

BZOJ1657 单调队列

BZOJ1658 贪心+差分序列

就是方向向左的路线记为1，否则记为-1，然后每段区间的权值和的绝对值*路线长度的和就是答案，脑补感觉还是比较正确

BZOJ1660 单调队列

BZOJ1661 爆搜

BZOJ1662 数位DP

BZOJ1663 DP

BZOJ1664 排序乱搞

BZOJ1665 暴力建图BFS

BZOJ1666 高J度

BZOJ1668 DP

BZOJ1669 n^2 LIS都可以过

BZOJ1671 BFS

BZOJ1672 排序后贪心

BZOJ1673 因为个数不会太多所以直接爆搜

BZOJ1674 直接建图BFS

BZOJ1676 直接爆搞

BZOJ1677 DP

BZOJ1679 排序乱搞

BZOJ1680 贪心

BZOJ1681 最短路

BZOJ1682 最小生成树

BZOJ1683 同1628

BZOJ1684 枚举分母，则分子是可以限制在一定范围内的

BZOJ1685 有个神神的贪心是每次先把大的尽可能拿掉，最后补个最小的

BZOJ1688 并查集

BZOJ1689 贪心

BZOJ2014 贪心

BZOJ2015 SPFA

BZOJ2016 二分答案

BZOJ2019 SPFA

BZOJ2020 贪心

BZOJ2021 背包

BZOJ2023 DP

BZOJ2101 DP

BZOJ2102 爆搜

BZOJ3016 往前往后扫一遍

BZOJ3017 DP

BZOJ3018 跑n^2次SPFA

BZOJ3296 并查集

BZOJ3297 DP

BZOJ3298 打表找规律发现每条y=x+k总会有一个后手必胜点，然后就可以先把这些点预处理出来最后判断就好了

BZOJ3300 栈

BZOJ3301 DP

BZOJ3389 贪心

BZOJ3390 最小生成树

BZOJ3391 树的重心

BZOJ3392 BFS

BZOJ3396 Dinic

BZOJ3399 贪心

BZOJ3400 DP

BZOJ3402 BFS

BZOJ3403 队列

BZOJ3404 预处理

BZOJ3410 贪心

BZOJ3432 二分答案

BZOJ3433 好神的贪心，是每次看能不能填右端点大的，不能就填右端点较小的。

BZOJ3479 最小生成树

BZOJ3480 预处理背包一下求出每个大小的最小值，直接从左往右扫一遍就好了

BZOJ3538 三次SPFA

BZOJ3540 前缀和+归并排序