Ethanyyc

$\Huge\color{red}{学术}$模式：不发帖，不私聊

3083

dushucheng0901

Ariel0501

Philip

Finn2009

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

using namespace std;

const int N = 2510, M = 6200 * 2 + 10;

int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx;
int d[N], q[N];
bool st[N];

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

void spfa()
{
memset(d, 0x3f, sizeof d);
d[S] = 0;

int hh = 0, tt = 1;
q[0] = S, st[S] = true;

while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;

for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (d[j] > d[t] + w[i])
{
d[j] = d[t] + w[i];
if (!st[j])
{
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
}

int main()
{
cin >> n >> m >> S >> T;

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

spfa();

cout << d[T] << endl;

return 0;
}



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

int op[8][7] =
{
{0, 2, 6, 11, 15, 20, 22},
{1, 3, 8, 12, 17, 21, 23},
{10, 9, 8, 7, 6, 5, 4},
{19, 18, 17, 16, 15, 14, 13},
{23, 21, 17, 12, 8, 3, 1},
{22, 20, 15, 11, 6, 2, 0},
{13, 14, 15, 16, 17, 18, 19},
{4, 5, 6, 7, 8, 9, 10}
};

int opt[8] = {5, 4, 7, 6, 1, 0, 3, 2};
int ctr[8] = {6, 7, 8, 11, 12, 15, 16, 17};

int q[24];
int pth[100];

int f()
{
static int s[4];
memset(s, 0, sizeof s);
for (int i = 0; i < 8; i ++ )
s[q[ctr[i]]] ++ ;

int maxv = 0;

for (int i = 1; i <= 3; i ++ )
maxv = max(maxv, s[i]);

return 8 - maxv;
}

void opr(int x)
{
int t = q[op[x][0]];
for (int i = 0; i < 6; i ++ )
q[op[x][i]] = q[op[x][i + 1]];
q[op[x][6]] = t;
}

bool dfs(int dep, int mx, int last)
{
if (dep + f() > mx)
return 0;

if (f() == 0)
return 1;

for (int i = 0; i < 8; i ++ )
{
if (last != opt[i])
{
opr(i);
pth[dep] = i;
if (dfs(dep + 1, mx, i))
return 1;
opr(opt[i]);
}
}

return 0;
}

int main()
{
while (cin >> q[0], q[0])
{
for (int i = 1; i < 24; i ++ )
cin >> q[i];

int dep = 0;
while (!dfs(0, dep, -1)) dep ++ ;

if (!dep) printf("No moves needed");
else
{
for (int i = 0; i < dep; i ++ ) printf("%c", 'A' + pth[i]);
}
printf("\n%d\n", q[6]);
}

return 0;
}



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

int n;

int q[15];
int w[5][15];

int f()
{
int cnt = 0;

for (int i = 0; i + 1 < n; i ++ )
{
if (q[i + 1] != q[i] + 1)
cnt ++ ;
}

return (cnt + 2) / 3;
}

bool check()
{
for (int i = 0; i + 1 < n; i ++ )
{
if (q[i + 1] != q[i] + 1)
return 0;
}

return 1;
}

bool dfs(int dep, int mx)
{
if (dep + f() > mx)
return 0;

if (check())
return 1;

for (int len = 1; len <= n; len ++ )
{
for (int l = 0; l + len - 1 < n; l ++ )
{
int r = l + len - 1;

for (int k = r + 1; k < n; k ++ )
{
memcpy(w[dep], q, sizeof q);

int x, y;

for (x = r + 1, y = l; x <= k; x ++, y ++ )
q[y] = w[dep][x];

for (x = l; x <= r; x ++, y ++ )
q[y] = w[dep][x];

if (dfs(dep + 1, mx))
return 1;

memcpy (q, w[dep], sizeof q);
}
}
}

return 0;
}

int main()
{
int T;
cin >> T;

while (T -- )
{
cin >> n;

for (int i = 0; i < n; i ++ )
cin >> q[i];

int dep = 0;

while (dep < 5 && !dfs(0, dep))
dep ++ ;

if (dep >= 5)
puts("5 or more");
else
cout << dep << endl;
}

return 0;
}


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

int n, m, k;
int g[50];
int w[1 << 24];

int cnt = 0;
int ans;

void dfs (int u, int s)
{
if (u == k)
{
w[cnt ++ ] = s;

return ;
}

if ((long long)s + g[u] <= m)
dfs (u + 1, s + g[u]);

dfs (u + 1, s);
}

void dfs2 (int u, int s)
{
if (u == n)
{
int l = 0, r = cnt - 1;

while (l < r)
{
int mid = l + r + 1 >> 1;

if (w[mid] + (long long)s <= m)
l = mid;
else
r = mid - 1;
}

if (w[l] + (long long)s <= m)
ans = max(ans, w[l] + s);

return ;
}

if ((long long)s + g[u] <= m)
dfs2(u + 1, s + g[u]);

dfs2 (u + 1, s);
}

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

for (int i = 0; i < n; i ++ )
cin >> g[i];

sort (g, g + n);
reverse (g, g + n);

k = n / 2;
dfs(0, 0);

sort(w, w + cnt);

int t = 1;

for (int i = 1; i < cnt; i ++ )
{
if (w[i] != w[i - 1])
w[t ++ ] = w[i];
}

cnt = t;

dfs2(k, 0);

cout << ans;

return 0;
}


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

int n;

int pth[105];

bool dfs(int u, int k)
{
if (u == k)
return pth[u - 1] == n;

bool vis[105] = {0};

for (int i = u - 1; i >= 0; i -- )
{
for (int j = i; j >= 0; j -- )
{
int s = pth[i] + pth[j];

if (s > n || s <= pth[u - 1] || vis[s])
continue;

vis[s] = 1;

pth[u] = s;

if (dfs(u + 1, k))
return 1;
}
}

return 0;
}

int main()
{
pth[0] = 1;

while (cin >> n, n)
{
int k = 1;

while (!dfs(1, k))
k ++ ;

for (int i = 0; i < k; i ++ )
cout << pth[i] << " ";

cout << endl;
}

return 0;
}


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

int n, m;

int minv[25];
int mins[25];

int R[25], H[25];

int ans = 1e9;

void dfs (int u, int v, int s)
{
if (v + minv[u] > n)
return;

if (s + mins[u] >= ans)
return;

if (s + 2 * (n - v) / R[u + 1] >= ans)
return;

if (!u)
{
if (v == n)
ans = s;

return;
}

for (int r = min(R[u + 1] - 1, (int)sqrt(n - v)); r >= u; r -- )
{
for (int h = min(H[u + 1] - 1, (n - v) / r / r); h >= u; h -- )
{
int t = 0;

if (u == m)
t = r * r;

R[u] = r;
H[u] = h;

dfs(u - 1, v + r * r * h, s + 2 * r * h + t);
}
}
}

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

for (int i = 1; i <= m; i ++ )
{
minv[i] = minv[i - 1] + i * i * i;
mins[i] = mins[i - 1] + 2 * i * i;
}

R[m + 1] = H[m + 1] = 1e9;

dfs (m, 0, 0);

if (ans == 1e9)
ans = 0;

cout << ans;

return 0;
}



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

