首页 > 其他分享 >ARC164

ARC164

时间:2023-07-10 12:00:23浏览次数:36  
标签:Tx int ARC164 long MAXN freopen MOD

ARC164

A

考虑先给\(N\)按三进制分解一下

然后对于\(3^m\rightarrow3^{m-1}\),实际上可以加\(2\)的贡献,我们先计算\(N\)最小需要\(S\)

然后可以发现只要\(K-S\)是偶数即可

#include<bits/stdc++.h>
using namespace std;
signed main()
{
  //  freopen("date.in","r",stdin);
  //  freopen("date.out","w",stdout);
   int T;
   long long N,K;
   scanf("%d",&T);
   while(T--)
   {
        scanf("%lld %lld",&N,&K);
        if((N-K)&1)
        {
            printf("No\n");
            continue;
        }

        long long Now=N;
        long long S=0;
        while(Now)
        {
            S+=(Now%3);
            Now/=3;
           // cerr<<Now<<endl;
        }
        if((S<=K)&&(K-S)%2==0)
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
   }

}

B

就是找\(01\)交替然后只有一条相同边的奇环

好像不能直接找环,因为环套环会出问题

直接由并查集维护即可,颜色不同的连边

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+5;
int n,m;
int x,y;
struct Edge{
    int u,v;
}edge[MAXN];
int fa[MAXN];
int c[MAXN];
int find(int x)
{
    if(fa[x]==x)
    {
        return fa[x];
    }
    fa[x]=find(fa[x]);
    return fa[x];
}
void unionn(int i,int j)
{
    fa[find(i)]=find(j);
}
bool found=0;
int main(){
  //  freopen("date.in","r",stdin);
   //  freopen("date.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        edge[i].u=x;
        edge[i].v=y;
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&c[i]);
        fa[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        if(c[edge[i].u]!=c[edge[i].v])
        {
            unionn(edge[i].u,edge[i].v);
        }
    }
    for(int i=1;i<=m;i++)
    {
        if(c[edge[i].u]==c[edge[i].v])
        {
            if(find(edge[i].u)==find(edge[i].v))
            {
                found=1;
            }
        }
    }
    if(found)
    {
        printf("Yes");
    }
    else
    {
        printf("No");
    }
}

C

先假设全部是\(A\)朝上

对于\(A\)来说,翻肯定选\(B_i-A_i\)最大的

对于\(B\),同样也要这样选

由于\(A\)一定会翻\(n\)次,这里我们可以用堆模拟这个过程

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=3e5+5;
int n;
struct node{
    int A,B;
}s[MAXN];
signed main(){
 //   freopen("date.in","r",stdin);
     //freopen("date.out","w",stdout);
    scanf("%lld",&n);
    int Sum=0;
    priority_queue<int>Q;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld %lld",&s[i].A,&s[i].B);
        Sum+=s[i].A;
        Q.push((s[i].B-s[i].A));
    }
    int Op=0;
    while(n--)
    {
        int temp=Q.top();
        Q.pop();
         Sum+=temp;
        Q.push(-temp);
        Op^=1;
    }
    printf("%lld",Sum);
}

D

如果能确定每个点的走的朝向,那其实可以直接抽象为括号匹配,答案就是每对匹配括号的距离之和

一个经典的套路,我们可以把左括号的贡献定义为\(-i\),这样我们就只需要算其合法序列的个数

考虑枚举位置\(i\)前面的\(?\)是\(+\)的数量,然后\(i\)的朝向就确定了,直接组合数算贡献即可

