Posted 02-05-2020Inspiring Learning / Competitive Programming

基于线性回归的传染趋势预测

— 空 —

这个春节对于每个国人来说，都是一个不一样的春节。各大旅游景点空了，货架上的口罩品类空了，正月的拜年日程空了，城市空了，人心却没有空。全世界都在为武汉加油，为中国加油。

— 数字 —

2月4日0—24时，31个省（自治区、直辖市）和新疆生产建设兵团报告新增确诊病例3887例（湖北省3156例），新增重症病例431例（湖北省377例），新增死亡病例65例（湖北省65例），新增治愈出院病例262例（湖北省125例），新增疑似病例3971例（湖北省1957例）。
　　截至2月4日24时，国家卫生健康委收到31个省（自治区、直辖市）和新疆生产建设兵团累计报告确诊病例24324例（海南省核减1例），现有重症病例3219例，累计死亡病例490例，累计治愈出院病例892例（海南省、湖北省各核减1例），现有疑似病例23260例。
　　目前累计追踪到密切接触者252154人，当日解除医学观察18457人，现有185555人正在接受医学观察。
　　累计收到港澳台地区通报确诊病例39例：香港特别行政区18例（死亡1例），澳门特别行政区10例，台湾地区11例。
——援引自国家卫生健康委员会官方网站

24小时实时更新的数字背后，是对患病者的祈祷，是对康复者的祝福，是对离世者的哀悼，更是对无私奉献的医护人员和支援企业及个人的敬礼。

Posted 02-01-2020Inspiring Learning / Competitive Programming

Matrix Linear Regression

人工智能第二讲

矩阵形式的线性回归

x_11表示第一个样本的第一个值

T: 转制，横竖向量转换

二范数就是各个数的平方和

伪逆矩阵

KNN分类算法

严重依赖于特征

图像数据处理基础

Posted 12-19-2019Inspiring Learning / Competitive Programming

ACSL Diff

import java.util.Scanner;

public class Diff {
    static String s1,s2;
    static String[] word1;
    static String[] word2;

    static void input() {
        Scanner input = new Scanner(System.in);
        s1 = input.nextLine();
        s2 = input.nextLine();
        int len1 = s1.length();
        int len2 = s2.length();
    
        // for(int i=0;i<word1.length;i++) System.out.println(word1[i]);
    }
    
    static String process(String A, String B)
    {
        String common="";
        word1 = A.split(" ");
        word2 = B.split(" ");
        int len1 = word1.length;
        int len2 = word2.length;
        for(int i=0;i<len1;i++)
        {
            for(int j=0;j<len2;j++)
            {
                int pos = word2[j].indexOf(word1[i]);
                if(pos!=-1)
                {
                    word2[j] = word2[j].substring(0,pos) + word2[j].substring(pos+word1[i].length());
                    common = common + word1[i];
                    break;
                }
            }
        }
        return common;
    }
    
    static String declan(String c1, String c2)
    {
        String ans="";
        int len1 = c1.length();
        for(int i=0;i<len1;i++)
        {
            String tmp  = c1.substring(i, i+1);
    
            int pos = c2.indexOf(tmp);
            if(pos==-1) continue;
            ans = ans + tmp;
    
            c2 = c2.substring(pos+1);
        }
        return (ans=="")?("NONE"):(ans);
    }
    
    public static void main(String[] args)
    {
        for(int i=0;i<5;i++)
        {
            System.out.println("Please enter No."+(i+1)+" line of the input data:");
            input();
            String common1 = process(s1,s2);
            String common2 = process(s2,s1);
            System.out.println("The answer to No."+(i+1)+"line is:");
            System.out.println(declan(common1,common2));
            // System.out.println(common1);
            // System.out.println(common2);
        }
        System.out.println("All output done...");
        System.out.println("Thanks for your testing");
        
        // return;
    }
}
/*
The quick brown fox did jump over a log
The brown rabbit quickly did outjump the fox
How much wood would a woodchuck chuck if a woodchuck could
chuck wood He would chuck as much wood as a woodchuck could
I scream you scream we all scream for ice cream
He screams she screams they all scream for a creamery
A skunk sat on a stump and thunk the stump stunk
but the stump thunk the skunk stunk
I have got a date at a quarter to eight
I will see you at the gate so do not be late

abc defgh ijkl mnopq rstuv wxyz
ab cdefgh ijklmn opq rst uv w xy z
*/

Posted 12-12-2019Inspiring Learning / Competitive Programming

Digital Reassembly

import java.util.Scanner;
public class digitReassembly {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        
        String s1 = input.next();
        String s2 = input.next();

        input.close();

        int num = Integer.valueOf(s2);

        while(s1.length()%num!=0)
        {
            s1 = s1 + "0";
        }

        int ans = 0;
        int cnt = s1.length()/num;
        int p = 0;
        for(int i=0;i<cnt;i++)
        {
            ans += Integer.valueOf(s1.substring(p,p+num));
            p = p+num;
        }

        System.out.println(ans);
    }
}

Posted 12-12-2019Inspiring Learning / Competitive Programming

ACSL CHMOD

import java.util.Scanner;

public class CHMOD
{
    static String[] num = new String[4];
    public static void input()
    {
        Scanner input = new Scanner(System.in);
        String s = input.next();
        int len = s.length();
        int cnt = 0;
        num[cnt++] = s.substring(0, 1);
        for(int i=1;i<len;i++)
        {
            if(s.charAt(i)>='0' && s.charAt(i)<='9')
            {
                num[cnt++] = Integer.toBinaryString(s.charAt(i)-'0');
            }
        }
        input.close();
    }

