首页 > 其他分享 >6月6日模拟赛题解

6月6日模拟赛题解

时间：2024-06-06 20:22:10浏览次数：16  
标签：std ch int 题解 read && 模拟 getchar

P4315 月下“毛景树”

没代码能力，写不动，赛时没写。
注意 pushdown 即可。

#include<bits/stdc++.h>
inline int read(){
	char ch=getchar();int x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
const int N=1e5+10;
int n,head[N],tot,dfn[N],top[N],dep[N],son[N],siz[N],fa[N],w[N],rnk[N];
std::pair<int,int> tr[N];
struct E{int v,next,w;}e[N<<1];
inline void add(int u,int v,int w){e[++tot]={v,head[u],w},head[u]=tot;}
inline void dfs1(int x){
	siz[x]=1;
	int y;
	for(int i=head[x];i;i=e[i].next){
		if(!dep[y=e[i].v]){
			w[y]=e[i].w;
			dep[y]=dep[x]+1;fa[y]=x;dfs1(y);siz[x]+=siz[y];
			if(!son[x]||siz[y]>siz[son[x]])son[x]=y;
		}
	}
}
inline void dfs2(int x,int t){
	top[x]=t;dfn[x]=++tot;rnk[tot]=x;
	if(!son[x])return;
	dfs2(son[x],t);
	int y;
	for(int i=head[x];i;i=e[i].next){
		y=e[i].v;
		if(y!=fa[x]&&y!=son[x])dfs2(y,y);
	}
}
struct Tree{int push,modi,max;}t[N<<2];
inline void pushdown(int p){
	if(t[p].push>=0){
		t[p<<1].modi=t[p<<1|1].modi=0;
		t[p<<1].max=t[p<<1|1].max=t[p<<1].push=t[p<<1|1].push=t[p].push;
	}
	if(t[p].modi){
		t[p<<1].modi+=t[p].modi,t[p<<1|1].modi+=t[p].modi;
		t[p<<1].max+=t[p].modi,t[p<<1|1].max+=t[p].modi;
	}
	t[p].push=-1,t[p].modi=0;
}
inline void update(int p){
	t[p].max=std::max(t[p<<1].max,t[p<<1|1].max);	
}
inline void build(int p,int l,int r){
	t[p].push=-1;
	if(l==r){t[p].max=w[rnk[l]];t[p].push=-1;return;}
	int mid=l+r>>1;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r);
	update(p);
}
inline int ask(int p,int l,int r,int x,int y){
	int res=-2e9;
	if(l>=x&&r<=y){return t[p].max;}
	pushdown(p);
	int mid=l+r>>1;
	if(x<=mid)res=std::max(res,ask(p<<1,l,mid,x,y));
	if(y>mid)res=std::max(res,ask(p<<1|1,mid+1,r,x,y));
	return res;
}
inline int query(int u,int v){
	int res=-2e9;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])std::swap(u,v);
		res=std::max(res,ask(1,1,n,dfn[top[u]],dfn[u]));
		u=fa[top[u]];
	}
	if(u==v)return res;
	if(dep[u]>dep[v])std::swap(u,v);
	res=std::max(res,ask(1,1,n,dfn[son[u]],dfn[v]));
	return res;
}
inline void change1(int p,int l,int r,int x,int y,int c){
	if(l>=x&&r<=y){t[p].modi+=c;t[p].max+=c;return;}
	pushdown(p);
	int mid=l+r>>1;
	if(x<=mid)change1(p<<1,l,mid,x,y,c);
	if(y>mid)change1(p<<1|1,mid+1,r,x,y,c);
	update(p);
}
inline void change2(int p,int l,int r,int x,int y,int c){
	if(l>=x&&r<=y){t[p].modi=0;t[p].push=c;t[p].max=c;return;}
	pushdown(p);
	int mid=l+r>>1;
	if(x<=mid)change2(p<<1,l,mid,x,y,c);
	if(y>mid)change2(p<<1|1,mid+1,r,x,y,c);
	update(p);
}
inline void modify(int u,int v,int c,int flag){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])std::swap(u,v);
		if(flag)change1(1,1,n,dfn[top[u]],dfn[u],c);
		else change2(1,1,n,dfn[top[u]],dfn[u],c);
		u=fa[top[u]];
	}
	if(u==v)return;
	if(dep[u]>dep[v])std::swap(u,v);
	if(flag)change1(1,1,n,dfn[son[u]],dfn[v],c);
	else change2(1,1,n,dfn[son[u]],dfn[v],c);
}
int main(){
	// freopen("in.in","r",stdin),freopen("out.out","w",stdout);
	std::ios::sync_with_stdio(false);std::cin.tie(0),std::cout.tie(0);
	std::cin>>n;
	dep[1]=1;
	for(int i=1;i<n;++i){
		int u,v,w;std::cin>>u>>v>>w;
		tr[i]={u,v};
		add(u,v,w);add(v,u,w);
	}
	dfs1(1);tot=0;
	dfs2(1,1);
	build(1,1,n);
	while(1){
		std::string s;
		std::cin>>s;
		if(s=="Max"){
			int u,v;std::cin>>u>>v;
			std::cout<<query(u,v)<<"\n";
		}
		if(s=="Change"){
			int k,c;std::cin>>k>>c;
			modify(tr[k].first,tr[k].second,c,0);
		}
		if(s=="Cover"){
			int u,v,c;std::cin>>u>>v>>c;
			modify(u,v,c,0);
		}
		if(s=="Add"){
			int u,v,c;std::cin>>u>>v>>c;
			modify(u,v,c,1);
		}
		if(s=="Stop"){
			exit(0);
		}
	}
}

