文档章节

2020年牛客算法入门课练习赛3 (A bfs B 容斥 C 线段树+主席树 D 暴力最短路 E 思维构造 )

o
 osc_icwhzig7
发布于 07/01 16:10
字数 2239
阅读 13
收藏 0

精选30+云产品,助力企业轻松上云!>>>

昨晚 div3 A 出了 最后一题,只有100左右人 A 的题有点兴奋 玩到2点,中午没睡着,傍晚吃了一颗维生素C(助睡眠)睡了20分钟,扛着迷迷糊糊的大脑来打这场。然后就没打好,四个题都会写,就是A题找bug浪费n久。导致赛时2题,赛后半小时又两题 

A-胖胖的牛牛

做法:经典bfs水题了。不会的去面壁,萌新除外

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

inline ll read()
{
	ll x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}
const int N=1e2+10;
char s[N][N];
int n;
ll vis[N][N];
int si,sj,ei,ej;
struct node
{
    int x,y;
    ll w;
    int id;
    bool operator <(const node &o)const
    {
        return w>o.w;
    }
};
int dir[4][2]={1,0,0,1,-1,0,0,-1};
void bfs()
{
    priority_queue<node>que;
    rep(i,1,n) rep(j,1,n) vis[i][j]=1e9;vis[si][sj]=0;

    que.push({si,sj,0,-1});
    while(que.size())
    {
        node now=que.top();que.pop();

        //printf("x:%d y:%d w:%d id:%d\n",now.x,now.y,now.w,now.id);

        if(now.x==ei&&now.y==ej){printf("%lld\n",now.w);return ;}

        for(int i=0;i<4;++i){
            int x=now.x+dir[i][0];
            int y=now.y+dir[i][1];
            if(x<1||y<1||x>n||y>n||s[x][y]=='x') continue;
            if(now.id==-1||i==now.id){
                if(vis[x][y]>=now.w){
                    vis[x][y]=now.w;
                    que.push({x,y,vis[x][y],i});
                }
            }
            else{
                int w=1;
                if(abs(now.id-i)==2) w=2;

                if(vis[x][y]>=now.w+w){
                    vis[x][y]=now.w+w;
                    que.push({x,y,vis[x][y],i});
                }
            }
        }

    }
    puts("-1");
}
int main()
{
    cin>>n;
    rep(i,1,n) rep(j,1,n) {
        cin>>s[i][j];
        if(s[i][j]=='A') si=i,sj=j;
        if(s[i][j]=='B') ei=i,ej=j;
    }

    if(si==0||sj==0||ei==0||ej==0){puts("-1");return 0;}

    bfs();
//    rep(i,1,n) {
//        rep(j,1,n) printf("%d ",vis[i][j]);
//        puts("");
//    }
}
/*
6
A . x x x x
. . . . . x
x . x x . x
x . . x x x
x x . . . x
x x x x B x
*/

 

B-牛牛的零食

做法:数据: n只有15,容斥一下,区间内 被8整除的个数 减去 被8整除同时被其他某个数整除的数 加上.....(奇加偶减)

由于数很大,计算多个数的LCM时需要运用唯一分解的 分解素数的方法 保存素数最大次幂

#pragma GCC optimize(2)
#include<bits/stdc++.h>

#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll powmod(ll a,ll b) {
    ll res=1;
    for(;b;b>>=1){
        if(b&1)res=res*a;
        a=a*a;
    }
    return res;
}
inline ll read()
{
	ll x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}
const int N=20;
ll a[N],l,r,f[N];
int n,len;

vector<pair<ll,ll> >num[N];

ll run(ll v)
{
    //v=v/8;

    ll ans=0;
    for(int i=1;i<=len;++i){//m枚举状态
        ll res=1;
        int num1=0;
        map<ll,ll>mp;
        for(int j=0;j<n;++j){//枚举点
            if(i&f[j]){
                for(auto it:num[j]) mp[it.first]=max(mp[it.first],it.second);
                num1++;
            }
        }

        int flag=1;
        for(auto it:mp){
            res=res*powmod(it.first,it.second);
            if(res>v) {
                flag=0;
                break;
            }
        }

        if(!flag) continue;
        //printf("v:%lld i:%d res:%lld\n",v,i,res);
        ll gc=gcd(res,8);
        res=res*8/gc;
        //res=res/gc;
        if(num1%2) ans+=v/res;
        else ans-=v/res;
    }
    return ans;
}
int main()
{
    n=read();
    rep(i,0,n-1) a[i]=read();

    f[0]=1;rep(i,1,n+1) f[i]=f[i-1]*2;
    rep(i,0,n-1)
    {
        ll tmp=a[i];
        for(int j=2;j*j<=tmp;++j){
            if(tmp%j==0){
                int res=0;
                while(tmp%j==0) res++,tmp=tmp/j;
                num[i].push_back({j,res});
            }
        }
        if(tmp!=1) num[i].push_back({tmp,1});

    }


    l=read(),r=read();
    len=(1<<n)-1;

    ll ans = r / 8 - (l - 1) / 8 - ( run(r) - run(l-1) );

    printf("%lld\n",ans);
}