    public static void process()
    {
        String[] ans = new String[]{"","","",""};
        for(int i=1;i<4;i++)
        {
            while(num[i].length()<3) num[i] = '0' + num[i];
            if(num[i].charAt(0) == '1') ans[i] += 'r'; else ans[i] += '-';
            if(num[i].charAt(1) == '1') ans[i] += 'w'; else ans[i] += '-';
            if(num[i].charAt(2) == '1') ans[i] += 'x'; else ans[i] += '-';
        }
        
        boolean flag1,flag2,flag3;
        flag1 = flag2 = flag3 = false;

        if(num[0].charAt(0)=='1' && ans[1].charAt(2)=='x') flag1 = true;
        if(num[0].charAt(0)=='2' && ans[2].charAt(2)=='x') flag2 = true;
        if(num[0].charAt(0)=='4' && ans[3].charAt(2)=='x') flag3 = true;
        
        for(int i=1;i<4;i++)
        {
            System.out.print(num[i]+" ");
        }
        System.out.print("and ");

        
        if(ans[1].charAt(2)=='x' && flag1 == true)
        {
            System.out.print( ans[1].charAt(0) );
            System.out.print( ans[1].charAt(1) );
            System.out.print("s");
        }
        else System.out.print(ans[1]+" ");

        if(ans[2].charAt(2)=='x' && flag2 == true)
        {
            System.out.print( ans[2].charAt(0) );
            System.out.print( ans[2].charAt(1) );
            System.out.print("s");
        }
        else System.out.print(ans[2]+" ");

        if(ans[3].charAt(2)=='x' && flag3 == true)
        {
            System.out.print( ans[3].charAt(0) );
            System.out.print( ans[3].charAt(1) );
            System.out.print("t");
        }
        else System.out.print(ans[3]);

        
    }

    
    public static void main(String[] args)
    {
        input();
        process();
    }
}

/*
0,5,2,6
1,7,3,0
2,4,1,5
4,2,3,4
4,5,6,7

*/

Posted 12-01-2019Inspiring Learning / Competitive Programming

ACSL STRING

Question

My thought

Nothing… The problem is pretty easy, however it troubled me for a quite long time. Just follow the instruction of the problem and simulate the whole process by coding.

Points to note

The conversion between String and int
How to handle carry
Pay attention to the additional sign
Sometimes we can use char to simplify the process

Code

Posted 10-24-2019 Declan Inspiring Learning / Competitive Programming

Data Structure

ArrayList

// the data type must be a type of class
ArrayList<String>  a = new ArrayList<String>();
ArrayList<Integer> b = new ArrayList<Integer>();

// the size of the ArrayList
arrayList.size();

// add data to the ArrayList
arrayList.add("DATA");

// replace data by returning the value of the replaced data
arrayList.set();

// remove data by returning the value of the removed data
arratList.remove();

How to traverse the ArrayList

Posted 01-29-2019Inspiring Learning / Competitive Programming

济南Day3 坐标型动态规划及背包

花店橱窗布置

思路

f[i][j]f[i][j]表示前i个花瓶前j个花束的最大美学价值
f[i][j]=max(f[i−1][k],f[i][j])f[i][j]=max(f[i−1][k],f[i][j])

当然还有另外一种思路(*太强了！！！*)：

整张表都是向右下方走的，向下走加上数值，向右走无影响
如果向下走代表花束放入花瓶，向右走无影响代表不放入

int f[N][N],mp[N][N];
for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
        f[i][j]=max(f[i-1][j]+mp[i][j],f[i][j-1]);

矩阵取数

思路

因为每次取头和尾，所以一定是一个连续的区间
f[i][j]f[i][j]表示从i取到j的最大得分
$f[i][j]=max(f[i][j-1]+a[j]*2^(i-1+n-j+1+1) \ , \ f[i-1][j]+a[i]*2^(i-1+n-j+1+1))$
指数是轮数，当前数前面有多少个数被取走，就有多少轮，注意一下1的问题

传纸条

思路

f[i][j][k][l]f[i][j][k][l]表示现在去的到了(i,j),回来的到了(k,l)
一共有四种情况，上上，左左，上左，左上
保证两条路径不相交if(j1==j2 && i1==i2) continue
f[i][j][k][l]=max(f[i−1][j][k−1])f[i][j][k][l]=max(f[i−1][j][k−1])
步数为i+j−1i+j−1

判断不合法的状态

1 2	if(i1+j1!=i2+j2) continue; if(i1==i2 && j1==j2 && i1+j1!=2 && i1+j1!=m+n) f[i1][j1][i2][j2]=-0x3f3f3f3f;

当m,n<100m,n<100时，四维数组开不下了，因为i1+j1=i2+j2i1+j1=i2+j2的时候才是合法的，并且三个数都确定时，我们可以直接算出j2j2,直接变成了三维

免费馅饼

题目

地面长度为L，高度为H，天上掉馅饼

人在地上每单位时间可以向左或向右移动0~2格，馅饼每单位时间掉落一格

求最多接到多少馅饼（馅饼有分值）

思路

f[i][j]f[i][j]表示第i秒到达第j个格子的最大得分
该状态是从哪里转移过来的呢？他可以从5个地方转移过来（没有到边界的时候）
运动具有相对性，我们可以把该问题类比成数字三角形，相当于馅饼不动，人每次向上移动一个单位
f[i][j]=ff[i][j]=f

三角蛋糕

思路

像数字三角形一样压缩成正三角形
f[i][j]=min(f[i+1][j],f[i+1][j+1])+1f[i][j]=min(f[i+1][j],f[i+1][j+1])+1

金明的预算方案

思路：分组背包

f[i][j]f[i][j]表示前i组物品重量不超过j的最大价值
一共5种转移方式
f[i][j]=max(f[i−1][j],f[i−1][j−w[i][k]]+v[i][k]),k=1,2,3,4,5f[i][j]=max(f[i−1][j],f[i−1][j−w[i][k]]+v[i][k]),k=1,2,3,4,5,五种情况已经重新配置的前提下

01/完全背包混合

根据物品的类型选择状态转移方程

二维限制的背包

把数组扩展成三维
f[i][j][k]=max(f[i−1][j][k],f[i−1][j−w[i]][k−v[i]]+c[i])f[i][j][k]=max(f[i−1][j][k],f[i−1][j−w[i]][k−v[i]]+c[i])

