首页 > 其他分享 >The 3rd Universal Cup. Stage 8: Cangqian

The 3rd Universal Cup. Stage 8: Cangqian

时间:2024-09-09 21:15:19浏览次数:12  
标签:include int Universal Cangqian ++ long ans Stage size

题解:

https://files.cnblogs.com/files/clrs97/ZJCPC24_Tutorial.pdf

 

Code:

A. Bingo

#include <bits/stdc++.h>
using namespace std;
string n;
int m;
typedef long long ll;
ll sum[1000005];
int pw[1000005];
bool all[1000005];
int sol[1000020];
void solv() {
    cin >> n >> m;
    int am = 0 ;
    for(int i = 0;i < n.size();i++) am = (10LL * am + n[i] - '0') % m;
    int ans = m - am;
    
    sum[n.size()] = 0;
    for(int i = 0;i < n.size();i++) {
        sum[i] = 1LL * ('9' - n[i]) * pw[n.size() - i - 1] ;
    }
    all[n.size()] = 1;
    for(int i = n.size() - 1;i >= 0;i--) {
        all[i] = all[i + 1] && (n[i] == '9') ;
    }
    for(int i = n.size() - 1;i >= 0;i--) sum[i] += sum[i + 1];
    string b; int d = m;
    while(d) {
        b += ((d % 10) + '0') ;
        d /= 10;
    }
    reverse(b.begin() , b.end()) ;
    vector<int> rm(b.size() + 1) ;
    for(int i = b.size() - 1;i >= 0;i--) {
        rm[i] = (b[i] - '0') * pw[b.size() - i - 1] + rm[i + 1] ;
    }
    for(int i = 0;i < n.size() && i + b.size() - 1 < n.size();i++) { //match
        for(int j = 0 ; j <= b.size();j++) {
            /// here mat , diff on n[i + j]
            if(i + j >= n.size()) break ;
            if(j == b.size()) {
                if(!all[i + j]) ans = min(ans , 1) ;
                break;
            }
            if(b[j] > n[i + j]) {
                /// 
                // printf("in %d %d : %d %d %d\n",i,j,(ll)(b[j] - n[i + j] - 1) * pw[n.size() - (i + j) - 1] , sum[i + j + 1] , 1LL * rm[j + 1] * pw[n.size() - (i+b.size())]) ;
                ans = min((ll)ans , 1 + (ll)(b[j] - n[i + j] - 1) * pw[n.size() - (i + j) - 1] + sum[i + j + 1] + 1LL * rm[j + 1] * pw[n.size() - (i+b.size())]);
            }
            if(j == b.size() || i + j >= n.size() || b[j] != n[i + j]) break;
        }
    }
    int L = (int)n.size() - 1;
    // printf("L %d\n",L) ;
    for(int i = 0;i < n.size() + 15;i++) sol[i] = 0;
    for(int i = 0;i < n.size();i++) sol[n.size() - i - 1] = n[i] - '0' ;
    sol[0] += ans ;
    for(int i = 0;i <= L;i++) {
        sol[i + 1] += sol[i] / 10;
        sol[i] %= 10;
        if(sol[i + 1]) L = max(L , i + 1) ;
    }
    for(int i = L;i >= 0;i--) cout << sol[i] ; cout << '\n';
    return ;
}
int main() {
    // freopen("in.txt","r",stdin);
    // freopen("out2.txt","w",stdout) ;
    ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
    int t;cin >> t;
    pw[0] = 1;
    for(int i = 1;i <= 100000;i++) {
        pw[i] = min(1000000000LL , pw[i - 1] * 10LL) ;
    }
    while(t--) solv() ;
}

 

B. Simulated Universe

#include<bits/stdc++.h>
using namespace std;
 
const int N=8e3+1e2+7;
 
int T,n;
 
int f[2][N];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=0;i<=n;i++)
            f[0][i]=-1e9;
        f[0][0]=0;
        int now=0,last=1;
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            swap(now,last);
            for(int j=0;j<=i+1;j++)
                f[now][j]=-1e9;
            string ty;
            cin>>ty;
            if(ty=="B")
            {
                ans+=2;
                for(int j=0;j<=i;j++)
                {
                    if(f[last][j]<0)
                        continue;
                    f[now][j+1]=max(f[now][j],f[last][j]);
                    if(f[last][j])
                        f[now][j]=max(f[now][j],f[last][j]-1);
                }
            }
            else
            {
                int a,b;
                cin>>a>>b;
                for(int j=0;j<=i;j++)
                {
                    if(f[last][j]<0)
                        continue;
                    f[now][max(j-a,0)]=max(f[now][max(j-a,0)],f[last][j]);
                    f[now][j]=max(f[now][j],f[last][j]+b);
                }
            }
        }
        for(int i=0;i<=n;i++)
            if(f[now][i]>=0)
            {
                ans-=i;
                break;
            }
        cout<<ans<<"\n";
    }
}
/*
1
3 6
1 2 3
4 5 6
6 9 9
8 12 13
10 15 17
12 18 21
*/

 

