2022NOIP比赛总结

embedded/2024/10/31 2:36:03/

种花

1.本题是一道前缀和优化加上枚举的问题。先考虑 C 因为 F 是 C 下边随便加一个点,所以只要求出 C 就求出了 F 。

注意到,并没有要求上下行一样,唯一的要求是 C 的两个横要隔一行,这就是问题的突破点,这题很明显的计数,计数则用到乘法原理和加法原理。

假设上边的有 a 个合法的横,那考虑这一行每一个合法的横(这里说的不同是长度不同)给答案的贡献是什么?是不是每一个贡献 a ,那这一行有 b 个不同的合法的横,那么答案就增加了 a×b,那每一行都这么处理,然后处理完一样就加上上一行的合法的方案数(因为他要求两个横之间至少隔一行)。当遇到土坑的时候就把记录数组清零即可。

想要求出 F ,只要求出这一列上有多少合法的 C 就行了(因为 F 是由 C 下边加上一个竖构成的),所所以我们只要复制过来记录 C 的公式然后把他存在另一个数组里到时候每找到一个能种花的地方 F 的答案加上这个数组就好了。

要想快速查询每一行有多少个合法的横,只需要预处理就可以了。

2.整体思路就是这样,接下来是代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1010,mod=998244353;
ll ac,af,c,f;
int n,m,id,t;
int d[N][N],ji,jif,jis;
char ma[N][N];
int main(){cin>>t>>id;while(t--){memset(d,0,sizeof(d));cin>>n>>m>>c>>f;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>ma[i][j];}}for(int i=1;i<=n;i++){for(int j=m-1;j>=1;j--){if(ma[i][j]=='1') d[i][j]=-1;else if(ma[i][j+1]=='0') d[i][j]=d[i][j+1]+1;}}for(int j=1;j<m;j++){ji=jif=jis=0;for(int i=1;i<=n;i++){if(d[i][j]==-1){ji=jif=jis=0;continue;}ac=ac%mod+(1ll*d[i][j]*(ji%mod))%mod;af=(af%mod+jif%mod)%mod;jif=(jif+(1ll*d[i][j]*(ji%mod)))%mod%mod;ji+=max(0,d[i-1][j]);}}cout<<(c*ac)%mod<<' '<<(f*af)%mod<<endl;ac=af=0;}return 0;
}

建造军营

(边没乘二,悲)

1.一道图论+dp题。只有 B 国炸毁了图的割边,才会使得图不连通,进而可能会导致军营不连通。也就是说,A 国可以随意地看守或不看守不是割边的边。因此想到边双缩点后用树形DP。

题目保证了给定的图连通,那么缩点后的图也必然连通,如果有多个双连通分量构成了环,就不符合双连通分量的定义,即这些首尾相连构成环的“双连通分量”应该被划在同一个双连通分量中。因此,缩点后形成的图连通且无环,也就形成了一棵树。设Vu表示双连通分量u中的点数,Eu表示双连通分量中u的边数,如果有n个双连通分量,则问题可以转化为:有一棵无根树,每个节点有2^{E_{u}}种不建造军营的方案和2^{E_{u}+V_{u}}-2^{E_{u}}种建造军营的方案。

以1为根节点,令 f(u,0/1) 表示以 u 为根的子树中没有/有军营的方案数。

发现每种状态所涵盖的情况过多,不好转移。可以对状态添加限制

令 f(u,0/1) 表示以 u 为根的子树中没有/有军营的方案数,若有军营,则所有的军营必须通过已经派兵看守的边与 u 连通。

先想想该如何统计答案:

对于每个结点u,令u子树外的所有点都不建军营,同时强制不选 fau​→u 的边,再累加方案数。

考虑转移:

