牛客算法周周练19 (A.推式子 B C.矩阵快速幂 D.模拟 E.BFS染色)

A.神秘钥匙

答案明显是 $\sum_{i=1}^ni*C_n^i$ (从n人找i人，并且i人都可以当队长)，但是，这个时间限制只能O(1)求值，因此，考虑怎么求和。推导过程： $\sum_{i=1}^niC_n^i=\sum_{i=1}^n{n!\over(n-i)!(i-1)!}=n\sum_{i=1}^n{(n-1)!\over(n-i)!(i-1)!}$
我们令j=i-1,则： $n\sum_{i=1}^n{(n-1)!\over(n-i)!(i-1)!}=n\sum_{j=0}^{n-1}{(n-1)!\over(n-j-1)!(j-1)!}=n\sum_{j=0}^{n-1}C_{n-1}^{j}=n2^{n-1}$

#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset> 
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
//#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}

template<typename T> void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int lcm(int a,int b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod 
    ll ans=1;
    while(n){
        if(n&1) ans=((ans%mod)*(a%mod))%mod;
        a=((a%mod)*(a%mod))%mod;
        n>>=1;
    }
    return ans%mod;
}
//==============================================================
ll n;


int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    //===========================================================
    read(n);
    write((n*ksm(2,n-1))%mod);
    //===========================================================
    return 0;
}

C.粉嘤花之恋

结论题，答案是f(n+2)-1,求的其实是前n项和，然后，把 $S_n$ 化为 $f_0$ 和 $f_1$ 表示就能看出规律了。求f(n+2)用矩阵快速幂。

#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset> 
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=998244353;
template<typename T>void write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}

template<typename T> void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int lcm(int a,int b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod 
    ll ans=1;
    while(n){
        if(n&1) ans=((ans%mod)*(a%mod))%mod;
        a=((a%mod)*(a%mod))%mod;
        n>>=1;
    }
    return ans%mod;
}
//==============================================================
#define int ll
ll n;
struct mat{
    int val[3][3];
    void cls(){
        memset(val,0,sizeof(val));
    }
    friend mat operator*(const mat&a,const mat&b){
        mat res;res.cls();
        rep(i,1,2){
            rep(j,1,2){
                rep(k,1,2){
                    res.val[i][j]=(res.val[i][j]+a.val[i][k]*b.val[k][j])%mod;
                }
            }
        }
        return res;
    }
};
ll solve(ll n){
    mat res;res.cls();
    rep(i,1,2) res.val[i][i]=1;
    mat base;base.cls();
    base.val[1][1]=base.val[1][2]=base.val[2][1]=1;
    while(n){
        if(n&1) res=res*base;
        base=base*base;
        n>>=1;
    }
    return res.val[1][1]%mod;
}

signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    //===========================================================
    read(n);
    write((solve(n+2)-1+mod)%mod);
    //===========================================================
    return 0;
}

D.神器大师泰兹瑞与威穆

模拟。需要注意的是，f操作的Find并不会导致超时，因为需要多个h操作之后才能抵消掉一个f操作，因此不会循环很多次的，比较难预料到的一个点。

#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset> 
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
//#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}

template<typename T> void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int lcm(int a,int b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod 
    ll ans=1;
    while(n){
        if(n&1) ans=((ans%mod)*(a%mod))%mod;
        a=((a%mod)*(a%mod))%mod;
        n>>=1;
    }
    return ans%mod;
}
//==============================================================
string s,t;
int p=0;
int mode=0;
int Find(char tar){
    rep(i,p+1,int(s.length())-1){
        if(s[i]==tar) return i;
    }
    return -1;
}
void solve(){
    rep(i,0,int(t.length())-1){
        //char opt;cin>>opt;
        if(mode==0){
            if(t[i]=='i') mode=1;
            else if(t[i]=='f'){
                i++;
                int pos=Find(t[i]);
                //cerr<<pos<<endl;
                if(~pos) p=pos;
            }
            else if(t[i]=='x'){
                s.erase(p,1);
            }
            else if(t[i]=='h'){
                if(p>0)p--;
            }
            else if(t[i]=='l'){
                if(p<s.length()-1) p++;
            }
        }
        else if(mode==1){
            if(t[i]=='e') mode=0;
            else {
                s.insert(p,1,t[i]);p++;
                //cerr<<p<<" "<<t[i]<<endl;
            }
        }
        //cerr<<s<<" "<<p<<endl;
    }
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    //===========================================================
    IOS
    cin>>s>>t;
    solve();
    cout<<s<<endl;  
    //===========================================================
    return 0;
}

地、颜色、魔法

其实就是从每个没有被"#"标记的边缘开始染色，然后统计没有被染色的数量就行了，复杂度O(n)。

#include <iostream>
#include <map>
#include <ctime>
#include <vector>
#include <climits>
#include <algorithm>
#include <random>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <bitset> 
#include <queue>
#define inf 0x3f3f3f3f
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define rep(i, a, n) for(register int i = a; i <= n; ++ i)
#define per(i, a, n) for(register int i = n; i >= a; -- i)
//#define ONLINE_JUDGE
using namespace std;
typedef long long ll;
const int mod=1e9+7;
template<typename T>void write(T x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}

