网站建设预算策划,网站开发收税,虾皮跨境电商平台入驻,宁波商城网站建设种花
1.本题是一道前缀和优化加上枚举的问题。先考虑 C 因为 F 是 C 下边随便加一个点#xff0c;所以只要求出 C 就求出了 F 。
注意到#xff0c;并没有要求上下行一样#xff0c;唯一的要求是 C 的两个横要隔一行#xff0c;这就是问题的突破点#xff0c;这题很明显…种花
1.本题是一道前缀和优化加上枚举的问题。先考虑 C 因为 F 是 C 下边随便加一个点所以只要求出 C 就求出了 F 。
注意到并没有要求上下行一样唯一的要求是 C 的两个横要隔一行这就是问题的突破点这题很明显的计数计数则用到乘法原理和加法原理。
假设上边的有 a 个合法的横那考虑这一行每一个合法的横这里说的不同是长度不同给答案的贡献是什么是不是每一个贡献 a 那这一行有 b 个不同的合法的横那么答案就增加了 a×b那每一行都这么处理然后处理完一样就加上上一行的合法的方案数因为他要求两个横之间至少隔一行。当遇到土坑的时候就把记录数组清零即可。
想要求出 F 只要求出这一列上有多少合法的 C 就行了因为 F 是由 C 下边加上一个竖构成的所所以我们只要复制过来记录 C 的公式然后把他存在另一个数组里到时候每找到一个能种花的地方 F 的答案加上这个数组就好了。
要想快速查询每一行有多少个合法的横只需要预处理就可以了。
2.整体思路就是这样接下来是代码。
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N1010,mod998244353;
ll ac,af,c,f;
int n,m,id,t;
int d[N][N],ji,jif,jis;
char ma[N][N];
int main(){cintid;while(t--){memset(d,0,sizeof(d));cinnmcf;for(int i1;in;i){for(int j1;jm;j){cinma[i][j];}}for(int i1;in;i){for(int jm-1;j1;j--){if(ma[i][j]1) d[i][j]-1;else if(ma[i][j1]0) d[i][j]d[i][j1]1;}}for(int j1;jm;j){jijifjis0;for(int i1;in;i){if(d[i][j]-1){jijifjis0;continue;}acac%mod(1ll*d[i][j]*(ji%mod))%mod;af(af%modjif%mod)%mod;jif(jif(1ll*d[i][j]*(ji%mod)))%mod%mod;jimax(0,d[i-1][j]);}}cout(c*ac)%mod (f*af)%modendl;acaf0;}return 0;
}
建造军营
边没乘二悲
1.一道图论dp题。只有 B 国炸毁了图的割边才会使得图不连通进而可能会导致军营不连通。也就是说A 国可以随意地看守或不看守不是割边的边。因此想到边双缩点后用树形DP。
题目保证了给定的图连通那么缩点后的图也必然连通如果有多个双连通分量构成了环就不符合双连通分量的定义即这些首尾相连构成环的“双连通分量”应该被划在同一个双连通分量中。因此缩点后形成的图连通且无环也就形成了一棵树。设Vu表示双连通分量u中的点数Eu表示双连通分量中u的边数如果有n个双连通分量则问题可以转化为有一棵无根树每个节点有种不建造军营的方案和种建造军营的方案。
以1为根节点令 f(u,0/1) 表示以 u 为根的子树中没有/有军营的方案数。
发现每种状态所涵盖的情况过多不好转移。可以对状态添加限制
令 f(u,0/1) 表示以 u 为根的子树中没有/有军营的方案数若有军营则所有的军营必须通过已经派兵看守的边与 u 连通。
先想想该如何统计答案
对于每个结点u令u子树外的所有点都不建军营同时强制不选 fau→u 的边再累加方案数。
考虑转移
显然地难点在 f(u,1) 的转移上。
考虑每新增一个子节点 v 对 f(u,1) 产生的贡献。
若到新增前都还未建造一个军营则以 v 为根的子树中必须有军营即 f(u,1)←f(u,0)×f(v,1)。
若到新增前已经建造过军营则以 v 为根的子树中有没有军营皆可且当以 v 为根的子树中没有军营时v 点是否与 u 点连通皆可即 f(u,1)←f(u,1)×[2f(v,0)f(v,1)]。
综上f(u,1)←f(u,0)×f(v,1)f(u,1)×[2f(v,0)f(v,1)]。
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N5e510,M1e610,MOD1e97;
int n,m,p;
int tot,tot2,head[N],head2[N];
int cnt,top,stk[N],dfn[N],low[N],bel[N];
int deg[N],V[N],E[N],s[N];
bool ins[N];
ll ans,f[N][2];
struct edge{int to,nxt;
}e[M1],e2[M1];
void add(int u,int v){e[tot]edge{v,head[u]};head[u]tot;
}
void add2(int u,int v){e2[tot2]edge{v,head2[u]};head2[u]tot2;
}
void tarjan(int u,int fa){dfn[u]low[u]cnt,ins[stk[top]u]1;for (int ihead[u];i;ie[i].nxt){int ve[i].to;if(vfa) continue;if(!dfn[v]) tarjan(v,u),low[u]min(low[u],low[v]);else if(ins[v]) low[u]min(low[u],dfn[v]);}if(dfn[u]low[u]){p;int x;do{ins[xstk[top--]]0,bel[x]p;V[p];}while(x!u);}
}
ll qp(ll base,int e){ll res1;while(e){if(e1) resres*base%MOD;basebase*base%MOD;e1;}return res;
}
void dfs(int u,int fa){s[u]E[u];for(int ihead2[u];i;ie2[i].nxt){int ve2[i].to;if(vfa) continue;dfs(v,u);s[u]s[v]1;}
}
void dp(int u,int fa){for (int ihead2[u];i;ie2[i].nxt){int ve2[i].to;if(vfa) continue;dp(v,u);f[u][1](f[u][1]*(((f[v][0]1)f[v][1])%MOD)%MODf[u][0]*f[v][1]%MOD)%MOD;f[u][0]f[u][0]*((f[v][0]1)%MOD)%MOD;}if(u1) ans(ansf[u][1])%MOD;else ans(ansf[u][1]*qp(2,s[1]-s[u]-1))%MOD;
}
int main(){cinnm;while(m--){int u,v;cinuv;add(u,v),add(v,u);}tarjan(1,0);for(int u1;un;u){for(int ihead[u];i;ie[i].nxt){int ve[i].to;if(bel[u]!bel[v]) add2(bel[u],bel[v]);else E[bel[u]];}}for(int i1;ip;i){E[i]1;f[i][0]qp(2,E[i]);f[i][1]qp(2,V[i]E[i])-f[i][0];}dfs(1,0);dp(1,0);coutans;return 0;
}
比赛
1.20分暴力
大体思路将所有询问按照右端点排序按照r从大到小处理两个数组的最大值。
f[i]对于每个r,x[i]*y[i]的累加和,相当于固定左端点是i,右端点是[i,r]任意数的贡献和。答案为转化为固定p移动q时间复杂度为O(n*nn*q)应该只能过前两个测试点。
#includebits/stdc.h
using namespace std;
#define LL long long
const int N3e510;
struct Node{int l,id;
};
vectorNode d[N];
LL a[N],b[N];
LL f[N];
LL x[N],y[N];
LL ans[N];
int main(){int t;int n,q;cintn;for(int i1;in;i){cina[i];}for(int i1;in;i){cinb[i];}cinq;for(int i1;iq;i){int l,r;cinlr;d[r].push_back({l,i});}for(int r1;rn;r){for(int i1;ir;i){x[i]max(x[i],a[r]);y[i]max(y[i],b[r]);f[i]x[i]*y[i];}for(auto [l,id]:d[r]){for(int il;ir;i)ans[id]f[i];}}for(int i1;iq;i){printf(%lld\n, ans[i]);}return 0;
}
只会写暴力……
喵了个喵
1.一道模拟题。
当k2n-2时有3种操作
插入ins把不等于栈顶的数入栈。
删除del把等于栈顶的数入栈与栈顶消除。
连接con把数放到备用栈一个钦定的空栈再与某个栈底进行消除。插入时如果有高度为1的栈就任选一个插入否则就插到高度为0的栈中。显然这样的栈总是存在。
实现时可以用set也可以维护一个栈删除时用栈顶替换。
当k2n-1时这样的栈不总是存在了此时除了将要放入的数原数其他数都已存在。我们先忽略这个数继续往后做。有几种情况
等于原数如果执行到这里则不会出现连接操作而使用备用栈。把它们都放入备用栈中对消结束循环。
连接如果执行这种操作只有可能上面的数被放入偶数次。因此预先放入原数可以让后面偶数个数对消不会有影响。结束循环。
删除如果删除后栈为空可以把原数放入备用栈这个栈变成新的备用栈结束循环。否则继续。
插入直接插入。注意插入的地方要和之前保持一致不能放到别处
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N310,M2e610,KN*2;
int T,n,m,k,a[M];
int o[M],p[M],b,c[K],c2[K];
int s[N][2],t[N];
int f[N],e[N],z,e2[N],z2;
void ins(int x){if(t[x]1) e2[f[x]z2]x;else if(!t[x]) e[f[x]z]x;
}
void del(int x){if(t[x]1) f[e2[--z2]]f[x],e2[f[x]]e2[z2];else if(!t[x]) f[e[--z]]f[x],e[f[x]]e[z];
}
void ins(int y,int i){int xa[i];del(y);o[i]0;p[i]y;c[x]y;s[y][t[y]]x;ins(y);
}
void del(int y,int i){int xa[i];del(y);o[i]0;p[i]y;c[x]0;--t[y];ins(y);
}
void con(int y,int i){int xa[i];del(y);o[i]e[0];p[i]y;c[x]0;b;s[y][0]s[y][1];--t[y];ins(y);
}
int main(){cinT;while(T--){cinnmk;bm;memset(c,0,(k5)2);memset(t,0,(n5)2);memset(f,0,(n5)2);zz20;for(int in;i;--i)ins(i);for(int i1;im;i) cina[i];for(int i1,j1;im;ij){int xa[i];if(int yc[x]){if(s[y][t[y]-1]x)del(y,i);else con(y,i);}else if(z2||z1)ins(z2?e2[z2-1]:e[z-1],i);else for(ji1;;j){if(xa[j]){int ye[0];ins(y,i);del(y,j);break;}if(int yc[a[j]]){if(s[y][t[y]-1]a[j]){del(y,j);if(!t[y]){ins(e[0],i);break;}c2[a[j]]y;}else{con(y,j);ins(y,i);break;}}else ins(c2[a[j]],j);}}printf(%d\n,b);for(int i1;im;i){if(o[i]) printf(1 %d\n2 %d %d\n,o[i],p[i],o[i]);else printf(1 %d\n,p[i]);}}
}