上课安排

考虑数学归纳法。

  • \(n=5\) 时，可以找出 \(\{1\},\{2,3\},\{3,4,5\}\)，对于 \(n=7\) 时，可以在每个集合后加一个 \(7\)，然后将 \(6\) 作为一个单独的集合，再加上一个 \(\{1,2,3,4,5\}\) 这样的集合。对于所有奇数，以此类推。
  • \(n=4\) 时，可以找出 \(\{1\},\{2,3\}\)，对于 \(n=6\) 时，可以在每个集合后加一个 \(7\)，然后将 \(5\) 作为一个单独的集合，再加上 \(\{1,2,3,4\}\) 这样的集合。对于所有偶数，以此类推。
    代码是打表找的规律（赛时快读锅了）。
#include<bits/stdc++.h>
inline int read(){
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<'9';ch=getchar())x=x*10+ch-'0';
    return x*f;
}
const int N=1e3+10;
int main(){
    freopen("course.in","r",stdin);freopen("course.out","w",stdout);
	int n;
	std::cin>>n;
    int ans=n-2;
    std::cout<<ans<<'\n';
    if(n&1){
        for(int i=1;i<=ans;++i){
            std::cout<<i<<' ';
            if(i<=n/2){
                int zc=n-(i*2-1);
                std::cout<<zc<<' ';
                zc+=3;
                for(int j=1;j<=i-1;++j,zc+=2)std::cout<<zc<<' ';std::cout<<'\n';
            }
            else{
                int zc=i-n/2+1;zc=zc*2-1;
                for(int j=1;j<=zc;++j)std::cout<<j<<' ';
                int w=zc+4;
                for(;w<=n;w+=2)std::cout<<w<<' ';std::cout<<'\n';
            }
        }
    }else{
        for(int i=1;i<=ans;++i){
            std::cout<<i<<' ';
            if(i<=n/2){
                int zc=n-(i*2-1);
                std::cout<<zc<<' ';
                zc+=3;
                for(int j=1;j<=i-1;++j,zc+=2)std::cout<<zc<<' ';std::cout<<'\n';
            }
            else{
                int zc=i-n/2+1;zc=zc*2;
                for(int j=1;j<=zc;++j)std::cout<<j<<' ';
                int w=zc+4;
                for(;w<=n;w+=2)std::cout<<w<<' ';std::cout<<'\n';
            }
        }
    }
}

