scarletocean
21分钟前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1010;
int f[N];

int main(void) {
int n, m;
scanf("%d %d", &n, &m);
memset(f, 0, sizeof(f));
int v, w, s;

for (int i = 0; i < n; i++) {
scanf("%d %d %d", &v, &w, &s);
if (s != 0) {            // 是多重背包 / 01背包（多重背包特殊情况）
if (s == -1)
s = 1;           // 多重背包特殊情况 s = 1
int num = min(s, m / v);   //节省1
for (int k = 1; num > 0; k <<= 1) {  // <<=是左移操作
if (k > num)
k = num;   // 注意这里和for循环的结束条件，可以减少代码量
num -= k;
for (int j = m; j >= v * k; j--) {       //从大到小枚举
f[j] = max(f[j], f[j - v * k] + w * k);
}
}
}
else {           // 完全背包，需要从小到大枚举
for (int j = v; j <= m; j++) {
f[j] = max(f[j], f[j - v] + w);
}
}

}
printf("%d\n", f[m]);
return 0;
}


scarletocean
1小时前

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 25000;
int f[N];
//int v = { 0 }, w = { 0 }, s = { 0 };

int main(void) {
int n, m;
scanf("%d %d", &n, &m);
memset(f, 0, sizeof(f));
int v, w, s;

for (int i = 0; i < n; i++) {
scanf("%d %d %d", &v, &w, &s);
int num = min(s, m / v);   //节省1
for (int k = 1; num > 0; k <<= 1) {  //节省2  <<=是左移操作
if (k > num)
k = num;   //注意这里和for循环的结束条件
num -= k;
for (int j = m; j >= v * k; j--) {
f[j] = max(f[j], f[j - v * k] + w * k);
}
}

}
printf("%d\n", f[m]);
return 0;
}


Ncik
3小时前

### 算法

#### dp方程：

dp[i][j]表示s中前$i$个字符和p的前$j$个字符是否匹配成功，如果匹配成功则为$true$，否则为$false$

##### 初始条件：
• sp为空串时，能匹配成功，所以

$dp=true$

• s为空串，p只为*时，*也能替换成空串，所以

$dp[i]=true$ (p串从$1$到$i$均是*号)，如果有除*号以外的字符就匹配不上了

#### C++ 代码

class Solution {
public:
bool isMatch(string s, string p) {
int sLen = s.size();
int pLen = p.size();
//为了空出边界条件dp 我们dp数组从下标为1开始使用
// dp[i][j]表示s中前i个字符和p的前j个字符是否匹配成功，如果匹配成功则为true

vector<vector<bool> > dp(sLen + 1, vector<bool>(pLen + 1, false));
dp = true;

//s为空，*也可以替换成空串，则当s为空p为连续的*号时候也是匹配成功的
for(int i = 1; i <= pLen; i++) {
if(p[i - 1] == '*') {
dp[i] = dp[i - 1];
}
}

for(int i = 1; i <= sLen; i++) {
for(int j = 1; j <= pLen; j++) {
//p的第j个字符是*号，*号可以匹配任意串
//所以无论是s的前i个字符和p的前j-1个字符匹配成功 将*号替换成空串
//还是s的前i-1个字符和p的前j个字符匹配成功，*号替换的长度不限制，
//所以可以将*号替换成的内容多加上s[i]
// 这两种情况都能推出s的前i个字符和p的前j个字符匹配成功
if(p[j - 1] == '*') {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
}

//p的第j个字符不是*号
//如果dp[i-1][j-1]为false，
//则s的前i-1个字符和p的前j-1个字符已经匹配失败了
//这时候dp[i][j]只能为false了
// 如果dp[i-1][j-1]为true，s的前i-1个字符和p的前j-1个字符已经匹配成功了
//则要看s的第i个字符s[i] 和p的第j个字符p[j]是否匹配成功
//s[i]和p[j]匹配成功有两种情况 1是两个字符相同，2是p[j]是？
else {
if(dp[i - 1][j - 1] == true) {
if(s[i - 1] == p[j - 1] || p[j - 1] == '?') {
dp[i][j] = true;
}
}
}
}
}
return dp[sLen][pLen];
}
};


3小时前

KMP：

