这一场div2主要偏向于公式的推导对于时间复杂度的优化。这要求我们对于生活中的一些数字图案具有一定的敏感度。

       题目中给了我们许多的提示，比如1e5的数据量，如果我们采取逐个配对的方法，那么时间复杂度一定会超时。再考虑到各种数据结构的嵌套中，并没有一种适合的方法。此时，我们的思考方向就要偏向于规律、化简。我们不妨对于数据进行枚举来寻找其中的规律。

题目大意
给定n个数字组成的数字（n的范围为（2,1e5））。每一个数字大小为（1,1e6）之间。问任一大于2的区间段内所有数字组成的集合的最大值与最小值的乘积的最大值

解题思路
这是一个非常经典的规律总结题。从最平凡的入手，我们会发现求出所有的区间段的值，它的时间复杂度为O(1e10)。首先，我考虑到dp动态规划的推导。那么要求出所有的区间段用（l,r）来维护，显然时间复杂度并没有优化。此时，我们不妨贪心的去思考这个问题，我们能否从最大处开始枚举，答案也是否定的。最后，在各种方法的试探之下，并没有一个符合的解决办法。那么，我们从规律入手，会发现对于三个数来说，我们会发现f(1,3)永远小于max(f(1,2),f(2,3))。我们会发现数组合并时，最小值的大小永远不会增加。

代码

#include<bits/stdc++.h>
using namespace std;

#define debug(a) cout << #a << ": " << a << endl;
#define LL long long 
#define IO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const int maxn = 1e5+10;
int a[maxn];

void solve()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;++i) {
        cin >> a[i];
    }
    LL ans = 0;
    for(int i = 2;i <= n;++i) {
        ans = max(ans,a[i]*1ll*a[i-1]);
    }
    cout << ans << endl;
}

int main()
{
    IO;
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

题目总结
这是一个非常常见的规律总结题。近似于短板效应，要建立一个长盛不衰的知识体系，就要不断学习巩固所学知识。而不是各方面都留有漏洞，多学不如精学。

题目大意
给定一个长度为n的数组和一个整数k。求出任意数对（i,j）i！=j满足ij-k(ai*aj)取得最大值。n的范围（2,1e5）,k的范围min（n,100）,ai的范围（1，n）

解题思路
我们希望取得最大值，那么我们不妨取i=n-1,j=n;我们可以发现f(n-1,n)的最小值为n^2-2kn-n，而f(i,n)的最大值为in。要使f(i,n)大于f(n-1,n)那么i的范围需要大于n-2k。由此可化简时间复杂度为O(1e7)

代码

#include<bits/stdc++.h>
using namespace std;

#define debug(a) cout << #a << ": " << a << endl;
#define LL long long 
#define IO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const int maxn = 1e5+10;
int a[maxn];


void solve()
{
    int n,k;
	cin >> n >> k;
	for(int i = 1;i <= n;++i) {
		cin >> a[i];
	}
	int l = max(1,n-200);
	LL ans = -1*1e18;
	for(int i = l;i < n;++i) {
		for(int j = i+1;j <= n;++j) {
			ans = max(ans,i*1ll*j-1ll*k*(a[i] | a[j]));
		}
	}
	cout << ans << endl;
}

int main()
{
    IO;
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

题目总结
一道比较经典的规律总结题，难度不高，很考验思维。但也给了相关提示。

题目大意
有t组样例，t的范围（1,3e4）
每组样例，给定n,m两个数，它们的范围为（1,1e9）
从n异或0,n异或1，······，n异或m。
求这些数组成的数组中第一个没有出现的最小的自然数的值。

解题思路
我们不妨从另一个角度思考，a异或b等于c。那么a异或c也就等于b。从这个角度出发，我们可以发现a如果异或一个值小于b。那么a通过异或就可以得到那个值。题目转变为求出最小的值使得a与其异或的值大于等于m+1

代码

#include<bits/stdc++.h>
using namespace std;

#define debug(a) cout << #a << ": " << a << endl;
#define LL long long 
#define IO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

void solve()
{
    int n,m;
    cin >> n >> m;
    ++m;
    int ans = 0;
    for(int k = 30;k >= 0;k--) {
        if((n>>k&1) == (m>>k&1)) continue;
        else if((n>>k&1) == 1) break;
        else ans |= (1<<k);
    }
    cout << ans << endl;
}

int main()
{
    IO;
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

题目总结
异或，我们不妨首先就考虑所有数字的二进制呈现形式。

题目大意
构造一个字符串，使得字符串中的每一个子串出现的次数都为奇数。

解题思路
为了使每一个子串出现的次数都为奇数，我们尽可能采用少量的字符串。通过实验证明了方法的可行性，见代码。

代码

#include<bits/stdc++.h>
using namespace std;

#define debug(a) cout << #a << ": " << a << endl;
#define LL long long 
#define IO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

int main()
{
    IO;
    int t;
    cin >> t;
    while(t--){
         int n;
         cin >> n;
         if(n == 1) {
            cout << 'a';
         }
         else if(n%2 == 0) {
            for(int i = 0;i < n/2;++i) cout << 'a';
            cout << 'b';
            for(int i = 0;i < n/2-1;++i) cout << 'a';
         }
         else {
            for(int i = 0;i <= n/2-1;++i) cout << 'a';
            cout << 'b' << 'c';
            for(int i = 0;i < n/2-1;++i) cout << 'a';
         }
         cout << endl;
    }
    return 0;
}

题目总结
字符串构造，第一，尽量采用少量的字符串；第二，大规模地数据构造体验。

题目概括
一种抽象化的剪枝，达到优化时间复杂度的目的。

代码

#include<bits/stdc++.h>
using namespace std;

#define debug(a) cout << #a << ": " << a << endl;
#define LL long long 
#define IO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const int maxn = 1e5+10,mod = 998244353;
int ans[maxn];
vector<vector<int>> ej(maxn);
int eo[maxn];
int sz[maxn];

void dfs(int p, int i) {
	int o;
	sz[i] = 1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (j != p) {
			dfs(i, j);
			sz[i] += sz[j];
		}
	}
}

void solve()
{
    int n;
    cin >> n;
    for(int i = 0;i < n;++i) eo[i] = 0;
    for(int i = 0;i < n-1;++i) {
        int x,y;
        cin >> x >> y;
        x--,y--;
        eo[x]++;
        ej[x].push_back(y);
        eo[y]++;
        ej[y].push_back(x);
    }
    for(int i = 0;i <= n+5;++i) ans[i] = 0;
    ans[1] = 1;
    for(int i = 0;i < n-1;++i) 
        ans[1] = ans[1]*2%mod;
    dfs(-1,0);
    for (int i = 2;i <= n;i++)
    if ((sz[0] - 1) % i == 0) {
        int good = 1;
        for (int j = 1;j < n;j++)
            if (sz[j] % i > 1) {
                good = 0;
                break;
            }
        if (good)
            ans[i]++;
    }
    for (int i = n;i >= 1;i--)
        for (int j = i + i;j <= n;j += i)
            ans[i] = (ans[i] - ans[j] + mod) % mod;
    for (int i = 1; i <= n; i++)
        cout << ans[i] << ' ';
    cout << endl;
    for(int i = 0;i < n+5;++i) {
        ej[i].clear();
    }
    return ;
}

int main()
{
    IO;
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}