前言
考了那么多试..几乎每次都由不如意的地方…
今天又看错题+哈希种子爆炸, 感觉在这样怕是要退役了啊…
吃芝麻
有A和B两人, 一开始A有a颗芝麻, B有b颗芝麻。
接下来两个人进行K轮操作, 如果a大于b, 那么B会从A手中拿走b颗芝麻, 否然A从B手中拿走a颗芝麻。
问操作结束后min(a, b)的值。
[latex]a, b, K \le 10^9 [/latex]
解题报告
智商题…从来没想过取模。
在数轴上割补以下, 就发现原问题和以下公式是等价的:
[latex] min(a^K \pmod{a+b}, b^K \pmod{a+b}) [/latex]
然后快速幂就好了QAQ, 考试时想了一个半小时没想出来…
[BZOJ 2054]疯狂的馒头
N ≤ 10^6,M ≤ 10^7
解题报告
首先颜色从大到小涂就可以忽略覆盖问题。
考虑用链表维护馒头, 链表暴力涂色后删除的均摊复杂度是线性的, 但是不能快速看某个馒头后面第一个没有涂色的馒头是哪一个。
用并查集代替链表, 每次涂色用并查集向后合并, 那么查询某个位置第一个没涂色的馒头可以直接用root(p), 就变成线性的了。
核心代码(对区间[l, r]涂上颜色i):
if(l > r) swap(l, r); l = root(l), r = root(r); while(l != r) { if(!ans[l]) ans[l] = i; int x = root(l+1); fa[l] = x; l = x; }
SURVIVE
Elaine太强辣! 居然自己想出这种难度的题(虽然已经有过这个脑洞了)!
给一条长度为N的数字长链,这条链上有些数字是相同的,有些地方是不同的,求数链有多少种可能。
数链不能有前导0, 对数链有M个要求, 第i个要求数链[a, b]区间和[c, d]区间相同。
解题报告
首先, 我们可以NM暴力用并查集处理出那些位置上的数字是相同的, 因为不能有前导0, 那么答案就等于9×10^(数字种类数-1)。
怎么优化并查集呢?
考试时就愉悦地在这里卡了2h+
我们可以像st表一样开出logN个并查集, 第i层的并查集中, 如果a和b在同一个集合内, 那么表示区间[a, a+(1<<i))和区间[b, b+(1<<i))是相同的, 那么处理M个要求时就可以像在线段树上打标记一样维护这个东东了。
最后统计答案时在st表上下传, 然后扫一遍统计即可。
代码
#include <cstdio> #include <cstring> #include <algorithm> #include <climits> #include <algorithm> using namespace std; typedef long long LL; const int MOD = 1000000007; const int MAXN = 100010; int plog[MAXN]; namespace UFS { int mem[19][MAXN]; int * fa; int root (int u) {return fa[u] ? fa[u] = root(fa[u]) : u;} void merge (int a, int b, int k) { fa = mem[k]; int ra = root(a), rb = root(b); if(ra == rb) return ; fa[ra] = rb; } int findRoot (int a, int k) { fa = mem[k]; return root(a); } } inline int advPow (int a, int b) { int ret = 1; while(b) { if(b & 1) ret = (LL)ret*a%MOD; a = (LL)a*a%MOD; b >>= 1; } return ret; } bool vis[MAXN]; int main () { int N, M; scanf("%d%d", &N, &M); for(int i = 1; (1<<i)<=N; i++) plog[1<<i] = i; for(int i = 1; i<=N; i++) plog[i] = max(plog[i-1], plog[i]); for(int i = 1; i<=M; i++) { int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d); while(a <= b) { int l = plog[b-a+1]; UFS :: merge (a, c, l); a += (1<<l), c += (1<<l); } } for(int i = plog[N]; i; i--) { for(int j = 1; j<=N-(1<<i)+1; j++) { int rt = UFS :: findRoot(j, i); UFS :: merge(j, rt, i-1); UFS :: merge(j+(1<<(i-1)), rt+(1<<(i-1)), i-1); } } int cnt = 0; for(int i = 1; i<=N; i++) { int p = UFS :: findRoot(i, 0); if(vis[p]) continue ; vis[p] = true, cnt++; } printf("%d\n", (int)(9LL*advPow(10, cnt-1)%MOD)); }
Join the discussion