• 前缀：指的是字符串的子串中从原串最前面开始的子串
如abcdef的前缀有：a,ab,abc,abcd,abcde

• 后缀：指的是字符串的子串中在原串结尾处结尾的子串
如abcdef的后缀有：f,ef,def,cdef,bcdef

• Next[i]：满足 以1开始的前缀以i结尾的后缀 相等条件的最大长度（长度≤i）

Next数组求解：

• 边界：Next=0;（由定义即可得到）

• 匹配状态：j + 1表示当前P要匹配的下标，i表示当前S串要匹配的下标
若P[j+1]=S[i]，直接匹配成功，则Next[j]=Next[j-1]+1;
若P[j+1]≠S[i]，匹配失败，需要根据Next[j]不断向前跳j，直到匹配成功或者j=0；
while (j && S[i] != P[j + 1]) j = Next[j]; Next数组运用：

wzc1995
3小时前

### 题目描述

#### 样例 输入：n = 4, left = [4,3], right = [0,1]

-下标 0 处的蚂蚁命名为 A 并向右移动。
-下标 1 处的蚂蚁命名为 B 并向右移动。
-下标 3 处的蚂蚁命名为 C 并向左移动。
-下标 4 处的蚂蚁命名为 D 并向左移动。

（也就是说在 t = 4.0000000001 时，木板上没有蚂蚁）。 输入：n = 7, left = [], right = [0,1,2,3,4,5,6,7] 输入：n = 7, left = [0,1,2,3,4,5,6,7], right = []


输入：n = 9, left = , right = 


输入：n = 6, left = , right = 



#### 限制

• 1 <= n <= 10^4
• 0 <= left.length <= n + 1
• 0 <= left[i] <= n
• 0 <= right.length <= n + 1
• 0 <= right[i] <= n
• 1 <= left.length + right.length <= n + 1
• leftright 中的所有值都是唯一的，并且每个值 只能出现在二者之一 中。

### 算法

##### (模拟) $O(n)$
1. 两只蚂蚁相遇可以忽略，因为交换方向如果不考虑蚂蚁编号的话实际上等于没有交换。
2. 对于向左走的蚂蚁，需要的时间等于初始的位置；对于向右走的蚂蚁，需要的时间等于长度减去初始位置。

#### 时间复杂度

• 分别遍历两个数组一次，时间复杂度为 $O(n)$。

• 仅需要常数的额外空间。

#### C++ 代码

class Solution {
public:
int getLastMoment(int n, vector<int>& left, vector<int>& right) {
int ans = 0;
for (int x : left)
ans = max(ans, x);

for (int x : right)
ans = max(ans, n - x);

return ans;
}
};


emilyusa
3小时前

### 题目描述

You may recall that an array A is a mountain array if and only if:

A.length >= 3
There exists some i with 0 < i < A.length - 1 such that:
A < A < … A[i-1] < A[i]
A[i] > A[i+1] > … > A[A.length - 1]
Given a mountain array mountainArr, return the minimum index such that mountainArr.get(index) == target. If such an index doesn’t exist, return -1.

You can’t access the mountain array directly. You may only access the array using a MountainArray interface:

MountainArray.get(k) returns the element of the array at index k (0-indexed).
MountainArray.length() returns the length of the array.
Submissions making more than 100 calls to MountainArray.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

#### 样例

Example 1:

Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.
Example 2:

Input: array = [0,1,2,4,2,1], target = 3
Output: -1
Explanation: 3 does not exist in the array, so we return -1.



### 算法1

O(logn)
O(1)

#### C++ 代码


