CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
第一次练习团队配合。五小时三人共做出 ABCIK 五题。配合有待加强。
Auxiliary Project
最开始是用 DP 做的。
#include <fstream>
using namespace std;
int work(int k)
{
static int f[1000001] = {0}, cost[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
if (k < 0)
return 0;
if (f[k])
return f[k];
for (int i = 0; i != 10; ++i)
if (work(k - cost[i]) > 0 || k == cost[i])
f[k] = max(f[k], work(k - cost[i]) + i);
return f[k];
}
int main()
{
int n;
ifstream fin("auxiliary.in");
ofstream fout("auxiliary.out");
fin >> n;
fout << work(n);
}
其实这题可以贪心：尽量用性价比最高的 7，多余的用 4 和 1 去补。
int work(int k)
{
return k % 3 == 1 ? k / 3 * 7 - 3 : k % 3 == 2 ? k / 3 * 7 + 1 : k / 3 * 7;
}
Boolean Satisfability
做的时候没注意每个标识符长度为 1，导致代码长了很多。
#include <fstream>
#include <string>
#include <set>
using namespace std;
ifstream fin("boolean.in");
ofstream fout("boolean.out");
set<string> b[3];
bool flag = 1, sign = 0;
int main()
{
for (string s, ss; getline(fin, s, '|');)
{
while (!isalpha(s.back()))
s.pop_back(); //不加这个有的样例过不掉
sign = s[0] == '~';
ss = s.substr(sign);
b[sign].insert(ss);
if (b[!sign].find(ss) != b[!sign].end())
flag = 0;
}
b[2].insert(b[0].begin(), b[0].end());
b[2].insert(b[1].begin(), b[1].end());
fout << (1LL << b[2].size()) - flag;
}
可以用 bitset 和位运算弄个大新闻。
#include <fstream>
#include <bitset>
using namespace std;
ifstream fin("boolean.in");
ofstream fout("boolean.out");
bitset<'z' - 'A' + 1> b[3];
bool flag = 1, sign = 0;
int main()
{
for (char ch; fin >> ch;)
{
if (isalpha(ch))
{
b[sign][ch - 'A'] = 1;
if (b[!sign][ch - 'A'])
flag = 0;
sign = 0;
}
if (ch == '~')
sign = 1;
}
b[2] = b[0] | b[1];
fout << (1LL << b[2].count()) - flag;
}
Consonant Fencity
暴力 dfs。算consonant fencity的时候应当边搜索边计算，如果等搜索到达终点再从头计算会 TLE。
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("consonant.in");
ofstream fout("consonant.out");
string s, con("bcdfghjklmnpqrstvxz");
vector<vector<int>> adjmap(con.size(), vector<int>(con.size(), 0));
vector<bool> state(con.size(), 0), ans_state(con.size(), 0);
int v = 0, ans_v = 0;
void dfs(int k)
{
if (k == con.size())
{
if (ans_v < v)
{
ans_v = v;
ans_state = state;
}
return;
}
dfs(k + 1);
state[k] = 1;
int t_v = v;
for (int i = 0; i != con.size(); i++)
if (i != k)
v += (state[i] ? -1 : 1) * adjmap[i][k];
dfs(k + 1);
state[k] = 0;
v = t_v;
}
int main()
{
fin >> s;
for (int i = 1, p = con.find(s[0]), q; i != s.size(); ++i, p = q)
{
q = con.find(s[i]);
if (p != con.npos && q != con.npos)
{
++adjmap[p][q];
++adjmap[q][p];
}
}
dfs(0);
for (int i = 0, p; i != s.size(); ++i)
{
p = con.find(s[i]);
fout << char(p != con.npos && ans_state[p] ? toupper(s[i]) : s[i]);
}
}
Equal Numbers
这 n 个数第 n-1 次操作后全变成他们的最小公倍数 有两种贪心策略：
- 每次在未处理的数中选择出现次数最少的数变成最小公倍数。
- 每次在倍数仍在这组数中的数中选择出现次数最少的数变成其倍数。 最优方案由以上两种策略产生。由于局部最优的方案不一定整体最优，因此将两种策略并行，每次输出其中最优的方案。
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("equal.in");
ofstream fout("equal.out");
vector<int> a, b, d(1e6 + 1, 0);
int n;
int main()
{
fin >> n;
for (int i = 0, t; i < n; ++i)
{
fin >> t;
++d[t];
}
for (int i = 1; i < d.size(); ++i)
if (d[i])
{
a.push_back(d[i]);
for (int j = 2 * i; j < d.size(); j += i)
if (d[j])
{
b.push_back(d[i]);
break;
}
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
for (int i = 0, p = 0, q = 0, sp = 0, sq = 0; i <= n; ++i)
{
while (p < a.size() && sp + a[p] <= i)
sp += a[p++];
while (q < b.size() && sq + b[q] <= i)
sq += b[q++];
fout << a.size() - max(p - 1, q) << ' ';
}
}
Fygon 2.0
dfs。
#include <cstdio>
#include <map>
#include <bitset>
typedef long long ll;
typedef std::bitset<32> Bs;
Bs bs[32], t;
void add(char a, char b)
{
a = (a == '1' ? 0 : a - 'a' + 1);
b = (b == '1' ? 0 : b - 'a' + 1);
bs[a][b] = 1;
bs[a][a] = 1;
bs[b][b] = 1;
}
ll dfs(Bs x)
{
static std::map<ll, ll> f;
if (f.find(x.to_ulong()) != f.end())
return f[x.to_ulong()];
ll &ret = f[x.to_ulong()] = x.none();
for (int i = 0; i < 32; ++i)
if ((x & bs[i]) == (1 << i))
{
x[i] = 0;
ret += dfs(x);
x[i] = 1;
}
return ret;
}
ll gcd(ll a, ll b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
freopen("fygon20.in", "r", stdin);
freopen("fygon20.out", "w", stdout);
int m;
scanf("%d", &m);
for (char a, b, c; m--;)
{
scanf(" for %c in range(%c, %c):", &a, &b, &c);
add(b, a);
add(a, c);
}
add('1', 'n');
for (int i = 0; i < 32; ++i)
for (int j = 0; j < 32; ++j)
if (bs[j][i])
bs[j] |= bs[i];
for (int i = 0; i < 32; ++i)
{
if (bs[i].none())
t[i] = 1;
for (int j = i + 1; j < 32; ++j)
if (bs[i] == bs[j])
t[j] = 1;
}
ll an = dfs(t.flip()), ad = 1, ag;
for (int i = 2; i < t.count() - 1; ++i)
ad *= i;
ag = gcd(an, ad);
printf("%d %lld/%lld", t.count() - 2, an / ag, ad / ag);
}
Intelligence in Perpendicularia
求多边形多边形内部可以看到，但在外部看不到的线条长度。 只要拿总周长减去最小外接矩形周长即可。
#include <fstream>
using namespace std;
ifstream fin("intel.in");
ofstream fout("intel.out");
int n, ans = 0, x[1024], y[1024];
int abs(int n)
{
return n < 0 ? -n : n;
}
int main()
{
fin >> n;
x[1023] = y[1023] = -1e7;
x[1022] = y[1022] = 1e7;
for (int i = 0; i != n; ++i)
{
fin >> x[i] >> y[i];
x[1023] = max(x[1023], x[i]);
y[1023] = max(y[1023], y[i]);
x[1022] = min(x[1022], x[i]);
y[1022] = min(y[1022], y[i]);
}
for (int i = 0; i != n; ++i)
ans += abs(x[(i + 1) % n] + y[(i + 1) % n] - x[i] - y[i]);
fout << ans - 2 * (x[1023] + y[1023] - x[1022] - y[1022]);
}
Kotlin Island
样例是骗人的。例如，第二个样例其实不做任何处理就行。
其次，只要处理奇数行和奇数列（编号从 0 开始）即可。
f[i][j] 表示将前 i 个奇数行和 j 个奇数列被充水后剩下的联通块数量，容易列出转移方程。转移的时候如果发现 f[i][j]==n 就可以输出了。
#include <fstream>
using namespace std;
ifstream fin("kotlin.in");
ofstream fout("kotlin.out");
int h, w, n, f[64][64] = {1, 0};
int main()
{
fin >> h >> w >> n;
for (int i = 0; 2 * i < h; ++i)
for (int j = 0; 2 * j < w; ++j)
{
if (i)
f[i][j] = max(f[i][j], f[i - 1][j] + j + 1);
if (j)
f[i][j] = max(f[i][j], f[i][j - 1] + i + 1);
if (f[i][j] == n)
{
for (int x = 0; x < h; ++x, fout << '\n')
for (int y = 0; y < w; ++y)
fout << ((x % 2 && x / 2 < i) ||
(y % 2 && y / 2 < j)
? '#'
: '.');
return 0;
}
}
fout << "Impossible";
}