C. Challenge NPC

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii ;
vector<pii> Ed;
int main() {
    ios::sync_with_stdio(false) ; cin.tie(0) ;
    int k ; cin >> k;
    int n = k + 2;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j < i;j++) {
            Ed.push_back({j*2 , i*2 - 1});
            Ed.push_back({j*2 - 1 , i *2});
        }
    }
    cout << n*2 << ' ' << Ed.size() <<' ' << 2 << '\n' ;
    for(int i = 1;i <= n*2;i++) {
        cout << (i&1) + 1 <<' ' ;
    }
    cout << '\n';
    for(auto [x,y] : Ed) cout << x <<' ' << y << '\n';
    return 0;
}

 

D. Puzzle: Easy as Scrabble

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=300005,P=998244353;
#define NO {puts("NO"); exit(0);}
int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; 
auto solve(){
    int n,m;
    cin>>n>>m;
    vector<string> a(n+2);
    for(auto &s:a) cin>>s;
    vector f(n+2,vector<array<char,4>>(m+1));
    vector inq(n+2,vector<bool>(m+2));
    for(int i=1;i<=n;i++){
        if(a[i][0]!='.')
            f[i][1][0]=a[i][0];
        if(a[i][m+1]!='.')
            f[i][m][1]=a[i][m+1];
    }
    for(int j=1;j<=m;j++){
        if(a[0][j]!='.')
            f[1][j][2]=a[0][j];
        if(a[n+1][j]!='.')
            f[n][j][3]=a[n+1][j];
    }
    auto check=[&](int x,int y){
        static int vis[256];
        static int time;
        int num=0; ++time;
        for(auto c:f[x][y]){
            if(!isalpha(c)) continue;
            if(a[x][y]!='x') a[x][y]=c;
            if(vis[c]!=time){
                vis[c]=time;
                num++;
            }
        }
        if(num>1) return true;
        return num==1&&a[x][y]=='x';
    };
    queue<pair<int,int>> qu;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(check(i,j)){
                qu.push({i,j});
                inq[i][j]=true;
            }
        }
    }
    while(qu.size()){
        auto [x,y]=qu.front(); qu.pop();
        inq[x][y]=false;
        a[x][y]='x';
        for(int i=0;i<4;i++){
            if(!isalpha(f[x][y][i])) continue;
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<=0||ny<=0||nx>n||ny>m) NO;
            f[nx][ny][i]=f[x][y][i];
            if(a[nx][ny]!='x') a[nx][ny]=f[x][y][i];
            if(!inq[nx][ny]&&check(nx,ny)){
                inq[nx][ny]=true;
                qu.push({nx,ny});
            }
        }
        f[x][y]={0,0,0,0};
    }
    puts("YES");
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='x') a[i][j]='.';
            putchar(a[i][j]);
        }
        puts("");
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
        // cout<<solve()<<'\n';
        // cout<<(solve()?"Yes":"No")<<'\n';
    }
    return 0;
}
 
 
/* Generated by powerful Codeforces Tool(cf tool)
 * Author: sleep__
 * Time: 2024-04-04 14:25:05
**/

 

E. Team Arrangement

#include<cstdio>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
const int N=65,inf=~0U>>1;
int n,i,w[N],num[N],ans;ull in[N],out[N];
struct E{int l,r;}e[N];
inline bool cmp(const E&a,const E&b){return a.r<b.r;}
inline void solve(int m){
  int sum=0;
  ull S=0;
  for(int i=1;i<=m;i++){
    S^=in[i];
    int now=num[i];
    sum+=now*w[i];
    now*=i;
    while(now--){
      if(!S)return;
      S-=S&-S;
    }
    S^=S&out[i];
  }
  if(sum>ans)ans=sum;
}
void dfs(int x,int m){
  if(x>m)return;
  num[x]=0;
  dfs(x+1,m);
  for(int i=1;;i++){
    m-=x;
    num[x]=i;
    if(!m)solve(x);
    if(m<=0)break;
    dfs(x+1,m);
  }
}
int main(){
  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%d%d",&e[i].l,&e[i].r);
  sort(e,e+n,cmp);
  for(i=0;i<n;i++){
    in[e[i].l]^=1ULL<<i;
    out[e[i].r]^=1ULL<<i;
  }
  for(i=1;i<=n;i++)scanf("%d",&w[i]);
  ans=-inf;
  dfs(1,n);
  if(ans==-inf)puts("impossible");else printf("%d",ans);
}

 

