文章/答案/技术大牛

发布

社区首页 >专栏 >单次比赛参与人数能超过 1000 人的 ECNU Online Judge 月赛真的值得参加吗？

单次比赛参与人数能超过 1000 人的 ECNU Online Judge 月赛真的值得参加吗？

ACM算法日常

发布于 2021-11-26 02:55:14

95000

代码可运行

文章被收录于专栏：ACM算法日常ACM算法日常

运行总次数：0

代码可运行

EOJ (ECNU Online Judge) 是由华东师范大学程序设计竞赛队员自主开发并维护的在线程序评测系统，该系统已拥有 14 年的历史，是国内最早的一批 OJ。目前已被广泛地用于我校的作业提交、考试、竞赛训练和各类校赛的举办。

为了推动我校和各兄弟院校在程序设计竞赛上的训练，我们于 2017 年 12 月推出了月赛。至今，EOJ 已经成功连续举办几十场月赛，即将到达四周年。最初，所有月赛的题目都是我校现役队员利用业余时间精心设计和准备的，其中不乏有交互题、构造题等在国内还不太常见的题型。现在我们联合了华师大二附中一起参与出题，同时开始开设 IOI 赛制的月赛，开始面向高中信息学竞赛学生提供竞赛训练和交流的平台。

EOJ 内置了一套积分系统，月赛的排名会对用户的积分产生影响，并在网站上汇总出一个不断更新的总排名。按照积分分段，在 EOJ 上的用户名的颜色也会不同，从高到低有红名、橙名、紫名、蓝名、绿名等等。

在 EOJ 上做月赛，你不仅能和红名的大神同场竞技，还能看到自己的积分变化曲线，看到自己的进步历程。你也许现在只能做一道题，但要相信，经过持之以恒的训练，你也能和大牛们一样，站到排行榜的最顶端。

在 ECNU Online Judge 注册即可获得每月月赛邮件通知。

同时，因为最近 EOJ Monthly 比赛获得了图森未来的全程赞助，所以比赛中排名优越的同学也将获得精美的奖品

我在19-20的两年内作为月赛的负责人，组织和贡献了不少题目。

为了让大家更好的感受比赛，今天我们来看一套 2019年7月的月赛题目。

比赛链接

https://acm.ecnu.edu.cn/contest/191/

题目贡献人及算法分布

#	Tag	Idea	Developer	Tester
A	线性基高斯消元	cs2017 Xiejiadong	Xiejiadong	Weaver_zhu
B	简单数学贪心	Xiejiadong	Xiejiadong	Kilo_5723 oxx1108
C	数学尺取法	blunt_axe	Weaver_zhu Kilo_5723	Kilo_5723 oxx1108
D	送分签到	Xiejiadong	Xiejiadong	Kilo_5723
E	树形DP	kblack	kblack	Xiejiadong

Problem A

考虑素因数分解。如果几个数乘起来是一个完全平方数，则其各个素因子幂次都是偶数。

一个区间

$(l, r)$

任意取数乘起来得到完全平方数则等价于，一些表示素因子幂次奇偶性的二进制串异或起来是否为

$0$

。于是可以考虑使用线性基解决问题。

对于本问题，如果答案为

$ans$

，则需要求出最大的

$ans$

使得

$(ans+1, n-1)$

任意取数异或上

$n$

的二进制串为

$0$

( 因为

$n$

是必须取得 )。

考虑线性基的部分，

$10^6$

以内的素数个数是

$10^5$

数量级的，我们需要

$O(10^5)$

长度的二进制串吗？实际上，

$1000$

以内的素数不超过

$200$

个，而

$1000$

以上的素因子，最多只有一个。

于是我们的线性基只是需要

$10^5$

左右数量的

$200$

位二进制串外加一个整数 ( 表示

$1000$

以上的素数 )。

加入一个数的时间复杂度是

$O(200)$

的，我们从大到小检测每次加入一个数后，是否有新的

$n$

的素因子在线性基中可以被取到。

这样枚举每个

$ans \in [1, n]$

