题目1：最大公约数的延伸问题

P1414 又是毕业季II - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目上提及了最大公约数，但是解答却没有直接使用最大公约数doge

题目意思是 给定n个数，再给定一个k，往这n个数中取k个，求这k个数的最大公约数是多少？

然后题目的要求是k的取值为1到n全部取一遍，分别求出对应的最大公约数。

我们知道，当取的数的个数越多，最大公约数肯定是小于等于取的个数少时的答案的。因为限制会变多。

一开始很容易想到枚举n个数取k个的所有组合，然后分别用辗转相除法求最大公约数，但是复杂度明显不符合要求，于是必须换一种思路。

我们想到，k个数的公约数含义就是这k个数均含有某个因数，如果我们把所有数的因数全部求出来，发现有k个数均含有某个因数，那么这个数必然是这k个数的公约数。其中找出最大的就是它们的最大公约数。但是要如何高效的做到这点呢？考虑到对于k=1，2……，n都要求出，我们可以这么做：

* 1、 求出每个因数出现的次数。

* 2、 对于每个次数记录最大的因数。

我们在输出答案的时候 选择默契值的最大值t开始往小查找。只要这个默契值的出现次数大于等于当前我们遍历到的人数，就可以认定为它是最大公约数，因为是从大到小遍历的。

于是我们的 做法如下：

void solve(){
    int t = 0;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        t = max(t,x);
        int m = sqrt(x);
        for(int j=1;j<=m;j++){
            if(x%j==0){
                c[j]++;  //c[]用于记录某个因子的出现次数。
                if(x!=j*j) c[x/j]++;
            }
        }
    }
    //输出结果。
    int x= t;
    for(int i=1;i<=n;i++){
        while(c[x]<i)x--;
        cout<<x<<endl;
    }
}   

题目2：前缀和&差分

基础：

前缀和解答区间查询问题：P8218 【深进1.例1】求区间和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

解答:

int a[100005],b[100005];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i] = b[i-1]+a[i];   //这里做出前缀和
    }
    int m;
    cin>>m;
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        cout<<b[r]-b[l-1]<<endl;  //这里记住如何求区间和
    }
}   

前缀和+差分解答多次区间增值问题：P2367 语文成绩 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

解答：

int a[5000005],b[5000005];
void solve(){
    int n,t;
    cin>>n>>t;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i] = a[i]-a[i-1];   //差分数组，事实上是后一项减去前一项的差值。
    }
    for(int i=1;i<=t;i++){
        int l,r,x;
        cin>>l>>r>>x;
        b[l]+=x;
        b[r+1]-=x;            //公式化的区间增值。记住就好，可以画图理解。
    }
    int minn=inf;
    for(int i=1;i<=n;i++){
        a[i] =a[i-1] + b[i];    //这里是差分数组转换为正常数组，也就是前缀和的逆形式。  可以观察和前面差分处理的区别。
        minn = min(a[i],minn);
    }
    cout<<minn<<endl;
}   

拓展：二维前缀和 和 二维差分

P3397 地毯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

int main()
{
	cin>>n>>t;
	while(t--)   //二维差分
	{
		cin>>lx>>ly>>rx>>ry;
		++b[lx][ly];
		--b[rx+1][ly];
		--b[lx][ry+1];
		++b[rx+1][ry+1];
	}
	for(int i=1;i<=n;i++) 
		for(int j=1;j<=n;j++) 
		{
			a[i][j]=b[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];  //求原数组
			cout<<a[i][j]<<" ";
			if(j==n) cout<<endl;
		}
	return 0;
}

题目3：离散化

暂时没找到专门讲这个的题，后面再补充吧

题目4：滑动窗口

做了一个类似的滑动窗口，不知道是不是，因为这个题归类归到了离散化名下。

[P3029 USACO11NOV] Cow Lineup S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

做法是将距离（struct node中的x）由小到大排序，然后在一个窗口中框住含有每一个不同种类的奶牛，维护距离的最小值，然后处理窗口左边界。

struct node {
    int x,p;
}s[70005];


bool cmp(node a,node b){
    return a.x<b.x;
}

void solve(){
    int n;
    cin>>n;
    map<int,int>t;
    map<int,bool>vis;
    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>s[i].x>>s[i].p;
        if(vis[s[i].p]==0){
            sum++;
            vis[s[i].p] = 1;
        }
    }    
    sort(s+1,s+1+n,cmp);
    int tail = 1;
    t[s[1].p]++;//最左边，第一格
    int tmp = 1;
    int ans = inf;
    //滑动窗口思想
    for(int i=1;i<=n;i++){
        while(tmp<sum&&tail<n){
            tail++;
            t[s[tail].p]++;
            if(t[s[tail].p]==1) tmp++;
        }
        if(tmp == sum) ans = min(ans,s[tail].x - s[i].x);
        t[s[i].p]--;
        if(t[s[i].p] == 0)tmp--;//处理左端   相当于左边界往后挪了一格。
    }
    cout<<ans<<endl;
}   

另外，今日有一场萌新赛，打得很垃圾，5/8。希望这几天能补满。