省选联考2022
先挖个坑，以后再来补（
upt 2022.9.22：补了 d1t2 和 d2t2。
预处理器
小模拟，开 \(2\) 个 \(\text{map}\)，一个记录定义的变换，一个记录在本次变换中是否已经经过。
然后就敲敲敲代码了。
代码：
#include<bits/stdc++.h>
#define pc(x) putchar(x)
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){f=ch=='-'?-1:f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
return x*f;
}
void write(int x)
{
if(x<0){x=-x;pc('-');}
if(x>9)write(x/10);
pc(x%10+48);
}
int n,len;
string s;
map<string,string>mp;
map<string,bool>vis;
bool check(char c)
{
if(c>='a'&&c<='z')return true;
if(c>='A'&&c<='Z')return true;
if(c>='0'&&c<='9')return true;
if(c=='_')return true;
return false;
}
void solve1()
{
int l=0,r=0;while(s[l]!=' ')++l;
++l;r=l;while(s[r]!=' ')++r;
string s1="";for(int i=l;i<r;++i)s1=s1+s[i];
string s2="";for(int i=r+1;i<len;++i)s2=s2+s[i];
mp[s1]=s2;
}
void solve2()
{
int l=0,r=0;while(s[l]!=' ')++l; ++l;
string s1="";for(int i=l;i<len;++i)s1=s1+s[i];
mp[s1]="";
}
string solve3(string s1)
{
string ans="";
int len1=(int)s1.size();
int l=0,r=0;
while(l<len1)
{
while(r<len1&&check(s1[r]))++r;
string s2="";for(int i=l;i<r;++i)s2=s2+s1[i];
string s3=mp[s2];
if((int)s3.size()<1||vis[s2])ans=ans+s2;
else
{
vis[s2]=true;
ans=ans+solve3(mp[s2]);
vis[s2]=false;
}while(r<len1&&!check(s1[r]))ans+=s1[r],++r;
l=r;
}return ans;
}
int main()
{
n=read();
for(int i=1;i<=n;++i)
{
getline(cin,s);len=(int)s.size();
if(s[0]=='#'&&s[1]=='d')solve1();
else if(s[0]=='#'&&s[1]=='u')solve2();
else cout<<solve3(s);
cout<<endl;
}return 0;
}
填树
发现不需要换根 dp，遂还是来补了一下，代码比较好打（拉插忘记取模，调一上午），千万千万不要忘记取模！！！
先想暴力树形 dp 怎么做。我们假设可选值域为 \([1,M]\)。
首先对题目中的答案可以容斥来计算，\([l,l+K]\) 的答案减去 \([l+1,l+K]\) 的答案就可以算出来树中非零最小值为 \(l\) 时极差小于等于 \(K\) 的数量。所以我们只需要计算出最小值分别为 \([1,M]\) 的时候的答案，就不会算重了。
设 \(res1\) 为当前区间的非零路径的个数，\(res2\) 为当前区间所有非零路径的权值和，\(val_u\) 为 \(u\) 在当前区间可选的权值个数，\(sum_u\) 为 \(u\) 在当前区间可选的权值之和，\(f_u\) 为 \(u\) 子树到 \(u\) 的非零路径数，\(g_u\) 为 \(u\) 子树到 \(u\) 的非零路径的权值和。
那么有转移：
\[\begin{aligned} res1 &= res1+f_uf_v \\ res2 &= res2+f_ug_v+g_uf_v \\ f_u &= f_u+f_vval_u \\ g_u &= g_u+g_vval_u+f_vsum_u \end{aligned} \]至此，枚举每个值域区间树形 dp 统计一次答案，时间复杂度为 \(O(nM)\)。
我们需要的是避免枚举整个值域，观察 \([l,l+K]\) 和 \([l_i,r_i]\) 的交的图像可以发现，是个分段函数，每个点都有 \(5\) 段，整个值域就被划分为了 \(O(n)\) 个段。在每一段中，所有点的权值个数只会有 \(3\) 种情况，\(-1,0,+1\)，所以每个点的权值个数在这一段中都是一个一次函数。那么 \(res1\) 就是 \(n\) 次函数，观察转移式又可以发现，\(res2\) 是至多 \(n-1\) 个一次函数和一个二次函数的乘积（比如 \(sum_u\)），也就是 \(n+1\) 次函数。因为我们每个段要求的是每个非零最小值的答案，所以想求出这个段的答案还需要做一遍前缀和，所以最高是 \(n+2\) 次函数。我们维护 \(n+3\) 个点值后用拉格朗日插值可以 \(O(n\log n)\) 求出这个段的答案。
总时间复杂度就是 \(O(n^3)\)。
代码 \(\text{2.87KB}\)，我 \(\text{define int long long}\) 加滥用取模，测试点时间之和 \(\text{6.81s}\) 通过此题。
代码：
#include<bits/stdc++.h>
#define pc(x) putchar(x)
#define pb push_back
#define int long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){f=ch=='-'?-1:f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
void write(int x)
{
if(x<0){x=-x;putchar('-');}
if(x>9)write(x/10);
putchar(x%10+48);
}
const int mod=1e9+7;
int n,K,ans1,ans2,res1,res2;
int val[205],sum[205],f[205],g[205];
struct node{int l,r;}a[205];
int p[1005],m;
vector<int>e[205];
void dfs(int x,int fa)
{
f[x]=val[x];res1=(res1+val[x])%mod;
g[x]=sum[x];res2=(res2+sum[x])%mod;
for(int y:e[x])
{
if(y==fa)continue; dfs(y,x);
res1=(res1+f[x]*f[y]%mod)%mod;
res2=(res2+f[x]*g[y]%mod+g[x]*f[y]%mod)%mod;
f[x]=(f[x]+f[y]*val[x]%mod)%mod;
g[x]=(g[x]+g[y]*val[x]%mod+f[y]*sum[x]%mod)%mod;
}
}
void calc(int l,int r,int op)
{
for(int i=1;i<=n;++i)
{
if(a[i].r<l||a[i].l>r)val[i]=0,sum[i]=0;
else if(a[i].l<l&&a[i].r>r)val[i]=r-l+1,sum[i]=(l+r)*(r-l+1)/2%mod;
else if(a[i].l<l)val[i]=a[i].r-l+1,sum[i]=(l+a[i].r)*(a[i].r-l+1)/2%mod;
else if(a[i].r>r)val[i]=r-a[i].l+1,sum[i]=(a[i].l+r)*(r-a[i].l+1)/2%mod;
else val[i]=a[i].r-a[i].l+1,sum[i]=(a[i].l+a[i].r)*(a[i].r-a[i].l+1)/2%mod;
}res1=res2=0;dfs(1,0);
ans1=(ans1+res1*op+mod)%mod;
ans2=(ans2+res2*op+mod)%mod;
}
int f1[205],f2[205];
int fac[205],pre[205],suf[205];
int qpow(int x,int y=mod-2)
{
int res=1;
while(y)
{
if(y&1)res=res*x%mod;
x=x*x%mod;y>>=1;
}return res;
}
int LGRG(int x,int *y)
{
fac[0]=pre[0]=suf[n+4]=1;int res=0;
for(int i=1;i<=n+3;++i)fac[i]=fac[i-1]*i%mod;
for(int i=1;i<=n+3;++i)pre[i]=pre[i-1]*(x-i+mod)%mod;
for(int i=n+3;i>=1;--i)suf[i]=suf[i+1]*(x-i+mod)%mod;
for(int i=1;i<=n+3;++i)
{
int tmp=fac[i-1]*fac[n+3-i]%mod;tmp=(n+1-i)&1?mod-tmp:tmp;
tmp=qpow(tmp)*pre[i-1]%mod*suf[i+1]%mod;
res=(res+tmp*y[i]%mod+mod)%mod;
}return res;
}
signed main()
{
n=read(),K=read();p[m=1]=0;
for(int i=1;i<=n;++i)
{
a[i]={read(),read()};
p[++m]=a[i].l,p[++m]=a[i].r;p[1]=max(p[1],a[i].r+1);
p[++m]=max(0ll,a[i].l-K);p[++m]=max(0ll,a[i].r-K);
}sort(p+1,p+m+1);m=unique(p+1,p+m+1)-(p+1);
for(int i=1;i<n;++i)
{
int u=read(),v=read();
e[u].pb(v);e[v].pb(u);
}
for(int i=1,j;i<m;++i)
{
int l=p[i],r=p[i]+K;
for(j=1;j<=n+3;++j,++l,++r)
{
if(l==p[i+1])break;
calc(l,r,1);calc(l+1,r,-1);
f1[j]=ans1,f2[j]=ans2;
}if(p[i+1]-p[i]<=n+3)continue;
ans1=LGRG(p[i+1]-p[i],f1),ans2=LGRG(p[i+1]-p[i],f2);
}write(ans1),pc('\n');write(ans2),pc('\n');
return 0;
}
学术社区
还没补
卡牌
首先简化题意，给你 \(n\) 个质因数集合，求有多少种选法使得集合的并包含询问的质因数集合。
容易想到暴力做法。
设 \(a_x\) 为 \(x\) 分解的质因数集合，\(c_x\) 为 \(x\) 的个数，\(f_{i}\) 为当前集合的并为 \(i\) 时的方案数。
那么显然可以进行转移：\(f_{j|a_x}=f_{j|a_x}+f_j\times(2^{c_x}-1)\)。
预处理出 \(2\) 的幂，用刷表法维护 \(f\)，时间复杂度为 \(O(nm\times 2^k)\)，\(k\) 为 \(n\) 个数的质因数个数。
思考如何优化暴力。
发现题目数据范围是 \(s_i\le 2000\)，所以想到根号状压。
具体的，前 \(13\) 个质因数可以状压，从 \(43\) 开始的质因数单独考虑。
由于每次询问 \(n\) 个数不变，而每次都重新状压则显然复杂度爆炸。
所以我们考虑对前 \(13\) 个质因数预处理出 \(f\) 数组。
对于大质因数每次询问单独考虑，这样的复杂度为 \(O(n\times 2^{13}+nm\times 2^{13})\)。
复杂度仍然炸掉，继续考虑优化。
观察转移式子，发现实际上一次转移就是 \(f\) 数组和 \(x\) 的集合幂级数 \(g(w)=w^0+(2^{c_x}-1)w^{a_x}\) 进行或卷积。
\[f_i=\sum_{j|k=i}f_j\times g_k \]那么我们可以不用维护 \(f_i\) 的真实值，维护它的点值就行了。
\(g(x)\) 只有 \(w_0\) 的系数是 \(1\)，\(w^{a_x}\) 的系数为 \(2^{c_x}-1\)，所以点值式子中，包含 \(a_x\) 的位置为 \(2^{c_x}\)，不包含则为 \(1\)。
因为所有位置上都是 \(2\) 的幂，所以只需要维护 \(2\) 的幂次就行了。
因为复杂度真正爆炸原因是每次询问都进行一遍大质因数的数的刷表，所以我们思考怎么能让大质因数也预处理出来贡献数组。
我们假设有大质因数的数都没有大质因数，那么可以将它的贡献预处理算在 \(f\) 中。
那还得考虑怎么去除某个询问大质因数没被包含的情况个数。
假设 \(g_{x,i}\) 是大质因数 \(x\) 对 \(f_i\) 的贡献，同样可以将其用点值的幂次表示出。
那么实际上答案就是 \(f/g_x\times(g_x-w^0)\)，\((g_x-w^0)\) 是大质因数 \(x\) 去除空集对 \(f\) 的贡献。
最后对 \(f\) 进行一次逆变换，求出真实值。答案即为包含询问质因数集合的 \(f_i\) 之和。
时间复杂度 \(O(2000\times2^{13}+c\log c+c\times 2^{13}+m\times 13\times 2^{13})\)
代码：
#include<bits/stdc++.h>
#define pc(x) putchar(x)
#define int long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){f=ch=='-'?-1:f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
void write(int x)
{
if(x<0){x=-x;putchar('-');}
if(x>9)write(x/10);
putchar(x%10+48);
}
const int mod=998244353;
const int S=(1<<13);
int n,m,ans;
int pri[15]={0,2,3,5,7,11,13,17,19,23,29,31,37,41};
int p2[4000006],cnt[2005],f[S],g[2005][S];
int p[18005],h[S],c,s;
void init()
{
p2[0]=1;//预处理2的幂
for(int i=1;i<=n;++i)p2[i]=(p2[i-1]<<1)%mod;
for(int i=1;i<=2000;++i)
{
int tmp=i;s=0;if(!cnt[i])continue;
for(int j=1;j<=13;++j)while(tmp%pri[j]==0)tmp/=pri[j],s|=(1<<(j-1));
for(int j=0;j<S;++j)if((j&s)==s)f[j]+=cnt[i];//点值相乘，幂次相加
if(tmp==43*43)tmp=43; if(tmp==1)continue;
for(int j=0;j<S;++j)if((j&s)==s)g[tmp][j]+=cnt[i];//大质因数的贡献
}
}
signed main()
{
n=read();
for(int i=1;i<=n;++i)++cnt[read()];
m=read();init();
while(m--)
{
c=read();ans=s=0;memcpy(h,f,sizeof h);
for(int i=1;i<=c;++i)p[i]=read();
sort(p+1,p+c+1);c=unique(p+1,p+c+1)-(p+1);//去重
for(int i=1;i<=c;++i)
for(int j=1;j<=13;++j)
if(p[i]==pri[j])s|=(1<<(j-1));//小质因数集合
for(int i=1;i<=c;++i)if(p[i]>41)
for(int j=0;j<S;++j)
h[j]-=g[p[i]][j];//去掉大质因数的贡献
for(int i=0;i<S;++i)h[i]=p2[h[i]];//进行非2的幂的乘法，要还原点值
for(int i=1;i<=c;++i)if(p[i]>41)
for(int j=0;j<S;++j)
h[j]=h[j]*(p2[g[p[i]][j]]-1)%mod;//乘上大质因数实际贡献
for(int i=1;i<S;i<<=1)
for(int j=0;j<S;++j)
if(j&i)h[j]=(h[j]-h[j^i]+mod)%mod;//IFMT求出真实值
for(int i=0;i<S;++i)if((i&s)==s)ans=(ans+h[i])%mod;//统计答案
write(ans),pc('\n');
}
return 0;
}
序列变换
当时的我连括号可以建树都不知道，但考场上想到了大贪心，\(4\) 种情况分开处理，每次都是外层括号向内层转移（其实这就是树了）。然而考场贪挂了，只有 \(36\) 分。/ll
首先发现，第一种操作就是将外层括号放进内层中，第二种操作可以让你在同一层里任意调换左括号的顺序，所以可以从外层向内一层层来处理。那么接下来就可以大力分讨了。
\(x=0,y=0\)：
每个左括号的贡献为 $0 $，答案就是 \(0\)。
void solve1(){puts("0");}
\(x=0,y=1\)：
对于同一层来说，因为最后只会留一个左括号在这一层且贡献为 \(0\)，而其他进内层的左括号都对答案有贡献，所以可以把这一层的最大值留在这里，其他进内层。
void solve2()
{
priority_queue<int>q;
int sum=0;//当前层的左括号权值和
for(int i=1;i<=n;++i)
{
for(int w:v[i])q.push(w),sum+=w;
sum-=q.top();q.pop();ans+=sum;
}write(ans),pc('\n');
}
\(x=1,y=0\)：
个人感觉这一种情况最不好想。
首先一个贪心是尽可能的用当前权值最小值的左括号去把其他左括号转移进内层。这样直接贪心显然不对，最小值进内层可能更优。
换个思路，操作完时，有 \(n-1\) 个左括号会留在 \(1\dots n-1\) 层，这些括号都对答案有贡献，而最后一个左括号在第 \(n\) 层没有贡献。所以第二个贪心是尽可能的让全局最大值进到最后一层，这样不会对答案有贡献。
考虑将两个贪心结合起来，既然最小值进内层可能更优，最大值进内层也可能更优，那让它们都进内层就行了，当前层留下一个非最大值非最小值的左括号就行了。因为第二个贪心中，中间值是一定对答案有贡献的，所以在本层放中间值一定不会使答案变劣。
但是，上面是存在中间值的处理方法，还有可能本层只有 \(2\) 个左括号。
首先，最大值如果不是全局最大值的话，就没有进内层的必要了，留着就行。最大值是全局最大值的话，进内层选其中一个都有可能使答案更优。但注意的是，如果是全局最大值进内层了，当且仅当它留在了最后才不会对答案有贡献。所以其实可以分 \(2\) 种情况考虑：全局最大值优先进内层，非全局最大值时最小值进内层；最小值优先进内层。两种情况都计算一遍答案取 \(\min\) 就行。
需要注意的是，在 \(n-1\) 层时，直接留下最小值，这样最大值才不会有贡献。
void solve3()
{
priority_queue<int,vector<int>,greater<int> >q;
int sum=0,siz=0,now=1e9;//sum是最小值进内层的答案，siz是当前左括号数量，now是当前最小值
for(int i=1;i<n;++i)//最小值进内层
{
siz+=v[i].size();
for(int w:v[i])q.push(w),now=min(now,w);
if(i==n-1){sum+=now;break;}
if(q.size()==1){q.pop();--siz;now=1e9;continue;}
--siz;sum+=(siz-1)*now;
q.pop();sum+=q.top();q.pop();
q.push(now);
}siz=0,now=1e9;while(!q.empty())q.pop();
for(int i=1;i<n;++i)//全局最大值进内层
{
siz+=v[i].size();
for(int w:v[i])q.push(w),now=min(now,w);
if(i==n-1){ans+=now;break;}
if(q.size()==1){q.pop();--siz;now=1e9;continue;}
if(q.size()==2)//就多这一部分
{
q.pop();
if(q.top()==mx){--siz;ans+=now;now=q.top();}
else{--siz;ans+=q.top();q.pop();q.push(now);}
//不是全局最大值的话仍然把最大值留在本层
}
else
{
--siz;ans+=(siz-1)*now;
q.pop();ans+=q.top();q.pop();
q.push(now);
}
}write(min(sum,ans)),pc('\n');
}
\(x=1,y=1\)：
因为留在本层或者进内层都会有贡献，所以我们需要的是尽可能减少最大值对答案的贡献。手算几个小样例就可以发现留着对答案的贡献会不多于进内层的贡献，所以可以将最大值直接留着，这样对答案的贡献最小。还是贪心的处理括号，用最小值的左括号将非最大值的左括号全部转移进内层，再用最大值的左括号转移最小值的左括号进内层。
void solve4()
{
priority_queue<int>q;
int sum=0,siz=0,now=1e9;//sum是当前层的和，siz是当前左括号数量，now是当前最小值
for(int i=1;i<=n;++i)
{
siz+=v[i].size();
for(int w:v[i])q.push(w),sum+=w,now=min(now,w);
if(q.size()==1){q.pop();--siz;sum=0;now=1e9;continue;}
ans+=sum+(siz-2)*now;sum-=q.top();q.pop();--siz;
}write(ans),pc('\n');
}
完整代码就不贴了。
嘤嘤嘤，考场挂到 \(36\) 分。/kk
最大权独立集问题
毒瘤题
标签：括号,省选,sum,内层,int,2022,质因数,联考,mod From： https://www.cnblogs.com/ctldragon/p/16534329.html