F. Stage: Agausscrab

#include<bits/stdc++.h>
using namespace std;
 
const int N=1e3+1e2+7;
 
int n;
 
string s[N];
 
int a[N];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>s[i]>>a[i];
    string ans;
    for(int i=1;i<=n;i++)
    {
        int r=0;
        for(int j=1;j<=n;j++)
            if(a[j]>a[i])
                r++;
        r+=1;
        for(int j=1;j<=r;j++)
            if(s[i].size())
                s[i].pop_back();
        ans+=s[i];
    }
    ans[0]=ans[0]-'a'+'A';
    cout<<"Stage: "<<ans<<"\n";
}

 

G. Crawling on a Tree

#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int N=10005,M=10005;
int n,m,i,lim[N],g[N],v[N<<1],w[N<<1],wt[N<<1],nxt[N<<1],ed;
int wf[N],wk[N],need[N],sz[N],heavy[N];
ll ans[M];
struct E{
  ll s,d[M];
  int l,r;
  void clr(){
    s=l=0;r=m;
    for(int i=0;i<=m;i++)d[i]=0;
  }
}f[15];
inline void add(int x,int y,int z,int k){
  v[++ed]=y;
  w[ed]=z;
  wt[ed]=k;
  nxt[ed]=g[x];
  g[x]=ed;
}
inline void merge(const E&A,const E&B,E&C){
  int l=A.l+B.l,r=min(A.r+B.r,m);
  static ll d[M];
  int i=A.l+1,j=B.l+1,k=l+1;
  while(k<=r&&i<=A.r&&j<=B.r)d[k++]=A.d[i]<B.d[j]?A.d[i++]:B.d[j++];
  while(k<=r&&i<=A.r)d[k++]=A.d[i++];
  while(k<=r&&j<=B.r)d[k++]=B.d[j++];
  C.s=A.s+B.s;
  C.l=l;
  C.r=r;
  for(int i=l+1;i<=r;i++)C.d[i]=d[i];
}
void dfs(int x,int y){
  need[x]=lim[x];
  sz[x]=1;
  for(int i=g[x];i;i=nxt[i]){
    int u=v[i];
    if(u==y)continue;
    wf[u]=w[i];
    wk[u]=wt[i];
    dfs(u,x);
    sz[x]+=sz[u];
    if(sz[u]>sz[heavy[x]])heavy[x]=u;
    need[x]=max(need[x],need[u]);
  }
}
void go(int x,int y,int o){
  int u=heavy[x];
  if(u){
    go(u,x,o);
    f[o+1].clr();
    merge(f[o],f[o+1],f[o]);
  }else f[o].clr();
  for(int i=g[x];i;i=nxt[i]){
    int u=v[i];
    if(u==y||u==heavy[x])continue;
    go(u,x,o+1);
    merge(f[o],f[o+1],f[o]);
  }
  int L=need[x],R=wk[x],W=wf[x];
  int A=max(f[o].l,L*2-R),B=min(f[o].r,R);
  if(A>B){
    for(int i=1;i<=m;i++)puts("-1");
    exit(0);
  }
  for(int i=f[o].l+1;i<=A;i++)f[o].s+=f[o].d[i];
  f[o].l=A;
  f[o].r=B;
  f[o].s+=1LL*(max(L,A)*2-A)*W;
  for(int i=A+1;i<=B&&i<=L;i++)f[o].d[i]-=W;
  for(int i=max(A,L)+1;i<=B;i++)f[o].d[i]+=W;
}
int main(){
  scanf("%d%d",&n,&m);
  for(i=1;i<n;i++){
    int x,y,z,k;
    scanf("%d%d%d%d",&x,&y,&z,&k);
    add(x,y,z,k);
    add(y,x,z,k);
  }
  for(i=2;i<=n;i++)scanf("%d",&lim[i]);
  wk[1]=m*2;
  dfs(1,0);
  go(1,0,0);
  for(i=1;i<=m;i++)ans[i]=-1;
  ll sum=f[0].s;
  for(i=f[0].l;i<=m;i++){
    if(i>=need[1])ans[i]=sum;
    if(i<m)sum+=f[0].d[i+1];
  }
  for(i=1;i<=m;i++)printf("%lld\n",ans[i]);
}

 