面包

题目

有N种面包，每种面包数量无限多，有高度和价值，高度是5的倍数
将面包叠成一个面包塔，高度不得超过T
给定常数k，若一个面包高度>=k，则它下面所有面包都会被压扁
一个面包最多被压扁一次，它的高度变为原来的4/5
求最大的价值

思路

如果没有面包被压扁，就是一个完全背包问题
如果有大面包，肯定要放到最上面，使得压缩高度尽可能大
枚举最上面是哪一个大面包，然后其余所有面包的高度都变为原来的五分之四，就转化成了一半的完全背包问题

Posted 01-29-2019Inspiring Learning / Competitive Programming

高精度模板

define N 1e5
struct bign
{
    int len;
    int v[N];
    
 	// 赋值 bign=bign
    bign operator = (char* s)
    {
        len=strlen(s);
        memset(v,0,sizeof(v));
        for(int i=0;i<len;i++)
        	v[i]=s[len-i-1]-'0';
        return *this;
    }
    //赋值 bign=int
    bign operator = (int x)
    {
        char s[N];
        sprintf(s,"%d",x);
        return *this=s;
	}
    
    // 高精加
  	bign operator + (const bign &b) const
    {
        bign c;
        memset(c.v,0,sizeof(c.v));
        c.len=max(len,b.len);
    	for(int i=0;i<c.len;i++)
            c.v[i]=v[i]+b.v[i];
        for(int i=0;i<c.len;i++)
        {
            c.v[i+1]+=c.v[i]/10;
            c.v[i]%=10;
		}
        if(c.v[c.len]) c.len++;
        return c;
	}
    // 高精乘
    bign operator * (const bign &b) const
    {
        bign c;
        memset(c.v,0,sizeof(c.v));
        c.len=len+b.len;
        for(int i=0;i<len;i++)
        	for(int j=0;j<b.len;j++)
                c.v[i+j]+=v[i]*b.v[j];
        for(int i=0;i<len;i++)
        {
            c.v[i+1]=c.v[i]/10;
            c.v[i]%=10;
		}
        while(c.len>1 && c.v[c.len-1]) c.len--;
      	return c;
	}
    // 高精加等于
    bign operator += (const bign &b)
    {
        return *this+b;
    }
    
    // 比大小
    bool operator < (const bign &b) const
    {
        if(len<b.len) return 1;
        if(len>b.len) return 0;
        for(int i=len-1;i>=0;i--)
        {
            if(v[i]<b.v[i]) return 1;
        	if(v[i]>b.v[i]) return 0;
        }
        return 0;//两个数相等返回flase
    }
    
    bool operator > (const bign &b) const
    {
        return b<*this;
	}
    
    bool operator <= (const bign &b) const
    {
        return !(b>*this);
	}
    
    bool operator >= (const bign &b) const
    {
        return !(b<*this);
	}
    
    bool operator == (const bign &b) const
    {
        return (b>*this)^(b<*this)
	}
};

Posted 01-29-2019Inspiring Learning / Competitive Programming

树形DP

二叉苹果树

思路

