Codeforces Round 1338 简要题解_mayaohua2003的博客-程序员秘密

技术标签: 图论  codeforces  动态规划  

A. Powered Addition

B. Edge Weight Assignment

C. Perfect Triples

找找规律容易发现答案跟四进制相关。
考虑将数字写成四进制,容易观察并归纳证明:所有匹配的 ( a , b , c ) (a,b,c) (a,b,c)位数都相同,并且位数相同,最高位为 1 1 1 2 2 2 3 3 3的数字分别会作为 a a a b b b c c c出现,互相匹配,且 a a a从小到大取遍所有最高位为 1 1 1的数,而后面每一位匹配关系是独立的,具体的,匹配关系是 ( 0 , 0 , 0 ) (0,0,0) (0,0,0) ( 1 , 2 , 3 ) (1,2,3) (1,2,3) ( 2 , 3 , 1 ) (2,3,1) (2,3,1) ( 3 , 1 , 2 ) (3,1,2) (3,1,2)。那么将 n n n写成四进制即可反过来得到 s n s_n sn了。
时间复杂度 O ( t log ⁡ n ) \mathcal O(t\log n) O(tlogn)

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int A[4]={
    0,1,2,3};
const int B[4]={
    0,2,3,1};
const int C[4]={
    0,3,1,2};

int main() {
    
  int cases;
  scanf("%d",&cases);
  for(;cases;cases--) {
    
  	ll n;
  	scanf("%lld",&n);
  	if (n<=3) {
    
  		printf("%lld\n",n);
  		continue;
	  }
	n-=4;
	int v=n%3;
	n/=3;
	ll d=1;
	int cnt=0;
	for(;;) {
    
		d*=4;
		cnt++; 
		if (d>n) break;
		n-=d;
	}
	int val[60],sz=0;
	memset(val,0,sizeof(val));
	while (n) {
    
		val[++sz]=n%4;
		n/=4;
	}
	ll s=0;
	if (!v) {
    
		s+=1;
		for(int i=cnt;i>0;i--) s=s*4LL+A[val[i]];
	}
	if (v==1) {
    
		s+=2;
		for(int i=cnt;i>0;i--) s=s*4LL+B[val[i]]; 
	}
	if (v==2) {
    
		s+=3;
		for(int i=cnt;i>0;i--) s=s*4LL+C[val[i]]; 
	}
	printf("%lld\n",s);
  }
  return 0;
}
/*
3
7
8
9 
*/ 

D. Nested Rubber Bands

考虑钦定一个点集 S S S,如何判定 S S S能否作为一个链出现。
首先注意到 S S S中不可能包含相邻的点。显然只用考虑 S S S中点构成的虚树上的点,对于虚树上某个非叶子节点 x x x,如果 x x x出现在 S S S中,那么容易证明合法必须满足以 x x x为根的话,至多两个子树中有 S S S中的点;如果 x x x没有出现在 S S S中,那么必须满足以 x x x为根的话,至多两个子树包含 S S S中的点且不是子树中仅有与 x x x相邻的点在 S S S中。
这样令 F [ i ] [ 0 / 1 ] [ 0 / 1 / 2 ] F[i][0/1][0/1/2] F[i][0/1][0/1/2]表示考虑点 i i i子树,点 i i i是否选择, i i i儿子子树中有几个包含 S S S中的点且不是子树中仅有与 i i i相邻的点在 S S S中,简单树形DP一下即可。
时间复杂度 O ( n ) \mathcal O(n) O(n)

#include <bits/stdc++.h>

using namespace std;

vector <int> e[100005];
int f[100005][2][3],ans;

void dfs(int x,int fa) {
    
  static int g[2][3];
  f[x][0][0]=0;
  f[x][1][0]=1;
  for(int i=0;i<e[x].size();i++)
    if (e[x][i]!=fa) {
    
    	int u=e[x][i];
    	dfs(u,x);
    	memcpy(g,f[x],sizeof(g));
        for(int j=0;j<3;j++) {
    
          if (f[x][0][j]!=-1) {
    
          	g[0][j]=max(g[0][j],f[x][0][j]+1);
          	for(int k=0;k<2&&j+1<3;k++) {
    
          		int t=max(f[u][0][k],f[u][1][k]);
          		if (t!=-1) g[0][j+1]=max(g[0][j+1],f[x][0][j]+t);
            }
		  }
		  if (f[x][1][j]!=-1) {
    
          	for(int k=0;k<2&&j+1<3;k++) {
    
          		int t=f[u][0][k];
          		if (t!=-1) g[1][j+1]=max(g[1][j+1],f[x][1][j]+t);
            }
		  }
	    }
	    memcpy(f[x],g,sizeof(f[x]));
	}
  for(int i=0;i<3;i++) {
    
  	ans=max(ans,f[x][0][i]);
  	ans=max(ans,f[x][1][i]);
  	if (fa) ans=max(ans,f[x][0][i]+1);
  }
}