H. Permutation

#include <bits/stdc++.h>
using namespace std;
int n;
const double C = (sqrt(5) - 1) / 2;
int f[1000005];
int d[1000005];
int qry(int l,int r) {
    cout << "? " << l <<' ' << r << '\n' ;
    fflush(stdout) ;
    int x ; cin >> x;
    return x;
}
void solv() {
    cin >> n;
    int l = 1 , r = n;
    int lst_pos = -1;
    while(l < r) {
        int c = d[r - l + 1];
        // printf("C %d %d %d\n",l,r,c) ;
        if(lst_pos == -1) lst_pos = qry(l , r);
        if(r - l == 1) {
            if(lst_pos == l) l = r;
            else r = l;
            break ;
        }
        if(l + c - 1 >= lst_pos) {
            int x = qry(l , l + c - 1);
            if(x == lst_pos) r = l + c - 1;
            else {
                l = l + c;
                lst_pos = -1;
            }
        }
        else {
            int x = qry(r - c + 1 , r);
            if(x == lst_pos) l = r - c + 1;
            else {
                r = r - c;
                lst_pos = -1;
            }
        }
    }
    cout << "! " << l << '\n' ;
    fflush(stdout) ;
    return ;
}
int main() {
    // ios::sync_with_stdio(false) ; cin.tie(0) ;
    int t;cin >> t;
    f[1] = f[2] = 0;
    for(int i = 3;i <= 1000000;i++) {
        int mxc = (int)(C * i); 
        f[i] = 1e9;
        for(int j = max(mxc - 10 , (i + 1)/2) ; j <= min(i - 1 , mxc + 10) ; j++) {
            if(max(f[j] + 1 , f[i - j] + 2) < f[i]) {
                f[i] = max(f[j] + 1 , f[i - j] + 2) ;
                d[i] = j;
            }
        }
        // if(f[i] > ceil(1.5 * log2(i)) - 1) {
        //     printf("%d %d %lf\n",i,f[i],ceil(1.5 * log2(i)) - 1);
        // }
    }
    // printf("%d\n",f[1000000]) ;?
    while(t--) solv() ;
}

 

I. Piggy Sort

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
const int N=2e3+1e2+7;
 
int T,n,m;
 
int x[N][N],sx[N];
 
map<int,int> vis[N];
 
int use[N];
 
int av[N],bv[N],fd,ans[N];
 
void dfs(int t)
{
    if(t==n+1)
    {
        vector<int> id(n);
        iota(id.begin(),id.end(),1);
        sort(id.begin(),id.end(),[&](const int &a,const int &b){
            if(av[a]*bv[b]!=av[b]*bv[a])
                return av[a]*bv[b]<av[b]*bv[a];
            return a<b;
        });
        fd=1;
        for(int i=0;i<n;i++)
            ans[id[i]]=i+1;
        for(int i=1;i<=n;i++)
            cout<<ans[i]<<" \n"[i==n];
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(use[i])
            continue;
        int va=x[2][i]-x[1][t];
        int vb=sx[2]-sx[1];
        int ok=1;
        for(int j=3;j<=m;j++)
        {
            if(va*(sx[j]-sx[1])%vb)
            {
                ok=0;
                break;
            }
            int w=va*(sx[j]-sx[1])/vb+x[1][t];
            if(!vis[j].count(w)||!vis[j][w])
            {
                ok=0;
                break;
            }
        }
        if(ok)
        {
            for(int j=1;j<=m;j++)
            {
                int w=va*(sx[j]-sx[1])/vb+x[1][t];
                vis[j][w]--;
            }
            use[i]=1;
            av[t]=va,bv[t]=vb;
            dfs(t+1);
            use[i]=0;
            for(int j=1;j<=m;j++)
            {
                int w=va*(sx[j]-sx[1])/vb;
                vis[j][w]++;
            }
        }
    }
}
 
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=1;i<=m;i++)
        {
            vis[i].clear();
            sx[i]=0;
            for(int j=1;j<=n;j++)
                cin>>x[i][j],vis[i][x[i][j]]++,sx[i]+=x[i][j];
        }
        if(sx[1]==sx[2])
        {
            for(int i=1;i<=n;i++)
                cout<<i<<" \n"[i==n];
            continue;
        }
        fd=0;
        dfs(1);
        assert(fd);
    }
}
/*
1
3 6
1 2 3
4 5 6
6 9 9
8 12 13
10 15 17
12 18 21
*/

 

