首页 > 其他分享 >Google Kick Start 2022 --Round C

Google Kick Start 2022 --Round C

时间:2022-10-13 23:12:03浏览次数:60  
标签:子串 平方 Google -- sum Start int 遍历 数组

Countdown

题意

给一个长为n的数组,一个数k,求数组中有多少个子串组成k,k-1,k-2....2,1

思路

扫一遍记录当前期望的值就行了。

代码

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int T,cas=0;
    scanf("%d",&T);
    while(T--)
    {
        int n,k,x,cur,res=0;
        scanf("%d%d",&n,&k);
        cur=k;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&x);
            if(x!=cur)cur=k;
            if(x!=cur)continue;
            else if(x==1)res++,cur=k;
            else cur=cur-1;
        }
        printf("Case #%d: %d\n",++cas,res);
    }
}

Stable Wall

题意

给若干(不多于26)块由1*1方块组成的异形砖块,然后拼成一个矩阵,当作墙,如果存在一种按顺序把每一块砖拼上去,使得拼的过程中每一块底部都有支撑,那么认为这堵墙是稳定的,否则不稳定。现在给出这个矩阵,由字母代表砖块的形状,求是否稳定。

思路

拓扑排序,遍历矩阵寻找不同砖块之间的依赖关系。再注意细节的处理就好了

代码

#include<bits/stdc++.h>

using namespace std;

char s[50][50];
vector<int> G[30];
vector<int> res;
int in[30];
bool vis[30],vis1[30];

void topo(int s)
{
    queue<int> Q;
    Q.push(s);
    vis[s]=1;
    res.push_back(s);
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        for(int i=0; i<G[u].size(); i++)
        {
            int v=G[u][i];
            if(!vis[v]&&(!--in[v]))
            {
                Q.push(v);
                vis[v]=1;
                res.push_back(v);
            }
        }
    }
}

int main()
{
    int T,cas=0;
    scanf("%d",&T);
    while(T--)
    {
        int r,c,n=0;
        scanf("%d%d",&r,&c);
        for(int i=0;i<30;i++)
            G[i].clear();
        res.clear();
        memset(vis,0,sizeof vis);
        memset(vis1,0,sizeof vis1);
        memset(in,0,sizeof in);
        for(int i=0;i<r;i++)
        {
            scanf("%s",s[i]);
            for(int j=0;j<c;j++)
            {
                int u=s[i][j]-'A';
                if(!vis1[u])n++;
                vis1[u]=1;
            }
        }
        for(int i=0;i<r-1;i++)
            for(int j=0;j<c;j++)
                if(s[i][j]!=s[i+1][j])
                {
                    int u=s[i+1][j]-'A',v=s[i][j]-'A';
                    if(u==v)continue;
                    G[u].push_back(v);
                }
        for(int i=0;i<26;i++)
        {
            sort(G[i].begin(),G[i].end());
            G[i].erase(unique(G[i].begin(),G[i].end()),G[i].end());
            for(int j=0;j<G[i].size();j++)
                in[G[i][j]]++;
        }
        for(int i=0;i<26;i++)
            if(!in[i]&&vis1[i]&&!vis[i])
                topo(i);
        printf("Case #%d: ",++cas);
        if(res.size()!=n)
            printf("-1\n");
        else
        {
            for(int i=0;i<res.size();i++)
            printf("%c",res[i]+'A');
            printf("\n");
        }
    }
}

Perfect Subarray

题意

给一个长为n的数组,元素在[-100,100]范围内,求数组有多少子串满足子串之和是一个完全平方数(0,1,4,9,16....

思路

考虑从左到右遍历数组,然后考虑以当前i结尾的子串有多少完全平方数。最暴力的想法,每遍历到一位i,可以枚举前面每一位j,判断寻找j-i是否是完全平方数。

但是这样时间复杂度为O(n^2),显示不能接受。想到额外条件,数组元素范围只有100,那么可以想到,子串之和带来的完全平方数不会很大,即使全部取最大值100,那么最大的完全平方数也只有1e7大小,也就是说子串和为完全平方数的可能的取值最多3100多种。

那么可以想到每遍历到一位i,遍历所有可能的完全平方数取值,然后对于每一个可能的完全平方数取值q,统计有多少j,使得j-isumq

可以用前缀和优化快速统计j,记当前1-i的和为tot,现在要使得j-i的和为q,那么就等价于1-j的和为tot-q,那么只需要统计有多少j,j<i,使得1-j的和为tot-q

正好可以在遍历过程中用哈希表t[s]记录前缀和为s的前缀和的个数。对于每一位i,可以先统计答案,再用当前的值更新哈希表。这样就可以保证j<i

代码

#include<bits/stdc++.h>

using namespace std;

const int MAX=1e5+5;

int a[MAX];

unordered_map<int,int>mp;

int main()
{
    int T,cas=0;
    scanf("%d",&T);
    while(T--)
    {
        mp.clear();
        int n,sum=0,maxx=-200;
        long long res=0;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]),maxx=max(maxx,a[i]);
        int m=sqrt(maxx*n)+5;
        mp[0]=1;
        int minn=0;
        for(int i=0;i<n;i++)
        {
            sum+=a[i];
            for(int j=0;j<m;j++)
            {
                int s=j*j;
                if(sum-s<minn)break;
                res+=mp[sum-s];
            }
            mp[sum]++;
            minn=min(minn,sum);
        }
        printf("Case #%d: ",++cas);
        printf("%lld\n",res);
    }
}

Candies

