终于有机会补NOIP的题了
T1
考虑枚举 C 与 F 的纵列
考虑预处理出每个点最左边和最下边可以延伸到哪
之后枚举列，然后对行做类似于扫描线的操作，统计有多少可行的 "第一横行"，然后把当前的行钦定为 "第二横行"，相乘贡献进答案
对于 F 要额外乘上向下延伸的可能方案
时间复杂度 \(\Theta(Tnm)\)
Code
#include<bits/stdc++.h>
#define int long long
#define reg register
using namespace std;
const int N=1e3+10,mod=998244353;
int n,m,c,f;
long long ans1,ans2;
int len[N][N],down[N][N];
char a[N][N];
signed main(){
reg int _,id; scanf("%lld%lld",&_,&id);
while (_--){
ans1=ans2=0;
scanf("%lld%lld%lld%lld",&n,&m,&c,&f);
for (reg int i=1;i<=n;i++) scanf("%s",a[i]+1);
for (reg int i=1;i<=n+1;i++) for (reg int j=1;j<=m+1;j++) len[i][j]=down[i][j]=0;
for (reg int j=m;j;j--) for (reg int i=1;i<=n;i++) if (a[i][j]=='0') len[i][j]=len[i][j+1]+1;
for (reg int i=n;i;i--) for (reg int j=1;j<=m;j++) if (a[i][j]=='0') down[i][j]=down[i+1][j]+1;
// for (reg int i=1;i<=n;i++,puts("")) for (reg int j=1;j<=m;j++) cout<<len[i][j]<<" ";
for (reg int j=1;j<=m;j++){
reg long long sum=0,cnt=0;
for (reg int i=1;i<=n;i++) if (a[i][j]=='1') cnt=sum=0; else{
ans1=(ans1+1ll*(len[i][j]-1)*sum%mod)%mod;
if (cnt) sum+=len[i-1][j]-1,sum%=mod; cnt++;
}
}
for (reg int j=1;j<=m;j++){
reg long long sum=0,cnt=0;
for (reg int i=1;i<=n;i++) if (a[i][j]=='1') cnt=sum=0; else{
ans2=(ans2+1ll*(len[i][j]-1)*sum%mod*(down[i][j]-1)%mod)%mod;
if (cnt) sum+=len[i-1][j]-1,sum%=mod; cnt++;
}
}
printf("%lld %lld\n",(ans1*c%mod+mod)%mod,(ans2*f%mod+mod)%mod);
}
return 0;
}
T2
约定：记位置 \(i\) 之后出现同色位置为 \(g_i\)，\((A_1,A_2,A_3…A_n)\) 表示从栈顶到栈底分别为 \(A_n,A_{n-1}…A_1\) 的栈
首先考虑 \(k=2n-2\) 的时候怎么做
可以让 \(n-1\) 个栈每个放两种颜色，剩下一个空栈用来消除其它栈的栈底部
考虑怎么拓展到 \(k=2n-1\)
考虑最极端的情况，当前 \(n-1\) 个栈都填满了两个颜色，接下来要填一个新颜色
这个颜色有两种选择，可以放在某个栈的顶部，那么那个 3 元栈中间就消不掉，或者放在空栈，那么剩下元素的栈底就消不掉
发现能不堵在空栈就不堵在空栈，所以考虑找到一个栈 \((A,B),s.t. g_B>g_A\)，那么在消除 \(B\) 之前 \(A\) 已经被消除了，\(B\) 的消除不会受到影响，这就解决了 \((A,B,C)\) 中 \(B\) 元素的消除
如果没有找到这样一个栈，那么所有的栈顶一定在栈底被消除之前消除，则可以把当前的元素放在空栈中
注意到如果按照后一种方式消除，会产生一下问题 \((A,B)\) 被替换为 \((A,c)\)，但此时 \(g_C>g_A\) 会导致不能消除，于是在选择单元栈时贪心选择对应 \(g\) 最大一个。
总结一下过程：首先如果空栈个数大于 1，那么直接选择；接下来如果有单元栈，选择元素对应 \(g\) 最大的一个。若都没有，选择 \(g_B>g_A\) 的 \((A,B)\)，最后实在没有选空栈
这个过程开三个 set 维护，分别为元素个数为 0,1,2。 时间复杂度 \(\Theta(S \log n)\)
Code
#include<bits/stdc++.h>
#define reg register
using namespace std;
inline int read(){
int k=1,x=0;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') k=-1; ch=getchar();}
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=getchar();
return k*x;
}
inline int cmin(reg int x,reg int y){return x<y?x:y;}
inline int cmax(reg int x,reg int y){return x>y?x:y;}
inline int cabs(reg int x){return x<0?-x:x;}
const int N=2e6+10,M=1e4+10,mod=1e9+7;
int debug=0;
struct Query{int op,x,y;}ans[N<<1];
struct Node{int op,x;inline bool operator<(const Node &rhs)const{return op==rhs.op?x>rhs.x:op>rhs.op;}};
int n,m,k,cnt,g[N],vis[N],s[M][4],top[M],bel[N],a[N];
vector<int> v[M]; set<Node> q1,q2,q0;
inline void work(reg int x,reg int y){if (y) ans[++cnt]=(Query){2,x,y}; else ans[++cnt]=(Query){1,x,0};}
inline void Ins(reg int id,reg int x){bel[x]=id;s[id][++top[id]]=x,work(id,0);}
inline void solve(){
for (reg int i=1;i<=m;i++) v[a[i]].push_back(i);
for (reg int i=1;i<=n;i++) q0.insert((Node){0,i});
for (reg int i=1;i<=k;i++) for (reg int j=0;j<v[i].size();j+=2) g[v[i][j]]=v[i][j+1],g[v[i][j+1]]=v[i][j],vis[v[i][j]]=1;
for (reg int i=1;i<=m;i++){
if (vis[i]){
if (q0.size()>1){
auto it=*q0.begin();
q0.erase(it); Ins(it.x,i);
q1.insert((Node){g[i],it.x});
}else if (!q1.empty()){
auto it=*q1.begin();
q1.erase(it); Ins(it.x,i);
q2.insert((Node){g[i]>it.op,it.x});
}else{
if ((*q2.begin()).op){
auto it=*q2.begin();
q2.erase(it); Ins(it.x,i);
}else{
auto it=*q0.begin();
q0.erase(it); Ins(it.x,i);
q1.insert((Node){g[i],it.x});
}
}
}else{
reg int now=bel[g[i]];
if (s[now][top[now]]==g[i]){
work(now,0);
if (top[now]==1) q1.erase((Node){g[s[now][1]],now});
else if (top[now]==2) q2.erase((Node){g[s[now][2]]>g[s[now][1]],now});
top[now]--;
if (top[now]==0) q0.insert((Node){0,now});
else if (top[now]==1) q1.insert((Node){g[s[now][1]],now});
else if (top[now]==2) q2.insert((Node){g[s[now][2]]>g[s[now][1]],now});
}else{
reg int emp=(*q0.begin()).x;
work(emp,0),work(emp,now);
if (top[now]==1) q1.erase((Node){g[s[now][1]],now});
else if (top[now]==2) q2.erase((Node){g[s[now][2]]>g[s[now][1]],now});
for (reg int i=1;i<top[now];i++) s[now][i]=s[now][i+1];
top[now]--;
if (top[now]==0) q0.insert((Node){0,now});
else if (top[now]==1) q1.insert((Node){g[s[now][1]],now});
else if (top[now]==2) q2.insert((Node){g[s[now][2]]>g[s[now][1]],now});
}
}
}
printf("%lld\n",cnt);
for (reg int i=1;i<=cnt;i++) if (ans[i].op==1) printf("1 %d\n",ans[i].x); else printf("2 %d %d\n",ans[i].x,ans[i].y);
}
inline void clear(){
q0.clear();q1.clear();q2.clear(); cnt=0;
for (reg int i=1;i<=k;i++) v[i].clear();
for (reg int i=1;i<=n;i++) top[i]=0;
for (reg int i=1;i<=m;i++) g[i]=bel[i]=vis[i]=0;
}
signed main(){
reg int _=read();
while (_--){
n=read(),m=read(),k=read(); for (reg int i=1;i<=m;i++) a[i]=read();
clear(); solve();
}
return 0;
}
T3
首先考虑将边双缩点，边双内部的边可以任意选择选或不选。
接下来考虑树型 dp。定义 \(dp_{u,1/0}\) 表示以 \(u\) 为根的子树中有没有关键点的方案数，转移如下，记：
则
\[f_{u,0}=\prod_{v \in son\{u\}} f_{v,0} \]\[f_{u,1}=(A-f_{u,0})(2^{sz_u})+f_{u,0}(2^{sz_u}-1) \]其中 \(sz_u\) 表示 \(u\) 代表的边双大小
考虑如何统计答案，我们在每个节点 \(u\) 钦定关键点只存在于 \(u\) 子树中
其中 \(tot\) 表示边双个数，\(size_u\) 表示缩点后 \(u\) 的子树大小
特别地，为了避免算重。每次统计答案时钦定边 \(fa_u \to u\) 不选择
Code
#include<bits/stdc++.h>
#define int long long
#define reg register
using namespace std;
inline int read(){
int k=1,x=0;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') k=-1; ch=getchar();}
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=getchar();
return k*x;
}
inline int cmin(reg int x,reg int y){return x<y?x:y;}
inline int cmax(reg int x,reg int y){return x>y?x:y;}
const int N=1e6+10,mod=1e9+7;
int n,m,head[N],cnt,ky[N];
struct EDGE{int pre,to;}edge[N<<1];
inline void add(reg int u,reg int v){edge[++cnt]=(EDGE){head[u],v},head[u]=cnt;}
int dfn[N],dfc,low[N],vis[N],s[N],top,tot,bel[N],sz[N],pw[N];
inline void tarjan(reg int u,reg int fa){
dfn[u]=low[u]=++dfc;vis[u]=1,s[++top]=u;
for (reg int i=head[u],v;v=edge[i].to,i;i=edge[i].pre) if (v^fa){
if (!dfn[v]) tarjan(v,u),low[u]=cmin(low[u],low[v]);
else if (vis[v]) low[u]=cmin(low[u],dfn[v]);
}
if (low[u]==dfn[u]){
tot++; reg int v;
while (v=s[top--]){bel[v]=tot,sz[tot]++;if (v==u) break;}
}
}
vector<int> G[N];
int ans,f[N][2],size[N];
inline void dfs(reg int u,reg int fa){ size[u]=f[u][0]=f[u][1]=1;
for (auto v:G[u]) if (v^fa){ dfs(v,u); size[u]+=size[v];
f[u][1]=f[u][1]*((2*f[v][0]%mod+f[v][1])%mod)%mod;
f[u][0]=f[u][0]*f[v][0]%mod*2%mod;
} f[u][1]-=f[u][0],f[u][1]%mod; f[u][1]=(f[u][1]*pw[sz[u]]%mod+f[u][0]*(pw[sz[u]]-1)%mod)%mod;
ans+=f[u][1]*(u==1?pw[0]:pw[tot-1-size[u]]),ans%=mod;
}
int u[N],v[N];
signed main(){
n=read(),m=read(); pw[0]=1;
for (reg int i=1;i<=cmax(n,m);i++) pw[i]=pw[i-1]*2%mod;
for (reg int i=1;i<=m;i++) u[i]=read(),v[i]=read(),add(u[i],v[i]),add(v[i],u[i]);
tarjan(1,0);
for (reg int i=1;i<=m;i++) if (bel[u[i]]!=bel[v[i]]) G[bel[u[i]]].push_back(bel[v[i]]),G[bel[v[i]]].push_back(bel[u[i]]);
for (reg int i=1;i<=tot;i++){sort(G[i].begin(),G[i].end());G[i].erase(unique(G[i].begin(),G[i].end()),G[i].end());} dfs(1,0);
printf("%lld",(ans*pw[m-(tot-1)]%mod+mod)%mod);
return 0;
}
T4
首先从一类问题引入；区间历史和
考虑这么一个问题，记 \(S(l,r,t)\) 表示 \(t\) 时刻 \([l,r]\) 的和
支持区间修改，维护任意 \(m\) 的 \(\sum_{i=1}^m S(l,r,i)\)
记 \(A_i\) 表示数组元素，\(B_i\) 表示区间历史和(不包括当前操作)
考虑定义一个辅助数组 \(C_i=B_i-t A_i\)
发现若 \(A_i\) 没有修改，那么 \(C_i\) 没有变化，若 \(A_i\) 修改，则
\(\Delta C_i=(B_i+A_i+x)-(t+1)(A_i+x)=-tx\) 即 \(-t \Delta A_i\)
这样就将问题转为区间加减与区间和查询的问题了
类似地，我们可以定义 \(S_i=A_iB_i\)，\(Ans_i\) 为历史和，\(C_i\) 的定义也是类似的
首先我们将所有的询问离线，按右端点排序。使用扫描线，此时的 "时刻" 变为当前的右端点。用线段树维护 \([l,r]\) 的区间历史和。
考虑扫描线从 \(r-1\) 变成 \(r\) 时带来的影响：有一段的区间最大值变成了 \(a_r(b_r)\)，剩下的不变。改变的区间容易用单调栈维护，问题变成了区间覆盖问题
考虑查询操作怎么实现，在线段树上维护区间的 \(\sum C,\sum A\)，则答案为 \(\sum C+(t+1)\sum S\)
接下来只需要维护区间信息与标记的合并与 lazytag 的合并即可
考虑 \(S_i\) 的影响因素有哪些，不难想到定义线段树信息
其中 \(len\) 是区间长度，转移矩阵是：
\[\begin{bmatrix} [ca=cb=0] & 0 & 0 & tags & 0 \\ [a=0]b & [a=0] & 0 & taga & 0 \\ [b=0]a & 0 & [b=0] & tagb & 0 \\ 0 & 0 & 0 & 1 & 0\\ ab & a & b & taglen & 1\end{bmatrix}\]其中 \(a,b\) 为区间覆盖后的元素，若为 \(0\) 则无变化
\(tags,taga,tagb,taglen\) 为标记
之后考虑 lazytag 合并，考虑一次修改后的变化如下：
再进行一次修改操作，考虑在保存了之间 \(C\) 的变化下的新增量
将上边 2,3,4 式带入 1 ，令 \(\sum S,\sum A,\sum B,\sum C,len\) 为未知量，得到系数
乘
\[\begin{bmatrix} [a=b=0] & [a=0]b & [b=0]a & ab & 0 \\ 0 & [a=0] & 0 & a & 0 \\ 0 & 0 & [b=0] & b & 0 \\ 0 & 0 & 0 & 1 & 0 \\ tags & taga & tagb & taglen & 1\end{bmatrix} \]最后考虑修改时的矩阵是什么
\[\Delta C = \Delta Ans - \Delta (t \cdot S)= \Delta Ans - \Delta (t \cdot S) \]展开得到 \(\Delta C=\Delta t \cdot S' -(t'+\Delta t)(S'+\Delta S)+t' \cdot S'\)
化简得到 \(\Delta C=-t \Delta S\)
最后考虑覆盖传入的标记是什么，根据上面推出的式子，得到
\(a=v,b=0,tags=t,taga=0,tagb=-vt,taglen=0\) 其中 \(v\) 为覆盖 \(A\) 的量，数组 \(B\) 的修改是类似的
Code
#include<bits/stdc++.h>
#define int long long
#define reg register
using namespace std;
inline int read(){
int k=1,x=0;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') k=-1; ch=getchar();}
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=getchar();
return k*x;
}
inline int cmin(reg int x,reg int y){return x<y?x:y;}
inline int cmax(reg int x,reg int y){return x>y?x:y;}
const int N=1e6+10,mod=1e9+7;
int n,m,head[N],cnt,ky[N];
struct EDGE{int pre,to;}edge[N<<1];
inline void add(reg int u,reg int v){edge[++cnt]=(EDGE){head[u],v},head[u]=cnt;}
int dfn[N],dfc,low[N],vis[N],s[N],top,tot,bel[N],sz[N],pw[N];
inline void tarjan(reg int u,reg int fa){
dfn[u]=low[u]=++dfc;vis[u]=1,s[++top]=u;
for (reg int i=head[u],v;v=edge[i].to,i;i=edge[i].pre) if (v^fa){
if (!dfn[v]) tarjan(v,u),low[u]=cmin(low[u],low[v]);
else if (vis[v]) low[u]=cmin(low[u],dfn[v]);
}
if (low[u]==dfn[u]){
tot++; reg int v;
while (v=s[top--]){bel[v]=tot,sz[tot]++;if (v==u) break;}
}
}
vector<int> G[N];
int ans,f[N][2],size[N];
inline void dfs(reg int u,reg int fa){ size[u]=f[u][0]=f[u][1]=1;
for (auto v:G[u]) if (v^fa){ dfs(v,u); size[u]+=size[v];
f[u][1]=f[u][1]*((2*f[v][0]%mod+f[v][1])%mod)%mod;
f[u][0]=f[u][0]*f[v][0]%mod*2%mod;
} f[u][1]-=f[u][0],f[u][1]%mod; f[u][1]=(f[u][1]*pw[sz[u]]%mod+f[u][0]*(pw[sz[u]]-1)%mod)%mod;
ans+=f[u][1]*(u==1?pw[0]:pw[tot-1-size[u]]),ans%=mod;
}
int u[N],v[N];
signed main(){
n=read(),m=read(); pw[0]=1;
for (reg int i=1;i<=cmax(n,m);i++) pw[i]=pw[i-1]*2%mod;
for (reg int i=1;i<=m;i++) u[i]=read(),v[i]=read(),add(u[i],v[i]),add(v[i],u[i]);
tarjan(1,0);
for (reg int i=1;i<=m;i++) if (bel[u[i]]!=bel[v[i]]) G[bel[u[i]]].push_back(bel[v[i]]),G[bel[v[i]]].push_back(bel[u[i]]);
for (reg int i=1;i<=tot;i++){sort(G[i].begin(),G[i].end());G[i].erase(unique(G[i].begin(),G[i].end()),G[i].end());} dfs(1,0);
printf("%lld",(ans*pw[m-(tot-1)]%mod+mod)%mod);
return 0;
}