C-牛牛的最美味和最不美味的零食

做法:eat部分不能暴力去写,这里用主席树维护每个位置是否有数,然后对2 操作的l r  查询下区间内第l 大   第r大的位置即可。

得到新的l、r即可。最大值就用普通线段树就可以了。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair<int, int>
#define mk make_pair
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
inline ll read()
{
	ll x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}
const int N=1e6+10,inf=1e9+10;
int sum[4*N],mx[4*N],mi[4*N],n,m;
void build(int id,int l,int r)
{
    if(l==r){
        scanf("%d",&mx[id]);
        mi[id]=mx[id];
        sum[id]=1;
        return ;
    }
    int mid=l+r>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    mx[id]=max(mx[id<<1],mx[id<<1|1]);
    mi[id]=min(mi[id<<1],mi[id<<1|1]);
    sum[id]=sum[id<<1]+sum[id<<1|1];
}
void up(int id,int l,int r,int pos)
{
    if(l==r){
        mx[id]=-inf,mi[id]=inf;sum[id]=0;
        return ;
    }
    int mid=l+r>>1;
    if(pos<=mid) up(id<<1,l,mid,pos);
    else up(id<<1|1,mid+1,r,pos);
    mx[id]=max(mx[id<<1],mx[id<<1|1]);
    mi[id]=min(mi[id<<1],mi[id<<1|1]);
    sum[id]=sum[id<<1]+sum[id<<1|1];
}
int qu1(int id,int l,int r,int k)
{
    if(l==r) return l;

    int ans=0;
    int mid=l+r>>1;
    if(sum[id<<1]>=k) return qu1(id<<1,l,mid,k);
    return qu1(id<<1|1,mid+1,r,k-sum[id<<1]);
}


void qu2(int id,int l,int r,int ql,int qr,int &ans1,int &ans2)
{

    if(ql<=l&&r<=qr){
        ans1=max(ans1,mx[id]);
        ans2=min(ans2,mi[id]);
        return ;
    }
    int mid=l+r>>1;
    if(ql<=mid) qu2(id<<1,l,mid,ql,qr,ans1,ans2);
    if(qr>mid) qu2(id<<1|1,mid+1,r,ql,qr,ans1,ans2);
}
int main()
{
    n=read(),m=read();
    build(1,1,n);
    while(m--)
    {
        int ty=read();
        if(ty==1){

            int k=read();
            int s=qu1(1,1,n,k);
            up(1,1,n,s);
        }
        else{
            int l=read(),r=read();
            l=qu1(1,1,n,l);
            r=qu1(1,1,n,r);

            int ans1=-inf,ans2=1e9;
            qu2(1,1,n,l,r,ans1,ans2);
            printf("%d %d\n",ans2,ans1);
        }
    }
}

D-瘦了的牛牛去旅游

数据n<=50

做法:由于n很小,考虑计算两个点内所有长度的距离。设dp[cnt][i][j] 为i点到j点  距离为cnt的最短路。

那么floyd 不仅要枚举中间节点k  还要枚举i到k的之间的距离l  进而得出k到j的中间距离 cnt-l

跑一边5层for循环即可。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair<int, int>
#define mk make_pair
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
inline ll read()
{
	ll x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}
const int N=52,inf=0x3f3f3f3f;

int dp[N][N][N];
int vis[N][N],n,m;
double ans[N][N];

int main()
{
	n=read();m=read();
	memset(dp,inf,sizeof(dp));
	rep(i,1,m){
        int u=read(),v=read(), w=read();
        vis[u][v]=1;
        dp[1][u][v]=min(dp[1][u][v],w);
	}

	for(int cnt=2;cnt<=n;++cnt){
        //printf("cnt:%d\n",cnt);
        for(int k=1;k<=n;++k){

            for(int i=1;i<=n;++i){
                if(!vis[i][k]) continue;
                for(int j=1;j<=n;++j){
                    
                    if(!vis[k][j]) continue;
                
                    vis[i][j]=1;
                    for(int l=0;l<=cnt;++l){
                        if(dp[l][i][k]>=inf||dp[cnt-l][k][j]>=inf) continue;
                        dp[cnt][i][j]=min(dp[cnt][i][j],dp[l][i][k]+dp[cnt-l][k][j]);
                    }
                    //puts("****");

                }


            }
        }
	}
	for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (i==j) continue;
            if (!vis[i][j]) ans[i][j]=-1;
            else {
                double res=1e18;
                for (int k=1; k<=n; k++) {
                    res=min(res,dp[k][i][j]*1.0/k);
                }
                ans[i][j]=res;
            }
        }
    }



	int q=read();
	while(q--)
    {
        int u=read(),v=read();
        if (!vis[u][v]) printf("OMG!\n");
        else printf("%.3f\n",ans[u][v]);
    }
}

 

 

