2021牛客暑期多校训练营1补题记录

Alice and Bob

#include<bits/stdc++.h>
using namespace std;
bool vis[5010][5010];
int main(){
    for(int i=0;i<=5000;i++){
        for(int j=0;j<=5000;j++){
            if(!vis[i][j]){
                for(int k=1;k+i<=5000;k++){
                    for(int q=0;q*k+j<=5000;q++){
                        vis[k+i][q*k+j]=1;
                    }
                }
                for(int k=1;k+j<=5000;k++){
                    for(int q=0;q*k+i<=5000;q++){
                        vis[q*k+i][k+j]=1;
                    }
                }
            }
        }
    }
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        if(vis[n][m]||vis[m][n])  puts("Alice");
        else puts("Bob");
    }
    return 0;
}

Ball Dropping

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5003,M=998244353;
signed main(){
    double r,a,b,h;
    cin>>r>>a>>b>>h;
    double f=(a-b)/2.0*(a-b)/2.0+h*h;
    f=sqrt(f);
    double s=f*r;
    if(2*r<=b){
        cout<<"Drop"<<endl;
    }else{
        double s1=(a+b)/2.0*h;
        s1-=s;
        s1*=2;
        s1-=a*h;
        s1/=(b-a);
        cout<<"Stuck"<<endl;
        printf("%.10lf\n",s1);
    }
    return 0;
}

Cut the Tree

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, ecnt, ret, ans;
int head[N];
int lc[N * 20], rc[N * 20], lis[N * 20], lds[N * 20], root[N],val[N];
int node_cnt;
int vis[N], sz[N], Max[N];
int sum;
int rt;
int res = N;

struct Edge {
    int to, next;
} e[N << 1];


inline void adde(int x, int y) {
    e[++ecnt].to = y;
    e[ecnt].next = head[x];
    head[x] = ecnt;
}

void Merge(int &x, int y) {
    if(!x || !y) {
        x = x + y;
        return;
    }
    lis[x] = max(lis[x], lis[y]);
    lds[x] = max(lds[x], lds[y]);
    ret = max(ret, max(lis[lc[x]] + lds[rc[y]], lis[lc[y]] + lds[rc[x]]));
    Merge(lc[x], lc[y]);
    Merge(rc[x], rc[y]);
}


int Query(int &x, int l, int r, int L, int R, int *h) {
    if(l > r) return 0;
    if(!x) return 0;
    if(L <= l && r <= R) return h[x];
    int tmp = 0, mid = l + ((r - l) >> 1);
    if(L <= mid) tmp = max(tmp, Query(lc[x], l, mid, L, R, h));
    if(R > mid) tmp = max(tmp, Query(rc[x], mid + 1, r, L, R, h));
    return tmp;
}

void Update(int &x, int l, int r, int pos, int val, int *h) {
    if(!x) {
        x = ++node_cnt;
        lis[x] = 0;
        lds[x] = 0;
        lc[x] = 0;
        rc[x] = 0;
    }
    h[x] = max(h[x], val);
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(pos <= mid) Update(lc[x], l, mid, pos, val, h);
    else Update(rc[x], mid + 1, r, pos, val, h);
}

void dfs(int u, int fa) {
    root[u] = 0;
    for(int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if(v == fa) continue;
        dfs(v, u);
    }
    ret = 0;
    int now_lis = 0, now_lds = 0, son_lis, son_lds;
    for(int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if(v == fa) continue;
        son_lis = Query(root[v], 1, n, 1, val[u] - 1, lis);
        son_lds = Query(root[v], 1, n, val[u] + 1, n, lds);
        Merge(root[u], root[v]);
        ans = max(ans, now_lis + 1 + son_lds);
        ans = max(ans, now_lds + 1 + son_lis);
        now_lds = max(now_lds, son_lds);
        now_lis = max(now_lis, son_lis);
    }
    ans = max(ans, ret);
    Update(root[u], 1, n, val[u], now_lis + 1, lis);
    Update(root[u], 1, n, val[u], now_lds + 1, lds);
}

void get_sz(int u, int fa) {
    sz[u] = 1;
    for(int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if(v == fa || vis[v]) continue;
        get_sz(v, u);
        sz[u] += sz[v];
    }
}

void get_rt(int u, int fa) {
    Max[u] = 0;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (v == fa || vis[v]) continue;
        get_rt(v, u);
        Max[u] = max(Max[u], sz[v]);
    }
    Max[u] = max(Max[u], sum - sz[u]);
    if (Max[rt] > Max[u] || !rt) rt = u;
}