int n;

int w[70];
int sum;
int l;

bool st[70];

bool dfs(int u, int cur, int s)
{
if (u * l == sum)
return 1;

if (cur == l)
return dfs(u + 1, 0, 0);

for (int i = s; i < n; i ++ )
{
if (st[i] || cur + w[i] > l)
continue;

st[i] = 1;
if (dfs(u, cur + w[i], i + 1))
return 1;

st[i] = 0;

if (!cur || cur + w[i] == l)
return 0;

int j = i;
while (j < n && w[j] == w[i]) j ++ ;
i = j - 1;
}

return 0;
}

int main()
{
while (cin >> n, n)
{
memset(st, 0, sizeof st);

sum = 0;

for (int i = 0; i < n; i ++ )
{
cin >> w[i];

sum += w[i];
}

sort(w, w + n);
reverse(w, w + n);

l = 1;
while (1)
{
if (sum % l == 0 && dfs(0, 0, 0))
{
cout << l << endl;
break;
}

l ++ ;
}
}

return 0;
}



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

int ones[1 << 9];

int mp[1 << 9];

int row[9], col[9];

int cell[3][3];

char str[100];

void init()
{
for (int i = 0; i < 9; i ++ )
row[i] = col[i] = (1 << 9) - 1;

for (int i = 0; i < 3; i ++ )
{
for (int j = 0; j < 3; j ++ )
cell[i][j] = (1 << 9) - 1;
}
}

