st. from summer (持续更新&刷题记录)-白红宇

st. from summer (持续更新&刷题记录)

阅读量：5268 次

发布时间：2019-06-14

本文共 2147 字，大约阅读时间需要 7 分钟。

在金中集训的时间快要耗尽了，接着暑假和高一这一年也就走到尾声了。

这一年在oi上是很失败的，毕竟投入时间没有保证。或许让所有关注这个博客亦或是关注我的人失望了。

不想让每一次的阶段总结变成持续努力的终点。所以，这一次就让它成为起点吧。

记录一下接下来的计划吧。慢慢添加，不断填坑。

【DP】

一定要满足一个状态需要调用到的状态在它之前已经全部求出且与后面无关

线性：正/倒

环形：注意循环顺序！！！（eg能量项链2006）

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const int maxn=500; 7 int v[maxn],n; 8 int f[maxn][maxn]; 9 int main(){10     scanf("%d",&n);11     for (int i=1;i<=n;i++){12         scanf("%d",&v[i]);13         v[n+i]=v[i];14     }15     memset(f,0,sizeof(f));16     for (int i=1;i<=2*n;i++){17         f[i][i]=0;18         //f[i][i+1]=v[i]*v[i+1]*v[i+2];19     }20     for (int j=2;j<=2*n;j++){21         for (int i=j-1;i>0&&j-i

环形dp

对比（

1.起点-终点-中间点//无法满足无后效性

2.终点-起点-中间点）

【贪心】

看出是贪心？

区间单调

涉及大小比较满足无后效性

(某道模拟题)

一般是排序：Pi/Qi/Pi-Qi

枚举分割线？

【哈希】

1.映射 2.判重

字符串哈希

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define mod 10000009 6 using namespace std; 7 const int maxn=10500; 8 const int maxl=2000; 9 unsigned long long hash;10 int n,ans=0;11 char s[maxl];12 int vis[mod+50];13 int num[maxn][maxl];14 bool diff(int x,int y){15     if (num[x][0]!=num[y][0]) return 1;16     if (num[x][num[x][0]-1]!=num[y][num[y][0]-1]) return 1;17     return 0;18 }19 int main(){20     scanf("%d\n",&n);21     memset(num,0,sizeof(num));22     for (int i=1;i<=n;i++){23         scanf("%s",s);24         int m=strlen(s);25         num[i][0]=m;26         hash=1;27         for (int j=0;j