首页 > 其他分享 >[Usaco2017 Open]Bovine Genomics 题解^&*^(

[Usaco2017 Open]Bovine Genomics 题解^&*^(

时间:2024-05-23 17:40:14浏览次数:17  
标签:Usaco2017 Genomics 600 int 题解 long 1100

不知道为啥,我死活想不到二分(楼下正解)

所以,就有了这篇题解

可以看到,这道题离暴力的距离只有一步!

就是数组开不下!!

小问答:数组开不下时,你会?
A:map
B:优化代码
C:gp_hash_table

由于正在学hash,所以容易想到...

tong[本来的下标%9999999]

然后就玄学的过了。。。

ACcode

#include<bits/stdc++.h>
#define int long long
using namespace std;
char a[600][1100],b[600][1100];
int n,m,cnt;
signed tong[10000000];
unsigned long long ha[600][1100],hb[600][1100],mi[1100];
signed main(){
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i]+1;
	}
	for(int i=1;i<=n;i++){
		cin>>b[i]+1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			ha[i][j]=ha[i][j-1]*13331+a[i][j]-'A'+1;
			hb[i][j]=hb[i][j-1]*13331+b[i][j]-'A'+1;
		}
	}
	mi[0]=1;
	for(int i=1;i<=m+10;i++){
		mi[i]=mi[i-1]*13331;
	}
	for(int j=1;j<=m;j++){
		for(int i=1;i+j<=m;i++){
			int flag=1;++cnt;
			for(int l=1;l<=n;l++){
				tong[(1uLL*ha[l][i+j]-ha[l][i]*mi[j]-'A'+1)%9999999]=cnt;
			}
			for(int l=1;l<=n;l++){
				if(tong[(1uLL*hb[l][i+j]-hb[l][i]*mi[j]-'A'+1)%9999999]==cnt){
					flag=0;
					break;
				}
			}
			if(flag){
				cout<<j;
				return 0;
			}
		}
	}
	return 0;
}

标签:Usaco2017,Genomics,600,int,题解,long,1100
From: https://www.cnblogs.com/lewisak/p/18209074

相关文章

  • 【转载】2024年度山东省自然科学基金项目(第一批)申报常见问题解答
    地址:https://mp.weixin.qq.com/s?__biz=Mzg2NDU5NjA1OQ==&mid=2247579452&idx=2&sn=a038e35fb2958666ab255993008c8064&chksm=ce650e08f912871e77d05569567a15fdffcbedd6a1762a19433b4aabcdcbdf96272d52e28112&mpshare=1&scene=23&srcid=0523SHJ0......
  • Vue 使用 Devextreme框架,下拉框不会随页面的滚动而移动的问题解决
    Devextreme的DxSelectBox组件的下拉选项部分,默认是绝对位置布局,导致页面滚动时,下拉部分不会上下移动个人的解决方案,监听页面滚动事件,如果目前有打开的下拉框,先关闭下拉框,随后迅速再打开,视觉效果上可以做到下拉选项跟随组件滚动vue项目中可能会有很多页面,很多下拉框,我是用的给每......
  • NPOI创建word文档,使用unicode写入打勾的小方框,word2021显示异常问题解决
    word2019查看NPOI创建的word中打勾方框,显示正常,但是word2021显示就变成下面这个样子了,应该是word2021对这个特殊字符的渲染导致的 想要普通的效果,白色背景黑边黑勾的效果,换一个字体可以解决 c# 代码XWPFDocumentdocument=newXWPFDocument();XWPFParagraphparagrap......
  • Java RMI遇到的Connection refused to Host: 127.x.x.x/192.x.x.x/10.x.x.x问题解决方
    问题故障解决记录--JavaRMIConnectionrefusedtohost:x.x.x.x....在学习JavaRMI时,我遇到了以下情况问题原因:可能大家的host是10或者192的私有地址,我估计都是和我一样的一个原因:/etc/hosts文件的配置问题(我是ubuntu系统下的实验环境),也就是主机名称和IP地址的映射关系......
  • Git:warning: CALF wilL be replaced by LF in xxxx 问题解决
    warning:CALFwilLbereplacedbyLFinxxxx问题解决办法出现这个问题的原因是像缓存区中提交文件时出现的 原因:windows中的换行符为CRLF,而在Linux下的换行符为LF,所以在执行add.时出现提示也就是,工作区的文件都应该用CRLF来换行。如果 改动文件时引入了LF,提......
  • git:Unable to negotiate问题解决
    场景说明:安装了Gitblit(自架的代码仓库服务)发现部分电脑无法推代码,报错误如下:Unabletonegotiatewith****port22:nomatchinghostkeytypefound.Theiroffer:ssh-rsa并排队了账户权限问题。解决方案:1.打开问题电脑的系统盘的当前登陆用户文件夹('C:\Users\你当前的......
  • [ARC178C] Sum of Abs 2 题解
    题意:给定\(n\)和\(L\)以及\(n\)个数\(a_i\)。对于每个\(1\lei\len\),求出一个长度为\(L\)的\(b\)序列满足:\(\sum_{i=1}^{L-1}\sum_{j=i+1}^{L}|b_j-b_i|=a_i\),并最小化\(b\)中的最大值。显然\(b\)中元素的顺序不影响原式的结果,所以我们可以假定\(b\)是不......
  • CF1085D Minimum Diameter Tree 题解
    CF1085DMinimumDiameterTree题解比较水的一道绿题观察样例可以发现,边权都平分在叶子节点唯一的一条连边上,由此猜到联想到可以把贪心地将边权全部平均分配到这些边上,这样写出来就能AC了。如何证明先来一张图方便理解:利用反证法:假设按上述做法分配边权后可以至少修改一次......
  • [SDOI2009] 晨跑 题解
    每个点拆成入点和出点。发现每个点、每条边都只能经过一次,所以所有边的容量都是\(1\)。#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintN=405,M=1e5+5;intn,m,s,t,k=1,h[N],vis[N];intto[M],nxt[M],w[M],f[M];intlst[N],flw[N],dis[N];v......
  • [SDOI2016] 数字配对 题解
    发现题目中描述的配对条件可以理解为:\(pc_i-pc_j=1\)且\(a_i\bmoda_j=0\),其中\(pc_i\)表示\(a_i\)的质因数个数。自然想到以\(pc\)奇偶性建立二分图,可以配对的点间连一条边。先不考虑费用,三种边为:\((s,i,b_i)\),其中\(pc_i\bmod2=1\)。\((i,t,b_i)\),其中\(pc_i\bm......