#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
const int MAXN=3005;
int n;
char s[MAXN*2];
int dp[MAXN*2][MAXN*2];
int Pow(int a,int b,int p)
{
    int res=1;
    int base=a;
    while(b)
    {
        if(b&1)
        {
            res=((long long)res*base)%p;
        }
        base=((long long)base*base)%p;
        b>>=1;
    }
    return res;
}
int inv(int a,int p)
{
    return Pow(a,p-2,p);
}
int fac[MAXN*2];
int inv_fac[MAXN*2];
int C(int n,int m)
{
    if(n<m||m<0)
    {
        return 0;
    }
    if((n==m)||(m==0))
    {
        return 1;
    }
    return ((((long long)fac[n]*inv_fac[m])%MOD)*inv_fac[n-m])%MOD;
}
int Prel[MAXN*2];
int Prer[MAXN*2];
int Surl[MAXN*2];
int Surr[MAXN*2];
int Prep[MAXN*2];
int Surp[MAXN*2];
signed main(){
    // freopen("date.in","r",stdin);
    // freopen("date.out","w",stdout);
    scanf("%d",&n);
    scanf("%s",s+1);
    fac[0]=1;
    for(int i=1;i<=2*n;i++)
    {
        fac[i]=((long long)fac[i-1]*i)%MOD;
    }
    inv_fac[2*n]=inv(fac[2*n],MOD);
    for(int i=2*n-1;i>=1;i--)
    {
        inv_fac[i]=((long long)inv_fac[i+1]*(i+1))%MOD;
    }
    int Res=0;
    int Tot=0;
    int Totl=0;
    int Totr=0;
    for(int i=1;i<=2*n;i++)
    {
        Prel[i]=Prel[i-1];
        Prer[i]=Prer[i-1];
        Prep[i]=Prep[i-1];
        if(s[i]=='+')
        {
            Prel[i]++;
            Totl++;
        }
        else if(s[i]=='-')
        {
            Prer[i]++;
            Totr++;
        }
        else
        {
            Prep[i]++;
            Tot++;
        }
    }
    for(int i=2*n;i>=1;i--)
    {
        Surl[i]=Surl[i+1];
        Surr[i]=Surr[i+1];
        Surp[i]=Surp[i+1];
        if(s[i]=='+')
        {
            Surl[i]++;
        }
        else if(s[i]=='-')
        {
            Surr[i]++;
        }
        else
        {
            Surp[i]++;
        }
        
    }
    for(int i=1;i<=2*n;i++)
    {
        if(s[i]!='+')
        {
            int O1=Prel[i-1];
            int O2=Prer[i-1];
            int O3=Surl[i+1];
            int O4=Surr[i+1];
            int O5=Prep[i-1];
            int O6=Surp[i+1];
            int O=O4-O3+O1-O2;
            for(int j=0;j<=O5;j++)
            {
                int Tp=(Totl+j);
                int Np=(n-Tp);
                if(Np>=0)
                {
                    if(O+j-(O5-j)-Np+(O6-Np)<0)
                    {
                        int Tx=((long long)C(O5,j)*C(O6,Np))%MOD;
                        Tx=((long long)Tx*(MOD-i))%MOD;
                   //     printf("%d -%d %d %d %d %d??\n",i,(MOD-Tx)%MOD,O5,O6,j,Np);
                        Res=((long long)Res+Tx)%MOD;
                        
                    }
                    else
                    {
                        int Tx=((long long)C(O5,j)*C(O6,Np))%MOD;
                        Tx=((long long)Tx*(i))%MOD;
                      //  printf("%d %d>??\n",i,Tx);
                        Res=((long long)Res+Tx)%MOD;
                    }
                }
                
            }
        }
        if(s[i]!='-')
        {
            int O1=Prel[i-1];
            int O2=Prer[i-1];
            int O3=Surl[i+1];
            int O4=Surr[i+1];
            int O5=Prep[i-1];
            int O6=Surp[i+1];
            int O=O4-O3+O1-O2;
            for(int j=0;j<=O5;j++)
            {
                int Tp=(Totl+j);
                if(s[i]=='?')
                {
                    Tp++;
                }
                int Np=(n-Tp);
                if(Np>=0)
                {
                    if(O+j-(O5-j)-Np+(O6-Np)>0)
                    {
                        int Tx=((long long)C(O5,j)*C(O6,Np))%MOD;
                        Tx=((long long)Tx*(MOD-i))%MOD;
                     //   printf("%d -%d??\n",i,(MOD-Tx)%MOD);
                        Res=((long long)Res+Tx)%MOD;
                    }
                    else
                    {
                        int Tx=((long long)C(O5,j)*C(O6,Np))%MOD;
                        Tx=((long long)Tx*(i))%MOD;
                 //       printf("%d %d>??\n",i,Tx);
                        Res=((long long)Res+Tx)%MOD;
                    }
                }
            }
        }
    }
    printf("%d\n",Res);
}

E

对于每个线段树的结点\(i\),我们记录分割点\(P_i\)

可以发现,对于区间\([l,r]\),它询问到的最大深度就是\(l-1,r\)分割点对应的节点的最大深度,因为对于中间的那段区间实际上一定是在其上面覆盖的

对于第一问,我们可以计算需要哪些分割点,然后在二叉树上一层一层铺即可

对于第二问,可以发现如果如果我们的分割点在\(d-1\),那访问次数实际上为在\(d-1\)深度分割点的数量\(\times2\)

于是我们要让位于\(d-1\)的分割点尽量少

对于\(d-1\)的一颗满二叉树,我们可以发现如果以\(dfs\)序标号,\(d-1\)的点都是奇数

据此我们可以\(dp\),设\(dp_{i,j}\)为前\(i\)需要的分割点走了\(j\)个点的最小次数,奇数位置放要记录贡献,偶数不用

#include<bits/stdc++.h>
using namespace std;
int n,Q;
int l,r;
int C[5005];
vector<int>V;
int dp[5005][5005];
signed main(){
        // freopen("date.in","r",stdin);
        // freopen("date.out","w",stdout);
    scanf("%d %d",&n,&Q);
    for(int i=1;i<=Q;i++)
    {
        scanf("%d %d",&l,&r);
        C[l-1]++;
        C[r]++;
    }
    int d=0;
    V.clear();
    for(int i=1;i<n;i++)
    {   
        if(C[i])
        {
            V.push_back(C[i]);
        }
    }
    for(int i=0;i<=20;i++)
    {
        if(((1<<i)-1)>=((int)V.size()))
        {
            d=i;
            break;
        }
    }
    if(d==0)
    {
        printf("%d %d\n",0,Q);
        return 0;
    }
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;
    for(int i=0;i<V.size();i++)
    {
        for(int j=0;j<(1<<d);j++)
        {
            if((j%2==0))
            {
                dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+V[i]);
                dp[i][j+1]=min(dp[i][j+1],dp[i][j]);
            }   
            else
            {
                dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]);
            }
        }
    }
    int Res=0x3f3f3f3f;
    for(int i=0;i<(1<<d);i++)
    {
        Res=min(Res,dp[V.size()][i]);
    }
    //printf("%d %d???\n",V.size(),(1<<d)-1);
    printf("%d %d\n",d,2*Res);
}

标签:Tx,int,ARC164,long,MAXN,freopen,MOD
From: https://www.cnblogs.com/kid-magic/p/17540677.html

相关文章