void solve(int x) {
    vis[x] = 1;
    int maxv = 0, u = 0;
    for(int i = head[x]; i; i = e[i].next) {
        int v = e[i].to;
        ans = node_cnt = 0;
        dfs(v, x);
        if (maxv < ans) maxv = ans, u = v;
    }
    res = min(res, maxv);
    if(vis[u]) return;
    get_sz(u, 0);
    sum = sz[u];
    get_rt(u, 0);
    solve(rt);
}

int main() {
    cin >> n;
    for(int i = 1; i <= n - 1; ++i) {
        int la, lb;
        cin >> la >> lb;
        adde(la, lb);
        adde(lb, la);
    }
    for(int i =  1; i <= n; ++i) {
        cin >> val[i];
    }
    sum = n;
    get_sz(1, 0);
    get_rt(1, 0);
    solve(rt);
    cout << res << endl;
    return 0;
}

Determine the Photo Position

#include<bits/stdc++.h>

using namespace std;

char a[2010][2010];
int pre[2010][2010];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }

    for(int i=1;i<=n;i++){
        int sum=0;
        for(int j=n;j;j--){
            if(a[i][j]=='0'){
                sum++;
            }else{
                sum=0;
            }
            pre[i][j]=sum;
        }
    }

    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(pre[i][j]>=m){
                ans++;
            }
        }
    }

    cout<<ans<<endl;
    return 0;
}

Escape along Water Pipe

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
#define MAXN 1005
int T, n, m, mp[MAXN][MAXN], vis[MAXN][MAXN][4];

const int dx[4]={1, 0, -1, 0};
const int dy[4]={0, 1, 0, -1};
const int type[4][4]={
    {5, 1, -1, 0},
    {3, 4, 0, -1},
    {-1, 2, 5, 3},
    {2, -1, 1, 4}
};

struct Sta {int x, y, dir;} pre[MAXN][MAXN][4];

bool check(int x, int y, int dir)
{
 if(x==n+1 && y==m && dir==0) return true;
    if(x<1 || x>n || y<1 || y>m || vis[x][y][dir]) return false;
    return true;
}

void print(Sta sta, int step)
{
    int x=sta.x, y=sta.y, dir=sta.dir;
    if(x==1 && y==1 && dir==0) {
        printf("%d\n", step*2);
        return;
    }
    Sta psta=pre[x][y][dir];
    print(psta, step+1);
    int px=psta.x, py=psta.y, pdir=psta.dir;
    int tmp=type[pdir][dir];
    if(tmp<4)
        printf("1 %d %d %d\n", (tmp-mp[px][py]+4)%4*90, px, py);
    else
        printf("1 %d %d %d\n", (tmp-mp[px][py]+2)%2*90, px, py);
    mp[px][py]=tmp;
    printf("0 %d %d\n", px, py);
}
bool bfs(){
    queue<Sta> q;
    q.push(Sta{1, 1, 0});
    vis[1][1][0]=1;
    while(!q.empty()) {
        int x=q.front().x, y=q.front().y, dir=q.front().dir;
        q.pop();
        if(mp[x][y]<4) {
            int ndir=(dir+1)%4;
            int nx=x+dx[ndir], ny=y+dy[ndir];
            if(check(nx, ny, ndir)) {
                q.push(Sta{nx, ny, ndir});
                vis[nx][ny][ndir]=1;
                pre[nx][ny][ndir]=Sta{x, y, dir};
            }
            ndir=(dir+3)%4;
            nx=x+dx[ndir], ny=y+dy[ndir];
            if(check(nx, ny, ndir)) {
                q.push(Sta{nx, ny, ndir});
                vis[nx][ny][ndir]=1;
                pre[nx][ny][ndir]=Sta{x, y, dir};
            }
            if(nx==n+1 && ny==m && ndir==0) return true;
        } else {
            int ndir=dir;
            int nx=x+dx[ndir], ny=y+dy[ndir];
            if(check(nx, ny, ndir)) {
                q.push(Sta{nx, ny, ndir});
                vis[nx][ny][ndir]=1;
                pre[nx][ny][ndir]=Sta{x, y, dir};
            }
            if(nx==n+1 && ny==m && ndir==0) return true;
        }
    }
    return false;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                scanf("%d",&mp[i][j]);
                memset(vis[i][j], 0, sizeof(vis[i][j]));
            }
        }
        if(bfs()){
            cout<<"YES"<<endl;
            print(Sta{n+1, m, 0}, 0);
        }else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