是

$\mathcal{O}(200)$

的。如果用

$bitset$

实现二进制串，空间也是足够的。

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int C = 1005;
int d[1000010];
int pid[1000010];
int m, smallCount;
bool have[100010];
ull g[100010][3],a[3],b[3];
int aBig,bBig;
int bIt;

void init()
{
    m=0;smallCount=0;aBig=0;bBig=0;bIt=0;
    memset(d,0,sizeof(d));
    memset(pid,0,sizeof(pid));
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(g,0,sizeof(g));
    memset(have,0,sizeof(have));
}

void precalc()
{
 for (int x=2;x<1000003;x++)
 {
  if (x==C) smallCount=m;
  if (d[x]!=0) continue;
  pid[x]=m++;
  for (int y=x;y<1000003;y+=x)
   if (d[y]==0) d[y]=x;
 }
 return;
}

void Set(ull* A,int p)
{
 A[p>>6]^=(ull)1<<(p&63);
}
bool get(ull* A, int p)
{
 return (A[p>>6]>>(p&63))&1;
}
void getPrimes(int x)
{
 for (int i=0;i<3;i++)
  a[i]=0;
 aBig=-1;
 while(x>1)
 {
  if (d[x]>=C)
  {
   aBig=pid[d[x]];
   x/=d[x];
   continue;
  }
  int y=d[x];
  int t=0;
  while(x%y==0) x/=y,t^=1;
  if (t) Set(a, pid[y]);
 }
 return;
}

bool moveIter()
{
 if (bBig!=-1)
 {
  if (!have[bBig]) return false;
  for (int i=0;i<3;i++)
   b[i]^=g[bBig][i];
  bBig=-1;
 }
 while(bIt>=0)
 {
  if (!get(b,bIt))
  {
   bIt--;
   continue;
  }
  if (!have[bIt]) return false;
  for (int i=0;i<3;i++)
   b[i]^=g[bIt][i];
  bIt--;
 }
 return true;
}

void solve(int x)
{
 getPrimes(x);
 if (aBig!=-1)
 {
  if (!have[aBig])
  {
   have[aBig]=1;
   for (int i=0;i<3;i++)
    g[aBig][i]=a[i];
   return;
  }
  for (int i=0;i<3;i++)
   a[i]^=g[aBig][i];
  aBig=-1;
 }
 for (int it=smallCount-1;it>=0;it--)
 {
  if (!get(a,it)) continue;
  if (!have[it])
  {
   have[it]=1;
   for (int i=0;i<3;i++)
    g[it][i]=a[i];
   return;
  }
  for (int i=0;i<3;i++)
   a[i]^=g[it][i];
 }
 return;
}
char sw[100];
int main()
{
 precalc();
 int y;
 scanf("%d",&y);
 if (d[y]==y)
 {
  printf("-1\n");
  return 0;;
 }
 getPrimes(y);
 for (int i=0;i<3;i++)
  b[i]=a[i];
 bBig=aBig;
 bIt=smallCount-1;
 int x=y;
 while(true)
 {
  if (moveIter()) {printf("%d\n", x);return 0;}
  x--;
  solve(x);
 }
 return 0;
}

Problem B

考虑如果有小朋友在

$x$

天来了图书馆。

可能他是每间隔

$x-1$

天来一次图书馆，于是所有日期为

$y$

且满足

$y-1\equiv 0(mod\; x-1)$

的日期都可以由他产生，故不再考虑这些天；

如果他不是每间隔

$x-1$

天来一次图书馆，那么他的间隔只能更小，假设他的间隔为

$a$

，一定有

$a|(x-1)$

，这样一来，他一定在第

$a+1$

天的时候来了图书馆，那个时候我们已经可以知道不用再对

$x$

天考虑了，所以不可能存在这样的情况。

于是，我们只需要从小到大依次考虑没有被标记过（不用再考虑）的天数，并从标记他所能取消的天数就可以了。

这样有两种方式维护，一种是对每个天数判断他的约数是否已经存在，时间复杂度

