Anish

4.4万

Anish
2天前
class Solution {
public:
// 最小化最大值
// 二分 + check贪心
// 技巧：限制是最大间距，所以是至少t个，题目一定要用m个，如果t > m, return false

bool check(int mid, int m, vector<int>& nums) {
int sum = 0, t = 0;
for (int i = 0; i < nums.size(); i ++) {
if (nums[i] > mid) return false; // 单个元素已超过最大间距
if (sum + nums[i] > mid) {
t ++;
sum = nums[i];
} else {
sum += nums[i];
}
}
t ++; // 最后一段
// 至少t个，但题目一定要用m个
if (t > m) return false; // 先去看不满足条件的情况
return true;

}

int splitArray(vector<int>& nums, int m) {
int l = 1, r = 1e9;
while (l < r) {
int mid = l + r >> 1;
if (check(mid, m, nums)) r = mid;
else l = mid + 1;
}
return l;
}
};


Anish
16天前

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 410, M = N;
int n, m;

int e[M], ne[M], w[M], idx, h[N];
bool st[N];
int dist[N];

void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int spfa() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;

queue<int> q;
q.push(1);
st[1] = true;

while (q.size()) {
int t = q.front();
q.pop();
st[t] = false;

for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
if (st[j] == false) {
q.push(j);
st[j] = true;
}
}
}
}

int res = 0;
for (int i = 1; i <= n; i ++) {
res = max(res, dist[i]);
}

if (res == 0x3f3f3f3f) return -1;
return res;
}

int main() {
cin >> n >> m;

memset(h, -1, sizeof h);

for (int i = 0; i < m; i ++) {
int a, b, c;
cin >> a >> b >> c;
}

cout << spfa() << endl;

return 0;
}


Anish
18天前

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
// 迭代写法
auto dummy = new ListNode(-1); // 创建一个虚拟头结点
auto p = dummy;
while (p->next != NULL && p->next->next != NULL) {
auto a = p->next, b = p->next->next; // (1)
p->next = b;           // (2)
a->next = b->next;     // (3)
b->next = a;           // (4)
p = a;                 // (5)
}
return dummy->next;
}
};


Anish
23天前
class Solution {
public:
// (s + s).find(s, 1) 这个时间复杂度是O(m*n)的
// 字符串哈希，时间复杂度O(n)
// abcabcabcabcabcabc
//    abcabcabc
typedef unsigned long long ULL;
static const int N = 2e4 + 7, P = 131;
ULL h[N], p[N];

ULL get(int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}

bool repeatedSubstringPattern(string s) {
int n = s.size();
s = " " + s + s;

p[0] = 1;
for (int i = 1; i <= 2 * n; i ++) {
h[i] = h[i - 1] * P + s[i];
p[i] = p[i - 1] * P;
}

for (int i = 2; i <= n; i ++) {
if (get(i, i + n - 1) == get(1, n)) {
return true;
}
}
return false;
}
};


Anish
23天前
#include <iostream>

using namespace std;

int f[6010];

int main() {
int n, m;
cin >> n >> m;

for (int i = 1; i <= n; i ++) {
int v, w, s;
cin >> v >> w >> s;
// 这样写多重背包问题II，必须要用一维的f[]，因为我没有去统计有多少个01背包物品
for (int k = 1; k <= s; k *= 2) {
for (int j = m; j >= k * v; j --) {
f[j] = max(f[j], f[j - k * v] + k * w);
}
s -= k;
}
if (s > 0) {
for (int j = m; j >= s * v; j --) {
f[j] = max(f[j], f[j - s * v] + s * w);
}
}
}

cout << f[m] << endl;

return 0;
}


Anish
24天前
// 八皇后遍历题型：整个棋盘是一个状态，需要恢复现场(回溯法)
#include <iostream>
#include <cstring>

using namespace std;

const int N = 12;
int n, m, sx, sy;
int res; // 用于统计全局答案
bool g[N][N];
int dx[] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[] = {2, -2, 2, -2, 1, -1, 1, -1};