显然地,f(u,0)=2^{E_{u}}*\prod_{v\in son(u)}2f(v,0),难点在 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)]。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10,M=1e6+10,MOD=1e9+7;
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[M<<1],e2[M<<1];
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 i=head[u];i;i=e[i].nxt){int v=e[i].to;if(v==fa) 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[x=stk[top--]]=0,bel[x]=p;V[p]++;}while(x!=u);}
}
ll qp(ll base,int e){ll res=1;while(e){if(e&1) res=res*base%MOD;base=base*base%MOD;e>>=1;}return res;
}
void dfs(int u,int fa){s[u]=E[u];for(int i=head2[u];i;i=e2[i].nxt){int v=e2[i].to;if(v==fa) continue;dfs(v,u);s[u]+=s[v]+1;}
}
void dp(int u,int fa){for (int i=head2[u];i;i=e2[i].nxt){int v=e2[i].to;if(v==fa) continue;dp(v,u);f[u][1]=(f[u][1]*(((f[v][0]<<1)+f[v][1])%MOD)%MOD+f[u][0]*f[v][1]%MOD)%MOD;f[u][0]=f[u][0]*((f[v][0]<<1)%MOD)%MOD;}if(u==1) ans=(ans+f[u][1])%MOD;else ans=(ans+f[u][1]*qp(2,s[1]-s[u]-1))%MOD;
}
int main(){cin>>n>>m;while(m--){int u,v;cin>>u>>v;add(u,v),add(v,u);}tarjan(1,0);for(int u=1;u<=n;u++){for(int i=head[u];i;i=e[i].nxt){int v=e[i].to;if(bel[u]!=bel[v]) add2(bel[u],bel[v]);else E[bel[u]]++;}}for(int i=1;i<=p;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);cout<<ans;return 0;
}

比赛

1.20分:暴力

大体思路:将所有询问按照右端点排序,按照r从大到小处理两个数组的最大值。

f[i]对于每个r,x[i]*y[i]的累加和,相当于固定左端点是i,右端点是[i,r]任意数的贡献和。答案为\sum _{i=l}^{r}f_i,转化为固定p,移动q,时间复杂度为O(n*n+n*q),应该只能过前两个测试点。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=3e5+10;
struct Node{int l,id;
};
vector<Node> 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;cin>>t>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){cin>>b[i];}cin>>q;for(int i=1;i<=q;i++){int l,r;cin>>l>>r;d[r].push_back({l,i});}for(int r=1;r<=n;r++){for(int i=1;i<=r;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 i=l;i<=r;i++)ans[id]+=f[i];}}for(int i=1;i<=q;i++){printf("%lld\n", ans[i]);}return 0;
}

只会写暴力…… 

喵了个喵

1.一道模拟题。

当k=2n-2时,有3种操作:

插入(ins):把不等于栈顶的数入栈。

删除(del):把等于栈顶的数入栈,与栈顶消除。

连接(con):把数放到备用栈(一个钦定的空栈),再与某个栈底进行消除。插入时,如果有高度为1的栈,就任选一个插入;否则就插到高度为0的栈中。显然这样的栈总是存在。

实现时,可以用set,也可以维护一个栈,删除时用栈顶替换。

当k=2n-1时,这样的栈不总是存在了,此时除了将要放入的数(原数),其他数都已存在。我们先忽略这个数,继续往后做。有几种情况:

等于原数:如果执行到这里,则不会出现连接操作而使用备用栈。把它们都放入备用栈中对消,结束循环。

连接:如果执行这种操作,只有可能上面的数被放入偶数次。因此预先放入原数,可以让后面偶数个数对消,不会有影响。结束循环。

删除:如果删除后栈为空,可以把原数放入备用栈,这个栈变成新的备用栈,结束循环。否则继续。

