tamsl3skafut

6637

18632289119
yxc的小迷妹
shaoyuqi

Iamyou_9
hncsxzx
wendao0723
binaryfinding

WA声闹彻明

happyfox
NG1
めぐみん

asdfasdfasdfa

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

using namespace std;

int t;

bool special(int n, int k, string s, string t)
{
if(n <= 3)  //  all numbers can not be swapped
{
if(s != t)
return false;
else return true;
}
else if(n == 4)
{
if(s == t) return true;
else
{
if(s[1] == t[1] && s[2] == t[2])  //  these number can not be swapped
{
if(s[0] == t[3] && s[3] == t[0])  // can be swapped
return true;
else return false;
}
else return false;
}
}
}

void solve()
{
int n, k;
string s, t;
cin >> n >> k;
cin >> s >> t;

if(n < 5)
{
if(special(n, k, s, t)) cout << "Yes" << endl;
else cout << "No" << endl;
}
else
{
map<char, int> cnt;

for(auto x : s)
cnt[x] ++;

for(auto x : t)
cnt[x] --;

bool ok = true;
for(auto [c, x] : cnt)
ok &= x == 0;

if(n == 5 && ok == true)
{
if(s[2] != t[2])
cout << "No" << endl;
else cout << "Yes" << endl;
}
else cout << (ok ? "Yes" : "No") << endl;
}
}

int main()
{
cin >> t;
while(t --)
solve();

return 0;
}


tamsl3skafut
5个月前

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 200010;

int n, a[N];

int main()
{
cin >> n;
for(int i = 1; i <= n; i ++)
cin >> a[i];

if(n % 2 == 0)
{
for(int i = n; i >= 2; i -= 2)
cout << a[i] << ' ';
for(int i = 1; i <= n - 1; i += 2)
cout << a[i] << ' ';
}
else
{
for(int i = n; i >= 1; i -= 2)
cout << a[i] << ' ';
for(int i = 2; i <= n - 1; i += 2)
cout << a[i] << ' ';
}

return 0;
}


tamsl3skafut
5个月前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int a, b, c;
int cnt[110];  //  记录 枚举sum 的模数的出现次数，如果出现重复且没有符合题意的模数出现就只能输出NO

int main()
{
cin >> a >> b >> c;
//  我们要求的sum就是a的倍数，枚举暴力即可。
for(int i = 1; i * a <= 0x3f3f3f3f; i ++)
{
cnt[(i * a) % b] ++;  //  记录出现次数

if(cnt[(i * a) % b] > 1)  //  重复次数>1
{
cout << "NO" << endl;
break;
}

if((i * a) % b == c)
{
cout << "YES" << endl;
break;
}
}

return 0;
}


tamsl3skafut
10个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1510, M = N;

int e[N], ne[N], idx, h[N], w[N];
int f[N][3];
// 1：被子节点看，0：被父节点看，2：被自己看（此时要加上w[i]）
int n;
bool st[N];

/*

f[i][0] = sigma( min(f[soni][1], f[soni][2]) )

f[i][2] = sigma( min(f[soni][1], f[soni][2], f[soni][0]) )

f[i][1] = sigma( min(f[soni][2] + sigma(min(f[esoni][1], f[esoni][2])) ) ); esoni: all sons expect soni
*/

{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u)
{
f[u][2] = w[u];

int sum = 0;

for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
dfs(j);

f[u][0] += min(f[j][1], f[j][2]);
f[u][2] += min(min(f[j][1], f[j][2]), f[j][0]);
sum += min(f[j][1], f[j][2]);  //  把下面要的状态转移方程的一部分先求出来
}

f[u][1] = 0x3f3f3f3f;
for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];

f[u][1] = min(f[u][1], f[j][2] + sum - min(f[j][1], f[j][2]));
//  sigma(min(f[esoni][1], f[esoni][2])) ) === sum - min(f[j][1], f[j][2])；
}
}

int main()
{
cin >> n;

memset(h, -1, sizeof h);
for(int i = 0; i < n; i ++)
{
int id, cost, cnt;
cin >> id >> cost >> cnt;
w[id] = cost;  //  这道题是节点有权，并不是边上有权

while(cnt --)
{
int ver;
cin >> ver;

st[ver] = true;
}
}

int root = 1;  //  节点从1开始
while(st[root]) root ++;

dfs(root);

cout << min(f[root][1], f[root][2]) << endl;

return 0;
}


tamsl3skafut
10个月前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1510;

int e[N], ne[N], idx, h[N];
int f[N][2];
//  以结点 i 为 根节点 的子树，在 i 上放置哨兵(1) 和不放哨兵(0) 的方案,  树型dp＆状态机
int n;
bool st[N];

void add(int a, int b)  // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

//  这个dfs本质是从下到上的，所以是对于这棵树来说是先更新儿子，再更新父亲

int dfs(int u)
{
f[u][1] = 1, f[u][0] = 0;  //  init状态

for(int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
dfs(j);
//  观察的是边，不是点！！！
f[u][0] += f[j][1];  //  u没有兵，它的旁边必须放
f[u][1] += min(f[j][1], f[j][0]);  //  u上有兵，旁边可放可不放，选最小的选法即可
}
}

