hgoi#20190519

muronglin
muronglin 2019年05月19日
  • 在其它设备中阅读本文章

T1- 求余问题

Abu Tahun 很喜欢回文。 一个数组若是回文的,那么它从前往后读和从后往前读都是一样的,比如数组{1},{1,1,1},{1,2,1},{1,3,2,3,1}都是回文数组,但是数组{11,3,5,11},{1,12}不是回文的。
Abu Tahun 有个包含 n 个整数的数组 A,他想让它变成回文的。他可以任意选择一个整数 m,然后让所有元素 Ai 变成 Ai mod m。 求最大的 m 的值。

解法

显然,需要满足

a[1]===an
a[2]===an-1
......

则一定有最大的 m 为gcd(a[1]-a[n],a[2]-a[n-1],......)

ac 代码

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int n,a[100010],ans=0;
int main()
{
    freopen("palindrome.in","r",stdin),freopen("palindrome.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n/2;i++)ans=gcd(ans,abs(a[i]-a[n-i+1]));
    if(ans)printf("%dn",ans);else puts("-1");
    return 0;
}

T2- 阶乘数组

你正在做“机器学习”研究,作为机器学习教育的一部分,你必须先学习组合数学。在老师给你讲了为什么组合数学里,到处会出现“阶乘!”后,你需要挑战下面这个问题:
给定一个数组 $ A = [A_1 , A_2 , ... , A_n] $ ,长度是 n,你需要完成 m 次操作,操作有 3 种:
1、给定闭区间 $ [l, r] $ ,为区间内的所有数增加 1
2、给定闭区间 $ [l, r] $ ,计算 $ \sum_{i=l}^r=A_i! \mod 10^9$
3、给位置 i 和数值 v,将第 i 个数变成 v

解法

因为是 mod 1e9,所以 40! mod 1e9 就是 0 了 显然是个线段树,标算是对于线段树上的每一个节点,存一个数组,cnt[i]表示这一区间 i 的数量有多少个 这个做法的复杂度就是40*nlogn,虽然能过,但是代码很长, 关键是我打炸了(大雾 还有一种做法,暴力维护,每次单点修是 logn,查询是 logn,区间修改暴力一下 有人会说:这不就 n 方了吗 所以需要优化,因为一个点最多进行 40 次区间修,所以维护一个标记,标记一个区间是否全部大于 40 然后复杂度是一样的,但是连懒标记都不用打唉,还能爆踩标算有木有捏 QAQ

ac 代码

#include<bits/stdc++.h>
#define mod 1000000000
#define ls (nw*2)
#define rs (nw*2+1)
#define mid ((l+r)>>1)
using namespace std;
int n,m,opt,x,y,g[40]={1},a[400010],t[400010],tag[400010];
void pushup(int nw){a[nw]=(a[ls]+a[rs])%mod,tag[nw]=tag[ls]&tag[rs];}
void build(int nw,int l,int r)
{
    if(l==r){scanf("%d",&t[nw]);if(t[nw]>=40)tag[nw]=1;else a[nw]=g[t[nw]];return;}
    build(ls,l,mid),build(rs,mid+1,r),pushup(nw);
}
void modify(int nw,int l,int r,int ql,int qr)
{
    if(tag[nw])return;
    if(l==r){t[nw]++;if(t[nw]>=40)a[nw]=0,tag[nw]=1;else a[nw]=g[t[nw]];return;}
    if(ql<=mid)modify(ls,l,mid,ql,qr);
    if(qr>mid)modify(rs,mid+1,r,ql,qr);
    pushup(nw);
}
void update(int nw,int l,int r,int q,int v)
{
    if(l==r){t[nw]=v;if(t[nw]>=40)a[nw]=0,tag[nw]=1;else a[nw]=g[t[nw]],tag[nw]=0;return;}
    if(q<=mid)update(ls,l,mid,q,v);else update(rs,mid+1,r,q,v);
    pushup(nw);
}
int query(int nw,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr)return a[nw];
    if(qr<=mid)return query(ls,l,mid,ql,qr);
    if(ql>mid)return query(rs,mid+1,r,ql,qr);
    return (query(ls,l,mid,ql,qr)+query(rs,mid+1,r,ql,qr))%mod;
}
int main()
{
    freopen("factorial.in","r",stdin),freopen("factorial.out","w",stdout);
    for(int i=1;i<=39;i++)g[i]=(1llg[i-1]i)%mod;
    scanf("%d%d",&n,&m),build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&opt,&x,&y);
        if(opt==1)modify(1,1,n,x,y); 
        if(opt==2)printf("%dn",query(1,1,n,x,y));
        if(opt==3)update(1,1,n,x,y);
    }
    return 0;
}

T3- 直角三角形

四个直角三角形(9,12,15),(12,16,20),(5,12,13),(12,35,37)较特殊的地方是它们的边长都是整数,而且其中一条直角边边长都是 12。可以证明,边长都是整数且其中一条直角边边长是 12 的直角三角形就这四个。 找到最小的整数 x,使得直角三角形的边长都为整数的情况下,包含直角边长为 x 的直角三角形个数恰好是 n 个。

解法

首先我们需要找到根据 x 求 n 的方法
$ x^2+y^2=z^2-> $
$ x^2=z^2-y^2-> $
$ x^2=(z+y)*(z-y)-> $
$ x^2=uv(u=z+y,v=z-y)-> $
$ z=(u+v)/2,y=(u-v)/2 $
所以每一对 $ (u,v) $ 只要满足 $ uv=x^2 $ 并且 $ u!=v $ 并且 $ u===v(mod\ 2) $ 就是一组解 具体的,对于 $ x=2^a*3^b*5^c*7^d*... $ ,方案数就是 $ [(2a-1)(2b+1)(2c+1)(2d+1)...-1]/2 $ 那知道 n 怎么求最小的 x 呢,考虑 dp,枚举每个质数的指数,然后转移时先不管特殊的 2

ac 代码

#include<bits/stdc++.h>
#define ll long long
#define lima 2000010
#define limb 10000000000000000
using namespace std;
void get(ll &x, ll y){if(x==0)x=y;else x=min(x,y);}
int n,q,prime[20]={14,2,3,5,7,11,13,17,19,23,29,31,33,37,41};
ll dp[lima],p=1,ans;
int main()
{
    freopen("triangle.in","r",stdin),freopen("triangle.out","w",stdout);
    dp[1]=1,scanf("%d",&n);
    for(int i=2;i<=prime[0];i++)for(int j=lima;j>=1;j--,p=1)
    {
        if(!dp[j])continue;
        for(int k=1;;k++)
        {
            p=1llpprime[i];
            if(1llj(k2+1)>lima||1lldp[j]*p>limb)break;
            get(dp[j(k2+1)],1lldp[j]p);
        }
    }
    while(n--)
    {
        scanf("%d",&q),q=q*2+1,ans=(dp[q]?dp[q]:limb+1);
        for(int k=1;;k++)
        {
            if((1ll<<k)>limb)break;
            if(q%(2*k-1))continue;
            if(dp[q/(2k-1)]&&1lldp[q/(2*k-1)]<limb/(1ll<<k))
                ans=min(ans,1lldp[q/(2k-1)]*(1ll<<k));
        }
        printf("%lldn",ans>limb?-1:ans);
    }
    return 0;
}