$dp[u][j表示节点u留下j条边的最大价值，每一次决策只有三种情况：剪左子树，剪右子树，两个都不剪
剪左边：dp[u][j]=dp[rson][j−1]+v[rson]dp[u][j]=dp[rson][j−1]+v[rson]，同理，剪右边：dp[u][j]=dp[lson][j−1]+v[lson]dp[u][j]=dp[lson][j−1]+v[lson]
两边都不剪：dp[u][j]=dp[lson][j]+dp[rson][k−j−2]dp[u][j]=dp[lson][j]+dp[rson][k−j−2]

代码：记忆化搜索

int f[N][N];
bool t[N][N];
int dp(int u,int k)
{
    if(t[u][k]) return f[u][k];
	t[u][k]=1;
    if(!k) return f[u][k]=0;
    int tmp1=dp(lson[u],k-1)+v[sonl[u]];
    int tmp2=dp(rson[u],k-1)+v[sonr[u]];
    int tmp3=0;
    for(int l=0;l<k-2;l++)
        tmp3=max(tmp3,dp(lson[u],l)+dp(rson[u],k-l-2));
   	return f[u][k]=max(tmp1,max(tmp2,tmp3+lson[u]+rson[u]));
}

先修课

题目

课的先修关系形成一棵树的结构，每门课有一门或者没有先修课。选M门课，能获得的最大学分是多少？

思路

dp[u][j]dp[u][j]以u为根的子树选j门课
把j-1门课分配给子树，就是一个背包？
然后我们用f[i][j]f[i][j]表示当前树中，前i棵子树选择j门课的最大学分。这样就能够通过f算出dp[i][j]dp[i][j],相当于树上DP套背包。对于每一个状态dp[i][j]dp[i][j]都需要用f算出学分分配的最佳方案

K-set

题目

在一棵树中选出最多的点，使得这些点中每个点最多与其他点连了k条边

思路

dp[u][0/1][0/1]dp[u][0/1][0/1]表示以u为父亲，取/不取父亲,取/不取自己的最大值
dp[u][0][0]dp[u][0][0]：自己和父亲都不取，u的儿子随便取。$f[u][0][0]=size∑i=1max( dp(vi,0,0) , dp(vi,0,1) )f[u][0][0]=∑i=1sizemax( dp(vi,0,0) , dp(vi,0,1) )$
dp[u][1][0]dp[u][1][0]：父亲要取，u自己不取，u的儿子同样随便取。f[u][1][0]=f[u][0][0]f[u][1][0]=f[u][0][0]
dp[u][1][1]dp[u][1][1]

：父亲要取，自己也要取，儿子取k-1条边。
- 这时我们就要考虑取哪几条边，也就是哪几个点。
- 对于任意一个u的儿子vivi,如果取这个点，那么它的贡献就是dp(vi,1,1)dp(vi,1,1)，如果不取这个点，那么它的贡献就是dp(vi,1,0)dp(vi,1,0)
- 因此这个点取或者不取，带来的贡献就是两种情况的差，所以我们只要按两种情况的差从大到小排序就好了。最后选取差值最大的k-1个点就OK了（前提是这k-1个点带来的贡献都是正的，如果有负贡献那么就取不满k-1个点）
dp[u][0][1]dp[u][0][1]：父亲不取，自己要取，儿子取k条边

Posted 01-15-2019Inspiring Learning / Competitive Programming

随机数基本使用方法

基本公式：

要取得[a,b)的随机整数，使用(rand() % (b-a))+ a;
要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a;
要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1;
通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。
要取得a到b之间的随机整数，另一种表示：a + (int)b * rand() / (RAND_MAX + 1)。
要取得0～1之间的浮点数，可以使用rand() / double(RAND_MAX)。

Posted 01-11-2019Inspiring Learning / Competitive Programming

四子连棋

这是我到目前为止写过最长的代码之一……

题意

4*4的棋盘，一共有三种属性：白棋，黑棋，空格（有且仅有两个），每一次可以移动一颗棋子，黑白棋交替进行，只能移到空格的地方。求达成四子连棋局面（横竖斜都算）所需的最小步数

分析

广搜，和八数码问题差不多，但是更繁琐了。
黑白棋交替进行，那么我们需要在搜索的时候除了当前地图和步数还需要保存当前该哪一方行棋
广搜要搜两遍，分别是黑棋先走或白棋先走
每一次需要考虑两个空格，所以从两个当前点搜状态

遇到的坑

很多都是重复的代码，只要细心就好了，但有一个*最坑的……*
黑棋先走和白棋先走走到的棋局相同的情况也是两种情况，不能判重删去！！！

Posted 01-11-2019Inspiring Learning / Competitive Programming

STL

C++ STL 之所以得到广泛的赞誉，也被很多人使用，不只是提供了像vector, string, list等方便的容器，更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组，list封装了链表，map和set封装了二叉树等，在封装这些数据结构的时候，STL按照程序员的使用习惯，以成员函数方式提供的常用操作，如：插入、排序、删除、查找等。让用户在STL使用过程中，并不会感到陌生。

迭代器

1 2	set<int>::iterator it_set//一个set<int>类型的迭代器 map<string,int>::iterator it_map//一个map<string,int>类型的迭代器

SET

set的各成员函数列表

begin()–返回指向第一个元素的迭代器
clear()–清除所有元素
count()–返回某个值元素的个数
empty()–如果集合为空，返回true
end()–返回指向最后一个元素的迭代器
equal_range()–返回集合中与给定值相等的上下限的两个迭代器
erase()–删除集合中的元素
find()–返回一个指向被查找到元素的迭代器
get_allocator()–返回集合的分配器
insert()–在集合中插入元素
lower_bound()–返回指向大于（或等于）某值的第一个元素的迭代器
key_comp()–返回一个用于元素间值比较的函数
max_size()–返回集合能容纳的元素的最大限值
rbegin()–返回指向集合中最后一个元素的反向迭代器
rend()–返回指向集合中第一个元素的反向迭代器
size()–集合中元素的数目
swap()–交换两个集合变量
upper_bound()–返回大于某个值元素的迭代器
value_comp()–返回一个用于比较元素间的值的函数

#include <iostream>
#include <cstdio>
#include <set>

using namespace std;
set<int> s;
set<int>::iterator it_set;

int main()
{
	int n;
	scanf("%d",&n);
	while(n--)
	{
		int tmp;
		scanf("%d",&tmp);
		s.insert(tmp);
	}
	for(it_set=s.begin();it_set!=s.end();it_set++)
	{
		printf("%d\n",*it_set);
	}
	return 0;
}

链接

容器set和multiset

Posted 01-05-2019Inspiring Learning / Competitive Programming

三角形牧场

P1284三角形牧场

题意

现在有n段木棍，全部使用组成三角形的三条边，使三角形的面积最大

分析

首先看数据范围，边长最大为40*40/3，并且因为要使用所有的木棍，所以只要两条边确定就可以知道第三条边的确定长度。因此我们可以设状态f[i][j]表示三角形的两条边分别是i，j的情况是否成立
f[i][j]=f[i−a[k]][j] || f[i][j−a[k]] || f[i][j]f[i][j]=f[i−a[k]][j] || f[i][j−a[k]] || f[i][j]，相当于01背包，就不解释了……
定义初始状态f[0][0]=1f[0][0]=1
三条边都知道了，如何求面积呢？这里我们需要用到海伦公式

S=√p(p−a)(p−b)(p−c)S=p(p−a)(p−b)(p−c)，p=12(a+b+c)p=12(a+b+c)

遇到的坑

~~好像没有什么~~

P1929 迷之阶梯

~~真的好坑，做了一下午……~~

题意

登上阶梯必须要按照它要求的方法，否则就无法登上阶梯。它要求的方法有以下三个限制：

如果下一步阶梯的高度只比当前阶梯高 1，则可以直接登上。

除了第一步阶梯外，都可以从当前阶梯退到前一步阶梯。

当你连续退下 k 后，你可以一次跳上不超过当前阶梯高度 2^{k}2k的阶梯。比如说你现在位于第 j 步阶梯，并且是从第 j+k 步阶梯退下来的，那么你可以跳到高度不超过当前阶梯高度+2^{k}2k的任何一步阶梯。跳跃这一次只算一次移动。

开始时我们在第一步阶梯，由于时间紧迫，我们需要用最少的移动次数登上迷之阶梯。请你计算出最少的移动步数。

分析

定义状态为f[i]表示到第i个阶梯的最小步数
由2可以直接得出if(h[i]==h[i-1]+1) f[i]=f[i-1]+1

遇到的坑

if(f[n]>=0x3f3f3f3f) f[n]=-1;在状态转移的过程中有可能比初始值更大，所以是大于等于

Posted 12-31-2018Inspiring Learning / Competitive Programming

动态规划习题2

P1970 花匠

分析

第一次很容易就能想到转移方程：
1
2
if(a[i]>a[i+1] && a[i]>a[i-1]) f[i]=f[i-1]+1;
else if(a[i]<a[i+1] && a[i]<a[i-1]) f[i]=f[i-1]+1;
但是这样做有一个很大的问题，无法确定最后一个状态的转移是否合法。

然后我就想找到最后一个状态是从哪里转移过来的，最后再额外判断一遍。~~虽然有点不像动态规划~~，只要用last1，last2两个变量储存倒数第二个和第三个留下的点，但还是WA了2个点。

原因好像是我丢掉了一些状态：我默认了只要这棵花能选就选，不满足无后效性
动态规划
正解：一维无法解决问题，那么就升一维。

定义状态为f[i][j]表示第i个花处在上升或下降序列中能选的最多的花数

状态转移方程为
1
2
3
4
if(a[i]<a[i+1] && a[i]<a[i-1]) f[i][0]=f[i-1][1]+1;
else f[i][0]=f[i-1][0];
if(a[i]>a[i+1] && a[i]>a[i-1]) f[i][1]=f[i-1][0]+1;
else f[i][1]=f[i-1][1];
贪心
*为了方便我们设当前的花为A，下一盆花为B*
- 第一盆花肯定要选，如果不选的话第二盆就成了第一盆，花的总数就会减少，一定不会比选第一盆花更优
- 如果B比A还高，那么一定会选择B，因为落差的区间变大了，能够容纳的合法的花也变多了；同理，如果B比A还小，那么一定会选择B
- 通过以上两个判断不停地找波峰和波谷，记录答案就可以了

P1020 导弹拦截

*非常恶心的一道题，我已经被搞晕了*

分析

第一问就是求最长不上升子序列，想象有一个栈，如果当前数小于等于栈顶的数，则直接入栈；否则二分查找栈内第一个大于等于当前数的数并替换它，因为与当前数相等的数是有贡献的
第二问就是求最长上升子序列，~~我不会证明，只能大概的胡诌~~，因为相当于我只关心子序列的长度，而只要有一个高度大于当前长度，就必须去新建一个序列，有点类似于木桶原理……

遇到的坑

最长不下降子序列等价于倒序的最长不上升子序列
最长下降子序列等价于倒序的最长上升子序列
lower_bound 二分查找第一个大于等于基准数的数（涵盖的范围更广）
upper_bound 二分查找第一个大于基准数的数

P1103 书本整理

~~*很有感触的一道题*~~

分析

可以抽象为：给定一串数列，首先对数列进行排序，然后从数列中删除K个数使得整个数列每相邻两个数的差的绝对值的和最小，输出最小的和，即最小不整齐度。~~好拗口~~
f[i][j]表示长度为j的数列，数列最后一个的位置标号为j
假设当前状态数列长度为j，现在以第i位为数列的最后一个，即最后一个肯定留下的最小不整齐度。因为这一位肯定要保留，所以状态肯定是从j-1转移过来的。其次我们就要枚举数列长度为j-1时，数列最后一个保留的数到底是多少，由此我们可以计算出应该增加的不整齐度

转移方程：

1	f[i][j]=min(f[t][j-1]+abs(a[i]-a[t]),f[i][j]);//最后一个保留a[i],数列长度为j的最小不整洁度

接下来考虑边界问题
- j<=i 序列里的数肯定不会超过所有当前的数
- t>=j-1 由上式同理可以得出，状态中的第一维度肯定大于等于第二维度
- t<i 数列里的最后一个数肯定不可能达到现在及以后的数
- j<=n-K 由题意可得……
~~分析最清晰的一回~~

遇到的坑

f[n][n-k]并不是最终答案！！！只要状态里最后一个位置编号大于n-K，并且序列里有n-K个数，就有可能成为答案，所以我们要扫一遍找到最终答案
赋初值！！！ 因为我们状态转移选择的是最小值，最开始所有状态都是0，无论怎么转移都是0。所以我们把所有初值赋值为无穷大？显然不可行。我们可以每当需要转移该状态时，在确定该状态一定会被改变的前提下提前赋值为无穷大****
真的都是很深很深的坑

AC代码

//与前文所使用的变量名有所不同
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int N=110;
struct ty
{
    int h,w;
};
ty b[N];
int n,K,f[N][N];//是否保留 

bool operator < (const ty &a,const ty &b)
{
    return a.h<b.h;
}

int main()
{
    scanf("%d%d",&n,&K);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&b[i].h,&b[i].w);
    
    K=n-K;
    sort(b+1,b+n+1);
    
    //第i个数保留j个的最小整齐度,序列的最后一个数序号为i 
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=K&&j<=i;j++)
        {
            if(j==1) continue;
            f[i][j]=0x3f3f3f3f;
            for(int t=j-1;t<i;t++)
            {
                f[i][j]=min(f[t][j-1]+abs(b[i].w-b[t].w),f[i][j]);
            }
//			printf("f[%d][%d]=%d\n",i,j,f[i][j]);
        }
    }
    
    int ans=0x3f3f3f3f;
    for(int i=K;i<=n;i++)
        ans=min(ans,f[i][K]);
    printf("%d\n",ans);
    return 0;
}

