首页 > 其他分享 >0825 思维题两则

0825 思维题两则

时间:2022-08-26 18:13:34浏览次数:105  
标签:思维 int ll long 0825 fib -- 两则 tc

0825 思维题两则

感觉总得写点题解记录一下,但是不想记录的太复杂,记录一下策略吧

解的好和讲的好是两回事,我毕竟解的都不好,也就没人看了,所以记得简略一点,不求讲的好了

Fibonacci Strings

如果在区域赛碰到了应该会狠狠的猜结论,所以就没有仔细推为什么成立

结论:从后往前选,选大的

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 107;
const ll inf = 1e9+7;
ll fib[N],pre[N];
ll a[N],maxn;
void solve() {
	int n;
	cin >> n;
	ll sum = 0;
	for(int i = 1 ; i <= n ; i++) {
		scanf("%lld",&a[i]);
		sum += a[i];
	}
	int len = 0;
	for(int i = 1 ; i <= maxn ; i++) {
		if(sum == pre[i]) {
			len = i;
			break;
		}
		if(pre[i] > sum)
			break;
	}
	if(!len) {
		puts("No");
		return ;
	}
	int last = 0;
	for(int i = len ; i >= 1 ; i--) {
		int maxi = 0;
		for(int j = 1 ; j <= n ; j++) {
			if(j==last)
				continue;
			if(a[maxi] < a[j])
				maxi = j;
		}
		if(a[maxi] >= fib[i]) {
			a[maxi] -= fib[i];
			last = maxi;
		} else {
			puts("No");
			return ;
		}
	}
	puts("Yes");
	return ;
}
int main() {
	fib[1] = 1;
	pre[1] = 1;
	fib[2] = 1;
	pre[2] = 2;
	for(int i = 3 ; i <= 100 ; i++) {
		fib[i] = fib[i-1] + fib[i-2];
		pre[i] = pre[i-1] + fib[i];
		if(fib[i] > inf) {
			maxn = i;
			break;
		}
	}

	int tc;
	cin >> tc;
	while(tc--)
		solve();
}

Burenka and Traditions

太难了,这个结论不好猜

题意

需要把数组都变成\(0\),能操作使得一段同时异或一个任意值,每次操作消耗\(len/2\)向上取余,求最小操作次数

还得看wc的视频

由于消耗是向上取余的,所以操作应该只有一个数字和两个数字,多了就没有意义了,可以分解成一个数字和两个数字。

考虑贪心的话,我们可以假设答案是$ n$,这样能保证这些操作一定会把数组变成\(0\)。

如果将一段变成\(0\),肯定是一个数字一个数字的变成\(0\),结论:后面是前面的数字异或和时,可以减少一次操作把这一段变成\(0\)。因此,只要找前缀合是\(0\)的段就行,找到了\(ans--\)。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
typedef long long ll;

ll a[N];

void solve() {
	int n;
	scanf("%d",&n);
	unordered_map<ll,bool>mp;
	ll ans = n,now = 0;
	mp[0] = 1;
	for(int i = 1 ; i <= n ; i++ ) {
		ll t;
		scanf("%lld",&t);
		now^=t;
		if(mp.count(now)) {
			ans--;
			mp.clear();
			now = 0;
		}
		mp[now]=1;
	}
	cout << ans << endl;
}

int main() {
	int tc;
	cin >> tc;
	while(tc--)
		solve();
}

标签:思维,int,ll,long,0825,fib,--,两则,tc
From: https://www.cnblogs.com/zhaohanzheng/p/16628510.html

相关文章

  • Xmind思维导图教程十二:如何在Xmind中设置仅显示工具栏的图标?
    Xmind2022Mac是一款非常便捷的制作思维导图的软件,制作思维导图可以帮助用户更高效的进行学习,在Xmind中如何设置仅显示工具栏的图标?下面我们分享具体的操作步骤。1、在Mac......
  • 【luogu AT2377】Blue and Red Tree(思维)(STL)(启发式合并)
    BlueandRedTree题目链接:luoguAT2377题目大意给你一棵树,每次你可以选一条路径,删掉其中的一条边,然后把路径两断点编号在另一个一样点数的图上连边。然后给你一个要求......
  • 3 敏捷测试思维方式
     敏捷测试与传统测试之间的区别,不仅在于测试的独立性、阶段性、计划性、自动化测试等多个方面有很大的不同,而且更大的区别是在测试原则和测试思维模式(TestMindset,也可翻......
  • [转]一线技术人应该关注的四种思维能力
    一、引言作为长期奋战在一线的技术人,我深刻体会到如下几个思维能力对技术人成长的重要性,熟练运用这几种思维可以帮助我们快速的进入到新的领域,在分析、定位和解决问题上有......
  • [转]16种常用的思维模型
    人们在围绕软件开发的讨论中,几乎不可避免会随口引用一两条原则。你可能听过人们说:“这行不通,因为‘X法则’!”。或者“你不知道‘Y原则’吗?”你是哪种类型的软件开发人员?......
  • Codeforces Round #292 (Div. 2) C. Drazil and Factorial(思维)
    https://codeforces.com/contest/515题目大意:给我们一个长度为n的数字a定义F(a)=a里面每一位数的阶层总乘积让我们求最大的x,需要满足F(x)=f(a)并且x中没有0和1input4......
  • Codeforces Round #638 (Div. 2) B. Phoenix and Beauty(构造/思维)
    https://codeforces.com/contest/1348/problem/B如果一个数组的所有长度为k的子数组的和相同,那么这个数组就是美丽的。数组的子数组是任何连续元素的序列。Phoenix目前......
  • 链路预测思维导图大纲
    最近帮同门写一份链路预测相关的introduction,再收集资料的同时,收获了一份链路预测大纲的思维导图,感觉很清晰,故此分享......
  • Codeforces Round #743 (Div. 2) B. Swaps(思维)
    https://codeforces.com/contest/1573/problem/B给定两个长度为n的数组,数组a和数组b数组a包含从1到2*n的任意顺序的奇数,数组b包含从1到2*n的任意偶数可执行的操作如下:......
  • CF1705(思维,二进制)
    https://codeforces.com/contest/1705/problem/E题意:给出01串s和t,问通过以下操作使s变成t的最小操作数。操作:s-1不同于s+1时,s取反。eg:110->100场上直接模拟后,感觉直接模......