qiao

AcWing

4447

qwwjh

AmazingMing

Dasseinzumtode
o_28
13170082479@163.com

txk666
yxc

ffhhyy
cai_bird_565

qiao
14天前

#### C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int N = 5e4 + 10;

int p[N], d[N];//d[x]表示：x到父节点的距离(经路径压缩后才为到root的距离)

int find(int x)
{
if (p[x] != x)
{
int t = p[x];
p[x] = find(p[x]);
d[x] += d[t];//经过路径压缩后，p[t]一定为root，因此d[t]表示为父节点到root的距离
}
return p[x];
}

int main()
{
int res = 0;
int n, k; cin >> n >> k;
for (int i = 1; i <= n; i++)p[i] = i;
while (k--)
{
int D, x, y; cin >> D >> x >> y;
int px = find(x), py = find(y);
if (x > n || y > n) { res++; continue; }
if (D == 2 && x == y) { res++; continue; }//不加continue就会多计数

if (px != py)
{
if (D == 1)//同类合并
{
d[px] += d[y] - d[x];
p[px] = py;
}
else if (D == 2)//捕食合并
{
d[px] += -1 + d[y] - d[x];
p[px] = py;
}
}
else
{
if (D == 1 && (d[x] - d[y]) % 3 != 0)res++;
if (D == 2 && (d[x] + 1 - d[y]) % 3 != 0)res++;
}
}
cout << res;
}


qiao
1个月前

int main()
{
//函数的凹凸性质可以使用打表制作图像，或者求导判断

//三分本质：每次消去不可能存在正确答案的区间

int l = 0, r = 3.14159265 / 2;//取值范围
//浮点型凹函数
while (r - l > 1e-7)
{
int lmid = l + (r - l) / 3.0, rmid = r - (r - l) / 3.0;
if (f(lmid) > f(rmid))l = lmid;
else r = rmid;
}
//浮点型凸函数
while (r - l > 1e-7)
{
int lmid = l + (r - l) / 3.0, rmid = r - (r - l) / 3.0;
if (f(lmid) < f(rmid))l = lmid;//>改为<
else r = rmid;
}
//整型凹函数
while (l < r)
{
int lmid = l + (r - l) / 3, rmid = r - (r - l) / 3;
if (f(lmid) > f(rmid))l = lmid + 1;
else r = rmid - 1;
}
//整型凸函数
while (l < r)
{
int lmid = l + (r - l) / 3, rmid = r - (r - l) / 3;
if (f(lmid) < f(rmid))l = lmid + 1;
else r = rmid - 1;
}
}


qiao
1个月前

#### C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;
int n;
int num[11];

int calc(int l, int r)
{
int res = 0;
for (int i = l; i <= r; i++)res = res * 10 + num[i];
return res;
}

int main()
{
int cnt = 0;
for (int i = 1; i <= 9; i++)num[i] = i;
cin >> n;

do
{
//枚举中间区间（分为三段，枚举出中间段，其余两段自然可得）
for (int i = 2; i <= 8; i++)
for (int j = i; j <= 8; j++)
{
int a = calc(1, i - 1);
int b = calc(i, j);
int c = calc(j + 1, 9);
// 注意判断条件，因为C++中除法是整除，所以要转化为加减乘来计算
if (c * (n - a) == b)cnt++;
}
} while (next_permutation(num+1,num+10));

cout <<cnt;
}

/*

next_permutation函数
组合数学中经常用到排列，这里介绍一个计算序列全排列的函数：next_permutation（start,end）
，和prev_permutation（start,end）。这两个函数作用是一样的，区别就在于前者求的是当前排列的下一个排列，
后一个求的是当前排列的上一个排列。至于这里的“前一个”和“后一个”，我们可以把它理解为序列的字典序的前后
，严格来讲，就是对于当前序列pn，他的下一个序列pn+1满足：不存在另外的序列pm，使pn<pm<pn+1.

next_permutation(首地址，首地址+长度)
作用:将区间内数组修改为下一个全排列（按照字典序），如果成功return 1 如果当前是最后一个则return 0
因为返回的是下一个，所以一般配合do while使用
*/


qiao
1个月前

#### C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int N = 6e3 + 10;