P3360 偷天换日

递归输入建图，然后对于叶子做背包，向父亲直接枚举转移即可（赛时快读锅了）。

#include<bits/stdc++.h>
#define int long long
inline int read(){
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    return x*f;
}
const int N=705;
int f[N][N],tot,head[N],max,cnt=1,a[N],v[N],b[305][40][N],lson[N],rson[N],wlson[N],wrson[N];
struct E{int v,next,w;}e[N];
inline void add(int u,int v,int w){w*=2;e[++tot]={v,head[u],w};head[u]=tot;}
inline void bp(int x,int t){
	int zc=0;
    for(int i=1;i<=t;++i){
        a[i]=read(),v[i]=read();
        zc+=v[i];
    }
    b[x][1][v[1]]=a[1];
    for(int i=2;i<=t;++i){
        for(int j=0;j<=zc;++j){
            b[x][i][j]=b[x][i-1][j];
            if(j>=v[i]){
                b[x][i][j]=std::max(b[x][i][j],b[x][i-1][j-v[i]]+a[i]);
            }
        }
    }
    for(int i=0;i<=zc;++i)f[x][i]=b[x][t][i];
}
inline void init(int x){
    int w=read();
    add(x,++cnt,w);
    int zc=cnt;
    int t=read();
    if(!t){
        init(zc);
        init(zc);
    }else{
        bp(zc,t);
    }
}
inline void dfs(int x){
    if(lson[x]){
    	dfs(lson[x]);
    	 for(int i=0;i+wlson[x]<=max;++i){
            f[x][i+wlson[x]]=f[lson[x]][i];
         }
	}
    if(rson[x]){
        dfs(rson[x]);
         for(int i=max;i>=0;--i){
             for(int k=1;k<=i;++k){
             	if(i+wrson[x]>max)continue;
                 f[x][i+wrson[x]]=std::max(f[x][i+wrson[x]],f[x][i-k]+f[rson[x]][k]);
             }
         }
    }
}
signed main(){
    // freopen("in.in","r",stdin);freopen("out.out","w",stdout);
    max=read()-1;init(1);
    for(int i=1;i<=cnt;++i){
    	int j=head[i];
    	if(!j){continue;}
    	lson[i]=e[j].v;wlson[i]=e[j].w;
        j=e[j].next;
    	if(j)rson[i]=e[j].v,wrson[i]=e[j].w;
	}
    dfs(1);
    int ans=0;
    for(int i=max;i>=0;--i){
        if(f[1][i]){
            ans=std::max(f[1][i],ans);
        }
    }
    std::cout<<ans<<'\n';
}

P2894 [USACO08FEB] Hotel G

发的题解是线段树合并，但我感觉没那意思。
跟山海经（小白逛公园）有些相似，考虑维护区间最长 \(0\) 的连续段，修改直接做，对于查询如果当前节点不满足则不合法，满足则查找左儿子，如果左儿子的值满足直接进去找，否则就是当前节点的答案。
赛时没代码能力，没写动，写了个有些唐氏的暴力（比较难卡）。等会补正解。

