全nm构造题,我爆零了
T1.排序
我读错题了……以为这是个普通的冒泡排序。因为需要用到所有的逆序对,所以每一次操作只能减少一个逆序对。考虑从小到大归位,我们按从大到小的顺序交换,这样保证了每一次交换都是\(a\)与\(a-1\)交换,相邻的两个交换,显然不会影响剩下的逆序对数,我们不断重复此操作,直至把\(1\)位置贡献的逆序对消除,这时位置\(1\)上的数一定是\(1\),剩下的数的相对位置不变,类似于递归处理。
代码
#define sandom signed
#include <bits/stdc++.h>
#define re register int
using namespace std; int wrt[20], TP;
const int Z = 1020;
inline int read() { int x = 0, f = 0; char c = getchar(); while (!isdigit(c)) f = c == '-', c = getchar(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); return f ? -x : x; }
inline void write(int x) { TP = 0; if (x < 0) putchar('-'), x = -x; while (x >= 10) wrt[++TP] = x % 10, x /= 10; wrt[++TP] = x; while (TP) putchar(wrt[TP--] | 48); putchar(' '); }
int n, m, a[Z];
vector <int> v[Z];
inline bool cmp(int x, int y) { return a[x] > a[y]; }
sandom main()
{
n = read();
for (re i = 1; i <= n; i++) a[i] = read();
for (re i = 1; i <= n; i++)
for (re j = i + 1; j <= n; j++)
if (a[i] > a[j]) v[i].push_back(j), ++m;
write(m), putchar('\n');
for (re i = 1; i <= n; i++)
{
sort(v[i].begin(), v[i].end(), cmp);
for (auto j : v[i]) write(i), write(j), putchar('\n');
}
return 0;
}
T2.Xorum
据说随机化分很高?但是我只有20……\(Houraisan\_Kaguya\)大佬给了一种稳定\(O(log^2n)\)的算法。小芝士:累加等价于左移。首先给定的是一个奇数,如果次低位为\(1\),可以把它左移一位,然后与原数异或,这样最低位仍然是\(1\),次低位为\(0\)。所以我们只对此讨论。设它为\(x\),把\(x\)不断左移,记为\(y\),当\(y\)的最低位的1与\(x\)的最高位的1对齐时停止,这时我们得到\(a=x+y\),\(b=x\oplus y\),\(c=a\oplus b\),手磨一下发现若\(x\)的最高位为\(high\),那么\(c=2^{high+1}\),我们用这个不断左移,把\(y\)除了最低位上的1全部异或掉,最后的\(y=2^{high}\),这样再\(x\oplus y\),就把\(x\)的最高位的1清除了,我们重复此操作,最后一定只剩下\(1\)。
代码
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <bits/stdc++.h>
#define re register int
#define int long long
using namespace std; int wrt[20], TP;
const int Z = 1e6 + 10;
inline void write(int x) { TP = 0; if (x < 0) putchar('-'), x = -x; while (x >= 10) wrt[++TP] = x % 10, x /= 10; wrt[++TP] = x; while (TP) putchar(wrt[TP--] | 48); putchar(' '); }
int n, m, x, y;
struct xorum { int op, x, y; }; vector <xorum> opt;
inline void add(int op, int x, int y) { opt.push_back({xorum{op, x, y}}); }
inline int left_move(int x, int pos) { while (pos--) add(1, x, x), x += x; return x; }
int solve(int x)
{
int high, a, b, c;
for (re i = 60; i >= 0; i--)
if (x & (1ll << i)) { high = i; break; }
int y = left_move(x, high);
add(1, x, y); a = x + y;
add(2, x, y); b = x ^ y;
add(2, a, b); c = a ^ b;
high++;
for (re i = high; i <= 60; i++)
if (y & (1ll << i))
{
c = left_move(c, i - high); high = i;
add(2, y, c); y = y ^ c;
}
add(2, x, y);
return x ^ y;
}
sandom main()
{
cin >> x;
if (x & 2)
{
add(1, x, x); y = x + x;
add(2, x, y); x = x ^ y;
}
while (x != 1) x = solve(x);
write(opt.size()), putchar('\n');
for (auto i : opt) write(i.op), write(i.x), write(i.y), putchar('\n');
return 0;
}
T3.有趣的区间问题
Special Judge中的一道良心数据结构题(但是我没切),经典套路:要么扫描线,要么CDQ分治。线段树需要跑60遍,所以我选择了CDQ。借鉴完美子图的思路即可——我们已经把左右区间单独的贡献计算完了,考虑合并:1.最大值和最小值都在左边,枚举左端点,我们只需要在右边维护一个单调指针,时刻保证右边的最大值和最小值不超过左边;2.最大值和最小值都在右边,同理;3.最大值在左边,最小值在右边,枚举左端点,在右边维护两个指针,一个是扩展指针,一个是反悔指针,只要右边的最大值不超过左边,我就一直扩展,并把贡献用桶记录下来,但是当我左移左端点时,可能会出现最小值出现在左侧的情况,这时候我们需要反悔,把这样的贡献全部从桶中清除,对于每一个左端点直接查桶就行;4.最大值在右边,最小值在左边,同理。小细节:为了去重,只需要扩展的时候一个是\(<\),一个是\(<=\)。
代码
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <bits/stdc++.h>
#define re register int
#define int long long
using namespace std;
const int Z = 1e6 + 10;
inline int read() { int x = 0, f = 0; char c = getchar(); while (!isdigit(c)) f = c == '-', c = getchar(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); return f ? -x : x; }
int n, m, ans;
int a[Z], b[Z];
inline int lowbit(int x) { return x & (-x); }
inline int pct(int x) { int cnt = 0; while (x) cnt++, x -= lowbit(x); return cnt; }
int Max[Z], Min[Z], rec[70];
void CDQ(int l, int r)
{
if (l == r) { ans++; return; }
int mid = l + r >> 1;
CDQ(l, mid), CDQ(mid + 1, r);
Max[mid] = Min[mid] = mid;
Max[mid + 1] = Min[mid + 1] = mid + 1;
for (re i = mid - 1; i >= l; i--) Max[i] = a[Max[i + 1]] > a[i] ? Max[i + 1] : i, Min[i] = a[Min[i + 1]] < a[i] ? Min[i + 1] : i;
for (re i = mid + 2; i <= r; i++) Max[i] = a[Max[i - 1]] > a[i] ? Max[i - 1] : i, Min[i] = a[Min[i - 1]] < a[i] ? Min[i - 1] : i;
for (re i = mid, j = mid + 1; i >= l; i--)//最大值和最小值都在左边
{
while (j <= r && a[Max[j]] < a[Max[i]] && a[Min[j]] > a[Min[i]]) j++;
if (b[Max[i]] == b[Min[i]]) ans += j - mid - 1;
}
for (re j = mid + 1, i = mid; j <= r; j++)//最大值和最小值都在右边
{
while (i >= l && a[Max[i]] <= a[Max[j]] && a[Min[i]] >= a[Min[j]]) i--;
if (b[Max[j]] == b[Min[j]]) ans += mid - i;
}
for (re i = mid, j = mid + 1, k = mid + 1; i >= l; i--)//最大值在左边,最小值在右边
{
while (j <= r && a[Max[j]] < a[Max[i]]) rec[b[Min[j]]]++, j++;
while (k < j && a[Min[k]] > a[Min[i]]) rec[b[Min[k]]]--, k++;
ans += rec[b[Max[i]]];
}
for (re t = 0; t <= 60; t++) rec[t] = 0;
for (re j = mid + 1, i = mid, k = mid; j <= r; j++)//最小值在左边,最大值在右边
{
while (i >= l && a[Max[i]] <= a[Max[j]]) rec[b[Min[i]]]++, i--;
while (k > i && a[Min[k]] >= a[Min[j]]) rec[b[Min[k]]]--, k--;
ans += rec[b[Max[j]]];
}
for (re t = 0; t <= 60; t++) rec[t] = 0;
}
sandom main()
{
n = read();
for (re i = 1; i <= n; i++) a[i] = read(), b[i] = pct(a[i]);
CDQ(1, n); cout << ans;
return 0;
}
T4.无聊的卡牌问题
赛时我与正解的差距只在读入上??我以为他给出的序列每三个一组(没仔细看样例),所以直接存了下来……赛后改成了栈就过了……从小到大依次入栈,当栈顶三个元素是同一个人取的时,就把这个三元组拿出来。显然三元组之间是有限制关系的,考虑拓扑排序。如果一个三元组\(i\)被另一个三元组\(j\)包含,那么需要先取出\(i\),再取出\(j\),所以连边\(i->j\),我是把两个人的三元组分开了,并且在拓扑时开了两个队列分别记录。每次从两个队列的队首分别取出一个元素,直接输出。tip:如果队首元素不会对其他造成限制,那么什么时候取它都可以,我们可以稍后再取它,优先取会对其他造成限制的三元组。
代码
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <bits/stdc++.h>
#define re register int
using namespace std; int wrt[20], TP;
const int Z = 1500;
inline int read() { int x = 0, f = 0; char c = getchar(); while (!isdigit(c)) f = c == '-', c = getchar(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); return f ? -x : x; }
inline void write(int x) { TP = 0; if (x < 0) putchar('-'), x = -x; while (x >= 10) wrt[++TP] = x % 10, x /= 10; wrt[++TP] = x; while (TP) putchar(wrt[TP--] | 48); putchar(' '); }
int n, m, stk[Z], n1, n2;
bool vs[Z];
struct three//三元组
{
int x[3];
friend bool operator !=(three A, three B) { return A.x[0] < B.x[0] && A.x[2] > B.x[2]; }//A包含B
}; three f[Z], g[Z];
struct edge { int v, ne; } e[Z * Z];
int head[Z], cnt, deg[Z];
inline void add(int x, int y) { deg[y]++; e[++cnt] = edge{y, head[x]}; head[x] = cnt; }
queue <int> q1, q2;
int del(queue <int> &q)
{
int lim = q.size() + 1, u = q.front(); q.pop();
while (!head[u] && lim)
{
q.push(u); lim--;
u = q.front(), q.pop();
}
for (re i = head[u]; i; i = e[i].ne)
{
int v = e[i].v; deg[v]--;
if (!deg[v])
{
if (v <= n) q1.push(v);
else q2.push(v);
}
}
return u;
}
void VOE()//拓扑排序
{
m = n << 1;
for (re i = 0 + 1; i <= n; i++) if (!deg[i]) q1.push(i);
for (re i = n + 1; i <= m; i++) if (!deg[i]) q2.push(i);
while (!q1.empty() || !q2.empty())
{
int u = del(q1);
for (re i = 0; i < 3; i++) write(f[u].x[i]); putchar('\n');
u = del(q2);
for (re i = 0; i < 3; i++) write(g[u - n].x[i]); putchar('\n');
}
}
sandom main()
{
n = read();
for (re i = 1; i <= n; i++)
{
int x = read(), y = read(), z = read();
vs[x] = vs[y] = vs[z] = 1;
}
for (re i = 1; i <= 6 * n; i++)
{
stk[++m] = i;
if (m >= 3 && vs[stk[m]] && vs[stk[m - 1]] && vs[stk[m - 2]]) f[++n1] = three{stk[m - 2], stk[m - 1], stk[m]}, m -= 3;
if (m >= 3 && !vs[stk[m]] && !vs[stk[m - 1]] && !vs[stk[m - 2]]) g[++n2] = three{stk[m - 2], stk[m - 1], stk[m]}, m -= 3;
}
//根据包含关系建立拓扑顺序
for (re i = 1; i <= n; i++)
for (re j = 1; j <= n; j++)
if (g[j] != f[i]) add(i, j + n);
for (re i = 1; i <= n; i++)
for (re j = 1; j <= n; j++)
if (f[j] != g[i]) add(i + n, j);
VOE();
return 0;
}