Posted 12-31-2018Inspiring Learning / Competitive Programming

P1429 平面最近点对（加强版）

题目

题目描述
给定平面上n个点，找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的

输入输出格式
输入格式：
第一行：n；2≤n≤200000

接下来n行：每行两个实数：x y，表示一个点的行坐标和列坐标，中间用一个空格隔开。

输出格式：
仅一行，一个实数，表示最短距离，精确到小数点后面4位。

输入输出样例
输入样例#1：
3
1 1
1 2
2 2
输出样例#1：
1.0000

思路

首先考虑暴力，枚举所有点对，复杂度为O(N^2)
然后就是正解：

分治算法
- 每一次把平面分成两个部分，找出左边的最近点对，右边的最近点对以及穿越分割线的最近点对。
- 在求穿越分割线的最近点对时，用左右已经算出的最小值作为参考，一旦大于就停止搜索

Posted 12-15-2018Inspiring Learning / Competitive Programming

动态规划2-背包DP

装箱问题

有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入描述：一个整数v，表示箱子容量；一个整数n，表示有n个物品；接下来n个整数，分别表示这n 个物品的各自体积
输出描述：一个整数，表示箱子剩余空间。
样例输入: 24 6
8 3 12 7 9 7
样例输出：0

状态：f[i][j]表示前i个物品能否装满j的体积