J. Even or Odd Spanning Tree

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200005,K=18,M=500005,inf=~0U>>1;
int Case,n,m,cnt,i,j,x,y,z,tmp,f[N],g[N],v[N<<1],w[N<<1],nxt[N<<1],ed;
int d[N],fa[N][K],fe[N][K],fo[N][K];
long long mst,ans;int delta;bool on[M];
struct E{int x,y,z;}e[M];
inline bool cmp(const E&a,const E&b){return a.z<b.z;}
inline void umax(int&a,int b){a<b?(a=b):0;}
int F(int x){return f[x]==x?x:f[x]=F(f[x]);}
inline void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}
void dfs(int x,int y){
  for(int i=1;i<K;i++){
    fa[x][i]=fa[fa[x][i-1]][i-1];
    fe[x][i]=max(fe[x][i-1],fe[fa[x][i-1]][i-1]);
    fo[x][i]=max(fo[x][i-1],fo[fa[x][i-1]][i-1]);
  }
  for(int i=g[x];i;i=nxt[i]){
    int u=v[i],z=w[i];
    if(u==y)continue;
    d[u]=d[x]+1;
    fa[u][0]=x;
    if(z&1){
      fe[u][0]=0;
      fo[u][0]=z;
    }else{
      fe[u][0]=z;
      fo[u][0]=0;
    }
    dfs(u,x);
  }
}
inline int ask(int x,int y,int w[][K]){
  if(x==y)return 0;
  if(d[x]<d[y])swap(x,y);
  int ret=0;
  for(int i=K-1;~i;i--)if(d[fa[x][i]]>=d[y]){
    umax(ret,w[x][i]);
    x=fa[x][i];
  }
  if(x==y)return ret;
    for(int i=K-1;~i;i--)if(fa[x][i]!=fa[y][i]){
    umax(ret,w[x][i]);
    umax(ret,w[y][i]);
    x=fa[x][i];
    y=fa[y][i];
  }
  umax(ret,w[x][0]);
  umax(ret,w[y][0]);
  return ret;
}
int main(){
  scanf("%d",&Case);
  while(Case--){
    scanf("%d%d",&n,&m);
    for(i=0;i<=n;i++){
      g[i]=d[i]=0;
      for(j=0;j<K;j++)fa[i][j]=fe[i][j]=fo[i][j]=0;
    }
    mst=cnt=ed=0;
    for(i=1;i<=m;i++){
      scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
      on[i]=0;
    }
    sort(e+1,e+m+1,cmp);
    for(i=1;i<=n;i++)f[i]=i;
    for(i=1;i<=m;i++){
      x=e[i].x,y=e[i].y,z=e[i].z;
      if(F(x)==F(y))continue;
      on[i]=1;
      f[f[x]]=f[y];
      mst+=z;
      cnt++;
      add(x,y,z),add(y,x,z);
    }
    if(cnt<n-1){
      puts("-1 -1");
      continue;
    }
    dfs(1,0);
    delta=inf;
    for(i=1;i<=m;i++){
      if(on[i])continue;
      z=e[i].z;
      tmp=ask(e[i].x,e[i].y,z&1?fe:fo);
      if(!tmp)continue;
      z-=tmp;
      if(delta>z)delta=z;
    }
    if(delta<inf)ans=mst+delta;else ans=-1;
    if(mst&1)swap(ans,mst);
    printf("%lld %lld\n",mst,ans);
  }
}
/*
3
2 1
1 2 5
3 1
1 3 1
4 4
1 2 1
1 3 1
1 4 1
2 4 2
*/

 

K. Sugar Sweet 3

