#include<bits/stdc++.h>
using namespace std;
const int N=3; //矩阵维数
typedef vector<pair<string,int> > VSI;
typedef pair<string,int> SI;
//带参数的矩阵乘法
void mul(VSI ans[N][N],SI a[N][N])
{
VSI res[N][N]; //临时矩阵
//模拟
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
for(int k=0;k<N;k++)
{
string s2=a[k][j].first; //参数
int i2=a[k][j].second; //系数
if(i2==0) continue; //优化,f(x)*0=0,不必继续往下计算
for(int l=0;l<ans[i][k].size();l++)
{
string s1=ans[i][k][l].first;
int i1=ans[i][k][l].second;
if(s2!="1"/*省略1*/) s1+=s2;
res[i][j].push_back({s1,i1*i2}); //参数:字符串直接加在后面;系数:直接相乘
}
}
//将临时矩阵复制到答案矩阵
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
ans[i][j].clear();
for(int k=0;k<res[i][j].size();k++) ans[i][j].push_back(res[i][j][k]);
}
return ;
}
//计数排序
unordered_map<char,int> h;
void Hash(char a)
{
if(!h.count(a)) h[a]=1;
else h[a]++;
return ;
}
//计数排序求最简单项式
string get_min(string a)
{
string res;
h.clear();
for(int i=0;i<a.length();i++) Hash(a[i]);
for(char x='a';x<='z';x++)
for(int i=1;i<=h[x];i++)
if(x!='h') res.push_back(x);
return res;
}
//化简
void simplify(VSI ans[N][N])
{
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
//对组成多项式的单项式求最简式
for(int k=0;k<ans[i][j].size();k++) ans[i][j][k].first=get_min(ans[i][j][k].first);
//排列项
sort(ans[i][j].begin(),ans[i][j].end());
//合并同类项
VSI res; //临时矩阵
int ne=0,num=0;
for(int k=0;k<ans[i][j].size();k=ne)
{
num=ans[i][j][k].second;
ne=k+1;
while(ne<ans[i][j].size() && ans[i][j][k].first==ans[i][j][ne].first)
{
num+=ans[i][j][ne].second;
ne++;
}
res.push_back({ans[i][j][k].first,num});
}
//将临时矩阵复制到答案矩阵
ans[i][j].clear();
for(int k=0;k<res.size();k++) if(res[k].second!=0) ans[i][j].push_back(res[k]);
}
return ;
}
//输出
void print(VSI ans[N][N])
{
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
for(int k=0;k<ans[i][j].size();k++) cout<<ans[i][j][k].second<<ans[i][j][k].first<<' ';
puts("");
}
puts("");
return ;
}
int main()
{
//填入第一个矩阵
VSI ans[N][N];
ans[0][0].push_back({"b",1});
ans[0][1].push_back({"a",1});
ans[0][2].push_back({"0",0});
ans[1][0].push_back({"a",-1});
ans[1][1].push_back({"b",1});
ans[1][2].push_back({"0",0});
ans[2][0].push_back({"0",0});
ans[2][1].push_back({"0",0});
ans[2][2].push_back({"1",1});
//填入后面相乘的矩阵
SI op1[N][N]=
{
{{"d",1},{"0",0},{"c",1}},
{{"0",0},{"1",1},{"0",0}},
{{"c",-1},{"0",0},{"d",1}}
};
SI op2[N][N]=
{
{{"1",1},{"0",0},{"0",0}},
{{"0",0},{"f",1},{"e",-1}},
{{"0",0},{"e",1},{"f",1}}
};
SI op3[N][N]=
{
{{"d",1},{"0",0},{"c",-1}},
{{"0",0},{"1",1},{"0",0}},
{{"c",1},{"0",0},{"d",1}}
};
SI op4[N][N]=
{
{{"b",1},{"a",-1},{"0",0}},
{{"a",1},{"b",1},{"0",0}},
{{"0",0},{"0",0},{"1",1}}
};
//带参数的矩阵乘法
mul(ans,op1);
mul(ans,op2);
mul(ans,op3);
mul(ans,op4);
//化简
simplify(ans);
//输出
print(ans);
return 0;
}
五一“欢乐”赛 题解
随机生成树 tree
题目描述
- 随机生成一棵树,一个节点的父亲为他的真因数之一;
- 请求出树上节点两两之间的距离和的期望。
题解
Subtask1($n\leq 15$)
暴力搜索每个节点的父亲编号,然后通过换根 dp 求得距离和,与情况总数做比即为答案。
时间复杂度为 $\Theta\left(n\prod\limits_{i=1}^n\left(\sigma_0(i)-1\right)\right)$。
Subtask6($n\leq 3\times 10^5$)
展开答案式。
$$
\begin{aligned}
&\sum_{i}\sum_{j}\texttt{dis}_T(i,j)\\
=&\sum_{i}\sum_{j}\texttt{dep}(i)+\texttt{dep}(j)-\texttt{dep}(\texttt{lca}(i,j))\\
=&\sum_{i}\left(n\times \texttt{dep}(i)+\sum_{j}\texttt{dep}(j)-\texttt{dep}(\texttt{lca}(i,j))\right)\\
=&2n\sum_i\texttt{dep}(i)-\sum_{i}\sum_{j}\texttt{dep}(\texttt{lca}(i,j))
\end{aligned}
$$
我们发现式子分成了两部分,根据期望的线性性,我们可以拆分答案,即
$$\mathbb{E}(\omega(T))=\mathbb{E}\left(2n\sum_i\texttt{dep}(i)\right)-\mathbb{E}\left(\sum_{i}\sum_{j}\texttt{dep}\left(\texttt{lca}(i,j)\right)\right)$$
前面的问题很好处理,不难看出
$$
\begin{aligned}
&\mathbb{E}(2n\sum_i\texttt{dep}(i))\\
=&2n\times\mathbb{E}(\sum_i\texttt{dep}(i))\\
=&2n\sum_i\mathbb{E}(\texttt{dep}(i))
\end{aligned}
$$
然而 $i\neq 1$ 时,有
$$
\mathbb{E}(\texttt{dep}(i))=\frac{\sum_{\texttt{fa}\mid i,\texttt{fa}\neq i}(\texttt{dep}_d)}{\sigma_0(i)-1}
$$
式子的第一部分被轻松解决,下面解决第二部分。
设 $f(\texttt{lca})$ 表示 $\texttt{lca}$ 被作为有序点对 $(i,j)$ 的 $\texttt{lca}$ 的次数。
$$
\begin{aligned}
&\sum_{i}\sum_{j}\texttt{dep}\left(\texttt{lca}(i,j)\right)\\
=&\sum_\texttt{u}\texttt{dep}(\texttt{u})\times\sum_i\sum_j\left[\texttt{lca}(i,j)=\texttt{u}\right]\\
=&\sum_\texttt{u}\texttt{dep}(\texttt{u})\times f_u
\end{aligned}
$$
如果求出了 $f_u$,由于它是与 $\texttt{dep}_u$ 无关的变量,所以我们可以直接乘起来得到答案。
我们可以用容斥原理来解决问题,具体地,对于两个节点 $i,j$ 的 $\texttt{lca}$ 必然有且仅有三种情况:
- $\texttt{lca}$ 是 $u$ 的祖先;
- $\texttt{lca}$ 是 $u$;
- $\texttt{lca}$ 是 $u$ 子树内的点;
不难发现,$\texttt{siz}_u^2$ 恰好包含了下面两种情况,也就是说,我们要求的 $f_u$ 为 $\texttt{siz}_u^2$ 减去第三种情况数,不难发现,它实际上就是
$$\sum_{v\in\texttt{son}_u}f_v$$
也就是说
$$f_u=\texttt{siz}_u^2-\sum_{v\in\texttt{son}_u}f_v$$
到这里,我们处理完了整个式子的展开,最后套上期望的格式,得到
$$
\texttt{siz}_i=1+\frac{\sum_{i\mid u,i\neq u}\texttt{siz}_u}{\sum_{i\mid u,i\neq u}1}
$$
然后枚举 $\texttt{lca}$ 处理即可。
std
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
const int MAXN=3e5+5;
int n,p;
struct modInt{
int x;
inline modInt(reg int x=0):x(x){
//assert(0<=x&&x<p);
return;
}
inline modInt operator+(const modInt& a)const{
reg int sum=x+a.x;
return sum>=p?sum-p:sum;
}
inline modInt operator-(const modInt& a)const{
reg int sum=x-a.x;
return sum<0?sum+p:sum;
}
inline modInt operator-(void)const{
return modInt(0)-*this;
}
inline modInt operator*(const modInt& a)const{
return 1ll*x*a.x%p;
}
};
inline modInt fpow(modInt x,reg int exp){
modInt res=1;
while(exp){
if(exp&1)
res=res*x;
x=x*x;
exp>>=1;
}
return res;
}
vector<int> V[MAXN];
modInt fac[MAXN],invfac[MAXN],inv[MAXN];
modInt dep[MAXN],f[MAXN],g[MAXN];
int main(void){
scanf("%d%d",&n,&p);
for(int i=1;i<=n;++i)
for(reg int j=i+i;j<=n;j+=i)
V[j].push_back(i);
fac[0]=1;
for(reg int i=1;i<=n;++i)
fac[i]=fac[i-1]*i;
invfac[n]=fpow(fac[n],p-2);
for(reg int i=n-1;i>=0;--i)
invfac[i]=invfac[i+1]*(i+1);
inv[0]=1;
for(reg int i=1;i<=n;++i)
inv[i]=invfac[i]*fac[i-1];
for(reg int u=2;u<=n;++u){
for(int v:V[u])
dep[u]=dep[u]+dep[v];
dep[u]=dep[u]*inv[V[u].size()]+1;
}
modInt ans=0;
for(reg int u=n;u>=2;--u){
static modInt siz[MAXN];
modInt sum=1;
siz[u]=1;
for(reg int v=u+u;v<=n;v+=u){
siz[v]=0;
for(int x:V[v/u])
siz[v]=siz[v]+siz[x*u];
siz[v]=siz[v]*inv[V[v].size()];
sum=sum+siz[v];
}
f[u]=sum*sum;
for(reg int v=u+u;v<=n;v+=u)
f[u]=f[u]-siz[v]*siz[v]*f[v];
ans=ans+dep[u]*(-f[u]*2+(n<<1)%p);
}
printf("%d\n",ans.x);
return 0;
}
矩形覆盖 cover
题目描述
- $n$ 块木板拼成的物体,求出把它切割成多个矩形的最小操作次数。
题解
Subtask1($n\leq 5$)
考虑枚举每一条木板之间要不要竖着切割,相邻两木板 $u,d$ 不同时要不要横着切割,求最小值即可。
时间复杂度为 $\Theta(2^{3n})$。
Subtask4($n\leq 500$)
发现题目存在限制,即横着切割的轨迹不能跨越竖着切割的痕迹。
也就是说,竖着切割把整个木板变成了多块子木板,这与动态规划的思想类似,考虑设计 $f_{l,r}$ 为解决 $[l,r]$ 区间木板的最小代价,不难得出
$$
f_{l,r}=\begin{cases}
0&,l=r\\
\min\{\texttt{cut}(l,r),\min_{i=l}^{r-1}\{f_{l,i}+f_{i+1,r}+1\}\}&,l\neq r
\end{cases}
$$
其中 $\texttt{cut}(l,r)$ 表示只用横向切割达成目的,不难用单调栈在 $\Theta(r-l)$ 的时间复杂度内求得。
不难用时间复杂度为 $\Theta(n^3)$ 的区间 dp 解决问题。
Subtask6($n\leq 2\times 10^3$)
不难发现我们可以优化求解 $\texttt{cut}(l,r)$ 的时间复杂度,左端点固定,右端点平移,即可在 $\Theta(n^2)$ 的复杂度内预处理完。
重新设计 dp 状态,设 $f_{i}$ 表示切割 $1\sim i$ 块木板的最小操作次数,那么
$$
f_i=\min\{\texttt{cut}(1,i),\min_{1\leq j < i}\{f_{j}+\texttt{cut}(j+1,i)\}\}
$$
时间复杂度为 $\Theta(n^2)$。
Subtask8($n\leq 5\times 10^5$)
不难发现,一个多边形如果它满足以下两个条件:
- 所有的边都与坐标轴平行或垂直;
- 凸,不存在一个内角大于 $\pi$;
它必定是一个矩形。
定义凸出来的角的顶点为凸点,凹进去的角的顶点为凹点。换句话说,我们要通过最小的次数消灭所有的凹点。
一次切割具有性质:切割不可能产生新的凹点,对凹点进行切割要么得到凸点,要么得到直线;
因为我们要消灭所有凹点,所以所有的凹点都要被我们切割一次,为了最优化答案,我们需要用最少的次数连接所有连线与坐标轴平行的凹点对。
因为题目限制中竖着切割会破坏横向切割的路径,也就是说,由于一开始这些操作都是合法的,而它们可能会变得不合法(两个端点变得分属两个多边形),所以在最优方案中,可以先进行这样的操作,只需要保证它们都还是合法的即可。而这等价于每个操作的端点都没有被切开,也就是任意两次操作都不相交。于是,我们的问题变成了求这些操作的最大独立集:两个操作之间有边,当且仅当它们相交。
这种点覆盖区间的最大匹配,我们用贪心法即可解决,用堆和单指针维护即可,时间复杂度 $\Theta(n\log_2n)$。
std
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
reg char ch=getchar();
reg int res=0;
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))res=10*res+(ch^'0'),ch=getchar();
return res;
}
const int MAXN=5e5+5;
struct Interval{
int l,r;
inline Interval(reg int l=0,reg int r=0):l(l),r(r){
return;
}
inline bool in(reg int x){
return l<=x&&x<=r;
}
inline bool operator<(const Interval& a)const{
return r<a.r;
}
inline bool operator>(const Interval& a)const{
return r>a.r;
}
};
inline bool cmp(const Interval& a,const Interval& b){
return a.l<b.l;
}
int n;
int u[MAXN],d[MAXN];
int cnt,p[MAXN];
int tot;
Interval inv[MAXN<<1];
inline void calc(reg int a[],reg int n){
reg int top=0;
static int S[MAXN];
for(reg int i=1;i<=n;++i){
if(a[i]==a[i-1])
continue;
if(a[i]>a[i-1])
S[++top]=i-1;
else{
while(top&&a[S[top]]>a[i])
--top;
if(top&&a[S[top]]==a[i])
inv[++tot]=Interval(S[top--]+1,i);
}
}
return;
}
int main(void){
n=read();
for(reg int i=1;i<=n;++i)
u[i]=read(),d[i]=read();
calc(u,n),calc(d,n);
reg int ans=0;
for(reg int i=2;i<=n;++i){
if(u[i]!=u[i-1]&&d[i]!=d[i-1])
p[++cnt]=i;
ans+=(u[i]!=u[i-1])+(d[i]!=d[i-1]);
}
sort(inv+1,inv+tot+1,cmp);
priority_queue<Interval,vector<Interval>,greater<Interval>/**/> Q;
ans-=cnt+tot;
for(reg int i=1,j=1;i<=cnt;++i){
while(j<=tot&&inv[j].l<=p[i])
Q.push(inv[j++]);
while(!Q.empty()&&Q.top().r<p[i])
Q.pop();
if(!Q.empty())
++ans,Q.pop();
}
printf("%d\n",ans);
return 0;
}
字串变换 strinq
题目描述
- 给你一个斐波那契串,查询多点的后缀排名。
题解
Subtask2($n\leq 30$)
考虑直接求出字符串,然后用倍增法求解后缀排名。
时间复杂度 $\Theta(n\texttt{fib}_n)$。
Subtask5($n\leq 10^{18}$)
作为后缀排名问题,显然建后缀数组不现实,自然的想法就是建出 SAM 然后遍历。
考虑这个特殊字符串的 SAM 有没有啥特殊结构。
注意到 $S_n=S_{n−1}S_{n−2}=S_{n−2}S_{n−3}S_{n−2}$。如果 $k=n-3$ 是奇数,那么注意到 $S_{k+1}S_k=S_{k+1}S_{k−1}S_{k−2}=\cdots=S_{k+1}S_{k−1}S_{k−3}\cdots S_4S_2S_1$ 而我们断言,$S_kS_{k+1}=S_{k+1}S_{k−1}S_{k−3}\cdots S_4S_1S_1S_0$。考虑归纳证明,基础情况是显然的。
而若这对于 $k−2$ 成立,则 $S_kS_{k+1}=S_kS_kS_{k−1}=S_kS_{k−1}S_{k−2}S_{k−1}=S_{k+1}S_{k−1}S_{k−3}S_{k−5}\cdots S_4S_1S_1S_0$ 因此,前后这两个部分实际上长得很像,除了最后两位一个是 $S_0S_1$ 一个是 $S_1S_0$ 以外(对于 $k$ 是偶数的情况也是一样的,只不过这两位反过来了而已)。
所以说,如果我们有了 $S_n−1$ 的 SAM,那么要得到 $S_n=S_{n−1}S_{n−2}$ 的 SAM,我们只要在后面拼上 $S_{n−2}$,然后将 $S_{n−1}$ 的倒数第二位与 $S_n$ 的最后一位连边即可。
所以说这个 SAM 的长相非常简单,就是一条主链再加上 $n-2$ 条额外的边。同时,其终态就是所有的 $S_n,S_{n−2},S_{n−4},\cdots,S_{n\bmod{2}}$ 对应的点。所以说,我们只要 $3n$ 个状态即可。
这样我们就得到了一个 $\Theta(n)$ 的做法。为了优化,注意到我们的询问 $i_j\leq 10^{18}$, 所以只要保留最后 $\Theta(\log i_j)$ 个状态即可。具体保留多少个可以简单的确定:把输入离 线,然后一边建 SAM 一边算从每个状态开始,可以得到多少个不同的后缀。如果这个值超过了所有输入的 $i_j$ 的最大值,那么就不建了即可。时间复杂度为 $\Theta(q\log i_j)$。不过当 $n$ 很小的情况需要暴力构造,但当 $n$ 这么小的时候直接求出所有后缀排序即可,没必要对每个 $n$ 都手动构造一遍 SAM。
std
#include <algorithm>
#include <cstdio>
#include <vector>
#include <string>
#include <tuple>
using ll = long long;
std::pair<ll, ll> get_fib(ll n, ll MOD)
{
if (!n)
return std::make_pair(0, 1);
ll x, y;
if (n & 1)
{
std::tie(x, y) = get_fib(n - 1, MOD);
return std::make_pair(y, (x + y) % MOD);
}
else
{
std::tie(x, y) = get_fib(n >> 1, MOD);
return std::make_pair((y * 2 - x + MOD) * x % MOD,
(x * x + y * y) % MOD);
}
}
ll qry[500005];
void solve_small(int n, int q, int MOD)
{
static std::string fib[] = {"b", "a", "ab", "aba", "abaab"};
std::string str = fib[n];
std::vector<std::string> suf;
for (int i = 0; i < str.size(); i++)
suf.push_back(str.substr(i));
std::sort(suf.begin(), suf.end());
for (int i = 0; i < q; i++)
printf("%d%c", (str.size() - suf[qry[i] - 1].size() + 1) % MOD, " \n"[i + 1 == q]);
}
struct Node
{
int trans[2];
ll len[2], ways;
bool is_end;
} node[305];
int main()
{
ll n, MOD;
int q;
scanf("%lld%d", &n, &q);
for (int i = 0; i < q; i++)
scanf("%lld", qry + i);
scanf("%lld", &MOD);
if (n <= 4)
{
solve_small(n, q, MOD);
return 0;
}
for (int i = 0; i < 300; i++)
{
node[i].trans[0] = node[i].trans[1] = -1;
node[i].len[0] = node[i].len[1] = 0;
node[i].ways = 0;
node[i].is_end = false;
}
ll bound = *std::max_element(qry, qry + q), m = n;
int tot = 0;
while (m >= 5)
{
node[tot].is_end = (m & 1) == (n & 1);
if (tot)
{
node[tot].trans[0] = tot - 1;
node[tot].len[0] = get_fib(m - 1, MOD).second - 2;
}
if (m & 1) // ba
{
if (tot)
{
node[tot + 2].trans[0] = tot - 2;
node[tot + 2].len[0] = 1;
}
node[tot + 2].trans[1] = tot + 1;
node[tot + 2].len[1] = 1;
node[tot + 1].trans[0] = tot;
node[tot + 1].len[0] = 1;
}
else // ab
{
if (tot)
{
node[tot + 2].trans[1] = tot - 2;
node[tot + 2].len[1] = 1;
}
node[tot + 2].trans[0] = tot + 1;
node[tot + 2].len[0] = 1;
node[tot + 1].trans[1] = tot;
node[tot + 1].len[1] = 1;
}
for (int i = 0; i < 3; i++)
{
node[tot + i].ways = node[tot + i].is_end;
for (int c = 0; c < 2; c++)
{
if (~node[tot + i].trans[c])
node[tot + i].ways += node[node[tot + i].trans[c]].ways;
}
}
if (node[tot].ways >= bound && (m & 1 ^ 1))
break;
tot += 3;
m--;
}
if (node[tot].ways < bound || (m & 1))
{
// Small ones
if (n & 1 ^ 1)
node[tot].is_end = node[tot + 3].is_end = true;
else
node[tot + 2].is_end = node[tot + 4].is_end = true;
node[tot + 5].trans[1] = tot + 3;
node[tot + 5].len[1] = 1;
node[tot + 2].trans[1] = tot - 2;
node[tot + 2].len[1] = 1;
node[tot + 4].trans[0] = tot + 1;
node[tot + 4].len[0] = 1;
const std::string str = "abaaba";
for (int i = 0; i <= 5; i++)
{
int c = str[5 - i] - 'a';
node[tot + i].trans[c] = tot + i - 1;
node[tot + i].len[c] = 1;
}
for (int i = 0; i < 5; i++)
{
node[tot + i].ways = node[tot + i].is_end;
for (int c = 0; c < 2; c++)
{
if (~node[tot + i].trans[c])
node[tot + i].ways += node[node[tot + i].trans[c]].ways;
}
}
tot += 5;
m = 0;
}
ll fib = get_fib(n, MOD).second, pre = 0;
if (m)
{
pre = get_fib(m, MOD).second;
ll x = m / 2 - 1;
pre = (pre - get_fib(x * 2 + 1, MOD).second + 1 + MOD) % MOD;
}
for (int i = 0; i < q; i++)
{
ll ans = fib, rk = qry[i];
if (n & 1)
{
if (m && rk == 1)
ans--;
else
ans -= pre;
if (m)
rk--;
}
else
{
if (rk <= m / 2 - 2)
{
ans -= get_fib(rk * 2 + 2, MOD).second;
ans += get_fib(rk * 2 + 1, MOD).second - 1;
rk = 0;
}
else
{
rk -= std::max(0ll, m / 2 - 2);
ans -= pre;
}
}
for (int u = tot; rk; )
{
rk -= node[u].is_end;
if (!rk)
break;
int x = node[u].trans[0], y = node[u].trans[1];
if (~x && node[x].ways >= rk)
{
ans -= node[u].len[0];
u = x;
}
else
{
if (~x)
rk -= node[x].ways;
ans -= node[u].len[1];
u = y;
}
}
printf("%lld%c", (ans % MOD + MOD + 1) % MOD, " \n"[i + 1 == q]);
}
return 0;
}
密码保护:「QOJ2019」德高望重 admirable
「QOJ2349」鸿鹄之志 bird
题目
题目链接:QOJ2349。
题目限制
- 时间限制:$1\texttt{s}$;
- 空间限制:$512\texttt{MiB}$;
- 输入文件:
bird.in
; - 输出文件:
bird.out
。
题目背景
你从小就励志,要当世界第一的猛汉王。
题目描述
展现自我的时刻到了,现在你面前有 $n$ 位考官,每位考官都是多面手,具体地,每一位考官都有 $k$ 个属性值,其中第 $i$ 位考官的属性值分别为 $a_{i,0},a_{i,1},a_{i,2},\cdots,a_{i,k-1}$。
考官喜欢合伙刁难你,具体地,他们会对自己的各项属性进行线性组合,线性组合可以看做一个长度为 $k$ 的 $01$ 串,例如 $01000$。一个合法的线性组合集合 $\mathbb{S}$ 应该满足如下需求:
- 如果一个串 $a\in\mathbb{S}$ ,那么它的取反串 $a'\not\in\mathbb{S}$ ;
- 如果一个串 $a\in\mathbb{S}$,那么它应当满足 $\operatorname{cnt}(a)<\operatorname{cnt}(a')$ 或者 $\operatorname{cnt}(a)=\operatorname{cnt}(a')$ 的同时 $\operatorname{val}(a)< \operatorname{val}(a')$,其中 $\operatorname{cnt}(x)$ 表示 $x$ 中 $1$ 的个数,$\operatorname{val}(x)$ 表示 $x$ 的大小。
如果看不懂,你可以使用如下代码生成长度为 $n$ 的合法线性组合集合。
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
const int n=4; //改变这里的值,即可得出不同长度的线性组合集合
int main(void){
bitset<n> B;
for(reg int i=0;i<(1<<n);++i){
B=i;
if(n&1){
if(B.count()<=n/2)
cout<<B<<endl;
}
else{
if(B.count()<n/2)
cout<<B<<endl;
else if(B.count()==n/2&&i<(1<<(n-1)))
cout<<B<<endl;
}
}
return 0;
}
不难发现,长度为 $n$ 的线性组合集合 $\mathbb{S}$ 满足 $|\mathbb{S}|=2^{n-1}$。
定义一个考官的武德为一个 $2^{n-1}$ 元组,即上述线性组合集合中的每一个线性组合都对应一个武德值。具体地,对于一个线性组合 $s$,考官 $i$ 对应的武德值为 $\left(\sum\limits_{w=0}^{k-1}(-1)^{s_w}a_{i,w}\right)$。
与考官的武德相比,你总是有所不如,对于一个考官,你面对他的审查产生的尴尬值为两人武德差值绝对值的最大值,即 $\max\limits_{s_{j}\in\mathbb{S}}\left|A_j-\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}a_{i,w}\right)\right|$。
考官也喜欢不讲武德,总喜欢让你尴尬,他们会组织起来,对你进行多次审查,定义一次区间 $[l,r]$ 内考官审查你的尴尬值为 $\sum\limits_{i=l}^{r}\left(\max\limits_{s_{j}\in\mathbb{S}}\left|A_j-\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}a_{i,w}\right)\right|\right)$。
你可以在审查开始之前修炼自己的武德,即自由改变 $A_j$。请求出尴尬值的最小值。
输入格式
第一行,三个整数 $n,q,k$。
后 $n$ 行,每行 $k$ 个整数 $a_{i,0},a_{i,1},\cdots,a_{i,k-1}$。
后 $q$ 行,每行两个正整数 $l,r$ 表示询问区间。
输出格式
共 $q$ 行,表示每次询问尴尬值的最小值。
样例
样例输入
4 3 2
1 2
3 4
5 6
7 8
1 1
1 2
2 4
样例输出
0.000000
4.000000
8.000000
样例解释
$k=2$ 时,线性组合集合 $\mathbb{S}={[00],[01]}$。
第一次询问,考官属性为 ${[1,2]}$,对应的武德值为 ${(3,-1)}$,应选择 $A_0=3,A_1=-1$,尴尬值取最小为 $0$;
第二次询问,考官属性为 ${[1,2],[3,4]}$,对应武德值为 ${(3,-1),(7,-1)}$,应选择 $A_0\in[3,7]$,$A_1=-1$,尴尬值取最小为 $4$;
第三次询问,考官属性为 ${[3,4],[5,6],[7,8]}$,对应武德值为 ${(7,-1),(11,-1),(15,-1)}$,应选择 $A_0=11,A_1=-1$,尴尬值取最小为 $8$。
数据范围与提示
子任务编号 | $n$ | $q$ | $k$ | $a$ | 分数 |
---|---|---|---|---|---|
$1$ | $\leq 10$ | $0$ | $=1$ | $\lvert a\rvert\leq 10^9$ | $5$ |
$2$ | $\leq 100$ | $\leq 100$ | $=1$ | $\lvert a\rvert\leq 10^3$ | $10$ |
$3$ | $\leq 100$ | $\leq 100$ | $=1$ | $\lvert a\rvert\leq 10^5$ | $5$ |
$4$ | $\leq 100$ | $\leq 100$ | $=2$ | $\lvert a\rvert\leq 10^3$ | $5$ |
$5$ | $\leq 10^5$ | $\leq 10^5$ | $=2$ | $\lvert a\rvert\leq 10^9$ | $20$ |
$6$ | $\leq 100$ | $\leq 100$ | $\leq 10$ | $\lvert a\rvert\leq 10^5$ | $10$ |
$7$ | $\leq 10^4$ | $\leq 10^4$ | $\leq 10$ | $\lvert a\rvert\leq 10^5$ | $45$ |
对于 $100\%$ 的数据,保证 $1\leq l\leq r\leq n$。
题解
下面我们直接说正解。
不难发现下面的规律,它表明各个属性之间对答案的影响无关。
如果我们设 $A_j=\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}x_{i,w}\right)$ 其中 $x$ 是我们任意选择,那么我们就对题目进行了恒等变换,不影响答案。
$$
\begin{aligned}
&\max\limits_{s_{j}\in\mathbb{S}}\left|A_j-\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}a_{i,w}\right)\right|\\\
=&\max\limits_{s_{j}\in\mathbb{S}}\left|\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}x_{i,w}\right)-\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}a_{i,w}\right)\right|\\
=&\max\limits_{s_{j}\in\mathbb{S}}\left|\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}\left(x_{i,w}-a_{i,w}\right)\right)\right|
\end{aligned}
$$
我们发现事实上线性组合就是一个幌子,如果我们将线性组合取反,由于上面式子绝对值的作用,我们得到的结果相同。也就是说如果我们把线性组合扩充到包含它与它的取反,结果不变。
这样的话,新的线性组合集合就包含了 $2^k$ 个元素,对应所有属性值之差乘上 $+1$ 或者 $-1$ 的自由组合,所以我们进一步转化,得到
$$
\begin{aligned}
&\max\limits_{s_{j}}\left|\left(\sum\limits_{w=0}^{k-1} (-1)^{s_{j,w}}\left(x_{i,w}-a_{i,w}\right)\right)\right|\\
=&\sum\limits_{w=0}^{k-1} \max\limits_{s_{j}}\left|(-1)^{s_{j,w}}\left(x_{i,w}-a_{i,w}\right)\right|\\
=&\sum\limits_{w=0}^{k-1} \max\limits_{s_{j}}\left|\left(x_{i,w}-a_{i,w}\right)\right|\\
=&\sum\limits_{w=0}^{k-1} \left|x_{i,w}-a_{i,w}\right|\\
\end{aligned}
$$
进一步地,我们得出答案其实就是 $k$ 维货仓选址。
我们选择运用主席树来解决区间中位数问题,时间复杂度为 $\Theta\left((k(n+q)\log_2n)\right)$。
代码以后再放。
「QOJ2342」鸭性统计 duck
首先,聪明的你应该把$duck$反过来读:就是“可达”。
所以这道题就是“可达性统计”的模板题。
只不过,这道题把数据加强到了 $10^5$,并且本题中的图可能存在环。
就是这两个问题,我们一个一个来处理。
对于图中存在环的问题,我们只需要 $\texttt{tarjan}$一下,缩点染色一下就行了,因为在一个环内的两个点肯定两两互相可达,我们把他染成一个颜色并没有问题,其他的操作正常进行,$\texttt{tarjan}$ 缩点肯定大家都会。
接着,我们要对付 $10^5$ 的数据。
对于简单版的可达性统计,我们是建了 bitset<1005> b[1005]
,b[x][y]
代表的是否能从 $x$ 点到达 $y$ 点,我们用 $\texttt{bitset}$,是为了把第二维压成一个 01 串,从而降低空间。但是对于 $10^5$ 的数据我们把 $\texttt{bitset}$ 建出来:bitset<100005> b[100005]
。算一下,上了 $1000\texttt{MiB}$,肯定不可取。
那怎么办呢?
这里就要用到一个很常用的,很重要的技巧:牺牲时间复杂度来补救空间复杂度!
因为我们发现,时间复杂度太优秀了,空间复杂度太菜了。于是我们想到一个类似分块的思想来解决这个问题。
我们可以把 $Q$ 次询问分成 $k$ 段,每一段长为 $len$,然后一段一段地解决,一段一段地处理,我们将每一段询问中 $(u,v)$ 的 $v$ 做一个离散化操作,使得 $\texttt{bitset}$ 的第二维空间降下来,因为这一段最后真正有用的就这 $len$ 个点能否到达,至于其他点能否到达我们不在乎,将它们都看作编号为 0 即可。每一段询问都进行同样的操作,就可以通过本题。其实这样的方法也不叫分块,它就是把一个问题分成了几段,依次处理。
当然,在保证空间复杂度的前提下,$k$ 越小越好。
$code:$
#include<cmath>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<bitset>
#define reg register
using namespace std;
const int maxn=2e5+5;
const int mod=1e9+7;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
int n,m,Q;
int wugui=0;
int head1[maxn];
struct node
{
int to;
int nxt;
}edge[maxn];
void add(int x,int y)
{
wugui++;
edge[wugui].to=y;
edge[wugui].nxt=head1[x];
head1[x]=wugui;
}
int in[maxn];
queue<int> q;
vector<int> v[maxn];
int low[maxn];
int dfn[maxn];
int cnt=0;
int s[maxn];
int col[maxn];
int color=0;
int vis[maxn];
int index1=0;
struct Query
{
int x,y;
}ask[maxn];
//tarjan
void tarjan(int x)
{
low[x]=dfn[x]=++index1;
vis[x]=1;
s[++cnt]=x;
for(reg int i=0;i<(int)v[x].size();i++)
{
int t=v[x][i];
if(dfn[t]==0)
{
tarjan(t);
low[x]=min(low[x],low[t]);
}
else
{
if(vis[t]==1)
low[x]=min(low[x],dfn[t]);
}
}
if(dfn[x]==low[x])
{
int v;
color++;
do
{
v=s[cnt];
cnt--;
col[v]=color;
vis[v]=0;
}
while(v!=x);
}
}
bitset<20005> a[maxn];
int re_in[maxn];
int tot=0;
int b[maxn];
int id[maxn];
int Get(int x)
{
return lower_bound(s+1,s+1+tot,x)-s;
}
int order[maxn];
int ORDER=0;
void Work(int l,int r)
{
// re_sort & Get_id
tot=0;
int fuck=0;
for(reg int i=l;i<=r;i++)
b[++fuck]=col[ask[i].y];
sort(b+1,b+1+fuck);
b[0]=-1e9;
for(reg int i=1;i<=fuck;i++)
{
if(b[i]!=b[i-1])
s[++tot]=b[i];
}
// bitset_dp & topo
for(reg int i=1;i<=color;i++)
{
id[i]=Get(i);
if(s[id[i]]!=i)
id[i]=0;
a[i].reset();
if(re_in[i]==0)
{
q.push(i);
int x=id[i];
a[i][x]=1;
}
}
for(reg int j=1;j<=ORDER;j++)
{
int point=order[j];
int x=id[point];
a[point][x]=1;
for(reg int i=head1[point];i;i=edge[i].nxt)
{
int t=edge[i].to;
a[t] |= a[point];
}
}
// Get_ans
for(reg int i=l;i<=r;i++)
{
int x=col[ask[i].x];
int y=col[ask[i].y];
if(a[x][id[y]])
cout<<"Y";
else
cout<<"N";
}
}
int main()
{
//tarjan
n=read(),m=read(),Q=read();
for(int i=1;i<=m;i++)
{
int x=read(),y=read();
v[x].push_back(y);
}
for(int i=1;i<=n;i++)
{
if(dfn[i]==0)
tarjan(i);
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<(int)v[i].size();j++)
{
int x=col[i];
int y=col[v[i][j]];
if(x==y)
continue;
in[x]++;
add(y,x);
}
}
//topo_sort
for(int i=1;i<=color;i++)
re_in[i]=in[i];
for(reg int i=1;i<=color;i++)
{
if(in[i]==0)
q.push(i);
}
while(!q.empty())
{
int point=q.front();
q.pop();
order[++ORDER]=point;
for(reg int i=head1[point];i;i=edge[i].nxt)
{
int t=edge[i].to;
in[t]--;
if(in[t]==0)
q.push(t);
}
}
// divide segments
for(int i=1;i<=Q;i++)
ask[i].x=read(),ask[i].y=read();
int len=20000;
int now=1;
while(true)
{
if(now+len-1<Q)
{
Work(now,now+len-1); // Get_ans
now=now+len;
}
else
{
Work(now,Q); // Get_ans
break;
}
}
return 0;
}
密码保护:「QOJ2046」奇妙数论题 gcd
密码保护:「QOJ2173」国际象棋 chess
密码保护:「QOJ2307」古老谜题 puzzle
