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