AGC038

时间：2019-09-22 18:51:23 阅读：82 评论：0 收藏：0 [点我收藏+]

开题开错翻车场.jpg

A

sol

$A > \frac{W}{2}$或者$B > \frac{H}{2}$的时候无解，否则构造方法长下面这样

技术分享图片

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

int main(){
    int H , W , A , B; cin >> H >> W >> A >> B;
    if(A > W / 2 || B > H / 2){puts("-1"); return 0;}
    for(int i = 1 ; i <= B ; ++i){
        for(int j = 1 ; j <= A ; ++j)
            putchar('0');
        for(int j = A + 1 ; j <= W ; ++j)
            putchar('1');
        putchar('\n');
    }
    for(int i = B + 1 ; i <= H ; ++i){
        for(int j = 1 ; j <= A ; ++j)
            putchar('1');
        for(int j = A + 1 ; j <= W ; ++j)
            putchar('0');
        putchar('\n');
    }
    return 0;
}

B

sol

我们令$i,j$相等当对$[i,i+K)$排序和对$[j,j+K)$排序后结果一样。我们考虑这样会有什么性质。

当这两个排序区间无交的时候，只有可能这两个区间都是升序的，否则不可能会相等；

如果两个排序区间有交，则一定满足$[j,i+K)$中的最小值大于$[i,j)$中的最大值，且$[i,j)$的元素升序排列；$[j,i+K)$中的最大值小于$[i+K,j+K)$中的最小值，且$[i+K,j+K)$的元素升序排列。那么不难得到$\forall x,y \in [i,j]$，$x$和$y$都是相等的，也就是原序列一定可以划分成若干段极大区间满足区间内任意两个位置相等。

用单调队列/set把这些区间找出来，然后把第二段中的情况稍加判断即可。

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

int main(){
    static int arr[200003]; int N , K;
    cin >> N >> K; for(int i = 1 ; i <= N ; ++i) cin >> arr[i];
    set < int > num; int ans = 1;
    for(int i = 1 ; i <= K ; ++i) num.insert(arr[i]);
    for(int i = K + 1 ; i <= N ; ++i){
        ans += *num.begin() != arr[i - K] || *--num.end() > arr[i];
        num.erase(arr[i - K]); num.insert(arr[i]);
    }
    bool flg = 0; int pre = -1 , cnt = 0;
    for(int i = 1 ; i <= N ; ++i){
        if(pre < arr[i]) ++cnt;
        else cnt = 1;
        pre = arr[i];
        if(cnt == K){flg = 1; --ans;}
    }
    cout << ans + flg; return 0;
}

C

sol

$\begin{align*} \sum\limits_{i=1}^N \sum\limits_{j=i+1}^N lcm(A_i,A_j) & = \sum\limits_{i=1}^N \sum\limits_{j=i+1}^N \frac{A_iA_j}{gcd(A_i,A_j)} \\ & = \sum\limits_{d = 1}^{maxA} \frac{1}{d} \sum\limits_{d|A_i} \sum\limits_{d|A_j} A_iA_j[gcd(A_i,A_j)=d] \\ &= \sum\limits_{d = 1}^{maxA} \frac{1}{d} \sum\limits_{d|A_i} \sum\limits_{d|A_j} A_iA_j \sum\limits_{p | \frac{A_i}{d} , p | \frac{A_j}{d}} \mu(p) \\ &= \sum\limits_{p=1}^{maxA} \mu(p) \sum\limits_{d=1}^{\frac{maxA}{p}} \frac{1}{d} \sum\limits_{dp|A_i} \sum\limits_{dp|A_j} A_iA_j \\ &= \sum\limits_{T=1}^{maxA} \sum\limits_{p | T} \mu(p) \frac{p}{T} \sum\limits_{T|A_i} \sum\limits_{T|A_j} A_iA_j \end{align*}$

先对于每个$T$预处理$\sum\limits_{p | T} \mu(p) \frac{p}{T}$，然后注意到$\sum\limits_{T|A_i} \sum\limits_{T|A_j} A_iA_j = \frac{(\sum\limits_{T | A_i} A_i)^2 - \sum\limits_{T | A_i}A_i^2}{2}$，对于每一个$T$枚举倍数算出$\sum\limits_{T | A_i} A_i$和$\sum\limits_{T | A_i}A_i^2$即可。

复杂度可以做到$O(maxA\ log\ maxA)$，但是很呆的我后面一部分写的是枚举约数……

AGC038

原文：https://www.cnblogs.com/Itst/p/11568311.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)