int main()
{
while(cin >> n)
{
memset(st, 0, sizeof st);
memset(h, -1, sizeof h);
idx = 0;
//  init三巨头！

for(int i = 0; i < n; i ++)
{
int id, cnt;
scanf("%d:(%d)", &id, &cnt);

while(cnt --)
{
int ver;
cin >> ver;

st[ver] = true;  //  把不是根的点排除
}
}

int root = 0;  //  找根，因为这题没说谁是根！且是!有向图!!, 还有，这道题有0节点，下道皇宫看守是从1开始i的
while(st[root]) root ++;

dfs(root);

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

return 0;
}


tamsl3skafut
10个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, M = N * 2;

int idx, ne[M], e[M], h[N], w[M];
int n, m;
int f[N][N];  //   以 i 为根节点的子树，包含 i 的连通块的边数不超过 j 的方案 的集合！！！！！！
// f(i,j) = max{ f(i, j − 1 − k) + f(soni, k) + wedgei} k ∈ [0,j − 1 ]
//  这个集合说明了很多

void add(int a, int b, int c)  // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}

void dfs(int u, int father)
{
for(int i = h[u]; i != -1; i = ne[i])
{
if(e[i] == father) continue;

dfs(e[i], u);

for(int j = m; j; j --)
for(int k = 0; k <= j - 1; k ++)
f[u][j] = max(f[u][j], f[u][j - k - 1] + f[e[i]][k] + w[i]);  // most valuable
}
}

int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 0; i < n - 1; i ++)
{
int a, b, c;
cin >> a >> b >> c;

}

dfs(1, -1);

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

return 0;
}


tamsl3skafut
10个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 50010, M = 50010;

int e[M], ne[M], idx, h[N];
int ans;
int n;
int sum[N];
bool st[N];

{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u)
{
st[u] = true;  //  树根

int d1 = 0, d2 = 0, dist = 0;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(!st[j])
{
int d = dfs(j);  //  先找出子树的最远步数
dist = max(d, dist);

if(d >= d1)
d2 = d1, d1 = d;
else if(d > d2) d2 = d;  //  更新d1,d2
}
}

ans = max(ans, d1 + d2);  //  更新最大步数

return dist + 1;
}

int main()
{
cin >> n;
memset(h, -1, sizeof h);

for(int i = 1; i <= n; i ++)
for(int j = 2; j <= n / i; j ++)
sum[i * j] += i;  //  从1到n的倍数的角度枚举计算各个数的约数的和

for(int i = 2; i <= n; i ++)  //  判断是否可以建边
if(sum[i] < i)

for(int i = 1; i <= n; i ++)
if(!st[i])
dfs(i);  //  遍历过的节点就不用再遍历了

cout << ans << endl;

return 0;
}


tamsl3skafut
10个月前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010, M = N * 2, INF = 0x3f3f3f3f;

int n;
int h[N], e[M], w[M], ne[M], idx;
int d1[N], d2[N], p1[N], up[N];
bool is_leaf[N];  //  树的末端不能再向下， d1=d2=0

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

int dfs_d(int u, int father)
{
d1[u] = d2[u] = -INF;
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(j == father) continue;
int d = dfs_d(j, u) + w[i];

if(d >= d1[u])
{
d2[u] = d1[u], d1[u] = d;
p1[u] = j;  //  更新最大的向下的路径由j而来
}
else if(d >= d2[u]) d2[u] = d;
}

if(d1[u] == -INF)
{
is_leaf[u] = true;
d1[u] = d2[u] = 0;
}

return d1[u];
}

int dfs_u(int u, int father)
{
for(int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if(j == father) continue;  //  无意义

//  看看最大向下长度路径是否是由当前节点来的
if(p1[u] == j) up[j] = max(d2[u], up[u]) + w[i];  //  向上的路径是u的向下次大值与u向上走的max + w[i]
else up[j] = max(up[u], d1[u]) + w[i];  //  与上同理

dfs_u(j, u);
}
}

int main()
{
cin >> n;
memset(h, -1, sizeof h);
for (int i = 0; i < n; i ++ )
{
int a, b, c;
cin >> a >> b >> c;

}

dfs_d(1, -1);  //  只向下找
dfs_u(1, -1);  //  只向上找

int res = d1[1];
for(int i = 2; i <= n; i ++)
if(is_leaf[i]) res = min(res, up[i]);  //  有无isleaf无所谓，因为这里是取max且叶子节点的d1是0
else res = min(res, max(up[i], d1[i]));

cout << res << endl;

return 0;
}


tamsl3skafut
10个月前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 10010, M = 2 * N;

int h[N], e[M], ne[M], w[M], idx;  //  idx代表边数
int ans;
int n;

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

int dfs(int u, int father)
{
int dist = 0;  //  表示从当前点往下走的最大长度, 用来更新d1，d2；
int d1 = 0, d2 = 0; //  最大长度，次大长度

for(int i = h[u]; ~i; i = ne[i])  //  遍历所有子树的边
{
int j = e[i];
if(j == father) continue;  //  爹
int d = dfs(j, u) + w[i];  //  更新最大长度
dist = max(d, dist);

if(d >= d1) d2 = d1, d1 = d;
else if(d >= d2) d2 = d;
}

ans = max(ans, d1 + d2);  //  d1 + d2就是当前通过这个点的最大路径（已经跑出上面的子树的遍历了）

return dist;
}

int main()
{
cin >> n;

memset(h, -1, sizeof h);
for(int i = 0; i < n - 1; i ++)
{
int a, b, c;
cin >> a >> b >> c;

}

dfs(1, -1);

cout << ans << endl;

return 0;
}


tamsl3skafut
11个月前
cd homework_6
vim source0.cpp
ggdG  # 删掉全文
Ctrl-a, "   在tmux中打开一个新的pane
vim source1.cpp
:set nonu  删掉行号
shift + 选中前3行
Ctrl + insert 复制选中内容

:set paste 进入粘贴模式
i进入编辑模式
Shift + insert粘贴内容