AcWing 1118. 分成互质组
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 15;
int n;
int p[N];
int group[N][N];
bool st[N];
int ans = N;
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 false;
return true;
}
void dfs(int g, int gc, int tc, int start)
{
if (g >= ans) return ;
if (tc == n) ans = g;
bool flag = true;
for (int i = start; i < n; i++)
if (!st[i] && check(group[g], gc, i))
{
st[i] = true;
group[g][gc] = i;
dfs(g, gc + 1, tc + 1, i + 1);
st[i] = false;
flag = false;
}
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 << endl;
return 0;
}
165. 小猫爬山
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;
int n, m;
int w[N];
int sum[N];
int ans = N;
void dfs(int u, int k)
{
if (k >= ans) return ;
if (k < ans && 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 << endl;
return 0;
}
AcWing 166. 数独
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 9, M = 1 << N;
int ones[M], map[M];
int row[N], col[N], cell[3][3];
char str[100];
void init()
{
for (int i = 0; i < N; i++)
row[i] = col[i] = (1 << N) - 1;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
cell[i][j] = (1 << N) - 1;
}
void draw(int x, int y, int t, bool is_set)
{
if (is_set) str[x * N + y] = '1' + t;
else str[x * N + 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 true;
int minv = 10;
int x, y;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (str[i * N + j] == '.')
{
int state = get(i, j);
if (ones[state] < minv)
{
minv = ones[state];
x = i, y = j;
}
}
int state = get(x, y);
for (int i = state; i; i -= lowbit(i))
{
int t = map[lowbit(i)];
draw(x, y, t, true);
if (dfs(cnt - 1)) return true;
draw(x, y, t, false);
}
return false;
}
int main()
{
for (int i = 0; i < N; i++) map[1 << i] = i;
for (int i = 0; i < 1 << N; i++)
for (int j = 0; j < N; j++)
ones[i] += i >> j & 1;
while (cin >> str, str[0] != 'e')
{
init();
int cnt = 0;
for (int i = 0, k = 0; i < N; i++)
for (int j = 0; j < N; j++, k++)
if (str[k] != '.')
{
int t = str[k] - '1';
draw(i, j, t, true);
}
else cnt++;
dfs(cnt);
puts(str);
}
return 0;
}
AcWing 167. 木棒
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 70;
int n;
int w[N], sum, length;
bool st[N];
bool dfs(int u, int s, int start)
{
if (u * length == sum) return true;
if (s == length) return dfs(u + 1, 0, 0);
for (int i = start; i < n; i++)
{
if (st[i]) continue;
if (s + w[i] > length) continue;
st[i] = true;
if (dfs(u, s + w[i], i + 1)) return true;
st[i] = false;
if (!s) return false;
if (s + w[i] == length) return false;
int j = i;
while (j < n && w[j] == w[i]) j++;
i = j - 1;
}
return false;
}
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);
length = 1;
while (true)
{
if (sum % length == 0 && dfs(0, 0, 0))
{
cout << length << endl;
break;
}
length++;
}
}
return 0;
}#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 70;
int n;
int w[N], sum, length;
bool st[N];
bool dfs(int u, int s, int start)
{
if (u * length == sum) return true;
if (s == length) return dfs(u + 1, 0, 0);
for (int i = start; i < n; i++)
{
if (st[i]) continue;
if (s + w[i] > length) continue;
st[i] = true;
if (dfs(u, s + w[i], i + 1)) return true;
st[i] = false;
if (!s) return false;
if (s + w[i] == length) return false;
int j = i;
while (j < n && w[j] == w[i]) j++;
i = j - 1;
}
return false;
}
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);
length = 1;
while (true)
{
if (sum % length == 0 && dfs(0, 0, 0))
{
cout << length << endl;
break;
}
length++;
}
}
return 0;
}