template<typename T> void read(T &x)
{
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int lcm(int a,int b){return a/gcd(a,b)*b;};
ll ksm(ll a,ll n){//看是否要mod 
    ll ans=1;
    while(n){
        if(n&1) ans=((ans%mod)*(a%mod))%mod;
        a=((a%mod)*(a%mod))%mod;
        n>>=1;
    }
    return ans%mod;
}
//==============================================================
#define int ll
const int maxn=1e6+1.0;
int n,m;
string a[maxn];
#define pii pair<int,int>
queue<pii> que;
int dir[4][2]={1,0,0,1,-1,0,0,-1};
void bfs(int x,int y){
    a[x][y]='@';
    que.push(make_pair(x,y));
    while(!que.empty()){
        pii now=que.front();que.pop();
        for(int i=0;i<4;i++){
            int dx=now.first+dir[i][0],dy=now.second+dir[i][1];
            if(dx<=0||dy<=0||dx>n||dy>m||a[dx][dy]!='.') continue;
            a[dx][dy]='@';
            que.push(make_pair(dx,dy));
        }
    }
}
int solve(){
    //cerr<<"ok"<<endl;
    rep(i,1,n){
        if(a[i][1]=='.'){
          bfs(i,1);
        }
        if(a[i][m]=='.'){
            bfs(i,m);
        }
    }
    //cerr<<"ok"<<endl;
    rep(i,1,m){
        if(a[1][i]=='.'){
            bfs(1,i);
        }
        if(a[n][i]=='.'){
            bfs(n,i);
        }
    }
    //cerr<<"ok"<<endl;
    int ans=0;
    rep(i,1,n){
        //cerr<<a[i]<<endl;
        rep(j,1,m){
            if(a[i][j]=='@') ans++;
        }
        //cerr<<endl;
    }
    return n*m-ans;
}

signed main()
{
    IOS
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    //===========================================================
    cin>>n>>m;
    rep(i,1,n) cin>>a[i],a[i]=" "+a[i];
    cout<<solve()<<endl;
    //===========================================================
    return 0;
}

全部评论

推荐最新楼层

02-10 16:01

Stanford University 算法工程师

拿下，华为编译器技术岗！她是谁？-程莹莹

深夜，电脑屏幕映照着实验室的一角鼠标轻轻点开那封来自华为的邮件“录用通知”字样映入眼帘长久以来的紧张与疲惫仿佛瞬间消散这份来自华为中央软件院软件开发工程师的offer成为了人工智能与计算机学院毕业生近年来在华为技术岗的一次突破她本科在江南，硕士仍在江南近七年时光 深耕一个赛道她是谁？线索一：肯坐冷板凳，深耕编译器作为“土生土长”的江大人，她的求学之路沉稳又踏实。从本科踏入人工智能与计算机学院，到硕士阶段继续深耕，七年时光里，当同龄人纷纷涌向CV /LLM 模型研究等热门赛道时，她反而一头扎进了少有人问津的底层编译领域——这个聚焦底层技术的研究方向，没有捷径可走，全靠一行行代码的打磨、一次次实验...

点赞评论收藏

昨天 16:52

门头沟学院销售工程师

任何人都能向面试官证明你懂AI——不需要会代码版

水母我啊，完全是代码0基础文科生，但是作为25届在校招生在AI行业站住脚跟，在55开的转正率成功留用并定为高P级，做成一些项目取得一些成就赚到了预想之外的钱钱后，想为也许在焦虑迷茫的不懂技术的小伙伴分享一些经验~从业务的视角聊聊，我们在投递非技术岗的时候，有哪些面试技巧，以及企业想要的人才画像——叠甲：本人也是摸爬滚打的经验此篇文章绝非万能焚诀——AI产品、AI销售、AI运营...这些岗位都不要求你会写代码,但你必须真正理解AI是什么,能做什么,不能做什么面试官是怎么判断你懂不懂AI的？HR面也好，业务面也好，+1+2面都好，很少有人会问你什么是Transformer，而是会更多询问你绝对绕不...

查看3道真题和解析

点赞评论收藏

01-09 13:28

已编辑

深圳大学产品经理

寒假实习

昨天在实习公司面试其他公司被同事发现，然后被反馈给主管。要下班的时候谈话直接被开除 哈哈哈哈哈实习实习 深圳！！ 有没有推荐或者继任的产品 运营 供应链都可以！

牛客60887332...：你这考研不是成了反向考了吗

你开始找寒假实习了吗？

点赞评论收藏

01-16 22:31

赣南师范大学运营

0offer

一个面试也没，心累   

白火同学：1、简历可以浓缩成一页，简历简历先要“简”方便HR快速过滤出有效信息，再要“历”用有效信息突出个人的含金量。 2、教育背景少了入学时间～毕业时间，HR判断不出你是否为应届生。 3、如果你的平台账号效果还不错，可以把账号超链接或者用户名贴到对应位置，一是方便HR知道你是具体做了什么内容的运营，看到账号一目了然，二是口说无凭，账号为证，这更有说服力。

面试被问期望薪资时该如何...

点赞评论收藏