Kue

4448

Kue
18小时前

### 拓展训练:背包问题具体方案

#include <cstring>
#include <iostream>
#include <math.h>
using namespace std;

const int N = 410;
int f[21][N][N];
int n, k, p;
int main()
{
cin >> n >> k >> p;
memset(f, -0x3f, sizeof f);
int m;
f[0][0][0] = 0;
for(m = 1; ; m++)
{
int v = pow(m, p);
if (v > n) break;
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= k; j++)
{
f[m][i][j] = f[m - 1][i][j];
if (i >= v && j) // 一定要大于+等于
{
f[m][i][j] = max(f[m][i - v][j - 1] + m, f[m][i][j]);
}
}
}
}
m--;
if(f[m][n][k] < 0) puts("Impossible");
else
{
printf("%d = ", n);
bool f1 = true;
while (m)
{
int v = pow(m, p);
while (f[m][n - v][k - 1] + m >= f[m - 1][n][k])
{
if (f1) f1 = false;
else printf(" + ");
printf("%d^%d", m, p);
n -= v;
k --;
}
m--;
}

}
}


Kue
2天前

Sexy primes are pairs of primes of the form (p, p+6), so-named since “sex” is the Latin word for “six”. (Quoted from http://mathworld.wolfram.com/SexyPrimes.html)

Now given an integer, you are supposed to tell if it is a sexy prime.

Input Specification:
Each input file contains one test case. Each case gives a positive integer N (≤10).

Output Specification:
For each case, print in a line Yes if N is a sexy prime, then print in the next line the other sexy prime paired with N (if the answer is not unique, output the smaller number). Or if N is not a sexy prime, print No instead, then print in the next line the smallest sexy prime which is larger than N.

Sample Input 1:
47
Sample Output 1:
Yes
41
Sample Input 2:
21
Sample Output 2:
No
23

#include <cstring>
#include <iostream>

using namespace std;
const int N = 110;
bool res = true;

bool is_prime(int x)
{
for(int i = 2; i <= x / i; i++)
{
if (x % i == 0) return false;
}
return true;
}
int check(int m)
{
if (is_prime(m))
{
bool f1 = is_prime(m - 6);
bool f2= is_prime(m + 6);
if (f1) return m - 6;
else if (f2) return m + 6;
else{
m++;
res = false;
while(true)
{
bool f1 = is_prime(m);
bool f2 = is_prime(m - 6);
bool f3 = is_prime(m + 6);
if (f1 && f2) return m;
else if (f1 && f2) return m;
m++;
}
}
}else{
m++;
res = false;
while(true)
{
bool f1 = is_prime(m);
bool f2 = is_prime(m - 6);
bool f3 = is_prime(m + 6);
if (f1 && f2) return m;
else if (f1 && f2) return m;
m++;
}
}
}

int main()
{
int m;
cin >> m;
int k = check(m);
if (res) puts("Yes");
else puts("No");
printf("%d", k);
}


Kue
2天前

# 英语词汇 - 数学篇

digit n. 数字

a URL consisting of the first 10-digit prime found in consecutive digits of the natural constant e

consecutive adj. 连续的

integer n. 整数

meanings n. 含义

sexy adj 性感的

PP奶核心句
fatter panda can have more milk
each panda can only compare with its neighbor(s)
It is only when another bowl of milk is at least 100 ml more than its own that a panda can sense the difference

Kue
2天前

### 核心:判定买的地是连续的,需要用前缀和算法,由于数据量较大,需要剪枝

#include <iostream>
#include <cstring>

using namespace std;
const int N = 10010;
int p[N];

int main()
{
int m, sum;
cin >> m >> sum;
for(int i = 1; i <= m; i++)
{
cin >> p[i];
p[i] = p[i] + p[i - 1];
}
int cnt = 0;
for(int i = 0; i < m; i++)
{
for(int j = i + 1; j <= m; j++)
{
//printf("%d %d %d\n", p[j] - p[i], p[j], p[i]);
if (p[j] - p[i] <= sum) cnt++;
else break;
}
}
printf("%d", cnt);
}


Kue
2天前

### 本质:熊猫重的喝的奶要比别人至少多100ml

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10010;
int p[N], l[N], r[N];

int main()
{
int m, num = 2, sum = 0;
cin >> m;
for(int i = 0; i < m; i++) cin >> p[i];
l[0] = num;
for(int i = 1; i < m; i++)
{
if (p[i] > p[i - 1]) l[i] = l[i - 1] + 1;
else if (p[i] == p[i - 1]) l[i] = l[i - 1];
else l[i] = 2;
}
num = 2;
r[m - 1] = num;
for (int i = m - 2; i >= 0; i--)
{
if (p[i] > p[i + 1]) r[i] = r[i + 1] + 1;
else if (p[i] == p[i + 1]) r[i] = r[i + 1];
else r[i] = 2;
}

for(int i = 0; i < m; i++)
{
sum += max(l[i], r[i]);
}
printf("%d", sum * 100);
}


Kue
3天前

### 拓展:vector[HTML_REMOVED]> ans; 通过ans来将vector内部排序,特别好用

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 110, M = 2 * N;
int e[M], ne[M], h[N], w[M], cnt;
int s;
vector<int> res;
vector<vector<int>> ans;
void add(int a, int b, int c, int d)
{
e[cnt] = b, ne[cnt] = h[a], w[a] = c, w[b] = d, h[a] = cnt++;
}

void dfs(int u, int x)
{
bool f = true;
res.push_back(w[u]);
if (x > s)
{
res.pop_back();
return;
}
for(int i = h[u]; ~i; i = ne[i])
{
int v = e[i];
// res.push_back(w[v]);
dfs(v, x + w[v]);
// res.pop_back();
f = false;
}
if (f)
{
if (x == s)
{
ans.push_back(res);
}
}
res.pop_back();

}
int main()
{
int m, n, x, y, z;
cin >> m >> n >> s;
vector<int> vc(m);
memset(h, -1, sizeof h);
for(int i = 0; i < m; i++) cin >> vc[i];
for(int i = 0; i < n; i++)
{
cin >> x >> y;
while (y--)
{
cin >> z;
}
}
dfs(0, vc[0]);
sort(ans.begin(), ans.end(), greater<vector<int>>());
for(auto t : ans)
{
printf("%d", t[0]);
for(int i = 1; i < t.size(); i++)
{
printf(" %d", t[i]);
}
puts("");
}
}


Kue
5天前

### 核心:就是看出规律,将push分成两个层次,push前是push,左儿子,push前是pop,右儿子

#include <iostream>
#include <cstring>
#include <stack>
#include <queue>
using namespace std;
const int N = 40;
int l[N], r[N];
bool f1 = true;
void post(int s)
{
if (l[s] != -1) post(l[s]);
if (r[s] != -1) post (r[s]);

if (f1) f1 = false;
else printf(" ");
printf("%d", s);
}
int main()
{
int m;
cin >> m;
string str;
memset(l, -1, sizeof l);
memset(r, -1, sizeof r);
bool flag = true;
int root = 0, s, type = 1;
stack<int> stk;
for(int i = 1; i <= 2 * m; i++)
{
cin >> str;
//cout << str;
if (str == "Push")
{
int x;
cin >> x;

if (flag) {
s = x;
flag = false;
}else{
if (type)
{
l[root] = x;
}else
{
r[root] = x;
}
}
// type放在后面
// 防止先执行后,type一直是1
type = 1;
root = x;
stk.push(x);

}else if (str == "Pop"){
type = 0;
root = stk.top();
stk.pop();
}
}

post(s);
}


Kue
6天前

### 核心在于dfs,透传一个层级数

#include <cstring>
#include <iostream>

using namespace std;

const int N = 110;
int e[N], ne[N], h[N], cnt;
int max_dep;
int dep[N];
{
e[cnt] = b, ne[cnt] = h[a], h[a] = cnt++;
}

void dfs(int u, int d)
{
if (h[u] == -1)
{
dep[d]++;
max_dep = max(max_dep, d);
return;
}
for(int i = h[u]; ~i; i = ne[i])
{
dfs(e[i], d + 1);
}
}
int main()
{
int m, n;
cin >> m >> n;
memset(h, -1, sizeof h);
while (n--)
{
int x, c, y;
cin >> x >> c;
while (c--)
{
cin >> y;
}

}
dfs(1, 0);
printf("%d", dep[0]);
for(int i = 1; i <= max_dep; i++) printf(" %d", dep[i]);
}


Kue
9天前

### 核心:lca的运用,直接跳上一层是不行的

⭐关键是理解二进制拼凑 在这里是怎么体现的

LCA下一层为第12层

f[x][总共<12步] != f[y][总共<12步] 那就跳(拼凑2^k)

f[i][j] 从i开始向上走2^j步所能走到的节点 0<=j<=logn
1
/ \
2 3
/ \
4 5
/ \
6 7
f[6][0] = 4
f[6][1] = 2
f[6][2] = 空集

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

const int N = 40010, M = 2 * N;
int e[M], ne[M], h[N], cnt;
int f[N][16], depth[N];

{
e[cnt] = b, ne[cnt] = h[a], h[a] = cnt++;
}
void bfs(int s)
{
queue<int> q;
q.push(s);
memset(depth, 0x3f, sizeof depth);
depth[0] = 0, depth[s] = 1;
while (q.size())
{
int u = q.front();
q.pop();
for(int i = h[u]; ~i; i = ne[i])
{
int v = e[i];

if (depth[v] > depth[u] + 1) // 防止反向边
{
q.push(v);
depth[v] = depth[u] + 1;
f[v][0] = u;
for(int j = 1; j <= 15; j++)
{
f[v][j] = f[f[v][j - 1]][j - 1];
}
}

}
}
}

int lca(int a, int b)
{
if (depth[a] < depth[b]) swap(a, b);
for (int k = 15; k >= 0; k -- )
if (depth[f[a][k]] >= depth[b])
a = f[a][k];
if (a == b) return a;
for (int k = 15; k >= 0; k -- )
if (f[a][k] != f[b][k])
{
a = f[a][k];
b = f[b][k];
}
return f[a][0];
}
// 这种做法不可行,会超时,不懂为啥
// 应该是有一层是自己跳自己,所以得从15层一直向上
/*int lca(int a, int b)
{
if (depth[a] < depth[b]) swap(a, b);

while (depth[a] > depth[b])
{
a = f[a][0];
}
while (a != b)
{
a = f[a][0];
b = f[b][0];
}
return a;
}*/
int main()
{
int m, n, root = 0;
cin >> m;
memset(h, -1, sizeof h);
for(int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
if (b == -1) root = a;
}
bfs(root);

cin >> n;
while (n --)
{
int a, b;
cin >> a >> b;
int res = lca(a, b);
if (res == a) puts("1");
else if (res == b) puts("2");
else puts("0");
}
}



### 核心:设置层级,除了第一次,每一次都是向上两层的级别

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

const int N = 40010, M = 2 * N;
int e[M], ne[M], h[N], cnt;
int f[N][16], depth[N];

{
e[cnt] = b, ne[cnt] = h[a], h[a] = cnt++;
}
void bfs(int s)
{
queue<int> q;
q.push(s);
memset(depth, 0x3f, sizeof depth);
depth[0] = 0, depth[s] = 1;
while (q.size())
{
int u = q.front();
q.pop();
for(int i = h[u]; ~i; i = ne[i])
{
int v = e[i];

if (depth[v] > depth[u] + 1) // 防止反向边
{
q.push(v);
depth[v] = depth[u] + 1;
f[v][0] = u;
for(int j = 1; j <= 15; j++)
{
f[v][j] = f[f[v][j - 1]][j - 1];
}
}

}
}
}

/*int lca(int a, int b)
{
if (depth[a] < depth[b]) swap(a, b);
for (int k = 15; k >= 0; k -- )
if (depth[f[a][k]] >= depth[b])
a = f[a][k];
if (a == b) return a;
for (int k = 15; k >= 0; k -- )
if (f[a][k] != f[b][k])
{
a = f[a][k];
b = f[b][k];
}
return f[a][0];
}*/
// 这种做法不可行,会超时,不懂为啥
// 应该是有一层是自己跳自己,所以得从15层一直向上
int lca(int a, int b)
{
int cnt = 0;
if (depth[a] < depth[b]) swap(a, b);

while (depth[a] > depth[b])
{
a = f[a][0];
cnt++;
// 这里找深度的问题, 应该是有1000+的深度
if (cnt >1000)
{
printf("===%d %d\n", a, f[a][0]);
for (int k = 15; k >= 0; k -- )
{
if (depth[f[a][k]] >= depth[b])
{
printf("----%d %d\n", a, f[a][k]);
a = f[a][k];

}
}

break;
}
}
cnt = 0;
while (a != b)
{
a = f[a][0];
b = f[b][0];
cnt++;
if (cnt > 10) break;
}
return a;
}
int main()
{
int m, n, root = 0;
cin >> m;
memset(h, -1, sizeof h);
for(int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
if (b == -1) root = a;
}
bfs(root);

cin >> n;
while (n --)
{
int a, b;
cin >> a >> b;
int res = lca(a, b);
if (res == a) puts("1");
else if (res == b) puts("2");
else puts("0");
}
}


Kue
10天前

### 核心的思路:还是在于差分,有点需要思考

#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 2010, M = 1000010; // 为啥一百万条边
int e[M], ne[M], h[N], w[M], cnt;
int deg[N], d[N];
bool st[N];
vector<int> vc;
int m, n;
void add(int a, int b, int c)
{
e[cnt] = b, w[cnt] = c, ne[cnt] = h[a], h[a] = cnt++;
deg[b]++;
}
void topo_sort()
{
queue<int> q;
for(int i = 1; i <= m + n; i++)
{
if (deg[i] == 0) q.push(i);
}
while (q.size())
{
int u = q.front();
q.pop();
vc.push_back(u);
for(int i = h[u]; ~i; i = ne[i])
{
int v = e[i];
deg[v]--;
if (deg[v] == 0) q.push(v);
}
}
}
int main()
{
cin >> m >> n;
memset(h, -1, sizeof h);
for(int i = 1; i <= n; i++)
{
int idx;
cin >> idx;
int beg = n, end = 1;
memset(st, false, sizeof st);
while (idx--)
{
int stop;
cin >> stop;
beg = min(beg, stop);
end = max(end, stop);
st[stop] = true;
}
int ver = m + i; // 虚拟点
// 错误做法, k (1, m)之间
for(int k = beg; k <= end; k++)
{
}
}
topo_sort();
for(int i = 1; i <= m; i++) d[i] = 1; // 为啥要全部初始化为1??, 因为不知道从哪个节点开始
//d[vc[0]] = 1; // 这种会少算,可能有多个度为0节点
for(int i = 0; i < vc.size(); i++)
{
int v = vc[i];
for(int j = h[v]; ~j; j = ne[j])
{
int x = e[j];
d[x] = max(d[x], d[v] + w[j]);
}
}
int res = 0;
for(int i = 1; i <= m; i++)
{
res = max(res, d[i]);
}
printf("%d", res);
}