/*
* // This is the MountainArray’s API interface.
* // You should not implement it, or speculate about its implementation
* class MountainArray {
* public:
* int get(int index);
* int length();
* };
/

class Solution {
public:
int findInMountainArray(int target, MountainArray &mountainArr) {
int n=mountainArr.length();
int l=0, r=n-1;
while(l[HTML_REMOVED]target)
l=mid+1;
else
r=mid;
}
if(mountainArr.get(l)==target) return l;
return -1;
}
};

wzc1995
3小时前

### 题目描述

#### 样例

输入：arr = [3,5,1]


输入：arr = [1,2,4]



#### 限制

• 2 <= arr.length <= 1000
• -10^6 <= arr[i] <= 10^6

### 算法

##### (排序) $O(n \log n)$
1. 将原数组从小到大排序。
2. 判断任意相邻两个数字的差值是否一致。

#### 时间复杂度

• 排序后遍历一次，故总时间复杂度为 $O(n \log n)$。

• 仅需要常数的额外空间。

#### C++ 代码

class Solution {
public:
bool canMakeArithmeticProgression(vector<int>& arr) {
sort(arr.begin(), arr.end());

int n = arr.size(), d = arr - arr;

for (int i = 2; i < n; i++)
if (arr[i] - arr[i - 1] != d)
return false;

return true;
}
};


# 单独开一章-附带归纳的算法类型 233

### July 4th Explore Card 264 Ugly Number II

ugly = sorted(2**a * 3**b * 5**c for a in range(32) for b in range(20) for c in range(14))
def nthUglyNumber(self, n):
return self.ugly[n-1]


def nthUglyNumber(self, n):
ugly = 
i2, i3, i5 = 0, 0, 0
while n > 1:
u2, u3, u5 = 2 * ugly[i2], 3 * ugly[i3], 5 * ugly[i5]
umin = min((u2, u3, u5))
if umin == u2:
i2 += 1
if umin == u3:
i3 += 1
if umin == u5:
i5 += 1
ugly.append(umin)
n -= 1
return ugly[-1]


Seeing the description we can arrive at the observation that bigger ugly numbers can be generated by multiplying smaller ugly numbers by 2, 3 and 5. In order to be exhaustive, we have to multiply every ugly number by 2, 3, and 5 do make sure we don’t miss any. The problem with that if you run this method on the first few ugly numbers:

1 -> 2, 3, 5 … 2 -> 4, 6, 10 … 3 -> 6, 9, 15

The problem with this is that there are going to be duplicates and (unsorted)

Therefore the OP’s solution is having 3 pointers, namely i2, i3, and i5, they will keep track of which multiple of 2, 3, 5 of the smaller ugly number they are pointing to. At every loop, you get three multiples of 2, 3 and 5 and you pick the smallest one to append to the ugly number array, this will fix the problem with new ugly number being unsorted, and since we appended that smallest next ugly number, increment the pointer that generated that smallest ugly number so we can add the next bigger one in the future. Since the if-statements are parallel, this also prevent duplicates from being added to the ugly number array, since if two or three u2, u3, and u5 are the same, their corresponding pointer will all be incremented.
Therefore after n-1 loops has executed, we have generated n ugly numbers, and the last number ugly[-1] will indeed be our answer.

# python

$\underline{python}$ 下划线赛高
1. 基础类
1） 离散数学 高等数学 等math
2） Markov Process 最优化Optimisation 凸优化 等stats 哈哈感觉回到了大学
2. 计算理论 对模型评价 过拟合 点估计/区间估计 树模型 （随机森林 gbdt集成学习思想）

#### 每类word2vector 神经网络语言模型

4小时前

Java双栈

class MyQueue {

Stack<Integer>stack1;
Stack<Integer>stack2;
/** Initialize your data structure here. */
public MyQueue() {
stack1=new Stack<>();
stack2=new Stack<>();
}

/** Push element x to the back of queue. */
public void push(int x) {
stack1.push(x);
}

/** Removes the element from in front of queue and returns that element. */
public int pop() {
if(stack2.isEmpty()){
if(stack1.isEmpty()) return -1;
while(!stack1.isEmpty()) stack2.push(stack1.pop());
}
return stack2.pop();
}

/** Get the front element. */
public int peek() {
if(stack2.isEmpty()){
if(stack1.isEmpty()) return -1;
while(!stack1.isEmpty()) stack2.push(stack1.pop());
}
return stack2.peek();
}

/** Returns whether the queue is empty. */
public boolean empty() {
return stack1.isEmpty()&&stack2.isEmpty();
}
}



4小时前

Java 详细注释

class Solution {
public TreeNode inorderSuccessor(TreeNode p) {
//如果有右孩子，那么后继为右孩子中的左孩子wang
if(p.right!=null){
p=p.right;
while(p.left!=null) p=p.left;
return p;
}
//如果没有右孩子，并且为父亲节点的右节点，那么就一直往上找
while(p.father!=null&&p==p.father.right) p=p.father;
return p.father;
}
}
`