B. Button lock
题意：有 (d) 个 01 按键以及一个 reset 按键，你需要把所有题目给定的 (n) 个密码全部表示一遍。只有按下 reset 按键后才能使所有 01 按键弹回。试使得按键次数最少。
做法：可以观察到 (ans = sum_{u in endvertex} (bitcount(u) + 1) - 1)，接下来要尽可能使 ans 最小。
二分图匹配算法可以保证其路径数最少，接下来我们考虑二分图匹配与匈牙利算法。
先设左边的点集为 S，右边的点集为 T。假如做完了二分图匹配，那么若左边点集 S 中有未匹配到的点，那么说明这个点是一条路径的结尾。这样，答案变成了使得左边点集 S 中未匹配的点的 1 的个数之和最少。
由于在匈牙利算法中，我们依次枚举左侧点集中的点，一个之前匹配到的点不可能再失配，而一个失配的点在之后还是失配。这样，可以贪心地将所有密码按照 1 的个数从大到小排序，然后再做匈牙利算法。二分图匹配算法可以使路径数最少，而上述排序使得失配的左侧点的对答案的贡献和尽可能小。
时间复杂度是 (O(VE) = O(2^d3^d) = O(6^d))
上面少证明了一个东西：是否 ans 最小的时候满足路径数最少呢？反证法，若 ans 最小的时候路径数不是最小的，那么可想而知是在二分图匹配中有一些更多的点失配了，在最大匹配的时候失配的点仍然失配；或是这个点虽然匹配上了，但是含有更多 1 的点失配了。这样答案只会比满足路径数最少的条件时的答案更大。
#include <bits/stdc++.h>
using namespace std;
const int N = 1030;
const int D = 15;
#define IL inline
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define dbg1(x) cout << #x << " = " << x << ", "
#define dbg2(x) cout << #x << " = " << x << endl
int d, n;
int a[N];
IL bool in(int x, int y) {
return (x & y) == x;
}
IL int bitcount(int x) {
return x == 0 ? 0 : bitcount(x >> 1) + (x & 1);
}
struct Hungary {
int n, m;
int Left[N], Right[N];
bool S[N], T[N];
vector<int> G[N];
IL void init(int n, int m) {
this -> n = n; this -> m = m;
fill(Left, Left + 1 + m, 0);
fill(Right, Right + 1 + n, 0);
fill(S, S+n+1, 0);
fill(T, T+m+1, 0);
for(int i=1;i<=n;i++) G[i].clear();
}
IL void AddEdge(int u, int v) {
G[u].pb(v);
}
bool match(int u) {
//dbg2(u);
S[u] = true;
for(auto v : G[u]) if(!T[v]) {
//dbg1(u); dbg2(v);
T[v] = true;
if(Left[v] == 0 || match(Left[v])) {
Left[v] = u; Right[u] = v;
return true;
}
}
return false;
}
int gao() {
int ans = 0;
fill(Left, Left+1+m, 0);
fill(Right, Right + 1 + n, 0);
for(int i=1;i<=n;i++) {
fill(T, T+1+m, 0);
if(match(i)) ans++;
}
return ans;
}
vector<int> ans;
int lb(int x) { return x & (-x);}
void dfs(int u) {
int v = Right[u];
//dbg1(u); dbg2(v);
if(v == 0) { ans.pb(0); return;}
for(int val = (a[u] ^ a[v]), j = __lg(val); val; val -= (1 << j), j = __lg(val)) {
//dbg1(val); dbg2(j);
ans.pb(d - j);
}
dfs(v);
}
void solve() {
//puts("wtf");
int matchcnt = gao();
//dbg1(matchcnt);
for(int i=1;i<=n;i++) {
if(Left[i] != 0) continue;
for(int val = a[i], j = __lg(val); val; val -= (1 << j), j = __lg(val)) {
//dbg1(i); dbg1(val); dbg2(j);
ans.pb(d - j);
}
dfs(i);
}
printf("%d
", (int)ans.size()-1);
for(int i=0;i<(int)ans.size()-1;i++) {
if(ans[i] == 0) putchar('R');
else printf("%d", ans[i] - 1);
printf("%c", "
"[i == (int)ans.size() - 2]);
}
}
};
Hungary lpr;
int main() {
//freopen("B2.in", "r", stdin);
//freopen("B2.out", "w", stdout);
scanf("%d%d", &d, &n);
lpr.init(n, n);
for(int i=1;i<=n;i++) {
for(int j=1;j<=d;j++) {
int v; scanf("%1d", &v);
a[i] = (a[i] << 1) | v;
}
}
sort(a+1, a+1+n, [](int a, int b) { return bitcount(a) > bitcount(b);});
//for(int i=1;i<=n;i++) {dbg1(i); dbg2(a[i]);}
for(int i=1;i<=n;i++) {
for(int j=1;j<i;j++) {
if(!in(a[i], a[j])) continue;
lpr.AddEdge(i, j);
}
}
lpr.solve();
return 0;
}
E. Equilibrium Point //
题意：略
前置知识：多边形的重心。每个三角形的
做法：可以发现合法括号序列的个数是卡特兰数。在 n = 18 的时候，卡特兰数为 477638700。那么，是否可以使用类似卡特兰数定义式的方式去做这个题呢？PS：(f(n+1) = f(0)f(n) + f(1)f(n-1) + ... + f(n)f(0))
然后可以发现似乎有一些情况下重心是一样的。也就是说可以把一些重心一样的括号序列去掉。
由卡特兰递推式，我们考虑现在有 L 和 R 两个括号序列，那么接下来我们将它们合并起来，新的括号序列的重心是什么样子的呢？可以发现新的括号序列跟原来的括号序列所围成的面积 (m_L, m_R)，原来的重心 ((x_L, y_L), (x_R, y_R))，以及 L 的长度 (2i) 相关。
[m_{new} = m_L + m_R \
x_{new} = x_L frac{m_L}{m_{new}} + (x_R+2i) frac{m_R}{m_{new}} \
y_{new} = y_L frac{m_L}{m_{new}} + y_R frac{m_R}{m_{new}}
]
还有一种情况是假如现在只有 L 括号序列，那么新的括号序列为 (L)
[m_{new} = m_L + 2i - 1 \
x_{new} = (x_L + 1) frac{m_L}{m_{new}} + i frac{2i-1}{m_{new}} \
y_{new} = (y_L + 1) frac{m_L}{m_{new}} + frac{i - frac{2}{3}}{2i-1} cdot frac{2i-1}{m_{new}}
]
也就是说，我们需要搞出来有 (i) 对括号的所有三元组 ((m, x, y)) 。通过类似卡特兰数定义式的枚举方法，可以预处理出来所有有 (i) 对括号情况下的三元组 ((m,x,y))。为了使得三元组唯一，请使用手写哈希表而不是STL，否则会TLE。这样，跑完之后发现只枚举了 79079257 次。即可解开此题。
另外，由于跑三元组的时候一方面由于精度问题，另一方面由于运算速度问题，最好避免使用浮点数。所以在维护三元组的时候，我们维护的东西其实是 ((m, mx, 3my))，具体式子请自行带入上方的式子推一推。
#include <bits/stdc++.h>
using namespace std;
#define mk make_pair
#define dbg1(x) cout << #x << " = " << x << ", "
#define dbg2(x) cout << #x << " = " << x << endl
typedef tuple<int, int, int> tiii;
typedef pair<tiii, tiii> pi6;
typedef long long ll;
const int mod = 10000007;
int cnt = 0;
int n;
double x, y;
struct Hash_table {
int n, now;
int hd[mod];
int nxt[mod];
int tim[mod];
ll v[mod];
void init() { n = 0; now++;}
bool insert(ll val) {
int s = val % mod;
if(tim[s] != now) { tim[s] = now; hd[now] = 0;}
for(int i=hd[s]; i!=0; i=nxt[i]) {
if(v[i] == val) return false;
}
nxt[n + 1] = hd[s];
v[n + 1] = val;
hd[s] = ++n;
return true;
}
}HASH;
vector<tuple<int, int, int> > a[20];
string solve(int i, tiii p) {
if(i == 0) return "";
for(auto b : a[i-1]) {
int ml = get<0>(b), xl = get<1>(b), yl = get<2>(b);
int mnew = ml + 2 * i - 1;
int xnew = xl + ml + i * (2 * i - 1);
int ynew = yl + 3 * ml + 3 * i - 2;
if(tiii(mnew, xnew, ynew) == p) {
return "(" + solve(i - 1, b) + ")";
}
}
for(int j=1;j<i;j++) {
for(auto b1 : a[j]) for(auto b2 : a[i-j]) {
int ml = get<0>(b1), mr = get<0>(b2);
int xl = get<1>(b1), xr = get<1>(b2);
int yl = get<2>(b1), yr = get<2>(b2);
int mnew = ml + mr;
int xnew = xl + xr + 2 * j * mr;
int ynew = yl + yr;
if(tiii(mnew, xnew, ynew) == p) {
return solve(j, b1) + solve(i - j, b2);
}
}
}
assert(0);
}
void add(int i, int mm, int xx, int yy) {
long long v = mm * (1ll << 40ll) + xx * (1ll << 20ll) + yy;
if(HASH.insert(v)) a[i].push_back(tiii(mm, xx, yy));
}
int main() {
#ifdef LOCAL
freopen("E.in", "r", stdin);
// freopen("E.out", "w", stdout);
#endif
clock_t aa = clock();
a[0].push_back(tiii(0, 0, 0));
for(int i=1;i<=18;i++) {
HASH.init();
for(int j=1;j<i;j++) { // the size of left bracket sequence.
for(auto b1 : a[j]) for(auto b2 : a[i-j]) {
int ml = get<0>(b1), mr = get<0>(b2);
int xl = get<1>(b1), xr = get<1>(b2);
int yl = get<2>(b1), yr = get<2>(b2);
int mnew = ml + mr;
int xnew = xl + xr + 2 * j * mr;
int ynew = yl + yr;
add(i, mnew, xnew, ynew);
}
cnt += a[j].size() * a[i-j].size();
}
// ( sequence )
for(auto b : a[i-1]) {
int ml = get<0>(b), xl = get<1>(b), yl = get<2>(b);
int mnew = ml + 2 * i - 1;
int xnew = xl + ml + i * (2 * i - 1);
int ynew = yl + 3 * ml + 3 * i - 2;
add(i, mnew, xnew, ynew);
}
cnt += a[i-1].size();
dbg1(i); dbg1(a[i].size()); dbg2(cnt);
}
clock_t b = clock();
// cerr << "running " << b - aa << "ms
";
scanf("%d%lf%lf", &n, &x, &y);
n /= 2;
for(auto b : a[n]) {
int bm = get<0>(b), bx = get<1>(b), by = get<2>(b);
double xx = 1.0 * bx / bm, yy = 1.0 / 3.0 * by / bm;
if(fabs(xx - x) + fabs(yy - y) <= 1e-8) {
printf("%s
", solve(n, b).c_str());
return 0;
}
}
return 0;
}
I. Is It Rated?
题意：略
做法：神奇的做法。算法名称叫做 Weighted Majority Algorithm，也可以百度天气预测问题。但是百度到的证明的数学符号似乎都崩了，所以我看不懂这算法是咋证明的……
代码实现中是给每一个人赋值一个他这一轮的可信权值，然后对 n 个人遍历一遍得出这一轮选 0 的概率。然后再整一个 ([0,1]) 的随机数去跟上面的概率比对选 0/1.
这一轮结束后，如果对了那么他的可信权值不用管，否则他的可信权值乘一个系数 (alpha)。题解中说 (frac{1}{2} < alpha < frac{19}{20})。代码中取的 0.8。
#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 5;
int n, m;
char s[N];
long double a[N];
int main() {
srand(time(0));
scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++) a[i] = 1e18;
for(int i=1;i<=m;i++) {
scanf("%s", s + 1); getchar();
long double tot0 = 0;
long double tot = 0;
for(int j=1;j<=n;j++) {
if(s[j] == '0') tot0 += a[j];
tot += a[j];
}
if(rand() * tot < tot0 * RAND_MAX) putchar('0');
else putchar('1');
putchar(10);
fflush(stdout);
char ans; ans = getchar();
for(int j=1;j<=n;j++) if(s[j] != ans) {
a[j] *= 0.8;
}
}
return 0;
}
J. Japanese Game
题意：略
做法：
假如说现在有 profile 了，怎么弄出来 mask？
显然可以得出按照最左边放置的放法，然后再得出按照最右边放置的放法，然后看看哪些一直都是 # 的方块仍然还是属于一个大 # 块的，这些方块在 mask 中仍然是 #。
考虑 (O(n^2)) 做法。枚举按照最左边放置的放法，在 mask 中显示 # 的格子需要向左移动 (i) 格，而小于等于 (i) 格的 # 全部都被删掉了需要加回来。这样只需要分开考虑每一个 _ 块怎么填即可。
- 如果 _ 在边上且长度为1，无解。
- 如果 __ 在中间且长度为 2，无解。
- 对每一个 _ 块加入长度为 1 或 2 的 # 块，一边加一边判断。
可以发现，若在 (i geq 4) 时候有答案成立，一定有 (i' = i - 2) 有答案成立。那么时间复杂度 (O(n))
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define dbg1(x) cout << #x << " = " << x << ", "
#define dbg2(x) cout << #x << " = " << x << endl
const int N = 100000 + 5;
const int inf = 1e9 + 7;
int n;
char ss[N];
char s[N];
struct Node {
int l;
char ch;
Node(int l=0, char ch=' '):l(l), ch(ch) {}
};
bool check(int lift) {
for(int i=1;i<=n;i++) s[i] = ss[i];
for(int i=1;i<=n;i++) if(s[i] == '#') {
for(int j=1;j<=lift;j++) s[i-j] = '#';
}
s[n-lift+1] = ' ';
vector<Node> a;
for(int i=1, j=1; i<=n-lift; i++) {
if(s[i] == s[j] && s[i+1] != s[i]) {
int len;
if(s[j] == '_') {
if(i == j) {
if(j == 1 || i == n - lift) return false;
else { j = i + 1; continue;}
}
if((j != 1 && i != n - lift) && i - j + 1 == 2) return false;
len = i - j + (j == 1) + (i == n - lift);
}
else len = i - j + 1;
a.pb(Node(len, s[j]));
j = i + 1;
}
}
vector<int> ans;
for(int i=0;i<a.size();i++) {
if(a[i].ch == '#') { ans.push_back(a[i].l); continue;}
int len = a[i].l;
for(int j=0;j<len/2-1;j++) {
ans.pb(1);
if(lift < 1) return false;
}
if(len % 2 == 1) {
ans.pb(2);
if(lift < 2) return false;
}
else {
ans.pb(1);
if(lift < 1) return false;
}
}
printf("%d
", (int)ans.size());
for(int i=0;i<ans.size();i++) {
printf("%d%c", ans[i], "
"[i == (int)ans.size()-1]);
}
return true;
}
int main() {
#ifdef LOCAL
freopen("J.in", "r", stdin);
#endif
scanf("%s", ss + 1);
n = strlen(ss + 1);
int lift = inf;
if(ss[1] == '#' || ss[n] == '#') lift = 0;
for(int i=1, j=1;i<=n;i++) {
if(ss[j] == '_' && ss[i] == '_' && i == n) {
lift = min(lift, i - j + 1);
}
else if(ss[j] == '_' && ss[i] == '#') {
if(j == 1) lift = min(lift, i - j);
else lift = min(lift, i - j - 1);
}
if(ss[j] != ss[i]) j = i;
}
for(int k=0;k<=min(lift, 3); k++) {
if(check(k)) return 0;
}
puts("-1");
return 0;
}