学大伟业 国庆Day2

期望得分:30+100+0=130

实际得分:30+100+20=150

忍者钩爪

(ninja.pas/c/cpp)

【问题描述】

小Q是一名酷爱钩爪的忍者,最喜欢飞檐走壁的感觉,有一天小Q发现一个练习使用钩爪的好地方,决定在这里大显身手。

场景的天花板可以被描述为一个无穷长的数轴,初始小Q挂在原点上。数轴上有N个坐标为整数的圆环供小Q实现钩爪移动。具体操作为:小Q可以将钩爪挂到圆环上,进而荡到关于圆环坐标轴对称的位置。例如小Q在3,圆环在7,则小Q可以通过该圆环移动到11。

现在一个问题难倒了小Q,如何判断自己能否到达某个整点呢?

【输入格式】

第一行两个整数N,M,表示圆环的数量和询问组数

接下来一行共N个整数描述每个圆环的坐标(可重复)

接下来M行每行包含一个整数描述询问

【输出格式】

共M行对应M个询问,若小Q能移动到目标点,输出Yes,否则输出No

题解(不是我的,所以有问题不要问我): 

对于30%的分数

可以使用暴力记忆化搜索得出答案。即维护每个坐标是否可达,继而进行搜索。

对于60%的分数

通过观察可知设当前坐标为x,则通过坐标为a的圆环可移动到2a-x处。连续通过两个圆环(a,b)可以移动到x+(2b-2a)处。

先以移动步数为偶数情况考虑简化版问题:设圆环坐标为a[1]~a[n],对于任意两个圆环,可由坐标x变为x+2(a[j]-a[i]),题目转化为对于N^2个数其中b[i,j]=2(a[j]-a[i]),通过有限次加减运算能否由x=0变化至目标。

根据广义裴蜀定理以及扩展欧几里得相关原理可知,当且仅当目标为gcd的倍数时有解。故预处理出全部可能的2(a[j]-a[i]),求出其最大公约数,在判断目标是否为gcd的倍数即可。

对于奇数的情况,可以通过枚举第一步的方案转化为偶数的情况,即维护一个set表示0步或1步可达点集(mod gcd意义下),再查询目标点在mod gcd下是否属于这个集合即可。复杂度瓶颈在于N^2个数求gcd。

对于100%的分数

通过欧几里得算法的性质与更相减损术可知gcd(a,b)=gcd(a-b,b)。设p1={2*(a[i]-a[1])|i>1}的最大公约数,设p2={2*(a[i]-a[j])}的最大公约数,易知p1>=p2(因为p1比p2约束宽松)。而对于任意i,j由于p1同时是2*(a[i]-a[1])、2*(a[j]-a[1])的约束,那么p1也一定是任意2*(a[i]-a[1])-2*(a[j]-a[1])=2*(a[i]-a[j])的约数,故p1<=p2。综上所述p1=p2,这样就不需要N^2个数同时求gcd了,只求p1即可,可获得满分。

#include<set>
#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;

#define N 100001

LL a[N];

set<LL>S;

void read(LL &x)
{
    x=0; int f=1; char c=getchar();
    while(!isdigit(c))  { if(c=='-') f=-1;  c=getchar(); }
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
    x*=f;
}

LL getgcd(LL i,LL j) { return !j ? i : getgcd(j,i%j); }

