首页 > 其他分享 >11.15 解题报告

11.15 解题报告

时间：2022-11-16 07:23:08浏览次数：54  
标签：ch 报告 int MAX 11.15 long 解题 readchar buf

T1

考场用时：\(40\) min
期望得分：\(30\) pts
实际得分：\(30\) pts
这题以前做过。
首先显然的一点是小 Y 行走的路径是一棵树，这题可以分两部分来做，首先对于每一个节点按照节点编号对于每一个终点升序排序。
然后对于 \(m=n-1\) 的部分是一棵树，直接 dfs 一遍即可，对于 \(m=n\) 的部分是一棵基环树，直接 dfs 找出这个环，然后枚举环上不走的那条边即可，复杂度 \(O(n^2)\) 可以接受。

#include<bits/stdc++.h>
#define ll long long
//#define int long long
using namespace std;
const int MAX=5e3+10;
const int MOD=998244353;
inline char readchar() {
	static char buf[100000], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
#define readchar getchar
	int res = 0, f = 0;
	char ch = readchar();
	for(; !isdigit(ch); ch = readchar()) if(ch == '-') f = 1;
	for(; isdigit(ch); ch = readchar()) res = (res << 1) + (res << 3) + (ch ^ '0');
	return f ? -res : res;
}
inline void write(int x) {
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
vector<int> s[MAX];
int vis[MAX],fa[MAX],dfn[MAX],cnt,huan[MAX],tot,mn=1,res=1e9;
int cut1,cut2,ans[MAX],a[MAX],cnt2,n,m;
void dfs(int f,int k){
	a[++cnt2]=k;
	for(int v:s[k]){
		if(v==f||((k==cut1&&v==cut2)||k==cut2&&v==cut1)) continue;
		dfs(k,v);
	}
	return ;
}
void fid(int f,int k){
	dfn[k]=++cnt;fa[k]=f;
	for(int v:s[k]){
		if(v==f) continue;
		if(dfn[v]){
			if(dfn[v]<dfn[k]) continue;
			huan[++tot]=v;
			for(;k!=v;v=fa[v])
				huan[++tot]=fa[v];
//			for(int i=1;i<=tot;i++) cout<<huan[i]<<" ";
			return ;
		}
		fid(k,v);
	}
	return ;
}
bool check(){
	for(int i=1;i<=n;i++){
		if(a[i]<ans[i]) return true;
		if(a[i]>ans[i]) return false;
	}
	return false;
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++) ans[i]=n-i+1;
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		s[u].push_back(v);
		s[v].push_back(u);
	}
	for(int i=1;i<=n;i++) sort(s[i].begin(),s[i].end());
	if(m==n){
		fid(0,1);
		for(int i=1;i<tot;i++){
			cut1=huan[i];
			cut2=huan[i+1];
			dfs(0,1);
			if(check()) for(int j=1;j<=n;j++) ans[j]=a[j];
			cnt2=0;
		}
		cut1=huan[tot],cut2=huan[1];
		dfs(0,1);
		if(check())
		{
			for(int i=1;i<=n;i++) ans[i]=a[i];
			cnt2=0;
		}
	}
	else{
		dfs(0,1);
		for(int i=1;i<=n;i++) ans[i]=a[i];
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
	return 0;
}

T2

考场用时：\(2。5\) h
期望得分：\(20\) pts
实际得分：\(20\) pts
直接推式子，分两种情况讨论，树剖或倍增维护。