$\mathcal{O}(n\sqrt{n})$

；

也可以用类似于筛法求质数那样做，时间复杂度

$\mathcal{O}(nlogn)$

。

可能需要特判

$n=1$

的情况。

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

char sw[100];
int n,a[200010],v[200010];

bool check(int x)
{
 for (int i=1;i<=(int)sqrt((double)x);i++)
 {
  if (x%i==0&&v[i]) return true;
  if (x%i==0&&v[x/i]) return true;
 }
 return false;
}
 
int main(){   
  scanf("%d",&n);
  if (n==1) {puts("1");return 0;}
  for (int i=1;i<=n;i++)
   scanf("%d",&a[i]);
  memset(v,0,sizeof(v));
  int ans=0;
  for (int i=2;i<=n;i++)
   if (!check(a[i]-1)) ans++,v[a[i]-1]=1;
  cout<<ans<<endl;
}

Problem C

解法1

首先进行初步的分析。不难发现可以将「星星会在时刻

$a_i + k \times b_i (k \in N)$

闪烁」的条件替换成「星星会在时刻

$(a_i \bmod b_i) + k \times b_i (k \in N)$

闪烁」，这不影响答案。这是因为如果在时刻

$x$

选中的星星都会闪烁，那么在时刻

$x + 10^9 \times \text{lcm}(b_1, b_2, \cdots, b_n)$

它们也都会闪烁。这样，我们就可以预先把输入进来的

$a_i$

全部对

$b_i$

取模。

然后发现这个题目本质是询问一个区间的线性同余方程组是否有解。也就是询问：

$\begin {cases} x \equiv a_1 \pmod {b_1} \\ x \equiv a_2 \pmod {b_2} \\ \cdots \\ x \equiv a_n \pmod {b_n} \end {cases}$

是否有解。

注意到不能直接使用 ExCRT 的方法计算答案，因为答案可能很大。但是这题只需要我们判断方程组是否有解，所以无需算出答案。

可以证明：一个线性同余方程组有解当且仅当其中的任意两个方程形成的方程组都有解。原因是一个线性同余方程组的所有解一定可以写成满足「

$x \equiv r_1 \pmod {p_1^{k_1}}, x \equiv r_2 \pmod {p_2^{k_2}}, \cdots$

（

$p$

是素数）」这样一组的条件的任何数。如果一个方程组没有解，那么一定存在「

$x \equiv r_1 \pmod {p_1^{k_1}}$

，并且

$x \equiv r_2 \pmod {p_1^{k_1}},$

，其中

$r_1 \neq r_2$

」这两个限制。而对于这两个限制，一定能找到两个方程，它们分别包含了两个限制的信息。也就是说，如果线性同余方程组无解，那么一定存在两个方程，它们组成的方程组无解。换句话说，如果任意两个方程形成的方程组都有解，则整个方程组一定有解。

我们暴力枚举每两个方程，判断它们是否矛盾即可。使用裴蜀定理即可证明它们不矛盾当且仅当

$\gcd(b_1, b_2)$

整除

$a_1 - a_2$

。时间复杂度

$\mathcal{O}(n + qn^2 \log b_i)$

。

考虑优化算法。看到了

$\gcd$

以后容易想到枚举因数。枚举因数

$d$

，考虑所有

$b_i$

是

$d$

倍数的星星。如果所有

$a_i \bmod d$

都相同的话，就没有矛盾。这样一次的复杂度是

$\mathcal{O}(b_i \log b_i)$

的，但是由于我们只需要枚举

$d$

是素数或素数的几次方的情况，复杂度可以降为

$\mathcal{O}(b_i \log \log b_i)$

。于是总共的时间复杂度减少到

$\mathcal{O}(q(n + b_i \log \log b_i))$

。

之前的算法似乎没什么前途，考虑换一种思路。

对于每组限制

$(a_i, b_i)$

，我们将

$b_i$

素因数分解：

$b_i = \prod_{j} p_j^{k_j}$

。然后，对于每一个

$p_j^{k_j}$

，将其拆成

$k_j$