int main()
{
    freopen("ninja.in","r",stdin);
    freopen("ninja.out","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) read(a[i]);
    LL gcd=0;
    for(int i=2;i<=n;i++) gcd=getgcd(abs(a[i]-a[1]<<1),gcd);
    LL x;
    if(gcd)
    {
        S.insert(0);
        for(int i=1;i<=n;i++) S.insert((2*a[i]%gcd+gcd)%gcd);
        while(m--)
        {
            read(x);
            puts(S.find((x%gcd+gcd)%gcd)!=S.end() ? "Yes" : "No");
        }
    }
    else
    {
        while(m--)
        {
            read(x);
            puts(x==a[1]*2 ? "Yes" : "No");
        }
    }
}

 30暴力

#include<cstdio>
#include<algorithm>

using namespace std;

int tmp[11];

int n,a[100001];

bool ok[20005];

void judge()
{
    int cnt1=0,cnt2=0;
    for(int i=1;i<=n;i++)
        if(tmp[i]==1) cnt1++;
        else if(tmp[i]==-1) cnt2++;
    if(cnt1==cnt2 || cnt1==cnt2+1)
    {
        int t=0;
        for(int i=1;i<=n;i++) t+=tmp[i]*a[i];
        ok[t]=true;
    }
}

void dfs(int now)
{
    if(now==n+1) 
    {
        judge();
        return;
    }
    tmp[now]=0; dfs(now+1);
    tmp[now]=1; dfs(now+1);
    tmp[now]=-1; dfs(now+1);
}

int main()
{
    freopen("ninja.in","r",stdin);
    freopen("ninja.out","w",stdout);
    int m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)  scanf("%d",&a[i]);
    int x;
    if(n<=10)
    {
        dfs(1);
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&x);
            if(x&1) puts("No");
            else puts(ok[x>>1] ? "Yes" : "No");
        }
    }
    else
    {
        sort(a+1,a+n+1);
        long long maxn=0,minn; int mid=n/2;
        if(mid==n*2)
        {
            for(int i=1;i<=mid;i++) maxn+=a[mid+i]-a[i];
        }
        else
        {
            for(int i=1;i<=mid;i++) maxn+=a[mid+i+1]-a[i];
            maxn+=a[mid+1];
        }
        minn=-maxn;
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&x);
            if(x&1) puts("Yes");
            else if(x>maxn || x<minn) puts("No");
            else puts("Yes");
        }
    }
}

线段树

先下放取反标记,在下方加标记

下放取反标记时,若存在加标记,加标记也取反

关键是如何处理加标记的影响

设当前线段树区间有4个数x1,x2,x3,x4

sum[i] 表示 选出i个数的乘积 的和

sum[1]=x1+x2+x3+x4

sum[2]=x1x2+x1x3+x1x4+x2x3+x2x4+x3x4

sum[3]=x1x2x3+x1x2x4+x1x3x4+x2x3x4

sum[4]=x1x2x3x4

操作:区间加a

以sum[3]为例

新的sum[3]=

(x1+a)(x2+a)(x3+a) +

(x1+a)(x2+a)(x4+a) +

(x1+a)(x3+a)(x4+a) +

(x2+a)(x3+a)(x4+a)

=x1x2x3+a(x1x2+x1x3+x2x3)+a^2(x1+x2+x3)+a^3 + 

  x1x2x4+a(x1x2+x1x4+x2x4)+a^2(x1+x2+x4)+a^3 + 

  x1x3x4+a(x1x3+x1x4+x3x4)+a^2(x1+x3+x4)+a^3 + 

  x2x3x4+a(x2x3+x2x4+x3x4)+a^2(x2+x3+x4)+a^3 

=sum[3] + a*sum[2]*2 + a^2*sum[1]*3 + a^4

所以 对有siz个元素的区间执行区间加a操作

那么sum[]的更新:

for  i: 10 ——> 1

    for  j:i-1——>1

      sum[i]+=a^(i-j)*sum[j]*C(siz-j,i-j)

解释:

有i个(xi+a)相乘

从里面选出j个xi,那就只能选i-j个a

后面那个组合数?

一共有siz个(xi+a) ,已经确定了有j个(xi+a)选择xi

一共要选i个(xi+a),那就要从剩下的siz-j个(xi+a)里选出 i-j个(xi+a)来用他们的a

所以是C(siz-j,i-j)

区间的合并

枚举左边选j个,那右边就选i-j个,乘起来就行了

例:

假设当前要选3个数

左边有2个数x1,x2  选1个,

右边有3个数x3,x4,x5  选2个

那就是 x1*x3*x4+x1*x3*x5+x1*x4*x5+x2*x3*x4+x2*x3*x5+x2*x4*x5

=x1*右边的sum[2]+x2*右边的sum[2]

=左边的sum[1] * 右边的sum[2]

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

#define N 50001

const int mod=1e9+7;

typedef long long LL;

int n;

int C[N][11];

int f[N<<2];
int siz[N<<2],mid[N<<2];
bool rev[N<<2];

struct node { int sum[11]; }ans[N<<2];

