内容纲要
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;
}