#include<bits/stdc++.h>
#define ll long long
#define lc(k) k<<1
#define rc(k) k<<1|1
#define orz cout<<"I AK IOI\n"
#define int long long
#define lb lower_bound
const int MAX=3e5+10;
const int MOD=998244353;
using namespace std;
inline char readchar(){
	static char buf[100000], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read(){
#define readchar getchar
	int res = 0, f = 0;
	char ch = readchar();
	for(; !isdigit(ch); ch = readchar()) if(ch == '-') f = 1;
	for(; isdigit(ch); ch = readchar()) res = (res << 1) + (res << 3) + (ch ^ '0');
	return f ? -res : res;
}
inline void write(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int n,q,cnt,head[MAX],siz[MAX],m;
int fa[MAX][20],dep[MAX],son[MAX],siz2[MAX],lg[MAX];
struct node{int u,v,net;}e[MAX<<1];
inline void add(int u,int v){
	e[++cnt]=(node){u,v,head[u]};
	head[u]=cnt;
	return ;
}
void dfs1(int f,int k){
	siz[k]=1;
	dep[k]=dep[f]+1;fa[k][0]=f;
	for(int i=1;(1ll<<i)<=dep[k];i++)
		fa[k][i]=fa[fa[k][i-1]][i-1];
	for(int i=head[k];i;i=e[i].net){
		int v=e[i].v;
		if(v==f) continue;
		dfs1(k,v);siz[k]+=siz[v];
		siz2[k]=(siz2[k]+siz[v]*siz[v])%MOD;
		if(siz[v]>siz[son[k]]) son[k]=v;
	}
	return ;
}
int tp[MAX];
void dfs2(int t,int k){
	tp[k]=t;
	if(son[k]) dfs2(t,son[k]);
	for(int i=head[k];i;i=e[i].net){
		int v=e[i].v;
		if(v==fa[k][0]||v==son[k]) continue;
		dfs2(v,v);
	}
	return ;
}
int lca(int u,int v){
	while(tp[u]!=tp[v]){
		if(dep[tp[u]]<dep[tp[v]]) swap(u,v);
		u=fa[tp[u]][0];
	}
	return dep[u]<dep[v]?u:v;
}
int query(int u,int v){
	for(int i=lg[dep[v]];i>=0;i--){
		if(dep[fa[v][i]]<=dep[u]) continue;
		v=fa[v][i];
	}
	return v;
}
signed main(){
//	return system("fc 1.out path3.ans"),0;
//	freopen("path4.in","r",stdin);
//	freopen("1.out","w",stdout);
//	freopen("path.in","r",stdin);
//	freopen("path.out","w",stdout);
	n=read(),m=read();
	lg[0]=-1;
	for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		add(u,v);add(v,u);
	}
	dfs1(0,1);dfs2(1,1);
	while(m--){
		int u=read(),v=read();
		int lca_=lca(u,v),ansl=0,ansr=0;
		if(lca_==u){
			int x=query(u,v);
//			cout<<x<<" "<<siz2[u]-siz2[x]<<endl;
			int x1=n-siz[x];
			ansl=(x1*(x1-1)%MOD-(siz2[u]-siz[x]*siz[x])-(n-siz[u])*(n-siz[u])%MOD+x1+3*MOD)%MOD;
		}
		else ansl=(siz[u]*(siz[u]-1)%MOD-siz2[u]+siz[u]+MOD)%MOD;
		if(lca_==v){
			int x=query(v,u);
			int x1=n-siz[x];
			ansr=(x1*(x1-1)%MOD-(siz2[v]-siz[x]*siz[x])-(n-siz[v])*(n-siz[v])%MOD+x1+3*MOD)%MOD;
		}
		else ansr=(siz[v]*(siz[v]-1)%MOD-siz2[v]+siz[v]+MOD)%MOD;
		write(ansl*ansr*4%MOD);
		putchar('\n');
	}
	return 0;
}
/*
7 1
1 2
1 3
1 4
4 5
2 6
2 7
1 7
*/

T3

考场用时：\(1.5\) h
期望得分：\(44\) pts
实际得分：\(44\) pts
直接暴力 dp，\(dp[i][0/1]\) 表示满足/不满足第 \(i\) 个国王的要求时的最小开销，那么 \(dp[i][0]=\sum dp[son[i]][1]\)，\(dp[i][1]=c[i]+\sum \min(dp[son[i]][0],dp[son[i]][1])\)。

#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int MAX=1e5+10;
const int MOD=998244353;
inline char readchar() {
	static char buf[100000], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
#define readchar getchar
	int res = 0, f = 0;
	char ch = readchar();
	for(; !isdigit(ch); ch = readchar()) if(ch == '-') f = 1;
	for(; isdigit(ch); ch = readchar()) res = (res << 1) + (res << 3) + (ch ^ '0');
	return f ? -res : res;
}
inline void write(int x) {
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int cnt,val[MAX],dp[MAX][2],head[MAX];
struct node{int u,v,next;}edge[MAX<<1];
void add(int u,int v){
	edge[++cnt]=(node){u,v,head[u]};
    head[u]=cnt;
    return ; 
}
int n,m;string s; 
void dfs(int now,int fa){
    dp[now][1]+=val[now];
    for(int i=head[now];i;i=edge[i].next){
        int v=edge[i].v;
        if(v==fa)  continue;
        dfs(v,now);
        dp[now][0]+=dp[v][1];
        dp[now][1]+=min(dp[v][0],dp[v][1]);
    }
}
signed main(){
    n=read(),m=read();
    cin>>s;
    for(int i=1;i<=n;++i) val[i]=read();
    for(int i=1;i<n;++i){
        int u=read(),v=read();
        add(u,v),add(v,u);
    }
    while(m--){
        memset(dp,0,sizeof(dp));
        int a=read(),x=read(),b=read(),y=read();
        if(x==1)  dp[a][0]=1e18;
        else dp[a][1]=1e18;
        if(y==1)  dp[b][0]=1e18;
        else dp[b][1]=1e18;
        dfs(1,0);
        if(min(dp[1][0],dp[1][1])>=1e18)  puts("-1");
        else cout<<min(dp[1][1],dp[1][0])<<endl;
    }
    return 0;
}

标签：ch,报告,int,MAX,11.15,long,解题,readchar,buf
From： https://www.cnblogs.com/wapmhac/p/16894665.html

相关文章

  • Vulnhub Chili靶机详细解题过程
    Chili识别目标主机IP地址本靶机存在无法从Virtualbox自动获得IP地址的问题，根据本人另文来解决该问题。──(kali㉿kali)-[~/Vulnhub/Chili]└─$sudonetdiscover-i......
  • CF刷题计划？（upd:11.15）
    CF刷题计划？CF1285F太nb了这个题暴力一点的做法是二分后直接莫反，但是不够快考虑枚举一个\(\gcd\)，令其为\(d\)然后从大到小枚举数，然后把\(\gcd(\frac{x}{d},\frac{y}{d}......
  • 【2022.11.15】luffy项目部署（9）
    内容概要1redis字符串操作2redishash操作3redis列表操作4redis管道5redis其他操作6django中集成redis7celery介绍内容详细#装了图形化客户......
  • Vulnhub Cherry靶机解题详细过程
    Cherry识别目标主机IP地址靶机存在无法从Virtualbox自动获取IP地址的问题，先参照本人另文解决该问题。┌──(kali㉿kali)-[~/Vulnhub/Cherry]└─$sudonetdiscover-......
  • 闲话 22.11.15
    闲话幸亏昨天写了两道题要不然今天没题可写了（明天学考？话说怎么那么多bitmask题啊杂题CF487ECyberland有\(n\)座城市，编号从\(1\)到\(n\)，有\(m\)条双向道......
  • 报告分享|2022年直播行业研究最新动态
    报告全文链接：http://tecdat.cn/?p=30326中国直播电商起源于2016年，之后大致经历2017-2018年的快速拓展期、2019-2020年的百花齐放期以及2021至今的全民直播三大阶段。中国......
  • 11.15
    今日内容1.软件开发架构2.网络编程简介3.OSI七层协议简介4.物理连接层5.数据链路层6.网络层7.传输层8.网络相关专业名词1.软件开发架构1.C/S架构Client:客户端......
  • Vulnhub Bluemoon靶机解题详细过程
    Bluemoon识别目标主机IP地址┌──(kali㉿kali)-[~/Vulnhub/Bluemoon]└─$sudonetdiscover-iethCurrentlyscanning:192.168.92.0/16|ScreenView:Unique......
  • Word03 政府工作年度报告-office真题
    1.课程的讲解之前，先来对题目进行分析，首先需要在考生文件夹下，将Wrod素材.docx文件另存为Word.docx，后续操作均基于此文件，否则不得分。  2.这一步非常的简单，打开下载素材......
  • 11.14 解题报告
    T1考场用时：\(1\)h期望得分：\(70\)pts实际得分：\(20\)pts有一个地方的\(m\)写成了\(n\)，直接T飞。对于\(70\)分的做法，考虑设\(dp_{i,j}\)表示分了\(i\)段，现......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99