第十二场湖南多校对抗赛总结
闲来无事写了一发，太菜只会写4题，大家都会的题硬是写不来
A
题意：给n个点，把这n个点变成平行x轴且相互挨着，求所有点需要移动的曼哈顿距离之和的最小值，$ n <= 1e5 $。
思路:
y轴上都知道是中位数，然后x轴上本弱写不来了，一直想着是左右挪，想不到一个可行的做法。看了题解才知道，其实也是中位数，只不过变了一下形。
假设最后的结果x轴上的左端点为a
那么x轴上的贡献 (ansX) = $ sum_{i=0}^{n-1}|Xi - (a + i)| $ = $sum_{i=0}^{n}|Xi - i - a| $
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
using namespace std;
const int N = 1e5 + 10;
vector<P> v1,v2;
int main(){
int n;
while(scanf("%d",&n)==1){
v1.clear(),v2.clear();
for(int i = 0;i < n;i++){
int x , y;
scanf("%d%d",&x,&y);
v1.push_back(P(x,y));
v2.push_back(P(y,x));
}
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end());
LL ans = 0,mid;
if(n % 2 == 0) mid = (v2[n / 2].first + v2[n / 2 - 1].first) / 2;
else mid = v2[n/2].first;
for(int i = 0;i < v2.size();i++) ans += abs(mid - v2[i].first);
for(int i = 0;i < v1.size();i++) v1[i].first -= i;
sort(v1.begin(),v1.end());
if(n % 2 == 0) mid = (v1[n / 2].first + v1[n / 2 - 1].first) / 2;
else mid = v1[n/2].first;
for(int i = 0;i < v1.size();i++) ans += abs(v1[i].first - mid);
cout<<ans<<endl;
}
return 0;
}
B
题意：长者对小明施加了膜法，使得小明每天起床就像马丁的早晨一样。 今天小明早上醒来发现自己成了一位仓管员。仓库可以被描述为一个n × m的网格，在每个网格上有几个箱子（可能没有）。为了防止倾倒，每个网格上，箱子不应该堆放超过h个。为了满足要求，小明需要搬一些箱子，每一次，他可以把箱子从一个网格到相邻的网格（如果两个网格共享一条边）。 请计算为了满足要求，小明至少需要搬多少次。
思路: 裸的费用流，相邻点建费用为1的边即可，边有点多，普通的板子似乎有点慢，题解说zkw费用只要40ms,有时间去学习一波。
C(待补)
题意：有n个团队，每个团队的工资为$ a_i $，有两种操作
2 x y 合并x和y团队所在的集合
1 x 查询团队x所属的集合中 第 (frac{cnt + 1}{2})小的工资
思路：
方法一：并查集+线段树合并
用并查集维护团队的联通关系，用线段树维护每种工资是否出现过。
首先，把工资离散化一下，如果有相等的工资，我们需要处理一下，最后把工资变成一个1～n的排列
然后线段树的第x个叶子的值等于0或者1，如果为1，表示这个工资在这个树里出现过。
最初的时候build出n条链，初始化并查集。
合并的时候，维护并查集，并把根对应的线段树合并。
查询的时候，直接在x对应的根对应的线段树里，通过线段树的结构二分到具体第k个叶子为1的节点是谁即可。
复杂度(O((n+m)logn))
说得高大上一点，这个权值线段树就是主席树，主席树可以求用来区间第k大，区间内不同数字等等问题。
复习一下主席树，首先得将所有权值离散化，区间[L,R]就代表权值在[L,R]的结点的一些信息
- 每插入一个点 最多修改了(logn)个区间，所以这里插入的复杂度为(nlogn)
所以只需要新开一个根 将这(logn)个区间修改即可，所以空间复杂度为(O(nlogn))- 求(k)大问题的时候，只需要比较左右区间的个数，然后递归查找即可
- 求区间不同数字的时候，定义pre[i]为在i前面最接近i的满足a[l] = a[i]的l
这样我们查询区间[L,R]时 其实也就是查询区间内pre[l]<l的数字的个数- 主席树合并的时候 至少会合并(1)个区间，最多会合并(n)个区间
前者最多会发生n-1次,后者最多只会发生一次,所以时间复杂度和空间复杂度同为(O(nlogn))
#include<bits/stdc++.h>
#define LL long long
#define ls(i) seg[i].lc
#define rs(i) seg[i].rc
using namespace std;
const int N = 2e5 + 10;
inline int read(){
int x = 0;
char c = getchar();
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - 48,c = getchar();
return x;
}
int pa[N],siz[N];
int Find(int x){
return pa[x] == x?x:pa[x] = Find(pa[x]);
}
int a[N],b[N];
struct node
{
int lc,rc,cnt;
} seg[N * 20];
int n, nn, m, tot;
int root[N];
void update(int &cur,int l,int r,int val)
{
seg[++tot] = seg[cur];
cur = tot;
seg[cur].cnt++;
if(l >= r) return ;
int mid = l + r >> 1;
if(val <= mid) update(seg[cur].lc,l,mid,val);
else update(seg[cur].rc,mid+1,r,val);
}
int kth(int rt,int l,int r,int k)
{
if(l == r) return l;
int cnt = seg[ls(rt)].cnt;
int mid = l + r>>1;
if(k<=cnt) return kth(ls(rt),l,mid,k);
else return kth(rs(rt),mid+1,r,k-cnt);
}
void Merge(int &ru,int rv){///合并两颗主席树，其实就是对应区间合并
if(!ru || !rv){///有一颗主席树不存在该区间，直接返回另一颗的该区间或者返回空
if(!ru) ru = rv;
return ;
}
seg[ru].cnt += seg[rv].cnt;
Merge(ls(ru),ls(rv));
Merge(rs(ru),rs(rv));
}
int main(){
while(scanf("%d%d",&n,&m)==2){
for(int i = 1;i <= n;i++){
pa[i] = i;
b[i-1] = a[i] = read();
}
sort(b,b + n);
nn = unique(b,b+n) - b;
for(int i = 1;i <= n;i++) a[i] = lower_bound(b, b + nn, a[i]) - b + 1;
root[0] = tot = 0;
for(int i = 1;i <= n;i++){
siz[i] = 1;
root[i] = root[0];
update(root[i],1,nn,a[i]);
}
for(int i = 0;i < m;i++){
int o, u, v, fu, fv;
o = read(),u = read();
if(o == 2){
v = read();
fu = Find(u), fv = Find(v);
siz[fu] += siz[fv], pa[fv] = fu;
Merge(root[fu],root[fv]);
}else{
int f = Find(u),sz = (siz[f]+1)/2;
printf("%d
",b[kth(root[f],1,nn,sz)-1]);
}
}
}
return 0;
}
D(待补)
题意：构造一个(n)对括号的合法序列，使得第(x)个左括号对应的右括号(p1)在第(y)左个括号对应的右括号(p2)之后((x <y))，即(p1 > p2),求满足条件的合法序列
思路： 卡特兰三角
对于整个序列可分为3个部分：第x个左括号之前，第x个左括号对应的右括号之后，以及这2个括号内。
首先先要知道一个公式：
(C_{m}(n,k))表示一个序列中有n个X和k个Y，满足"对于这个序列的任何前缀,Y出现的次数-X的出现的次数< m"的组合数。
简单分析一下这个公式是怎么来的
类比一下n对合法的括号序列的方案数 (inom{n + n}{n} - inom{n + n}{n - 1})
如何求出不合法的序列呢？
假设在位置x处出现了前面所有右括号的数量比左括号的数量多1，则这个序列就已经不合法了，再看此时x后面所有的左括号数量会比右括号多1，若我们把后面左右括号数量互换一下，则右括号数量变成了n+1。其实也就意味着对于所有不合法的序列（即某处右括号比左多)，互换后面括号数量之后对应着所有n+1个右括号和n-1个左括号组成的序列，即它们的全排列(inom{n + n}{n - 1})
然后这里对于一个序列中有n个X和k个Y
其实也就是说某处出现了(cnt_r - cnt_l = m)的情况，后面左括号有(n - cnt_l)个，右括号有(k - cnt_r)个,互换之后右括号共有(n - cnt_l + cnt_r = n + m)个 即(inom{n + k}{n + m} = inom{n + k}{k - m})
①对于最后一部分，枚举这一部分内有多少对括号((cnt∈[y-x,N-x]))，组合数可以用卡特兰数求解(因为这个括号内部一定是符合规则的括号序列)。
②对于前两部分，我们可以枚举第一部分有多少个右括号(右括号数量(cnt_1<x)),这一部分一定要满足(n=x-1,k=cnt_1,m=1)的卡特兰三角，第二部分的右括号数=(N-1-cnt-cnt_1) ,左括号数=(N-x-cnt),那么第二部分要满足(n=N-x-cnt,k=N-1-cnt-cnt_1,m=x-cnt_1)的卡特兰三角
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1010;
const int mod = 1e9 + 7;
int C[N][N];
void init(){
for(int i = 0;i < N;i++) C[i][i] = C[i][0] = 1;
for(int i = 1;i < N;i++){
for(int j = 1;j < i;j++) C[i][j] = (C[i-1][j-1] + C[i-1][j])%mod;
}
}
int cal(int n,int k,int m){/// n个x k个y y-x个数<m的组合数
if(k < m) return C[n + k][k];
if(k >= m && k <= n + m - 1) return (C[n+k][k] - C[n + k][k - m] + mod)%mod;
return 0;
}
int main(){
init();
int n , x , y,T;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&x,&y);
int ans = 0;
for(int cnt = y - x; cnt <= n - x;cnt++){ ///枚举第x对括号之间的括号对数
int tmp_mid = cal(cnt,cnt,1);
for(int cnt1 = 0;cnt1 <= x - 1;cnt1++){ ///枚举x左边的右括号数
int tmp_l = cal(x-1,cnt1,1);
int tmp_r = cal(n-x-cnt,n-cnt1-cnt-1,x-cnt1);
ans += 1LL * tmp_mid * tmp_l % mod * tmp_r % mod;
ans %= mod;
}
}
printf("%d
",ans);
}
return 0;
}
E(待补)
小明非常喜欢n串字符串，非常讨厌m串字符串。 他想获得一个字符串S，S包含了所有他喜欢的串，且不包含任何一个他讨厌的串。 小明懒得思考了，要你帮他写个程序求出这个串。
Input
每个文件只有一组数据。 第一行两个整数(n,m(1 leq n+m ≤15,n≥1,m≥0)) 接下来n行，每行一个字符串Ai，表示小明喜欢的 接下来m行，每行一个字符串Bi，表示小明讨厌的 ((sum|Ai|) + (sum|Bi|)≤300) 字符串中只有小写字母从a到j
Output
输出一个满足条件的最短字符串即可，字符串中只允许出现小写字母从a到j。 如果存在多组解，可以输出任意解。 如果不存在这样的字符串，输出"-"
思路: 将字符串都插入到字典树中，建立AC自动机，这样可以预处理中从root到每个点结尾的串包含了哪些字符串，可以用状压表示。然后我们在Trie图上做最短路即可，dp[j][s]表示从root出发,Trie图上走到结点j，经过的字符串的集合为s的最短路径，由于边的权值为1,所以就变成了bfs，即某个状态一旦访问过，就不需要再访问了，这样复杂度就变成了$O(10 * (sum|Ai|) + (sum|Bi|) * 2^{n+m} ) approx 10^7 $，这是上限，实际上达不到这么大。
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define LL long long
#define P pair<string,int>
#define ls(i) seg[i].lc
#define rs(i) seg[i].rc
using namespace std;
using namespace __gnu_pbds;
const int SIZE = 10;
const int MAXNODE = 310;
const int MAXN = MAXNODE * (1<<15);
int fa[MAXN],alp[MAXN],cur[MAXN],mask[MAXN],vis[MAXNODE][1<<15];
int n , m,s1,s2;
struct AC{
int ch[MAXNODE][SIZE];
int f[MAXNODE],last[MAXNODE],val[MAXNODE];
int sz;
void init(){
sz = 1;
memset(ch[0], 0, sizeof ch[0]);
memset(vis,0,sizeof(vis));
}
int idx(char c){
return c - 'a';
}
void _insert(char* s, int v){
int u = 0,len = strlen(s);
for(int i = 0;i < len;i++){
int c = idx(s[i]);
if(!ch[u][c]){
memset(ch[sz], 0, sizeof ch[sz]);
val[sz] = 0;
ch[u][c] = sz++;
}
u = ch[u][c];
}
val[u] |= (1<<v);
}
void getFail(){
queue<int> q;
f[0] = 0;
for(int c = 0;c < SIZE;c++){
int u = ch[0][c];
if(u){
f[u] = 0;
q.push(u);
last[u] = 0;
}
}
while(!q.empty()){
int r = q.front();q.pop();
for(int c = 0;c < SIZE;c++){
int u = ch[r][c];
if(!u){
ch[r][c] = ch[f[r]][c];
continue;
}
q.push(u);
int v = f[r];
while(v && !ch[v][c]) v = f[v];
f[u] = ch[v][c];
last[u] = val[f[u]]?f[u]:last[f[u]];
val[u] |= val[last[u]];
}
}
}
void Print(int u){
if(fa[u] != -1){
Print(fa[u]);
printf("%c",alp[u] + 'a');
}
}
bool bfs(){
int tot, p, u, s, c;
queue<int> q;
fa[0] = -1,tot = cur[0] = mask[0] = 0;
vis[0][0] = 1;
q.push(tot++);
while(!q.empty()){
p = q.front();q.pop();
u = cur[p], s = mask[p];
if(s == s1){
Print(p);
return true;
}
for(int i = 0;i < SIZE;i++){
c = ch[u][i];
if(val[c] & s2) continue;///不能包含不喜欢子串
if(vis[c][s | val[c]]) continue;
vis[c][s | val[c]] = 1;
fa[tot] = p,mask[tot] = val[c] | s,alp[tot] = i,cur[tot] = c;
q.push(tot++);
}
}
return false;
}
}ac;
int main()
{
char text[310];
while(scanf("%d%d",&n,&m)==2){
ac.init();
s1 = (1<<n) - 1,s2 = (1<<(n+m)) - (1<<n);
for(int i = 0;i < n + m;i++) {
scanf("%s",text);
ac._insert(text,i);
}
ac.getFail();
if(!ac.bfs()) printf("-");
printf("
");
}
return 0;
}
F
思路: $ dp[i][j] $表示前i个字符第i个选字母j的最小费用
$ dp[i][j] = cost(i,j) + $ (min){(dp[i-1][k])}
(用mi[i]表示)(min){(dp[i-1][k])} 降低复杂度 避免TLE
G
题意：将数字1-n按字典序排列，求字典序第k小，$ n <= 1e6 $
思路：
方法一：字典树查第k小+离线操作
这种做法太骚了，直接把查询离线，从小到大插入到字典树中，顺便维护每个节点的size。那么我们能很容易的查找出第k大的路径，路径即对应了我们要查找的答案，最后再一次性输出答案即可。
这种做法非常的无脑，但是缺点在创建字典树需要大量的内存，不过这题数据范围给的非常大。
方法二：我在做这题的时候并没有想到离线，数据量太大，所以就没用字典树。实际完全可以模拟计算出每个点的size。
假设当前在前缀为s的地方，我们计算出走到它的右边即前缀为s+1的地方需要cnt次
若cnt <= k 那么 k -= cnt,s++
否则 k -= cnt ,s *= 10 答案肯定在前缀为s的子树中
重复上述两个步骤直到k = 0, s就是答案
现在关键就是如何求cnt了, 把字典树画出来后，能够直观看出来其实就是每一层右边的减去左边的
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
using namespace std;
const int N = 1e5 + 10;
int cal(int n,int x){
int y = x + 1, ans = 0;
while(x <= n){
ans += min(y,n + 1) - x;
x *= 10, y *= 10;
}
return ans;
}
int findkth(int n,int k){
int s = 1;
k--;
while(k){
int cnt = cal(n, s);
if(cnt <= k) k -= cnt, s++;
else k--,s *= 10;
}
return s;
}
int main(){
int T, n, k;
cin>>T;
while(T--){
scanf("%d%d",&n,&k);
printf("%d
",findkth(n,k));
}
}
H
题意：
楼下的面包店畅销的面包都快卖完了，只剩下了两种买的人少的面包。 第一种面包卖W1元，能增加H1点能量 第二种面包卖W2元，能增加H2点能量 现在小明身上只有C元，两种面包都有无限多个
那么小明最多能通过买面包增加多少点能量？
C, H1, H2, W1, W2(1 ≤ C, H1, H2, W1, W2 ≤ (10^9))
思路：这道题我yy了这么一种做法，就是尽快多取性价比高的，然后再慢慢分一些给另一种，然后答案取最优，然而WA。赛后我又想了想，我两种都尽可能的多取，然后再慢慢的分另一种，再设置一个上界$ 10 ^ 5 $，然后就A了。
去看正解，刚好(10^5 > sqrt{C})，所以可以说歪打正着和正解差不多。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL solve(int c,int h1,int w1,int h2,int w2){
LL cnt = c / w1;
int x = min(100000,(int)cnt);
LL ans = 0;
for(int i = 0;i <= x;i++){
ans = max(ans, (cnt - i) * h1 + (c - (cnt - i) * w1) / w2 * h2);
}
return ans;
}
int main(){
int c,h1,h2,w1,w2;
while(scanf("%d%d%d%d%d",&c,&h1,&h2,&w1,&w2)!=EOF){
if(h1 == h2){
if(w1 > w2) swap(w1, w2);
cout<<1LL * c / w1 * h1<<endl;
}else{
cout<<max(solve(c,h2,w2,h1,w1),solve(c,h1,w1,h2,w2))<<endl;
}
}
return 0;
}
J
题意：他有一条纸带，上面有n个数字，第i个数字为Ai。 他想把纸带选三个位置p1, p2, p3(p1 < p2 < p3)把纸带剪成4个每条长度至少为1的4条纸带。 分别为[1, p1-1], [p1+1, p2-1], [p2+1, p3-1], [p3+1, n],使得4个部分中数字之和相等。
$ n <= 10^5，0<= A[i] <= 10 ^ 9$
思路：本场最水的题了，特殊处理一下全为0的情况。
$ sum[i] $ 表示1到i的前缀和， 拿map记录一下(sum[i])出现的最左的位置。然后只要枚举p1即可，再判断是否合法即可。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e5 + 10;
LL sum[N];
int a[N];
map<LL,int> mp;
int main(){
int n;
while(scanf("%d",&n)==1){
sum[0] = 0,mp.clear();
for(int i = 1;i <= n;i++){
scanf("%d",a + i);
sum[i] = sum[i-1] + a[i];
if(!mp[sum[i]]) mp[sum[i]] = i;
}
if(sum[n] == 0){
printf("2 4 6
");
continue;
}
int flag = 0;
for(int p1 = 2;p1 + 5 <= n;p1++){
LL res = sum[p1-1];
LL x1 = res + sum[p1];
int p2 = mp[x1] + 1;
if(p2 == 1 || p2 == p1) continue;
x1 = sum[p2] + res;
int p3 = mp[x1] + 1;
if(p3 == 1 || p3 == p2) continue;
if(sum[n] - sum[p3] != res) continue;
printf("%d %d %d
",p1,p2,p3);
flag = 1;
break;
}
if(!flag) printf("-1
");
}
}