个限制，模数分别等于

$p_j, p_j^2, \cdots, p_j^{k_j}$

，余数等于

$a_i$

对它们取模的结果。对于一组

$(a_i, b_i)$

，我们最多会将其拆成

$\log b_i$

组限制。实现素因数分解时可以使用线性筛。

拆分后的好处是什么呢？发现如果两个方程矛盾，那么从它们中一定可以各自选出一个限制，满足限制的模数相同，但余数不同。

这样我们就把问题转化成了：给定

$\mathcal{O}(n \log n)$

组有序数对

$(a_i, b_i)$

，每次询问一个区间内是否存在

$b_i$

相同且

$a_i$

不同的一组数对。

不难发现对于每一个点

$i$

，一定存在一点

$p_i$

使得以

$i$

为右端点的区间

$[l, i]$

中所有

$l \ge p_i$

的答案都为 Yes，而

$l < p_i$

的区间答案都为 No。考虑用 2 - pointers 预处理出

$p_i$

。由于具体过程叙述起来较为复杂，请读者自行思考，也可以参考标程。

时间复杂度

$\mathcal{O}(n \log b_i + b_i)$

。

解法2

尝试维护一个集合，保证其中所有星星都能同时闪烁。考虑何种情况下集合满足这个性质。

我们发现，对每一个质数

$p$

，对所有的

$i$

使得

$p \mid b_i$

，需要让每一个

$a_i \; {\rm mod }\; p^{k_i}$

互不冲突，其中

$p^{k_i}\mid b_i,p^{k_i+1}\nmid b_i$

。而不冲突的定义为：令最大的

$p^{k_x}=P$

，对应的

$a_x \; {\rm mod }\; P = MOD$

，则对所有的

$i$

都有

$a_i \; {\rm mod }\; p^{k_i} = MOD \; {\rm mod }\; p^{k_i}$

。

利用这个性质，滑动窗口维护对每一个

$l$

，最大的

$r$

使得

$[l,r]$

中的星星能同时闪烁。

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
const int maxn=1e6+5,maxm=1e7+5,maxp=7e5+5;
struct num{
 int mod,cnt;
 num(int _m=0,int _c=0){
  mod=_m; cnt=_c;
 }
};
int prime[maxp],mindiv[maxm],nextp[maxm],id[maxm],siz;
int divs[maxn][10],mods[maxn][10],sizs[maxn];
int ans[maxn];
map<int,num> stat[maxp];
void init(){
    int i,j;
    int a,b;
    siz=0;
    for (i=1;i<maxm;i++) mindiv[i]=i;
    for (i=2;i<maxm;i++){
        if (i==mindiv[i]){
   id[i]=siz;
   prime[siz++]=i;
        }
        for (j=0;j<siz&&prime[j]<=mindiv[i]&&i*prime[j]<maxm;j++)
            mindiv[i*prime[j]]=prime[j];
    }
    for (i=2;i<maxm;i++){
        a=mindiv[i]; b=i/a;
        nextp[i]=(b%a)?b:nextp[b];
    }
}
void make(int div[],int mod[],int &siz,int pos,int val){
    siz=0;
    while (pos!=1){
        div[siz]=pos/nextp[pos];
        mod[siz]=val%div[siz];
        siz++;
        pos=nextp[pos];
    }
}
bool violate(int div[],int mod[],int siz){
    int i;
    int diva,divb,moda,modb;
    map<int,num>::iterator it;
    for (i=0;i<siz;i++){
  while (stat[id[mindiv[div[i]]]].size()){
   it=stat[id[mindiv[div[i]]]].end(); it--;
   if (it->second.cnt) break;
   stat[id[mindiv[div[i]]]].erase(it);
  }
  if (!stat[id[mindiv[div[i]]]].size()) continue;
  it=stat[id[mindiv[div[i]]]].end(); it--;
  diva=it->first; divb=div[i];
  moda=it->second.mod; modb=mod[i];
  if (diva<divb){
   swap(diva,divb); swap(moda,modb);
  }
  if (moda%divb!=modb) return true;
    }/*
        if (cnt[divs[pos][i]]&&mods[pos][i]!=val[divs[pos][i]])
            return true;*/
    return false;
}
void add(int div[],int mod[],int siz){
    int i;
    for (i=0;i<siz;i++){
     if (stat[id[mindiv[div[i]]]].find(div[i])!=stat[id[mindiv[div[i]]]].end())
   stat[id[mindiv[div[i]]]][div[i]].cnt++;
  else
   stat[id[mindiv[div[i]]]][div[i]]=num(mod[i],1);
    }
}
void del(int div[],int mod[],int siz){
    int i;
    for (i=0;i<siz;i++)
  stat[id[mindiv[div[i]]]][div[i]].cnt--;
}
int main(){
    // freopen("in.txt","r",stdin);
    // freopen("out2.txt","w",stdout);
    init();
    int i,n,q;
    int l,r,t;
    int x,y;
    scanf("%d",&n);
    for (i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        make(divs[i],mods[i],sizs[i],y,x);
    }
    l=1; r=1;
    while (l<=n){
        while (r<=n&&!violate(divs[r],mods[r],sizs[r])){
            add(divs[r],mods[r],sizs[r]);
            r++;
        }
        ans[l]=r-1;
        del(divs[l],mods[l],sizs[l]);
        l++;
    }
    scanf("%d",&q);
    for (i=0;i<q;i++){
        scanf("%d%d",&l,&r);
        puts(ans[l]>=r?"Yes":"No");
    }
    return 0;
}

