2.2万

ye_yu
PaulCe8

acwing_ydx
Js..
YikN
12_W
lusy
Naxx
RGYZ

lixiaoqian

TREE

wW

rouroud

#include <stdio.h>
#include <stdlib.h>

#define N 1010
#define ri register int

int n, v;
int weights[N], values[N], dp[N][N];

int main(const int argc, char** const argv) {
scanf("%d %d", &n, &v);
for (ri i = 1; i <= n; ++i)
scanf("%d %d", weights + i, values + i);

for (ri i = 1; i <= n; ++i)
for (ri j = 1; j <= v; ++j) {
if (weights[i] <= j) { // 01背包的核心, 状态转移方程
dp[i][j] = fmax(dp[i - 1][j], values[i] + dp[i - 1][j - weights[i]]);
} else {
dp[i][j] = dp[i - 1][j];
}
// printf("%d%c", dp[i][j], j == v ? 10 : 32);
}

printf("%d", dp[n][v]);
return 0;
}


### 据说是经典的树型DP

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ri register int
#define N 1000100

typedef long long int LL;

struct Edge {
int to, nxt;
} edges[N << 1]; // 无向图

void addEdge(int u, int v) {
edges[++cnt_edge].to = v;
}

int n = 0, sign = 1;
char c = getchar();
while (c < 48 || c > 57) {
if (c == '-') sign = ~0;
c = getchar();
}
while (c >= 48 && c <= 57) {
n = (n << 1) + (n << 3) + (c ^ 48);
c = getchar();
}
return sign * n;
}

int n, sizes[N];
LL depths[N];

// Bottom-Up
void DFS1(int curr, int parent) {
sizes[curr] = 1;
for (int e = head[curr]; e; e = edges[e].nxt) {
int child = edges[e].to;
if (child == parent) continue;
DFS1(child, curr);
sizes[curr] += sizes[child];
depths[curr] += sizes[child] + depths[child];
}
}

// Top Down
void DFS2(int curr, int parent) {
if (parent)
//depths[curr] += depths[parent] - depths[curr] + n - (sizes[curr] << 1);
depths[curr] = depths[parent] + n - (sizes[curr] << 1);
for (int e = head[curr]; e; e = edges[e].nxt) {
int child = edges[e].to;
if (child == parent) continue;
DFS2(child, curr);
}
}

int main(int argc, char const *argv[]) {
n = r();
// build the undirected graph
for (int m = n - 1, u, v; m--; ) {
u = r(), v = r();
}

DFS1(1, 0);
DFS2(1, 0);

int ans = 1;
for (int u = 2; u <= n; u = -~u)
if (depths[u] > depths[ans]) ans = u;

return printf("%d", ans), 0;
}


### DFS代码写起来简单

#include <iostream>
#include <vector>

using namespace std;

int n, m;

enum Color { UNKNOWN, BLUE, RED };

inline bool DFS(vector<vector<int>>& g, vector<Color>& colors, int curr, Color color) {
colors[curr] = color;
for (const auto& nxt : g[curr]) {
if (colors[nxt] == color) return false;
if (colors[nxt] == UNKNOWN && !DFS(g, colors, nxt, color == BLUE ? RED : BLUE))
return false;
}
return true;
}

int main(const int argc, const char** const argv) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

cin >> n >> m;
vector<vector<int>> g(n + 1);
vector<Color> colors(n + 1, UNKNOWN);

for (int u, v; m; --m) {
cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}

for (int i = 1; i <= n; ++i) {
if (colors[i] == UNKNOWN && !DFS(g, colors, i, BLUE)) {
cout << "No";
return 0;
}
}

cout << "Yes";
return 0;
}


### 卡恩算法

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 100005

int n, m;
struct Edge {
int to, nxt;
} edges[MAX_N];

int indegrees[MAX_N], ans[MAX_N], ansSize;

void addEdge(int u, int v) {
edges[++cnt_edges].to = v;
}

int main(void) {
scanf("%d %d", &n, &m);
for (int u, v; m; --m) {
scanf("%d %d", &u, &v);
++indegrees[v];
}

int q[MAX_N], front = 0, rear = 0;
for (int i = 1; i <= n; ++i)
if (!indegrees[i]) q[rear++] = i;

while (front < rear) {
int curr = q[front++];
ans[ansSize++] = curr;
for (int e = head[curr]; e; e = edges[e].nxt) {
int nei = edges[e].to;
if (!--indegrees[nei]) q[rear++] = nei;
}
}

if (ansSize < n) {
puts("-1");
return 0;
}

for (int i = 0; i < ansSize; ++i)
printf("%d ", ans[i]);

return 0;
}


11天前

### 暂时只会简单的证明，先背诵代码模版！

#include <iostream>
#include <vector>
#include <tuple>
#include <cstring>

using namespace std;

using T = tuple<int, int, int>;
const int oo = 0x3f3f3f3f;

int n, m, k;
vector<T> edges;

inline void bellman_ford(void) {
int dists[n + 1], backup[n + 1];
memset(dists, oo, sizeof dists);
dists[1] = 0; // 源点到源点的距离为0

int u, v, w;
for (int i = 0; i < k; ++i) {
memcpy(backup, dists, (n + 1) * sizeof(int));
for (int j = 0; j < edges.size(); ++j) {
u = get<0>(edges[j]), v = get<1>(edges[j]), w = get<2>(edges[j]);
dists[v] = min(dists[v], backup[u] + w);
}
}

cout << (dists[n] > oo >> 1 ? "impossible" : to_string(dists[n]));
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

cin >> n >> m >> k;
for (int u, v, w; m; --m) {
cin >> u >> v >> w;
edges.emplace_back(u, v, w);
}

bellman_ford();
return 0;
}