for(int i=1;i<=n;i++)
for(int j=1;j<=v;j++)
    f[i][j]=f[i-1][j] || f[i-1][j-v[i]];
for(int i=v;i>0;i++)
    if(f[n][i]) printf("%d",v-i);

优化

01滚动
f[i][j]中每一次的状态转移只与上一行有关系，所以只需要一个2层的数组，可以用&1实现
就地滚动
每一次都会由左边的值转移到现在，所以每一次只要将循环从右往左就可以了

01背包

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

##方法1：动态规划
状态：还是一样，每一个背包只有选或者不选两种决策，这道题多了一个条件，相当于状态多了一个维度
转移方程：f[i][j][k]=f[i-1][j][k]||f[i-1][j-v[i]][k-c[i]]
*i维度可以01滚动*

Posted 12-15-2018Inspiring Learning / Competitive Programming

动态规划1

笔记

最优子结构：子结构最优，全局一定最优
无后效性：各个决策部分单独存在，不会相互影响

确定状态
- 维度从低往高试
确定转移方程
- 每一个状态的决策
- 初始值
- 边界问题
是否可以降低维度或其他优化

最大子串和

题意：给你一个有正有负的序列，求一个=子串（连续的一段），使其和最大！
样例输入： -5 6 -1 5 4 -7
样例输出： 14

状态：f[i]表示前i个数的最大子串和，每个状态只有两种决策：1. 与前面构成一个子串 2. 单独成为一个子串的开头
转移方程: f[i]=max(f[i−1]+a[i],a[i])f[i]=max(f[i−1]+a[i],a[i])

不相交的两个子串的最大和

给你一个有正有负的序列，求两个不重叠的子串，使其和最大！

方法一

两个不重叠的子串中间一定有一个分界点，我们可以枚举这个分界点，分别求出这个点左边的最大子串和以及右边的最大子串和

方法二

定义状态f[i][j]为前i个数组成了j个子串的最大值，当前状态下有两种选择，一种是与前面组成子串，一种是单独成为一个子串，但是需要枚举这个数前面的串的结尾在哪里
状态转移方程为f[i][j]=max(f[i−1][j]+a[i],f[k][j−1]+a[i],0<k<if[i][j]=max(f[i−1][j]+a[i],f[k][j−1]+a[i],0<k<i
优化：可以用前缀和维护k维度，算出前k个数的最大和

最大子矩形

在一个矩阵中找到一个子矩阵，该子矩阵和最大！！输出最大和即可。

从暴力的角度考虑，这道题需要枚举矩形的两个顶点，也就是O(n^4)
我们可以只枚举两个顶点的行坐标，即找到这个矩形的高度所在的位置，然后把每一列的数之和求出来当做一个数，可以提前求出每一列前缀和，也就转化成了求最大子串和。

最长公共子序列

给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
最长公共子序列:公共子序列中长度最长的子序列。
给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…, yn}，找出X和Y的一个最长公共子序列。

状态：f[i][j]表示X的前i位与Y的前j位最长公共子序列的长度
转移方程：

for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
    if(X[i]==Y[j]) f[i][j]=f[i-1][j-1]+1;
    else f[i][j]=max(f[i-1][j],f[i][j-1]);
}

回文词

回文词是一种对称的字符串——也就是说，一个回文词，从左到右读和从右到左读得到的结果是一样的。任意给定一个字符串，通过插入若干字符，都可以变成一个回文词。你的任务是写一个程序，求出将给定字符串变成回文词所需插入的最少字符数。比如字符串“Ab3bd”，在插入两个字符后可以变成一个回文词（“dAb3bAd”或“Adb3bdA”）。然而，插入两个以下的字符无法使它变成一个回文词。
给出一个字符串求出使其变为回文串需要插入的最少字符数。

思路：需要添加的字符的长度为原字符串的总长度减去现有的回文串长度，所以只要求出原字符串的回文串的长度就可以解决了
回文串的定义是正串与反串一样，那么正串与反串的最长公共子序列长度就是回文串的长度
为什么不是最长公共子串长度？* 在添加字符的时候可以在任意位置插入，所以不必要求连续。所以如果只能从左右两边加入，那么就是最长公共子串长度*

乘积最大

设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。
如：有一个数字串：312，当N=3，K=1时会有以下两种分法：1） 312=362） 312=62
这时，符合题目要求的结果是：31*2=62

状态：f[i][j]表示前i位使用k个乘号的最大乘积
决策：

这个数与前面的数组成更大的数，需要枚举这个数的起点
单独成为一个新数

*在算乘积的时候可以先算出前缀‘乘’*
转移方程:

for(int i=1;i<=n;i++)
    muti[i]*=muti[i-1]*a[i];
muti[0]=1;

for(int i=1;i<=n;i++)
for(int j=1;j<=k;j++)
{
    f[i][j]=f[i-1][j-1]*a[i];
    for(int k=1;k<i;k++)
        f[i][j]=f[k][j-1]*(muti[i]/muti[k-1]);
}

Posted 12-08-2018Inspiring Learning / Competitive Programming

2018/12/8模拟赛

~~终于有一次能在考场上打出正解的模拟赛~~

连线游戏

题目

连线游戏（lines.cpp）
文件输入输出
时间限制：1s
空间限制：256M