插入:直接插入。(注意插入的地方要和之前保持一致,不能放到别处)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=310,M=2e6+10,K=N*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 x=a[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 x=a[i];del(y);o[i]=0;p[i]=y;c[x]=0;--t[y];ins(y);
}
void con(int y,int i){int x=a[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(){cin>>T;while(T--){cin>>n>>m>>k;b=m;memset(c,0,(k+5)<<2);memset(t,0,(n+5)<<2);memset(f,0,(n+5)<<2);z=z2=0;for(int i=n;i;--i)ins(i);for(int i=1;i<=m;++i) cin>>a[i];for(int i=1,j=1;i<=m;i=++j){int x=a[i];if(int y=c[x]){if(s[y][t[y]-1]==x)del(y,i);else con(y,i);}else if(z2||z>1)ins(z2?e2[z2-1]:e[z-1],i);else for(j=i+1;;++j){if(x==a[j]){int y=e[0];ins(y,i);del(y,j);break;}if(int y=c[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 i=1;i<=m;++i){if(o[i]) printf("1 %d\n2 %d %d\n",o[i],p[i],o[i]);else printf("1 %d\n",p[i]);}}
}


http://www.ppmy.cn/embedded/133775.html

相关文章

【MySQL】 运维篇—备份与恢复:备份策略与方法

数据库是存储和管理关键数据的核心&#xff0c;随着数据量的不断增加和业务的不断发展&#xff0c;确保数据的安全性和可恢复性变得至关重要。数据库备份是一种保护措施&#xff0c;可以在数据丢失、损坏或系统故障时&#xff0c;快速恢复数据&#xff0c;确保业务的连续性和稳…

Linux初阶——线程(Part1)

一、线程概念 1、如何理解线程 说到线程&#xff0c;那么我们就要回到进程了。 1.1. 再谈进程 对一个进程来说&#xff0c;它在内存中是这样的&#xff1a; 图1.1-a 其中一个 task_struct 独享一个进程地址空间和一个页表。 而线程其实和进程差不多&#xff0c;是这样的&…

计算机网络 | 第二章 物理层 | 26王道考研自用笔记

物理层任务&#xff1a;实现相邻节点之间比特&#xff08;0或1&#xff09;的传输 2.1 通信基础基本概念 2.1.1 信源、信宿、信号、信道 在通信系统中&#xff0c;信源负责生成信息&#xff0c;信宿接收和解释信息。信号是传输信息的载体&#xff0c;经过信道从信源到达信宿。…

JS 读取KML文件并返回经纬度

项目场景: 提示:这里简述项目相关背景: 因为客户提供文件是KML 文件,需要获取KML文件中的数据。 声明一个异步函数 fetchKML,它接受一个参数 url,该参数代表要加载的KML文件的路径或URL。try {使用 try 语句块开始,捕获可能在执行过程中发生的错误。// 使用Fetch API加…

iPhone当U盘使用的方法 - iTunes共享文件夹无法复制到电脑怎么办 - 如何100%写入读出

效果图 从iPhone复制文件夹到windows电脑 步骤windows 打开iTunes通过USB连接iPhone和电脑手机允许授权iTunes中点击手机图标&#xff0c;进入到点击左边“文件共享”&#xff0c;在右边随便选择一个App&#xff08;随意...&#xff09;写入U盘&#xff1a;拖动电脑的文件&am…

warmup

首页只有一个笑脸&#xff0c;没有什么有效信息&#xff0c; 查看源代码发现,source.php。 访问source.php,显而易见&#xff0c;php代码审计。 <?phphighlight_file(__FILE__);class emmm{public static function checkFile(&$page){ //设立白名单&#xff0c;so…

大模型,多模态大模型面试【LoRA,分类,动静态数据类型,DDPM,ControlNet,IP-Adapter, Stable Diffusion】

大模型&#xff0c;多模态大模型面试【LoRA&#xff0c;分类&#xff0c;动静态数据类型&#xff0c;DDPM&#xff0c;ControlNet&#xff0c;IP-Adapter, Stable Diffusion】 问题一&#xff1a;LoRA是用在节省资源的场景下&#xff0c;那么LoRA具体是节省了内存带宽还是显存呢…

一小时速通JavaScript模块化,涵盖CommonJS与ES6模块化

学习源码可以看我的个人前端学习笔记 (github.com):qdxzw/frontlearningNotes 觉得有帮助的同学&#xff0c;可以点心心支持一下哈&#xff08;笔记是根据b站尚硅谷的前端讲师【张天禹老师】整理的&#xff0c;用于自己复盘&#xff0c;有需要学习的可以去b站学习原版视频&…