「FZOI」OI 周赛 #2 Div.2 – 题解

A - 维他柠檬茶

很傻逼，直接把所有剩余液体加起来，然后放入最大的和次大的杯子进行判断即可。

B - 毒瘤题

我们可以考虑从 $n \to 1$ 进行扫描，更新可以向左的最大距离。如果最大距离为 $0$ 时，则有人没看到毒瘤题，计入答案即可。

C - 笔记本等式

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;

const int MAXN=1000000+5;
const int MAXQ=100+5;

int n;
int cnt,cnta=1,cntb;

inline void Read(void);
inline void Work(void);

int main(void){
    Read();
    Work();
    return 0;
}

struct Node{
    bool flag;//符号， true -> '+', false -> '-'
    int val;//绝对值
    inline Node(void){
        flag=false,val=0;
        return;
    }
    inline Node(reg bool a,reg int b){
        flag=a,val=b;
        return;
    }
};

Node a[MAXQ];

inline void Read(void){
    n=-1;//其实并不需要这一行
    a[1]=Node(true,0);//第一个是正的，绝对值不确定。
    static char ch;
    reg int i=1;
    cin>>ch;//吞掉开头的 '?'
    do{
        cin>>ch;//读入数学符号 '+', '-', '='
        if(ch=='+')
            ++cnta,a[++i]=Node(true,0);//正
        else if(ch=='-')
            ++cntb,a[++i]=Node(false,0);//负
        else if(ch=='='){
            cin>>n;
            break;
        }
        cin>>ch;
    }while(n==-1);
    cnt=cnta+cntb;//cnt -> Q
    return;
}

inline void Work(void){
    reg int Max=cnta*n-cntb,Min=-cntb*n+cnta;
    //Max 为最大，Min 为最小
    if(n<Min||n>Max){//不在值域之内
        puts("Impossible");
        return;
    }
    for(reg int i=1;i<=cnt;++i)
        a[i].val=a[i].flag?n:1;
    reg int temp=(Max-n)/(n-1),t2=(Max-n)%(n-1);
    //彻底更改 temp 个，小幅度修改第 temp+1 的值
    for(reg int i=1;i<=temp;++i)
        if(a[i].val==n)
            a[i].val=1;
        else
            a[i].val=n;
    if(a[temp+1].val==n)
        a[temp+1].val-=t2;
    if(a[temp+1].val==1)
        a[temp+1].val+=t2;
    //输出
    puts("Possible");
    for(reg int i=1;i<=cnt;++i)
        if(i==1)
            printf("%d",a[i].val);
        else
            printf(" %c %d",a[i].flag?'+':'-',a[i].val);
    printf(" = %d\n",n);
    return;
}

D - 序列

很有意思的一题。无解的情况非常显然：当这$n$个的$\gcd$不为$1$时，那么无解。如果这个序列本身就有$k$个$1$，那么答案就是$n - k$。剩余情况，最优策略一定是：一段区间$[l, r]$中，把$al$不停向右合并找出一个$1$，然后再把这个$1$扩散到剩下的$n - 1$个数中。最终，我们把问题转换为找到最小的一段区间满足 $[l, r], \gcd{l \leq i \leq r}(a_i) = 1$。

正常的方式就是用 $\Theta(n^2)$ 的方式枚举并记录区间 $\gcd$，并更新答案取最小值。然而，我们发现这个问题有二分性：当右端点固定时，区间长度越大，$\gcd$ 为 $1$ 的可能性越大，且一定存在一个分界点，其右侧都为 $1$，其左侧都不为 $1$ 。我们要找出这个最小的区间长度，用二分答案的形式。

然而，我们需要一种方式快速算出区间的 $\gcd$。这个时候我们可以使用 ST 表来进行区间 $\gcd$ 的计算，然后配合上二分答案，答案就是 $n - 1 + len - 1$。时间复杂度为 $\Theta(n \log^2 n)$。

// QOJ2016.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5 + 200;

int n, st[20][MAX_N], ans = 0x3f3f3f3f;

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int query(int l, int r)
{
    int d = 0, pos = l;
    for (int i = 19; i >= 0; i--)
        if (pos + (1 << i) - 1 <= r)
            d = ((d == 0) ? st[i][pos] : gcd(d, st[i][pos])), pos += (1 << i);
    return d;
}

int main()
{
    scanf("%d", &n);
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &st[0][i]);
        if (st[0][i] == 1)
            cnt++;
    }
    if (cnt > 0)
        printf("%d\n", n - cnt), exit(0);
    int combo = st[0][1];
    for (int i = 2; i <= n; i++)
        combo = gcd(combo, st[0][i]);
    if (combo != 1)
        puts("-1"), exit(0);
    for (int i = 1; i < 20; i++)
        for (int j = 1; j + (1 << i) - 1 <= n; j++)
            st[i][j] = gcd(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
    for (int i = 1; i <= n; i++)
    {
        int l = 1, r = i - 1, res = -1;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (query(mid, i) != 1)
                r = mid - 1;
            else
                l = mid + 1, res = i - mid;
        }
        if (res != -1)
            ans = min(ans, res + n - 1);
    }
    printf("%d\n", ans);
    return 0;
}