void read(int &x)
{
    x=0; int ff=1; char c=getchar();
    while(!isdigit(c)) { if(c=='-') ff=-1; c=getchar(); }
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
    x*=ff; 
}

int tot=0;

void MOD(int &a,int b)
{
    a+=b;
    a-= a>=mod ? mod : 0;
}

void pre(int n)
{
    C[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        C[i][0]=1;
        for(int j=1;j<=min(i,10);j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    }
}

void update(int k)
{
    for(int i=1;i<=10;i++)
    {
        ans[k].sum[i]=0;
        for(int j=1;j<i;j++) MOD(ans[k].sum[i],1ll*ans[k<<1].sum[j]*ans[k<<1|1].sum[i-j]%mod);
        MOD(ans[k].sum[i],ans[k<<1].sum[i]); MOD(ans[k].sum[i],ans[k<<1|1].sum[i]); 
    }
}

void build(int k,int l,int r)
{
    siz[k]=r-l+1;
    if(l==r) { read(ans[k].sum[1]); MOD(ans[k].sum[1],0); return; }
    mid[k]=l+r>>1;
    build(k<<1,l,mid[k]); build(k<<1|1,mid[k]+1,r);
    update(k);
}

void insert(int k,int w)
{
    MOD(f[k],w);
    for(int i=10;i;i--)
    {
        int x=w;
        for(int j=i-1;j;j--,x=1ll*x*w%mod)
            MOD(ans[k].sum[i],1ll*x*ans[k].sum[j]%mod*C[siz[k]-j][i-j]%mod);
        MOD(ans[k].sum[i],1ll*x*C[siz[k]][i]%mod);
    }
}

void turn(int k)
{
    rev[k]^=1;
    if(f[k]) f[k]=mod-f[k];
    for(int i=9;i>0;i-=2) 
        if(ans[k].sum[i]) ans[k].sum[i]=mod-ans[k].sum[i];
}

void down(int k)
{
    if(rev[k]) turn(k<<1),turn(k<<1|1),rev[k]=0;
    if(f[k]) insert(k<<1,f[k]),insert(k<<1|1,f[k]),f[k]=0;
}

void add(int k,int l,int r,int opl,int opr,int w)
{
    if(l>=opl && r<=opr) { insert(k,w); return; }
    down(k);
    if(opl<=mid[k]) add(k<<1,l,mid[k],opl,opr,w);
    if(opr>mid[k]) add(k<<1|1,mid[k]+1,r,opl,opr,w);
    update(k);
}

void reverse(int k,int l,int r,int opl,int opr)
{
    if(l>=opl && r<=opr)  { turn(k); return; }
    down(k);
    if(opl<=mid[k]) reverse(k<<1,l,mid[k],opl,opr);
    if(opr>mid[k]) reverse(k<<1|1,mid[k]+1,r,opl,opr);
    update(k);
}

node query(int k,int l,int r,int opl,int opr,int w)
{
    if(l>=opl && r<=opr) return ans[k];
    down(k);
    if(opr<=mid[k]) return query(k<<1,l,mid[k],opl,opr,w);
    else if(opl>mid[k]) return query(k<<1|1,mid[k]+1,r,opl,opr,w);
    else 
    {
        node L=query(k<<1,l,mid[k],opl,opr,w),R=query(k<<1|1,mid[k]+1,r,opl,opr,w);
        node tmp;
        for(int i=1;i<=w;i++)
        {
            tmp.sum[i]=(L.sum[i]+R.sum[i])%mod;
            for(int j=1;j<i;j++) MOD(tmp.sum[i],1ll*L.sum[j]*R.sum[i-j]%mod);
        }
        return tmp;
    }
}

int main()
{
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    int n,m; 
    read(n); read(m);
    pre(n);
    build(1,1,n);
    int ty,l,r,w;
    while(m--)
    {
        read(ty); read(l); read(r);
        if(ty==1)
        {
            read(w); w%=mod;
            w+= w<0 ? mod : 0;
            add(1,1,n,l,r,w);
        }
        else if(ty==2) reverse(1,1,n,l,r);
        else
        {
            read(w);
            node p=query(1,1,n,l,r,w);
            printf("%d\n",query(1,1,n,l,r,w).sum[w]);
        }
    }
}

GG

20分暴力

#include<cstdio>
#include<cmath>

using namespace std;

int n,N,d;

double a[17][17],b[177150];

int ty[17],tmp[11],bit[11];

double ans;

void init()
{
    scanf("%d%d",&n,&N);
    for(int i=1;i<=n;i++) 
        for(int j=1;j<=n;j++)
            scanf("%lf",&a[i][j]);
    scanf("%d",&d);
    for(int i=1;i<=n;i++) scanf("%d",&ty[i]);
}

void add(double may)
{
    int t=0;
    for(int i=1;i<=N;i++) t+=tmp[i]*bit[i-1];
    b[t]+=may;
}

void dfs(int tim,int now,double may)
{
    if(tim==N+1) { add(may); return; }
    for(int i=1;i<=n;i++)
    {
        tmp[tim]=ty[i];
        dfs(tim+1,i,may*a[now][i]);
    }
}

int main()
{
    freopen("walk.in","r",stdin);
    freopen("walk.out","w",stdout);
    init();
    tmp[1]=ty[1]; 
    bit[0]=1; for(int i=1;i<=N;i++) bit[i]=bit[i-1]*3;
    dfs(2,1,1.0);
    int tot=pow(3,N);
    for(int i=0;i<tot;i++) ans+=b[i]*b[i];
    printf("%.9lf",ans);
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏锦小年的博客

复杂网络(2)--图论的基本理论-最小生成树问题

连通且不含圈的无向图称为树(tree)。树中度为1的节点称为树叶,度大于1的节点称为分支点。 若图G=(V,E)的生成子图是一棵树,则称该树为图G的生成树(...

3696
来自专栏深度学习自然语言处理

基于attention的seq2seq机器翻译实践详解

理理思路 文本处理,这里我是以eng_fra的文本为例,每行是english[tab]french,以tab键分割。获取文本,清洗。 分别建立字典,一个engl...

5646
来自专栏专知

【Keras教程】用Encoder-Decoder模型自动撰写文本摘要

【导读】这篇博文介绍了如何在深度学习框架Keras上实现文本摘要问题,探讨了如何使用编码器-解码器递归神经网络体系结构来解决文本摘要问题,如何实现文本摘要问题的...

9535
来自专栏Vamei实验室

Python标准库12 数学与随机数 (math包,random包)

我们已经在Python运算中看到Python最基本的数学运算功能。此外,math包补充了更多的函数。当然,如果想要更加高级的数学功能,可以考虑选择标准库之外的n...

2438
来自专栏机器学习算法原理与实践

用scikit-learn学习K-Means聚类

    在K-Means聚类算法原理中,我们对K-Means的原理做了总结,本文我们就来讨论用scikit-learn来学习K-Means聚类。重点讲述如何选择...

831
来自专栏计算机视觉life

SLIC超像素分割详解(二):关键代码分析

SLIC超像素分割详解(二) 网站http://ivrl.epfl.ch/research/superpixels给出了SLIC的代码。对于其中C++代码的几个...

2697
来自专栏程序员叨叨叨

8.4 CG 标准函数库

和 C 的标准函数库类似,Cg 提供了一系列内建的标准函数。这些函数用于执行数学上的通用计算或通用算法(纹理映射等),例如,需要求取入射光线的反射光线方向向量可...

2815
来自专栏灯塔大数据

每周学点大数据 | No.7大数据规模的算法分析

No.7期 大数据规模的算法分析 Mr. 王:这样的时间界限记为O(1),我们称之为常数时间算法,这样的算法一般来说是最快的,因为它与输入规模完全无关,不论输...

2074
来自专栏转载gongluck的CSDN博客

bmp图像大小biSizeImage算法公式由来

LPBITMAPINFOHEADER lpbmiHeader; // ... 计算BMP方法 法一:lpbmiHeader->biSizeImage = (cx...

5035
来自专栏悦思悦读

分类模型的评价指标:Precision,Recall和Accuracy

既然要判断程度,就必然会用到能够描述“多少”的数值型指标。今天我们就要介绍几种分类模型最常用的评价指标。

1734

扫码关注云+社区

领取腾讯云代金券