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

Black and white

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
//#define int long long
const int N=5010*5010;
long long g[2];
struct Node{
    int x,y;
    long long val;
}node[N];
int fa[2*5010];
bool cmp(Node x,Node y){
    return x.val<y.val;
}
int get(int x){
    if(fa[x]==x)return x;
    return fa[x]=get(fa[x]);
}
vector<Node> e[100005];
signed main(){
    int n,m,a,b,c,d,p;
    cin>>n>>m>>a>>b>>c>>d>>p;
    g[0]=a;
    int cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            g[1]=(g[0]*g[0]%p*b%p+g[0]*c%p+d)%p;
            e[g[1]].push_back({i,j+n});
            g[0]=g[1];
        }
    }
    for(int i=1;i<=n+m;i++)fa[i]=i;
    long long ans=0;
    for(int i=0;i<p;i++){
        for(auto j:e[i]){
            int x=j.x,y=j.y;
            if(fa[get(x)]==fa[get(y)])continue;
            fa[get(x)]=get(y);
            ans+=i;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Minimum grid

#include<iostream>
#include<cstring>
using namespace std;
#define int long long

const int maxn=2e3+10;
int a[maxn],b[maxn];
const int maxe=1e6+10;
int tot,h[maxe],ne[maxe*2],ver[maxe*2];
void add(int x,int y){
    ver[++tot]=y;ne[tot]=h[x];h[x]=tot;
}
int visit[maxe],match[maxe];
bool dfs(int x){
    for(int i=h[x],y;i;i=ne[i]){
        if(!visit[y=ver[i]]){
            visit[y]=1;
            if(!match[y]||dfs(match[y])){
                match[y]=x;return true;
            }
        }
    }
    return false;
}
signed main(){
    int n,m,k;
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&b[i]);
    }
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%lld%lld",&x,&y);
        if(a[x]==b[y]){
            add(x,y);
        }
    }
    for(int i=1;i<=n;i++){
        memset(visit,0,sizeof(visit));
        dfs(i);
    }
    int ans=0;
    for(int i=1;i<=n;i++)ans+=(a[i]+b[i]);
    for(int i=1;i<=n;i++){
        if(match[i]){
            ans-=b[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}

Math

#include<bits/stdc++.h>
#define i128 __int128
using namespace std;
typedef long long ll;
const i128 N = 2e18;
i128 a[5000010];
int tot=0;
int main(){
    a[++tot]=1;
    for(i128 i=2;i<=1000002;i++){
        i128 x=i;
        i128 y=i*i*i;
        i128 k=i*i;
        a[++tot]=y;
        while(1){
            i128 tmp=k*y-x;
            if(tmp>N) break;
            a[++tot]=tmp;
            x=a[tot-1];
            y=a[tot];
        }
    }
    sort(a+1,a+1+tot);
    int t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        int ans=upper_bound(a+1,a+1+tot,n)-a;
        cout<<ans-1<<endl;
    }
    return 0;
}

24dian

#include<bits/stdc++.h>
#define ll long long
using namespace std;
double a[5];
int b[5],B[5],n,m,ans,as[50005][5],F;
bool check(double x){
    return (x-(int)x)>=1e-6&&(x-(int)x)<=1-1e-6;
}
void dfs1(int s,int f){
    if(F==3)return;
    if(s==n){
        if(abs(a[1]-m)<1e-6){
            if(f)F|=1;
            else F|=3;
        }
        return;
    }
    double A[5];
    for(int i=0;i<=4;i++)A[i]=a[i];
    if(s<n){
        for(int i=1;i<=n-s+1;i++){
            for(int j=1;j<=n-s+1;j++){
                if(i==j)continue;
                for(int k=1;k<=4;k++){
                    int w=f;
                    if(k==1)a[i]+=a[j];
                    if(k==2)a[i]-=a[j];
                    if(k==3)a[i]*=a[j];
                    if(k==4){
                        a[i]/=a[j];
                        if(check(a[i]))w=1;
                    }
                    a[j]=99999999;
                    sort(a+1,a+n+2-s);
                    a[n+1-s]=0;
                    dfs1(s+1,w);
                    for(int i=0;i<=4;i++)a[i]=A[i];
                }
            }
        }
    }
}
void dfs(int s,int k){
    if(s>n){
        F=0;dfs1(1,0);
        if(F==1){
            ans++;
            for(int i=1;i<=4;i++){
                as[ans][i]=a[i];
            }
        }
        return;
    }
    for(int i=k;i<=13;i++){
        a[s]=i;
        dfs(s+1,i);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    if(n>3)dfs(1,1);
    cout<<ans<<endl;
    for(int i=1;i<=ans;i++){
        for(int j=1;j<=4;j++)
            {
                printf("%d ",as[i][j]);
            }
        cout<<endl;
    }
    return 0;
}

Yu Ling(Ling YueZheng) and Colorful Tree

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int link[200010];
int tot = 0, now;
struct edge
{
    int y, next;
    LL v;
} a[300010];
int in[200010], out[200010], col[200010], ver[200010];
LL dep[200010];
void insert(int x, int y, LL v)
{
    a[++tot] = {y, link[x], v};
    link[x] = tot;
}
void dfs(int x)
{
    in[x] = ++now;
    for (int i = link[x]; i; i = a[i].next)
    {
        int y = a[i].y;
        if (!in[y])
        {
            dep[y] = dep[x] + a[i].v;
            dfs(y);
        }
    }
    out[x] = ++now;
}
int main()
{
    int n, q;
    cin >> n >> q;
    for (int i = 1; i < n; ++i)
    {
        int x, y;
        LL v;
        cin >> x >> y >> v;
        insert(x, y, v);
        insert(y, x, v);
    }
    now = 0;
    dep[1] = 0;
    dfs(1);
    // for (int i = 1; i <= n; ++i)
    //     cout << dep[i] << endl;
    while (q--)
    {
        int opt, u, x, l, r;
        cin >> opt;
        if (!opt)
        {
            cin >> u >> x;
            col[u] = x;
            ver[x] = u;
        }
        else 
        {
            cin >> u >> l >> r >> x;
            int st = (l + x - 1) / x * x;
            LL ans = 1e18;
            for (int i = st; i <= r; i += x)
            {
                if (in[ver[i]] <= in[u] && out[u] <= out[ver[i]])
                    ans = min(ans, dep[u] - dep[ver[i]]);
            }
            if (ans == 1e18)
                cout << "Impossible!" << endl;
            else 
                cout << ans << endl;
        }
    }
    return 0;
}

Kuriyama Mirai and Exclusive Or

#include<iostream>
using namespace std;

const int N = 6e5 + 10;
int n, q, a[N], aa[N],m;
bool b[N][30];

void update(int l,int x){
    for(int i=0,j=1;i<30;i++,j<<=1){
//        cout<<"SSDS"<<l<<endl;
        if((x&j))aa[l]^=j;
        int k=(((x>>i)+1)<<i)-x+l;
        if(k<=n)b[k][i]^=1;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++){
        int op,l,r,x;
        scanf("%d%d%d%d",&op,&l,&r,&x);
        if(op){
            update(l,x);
            if((r+1)<=n)update(r+1,x+r-l+1);
        }else{
            aa[l]^=x;
            if((r+1)<=n)aa[r+1]^=x;
        }
    }
    //cout<<"MM
    for(int i=0,j=1;i<30;i++,j<<=1){
        for(int k=1;k<=n;k++){
            if((k+j)<=n)b[k+j][i]^=b[k][i];
            if(b[k][i])aa[k]^=j;
        }    
    }
    for(int i=2;i<=n;i++){
        aa[i]^=aa[i-1];
    }
    for(int i=1;i<=n;i++){
        a[i]^=aa[i];
        printf("%d ",a[i]);
    }
    return 0;
}

Counting Triangles

#include<iostream>
using namespace std;
namespace GenHelper
{
    unsigned z1,z2,z3,z4,b,u;
    unsigned get()
    {
        b=((z1<<6)^z1)>>13;
        z1=((z1&4294967294U)<<18)^b;
        b=((z2<<2)^z2)>>27;
        z2=((z2&4294967288U)<<2)^b;
        b=((z3<<13)^z3)>>21;
        z3=((z3&4294967280U)<<7)^b;
        b=((z4<<3)^z4)>>12;
        z4=((z4&4294967168U)<<13)^b;
        return (z1^z2^z3^z4);
    }
    bool read() {
      while (!u) u = get();
      bool res = u & 1;
      u >>= 1; return res;
    }
    void srand(int x)
    {
        z1=x;
        z2=(~x)^0x233333333U;
        z3=x^0x1234598766U;
        z4=(~x)+51;
          u = 0;
    }
}
using namespace GenHelper;
bool edge[8005][8005];
int f[2][8010];
int main() {
  int n, seed;
  cin >> n >> seed;
  srand(seed);
  for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++){
            int x=read();
            f[x][i]++;f[x][j]++;
        }
   long long res=0;
   res=(long long)(n)*(long long)(n-1)*(long long)(n-2)/(long long)6;
   for(int i=0;i<n;i++){
       res-=(long long)f[0][i]*(long long)(f[1][i])/2;
   }
  cout<<res<<endl;
  return 0;
}

全部评论

推荐最新楼层

昨天 00:48

辽宁大学实施工程师

我的三面还是挂了

我和安克的HR聊得特别愉快，没想到最后还是没能通过。我是真的很想加入这个团队，感觉自己和他们的理念很契合。收到通知时，心里一沉，虽然他们说这并不是对我的否定，但我还是忍不住感到遗憾。希望以后能够找一个适合的舞台吧！

牛客创作赏金赛

点赞评论收藏

昨天 13:37

已编辑

贵阳人文科技学院 Web前端

简历建议，大佬们能帮忙提提建议吗

感觉白学了，浪费了半年来考研，现在考研也无望了，秋招也没有跟上，怎么办呀我还能有机会入行吗。

简历中的项目经历要怎么写秋招被确诊为……

点赞评论收藏

10-16 12:29

携程_移动安全研发

转正了呀

Yushuu：你的确很厉害，但是有一个小问题：谁问你了？我的意思是，谁在意？我告诉你，根本没人问你，在我们之中0人问了你，我把所有问你的人都请来 party 了，到场人数是0个人，誰问你了？WHO ASKED？谁问汝矣？誰があなたに聞きましたか？누가 물어봤어？我爬上了珠穆朗玛峰也没找到谁问你了，我刚刚潜入了世界上最大的射电望远镜也没开到那个问你的人的盒，在找到谁问你之前我连癌症的解药都发明了出来，我开了最大距离渲染也没找到谁问你了我活在这个被辐射蹂躏了多年的破碎世界的坟墓里目睹全球核战争把人类文明毁灭也没见到谁问你了😆

点赞评论收藏