E-只能吃土豆的牛牛

做法:一定是前i个数进行 2^i -1 次方案数是前 (2^i)-1 小的。于是我们遍历找到第一个大于k的位置

答案加上 这个位置 的前面那个3^(i-1)  然后方案数k 减去2^(i-1) 继续 递归从前往后找 第一个大于k得位置即可。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair<int, int>
#define mk make_pair
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
inline ll read()
{
	ll x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}
const int N=33;
const ll MAX=1ll<<32;
ll f[N],ans,val[N];
void init()
{
    f[0]=1;
    val[0]=1;
    for(int i=1;i<N;++i) {
        f[i]=f[i-1]*2;
        val[i]=val[i-1]*3;
    }

}
ll dfs(int id,ll k)
{
    ll ans=0;
    if(id<=0||k<=0) return 0;
    for(int i=0;i<id;++i){
        if(f[i]>k){
            ans+=val[i-1];
            ans+=dfs(i,k-f[i-1]);
            break;
        }
    }
    return ans;
}
int main()
{
	init();
	int cas=0;
	int _=read();while(_--)
	{
	    ll k=read();
	    ans=dfs(33,k);
	    printf("Case #%d: %lld\n",++cas,ans);
	}
}

 

o
粉丝 0
博文 59
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
2020年牛客算法入门课练习赛3 (A bfs B 容斥 C 线段树+主席树 D 暴力最短路 E 思维构造 )

昨晚 div3 A 出了 最后一题,只有100左右人 A 的题有点兴奋 玩到2点,中午没睡着,傍晚吃了一颗维生素C(助睡眠)睡了20分钟,扛着迷迷糊糊的大脑来打这场。然后就没打好,四个题都会写,就是...

ccsu_deer
06/30
0
0
嘤嘤嘤多校训练记录

[TOC] 嘤嘤嘤多校训练记录 国庆大腿的博客 yiqzq大腿的博客 牛客多校第一场 题号 标题 状态 题解 tag A Equivalent Prefixes 通过 ppq 国庆腿子 二分+分治/单调栈 B Integration 通过 ppq 公...

osc_fdgnewj9
2019/07/23
4
0
重走长征路---OI每周刷题记录——hzwer

重走长征路---OI每周刷题记录——hzwer OI每周刷题记录——hzwer 原文地址http://hzwer.com/410.html 2015年6月15日 6月15日 2015 详见https://blog.csdn.net/mrcrack/article/details/87157...

mrcrack
04/01
0
0
台州学院maximum cow训练记录

前队名太过晦气,故启用最大牛 我们的组队大概就是18年初,组队阵容是17级生詹志龙、陶源和16级的黄睿博。 三人大学前均无接触过此类竞赛,队伍十分年轻。我可能是我们队最菜的,我只是知道的...

osc_61miqbdb
2018/09/02
7
0
刷题

<h2>6月15日</h2><p class="title">Codeforces Round #158 (Div. 2)</p><p>A.模拟</p><p>B.map</p><p>C.map</p><p>D.构造</p><p>E.线段树</p><p class="title">Croc Champ 2013 – Round 2<......

osc_02vmpq90
2019/02/06
3
0

没有更多内容

加载失败,请刷新页面

加载更多

Kafka如何在千万级别时优化JVM GC问题?

大家都知道Kafka是一个高吞吐的消息队列,是大数据场景首选的消息队列,这种场景就意味着发送单位时间消息的量会特别的大,那既然如此巨大的数据量,kafka是如何支撑起如此庞大的数据量的分发...

hummerstudio
06/18
0
0
我打赌!90%程序员都破解不了这个粽子,不信你试!

放假了 各位读者朋友们,马上就是端午小长假啦,开心激动有木有? 新的故事文章还在创作中,写了初稿感觉不太满意又推倒重来。其实写故事还是挺难的,读者可能第一次第二次有新鲜感,写多了就...

轩辕之风
06/24
0
0
如何删库跑路?教你使用Binlog日志恢复误删的MySQL数据

前言 “删库跑路”是程序员经常谈起的话题,今天,我就要教大家如何删!库!跑!路! 开个玩笑,今天文章的主题是如何使用Mysql内置的Binlog日志对误删的数据进行恢复,读完本文,你能够了解...

后端技术漫谈
01/14
13
0
PHP设计模式之代理模式

PHP设计模式之代理模式 代理人这个职业在中国有另外一个称呼,房产经济人、保险经济人,其实这个职业在国外都是叫做房产代理或者保险代理。顾名思义,就是由他们来帮我们处理这些对我们大部分...

硬核项目经理
2019/09/23
5
0
Redis的复制模式

Redis的复制功能分为同步(sync)和命令传播(command propagate)两个操作。 同步 同步操作用于将从服务器的数据库状态更新至主服务器当前所处的数据库状态。 1. 旧版本的执行步骤 从服务器...

osc_s9cni3go
9分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部