#include <bits/stdc++.h>
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();

    for (; ch < '0' || ch > '9'; ch = getchar())
        if (ch == '-')
            f = -1;

    for (; ch >= '0' && ch <= '9'; ch = getchar())
        x = x * 10 + ch - '0';

    return x * f;
}
const int N = 5e4 + 10;
int n, m, a[N];
inline void write(int x) {
    if (x >= 10) {
        write(x / 10);
    }

    putchar(x % 10 + '0');
}
signed main() {
    freopen("hotel.in", "r", stdin);
    freopen("hotel.out", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    n = read(), m = read();

    for (int i = 1; i <= m; ++i) {
        int op = read();

        if (op == 1) {
            int l = read();
            bool flag = 0;

            for (int j = 1; j + l - 1 <= n; ++j) {
                if (a[j] || a[j + l - 1])
                    continue;

                int zc = 0;

                for (int k = j; k <= j + l - 1; ++k) {
                    if (a[k]) {
                        j = k;
                        break;
                    } else
                        zc++;
                }

                if (zc == l) {
                    write(j);
                    putchar('\n');
                    flag = 1;

                    for (int k = j; k <= j + l - 1; ++k)
                        a[k] = 1;

                    break;
                }
            }

            if (!flag)
                write(0), putchar('\n');
        } else {
            int l = read(), r = read();
            r = l + r - 1;

            for (int j = l; j <= r; ++j)
                a[j] = 0;
        }
    }
}

P4303 [AHOI2006] 基因匹配

赛时没咋看，感觉比前面四道加起来有深意。
根据性质，每个数出现 \(5\) 次，所以只会在这 \(5\) 个位置匹配成功。
具体来说，记一下 \(a\) 串的每个数出现的位置，设 \(f_i\) 表示匹配到 \(a\) 串的第 \(i\) 个位置时的最长 LCS 长度，然后遍历 \(b\) 串，查找 \(b_i\) 在 \(a\) 串中的位置 \(x\)，有 \(f_x=\max(f_k+1)(k\le x-1)\)，（注意倒序）上数据结构维护即可。

#include<bits/stdc++.h>
inline int read(){
	char ch=getchar();int x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
const int N=1e5+10;
int n,f[N];
std::vector<int> v_a[N],v_b[N];
struct Tree{int ans;}t[N<<2];
inline void change(int p,int l,int r,int pos,int x){
	if(l==r){t[p].ans=x;return;}
	int mid=l+r>>1;
	if(pos<=mid)change(p*2,l,mid,pos,x);
	else change(p*2+1,mid+1,r,pos,x);
	t[p].ans=std::max(t[p*2].ans,t[p*2+1].ans);
}
inline int query(int p,int l,int r,int x,int y){
	if(x>y)return 0;
	if(l>=x&&r<=y)return t[p].ans;
	int mid=l+r>>1,res=0;
	if(x<=mid)res=std::max(res,query(p*2,l,mid,x,y));
	if(y>mid)res=std::max(res,query(p*2+1,mid+1,r,x,y));
	return res;
}
int main(){
// 	freopen("match.in","r",stdin),freopen("match.out","w",stdout);
	std::ios::sync_with_stdio(false);std::cin.tie(0),std::cout.tie(0);
	n=read();
	for(int i=1;i<=n*5;++i){
		int x=read();v_a[x].push_back(i);
	}
	for(int i=1;i<=n;++i)std::reverse(v_a[i].begin(),v_a[i].end());
	n*=5;
	int ans=0;
	for(int i=1;i<=n;++i){
		int x=read();
		for(int y:v_a[x]){
			f[y]=std::max(f[y],query(1,1,n,1,y-1)+1);
			change(1,1,n,y,f[y]);
			ans=std::max(ans,f[y]);
		}
	}
	std::cout<<ans<<'\n';
}

标签：std,ch,int,题解,read,&&,模拟,getchar
From： https://www.cnblogs.com/Ishar-zdl/p/18235961

相关文章

  • 各家AI大胆帮我预测一下2024年全国高考语文作文 并模拟出题 坐看AI算的准不准
    chatgpt-4o抱歉，我无法预测具体的高考题目。不过，我可以根据近年的趋势和主题为你模拟一个可能的作文题目：2024年全国高考语文作文模拟题目：题目：《共同的家园》要求：以“共同的家园”为主题，写一篇文章。可以采用记叙、议论、描写等文体，自选角度。不少于800字。背景提示：在......
  • 利用西门子DQ模块控制移位寄存器，模拟串行通信
    1.背景以前了解过串行通信的方法但是没有详细了解过具体实现。趁着手上有的一堆破铜烂铁尝试自己去实现一个最简单的串行控制。目的是通过移位寄存器的不同位的表达，达到2*2=4个的继电器管断组合，达到切换矩阵的目的。这里只记录一下程序实现，不记录硬件电路。2.材料移位寄......
  • arc179d 题解
    arc179d思路设计树形dp。\(dp_{u,0}\)表示进子树\(u\)并不再出去的代价。\(dp_{u,1}\)表示进子树\(u\)并返回，且传送门在\(fa\)、不在子树内使用传送门的代价。\(dp_{u,2}\)表示进入子树\(u\)并返回，且可以在子树内使用传送门。发现\(dp_{u,1}\)一定是遍历子树最后......
  • abc355f 题解
    abc355f直接贺lct维护mst的代码。思路观察到\(w_i\le10\)，考虑分开建\(10\)个图表示边权小于等于\(i\)的边组成的图。连并查集，记录当前图连了\(siz_i\)条边。可以发现第\(i-1\)个图是第\(i\)个图的子图。所以差分\(siz_i-siz_{i-1}\)可以得到原图的最小生成......
  • CF1575E 题解
    CF1575E思路点分治，记录当前子树到分治中心的权值和和换车次数。将新子树的答案合并时分类讨论分治中心到子树祖先\(u\tov\)的颜色。树状数组维护前缀和。复杂度\(O(n\log^2n)\)。codeintn,k,a[maxn],ans;inthead[maxn],tot;structnd{ intnxt,to,fl;}e[maxn<<1];......
  • abc355e 题解
    abc355e思路WC2024T3中知道一个技巧：如果知道区间\([l,r]\)的和就连边\(l\tor+1\)，那么想推出\([L,R]\)的区间和就要求\(L\)和\(R+1\)联通。按题意把符合要求的边连上，设边权为\(1\)跑bfs，求出\(L\)到\(R+1\)的最短路并记录路径上的点，就可以得到要询问的区间。......
  • CF1007B 题解
    CF1007B思路显然题目要求计数\(u\midA,v\midB,w\midC\)。\(O(n\sqrtn)\)预处理出每个数的所有因数，记为集合\(p_i\)。容斥，记集合\(a,b,c,ab,ac,bc,all\)为\(p_A,p_B,p_C,p_A\capp_B,p_A\capp_A,p_B\capp_C,p_A\capp_B\capp_C\)。可以用bitset维护交集。首先加......
  • 【面试宝藏】MySQL 面试题解析
    MySQL面试题解析1.数据库三大范式是什么？第一范式（1NF）：确保每列的原子性，即每列不能再分。第二范式（2NF）：在满足1NF的基础上，每个非主属性完全依赖于主键，即消除部分依赖。第三范式（3NF）：在满足2NF的基础上，任何非主属性不依赖于其他非主属性，即消除传递依赖。2.MySQL有关权限......
  • 【面试宝藏】Redis 常见面试题解析其二
    Redis高级面试题解析20.说说Redis哈希槽的机制？Redis集群采用哈希槽（HashSlot）机制来分布和管理数据。整个哈希空间被划分为16384个槽，每个键通过CRC16校验后取模映射到一个哈希槽。每个节点负责一部分哈希槽，从而实现数据分片和负载均衡。21.Redis集群的主从复制......
  • 校内模拟赛总结，又名挂分日记
    倒序排序20240601A容易发现是矩阵快速幂B把每一段编个号，找到号码出现的顺序，还要考虑段内的顺序C用类似线段树的东西维护，将pushup改成\(O(n)\)的即可，没做出来D不会20240502今天又犯傻逼错误A简单背包，背包的大小开小了，100->10B数位DP，答案与输入并不在同一数量级，但......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99