Find 3-friendly Integers

#include<iostream>
using namespace std;
#define int long long
int check(int u){
    int ans=0;
    for(int i=0;i<=99;i++){
        if(i<=9){
            if(i%3==0){
                ans++;
            }
        }else{
            int a=i%10;int b=i/10;
            if(a%3==0||b%3==0||i%3==0)ans++;
        }
    }
    if(u>99){
        int res=0;
        res+=ans;
        res+=(u-(long long)100+(long long)1);
        return res;
    }else{
        int res=0;
        for(int i=0;i<=u;i++){
            if(i<=9){
                if(i%3==0){
                    res++;
                }
            }else{
                int a=i%10;int b=i/10;
                if(a%3==0||b%3==0||i%3==0)res++;
            }
        }
        return res;
    }
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        int l,r;
        scanf("%lld%lld",&l,&r);
        int u=check(l-1);
        int v=check(r);
       // cout<<"NN"<<u<<" "<<v<<endl;
        cout<<v-u<<endl;
    }
}
//1 20
//1 100

Game of Swapping Numbers

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int maxn=5e5+10;
int a[maxn],b[maxn],Ma[maxn], Mi[maxn];

bool cmp(int x,int y){
    return x>y;
}
signed main(){
    int n, k;
    cin >> n >> k;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i];
    }
    for(int i=1; i<=n; i++)
    {
        cin >> b[i];
    }
    long long ans=0;
    if(n==2)
    {
        if(k%2)
        {
            swap(a[1],a[2]);
        }
        ans=ans+abs(a[1]-b[1])+abs(a[2]-b[2]);
    }else{
        for(int i=1;i<=n;i++){
            ans=ans+abs(a[i]-b[i]);
            Ma[i]=max(a[i],b[i]);
            Mi[i]=min(a[i],b[i]);
        }
        sort(Ma+1,Ma+1+n);
        sort(Mi+1,Mi+1+n,cmp);
        for(int i=1;i<=n&&i<=k;i++){
            if(Mi[i]>Ma[i]){
                ans=ans+2*(Mi[i]-Ma[i]);
            }else{
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Hash Function

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAXN=2e6+10;
const int p=500000;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const double Pi=acos(-1.0);
struct complex
{
    double x=0,y=0;
    complex (double xx=0,double yy=0){x=xx,y=yy;}
}a[MAXN],b[MAXN];
complex operator + (complex a,complex b){ return complex(a.x+b.x , a.y+b.y);}
complex operator - (complex a,complex b){ return complex(a.x-b.x , a.y-b.y);}
complex operator * (complex a,complex b){ return complex(a.x*b.x-a.y*b.y , a.x*b.y+a.y*b.x);}//不懂的看复数的运算那部分 
int N,M;
int l,r[MAXN];
bool vis[MAXN];
int limit=1;
void fast_fast_tle(complex *A,int type)
{
    for(int i=0;i<limit;i++) 
        if(i<r[i]) swap(A[i],A[r[i]]);//求出要迭代的序列 
    for(int mid=1;mid<limit;mid<<=1)//待合并区间的中点
    {
        complex Wn( cos(Pi/mid) , type*sin(Pi/mid) ); //单位根 
        for(int R=mid<<1,j=0;j<limit;j+=R)//R是区间的右端点，j表示前已经到哪个位置了 
        {
            complex w(1,0);//幂 
            for(int k=0;k<mid;k++,w=w*Wn)//枚举左半部分 
            {
                complex x=A[j+k],y=w*A[j+mid+k];//蝴蝶效应 
                A[j+k]=x+y;
                A[j+mid+k]=x-y;
            }
        }
    }
}
int main()
{
    int N=read();
    for(int i=0;i<N;i++){
        int t;scanf("%d",&t);
        a[t].x=1;
        b[p-t].x=1;
    }
    while(limit<=500000+500000){
        limit<<=1,l++;
    }
    for(int i=0;i<limit;i++)
        r[i]= ( r[i>>1]>>1 )| ( (i&1)<<(l-1) ) ;
    fast_fast_tle(a,1);
    fast_fast_tle(b,1);
    for(int i=0;i<limit;i++) a[i]=a[i]*b[i];
    fast_fast_tle(a,-1);
    for(int i=0;i<limit;i++){
        if((int)(a[i].x/limit+0.5)!=0){
            vis[abs(i-p)]=1;
        }
    }
    for(int i=1;i<=p+1;i++){
        int f=1;
        for(int j=i;j<=500000;j+=i){
            if(vis[j]){
                f=0;
                break;
            }
        }
        if(f){
            cout<<i;
            break;
        }
    }
    /*for(int i=N;i<=p+1;i++){
        int f=1;
        for(int k=1;k*i<=p;k++){
            if(vis[k*i]) {
                f=0;
                break;
            }
        }
        if(f) {
            cout<<i;
            break;
        }
    }*/
    return 0;
}

Increasing Subsequence

#include<bits/stdc++.h>
using namespace std;
const int N=5005,mod=998244353;
typedef long long LL;
const double eps=1e-7;

LL a[N],inv[N];
LL n;
LL qsm(LL a,LL n){
    LL res=1;
    while(n){
        if(n&1)res=(LL)res*a%mod;
        a=(LL)a*a%mod;
        n>>=1;
    }
    return res;
}
LL  f[N][N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    LL ans=0;
    for(int i=1;i<=n;i++)inv[i]=qsm(i,mod-2);
    for(int j=n;j>=0;j--){
        LL cnt=0,sum=0;
        for(int i=n;i>=0;i--){
            if(a[i]>j){
                cnt++;
                sum+=f[j][a[i]];
                sum%=mod;
            }else if(a[i]<j){
                f[a[i]][j]+=1;
                if(!cnt)continue;
                f[a[i]][j]+=sum*inv[cnt];
                f[a[i]][j]%=mod;
            }
        }
    }
    for(int i=1;i<=n;i++)ans=(ans+f[0][i])%mod;
    cout<<ans*inv[n]%mod<<endl;
    return 0;
}

Journey among Railway Stations

#include <bits/stdc++.h>
#define ll long long
#define qc ios::sync_with_stdio(false); cin.tie(0);cout.tie(0)
#define fi first
#define se second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define pb push_back
using namespace std;
const int MAXN = 1e6 + 10;
const ll mod = 1e9 + 7;
int u[MAXN], v[MAXN], c[MAXN];
int n;
struct Tree{
    // 能否到达 最晚到达 最早到下一站 经过花费时间
    int res, v, u, c;
}tree[MAXN << 2];
Tree merge(Tree a, Tree b){
    Tree tmp;
    tmp.res = a.res & b.res;
    if(a.u > b.v){
        tmp.res = 0;
    }
    tmp.c = a.c + b.c;
    tmp.v = min(a.v, b.v - a.c);
    tmp.u = max(a.u + b.c, b.u);
    return tmp;
}
void build(int rt, int l, int r){ 
    if(l == r){
        tree[rt].res = 1;
        tree[rt].c = c[l];
        tree[rt].v = v[l];
        tree[rt].u = u[l] + c[l];
        return ;
    }
    int m = (l + r) >> 1;
    build( rt << 1,l, m);
    build( rt << 1 | 1,m+1, r);
    tree[rt] = merge(tree[rt << 1], tree[rt << 1 | 1]);
}
Tree query(int rt,int l,int r,int L,int R){
    if(L<=l&&R>=r){
        return tree[rt];
    }
    int mid=(l+r)>>1;
    if(R<=mid)return query(rt*2,l,mid,L,R);
    else if(L>mid)return query(rt*2+1,mid+1,r,L,R);
    else return merge(query(rt*2,l,mid,L,R),query(rt*2+1,mid+1,r,L,R));
}
void update(int rt,int l,int r,int pos){
    if(l==r&&l==pos){
        tree[rt].res=1;
        tree[rt].v=v[l];
        tree[rt].u=u[l]+c[l];
        tree[rt].c=c[l];
        return ;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)update(rt*2,l,mid,pos);
    else update(rt*2+1,mid+1,r,pos);
    tree[rt]=merge(tree[rt*2],tree[rt*2+1]);
}
void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&u[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&v[i]);
    }
    for(int i=1;i<n;i++){
        scanf("%d",&c[i]);
    }
    build(1,1,n);
    int Q;
    scanf("%d",&Q);
    while(Q--){
        int op;
        scanf("%d",&op);
        if(op==0){
            int l,r;
            scanf("%d%d",&l,&r);
            if(query(1,1,n,l,r).res){
                printf("Yes\n");
            }else{
                printf("No\n");
            }
        }
        else if(op==1){
            int x,y;
            scanf("%d%d",&x,&y);
            c[x]=y;
            update(1,1,n,x);
        }else{
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            u[x]=y;
            v[x]=z;
            update(1,1,n,x);
        }

    }
}
int main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

Knowledge Test about Match

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 7;
double sqr[maxn];
int a[maxn];
#define f(x, y) (x > y ? sqr[x - y] : sqr[y - x])
int main() {
    int T;
    cin >> T;
    for (int i = 1; i < maxn; i++) sqr[i] = sqrt(i);
    while (T--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i];
        sort(a, a + n);
        for (int k = 0; k < 2; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (f(i, a[i]) + f(j, a[j]) > f(i, a[j]) + f(j, a[i])) {
                        swap(a[i], a[j]);
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) cout << a[i] << ' ';
        cout << '\n';
    }
}
全部评论

相关推荐

11-21 15:02
嘉士伯_运营管理_HR
为什么建议看看外企
不知不觉已经十一月份了，国庆回来秋招就算真的进入中后期了，基本就是考选调，考体制内了，私企最后能投的一波就是十月上旬了，现在投着，前面大佬释放hc&nbsp;大家还有一点机会1.不喜欢你工作太卷！（俺是卷心菜，虽卷但菜）外企非常严格地遵循无996，955工作制的同时实现WLB（work&nbsp;life&nbsp;balance），即即工作生活平衡，到点就可以走人~如果怕堵车或者有其他事情（比如不太舒服、有急事）都可以提前回去，部分外企每周还有一天或两天居家办公，嘿嘿~2.不喜欢你太给自己设限请大声说:我们都有无限可能不同于国企对应届生身份卡的比较严格，外企尤其往届生友好，毕业两年内还保有应届生身份的姐妹都可以去投！...
百威成长空间 50人发布
点赞 评论 收藏
分享
今天 12:48
南京工业大学 Java
看腻了佬，十分钟来看看一名计算机普通双非硕的秋招总结
牛客上充斥着佬们的offer选择和秋招总结，这两天想找些双非硕兄弟们的秋招记录参考参考，能找到的帖子少之又少，趁着今天有时间有心情分享一下供兄弟们参考也作为自己的一个总结😎&nbsp;始终觉得互联网上也该有更多普通人的生活记录，羡慕佩服佬的同时真的时而也会焦虑迷茫😢&nbsp;首先介绍下个人bg，南京某学院本计科专业，南京某双非电子信息硕(不过学校有个双一流名头)&nbsp;简单说硕士期间和大部分人一样做的深度学习，自学java找工作，那么久了水平依旧是苍穹外卖水平hhh，力扣刷了30左右hhh，不过八股个人觉得背的还可以，反正应付面试很ok，大概就是这样&nbsp;不优秀不突出但普通hhh&nbsp;适合更多👶&nbsp;哥们呢我比较爱玩，...
找工作，你会甘心进小厂还是猛冲大厂 双非有机会进大厂吗
点赞 评论 收藏
分享
10-15 09:13
已编辑
天津大学 soc前端设计
点赞 评论 收藏
分享
头像
11-19 16:15
已编辑
中南大学 Java
点赞 评论 收藏
分享
点赞 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
260156次浏览 2142人参与
# 0offer是寒冬太冷还是我太菜 #
886067次浏览 7895人参与
# 北方华创开奖 #
23502次浏览 260人参与
# 地方国企笔面经互助 #
2792次浏览 7人参与
# 学历or实习经历，哪个更重要 #
43029次浏览 319人参与
# 选完offer后，你后悔学本专业吗 #
12863次浏览 91人参与
# 查收我的offer竞争力报告 #
18780次浏览 248人参与
# 应届生被毁约被毁意向了怎么办 #
27971次浏览 243人参与
# 你最想要的公司福利是？ #
41514次浏览 144人参与
# 如何一边实习一边秋招 #
986844次浏览 12608人参与
# 一觉醒来，我觉醒了超级打工人系统 #
3236次浏览 36人参与
# 嵌入式转岗的难度怎么样 #
11107次浏览 250人参与
# 你最希望上岸的公司是？ #
76194次浏览 469人参与
# 如何写一份好简历 #
604412次浏览 8494人参与
# 面试体验感最好的是哪家？ #
83509次浏览 815人参与
# 机械应届生薪资要多少才合适？ #
12523次浏览 61人参与
# 牛客十周岁生日快乐 #
48601次浏览 756人参与
# 你认为第一份工作重要吗 #
5401次浏览 49人参与
# 985本硕1个中小厂offer，摆烂or继续努力 #
79725次浏览 589人参与
# 秋招OC许愿 #
227779次浏览 1878人参与
# 来聊聊机械薪资天花板是哪家 #
65257次浏览 441人参与
牛客网
牛客企业服务