T1 简单的求和（原题 HDU4473 Exam）
开始想复杂了。。。想到什么数论分块套数论分块，还是只能拿部分分。。。
一看题解，傻眼了。。。简直完全是最基础的暴力。。。
因为 (a*b|x)，所以我们假设商为 c，则 a*b*c=x
枚举 a和b（a<b<c）有序排列，减少循环。。。
最后答案通过排列组合算出：
1、三个数相同，只有一种情况。
2、三个数中有两个相同，则算3次。
3、三个数互不相同，则算6次。
代码：
1 #include<cstdio> 2 #include<iostream> 3 #define ll long long 4 using namespace std; 5 ll n,a,b,c,ans; 6 int main() 7 { 8 freopen("sum.in","r",stdin); 9 freopen("sum.out","w",stdout); 10 scanf("%lld",&n); ans=0; 11 for (a=1; a*a*a<=n; ++a) 12 for (b=a; a*b*b<=n; ++b) 13 { 14 c=n/(a*b); 15 if (c<b) break; 16 if (a==b) ans+=(c-b)*3+1; 17 else ans+=(c-b)*6+3; 18 } 19 printf("%lld\n",ans); 20 fclose(stdin); fclose(stdout); 21 return 0; 22 }
T2 奇妙的数列（原题BZOJ 4059 Non-boring sequences）
dalao门都用线段树+扫描线虐，蒟蒻表示不会，以后再说。。。
但是考场上想到了对于区间 [l,r]，存在 x in [l,r] 且 pre[x]<l && nxt[x]>r 则该区间成立，否则不满足。 然而我还在线性O(n)找规律（没办法，太弱了。。。）
这里其实很明显的分治。诶！！！
再专业点这题用的是 逆启发式合并过程。
满足条件则返回，否则从两边往中间找中间点 i，拆开两边分别分治递归。
复杂度大概 O(nlogn)
注：还有一点这里我用 map存某个值最新一次出现的位置，用数组+离散化没试过（map本身也是离散的）
贴代码：
1 #include<cstdio> 2 #include<map> 3 using namespace std; 4 const int N=200005; 5 int n,t,a[N],pre[N],nxt[N]; 6 inline bool check(int l,int r) 7 { 8 if (l>=r) return l; 9 int ll=l,rr=r; 10 for (int i=l; i<=r; ++i) 11 { 12 if (i&1) 13 { 14 if (pre[ll]<l && nxt[ll]>r) return (check(l,ll-1)&&check(ll+1,r)); ++ll; 15 } 16 else { 17 if (pre[rr]<l && nxt[rr]>r) return (check(l,rr-1)&&check(rr+1,r)); --rr; 18 } 19 } 20 return 0; 21 } 22 int main() 23 { 24 freopen("sequence.in","r",stdin); 25 freopen("sequence.out","w",stdout); 26 scanf("%d",&t); 27 while (t--) 28 { 29 scanf("%d",&n); 30 map<int,int> M; 31 for (int i=1; i<=n; ++i) 32 { 33 scanf("%d",&a[i]); 34 nxt[M[a[i]]]=i; 35 pre[i]=M[a[i]]; 36 M[a[i]]=i; 37 } 38 for (int i=1; i<=n; ++i) nxt[M[a[i]]]=n+1; 39 if (check(1,n)) puts("TAK"); else puts("NIE"); 40 } 41 return 0; 42 }
T3 树上的路径（原题 BZOJ 4458 GTY的OJ）
原文：https://www.cnblogs.com/Frank-King/p/9870680.html