【题目描述】
Farmer John最近发明了一个游戏，来考验自命不凡的贝茜。游戏开始的时候，FJ会给贝茜一块画着N (2 <= N <= 200)个不重合的点的木板，其中第i个点的横、纵坐标分别为X_i和Y_i (-1,000 <= X_i <=1,000； -1,000 <= Y_i <= 1,000)。
贝茜可以选两个点画一条过它们的直线，当且仅当平面上不存在与画出直线平行的直线。游戏结束时贝茜的得分，就是她画出的直线的总条数。为了在游戏中胜出，贝茜找到了你，希望你帮她计算一下最大可能得分。

【输入格式】
第1行: 输入1个正整数：N
第2..N+1行: 第i+1行用2个用空格隔开的整数X_i、Y_i，描述了点i的坐标

【输入样例】(lines.in):
4
-1 1
-2 0
0 0
1 1

【输出格式】
第1行: 输出1个整数，表示贝茜的最大得分，即她能画出的互不平行的直线数

【输出样例】 (lines.out):
4

【输出说明】

贝茜能画出以下4种斜率的直线：-1，0，1/3以及1。

思路

枚举两两构成直线的k值，如果k值不存在，则ans++。

遇到的坑

要考虑精度问题，考试的时候写了1e-5，结果炸了，改成1e-7就对了，甚至不加精度判断都能AC
特判分母为0的情况，本来以为Inf是无限大，所有Inf表示的都是一个意思，但实际炸了……
###AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N=210;
int x[N],y[N],n;
double ans[N*N];

int main()
{	
	freopen("lines.in","r",stdin);
	freopen("lines.out","w",stdout);
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&x[i],&y[i]);
	
	int cnt=0;
	for(int i=1;i<=n;i++)
	for(int j=i+1;j<=n;j++)
	{
		double sta;
		if(x[i]-x[j]==0) sta=0x3f3f3f3f;
		else sta=1.0*(y[i]-y[j])/(x[i]-x[j]);
		
		bool flag=1;
		for(int k=1;k<=cnt;k++)
		{
			if(ans[k]-sta<=1e-10 && ans[k]-sta>=-1e-10)
			{
				flag=0;
				break;	
			} 
		}
		if(flag) ans[++cnt]=sta;//printf("%lf\n",sta);
	}
	printf("%d\n",cnt);
	return 0; 
}

独木桥

题目

【问题描述】
战争已经进入到紧要时刻。你是运输小队长，正在率领运输部队向前线运送物资。运输任务像做题一样无聊。你希望找些刺激，于是命令你的士兵们到前方的一座独木桥上欣赏风景，而你留在桥下欣赏士兵们。士兵们十分愤怒，因为这座独木桥十分狭窄，只能容纳一个人通过。假如有两个人相向而行在桥上相遇，那么他们两人将无法绕过对方，只能由一个人回头下桥，让另一个人先通过。但是，可以有多个人同时呆在同一个位置。
突然，你收到从指挥部发来的信息，敌军的轰炸机正朝着你所在的独木桥飞来！为了安全，你的部队必须撤下独木桥。独木桥的长度为L，士兵们只能呆在坐标为整数的位置，所有士兵的速度都为1，当一个士兵某一时刻来到了坐标为0或L+1的位置时，他就离开了独木桥。
每个士兵都有一个初始面对的方向，他们会以匀速朝着这个方向行走，中途不会自己改变方向。但是，如果两个士兵面对面相遇，他们无法彼此通过对方，于是就分别转身，继续行走。转身不需要任何时间。
由于先前的愤怒，你已不能控制你的士兵。甚至，你连每个士兵初始面对的方向都不知道。因此，你想要知道你的部队最少需要多少时间就可能全部撤离独木桥。另外，总部也在安排阻拦敌人的进攻，因此你还需要知道你的部队最多需要多少时间才能全部撤离独木桥。

【输入文件】
第一行：一个整数L，表示独木桥的长度。桥上的坐标为1..L
第二行：一个整数N，表示初始时留在桥上士兵的数目。
第三行：有N个整数，分别表示每个士兵的初始坐标。初始时，没有两个士兵在同一坐标。

【输出文件】只有一行，输出两个整数，分别表示部队撤离独木桥的最小时间和最大时间。两个整数用一个空格分开。

【样例输入】
4
2
1 3

【样例输出】
2 4

【数据规模及约定】
N≤L≤1000

思路

两个人遇见并分别掉头与两个人继续往前走是等价的，因为人与人之间不存在差异。

每个士兵只有两种选择，向左或向右

最大值就是每个士兵的最长选择的集合中的最大值

最小值就是每个士兵的最短选择的集合中的最大值

遇到的坑

最外一层都是max，满足木桶原理

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int l,n,ans1,ans2;//max,min

int main()
{
	freopen("bridge.in","r",stdin);
	freopen("bridge.out","w",stdout);
	
	scanf("%d%d",&l,&n);
	while(n--)
	{
		int x;
		scanf("%d",&x);
		ans1=max(ans1,min(x,l-x+1));//min
		ans2=max(ans2,max(x,l-x+1));//max
	}
	printf("%d %d\n",ans1,ans2);
	return 0;
}

俄罗斯方块

最水的一道题，直接模拟，分七种情况，细心一点就好了

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N=110;
int mp[N],c,p,ans;

int main()
{
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	
	scanf("%d%d",&c,&p);
	for(int i=1;i<=c;i++)
		scanf("%d",&mp[i]);

	if(p==1)
	{
		for(int i=1;i<=c-3;i++)
			if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2] && mp[i+2]==mp[i+3]) ans++;
		printf("%d\n",c+ans);
		return 0;
	}
	if(p==2)
	{
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]) ans++;
		printf("%d\n",ans);
		return 0;
	}
	if(p==3)
	{
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2]-1) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]+1) ans++;
		printf("%d\n",ans);
		return 0;
	}
	if(p==4)
	{
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1]+1 && mp[i+1]==mp[i+2]) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]-1) ans++;
		printf("%d\n",ans);
		return 0;
	}
	if(p==5)
	{
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2]) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]-1) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]+1) ans++;
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1]+1 && mp[i]==mp[i+2]) ans++;
		printf("%d\n",ans);
		return 0;
	}
	if(p==6)
	{
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2]) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]) ans++; 
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1]-1 && mp[i+1]==mp[i+2]) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]+2) ans++; 
		printf("%d\n",ans);
		return 0;
	}
	if(p==7)
	{
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2]) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]) ans++; 
		for(int i=1;i<=c-2;i++)
			if(mp[i]==mp[i+1] && mp[i+1]==mp[i+2]+1) ans++;
		for(int i=1;i<=c-1;i++)
			if(mp[i]==mp[i+1]-2) ans++; 
		printf("%d\n",ans);
		return 0;
	}
	return 0;
}

