linq button build controller vue绑定点击事件 管理后台框架 后台系统模板 sql数据库教学视频 jq选择子元素 bootstrap日历插件 pip环境变量 安卓虚拟机运行windows java 注解 kubernetes视频教程 mysql建表 python如何注释 python使用正则表达式 java教学 java抽象方法 垃圾邮件数据集 microkms 计算机网络自顶向下 idea重命名快捷键 说话不算数的经典语句 spss22安装教程 修改ip地址软件 天正建筑2007 电脑书籍下载 电脑代码雨 羽化快捷键 爱奇艺视频下载到电脑 cad拉伸命令 ps阵列 dll注入器 联表查询 python去掉空格 cdr填充颜色 只狼二段跳 代理服务器软件 骰子技巧
当前位置: 首页 > 学习教程  > 编程语言

The Oculus HDU - 6768(ull自然取余溢出 哈希)

2020/8/11 19:13:31 文章标签:

Let’s define the Fibonacci sequence F1,F2,… as F1=1,F2=2,Fi=Fi−1+Fi−2 (i≥3).

It’s well known that every positive integer x has its unique Fibonacci representation (b1,b2,…,bn) such that:

· b1×F1+b2×F2+⋯+bn×Fn=x.

· bn=1, and for each i (1≤i<n), bi∈{0,1} always holds.

· For each i (1≤i<n), bi×bi+1=0 always holds.

For example, 4=(1,0,1), 5=(0,0,0,1), and 20=(0,1,0,1,0,1) because 20=F2+F4+F6=2+5+13.

There are two positive integers A and B written in Fibonacci representation, Skywalkert calculated the product of A and B and written the result C in Fibonacci representation. Assume the Fibonacci representation of C is (b1,b2,…,bn), Little Q then selected a bit k (1≤k<n) such that bk=1 and modified bk to 0.

It is so slow for Skywalkert to calculate the correct result again using Fast Fourier Transform and tedious reduction. Please help Skywalkert to find which bit k was modified.
Input
The first line of the input contains a single integer T (1≤T≤10000), the number of test cases.

For each case, the first line of the input contains the Fibonacci representation of A, the second line contains the Fibonacci representation of B, and the third line contains the Fibonacci representation of modified C.

Each line starts with an integer n, denoting the length of the Fibonacci representation, followed by n integers b1,b2,…,bn, denoting the value of each bit.

It is guaranteed that:

· 1≤|A|,|B|≤1000000.

· 2≤|C|≤|A|+|B|+1.

·∑|A|,∑|B|≤5000000.
Output
For each test case, output a single line containing an integer, the value of k.
Sample Input
1
3 1 0 1
4 0 0 0 1
6 0 1 0 0 0 1
Sample Output
4

**思路:**一开始比赛看到这个题,无从下手,肯定会爆数据范围,后来发现,ull自然溢出取余,哈希思想直接暴力就可以做出来,草率了。。。不过也让我知道了原来这就是哈希思想。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<iomanip>
#include<map>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<set>
#include<cctype>
#include<string>
#include<stdexcept>
#include<fstream>
#include<sstream>
#define mem(a,b) memset(a,b,sizeof(a))
#define debug() puts("what the fuck!")
#define dedebug() puts("what the fuck!!!")
#define ll long long
#define ull unsigned long long
#define speed {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); };
using namespace std;
const double PI = acos(-1.0);
const int maxn = 2e6 + 50;
const int N = 110;
const int INF = 0x3f3f3f3f;
const int inf = 0xfffffff;//比INF小,防止累加爆int
const double esp_0 = 1e-6;
const double gold = (1 + sqrt(5)) / 2;
const int mod = 193;
int gcd(int x, int y) {
	return y ? gcd(y, x % y) : x;
}
struct node {
	ll a, b, c, d;
	node(ll a, ll b, ll c, ll d) :a(a), b(b), c(c), d(d) {};
};
ull f[maxn];
void init() {
	f[1] = 1;
	f[2] = 2;
	for (int i = 3; i < maxn; ++i) {
		f[i] = f[i - 1] + f[i - 2];
	}
}
int main() {
	init();
	int t;
	scanf("%d", &t);
	while (t--) {
		int a, b, c;
		ull A = 0, B = 0, C = 0;
		scanf("%d", &a);
		for (int i = 1; i <= a; ++i) {
			int x;
			scanf("%d", &x);
			if (x)A += f[i];
		}
		scanf("%d", &b);
		for (int i = 1; i <= b; ++i) {
			int x;
			scanf("%d", &x);
			if (x)B += f[i];
		}
		scanf("%d", &c);
		for (int i = 1; i <= c; ++i) {
			int x;
			scanf("%d", &x);
			if (x)C += f[i];
		}
		A *= B;
		int step = 1;
		while (C + f[step] != A) {
			step++;
		}
		printf("%d\n", step);
	}
	return 0;
}

本文链接: http://www.dtmao.cc/news_show_100084.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?