#include <bits/stdc++.h>
using namespace std;
int A , B , C  , x;
int n ;
const int N = 605;
const int mod = 1e9 + 7;
int fpow(int a,int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = 1LL * ans * a %mod;
        a = 1LL * a * a %mod; b>>= 1;
    }
    return ans;
}
int F[N][N];
// int Ga[N][N] , Gb[N][N], Gc[N][N];
// int dota[N][N] , dotb[N][N] , dotc[N][N];
int dot[N][N];
int Cata[N] ;
int d[N] ;
int t[N * 2] , rt[N * 2] ;
int lm ; ///多项式的项数
int mat[N][N] , rmat[N][N];
int C_(int a,int b) {
    return 1LL * t[a] * rt[b] % mod * rt[a - b] % mod;
}
int A_(int a,int b) {
    return 1LL * t[a] * rt[a - b] % mod;
}
vector<int> get_coe(int n , vector<int> w) { ///已知n个点值[1 to n],求sum{ai * wi} 对应的 di的系数,i from 0 to n - 1
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++) {
            mat[i][j] = fpow(i , j - 1) ; // MAT * A = D
            rmat[i][j] = (i == j) ;
        }
    }
    for(int i = 1;i <= n;i++) {
        int cur = -1;
        for(int j = i ;j <= n;j++) {
            if(mat[j][i]) {cur = j ; break ;}
        }
        for(int j = 1;j <= n;j++) {swap(mat[cur][j] , mat[i][j]) ; swap(rmat[cur][j] , rmat[i][j]) ;}
        int r = fpow(mat[i][i] , mod - 2);
        for(int j = 1;j <= n;j++) {
            if(i == j) continue ;
            int f = (mod - 1LL * mat[j][i] * r %mod) % mod;
            for(int k = 1;k <= n;k++) {mat[j][k] = (mat[j][k] + 1LL * mat[i][k] * f) % mod ; rmat[j][k] = (rmat[j][k] + 1LL * rmat[i][k] * f) % mod;}
        }
        for(int j = 1;j <= n;j++) {
            mat[i][j] = 1LL * mat[i][j] * r % mod;
            rmat[i][j] = 1LL * rmat[i][j] * r % mod;
        }
    }
    // for(int i = 1;i <= n;i++ , printf("\n")) for(int j = 1;j <= n;j++) printf("%d ",rmat[i][j]) ;
    ///A = Rmat * D
    
    vector<int> coe(n) ;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++) {
            coe[j] = (coe[j] + 1LL * w[i] * rmat[i + 1][j + 1]) % mod;
        }
    }
    return coe;
}
 
int main() {
    cin >> A >> B >> C >> x;
    n = A + B + C;
    if(n & 1) {
        cout << 0 ; return 0;
    }
    if(A > n/2 || B > n/2 || C > n/2) {
        cout << 0 ; return 0;
    }
    t[0] = rt[0] = 1;
    for(int i = 1;i <= n + 1;i++) t[i] = 1LL * t[i - 1] * i % mod , rt[i] = fpow(t[i] , mod - 2) ;
    Cata[0] = 1;
    for(int i = 1;i <= n/2;i++) Cata[i] = 1LL * C_(i*2 , i) * fpow(i + 1 , mod - 2) % mod;
 
    //// F[i][j]表示i个主元分j段的方案数,Fi(x)作为其egf
    F[0][0] = 1;
    lm = n / 2 + 1;
    for(int i = 1;i <= n/2;i++) {
        for(int j = 1;j <= i;j++) {
            for(int k = 1;k <= i;k++) { ///最后一段包含的主元个数
                F[i][j] = (F[i][j] + 1LL * F[i - k][j - 1] * Cata[k - 1]) % mod;
            }
            // printf("%d %d : %d\n",i,j,F[i][j]) ;
        }
    }
    for(int i = 0;i <= n/2;i++) {
        for(int j = 0;j <= i;j++) F[i][j] = 1LL * F[i][j] * rt[j] % mod ; ///变成egf
        for(int j = 1;j <= lm;j++) {
            dot[i][j] = 0;
            for(int k = i;k >= 0;k--) dot[i][j] = (1LL * dot[i][j] * j + F[i][k]) % mod;
            ///dot 代表点值
        }
    }
    vector<int> w(n/2 + 1) ;
    for(int i = 0;i <= n/2;i++) w[i] = 1LL * fpow(i , x) * t[i] % mod;
    
    vector<int> coe = get_coe(n/2 + 1 , w) ; /// coe.len = n/2 + 1
    
    
    int ans = 0;
    for(int a = 0;a <= n/2 && a <= A;a++) {
        for(int b = 0;b + a <= n / 2 && b <= B;b++) {
            int c = n / 2 - a - b;
            if(c > C) continue ;
            /// F[a] * F[b] * F[c]
            for(int i = 1;i <= lm;i++) d[i] = 1LL * dot[a][i] * dot[b][i] % mod * dot[c][i] % mod;
            // for(int i = 1;i <= lm;i++) printf("%d ",3LL * d[i] % mod) ; printf("\n") ;
            int sol = 0;
            for(int i = 1;i <= lm;i++) sol = (sol + 1LL * d[i] * coe[i - 1]) % mod;
 
 
			int sol2 = 0;
            for(int ab = 0;ab <= A - a && ab <= b; ab++){
                int ac = (A - a - ab) ;
                int bc = (c - ac) ;
                int ba = (B - b - bc) ;
                int ca = (a - ba) ;
                int cb = (C - c - ca) ;
                if(ac < 0 || bc < 0 || ba < 0 || ca < 0 || cb < 0) continue ;
                sol2 = (sol2 + 1LL * C_(a , ba) * C_(b , ab) % mod * C_(c , ac)) % mod;
            }
            // printf("%d %d %d : %d %d\n",a,b,c,sol,sol2);
 
            ans = (ans + 1LL * sol * sol2) % mod;
        }
    }
    cout << ans << '\n';
}

 

