基础赛 T1，T2，T3 题解

经验分享区
1

我太菜了。

T1

特判一下主题库即可。
还是放个核心代码吧

if('0'<=s[0]&&s[0]<='9') cout<<"https://www.luogu.com.cn/problem/P"<<s<<"\n";
else cout<<"https://www.luogu.com.cn/problem/"<<s<<"\n";

时间复杂度 O(T) 。

T2

首先将其化为二进制。
若长度不为二的整数次幂，将不为一的一项拆分即可。
这里用到了一个技巧，判断是否为二的整数次幂可以用 !(n&(n-1))。
再贴个核心代码

for(int i=1;i<=(int)1e18;i<<=1){
	if(m&1) a[++cnt]=i;
	m>>=1;
}
while(cnt&(cnt-1)){
	for(int i=1;i<=cnt;i++){
		if(a[i]!=1){
			for(int j=cnt+1;j>=i;j--){
				a[j+1]=a[j];
			}
			a[i]/=2,a[i+1]/=2,cnt++;
			break;	
		}
	}		
}

时间复杂度 O(T\log n) 。

T3

容易发现， f(b) 要么为 0 ，要么为 1 。
所以我们预处理一下 a_i>a_{i+1} 的个数，再计算。
先枚举右端点，再枚举左端点，同时用前缀和的方式优化计算。
如果满足条件的对数大于一，直接 break。

for(int r=3;r<=n;r++){
	for(int l=r-2;l>=1;l--){
		int t=cnt[r-1]-cnt[l-1];
		if(t==1) cnt2+=(a[r]<a[l]);
		if(t>1) break;
	}
}

时间复杂度可以卡到 O(Tn^2) 。
众所周知 n^2 能过千万，我们就成功通过了这道题。

1 个赞
2

T3 得注意到做很多次操作和做一次操作是等价的。

然后你就会发现 f(x)\in\{0,1\} 。

f_{a_{l\cdots r}}=1 当且仅当 a_{l\cdots r} 左边一部分单调递增，右边一部分单调递增，右边最大的元素比左边最小的元素小，这样才能接上。

双指针拿下了。时间复杂度 O(\sum n) 。

#include<bits/stdc++.h>
using namespace std;
int T,n,a[6000000],it,r;
long long ans;
int main(){
	read(T);
	while(T --){
		read(n),it = 1,r = ans = 0;
		for(int i = 1;i <= n;i ++) read(a[i]);
		for(int i = 1;i <= n;i ++){
			if(a[i] < a[i - 1]) it = r + 1,r = i - 1;
			while(a[it] < a[i] && it <= r) it ++;
			ans += r - it + 1; 
		}
		printf("%lld\n",ans);
	}
	return 0;
}
3

感谢大佬
%%%%%%%%%%%%%

4

按理说，非求助性帖子不能给解决方案哦~