ZROI2018.7.27% 你赛

提高组模拟赛

题面

TIM20180727123640.png

A. 小 T 的 GCD

分两个问题求解

Task1

考虑到在你找到符合要求的序列后后,在其左右两边增加数字,并不会对结果有影响(多多益善)。所以直接计算整个序列的 gcd,判断是否为 1 即可。

Task2

  • lcm(a1..ar)=a1*a2*...*ar,即 a1..ar两两互质
  • 若直接求两两的 gcd,复杂度过高。
  • 由互质,想到分解质因数。如果两个数没有相同的质因子,则这两个数不互质。
  • 分解质因数?套用线性筛素数的结构,定义 f[],t[]t[i] 表示 i 的最小质因子,f[i]=i/t[i]。线性筛素数本质是被最小的质因子筛掉,借此可顺便处理 f[],t[]
  • 由此,可 O(logn) 查询一个数字的所有质因子(包括重复的,而且复杂度还不到 logn)。
  • 有了以上的准备,要找到符合要求的序列,怎么做?
    • 枚举起点终点?O(n^3logn),显然超时。
    • 枚举起点,然后每个起点用 O(n) 的复杂度边加边更新?O(n^2logn),照常超时。
    • 类似单调队列的思想,当前序列区间为 [l,r],则当 r++ 时,纳入了新的数字,则从 l 开始把所有与新数字冲突的数字从队尾踢掉;然后用现在的序列长度更新答案。复杂度 O(nlogbn).
      ```cpp

      include

      define N 100005

      define A 1000006

      using namespace std;
      int T,n,a[N],t1,t2;
      bool bp[A];
      int p[A],cnt;
      int f[A],t[A],times[A];
      void pri_db(int k){// 线筛质数
      bp[0]=bp[1]=1,t[1]=f[1]=1,cnt=0;
      for(int i=2;i<=k;i++){if(!bp[i])p[++cnt]=i,t[i]=i,f[i]=1;
      for(int j=1;j<=cnt;j++){int mul=i*p[j];
          if(mul>k)break;
          bp[mul]=1,f[mul]=i,t[mul]=p[j];
          if(i%p[j]==0)break;
      }
      
      }
      }
      void push(int k){while(k!=1)times[t[k]]++,k=f[k];}// 把 k 的质因子入队
      void pop(int k){while(k!=1)times[t[k]]—,k=f[k];}// 出队
      bool find(int k){// 查找是否有重复质因子
      while(k!=1){if(times[t[k]])return true;
      k=f[k];
      
      }
      return false;
      }
      int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main(){scanf(“%d”,&T);
pri_db(1000000);
for(int i_=1;i_<=T;i_++){scanf(“%d”,&n);
for(int i=1;i<=n;i++)scanf(“%d”,&a[i]);
//task1
int g=a[1];
for(int i=2;i<=n;i++)g=(gcd(a[i],g));
t1=(g==1?n:-1);
//task2
t2=-1;
int l=1,r=1;
memset(times,0,sizeof(times));
while(l<=n&&r<=n){while(find(a[r])){// 不停从队尾踢数
pop(a[l]);
l++;
}
push(a[r]);
t2=max(t2,r-l+1),++r;
}
if(t2==1)t2=-1;
printf(“Case %d: %d %d\n”,i_,t1,t2);
}
return 0;
}
```

B. 小 T 的序列

f[i,j,k] 前 i 个数,长度为 j,和为 k 的序列个数。
动态规划,边界 f[m,i,n]*i!(考虑序列的顺序),求和即可。
复杂度 O(m^4)

C. 小 T 的式子

f[i,j] 前 i 个数中,选出来的数 %k=j 的数。
f[2i,j]sum(f[i,j])


  转载请注明: Sshwy's Blog ZROI2018.7.27% 你赛

 上一篇
分块入门 分块入门
引言时隔很久过来填坑了。其实分块就是暴力,其本质仍是对维护信息的割裂与整合归一 线性分块在线性结构上维护信息,我们尝试用分块处理。这种分块将结构分割为连续的几段,在维护段内的信息再整合为要查询的信息。形式化地说,我们把长度为 的序
2018.10.01
下一篇 
ZROI2018.8.1 吴瑾昭的忠告 ZROI2018.8.1 吴瑾昭的忠告
ZROI2018.8.1 骗分赛 题面ABCD 来自吴奆奆的教诲 打 OI 赛,不是看你能 AC 多少道,而是看你能不挂多少道。 A. 说好的一起富起来呢贺爸你怎么不等我Subtask3只考虑一维,O(n) 求出最长的 O 段再乘上 m
2018.10.01
  目录