void draw(int x, int y, int t, bool is_set)
{
if (is_set)
str[x * 9 + y] = '1' + t;
else
str[x * 9 + y] = '.';

int v = 1 << t;

if (!is_set)
v = -v;

row[x] -= v;
col[y] -= v;

cell[x / 3][y / 3] -= v;
}

int lowbit(int x)
{
return x & -x;
}

int get(int x, int y)
{
return row[x] & col[y] & cell[x / 3][y / 3];
}

bool dfs(int cnt)
{
if (!cnt)
return 1;

int minv = 10;

int x, y;

for (int i = 0; i < 9; i ++ )
{
for (int j = 0; j < 9; j ++ )
{
if (str[i * 9 + j] == '.')
{
int st = get(i, j);

if (ones[st] < minv)
{
minv = ones[st];
x = i, y = j;
}
}
}
}

int st = get(x, y);

for (int i = st; i; i -= lowbit(i))
{
int t = mp[lowbit(i)];

draw(x, y, t, 1);

if (dfs(cnt - 1))
return 1;

draw(x, y, t, 0);
}

return 0;
}

int main()
{
for (int i = 0; i < 9; i ++ )
mp[1 << i] = i;

for (int i = 0; i < 1 << 9; i ++ )
{
for (int j = 0; j < 9; j ++ )
ones[i] += i >> j & 1;
}

while (cin >> str, str[0] != 'e')
{
init();

int cnt = 0;

for (int i = 0, k = 0; i < 9; i ++ )
{
for (int j = 0; j < 9; j ++, k ++ )
{
if (str[k] != '.')
{
int t = str[k] - '1';
draw(i, j, t, true);
}
else
cnt ++ ;
}
}

dfs(cnt);

puts(str);
}

return 0;
}



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

int n, m;

int w[20];

int sum[20];

int ans = 20;

void dfs (int u, int k)
{
if (k >= ans)
return;

if (u == n)
{
ans = k;

return;
}

for (int i = 0; i < k; i ++ )
{
if (sum[i] + w[u] <= m)
{
sum[i] += w[u];

dfs (u + 1, k);

sum[i] -= w[u];
}
}

sum[k] = w[u];

dfs (u + 1, k + 1);

sum[k] = 0;
}

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

for (int i = 0; i < n; i ++ )
cin >> w[i];

sort (w, w + n);

reverse (w, w + n);

dfs (0, 0);

cout << ans;

return 0;
}


Ethanyyc
12天前
#include <bits/stdc++.h>
using namespace std;

int n;
int p[10];
int group[10][10];
bool st[10];
int ans = 10;

int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}

bool check(int group[], int gc, int i)
{
for (int j = 0; j < gc; j ++ )
{
if (gcd(p[group[j]], p[i]) > 1)
return 0;
}
return 1;
}

void dfs(int g, int gc, int tc, int start)
{
if (g >= ans)
return;

if (tc == n)
ans = g;

bool flag = 1;

for (int i = start; i < n; i ++ )
{
if (!st[i] && check(group[g], gc, i))
{
st[i] = 1;
group[g][gc] = i;
dfs(g, gc + 1, tc + 1, i + 1);
st[i] = 0;

flag = 0;
}
}

if (flag)
dfs(g + 1, 0, tc, 0);
}

int main()
{
cin >> n;

for (int i = 0; i < n; i ++ )
cin >> p[i];

dfs(1, 0, 0, 0);

cout << ans;
return 0;
}