T1 哈密顿路
容易发现一条哈密顿回路一定会经过节点 \(1\) ,因此考虑从节点 \(1\) 进行 dp ,设 \(f_{S,i}\) 表示是否存在方案在 \(i\) 节点结束,经过点集为 \(S\) ,统计答案是需要枚举在 \(1\) 之前经过的点集简单进行合并即可。由于 dp 值只有 \(0/1\) ,压位后转移总复杂度为 \(O(n2^n)\) 。
code
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 24, max2 = 1 << 24;
#define lowbit(now) ( now & -now )
int n;
char edge[max1 + 5][max1 + 5];
int f[max2 + 5], g[max2 + 5];
int ans[max1 + 5];
int main ()
{
freopen("hamilton.in", "r", stdin);
freopen("hamilton.out", "w", stdout);
scanf("%d", &n);
for ( int i = 1; i <= n; i ++ )
{
scanf("%s", edge[i] + 1);
for ( int j = 1; j <= n; j ++ )
if ( edge[i][j] == '1' )
f[1 << i - 1] |= 1 << j - 1;
}
for ( int s = 1; s < 1 << n; s ++ )
f[s] = f[s ^ lowbit(s)] | f[lowbit(s)];
g[1] = 1;
for ( int s = 1; s < 1 << n; s ++ )
{
if ( !g[s] )
continue;
for ( int i = 1; i <= n; i ++ )
if ( !( s >> i - 1 & 1 ) && ( f[g[s]] >> i - 1 & 1 ) )
g[s | 1 << i - 1] |= 1 << i - 1;
}
for ( int s = 0; s < 1 << n; s ++ )
for ( int i = 1; i <= n; i ++ )
if ( g[s] >> i - 1 & 1 )
ans[i] |= g[( ( 1 << n ) - 1 ) ^ s ^ 1];
for ( int i = 1; i <= n; i ++ )
{
for ( int j = 1; j <= n; j ++ )
{
if ( i == j )
putchar('0');
else
putchar('0' + ( ans[i] >> j - 1 & 1 ));
}
putchar('\n');
}
return 0;
}
T2 统一省选
考虑将每个关卡写成函数的形式:
\[\begin{aligned}
f(x)&=
\begin{cases}
-\infty & x\le a_i\\
x-a_i & x>a_i
\end{cases}
\\
g(x)&=
\begin{cases}
-\infty & x<a_i\\
a_i & x\ge a_i
\end{cases}
\\
h(x)&=
\begin{cases}
a_i & x\le a_i\\
x & x>a_i
\end{cases}
\end{aligned}
\]
容易发现这些操作可以归纳为函数:
\[f(x)=
\begin{cases}
-\infty & x\le A\\
Y & A<x\le B\\
x-B+Y & x > B
\end{cases}
\]
发现上述函数合并后形式不变,使用线段树维护即可。
code
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 1e6;
const long long inf = 1e14;
int n, q;
long long H0;
struct Option
{
int type;
long long val;
}opt[max1 + 5];
struct Data
{
long long A, B, Y;
Data () {}
Data ( long long __A, long long __B, long long __Y )
{ A = __A, B = __B, Y = __Y; }
};
Data Merge ( const Data &L, const Data &R )
{
Data res;
if ( R.B <= L.Y )
{
res.A = L.A;
res.B = L.B;
res.Y = L.Y - R.B + R.Y;
}
else if ( R.A < L.Y && R.B > L.Y )
{
res.A = L.A;
res.B = L.B + R.B - L.Y;
res.Y = R.Y;
}
else
{
res.A = R.A + L.B - L.Y;
res.B = R.B + L.B - L.Y;
res.Y = R.Y;
}
return res;
}
long long Query ( long long x, const Data &D )
{
if ( x <= D.A )
return -inf;
else if ( x > D.B )
return x - D.B + D.Y;
return D.Y;
}
struct Segment_Tree
{
#define lson(now) ( now << 1 )
#define rson(now) ( now << 1 | 1 )
Data tree[max1 * 4 + 5];
void Insert ( int now, int pos )
{
if ( opt[pos].type == 1 )
{
tree[now].A = opt[pos].val;
tree[now].B = opt[pos].val;
tree[now].Y = 0;
}
else if ( opt[pos].type == 2 )
{
tree[now].A = opt[pos].val - 1;
tree[now].B = inf;
tree[now].Y = opt[pos].val;
}
else
{
tree[now].A = 0;
tree[now].B = opt[pos].val;
tree[now].Y = opt[pos].val;
}
return;
}
void Build ( int now, int L, int R )
{
if ( L == R )
return Insert(now, L);
int mid = L + R >> 1;
Build(lson(now), L, mid);
Build(rson(now), mid + 1, R);
tree[now] = Merge(tree[lson(now)], tree[rson(now)]);
return;
}
void Insert ( int now, int L, int R, int pos )
{
if ( L == R )
return Insert(now, pos);
int mid = L + R >> 1;
if ( pos <= mid )
Insert(lson(now), L, mid, pos);
else
Insert(rson(now), mid + 1, R, pos);
tree[now] = Merge(tree[lson(now)], tree[rson(now)]);
return;
}
Data tmp;
int Query ( int now, int L, int R, int pos )
{
if ( L >= pos )
{
Data sum = Merge(tmp, tree[now]);
int mid = L + R >> 1;
if ( ::Query(H0, sum) <= 0 )
{
if ( L == R )
return L;
int res = Query(lson(now), L, mid, pos);
if ( res == -1 )
res = Query(rson(now), mid + 1, R, pos);
return res;
}
tmp = sum;
return -1;
}
int mid = L + R >> 1, res = -1;
if ( pos <= mid )
res = Query(lson(now), L, mid, pos);
if ( res == -1 )
res = Query(rson(now), mid + 1, R, pos);
return res;
}
}Tree;
int main ()
{
freopen("bad.in", "r", stdin);
freopen("bad.out", "w", stdout);
scanf("%d%d%lld", &n, &q, &H0);
for ( int i = 1; i <= n; i ++ )
scanf("%d%lld", &opt[i].type, &opt[i].val);
Tree.Build(1, 1, n);
int op, x, ans;
while ( q -- )
{
scanf("%d", &op);
if ( op == 1 )
{
scanf("%d", &x);
scanf("%d%lld", &opt[x].type, &opt[x].val);
Tree.Insert(1, 1, n, x);
}
else
{
scanf("%d", &x); Tree.tmp.A = Tree.tmp.B = Tree.tmp.Y = 0;
ans = Tree.Query(1, 1, n, x);
if ( ans == x )
printf("-1\n");
else if ( ans == -1 )
printf("%d\n", n);
else
printf("%d\n", ans - 1);
}
}
return 0;
}
T3 并行计算
根据某些奇怪的证明可以知道操作次数下界为 \(\min(\lceil\log n\rceil,0.4n)+O(1)\) 。
可以大力手玩得到 \(6\) 次消去 \(15\) 个数,以及 \(4\) 次消去 \(10\) 个数的构造,对于 \(n\) 的大部分使用上述构造,其余的使用 \(3\) 次 \(7\) 个数, \(2\) 次 \(3\) 个数, \(1\) 次 \(1\) 个数简单补全即可。
由于数据点较少但本题特殊情况较多,代码可能在一些情况上存在漏洞。
code
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct Answer
{
int a, b, c;
Answer () {}
Answer ( int __a, int __b, int __c )
{ a = __a, b = __b, c = __c; }
};
vector <Answer> ans;
void Make_16_6 ( int s )
{
ans.push_back(Answer(s + 1, s + 2, s + 2));
ans.push_back(Answer(s + 3, s + 4, s + 4));
ans.push_back(Answer(s + 5, s + 6, s + 6));
ans.push_back(Answer(s + 8, s + 9, s + 9));
ans.push_back(Answer(s + 2, s + 3, s + 3));
ans.push_back(Answer(s + 2, s + 4, s + 4));
ans.push_back(Answer(s + 6, s + 7, s + 7));
ans.push_back(Answer(s + 10, s + 11, s + 11));
ans.push_back(Answer(s + 4, s + 5, s + 5));
ans.push_back(Answer(s + 4, s + 6, s + 6));
ans.push_back(Answer(s + 4, s + 7, s + 7));
ans.push_back(Answer(s + 13, s + 14, s + 14));
ans.push_back(Answer(s + 7, s + 8, s + 8));
ans.push_back(Answer(s + 7, s + 9, s + 9));
ans.push_back(Answer(s + 11, s + 12, s + 12));
ans.push_back(Answer(s + 14, s + 15, s + 15));
ans.push_back(Answer(s + 9, s + 10, s + 10));
ans.push_back(Answer(s + 9, s + 11, s + 11));
ans.push_back(Answer(s + 9, s + 12, s + 12));
ans.push_back(Answer(s + 15, s + 16, s + 16));
ans.push_back(Answer(s + 12, s + 13, s + 13));
ans.push_back(Answer(s + 12, s + 14, s + 14));
ans.push_back(Answer(s + 12, s + 15, s + 15));
ans.push_back(Answer(s + 12, s + 16, s + 16));
return;
}
void Make_11_4 ( int s )
{
ans.push_back(Answer(s + 1, s + 2, s + 2));
ans.push_back(Answer(s + 3, s + 4, s + 4));
ans.push_back(Answer(s + 5, s + 6, s + 6));
ans.push_back(Answer(s + 8, s + 9, s + 9));
ans.push_back(Answer(s + 2, s + 3, s + 3));
ans.push_back(Answer(s + 2, s + 4, s + 4));
ans.push_back(Answer(s + 6, s + 7, s + 7));
ans.push_back(Answer(s + 9, s + 10, s + 10));
ans.push_back(Answer(s + 4, s + 5, s + 5));
ans.push_back(Answer(s + 4, s + 6, s + 6));
ans.push_back(Answer(s + 4, s + 7, s + 7));
ans.push_back(Answer(s + 10, s + 11, s + 11));
ans.push_back(Answer(s + 7, s + 8, s + 8));
ans.push_back(Answer(s + 7, s + 9, s + 9));
ans.push_back(Answer(s + 7, s + 10, s + 10));
ans.push_back(Answer(s + 7, s + 11, s + 11));
return;
}
void Make_8_3 ( int s )
{
ans.push_back(Answer(s + 1, s + 2, s + 2));
ans.push_back(Answer(s + 3, s + 4, s + 4));
ans.push_back(Answer(s + 5, s + 6, s + 6));
ans.push_back(Answer(s + 7, s + 8, s + 8));
ans.push_back(Answer(s + 2, s + 3, s + 3));
ans.push_back(Answer(s + 2, s + 4, s + 4));
ans.push_back(Answer(s + 6, s + 7, s + 7));
ans.push_back(Answer(s + 6, s + 8, s + 8));
ans.push_back(Answer(s + 4, s + 5, s + 5));
ans.push_back(Answer(s + 4, s + 6, s + 6));
ans.push_back(Answer(s + 4, s + 7, s + 7));
ans.push_back(Answer(s + 4, s + 8, s + 8));
return;
}
void Make_4_2 ( int s )
{
ans.push_back(Answer(s + 1, s + 2, s + 2));
ans.push_back(Answer(s + 3, s + 4, s + 4));
ans.push_back(Answer(2000, 2000, 2000));
ans.push_back(Answer(2000, 2000, 2000));
ans.push_back(Answer(s + 2, s + 3, s + 3));
ans.push_back(Answer(s + 2, s + 4, s + 4));
ans.push_back(Answer(2000, 2000, 2000));
ans.push_back(Answer(2000, 2000, 2000));
return;
}
void Make_2_1 ( int s )
{
ans.push_back(Answer(s + 1, s + 2, s + 2));
ans.push_back(Answer(2000, 2000, 2000));
ans.push_back(Answer(2000, 2000, 2000));
ans.push_back(Answer(2000, 2000, 2000));
return;
}
int main ()
{
freopen("computer.in", "r", stdin);
freopen("computer.out", "w", stdout);
int n, s; scanf("%d", &n);
for ( s = 0; s + 16 <= n; s += 15 )
Make_16_6(s);
if ( n - s == 1 )
;
else if ( n - s == 2 )
Make_2_1(s);
else if ( n - s == 3 )
Make_4_2(s);
else if ( n - s == 4 )
Make_4_2(s);
else if ( n - s == 5 )
{
if ( !ans.empty() )
{
for ( int i = 0; i < 24; i ++ )
ans.pop_back();
Make_11_4(s - 15);
Make_11_4(s - 5);
}
else
Make_8_3(s);
}
else if ( n - s == 6 )
{
if ( !ans.empty() )
{
for ( int i = 0; i < 24; i ++ )
ans.pop_back();
Make_11_4(s - 15);
Make_11_4(s - 5);
}
else
Make_8_3(s);
}
else if ( n - s == 7 )
Make_8_3(s);
else if ( n - s == 8 )
Make_8_3(s);
else if ( n - s == 9 )
Make_11_4(s);
else if ( n - s == 10 )
Make_11_4(s);
else if ( n - s == 11 )
Make_11_4(s);
else if ( n - s == 12 )
Make_11_4(s), Make_2_1(s + 10);
else if ( n - s == 13 )
Make_11_4(s), Make_4_2(s + 10);
else if ( n - s == 14 )
Make_11_4(s), Make_4_2(s + 10);
else
Make_11_4(s), Make_8_3(s + 10);
printf("%lu\n", ans.size() >> 2);
int cnt = 0;
for ( auto v : ans )
{
printf("%d %d %d ", v.c, v.a, v.b);
++cnt;
if ( !( cnt & 3 ) )
putchar('\n');
}
return 0;
}