171 F - Strivore
直接把初始字符当成隔板，统计的方案数会有重复
为了避免重复情况，规定隔板字母尽可能最后出现，即在隔板字母后面不能插入含隔板字母的字符串
所以在隔板字母后插入的字符只有25种选择，而在最前面的位置插入字符有26种选择
枚举在最前面位置插入的字符个数，这些字符有26中选法，剩下的字符插入到隔板字母的后面，有25种选法
剩余字符的插入位置利用隔板法转化为在剩余字符中选择(m - 1)块板(第一块板已固定)
const int P = 1e9 + 7;
const int N = 2e6 + 10;
int n, m;
char s[N];
int fact[N], infact[N];
int pow_mod(int a, int b, int p)
{
int res = 1;
while(b)
{
if(b & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
b >>= 1;
}
return res;
}
void init()
{
fact[0] = infact[0] = 1;
for(int i = 1; i < N; ++ i)
{
fact[i] = (LL)fact[i - 1] * i % P;
infact[i] = (LL)infact[i - 1] * pow_mod(i, P - 2, P) % P;
}
}
int C(int a, int b)
{
return (LL)fact[a] * infact[b] % P * infact[a - b] % P;
}
int main()
{
init();
scanf("%d%s", &n, s); m = strlen(s);
int res = 0;
for(int i = 0; i <= n; ++ i)
{
int tmp = (LL)pow_mod(25, n - i, P) * C(n + m - i - 1, m - 1) % P;
tmp = (LL)tmp * pow_mod(26, i, P) % P;
res = (res + tmp) % P;
}
printf("%d
", res);
return 0;
}
172 F - Unfair Nim
令(A = a_1 - x), (B = a_2 + x)
(A) ^ (B) ^ (a_3) ^ (...) ^ (a_n = 0)
令(y = a_3) ^ (...) ^ (a_n), (x = a_1 + a_2 = A + B)
(A + B = 2 * (A ;&; B) + A) ^ (B)
故满足下列式子：(A ;&; B = dfrac{x - y}{2})， 且(A) ^ (B = y)
如果(x < y)或者(2)不能整除(x - y)，不合法，输出(-1)
找到在([1,a_1])内满足上式的最大的(A)
考虑(A)的每一位，(A ;&; B)的位必须为(1)
(XOR = 1, AND = 1), 不合法，输出(-1)
(XOR = 1, AND = 0), 如果(A)当前位为(1)不超过(a_1)，则此位置(1)，否则为(0)
(XOR = 0, AND = 1), (A)当前位为(1)
(XOR = 0, AND = 0), (A)当前位为(0)
const int N = 300 + 10;
typedef long long LL;
int n;
LL a[N];
int main()
{
IOS;
cin >> n;
LL x, y = 0;
for(int i = 1; i <= n; ++ i) cin >> a[i];
for(int i = 3; i <= n; ++ i) y ^= a[i];
x = a[1] + a[2];
if((x - y) < 0 || (x - y) % 2) { puts("-1"); return 0; }
LL XOR = y, AND = (x - y) / 2;
LL A = AND;
for(int i = 60; i >= 0; -- i)
{
int Ai, Xi;
Ai = (AND >> i) & 1;
Xi = (XOR >> i) & 1;
if(Ai == 1 && Xi == 1) { puts("-1"); return 0; }
if(Ai == 0 && Xi == 1)
if(A + (1LL << i) <= a[1]) A += (1LL << i);
}
if(A >= 1 && A <= a[1]) cout << a[1] - A << endl;
else puts("-1");
return 0;
}
173 F - Intervals on Tree
森林中子树的数量 = 点的数量 - 边的数量
考虑所有集合中点的数量总和为(n * 1 + (n - 1) * 2 + (n - 2) * 3 ; + ; ... ; + ; 1 * n)
考虑每条边((a,b))的贡献(即出现次数)为：(a * (n - b + 1))
int n;
int main()
{
scanf("%d", &n);
LL res = 0;
for(int i = n; i >= 1; -- i)
res += (LL)i * (n + 1 - i);
for(int i = 1; i < n; ++ i)
{
int a, b;
scanf("%d%d", &a, &b);
if(a > b) swap(a, b);
res -= (LL)a * (n - b + 1);
}
printf("%lld
", res);
return 0;
}
174 F - Range Set Query
离线查询([l,r])中不同数字的个数
对于当前区间来说,每种数字仅保留最后一个位置(置为1),其他的置为0，答案即为([l,r])的权值和.
故先把所有查询读入，按照右端点排序，保证查询区间的右端点依次出现.
修改为(0)和查询权值和的操作用树状数组优化.
const int N = 5e5 + 20;
struct Query
{
int l, r, id;
}q[N];
int n, m, tr[N], a[N], ans[N];
int pos[N];
bool cmp(Query a, Query b) { return a.r < b.r; }
int lowbit(int x) { return x & -x; }
int sum(int x) { int res = 0; for(int i = x; i; i -= lowbit(i)) res += tr[i]; return res; }
void add(int x, int v) { for(int i = x; i <= n; i += lowbit(i)) tr[i] += v; }
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
for(int i = 1; i <= n; ++ i) add(i, 1);
for(int i = 1; i <= m; ++ i)
{
scanf("%d%d", &q[i].l, &q[i].r);
q[i].id = i;
}
sort(q + 1, q + m + 1, cmp);
int last = 1;
for(int i = 1; i <= m; ++ i)
{
for(int j = last; j <= q[i].r; ++ j)
{
if(pos[a[j]]) add(pos[a[j]], -1);
pos[a[j]] = j;
}
ans[q[i].id] = sum(q[i].r) - sum(q[i].l - 1);
last = q[i].r + 1;
}
for(int i = 1; i <= m; ++ i)
printf("%d
", ans[i]);
return 0;
}
175 F - Making Palindrome
每个字符串可以看做是一个初始状态，状态由字符串和放置位置（置于左侧或右侧）组成,初始串既可以放在左侧，也可以放在右侧.
对于每一次合并，可以将回文的部分删去，剩余部分则是一个串的前缀或后缀, 故可以把所有字符串的前后缀处理成每个状态.
每一次合并的花费为选择串的价值，即从一个状态连接选择串转移到另一个状态，也就是从当前状态到另一个状态连一条权值为选择串价值的边.
每一个初始串都是一个起点，每一个回文串都是一个终点.
构建一个超级源点，向每个初始串连权值为(c_i)的边，构建一个超级汇点，每个回文串向超级汇点连一条权值为(0)的边，跑最短路即可.
const int N = 100 + 2;
const int M = 1e5 + 20;
const LL INF = 1e18;
string s[N];
int c[N];
int n, cnt;
map<pair<string, int>, int> Sub;
bool check(string str)
{
if((int)str.size() <= 1) return 1;
int len = str.size() - 1;
for(int i = 0; i <= len / 2; ++ i)
if(str[i] != str[len - i]) return 0;
return 1;
}
int conn(string a, string b, string &c)
{
int i = 0, j = b.size() - 1;
while(i < (int)a.size() && j >= 0)
if(a[i ++ ] != b[j -- ]) return -1;
if(i >= (int)a.size() && j < 0) { c = ""; return 0; }
else if(j >= 0) { c = b.substr(0, j + 1); return 1; }
else if(i < (int)a.size()) { c = a.substr(i); return 0; }
}
struct Edge
{
int to, nxt, w;
}line[M * 2];
LL dis[M];
int fist[M], idx;
bool st[M];
struct zt
{
int x; LL d;
};
bool operator < (zt a, zt b) { return a.d > b.d; }
void add(int x, int y, int z)
{
line[idx] = (Edge){y, fist[x], z};
fist[x] = idx ++;
}
void heap_dijkstra()
{
priority_queue<zt> q;
for(int i = 1; i <= cnt + 1; ++ i) dis[i] = INF;
q.push((zt){0, 0});
while(!q.empty())
{
zt u = q.top(); q.pop();
if(st[u.x]) continue;
st[u.x] = 1;
for(int i = fist[u.x]; i != -1; i = line[i].nxt)
{
int v = line[i].to;
if(dis[v] > dis[u.x] + line[i].w)
{
dis[v] = dis[u.x] + line[i].w;
q.push((zt){v, dis[v]});
}
}
}
}
int main()
{
IOS;
memset(fist, -1, sizeof fist);
cin >> n;
for(int i = 1; i <= n; ++ i)
{
cin >> s[i] >> c[i];
for(int j = s[i].size() - 1; j >= 0; -- j)
Sub[make_pair(s[i].substr(j), 0)] = ++ cnt;
for(int j = 1; j <= (int)s[i].size(); ++ j)
Sub[make_pair(s[i].substr(0, j), 1)] = ++ cnt;
}
Sub[make_pair("", 0)] = ++ cnt;
Sub[make_pair("", 1)] = ++ cnt;
for(int i = 1; i <= n; ++ i)
{
add(0, Sub[make_pair(s[i], 0)], c[i]);
add(0, Sub[make_pair(s[i], 1)], c[i]);
}
for(auto x: Sub)
if(check(x.first.first))
add(x.second, cnt + 1, 0);
for(auto x: Sub)
for(int i = 1; i <= n; ++ i)
{
int res; string v;
if(x.first.second == 0)
res = conn(x.first.first, s[i], v);
else res = conn(s[i], x.first.first, v);
if(res != -1) add(x.second, Sub[make_pair(v, res)], c[i]);
}
heap_dijkstra();
if(dis[cnt + 1] >= INF) cout << "-1" << endl;
else cout << dis[cnt + 1] << endl;
return 0;
}
2021.1.28