10.5NOIP模拟赛

xiaoxiao2021-02-28  53

今天的文件夹10.5终于和去年的重名了。时间飞逝,做一个OIer的时间已经不止一年了,于是今天搞个可笑又可悲的大新闻纪念一下——爆零。。。好好总结吧TAT。。。 题解: 无向图求割点,如果土地块数小于3则输出-1,如果存在割点输出1,否则输出2。 解释:定义一个点(土地)的入度为与它边相邻土地的块数。如果不存在割点,那么在这个连通块的四个角上一定存在一个入度为2的点。假设在右上角有一个这样的点,那么把它的左边点与右边点割掉即可,所以输出2。

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> using namespace std; const int MAXN=90000+5; int n,m,land; int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; char s[305][305]; int head[MAXN],edge,tim=0; struct EDGE { int v,nxt; }e[MAXN<<2]; int low[MAXN],dfn[MAXN],f[MAXN],cut=0; bool iscut[MAXN]; inline int id(int i,int j) { return (i-1)*m+j; } inline void adde(int u,int v) { e[++edge].nxt=head[u],e[edge].v=v,head[u]=edge; } void dfs(int p,int fa) { low[p]=dfn[p]=++tim; int ch=0; for (int i=head[p];~i;i=e[i].nxt) { int v=e[i].v; if (!dfn[v]) { ++ch; dfs(v,p); low[p]=min(low[p],low[v]); if (low[v]>=dfn[p]) iscut[p]=true,++cut; } else if (dfn[v]<dfn[p]&&v!=fa) low[p]=min(low[p],dfn[v]); } if (fa<0&&ch==1) iscut[p]=false,--cut; } int main() { freopen("board.in","r",stdin); freopen("board.out","w",stdout); int kase; scanf("%d",&kase); while (kase--) { memset(head,-1,sizeof(head)); memset(dfn,0,sizeof(dfn)); memset(iscut,0,sizeof(iscut)); edge=tim=land=0; cut=0; scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) scanf("%s",s[i]+1); for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) if (s[i][j]=='#') { ++land; for (int k=0;k<4;++k) { int tx=i+dx[k],ty=j+dy[k]; if (s[tx][ty]=='#'&&tx>0&&tx<=n&&ty>0&&ty<=m) adde(id(i,j),id(i+dx[k],j+dy[k])); } } if (land<3) {puts("-1");continue;} dfs(e[1].v,-1); puts(cut?"1":"2"); } return 0; }

题解: 结论是:如果B=1,10,100,1000并且A != 2B,那么答案是2,否则是1。二倍关系答案为1的解释略(显然),下面解释1,10,100,1000的特殊性质: 举个例子,如果B= 10,A = 50,那么买了1之后,需要找零49,这个9肯定是由1,2,5凑出来的(能拼出49,一定能拼出9,然后剩下的部分即使有1,2,5,他们也一定能拼出10),减掉他们之后相当于用10,20,去凑40,就回到了普通的情况。 有点晕,所以还是我来概括一句:在B=10的情况,一定可以用大于10和小于10的玉石找零,所以要用找回来的玉石再操作一次。

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int main() { freopen("change.in","r",stdin); freopen("change.out","w",stdout); int kase,A,B; scanf("%d",&kase); while (kase--) { scanf("%d%d",&A,&B); if ((B<<1)==A) puts("1"); else { if (B==1) puts("2"); else if (B==10) puts("2"); else if (B==100) puts("2"); else if (B==1000) puts("2"); else puts("1"); } } return 0; }

题解: 世界级的贪心,如果这条路径上要放经济城,那么放在LCA上一定更优(更有可能帮更其它深度变化幅度大的路径节省经济城)。所以将所有路径按其LCA的深度从深到浅排序,然后每次查询路径端点标记是否为1,如果没有的话,++ans,然后将LCA的子树标记赋成1。 思维水平不够啊,考场上暴力都没想清楚,下来看完题解二十分钟1A。。。

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define root 1,1,n #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r const int MAXN=1e5+4; int n,m; int head[MAXN],f[18][MAXN],in[MAXN],out[MAXN],dep[MAXN],tim,edge; struct EDGE { int v,nxt; }e[MAXN<<1]; struct Q { int u,v,top; friend bool operator <(const Q &a,const Q &b) { return dep[a.top]>dep[b.top]; } }q[MAXN]; int sum[MAXN<<2],lazy[MAXN<<2]; inline void pushup(int rt) { sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } inline void pushdown(int rt,int len) { if (~lazy[rt]) { lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt]; sum[rt<<1]=lazy[rt]*(len-(len>>1)); sum[rt<<1|1]=lazy[rt]*(len>>1); lazy[rt]=-1; } } void build(int rt,int l,int r) { lazy[rt]=-1; if (l==r) {sum[rt]=0;return ;} int mid=(l+r)>>1; build(lson); build(rson); pushup(rt); } void modify(int rt,int l,int r,int L,int R) { if (L<=l&&r<=R) { sum[rt]=r-l+1; lazy[rt]=1; return ; } pushdown(rt,r-l+1); int mid=(l+r)>>1; if (L<=mid) modify(lson,L,R); if (mid<R) modify(rson,L,R); pushup(rt); } int query(int rt,int l,int r,int L,int R) { if (L<=l&&r<=R) return sum[rt]; pushdown(rt,r-l+1); int mid=(l+r)>>1,ret=0; if (L<=mid) ret+=query(lson,L,R); if (mid<R) ret+=query(rson,L,R); return ret; } inline void adde(int u,int v) { e[edge].nxt=head[u],e[edge].v=v,head[u]=edge++; e[edge].nxt=head[v],e[edge].v=u,head[v]=edge++; } void dfs(int p,int father) { in[p]=++tim; for (int i=head[p];~i;i=e[i].nxt) { int v=e[i].v; if (v^father) { f[0][v]=p; dep[v]=dep[p]+1; dfs(v,p); } } out[p]=tim; } inline void da() { for (int j=1;(1<<j)<=n;++j) for (int i=1;i<=n;++i) f[j][i]=f[j-1][f[j-1][i]]; } inline int lca(int x,int y) { if (dep[x]<dep[y]) swap(x,y); int t=dep[x]-dep[y]; for (int i=0;i<=17;++i) if (t&(1<<i)) x=f[i][x]; if (x==y) return x; for (int i=17;i>=0;--i) if (f[i][x]^f[i][y]) x=f[i][x],y=f[i][y]; return f[0][x]; } inline int read() { int x=0;char c=getchar(); while (c<'0'||c>'9') c=getchar(); while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x; } int main() { freopen("fill.in","r",stdin); freopen("fill.out","w",stdout); int kase=read(); while (kase--) { memset(head,-1,sizeof(head)); edge=0,tim=0; n=read(),m=read(); for (register int i=1;i<n;++i) { int u=read(),v=read(); adde(u,v); } dfs(1,0); da(); build(root); for (register int i=1;i<=m;++i) q[i].u=read(),q[i].v=read(),q[i].top=lca(q[i].u,q[i].v); sort(q+1,q+m+1); int ans=0; for (int i=1;i<=m;++i) { int u=q[i].u,v=q[i].v,top=q[i].top; int t1=query(root,in[u],in[u]); int t2=query(root,in[v],in[v]); if (!t1&&!t2) ++ans,modify(root,in[top],out[top]); } printf("%d\n",ans); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-850417.html

最新回复(0)