//h[N]内部存的是idx，e[N], ne[N]是用于描述idx的，（idx，e[N], ne[N]共同组成节点）
//但h[N]的下标存的是题目中的点
int h[N], e[N], ne[N], idx;
int happy[N];
int f[N][2];
bool has_fa[N];

//添加有向边 u->v
{
e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}

void dfs(int u)
{
f[u][1] = happy[u];

for (int i = h[u]; i != -1; i = ne[i])
{
int v = e[i];
dfs(v);//计算方向为：自下而上，因此必须先计算好子节点，然后以此计算父节点

f[u][1] += f[v][0];
f[u][0] += max(f[v][0], f[v][1]);
}

}

int main()
{
int n; cin >> n;
for (int i = 1; i <= n; i++)scanf("%d", &happy[i]);
memset(h, -1, sizeof(h));

for (int i = 0; i < n - 1; i++)
{
int a, b; scanf("%d%d", &a, &b);
has_fa[a] = 1;
}

int root = 1;//注意：此为题中的节点（1~N）而不是idx
while (has_fa[root])root++;

dfs(root);

cout << max(f[root][0], f[root][1]);
}



qiao
1个月前
#include<bits/stdc++.h>
using namespace std;

const int N = 6e3 + 10;

//e[N], ne[N]是用于描述idx的，而h[N]内部存的就是idx
//但h[N]的下标存的是题目中的点
int h[N], e[N], ne[N], idx;
int happy[N];
int f[N][2];
bool has_fa[N];

void add(int u, int v)//添加有向边 u->v
{
e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}

void dfs(int u)
{
f[u][1] = happy[u];

for (int i = h[u]; i != -1; i = ne[i])
{
int v = e[i];
dfs(v);

f[u][1] += f[v][0];
f[u][0] += max(f[v][0], f[v][1]);
}

}

int main()
{
int n; cin >> n;
for (int i = 1; i <= n; i++)scanf("%d", &happy[i]);
memset(h, -1, sizeof(h));

for (int i = 0; i < n - 1; i++)
{
int a, b; scanf("%d%d", &a, &b);
has_fa[a] = 1;
}

int root = 1;
while (has_fa[root])root++;

dfs(root);

cout << max(f[root][0], f[root][1]);
}



qiao
1个月前
#include<bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
const int MOD = 1e9 + 7;

int f[N];

int main()
{
int n; cin >> n;
f[0] = 1;

for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
f[j] = (f[j] + f[j - i]) % MOD;
cout << f[n];
}


qiao
1个月前
#include<bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
char a[N][15], b[15];
int f[N][N];

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

for (int i = 1; i <= n; i++)scanf("%s", &a[i][1]);

for (int j = 1; j <= m; j++)
{
scanf("%s", b + 1); int x; cin >> x;
int cnt = 0;

for (int i = 0; i <= n; i++)f[i][0] = i;
for (int j = 1; j <= m; j++)f[0][j] = j;

for (int k = 1; k <= n; k++)
{
int la = strlen(a[k]+1);
int lb = strlen(b+1);
for (int i = 1; i <= la; i++)
for (int j = 1; j <= lb; j++)
{
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
if (a[k][i] == b[j])f[i][j] = min(f[i][j], f[i - 1][j - 1]);
else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
}
if (f[la][lb] <= x)cnt++;
}
cout << cnt << endl;
}

}


qiao
1个月前
#include<bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
char a[N], b[N];
int f[N][N];

int main()
{
int n, m;
cin >> n; scanf("%s", a + 1);
cin >> m; scanf("%s", b + 1);

for (int i = 0; i <= n; i++)f[i][0] = i;
for (int j = 1; j <= m; j++)f[0][j] = j;

for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
if (a[i] == b[j])f[i][j] = min(f[i][j], f[i - 1][j - 1]);
else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
}

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


qiao
1个月前

#### C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
int f[N][N];
char a[N], b[N];

int main()
{
int n, m; cin >> n >> m;
scanf("%s%s", a + 1, b + 1);

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

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



qiao
1个月前

**[//]: # (打卡模板，上面预览按钮可以展示预览效果 ^^)

#include<bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
int f[N][N];
char a[N], b[N];

int main()
{
int n, m; cin >> n >> m;
scanf("%s%s", a + 1, b + 1);

for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (a[i] == b[j])f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
cout << f[n][m];
}


**