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;
}