第十四届蓝桥杯大赛软件赛省赛A组 C++

· · 个人记录

C:平方差

X=YY-ZZ,X=(Y+Z)(Y-Z)=T1T2

Y=(T1+T2)/2,Z=(T1-T2)/2,T1T2奇偶性相同;

x为奇数总是可以 X=1*X 若X为偶数，则两个因子都为偶数，看他是否为4的倍数。 分开两种情况讨论即可。

D更小的数

思路：逆序对总是可以的。23（）32这样的带回文的也是可以的。统计完逆序再统计区间两端的回文有些麻烦。 但这样的区间是依赖内部区间的，从小区间到大区间。考虑区间dp

设置bool dp[i][j]为这个区间反转后是否为符合要求的区间。

枚举区间长度,枚举起点i，找到终点j dp[i][j] ai<aj:=0;ai>aj:=1 ai=aj:dp[i-1][j-1]，实际复杂度O(N*N)