no.1

周赛10. 隐藏字符串

思路

事实上等差数列是个幌子。因为一个等差数列可以被前两的元素唯一确定。因此，欲求被隐藏的最多的等差数列的字符串，只需要关注前两个字符即可~ 最终答案可能是由一个元素或者是两个元素更新而来。
设 s[i] 是第i个小写字符的出现次数 ， 那么
f[i][j] += s[i] , 表示以第j个小写字母结尾的，以第i个小写字母开始的，有且只有这两个字符的串的出现次数。
最终res =max(res , f[i][j] , s[k])

no.2

周赛12.环形数组

这是一个线段树的模板题。变形仅仅是将线段数轴首尾相连而已。
然后就是注意线段树代码的细节。

复习线段树

线段树维护核心的数据对象，Node，里面有左儿子，右儿子，有懒标记，有区间答案值。
线段树五大操作，PushUp,PushDown,Update,Query,Build

线段树模板代码如下，以本题为例

struct Node
{
    int l, r;
    LL dt, mn;  // 懒标记dt ,区间答案mn
}tr[N * 4];

void pushup(int u)
{
    tr[u].mn = min(tr[u << 1].mn, tr[u << 1 | 1].mn);  // 从下向上传递区间最小值
}

void pushdown(int u)
{
    auto &root = tr[u], &l = tr[u << 1], &r = tr[u << 1 | 1];
    l.dt += root.dt, l.mn += root.dt;
    r.dt += root.dt, r.mn += root.dt;
    root.dt = 0;  // 懒标记传给后代之后记得本懒标记清空
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, 0, w[l]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);  // 树刚刚建好就可以进行答案的查询了，这行代码千万别忘了
    }
}

void update(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r)  // 结点区间被完全覆盖，则更新结点区间
    {
        tr[u].dt += d, tr[u].mn += d;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) update(u << 1, l, r, d);
        if (r > mid) update(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

LL query(int u, int l, int r)  // 代码结构和update类似
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].mn;
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        LL res = INF;
        if (l <= mid ) res = query(u << 1, l, r);
        if (r > mid) res = min(res, query(u << 1 | 1, l, r));
        return res;
    }
}

no3

周赛15 最小的正整数

两个模板，复习一下~

gcd

LL gcd(LL a , LL b) 
{
    return b ? gcd(b,a%b) : a ;
}

LL lcm(LL a ,LL b) 
{
    return a / gcd(a,b) * b ; 
}

no4

周赛17 方格集数量

题不是个难题,通过公式推导即可。

公式为
对每行来说
$row = \sum_{i=1}^{n} 2^{\sum{0}} + 2^{m-\sum{0}} - 2 $
对每列来说
$col = \sum_{i=1}^{m} 2^{\sum{0}} + 2^{m-\sum{0}} - 2 - n $
$ans = row + col$ 为最终答案。

记录本题的目的是想记录一个教训。
当你使用LL的时候，务必使用printf输出，否则会有意想不到的后果。
如果代码涉及了LL的幂运算，请使用快速幂替代pow函数。
务必记住!!!

no5

周赛17 无线网络

很典型的双指针。他在一定程度上像leetcode的推多米诺那道题。也或许双指针都是这样吧~

feature :
给定一个数轴，数轴上有两组数字A,B。（已经在数轴上排列好）现求他们之间的关系。
比如，求某一个 B族的每一个数字，左边距离他最近的A族数字是谁。无需$n^2$的复杂度。用i枚举B族，j枚举A族，j无需后撤只需一直右移即可。

no6

周赛18 砍树

题目中描述，说尽可能切最多的边，形成的连通分量都有偶数个成员，又因为偶数个连通分量可以一直切分成两个节点的连通分量。换言之，切多少边可以使之变成都是两个节点的分量（此时切的边是最多的边）。

只需要枚举每一个结点的孩子总个数。如果孩子总个数是奇数，那么加上自己就是偶数，那么自己连向根节点的那个边就可以切掉。按照这个思路写一个dfs即可~

no7

周赛19 石子游戏

我万万没想到这道题可以通过巧妙的纯暴力（当然，还有个前缀和）来写。
原本我的解法是通过二分来得到最优阈值，然后while循环套住二分。可惜只能过一半多一些的数据。
代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;


const int N =  2e5+10 ;
int res  ;
int n , k ;
int a[N] ; 
int minv = 0x3f3f3f3f ,  maxv = -1 ;
bool check_final() 
{
    for(int i = 1 ; i <= n ; i ++ ) 
    {
        if(a[i] != minv ) return 0 ;
    }
    return 1 ;
}
bool check(int h) 
{
    int sum = 0 ;
    for(int i = 1 ; i <= n ;i ++ ) 
    {
        if(a[i] > h) 
        {
            sum += a[i] - h ;
        } 
        if(sum > k ) return 0 ;
    }
    return 1 ;

}

void update(int h) 
{
    for(int i = 1 ; i <= n ;i ++ ) 
    {
        if(a[i] > h) 
        {
            a[i] = h ;
        } 
    }
}

int main()
{
    cin >> n >> k ;

    for(int i = 1 ; i <= n ; i ++) 
    {
        scanf("%d",&a[i]) ;
        minv = min(minv , a[i]) ;
        maxv = max(maxv , a[i]) ;
    }
    maxv -- ;
    if(check_final()) 
    {
        cout << 0 << endl;
        return 0 ;
    }


    while (1)
    {
        int l = minv ;
        int r = maxv ; 
        while(l < r) 
        {
            int mid = l + r >> 1 ;
            if(check(mid)) r = mid;
            else  l = mid + 1 ;
        }
        res ++ ;
        update(l) ;// l 便是阈值 h
        if(l == minv) break ;
    }
    cout << res << endl;

    return 0 ;
}

可以由于数据偏小，可以通过巧妙的枚举来解决。
从最高的高度开始向下一个一个的枚举。每次高度只降低1。详见yxc代码。

no8

多路归并
周赛20 最小的和

代码不难，但是要学会从题目中识别出多路归并的模型。
有n个序列，用$O(n)$的时间复杂度求出前k小（大）项，即为多路归并的模型。
至于n个序列，往往是自己从题目的二次提炼。

for(int i =  0; i < sum ; i ++ ) 
{

    int t = 0 ;
    for(int j =  0 ; j < n ; j ++ ) 
    {
        if(c[j] > c[t] )
        {
            t = j ;
        }
    }
}

no9

高精度

题目简练，却很是经典~

在此记录一下加法的典型高精度框架

int t = 1 ;
for(int  i = k ; i < len ; i ++) 
{

    t += q[i] ;
    q[i] =  t % 2 ;
    t /= 2 ;
    if(!t) break ;
}
if(t) q[len++] = t ;

no10

最大公约数

知识点是欧拉函数

这道题目的推导比较巧妙，值得反复琢磨。
复习一下欧拉函数模板

LL phi(LL x) 
{
    LL res = x ;
    for(int i = 2 ; i <= x / i ; i ++) 
    {
        if(x % i == 0 ) 
        {
            res = res / i * (i-1) ;
            while(x % i == 0) x/= i ;
        }
    }
    if(x > 1) res = res / x * (x -1 ) ;
    return res ;
}