int main() {
    
  memset(f,255,sizeof(f));
  int n;
  scanf("%d",&n);
  for(int i=1;i<n;i++) {
    
  	int x,y;
  	scanf("%d%d",&x,&y);
  	e[x].push_back(y);
  	e[y].push_back(x);
  }
  dfs(1,0);
  printf("%d\n",ans);
  return 0;
}

E. JYPnation

给定的图是一个竞赛图。众所周知,竞赛图缩点后形成一条链,且取一个生成子图,若存在环必然存在三元环。显然根据题意,只可能有最后一个强连通分量大小 > 1 >1 >1。那么不断删去 0 0 0度点,只考虑一个非平凡强连通分量的情况。
考虑枚举点 x x x计算所有 d i s ( x , y ) dis(x,y) dis(x,y),那么可以发现 ∀ y \forall y y d i s ( x , y ) ≤ 3 dis(x,y)\leq 3 dis(x,y)3,证明是考虑若最短路长度 > 3 >3 >3,注意到最短路上不相邻的节点一定由后面连向前面,那么取出最短路上最后三个点及 x x x就非法了。
d i s ( x , i ) = 1 dis(x,i)=1 dis(x,i)=1显然当且仅当 x x x i i i有边,令 d i s ( x , i ) = 1 dis(x,i)=1 dis(x,i)=1的集合为 S S S d i s ( x , i ) > 1 dis(x,i)>1 dis(x,i)>1的集合为 T T T,显然 S S S T T T都非空。
考虑 T T T集合中一个点 y y y,使得 d i s ( x , y ) = 2 dis(x,y)=2 dis(x,y)=2,那么令 S S S中到 y y y有边的集合为 U U U,其他点集合为 V V V,显然 U U U非空。首先容易证明 U U U中无环,其次可以证明 U U U V V V连接的边都是由 V V V连向 U U U(否则若存在 p ∈ U p\in U pU q ∈ V q\in V qV,由 p p p连向 q q q,那么取出 x x x p p p y y y q q q就非法了),还能证明 V V V中也无环(否则必存在三元环,且全部连向至少一个 U U U中的点,显然非法)。
这样,可以发现 S S S内部形成一条链,且连向 y y y的点是这条链的一个后缀。事实上,甚至可以证明 T T T内部也形成一条链,且 d i s ( x , y ) = 3 dis(x,y)=3 dis(x,y)=3的点是这条链的一个后缀,并且从前往后考虑链上每个点, S S S到它的边数单调不升。
有了上面的引理就很好做了。考虑先求出 S S S内部最后一个点 m x mx mx,因为 S S S内部形成一条链,那么直接看两个点之间边的方向就可以判定在链上的相对位置关系,所以扫一遍即可。然后对于 T T T中每个点 y y y d i s ( x , y ) = 2 dis(x,y)=2 dis(x,y)=2当且仅当 m x mx mx y y y有边。
时间复杂度 O ( n 2 ) \mathcal O(n^2) O(n2)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

bool e[8005][8005];
int ind[8005];

bool vis[8005];
char str[8005];