Problem D

我们可以考虑以

$(0,0)$

格子作为原点建立坐标系。

于是子矩阵就相当于限制了变量

$x$

和

$y$

的范围，对角线变成了直线

$y=x$

和

$y=-x+(n-1)$

。

问题变成了求给定的范围内的整点个数。

需要注意矩阵边长为奇数的时候，矩阵正中央的格子会被重复计算。

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

LL n,q,a,b,c,d;
char sw[100];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>q;
    while(q--)
    {
        LL ans=0;
        cin>>a>>b>>c>>d;
        if (n%2==1)
        {
            if (a<=n/2&&c>=n/2&&b<=n/2&&d>=n/2)
            ans--;
        }
        LL l=max(a,b),r=min(c,d);
        ans+=max(0LL,r-l+1);
        b-=(n-1LL),d-=(n-1LL);
        b=-b,d=-d;
        l=max(d,a),r=min(b,c);
        ans+=max(0LL,r-l+1);
        cout<<ans<<endl;
    }
    return 0;
}

Problem E

状态无非分为两种：理论状态（所有门元器件正常的时候的输出）、实际状态。

于是我们令

$f[i][x][y](x=0/1 , y=0/1)$

表示门元器件

$i$

的理论输出为

$x$

，实际输出为

$y$

的方案数。

理论和实际状态都为

$0$

的是最好处理的，因为理论

$0$

的状态只能是所有的输入为

$1$

。

理论的状态为

$1$

，实际状态为

$0$

，那么对于理论状态只需要任意一个输入或者多个输入为

$0$

即可。这个处理起来会有点麻烦，但是我们可以通过输入为

$0$

或者

$1$

的状态减去输入全

$0$

的状态快速得到。

理论的状态为

$0$

，实际状态为

$1$

的情况和上一种情况类似的处理。

而对于最后一类状态，即理论和实际都为

$1$

的状态，我们通过所有的状态减去前面三个状态转移即可。

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

#define LL long long  

using namespace std;
  
inline char nc(){
    /* 
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
    */return getchar();
}
  