// dfs功能：返回有多少中途径能走完棋盘
void dfs(int u, int x, int y) {
if (u == n * m) {
res ++;
return;
}

for (int d = 0; d < 8; d ++) {
int a = x + dx[d], b = y + dy[d];
if (0 <= a && a < n && 0 <= b && b < m && g[a][b] == false) {
g[a][b] = true;
dfs(u + 1, a, b);
g[a][b] = false;
}
}

}

int main() {
int T;
cin >> T;

while (T --) {
cin >> n >> m >> sx >> sy;
memset(g, false, sizeof g);
res = 0; // 每组初始化res
g[sx][sy] = true;
dfs(1, sx, sy);
cout << res << endl;
}

return 0;
}


Anish
26天前

#include <iostream>

using namespace std;

typedef unsigned long long ULL;
const int N = 1e6 + 7, P = 131;
ULL h[N], p[N];

ULL get(int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
string s;
cin >> s;

int n = s.size();
s = " " + s;

p[0] = 1;
for (int i = 1; i <= n; i ++) {
h[i] = h[i - 1] * P + s[i];
p[i] = p[i - 1] * P;
}

int m;
cin >> m;

while (m --) {
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
if (get(l1, r1) == get(l2, r2)) puts("Yes");
else puts("No");
}

return 0;
}


Anish
26天前

// 分组背包 + 逆推方案
#include <iostream>
#include <cstring>

using namespace std;

const int N = 16;

int f[N][N];
int w[N][N];
int path[N][N];

int main() {
int n, m;
cin >> n >> m;

for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
cin >> w[i][j]; // 第i个公司分配j台机器时的盈利值
}
}

// 分组背包
// f[i][j]表示只在前i个公司分配设备，且设备数不超过j的最大盈利值
for (int i = 1; i <= n; i ++) {
for (int j = 0; j <= m; j ++) {
for (int k = 0; k <= m; k ++) { // 从第i组物品中去选，只能选其中一个。设备数k可以为0
if (j >= k) {
if (f[i][j] < f[i - 1][j - k] + w[i][k]) {
f[i][j] = f[i - 1][j - k] + w[i][k];
path[i][j] = k; // i,j这个状态选了k
}
}
}
}
}

cout << f[n][m] << endl;

// 逆推：求出每组选了哪种物品
int i = n, j = m;
while (i >= 1 && j >= 0) {
cout << i << " " << path[i][j] << endl;
j -= path[i][j];
i --;
}

return 0;
}


Anish
26天前

// 分组背包 + 逆推方案
#include <iostream>
#include <cstring>

using namespace std;

const int N = 16;

int f[N][N];
int w[N][N];
int path[N][N];

int main() {
int n, m;
cin >> n >> m;

for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
cin >> w[i][j]; // 第i个公司分配j台机器时的盈利值
}
}

// 分组背包
// f[i][j]表示只在前i个公司分配设备，且设备数不超过j的最大盈利值
for (int i = 1; i <= n; i ++) {
for (int j = 0; j <= m; j ++) {
for (int k = 0; k <= m; k ++) { // 从第i组物品中去选，只能选其中一个。设备数k可以为0
if (j >= k) {
if (f[i][j] < f[i - 1][j - k] + w[i][k]) {
f[i][j] = f[i - 1][j - k] + w[i][k];
path[i][j] = k; // i,j这个状态选了k
}
}
}
}
}

cout << f[n][m] << endl;

// 逆推：求出每组选了哪种物品
int i = n, j = m;
while (i >= 1 && j >= 0) {
cout << i << " " << path[i][j] << endl;
j -= path[i][j];
i --;
}

return 0;
}


Anish
28天前
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set <int> hash; // 只要是unordered开头，都是哈希
for (auto x : nums) hash.insert(x);

int res = 0;
for (auto num : nums) {
// set已经去重：2,3,4,5  8,9, 20,21,22
// 只去计算2, 8, 20
if (hash.count(num - 1) == 0) {
int end = num;
while (hash.count(end)) end ++;
res = max(res, end - num);
}
}
return res;
}
};