1328

WangJY
123_34

OI
wssdl
Van_sama
yuanxinwang2022
@.@_7
SABI
che_che

Carver
CHN右手

ycq

5小时前
#include <iostream>
#include <queue>
#include <map>

using namespace std;

typedef pair<int, int> PII;

string st[] = {"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};

struct Node
{
int a, b, step;
string s;
};

int a, b, c;

void bfs()
{
queue<Node> q;
map<PII, int> h;

q.push({0, 0, 0, ""});
h[{0, 0}] = 1;

while (!q.empty())
{
auto t = q.front(); q.pop();

if (t.a == c || t.b == c)
{
cout << t.step << endl;
for (int i = 0; i < t.s.size(); ++i)
cout << st[t.s[i] - '1'] << endl;
return;
}

if (h[{a, t.b}] != 1)
h[{a, t.b}] = 1, q.push({a, t.b, t.step + 1, t.s + "1"});
if (h[{t.a, b}] != 1)
h[{t.a, b}] = 1, q.push({t.a, b, t.step + 1, t.s + "2"});
if (h[{0, t.b}] != 1)
h[{0, t.b}] = 1, q.push({0, t.b, t.step + 1, t.s + "3"});
if (h[{t.a, 0}] != 1)
h[{t.a, 0}] = 1, q.push({t.a, 0, t.step + 1, t.s + "4"});

if (t.a >= b - t.b && h[{t.a - (b - t.b), b}] != 1) //a能把b装满
h[{t.a - (b - t.b), b}] = 1, q.push({t.a - (b - t.b), b, t.step + 1, t.s + "5"});
else if (t.a < b - t.b && h[{0, t.b + t.a}] != 1) //把a倒完也装不满
h[{0, t.b + t.a}] = 1, q.push({0, t.b + t.a, t.step + 1, t.s + "5"});
if (t.b >= a - t.a && h[{a, t.b - (a - t.a)}] != 1) //b能把a装满
h[{a, t.b - (a - t.a)}] = 1, q.push({a, t.b - (a - t.a), t.step + 1, t.s + "6"});
else if (t.b < a - t.a && h[{a + t.b, 0}] != 1) //把b倒完也装不满
h[{t.a + t.b, 0}] = 1, q.push({t.a + t.b, 0, t.step + 1, t.s + "6"});
}

puts("impossible");
}

int main()
{
cin >> a >> b >> c;

bfs();
return 0;
}


17小时前
#include <iostream>
#include <algorithm>

using namespace std;

int a, b;
string n;

int char_to_int(char x)
{
if (x >= 'A' && x <= 'F')
return x - 'A' + 10;
if (x >= 'a' && x <= 'f')
return x - 'a' + 10;
if (x >= '0' && x <= '9')
return x - '0';
}

char int_to_char(int x)
{
if (x >= 10)
return x - 10 + 'A';
return x + '0';
}

int first(string t, int n) //第一步，任意进制转10进制
{
int dec = 0;
for (int i = 0; i < t.size(); ++i)
dec = dec * n + char_to_int(t[i]);
return dec;
}

string second(int dec, int n) //第二步，十进制转任意进制
{
string res;
while (dec)
res += int_to_char(dec % n), dec /= n;
reverse(res.begin(), res.end()); //记住是反着的
return res;
}

int main()
{
cin >> a >> n >> b;
//把a进制数n转换成b进制数

cout << second(first(n, a), b) << endl;
return 0;
}


17小时前
#include <iostream>
#include <algorithm>

using namespace std;

int a, b;
string n;

int char_to_int(char x)
{
if (x >= 'A' && x <= 'F')
return x - 'A' + 10;
if (x >= 'a' && x <= 'f')
return x - 'a' + 10;
if (x >= '0' && x <= '9')
return x - '0';
}

char int_to_char(int x)
{
if (x >= 10)
return x - 10 + 'A';
return x + '0';
}

int first(string t, int n) //第一步，任意进制转10进制
{
int dec = 0;
for (int i = 0; i < t.size(); ++i)
dec = dec * n + char_to_int(t[i]);
return dec;
}

string second(int dec, int n) //第二步，十进制转任意进制
{
string res;
while (dec)
res += int_to_char(dec % n), dec /= n;
reverse(res.begin(), res.end()); //记住是反着的
return res;
}

int main()
{
cin >> a >> n >> b;
//把a进制数n转换成b进制数

cout << second(first(n, a), b) << endl;
return 0;
}


18小时前

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

using namespace std;

const int N = 110;

int n, T, u;
char s1[N], s2[N], s[2 * N], tmp[2 * N];

struct Node
{
string s;
int step;
};

void shuffle()
{
for (int i = 0, j = 1; i < n; j += 2, ++i)
tmp[j] = s1[i];
for (int i = 0, j = 0; i < n; j += 2, ++i)
tmp[j] = s2[i];

for (int i = 0; i < n; ++i)
s1[i] = tmp[i];
for (int i = n; i < 2 * n; ++i)
s2[i - n] = tmp[i];
}

bool check()
{
for (int i = 0; i < 2 * n; ++i)
if (tmp[i] != s[i])
return false;
return true;
}

string c2s(char c[], int n)
{
string t;
for (int i = 0; i < n; ++i)
t += c[i];
return t;
}

void bfs()
{
queue<Node> q;
unordered_map<string, int> h;

q.push({c2s(tmp, n + n), 0});
h[q.front().s] = 1;

while (!q.empty())
{
auto t = q.front(); q.pop();

if (check())
{
cout << u << ' ' << t.step << endl;
return;
}

shuffle();
if (h[c2s(tmp, 2 * n)] != 1)
q.push({c2s(tmp, 2 * n), t.step + 1}), h[q.front().s] = 1;
}

cout << u << ' ' << -1 << endl;
}

int main()
{
cin >> T;
for (u = 1; u <= T; ++u)
{
memset(tmp, 0, sizeof tmp);
cin >> n >> s1 >> s2 >> s;
bfs();
}
return 0;
}


18小时前
#include <iostream>
#include <queue>
#include <unordered_map>
#include <cstring>

using namespace std;

const int N = 1100;

int n, T, res, u;
char s1[N], s2[N], s[2 * N], tmp[2 * N];

struct Node
{
string s;
int step;
};

void shuffle()
{
for (int i = 0, j = 1; i < n; j += 2, ++i)
tmp[j] = s1[i];
for (int i = 0, j = 0; i < n; j += 2, ++i)
tmp[j] = s2[i];

for (int i = 0; i < n; ++i)
s1[i] = tmp[i];
for (int i = n; i < 2 * n; ++i)
s2[i - n] = tmp[i];
}

bool check()
{
for (int i = 0; i < 2 * n; ++i)
if (tmp[i] != s[i])
return false;
return true;
}

string c2s(char c[], int n)
{
string t;
for (int i = 0; i < n; ++i)
t += c[i];
return t;
}

void bfs()
{
queue<Node> q;
unordered_map<string, int> h;
res = -1;

q.push({c2s(tmp, n + n), 0});
h[q.front().s] = 1;

while (!q.empty())
{
auto t = q.front(); q.pop();

if (check())
{
cout << u << ' ' << t.step << endl;
return;
}
shuffle();
if (h[c2s(tmp, 2 * n)] != 1)
q.push({c2s(tmp, 2 * n), t.step + 1}), h[q.front().s] = 1;
}

cout << u << ' ' << -1 << endl;
}

int main()
{
cin >> T;
for (u = 1; u <= T; ++u)
{
memset(tmp, 0, sizeof tmp);
cin >> n >> s1 >> s2 >> s;
bfs();
}
return 0;
}


19小时前
#include <iostream>

using namespace std;

const int N = 30010;

int n, m, T;
int p[N], s[N], d[N];

int find(int x)
{
if (x == p[x])
return x;
int root = find(p[x]);
d[x] += d[p[x]];
return p[x] = root;
}

int main()
{
for (int i = 1; i < N; ++i)
p[i] = i, s[i] = 1;

scanf("%d", &m);
while (m--)
{
char op[2];
int a, b;
scanf("%s%d%d", op, &a, &b);

if (op[0] == 'M')
{
int pa = find(a), pb = find(b);
if (pa != pb)
{
d[pa] = s[pb];
s[pb] += s[pa];
p[pa] = pb;
}
}
else
{
int pa = find(a), pb = find(b);
if (pa != pb)
puts("-1");
else
printf("%d\n", max(0, abs(d[a] - d[b]) - 1));
}
}

return 0;
}


1天前
#include <iostream>
#include <queue>

using namespace std;

int n;
priority_queue<int, vector<int>, greater<int>> q;

//结论：WPL等于哈弗曼树上所有非叶结点权值之和

int main()
{
cin >> n;
while (n--)
{
int x;
cin >> x;
q.push(x);
}

int res = 0;
while (q.size() > 1)
{
auto a = q.top(); q.pop();
auto b = q.top(); q.pop();
res += a + b;
q.push(a + b);
}

cout << res << endl;
return 0;
}


1天前
#include <iostream>
#include <queue>

using namespace std;

int n;
priority_queue<int, vector<int>, greater<int>> q;

//结论：WPL等于哈弗曼树上所有非叶结点权值之和

int main()
{
cin >> n;
while (n--)
{
int x;
cin >> x;
q.push(x);
}

int res = 0;
while (q.size() > 1)
{
auto a = q.top(); q.pop();
auto b = q.top(); q.pop();
res += a + b;
q.push(a + b);
}

cout << res << endl;
return 0;
}


1天前
#include <iostream>
#include <unordered_map>

using namespace std;

//最多有1e5对关系，因此涉及2e5结点
const int N = 2e5 + 10;

struct Query
{
int x, y, e;
};

int n, m, T;
int p[N];
unordered_map<int, int> h;
Query query[N];

int get(int x)
{
if (!h.count(x))
h[x] = ++n;
return h[x];
}

int find(int x)
{
if (x == p[x])
return x;
return p[x] = find(p[x]);
}

int main()
{
scanf("%d", &T);
while (T--)
{
n = 0;
h.clear();
scanf("%d", &m);
for (int i = 0; i < m; ++i)
{
int x, y, e;
scanf("%d%d%d", &x, &y, &e);
query[i] = {get(x), get(y), e};
}

for (int i = 1; i <= n; ++i)
p[i] = i;

for (int i = 0; i < m; ++i)
if (query[i].e)
p[find(query[i].x)] = find(query[i].y);

bool has_conflict = false;
for (int i = 0; i < m; ++i)
if (!query[i].e)
{
int px = find(query[i].x), py = find(query[i].y);
if (px == py)
{
has_conflict = true;
break;
}
}

if (has_conflict)
puts("NO");
else
puts("YES");
}

return 0;
}



1天前
#include <iostream>
using namespace std;

const int N = 10010;

int n, m, vol;
int v[N], w[N];
int f[N], p[N];

int find(int x)
{
if (x == p[x])
return x;
return p[x] = find(p[x]);
}

int main()
{
cin >> n >> m >> vol;
for (int i = 0; i < n; ++i)
p[i] = i;
for (int i = 0; i < n; ++i)
cin >> v[i] >> w[i];

while (m--)
{
int a, b;
cin >> a >> b;
--a, --b;
int pa = find(a), pb = find(b);
if (pa != pb)
{
v[pa] += v[pb];
w[pa] += w[pb];
p[pb] = pa;
}
}

for (int i = 0; i < n; ++i)
if (p[i] == i)
for (int j = vol; j >= v[i]; --j)
f[j] = max(f[j], f[j - v[i]] + w[i]);

cout << f[vol] << endl;
return 0;
}