L. Challenge Matrix Multiplication

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef pair<int,int> pii;
int to[N] , fir[N] , nxt[N] ;
bool ok[N];
int cc = 0;
int nc , nodes[N];
void adde(int u,int v) {
    ++cc;
    to[cc] = v;
    nxt[cc] = fir[u];
    fir[u] = cc;
}
 
int in[N] , out[N] ;
int n ,m ;
 
 
int ans[N];
 
 
bool vis[N];
pii fr[N] ;
int cnt = 0;
int qu[N] , l , r;
void bfs(int u) {
    l = 1 , r = 0;
    qu[++r] = u;
    vis[u] = 1;
    while(l <= r) {
        int u = qu[l++];
        cnt++;
        for(int i = fir[u] ; i ; i = nxt[i]) {
            if(!vis[to[i]]) {
                qu[++r] = to[i] ;
                vis[to[i]] = 1;
            }
        }
    }
    return ;
}
int main() {
    ios::sync_with_stdio(false) ; cin.tie(0); cout.tie(0);
    clock_t cl = clock() ;
    cin >>n>>m; //printf("??? %d %d\n",n,m);
    
    for(int i = 1;i <= m;i++) {
        int u , v;cin >> u >> v;
        in[v]++ ; out[u]++;
        adde(u , v);
    }
    for(int i = 1;i <= n;i++) ans[i] = 1;
    int all = m;
    clock_t sum0 = 0 , sum1 = 0;
    while(all) {
        // clock_t a = clock();
        for(int i = 1;i <= n;i++) {
            if(in[i] < out[i]) {
                memset(vis,0,sizeof(vis)) ;
                vis[i] = 1;
                int lst;
                for(int j = i ; j <= n;j++) {
                    if(!vis[j]) continue ;
                    if(in[j] > out[j]) {lst = j ; break ;}
                    for(int x = fir[j] ; x ; x = nxt[x]) {
                        if(!vis[to[x]] && !ok[x]) {
                            vis[to[x]] = 1;
                            fr[to[x]] = {j , x};
                        }
                    }
                }
                
                int u = lst ;
                nc = 0;
                while(u) {
                    nodes[nc++] = u;
                    if(u != i) in[u]--;
                    if(u != lst) out[u]--;
                    if(u == i) break ;
                    ok[fr[u].second] = 1;
                    u = fr[u].first ;
                    all--;
                }
                break ;
            }
        }
        // sum0 += (clock() - a);
        // a = clock() ;
        cnt = 0;
        memset(vis,0,sizeof(vis));
        for(int i = 0;i < nc;i++) {
            bfs(nodes[i]) ;
            ans[nodes[i]] = cnt;
        }
        // static int gg = 0;
        // sum1 += (clock() - a) ;
        // printf("i-th round %d %d\n",++gg , nc) ;
    }
    // cerr << (double)(clock() - cl) / CLOCKS_PER_SEC <<' ' << (double)sum0 / CLOCKS_PER_SEC <<' ' << (double)sum1 / CLOCKS_PER_SEC << '\n';
    // return 0;
    for(int i = 1;i <= n;i++) cout << ans[i] <<' ' ;
    cout << '\n';
}

 

M. Triangles

#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	long long n,a,b;
	cin>>n>>a>>b;
	long long ans=0;
	for(long long r=1;r<=n;r++)
	{
		ans+=r*(r+1);
		if(r*2>n)ans-=(r*2-n)*(r*2-n+1)/2;
	}
	for(long long i=1;i<=b;i++)
	{
		ans-=(a-b+1);
		ans-=max(min(a+1-i,n-a)-(b-i),0ll);
	}
	cout<<ans<<endl;
	return 0;
}

 