inline void read(int &x){
  char c=nc();int b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
  
inline void read(LL &x){
  char c=nc();LL b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
 
inline void read(char &x){
  for (x=nc();!(x=='('||x==')');x=nc());
}

inline int read(char *s)
{
    char c=nc();int len=1;
    for(;!(c=='('||c==')');c=nc()) if (c==EOF) return 0;
    for(;(c=='('||c==')');s[len++]=c,c=nc());
    s[len++]='\0';
    return len-2;
}
int wt,ss[19];
inline void print(int x){
    if (x<0) x=-x,putchar('-'); 
    if (!x) putchar(48); else {
    for (wt=0;x;ss[++wt]=x%10,x/=10);
    for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
    if (x<0) x=-x,putchar('-');
    if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}

const LL p=998244353;
int n,F[200010],f[200010],hang[200010],g[200010];
LL dp[200010][2][2];
vector<int> c[200010];

LL power(LL x,LL y)
{
    LL res=1;
    for (;y;y>>=1)
    {
        if (y&1) res=res*x%p;
        x=x*x%p;
    }
    return res;
}
 
void dfs(int x)
{
    if (c[x].size()==0)
    {
        if (F[x]==-1)
        {
            dp[x][0][0]=1;
            dp[x][1][1]=(power(2LL,hang[x])-1+p)%p;
            dp[x][0][1]=dp[x][1][0]=0;
        }
        else if (F[x]==1)
        {
            dp[x][0][1]=1;
            dp[x][1][1]=(power(2LL,hang[x])-1+p)%p;
            dp[x][0][0]=dp[x][1][0]=0;
        }
        else if (F[x]==0)
        {
            dp[x][0][0]=1;
            dp[x][1][0]=(power(2LL,hang[x])-1+p)%p;
            dp[x][1][1]=dp[x][0][1]=0;
        }
        return ;
    }
    for (int i=0;i<c[x].size();i++)
        dfs(c[x][i]);
    dp[x][0][0]=1;
    for (int i=0;i<c[x].size();i++)
        dp[x][0][0]=(dp[x][0][0]*dp[c[x][i]][1][1])%p;
    dp[x][0][1]=1;
    for (int i=0;i<c[x].size();i++)
        dp[x][0][1]=(dp[x][0][1]*(dp[c[x][i]][1][1]+dp[c[x][i]][1][0]))%p;
    dp[x][0][1]=(dp[x][0][1]+p-dp[x][0][0])%p;
    dp[x][1][0]=1;
    for (int i=0;i<c[x].size();i++)
        dp[x][1][0]=(dp[x][1][0]*(dp[c[x][i]][1][1]+dp[c[x][i]][0][1]))%p;
    dp[x][1][0]=(dp[x][1][0]+p-dp[x][0][0])%p;
    dp[x][1][1]=power(2LL,hang[x]);
    for (int i=0;i<c[x].size();i++)
        dp[x][1][1]=(dp[x][1][1]*(dp[c[x][i]][1][1]+dp[c[x][i]][0][1]+dp[c[x][i]][1][0]+dp[c[x][i]][0][0]))%p;
    dp[x][1][1]=(dp[x][1][1]+3*p-dp[x][1][0]-dp[x][0][1]-dp[x][0][0])%p;
    if (F[x]==0)
    {
        dp[x][1][0]=(dp[x][1][0]+dp[x][1][1])%p;dp[x][1][1]=0;
        dp[x][0][0]=(dp[x][0][0]+dp[x][0][1])%p;dp[x][0][1]=0;
    }
    else if (F[x]==1)
    {
        dp[x][1][1]=(dp[x][1][0]+dp[x][1][1])%p;dp[x][1][0]=0;
        dp[x][0][1]=(dp[x][0][0]+dp[x][0][1])%p;dp[x][0][0]=0;
    }
}
 
int main()
{
    read(n);
    int root;
    for (int i=1;i<=n;i++)
    {
        read(f[i]);read(g[i]);read(F[i]);
        if (f[i]==0) root=i;else c[f[i]].push_back(i);
    }
    for (int i=1;i<=n;i++)
        hang[i]=g[i]-c[i].size();
 dfs(root);
    LL res=(dp[root][0][0]+dp[root][1][1])%p;
    LL ans=(dp[root][0][0]+dp[root][1][1]+dp[root][0][1]+dp[root][1][0])%p;
    res=(res*power(ans,p-2))%p;
    print(res),puts("");
 return 0;
}