int main() {
    
  int n;
  scanf("%d",&n);
  for(int i=1;i<=n;i++) {
    
  	scanf("%s",str+1);
  	int r=0;
  	for(int j=1;j<=n;j+=4) {
    
  		r++;
  		int t=(isdigit(str[r]))?str[r]-'0':str[r]-'A'+10;
  		e[i][j]=((t>>3)&1);
  		e[i][j+1]=((t>>2)&1);
  		e[i][j+2]=((t>>1)&1);
  		e[i][j+3]=(t&1);
	  }
  }
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
      if (e[i][j]) ind[j]++;
  ll ans=0;
  int sz=n;
  for(;;) {
    
  	int id=0;
  	for(int i=1;i<=n;i++)
  	  if (!vis[i]&&!ind[i]) {
    
  	  	  id=i;
  	  	  break;
		}
	if (!id) break;
	sz--;
	vis[id]=1;
	ans+=614LL*n*sz+sz;
	for(int i=1;i<=n;i++)
	  if (e[id][i]) ind[i]--;
  }
  for(int i=1;i<=n;i++)
    if (!vis[i]) {
    
    	int cnt=0,id=0;
    	for(int j=1;j<=n;j++)
    	  if (!vis[j]&&e[i][j]) {
    
    	  	cnt++;
    	  	if (!id||e[id][j]) id=j;
		  }
		ans+=cnt;
		for(int j=1;j<=n;j++)
		  if (!vis[j]&&i!=j&&!e[i][j]) ans+=((e[id][j])?2:3);
	}
  printf("%lld\n",ans);
  return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_38609262/article/details/105589734

智能推荐

Variance Calculation in Cost Object Accounting_ctf63282的博客-程序员秘密

1 Variance calculation in Cost Object Accounting is used for monitoring the financial aspects of day to day ...

关于计算机动画制作的过程,关于计算机制作动画的过程_赤水.鲁的博客-程序员秘密

关于计算机制作动画的过程 关于计算机制作动画的过程 较量争论灵便画妙技_2_动画制作过程1.txt41滴水能穿石,只由于它永久加害统一点。42洋火假定躲避点火的苦楚,它的一辈子都将昏暗无光。 本文由imaginationhyq进献 ppt文档可能在WAP端阅读体验欠佳。倡始您优先决议TXT,或下载源文件到本机检查。 2009 计算矫捷画妙技 第二讲 动画产进程 北京航空航天大学合计机学院 孟宪海 ...

Android.mk Application.mk CMakeLists.txt_折跃的博客-程序员秘密

1.编译静态库文件Android.mk:LOCAL_PATH := $(call my-dir)include $(CLEAR_VARS)LOCAL_MODULE := hello-jniLOCAL_SRC_FILES := hello-jni.cinclude $(BUILD_STATIC_LIBRARY)文件Application.mk:APP_MODULES :=hel...

python winsound_python写报警程序中的声音实现winsound_weixin_39812465的博客-程序员秘密

写windowns下的报警程序,有一个报警声音的实现,在python中有个winsound模块可以来实现,方法也很简单:import timeimport winsounddef play_music():winsound.PlaySound('alert', winsound.SND_ASYNC)time.sleep(3)&gt;import winsoundPlaySound(sound, f...

oracle asm软件,Oracle入门教程:ASM的kfed工具_井小歪不歪在拍照的博客-程序员秘密

ASM常用kfod来获取ASM磁盘组的物理磁盘信息,其用法如下:-bash-3.2$ kfod -help_asm_a/llow_only_raw_disks KFOD allow only raw devices [_asm_allow_only_raw_disks=TRUE/(FALSE)]_asm_l/ibraries ASM Libraries[_...

Apple可以改善下一代Apple Watch的4种心率变异性数据的方法_weixin_26744853的博客-程序员秘密

Being healthy is hard to quantify in today’s world. With the advent of wearable technology, health data are readily available at low costs in the hands of consumers. 在当今世界,很难量化健康 。 随着可穿戴技术的出现,消费者很容易以低...

随便推点

studio无法连接手机adb interface有黄色感叹号,无法识别_初来的菜的博客-程序员秘密

原创连接我的电脑——&gt;右击管理——&gt;选择左侧设备管理器——&gt;找到adb interface——&gt;右击更新驱动——&gt;浏览计算机以查找驱动程序软件——&gt;从计算机的设备驱动程序列表中选择——&gt;下一步从磁盘安装——&gt;选择电脑上的androidSDK目录中的android_winusb.inf 文件——&gt;选择第三项,也就是 “Android Com...

频谱效率是如何定义的 _wangchuanjin的博客-程序员秘密

频谱效率是如何定义的频谱效率Wn又称频带利用率,用来衡量系统的有效性。它定义为单位带宽传输频道上每秒可传输的比特数,单位是 bit/s/Hz。它是单位带宽通过的数据量的度量,由此衡量一个信号传输技术对带宽资源的利用率。如果传输频道的带宽为W ,我们有:Nw=Rb/w习惯上把Nw > 1的调制方案称为带宽有效性调制,反之则称为功率有效性调制。对于基带信号或单边带传输系统,奈奎

Android 实现View的渐隐渐现功能_无云的博客-程序员秘密

转自:http://www.open-open.com/lib/view/open1346906329006.htmlandroid实现View的渐隐渐现功能就用到了动画Animation首先在res目录下新建anim文件夹,然后再anim文件夹下新建xml文件gradually.xml该xml文件主要定义实现渐变的方式1xml 

vue错误TypeError_vue typeerror:readdirp : root argument must be a s_PrinciplesMan的博客-程序员秘密

【前提】:搭建项目商家详情头部时,能够完整渲染出整体头部界面无问题,但开发者工具仍然报出“Error in render: "TypeError: Cannot read property '0' of undefined”错误,具体如下【解决过程】:首先Google翻一下:见文之意:这里的意思就是模板在渲染时候,读取对象中的某个对象的属性值时,这个对象不存在,说通俗点就是三层表达式a.b.c,在对象a中没有对象b,那么读取对象a.b.c中的值,自然会报错。如果是两层表达式a.b则不

基于python的房价分析国内外_Python3爬取房价信息并分析|python爬虫|python入门|python教程..._weixin_39915204的博客-程序员秘密

https://www.xin3721.com/eschool/pythonxin3721/本文转载至知乎ID:Charles(白露未晞)知乎个人专栏下载W3Cschool手机App,0基础随时随地学编程>>戳此了解导语进入正题,利用Python爬取房价信息并进行简单的数据分析。好久没发爬虫相关的内容了,想想还是抽空过来发一篇吧~~~Ok,让我们开始吧~~~相关文件网盘下载链接: https://...

推荐文章

热门文章

相关标签