11天前

### 暂时还不会双端BFS

#include <bits/stdc++.h>

using namespace std;

const string goal = "12345678x";

inline int bfs(const string& s) {
queue<string> q{{s}};
unordered_set<string> seen{s};

const int dirs[] = { 0, -1, 0, 1, 0 };

int steps = 0;
while (not q.empty()) {
size_t s = q.size();
while (s--) {
const auto curr = q.front(); q.pop();
if (curr == goal) return steps;
int p = curr.find('x');
int x = p % 3, y = p / 3;
for (int i = 0; i < 4; ++i) {
int nx = x + dirs[i], ny = y + dirs[i + 1];
if (nx < 0 || ny < 0 || nx == 3 || ny == 3)
continue;
string t(curr);
swap(t[p], t[ny * 3 + nx]);
if (seen.count(t)) continue;
q.emplace(t);
seen.emplace(t);
}
}
++steps;
}

return -1;
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

string s;
char x;
for (int i = 0; i < 9; ++i) {
cin >> x;
s += x;
}

cout << bfs(s);
return 0;
}


13天前

#### 理论上最好的时间复杂度为$O(NlogN)$, 最坏情况下时间复杂度退化到$O(N^2)$

#include <iostream>

using namespace std;

void qsort(int a[], int l, int r) {
// recursion exit conditon (空集或只有一个元素)
if (l >= r) return;
int i = l, j = r, x = a[(l + r) >> 1]; // x 为哨兵
do {
while (a[i] < x) ++i;
while (a[j] > x) --j;
if (i <= j) swap(a[i++], a[j--]);
} while (i <= j);
qsort(a, l, j);
qsort(a, i, r);
}

int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int n;
cin >> n;

int a[n];
for (int i = 0; i < n; ++i) cin >> a[i];
qsort(a, 0, n - 1);
for (int i = 0; i < n; ++i) cout << a[i] << ' ';

return 0;
}


21天前

### DFS

#include <iostream>
#include <unordered_set>

#define N 55

int m, n, k;
int g[N][N];

int n = 0, sign = 1;
char c = getchar();
while (c < 48 || c > 57) {
if (sign == '-') sign = ~0;
c = getchar();
}
while (c >= 48 && c <= 57) {
n = (n << 1) + (n << 3) + (c ^ 48);
c = getchar();
}
return sign * n;
}

void print_grid(void) {
int x, y;
for (y= 0; y < m; ++y)
for (x = 0; x < n; ++x)
printf("%d%c", *(*(g + y) + x), x == n - 1 ? 10 : 32);
}

std::unordered_set<int> s;

void DFS(int x, int y, int k, int v) {
static const int dirs[] = { 0, -1, 0, 1, 0 };
if (x < 0 || y < 0 || x == n || y == m) return;
v = v * 10 + *(*(g + y) + x);
if (!k) {
s.emplace(v);
return;
}
for (int i = 0; i < 4; ++i)
DFS(x + *(dirs + i), y + *(dirs + i + 1), k - 1, v);
}

int main(void) {
m = r(), n = r(), k = r();
int x, y;
for (y= 0; y < m; ++y)
for (x = 0; x < n; ++x)
*(*(g + y) + x) = r();

for (y = 0; y < m; ++y)
for (x = 0; x < n; ++x) DFS(x, y, k, 0);

return printf("%d", s.size()), 0;
}


23天前
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 2010
#define M 10010

const int INF = 0x3f3f3f3f;

struct Edge {
int to, nxt, w;
} edges[M];

void addEdge(int u, int v, int w) {
edges[cnt_edges].to = v;
edges[cnt_edges].w = w;
}

int n, m;

int spfa_algorithm() {
int q[(int)5E6], front = 0, rear = 0;
int cnts[N], exists[N], dists[N];

memset(cnts, 0x0000, sizeof cnts);
memset(exists, 0x0000, sizeof exists);
memset(dists, INF, sizeof dists);

for (int u = 1; u <= n; ++u) {
q[rear++] = u;
exists[u] = 1;
dists[u] = 0;
}
int curr;
while (front < rear) {
curr = q[front++];
exists[curr] = 0;
for (int i = head[curr]; ~i; i = edges[i].nxt) {
int v = edges[i].to, w = edges[i].w;
if (dists[curr] + w < dists[v]) {
dists[v] = dists[curr] + w;
if (exists[v]) continue;
q[rear++] = v;
exists[v] = 1;
++cnts[v];
if (cnts[v] == n) return 1;
}
}
}

return 0;
}

int main(const int argc, const char* const argv[]) {

scanf("%d %d", &n, &m);

int u, v, w;
while (m--) {
scanf("%d %d %d", &u, &v, &w);
addEdge(u, v, w); // 有向图
}

puts(spfa_algorithm() ? "Yes" : "No");
return 0;
}


28天前
#include <iostream>

using namespace std;

// s2 是不是s1 的子序列
bool is_subseqence(const string& s1, const string& s2) {
int i = 0, j = 0;
while (i < s1.length() && j < s2.length()) {
if (s1[i] == s2[j]) ++j;
++i;
}
return j == s2.length();
}

int main(void) {
string s;
while (cin >> s)
cout << (is_subseqence(s, "EASY") ? "easy" : "difficult") << endl;

return 0;
}