题意

给长为n的数组aq个询问,每个询问要不更改某一位的值,要不求l-r区间的sum

sum定义如下:

\[sum=\sum_{i=l}^r(-1)^{i-l}a[i] \]

最后求所有查询的sum的和

思路

很典型的线段树风格的题目。修改很简单,区间sum需要考虑一下。直接拿官方题解的图。

img

整体的阶梯是1-nsum,可以看到5-8的答案是蓝色部分,是包含在1-nsum当中的。

先按1-nsum计算方法建一棵树T1,再正负交替建立一棵树T0,以5-8为例,查询的答案就是T1[5-8]-T0[5-8]*4,那么只需要维护T0 T1两棵线段树就可以了

代码

#include<bits/stdc++.h>

using namespace std;

const int MAX=2e5+5;

struct data
{
    long long sum;
}tree[2][MAX<<2];//0 for -1^i;  1 for -1^i*i
int a[MAX];

void pushup(int rt)
{
    int ls=rt<<1,rs=rt<<1|1;
    tree[0][rt].sum=tree[0][ls].sum+tree[0][rs].sum;
    tree[1][rt].sum=tree[1][ls].sum+tree[1][rs].sum;
}

void build(int l,int r,int rt)
{
    if(l==r)
    {
        int factor=l&1?1:-1;
        tree[1][rt].sum=1ll*a[l]*factor*l;
        tree[0][rt].sum=1ll*a[l]*factor;
        return ;
    }
    int m=(l+r)>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    pushup(rt);
}

void update_point(int P,int C,int l,int r,int rt)
{
    if(l==r)
    {
        int factor=l&1?1:-1;
        tree[1][rt].sum=1ll*C*factor*l;
        tree[0][rt].sum=1ll*C*factor;
        return ;
    }
    int m=(l+r)>>1;
    if(P<=m)
        update_point(P,C,l,m,rt<<1);
    else
        update_point(P,C,m+1,r,rt<<1|1);
    pushup(rt);
}

long long query(int L,int R,int l,int r,int rt,int treenum)
{
    if(L<=l&&r<=R)
    {
        return tree[treenum][rt].sum;
    }
    long long ans=0;
    int m=(l+r)>>1;
    if(L<=m)
        ans+=query(L,R,l,m,rt<<1,treenum);
    if(R>m)
        ans+=query(L,R,m+1,r,rt<<1|1,treenum);
    return ans;
}

int main()
{
    int T,cas=0;
    scanf("%d",&T);
    while(T--)
    {
        int n,q;
        long long sum=0;
        char s[5];
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        build(1,n,1);
        while(q--)
        {
            int x,y;
            scanf("%s%d%d",s,&x,&y);
            if(s[0]=='Q')
            {
                long long cur=0;
                cur=query(x,y,1,n,1,1);
                cur-=query(x,y,1,n,1,0)*(x-1);
                if(x%2==0)cur*=-1;
                sum+=cur;
            }
            if(s[0]=='U')
                update_point(x,y,1,n,1);
        }
        printf("Case #%d: %lld\n",++cas,sum);
    }
}

标签:子串,平方,Google,--,sum,Start,int,遍历,数组
From: https://www.cnblogs.com/cryingrain/p/16790065.html

相关文章

  • CSharp: null object pattern in donet core 3
     ///<summary>///空对象模式nullobjectpattern///geovin,GeovinDueidt///</summary>interfaceIVehicle{voidTrave......
  • elasticsearch聚合查询之排序
    排序默认只能按两个字段排序:_count和_key 如果想按二次聚合结果中的字段排序语法如下: GEThow2java/product/_search//求每个地方商品数量,并按平均价格从高往低排......
  • java基础
    基础补漏:JVM模型:https://blog.csdn.net/qq_36704549/article/details/109390566(1)jvm是一种用于计算设备的规范,它是一个虚构出来的机器,是通过在实际的计算机上仿真模拟各......
  • 实验4:开源控制器实践——OpenDaylight
    一、实验目的1.能够独立完成OpenDaylight控制器的安装配置;2.能够使用Postman工具调用OpenDaylightAPI接口下发流表。二、实验环境Ubuntu20.04Desktopamd64三、实......
  • 《git学习笔记》
    git简介Linus花了两周时间自己用C语言写了一个分布式版本控制系统。安装gitLinux可以尝试输入git,看看系统有没有安装Git,如果没有安装,又碰巧用Debian或UbuntuLinux,通......
  • 派生类中扩展属性
    对于在父类中存在的属性,如果要在其派生类中继续扩展属性可以这样实现1classValley:2def__init__(self):3self._name=None45@pro......
  • 实验1
    #include<stdio.h>intmain(){printf("0\n");printf("<H>\n");printf("II\n");printf("0\n");printf("<H>\n");printf("II\n");}......
  • 1961: 硬币组合
      这道题目是一道经典的DP:讲一下思路:f[i]:指i元可以用最少多少张钞票凑齐,凑不齐的话值为-1先将f数组初始化为无穷大(因为后面有min操作所以不能用-1)输入的同时将f[a......
  • 二分法/三元表达式
    算法简介1.什么是算法?算法就是帮助我们解决问题的有效方法,例如我们自己想去哪里,我们的脑子就自动开始思考,路程怎么样,先去哪里再去哪里,这就是我们人脑的计算。2.实际算法......
  • js分时问候案例
    分时问候案例<div>上午好!</div><script>//获取事件vardiv=document.querySelector('div');//绑定事件,执行程序//判断时间......