标签:include,int,Universal,Cangqian,++,long,ans,Stage,size
From: https://www.cnblogs.com/clrs97/p/18405338

相关文章

  • vue项目利用git commit 触发执行 eslint检查,使用husky 和 lint-staged
    lint-staged安装和使用说明lint-staged是一个插件,为了方便触发eslint,配置哪些文件触发eslintstylelint等安装yarnaddlint-staged创建.lintstagedrc在根目录{"*.vue":"eslint","*.ts":"eslint","*.tsx":"eslint&quo......
  • The 2023 ICPC Asia Nanjing Regional Contest (The 2nd Universal Cup. Stage 11: Na
    C-PrimitiveRoot题意给定p与m(p为质数),已知(g^(P-1))%P==1且g<=m。求g的个数。思路由(g^(P-1))%P==1与异或性质a-b<=a^b<=a+b,可以推出g=((k*p+1)^(p-1))与p*(k-1)+2<=g<=p*(k+1)。又因为g<=m,则当p*(k+1)<=......
  • ServiceStage集成Sermant实现应用的优雅上下线
    作者:聂子雄华为云高级软件工程师摘要优雅上下线旨在确保服务在进行上下线操作时,能够平滑过渡,避免对业务造成影响,保证资源的高效利用。Sermant基于字节码增强的技术实现了应用优雅上下线能力,应用发布与运维平台ServiceStage通过集成Sermant使得应用在进行持续发布时实现无侵入式地......
  • The 1st Universal Cup. Stage 8: Slovenia
    Preface这场其实是昨天打的,但因为今天没训练就摆烂拖到今天才补题和写博客这场题感觉都挺可做的,但前期出题有点慢导致后期没时间了,徐神和祁神赛后20min过了J有点可惜A.Bandits题都没看,不做评价B.CombinationLocks不难发现这题本质就是在0/1串上操作,每次移动到另......
  • Photomator 3.3.22 (macOS Universal) - 照片编辑软件
    Photomator3.3.22(macOSUniversal)-照片编辑软件适用于Mac、iPhone和iPad的终极照片编辑器请访问原文链接:https://sysin.org/blog/photomator/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.orgPhotomator适用于Mac、iPhone和iPad的终极照片编辑器。P......
  • The 3rd Universal Cup. Stage 7- Warsaw
    B.MissingBoundaries给\(N\)个区间,可能存在一些区间的端点不确定。现在你要指定区间的端点,是否可以使得所有不重不漏的覆盖\([1,L]\)首先考虑两个端点都确定的区间,两两之间应该不相交。考虑只有一个端点的区间,对于已经被确定的点,一定不能是在已被覆盖的区间内。其次所有的......
  • The 1st Universal Cup. Stage 7: Zaporizhzhia
    Preface在寝室白兰了一周多后也是终于等到徐神归来开始训练了这场的题感觉比较偏数学了,感觉和之前打的一个Tokyo的OpenCup很像,因此后期挺坐牢的4h左右堪堪写出7题,最后全队RushD结果发现暴力打表都打错了,怎么回事呢A.SquareSum这题在去年暑假前集训数学专题中......
  • [Paper Reading] One-Stage 3D Whole-Body Mesh Recovery with Component Aware Trans
    One-Stage3DWhole-BodyMeshRecoverywithComponentAwareTransformerlink时间:CVPR2023机构:粤港澳大湾区数字经济研究院(IDEA)&&清华大学深圳国际研究生院TL;DR使用一个纯Transformer结构模型(名为OSX)直接预测Body/Hand/Face的参数,避免了之前各模型分开预测后融合复......
  • SRL_STAGES_TO_REG_INPUT
    寄存器级可以通过SLR输入拉出,也可以使用SRL_STAGES_TO_REG_INPUT属性。这提供了对流水线寄存器结构的控制,以在流水线下和流水线上寻址SRL基元的输入侧。架构支持所有架构。适用对象•单元格(get_cell)作为叶级SRL实例。价值观•1:Vivado逻辑优化将从指定的SRL中提取寄存......
  • The 3rd Universal Cup. Stage 1: St. Petersburg Finalized Standings
    C.CherryPicking这道题用了一个类似ODT的题思路。首先我们可以想到是,如果删除某些选手,只有可能会导致区间的合并,不会导致区间的分裂。所以我们可以枚举一下$x$的值,然后找到需要删除的点。用set​维护相同且相邻区间,找到删除点所在的区间后,给区间长度减一。如果区间长度为空......