/*
5 7
2 0 3 1 2
*/

Posted 12-06-2018Inspiring Learning / Competitive Programming

汉诺塔问题

题面

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

自己汉诺塔问题晕了很久，但搜索写多了至少也有一些通悟

不妨假设：

当只有
1
1个盘子
时
1. 把盘子从A直接移到C
当只有
1
2个盘子
时
1. 将上面的盘子从A移动到B
2. 将下面的盘子从A移动到C
3. 将B上的盘子从B移动到C
当有
1
3个盘子
时
1. 将上面的盘子从A移动到C
2. 将中间的盘子从A移动到B
3. 将C上的盘子从C移动到B
4. 将下面的盘子从A移动到C
5. 将B上面的盘子从B移到A
6. 将B上的盘子从B移到C
7. 将A上的盘子从A移到C

可以发现当有3个盘子时，中间就会转化成2个盘子的情况，2个盘子最后就会转化成1个盘子的情况，显然可采用递归的方法

思路

把n-1个盘子移到B，再把最下面的盘子移到C，再把B上的n-1个盘子移到C

#include <iostream>
#include <cstdio>
using namespace std;

int ans,n;

void dfs(int x,int a,int b,int c)// num from  trans   end
{
    if(x==1)
    {
        printf("move from %d to %d\n",a,c);
        ans++;
     	return;   
    }
    dfs(x-1,a,c,b);
    printf("move from %d to %d\n",a,c);
    ans++;
    dfs(x-1,b,a,c);
}

int main()
{
    scanf("%d",&n);
    dfs(n,1,2,3);
    printf("need %d steps\n",ans);
	return 0;
}

自己遇到的坑

a,b,c三个柱子没有搞清楚，递归函数里到底四个参数分别代表什么要搞清楚

其他一些……

f[n]=f[n-1]*2+1

本次的次数就等于把n-1个盘子移动了两回，加上剩下的最大的盘子移动的一次

Posted 12-06-2018Inspiring Learning / Competitive Programming

滑动窗口

思路：单调队列

以求最小值为例

在读取每一个数 ai 的过程中，判断队尾的数是否大于ai,如果大于则证明队尾的数已经没有意义了，因为***它已经不可能成为现在及以后所有窗口内的最小值***，不妨弹出，重复以上操作，直到ai小于队尾的数，再把ai放到队尾
当现在的长度已经达到窗口的长度时，每一次都会输出最小值，因为队列是单调递减的，第一个数一定是现在窗口内最小的数，直接输出
在队尾添加的过程中，***要始终保证队列里的数都在窗口内***，当区间长度大于窗口长度时，要从队首弹出

自己遇到的坑

***队列内存储的是这个数的位置，不是这个数的大小***，大小通过数组类似映射表示
*要考虑好整个过程的先后顺序*
1. 先确保队列内的数都在范围内
2. 把所有比ai小的队尾数依次弹出
3. 将ai入队
4. 如果达到滑动窗口范围，输出值
*两个数的编号相减加1代表该闭区间的长度*
当算完最小值时队列不一定是空的，要先清空队列

C++ STL 双端队列 deque

q.push_back: 从后端加入 q.pop_back: 从后端弹出
从前端就是front
q.clear: 清空队列
q.size(): 读取队列的长度，但是好像类型不是int，只能用来判断数组是否为空

AC代码

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

const int N=1e6+5;
int a[N];
deque<int> q;

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    
//	q.push_back(1);
    //minn
    for(int i=1;i<=n;i++)
    {
        if(q.size() && i-k>=q.front()) q.pop_front();
        while(q.size() && a[i]<=a[q.back()]) q.pop_back();
        q.push_back(i);
        if(i>=k) printf("%d ",a[q.front()]);
    }
    
//	return 0;
    printf("\n");
    q.clear();
//	q.push_back(1);
    //maxn
    for(int i=1;i<=n;i++)
    {
        if(q.size() && i-k>=q.front()) q.pop_front();
        while(q.size() && a[i]>=a[q.back()]) q.pop_back();
        q.push_back(i);
        if(i>=k) printf("%d ",a[q.front()]);
    }
    
    return 0;
}

— 空 —

— 数字 —

人工智能第二讲

矩阵形式的线性回归

KNN分类算法

图像数据处理基础

Question

My thought

Points to note

Code

ArrayList

How to traverse the ArrayList

花店橱窗布置

思路

矩阵取数

思路

传纸条

思路

免费馅饼

题目

思路

三角蛋糕

思路

金明的预算方案

思路：分组背包

01/完全背包混合

二维限制的背包

面包

题目

思路

二叉苹果树

思路

代码：记忆化搜索

先修课

题目

思路

K-set

题目

思路

基本公式：

题意

分析

遇到的坑

黑棋先走和白棋先走走到的棋局相同的情况也是两种情况，不能判重删去！！！

STL

迭代器

SET

set的各成员函数列表

链接

题意

分析

遇到的坑

题意

分析

遇到的坑

分析

动态规划

贪心

分析

遇到的坑

P1103 书本整理

分析

遇到的坑

AC代码

P1429 平面最近点对（加强版）

题目

思路

动态规划2-背包DP

装箱问题

优化

01滚动

就地滚动

01背包

笔记

最大子串和

不相交的两个子串的最大和

方法一

方法二

最大子矩形

最长公共子序列