2022-2023 ICPC, Asia Yokohama Regional Contest 2022（题解）

2022-2023 ICPC, Asia Yokohama Regional Contest 2022

文章目录

  • A. Hasty Santa Claus
  • B. Interactive Number Guessing
  • C. Secure the Top Secret
  • D. Move One Coin
  • E. Incredibly Cute Penguin Chicks
  • F. Make a Loop
  • G. Remodeling the Dungeon
  • H. Cake Decoration
  • I. Quiz Contest
  • J. Traveling Salesperson in an Island
  • K. New Year Festival

A. Hasty Santa Claus

思路：贪心。将区间优先按照 a i a_i ai​其次 b i b_i bi​大小进行排序，然后从第 1 1 1天枚举至第 31 31 31天，每次取出前 k k k个house进行拜访。复杂度 O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2​n)。

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson (k<<1)
#define rson (k<<1)+1
#define mid ((l+r)/2)
#define sz(x) int(x.size())
#define pii pair<int,int>
#define bit bitset<100000>
using namespace std;
const int MAX=3e5+10;
const int MOD=998244353; //G=3
const int INF=INT_MAX;
const double PI=acos(-1.0);
typedef int64_t ll;
struct lenka{int l,r,idx;};
bool cmp(lenka a,lenka b){return a.l==b.l?a.r<b.r:a.l<b.l;}
int ans[1100];
int solve()
{
    int n,k;
    cin>>n>>k;
    vector<lenka>a;
    a.resize(n);
    for(int i=0;i<n;i++)scanf("%d%d",&a[i].l,&a[i].r),a[i].idx=i;
    sort(a.begin(),a.end(),cmp);
    for(int i=1;i<=31;i++)
    {
        vector<int>v;
        int m=k;
        for(int j=0;j<sz(a)&&m;j++)
        {
            if(i<a[j].l)continue;
            v.push_back(j);
            ans[a[j].idx]=i;
            m--;
        }
        reverse(v.begin(),v.end());
        for(int j:v)a.erase(a.begin()+j);
        for(auto &j:a)j.l=max(j.l,i+1);
        sort(a.begin(),a.end(),cmp);
    }
    for(int i=0;i<n;i++)printf("%d\n",ans[i]);
    return 1;
}
int main()
{
    int T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}

B. Interactive Number Guessing

思路:考虑一位一位确定，二分区间 [ 0 , 9 ] [0,9] [0,9]，当 x i + m i d ≥ 10 x_i+mid\ge10 xi​+mid≥10时，会产生进位，数位和就会变少，否则会变多。

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson (k<<1)
#define rson (k<<1)+1
#define mid ((l+r)/2)
#define sz(x) int(x.size())
#define pii pair<int,int>
#define bit bitset<100000>
using namespace std;
const int MAX=3e5+10;
const int MOD=998244353; //G=3
const int INF=INT_MAX;
const double PI=acos(-1.0);
typedef int64_t ll;
ll ask(ll x)
{
    cout<<"query "<<x<<endl;
    cin>>x;
    return x;
}
int solve()
{
    ll ans=0,pre=1;
    ll s=ask(0);
    for(ll i=0;i<18;i++)
    {
        ll l=0,r=9;
        while(r>=l)
        {
            ll ret=ask(pre*mid)-s;
            if(ret<0)r=mid-1;
            if(ret>0)l=mid+1;
            if(ret==0)
            {
                if(mid==9)ans+=pre;
                break;
            }
        }
        ans+=pre*(9-mid);
        pre*=10;
    }
    cout<<"answer "<<ans<<endl;
    return 1;
}
int main()
{
    int T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}

C. Secure the Top Secret

题解

D. Move One Coin

思路:考虑将硬币的坐标排序后，用坐标的差分数组是否相同来判断是否匹配，因为至多只需移动一枚硬币即可匹配，所以2个图的差分数组不同项最多为2个，且一张图一个，当碰到不同项时，直接枚举删除硬币后判断是否匹配即可。复杂度 O ( H ∗ W ) O(H*W) O(H∗W)。

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson (k<<1)
#define rson (k<<1)+1
#define mid ((l+r)/2)
#define sz(x) int(x.size())
#define pii pair<int,int>
#define bit bitset<100000>
using namespace std;
const int MAX=1e6+10;
const int MOD=998244353; //G=3
const int INF=INT_MAX;
const double PI=acos(-1.0);
typedef int64_t ll;
struct lenka
{
    int n,m;
    char s[510][510];
    void read()
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)scanf("%s",s[i]);
    }
    void rota()
    {
        char tmp[510][510];
        for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)tmp[i][j]=s[j][i];
        swap(n,m);
        for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)s[i][j]=tmp[i][m-1-j];
    }
    vector<pii> seri()
    {
        vector<pii>v;
        for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            if(s[i][j]!='o')continue;
            v.push_back({i,j});
        }
        return v;
    }
};
pii operator-(pii a,pii b){return {a.fi-b.fi,a.se-b.se};}
pii operator+(pii a,pii b){return {a.fi+b.fi,a.se+b.se};}
int print(vector<pii> a){for(pii &kv:a)printf("%d %d\n",kv.se,kv.fi);return 1;}
int check(vector<pii> &a,vector<pii> &b)
{
    set<pii>s;
    for(int i=1;i<sz(a);i++)s.insert(a[i]-a[0]);
    for(int i=1;i<sz(b);i++)
    {
        if(s.count(b[i]-b[0]))s.erase(b[i]-b[0]);
        else s.insert(b[i]-b[0]);
    }
    return s.size();
}
pii get(vector<pii> &a,vector<pii> &b)
{
    set<pii>s;
    for(int i=1;i<sz(a);i++)s.insert(a[i]-a[0]);
    for(int i=1;i<sz(b);i++)s.erase(b[i]-b[0]);
    return *s.begin();
}
int f(vector<pii> a,vector<pii> b)
{
    if(check(a,b)==0)return print({a[0],a[0]});
    if(sz(a)==2)return print({a[1],b[1]-b[0]+a[0]});
    if(check(a,b)>2)
    {
        auto ta=a,tb=b;
        ta.erase(ta.begin());
        if(check(ta,b)==1)return print({a[0],ta[0]+get(b,ta)});
        tb.erase(tb.begin());
        if(check(tb,a)==1)return print({a[0]+get(a,tb),a[0]-(b[1]-b[0])});
        if(check(ta,tb)==0)return print({a[0],a[1]-(b[1]-b[0])});
        return 0;
    }
    assert(check(a,b)==2);
    print({a[0]+get(a,b),a[0]+get(b,a)});
    return 1;
}
int solve()
{
    lenka a,b;
    a.read();
    b.read();
    for(int i=0;i<6;i++)
    {
        if(f(a.seri(),b.seri()))return 0;
        b.rota();
    }
    return 0;
}
int main()
{
    int T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}

E. Incredibly Cute Penguin Chicks

思路：用 C [ i ] , I [ i ] , P [ i ] C[i],I[i],P[i] C[i],I[i],P[i]分别代表各字母数量的前缀和，用 d [ i ] d[i] d[i]表示 [ 0 , i ] [0,i] [0,i]的方案数，则 d i = ∑ d j d_i=\sum d_j di​=∑dj​，当且仅当以下任一条件满足

  1. C i − C j = I i − I j , P i − P j > C i − C j C_i-C_j=I_i-I_j,P_i-P_j>C_i-C_j Ci​−Cj​=Ii​−Ij​,Pi​−Pj​>Ci​−Cj​
  2. C i − C j = P i − P j , I i − I j > C i − C j C_i-C_j=P_i-P_j,I_i-I_j>C_i-C_j Ci​−Cj​=Pi​−Pj​,Ii​−Ij​>Ci​−Cj​
  3. I i − I j = P i − P j , C i − C j > I i − I j I_i-I_j=P_i-P_j,C_i-C_j>I_i-I_j Ii​−Ij​=Pi​−Pj​,Ci​−Cj​>Ii​−Ij​

转移复杂度为 O ( n 2 ) O(n^2) O(n2)，考虑优化，将上面条件式子转化一下得

  1. C i − I i = C j − I j , P i − C i > P j − C j C_i-I_i=C_j-I_j,P_i-C_i>P_j-C_j Ci​−Ii​=Cj​−Ij​,Pi​−Ci​>Pj​−Cj​
  2. C i − P i = C j − P j , I i − C i > I j − C j C_i-P_i=C_j-P_j,I_i-C_i>I_j-C_j Ci​−Pi​=Cj​−Pj​,Ii​−Ci​>Ij​−Cj​
  3. I i − P i = I j − P j , C i − I i > C j − I j I_i-P_i=I_j-P_j,C_i-I_i>C_j-I_j Ii​−Pi​=Ij​−Pj​,Ci​−Ii​>Cj​−Ij​

如此我们只需分别记住在 { C i − I i , P i − C i } , { C i − P i , I i − C i } , { I i − P i , C i − I i } \{C_i-I_i,P_i-C_i\},\{C_i-P_i,I_i-C_i\},\{I_i-P_i,C_i-I_i\} {Ci​−Ii​,Pi​−Ci​},{Ci​−Pi​,Ii​−Ci​},{Ii​−Pi​,Ci​−Ii​}下的 d i d_i di​的值，再根据转化后的式子去dp转移。
因为式子中需要判断大小，我们可以预处理出所有可能的值并离散化，dp转移时二分查找求区间和，并记录下当前dp值，用树状数组来求区间和以及单点修改。复杂度 O ( n log ⁡ 2 n ) O(n\log_2n) O(nlog2​n)。

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson (k<<1)
#define rson (k<<1)+1
#define mid ((l+r)/2)
#define sz(x) int(x.size())
#define pii pair<ll,ll>
#define bit bitset<100000>
using namespace std;
const int MAX=1e6+10;
const int MOD=998244353; //G=3
const int INF=INT_MAX;
const double PI=acos(-1.0);
typedef int64_t ll;
struct lenka
{
    map<int,vector<int>> ma;
    map<int,map<int,int>> idx;
    void push(int a,int b,int c){ma[a-b].push_back(c-a);}
    void uniq()
    {
        for(auto &kv:ma)
        {
            auto &v=kv.se;
            v.push_back(-MAX);
            v.push_back(0);
            sort(v.begin(),v.end());
            v.erase(unique(v.begin(),v.end()),v.end());
            for(int i=0;i<sz(v);i++)idx[kv.fi][v[i]]=i;
            fill(v.begin(),v.end(),0);
        }
    }
    void add(int a,int b,int c,int y)
    {
        auto &v=ma[a-b];
        int x=idx[a-b][c-a];
        while(x+1<=sz(v))
        {
            v[x]+=y;
            v[x]%=MOD;
            x+=x&(-x);
        }
    }
    int ask(int a,int b,int c)
    {
        auto &v=ma[a-b];
        int x=idx[a-b][c-a]-1;
        int sum=0;
        while(x>0)(sum+=v[x])%=MOD,x-=x&(-x);
        return sum;
    }
}v[3];
char s[MAX];
int solve()
{
    scanf("%s",s);
    int n=strlen(s);
    int sc=0,si=0,sp=0;
    for(int i=0;i<n;i++)
    {
        sc+=s[i]=='C';
        si+=s[i]=='I';
        sp+=s[i]=='P';
        v[0].push(si,sp,sc);
        v[1].push(sc,sp,si);
        v[2].push(sc,si,sp);
    }
    for(int i=0;i<3;i++)
    {
        v[i].uniq();
        v[i].add(0,0,0,1);
    }
    sc=si=sp=0;
    for(int i=0;i<n;i++)
    {
        sc+=s[i]=='C';
        si+=s[i]=='I';
        sp+=s[i]=='P';
        int ac=v[0].ask(si,sp,sc);
        int ai=v[1].ask(sc,sp,si);
        int ap=v[2].ask(sc,si,sp);
        int sum=((ac+ai)%MOD+ap)%MOD;
        if(i+1==n)return printf("%d\n",sum);
        v[0].add(si,sp,sc,sum);
        v[1].add(sc,sp,si,sum);
        v[2].add(sc,si,sp,sum);
    }
    return 0;
}
int main()
{
    int T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}

F. Make a Loop

思路：因为最后所有弧要连接闭合，那么最终这些圆弧的向量和一定为0。我们可以依次将所有弧区分为4个部分，如下图:
在这里插入图片描述
假设图中起点为 S S S，方向为逆时针方向。绿色部分圆弧向量为 ( − r i , − r i ) (-r_i,-r_i) (−ri​,−ri​)，半径总和为 S 1 S_1 S1​。黄色部分向量为 ( r i , − r i ) (r_i,-r_i) (ri​,−ri​)，半径总和为 S 2 S_2 S2​。蓝色部分向量为 ( r i , r i ) (r_i,r_i) (ri​,ri​)，半径总和为 S 3 S_3 S3​。红色部分向量为 ( − r i , r i ) (-r_i,r_i) (−ri​,ri​)，半径总和为 S 4 S_4 S4​。由最终向量和为0得 S 1 + S 4 = S 2 + S 3 S 1 + S 2 = S 4 + S 3 S 1 + S 2 + S 4 + S 3 = ∑ 1 ≤ i ≤ n r i S_1+S_4=S_2+S_3\\ S_1+S_2=S_4+S_3\\ S_1+S_2+S_4+S_3=\sum_{1\le i\le n} r_i S1​+S4​=S2​+S3​S1​+S2​=S4​+S3​S1​+S2​+S4​+S3​=1≤i≤n∑​ri​由上面的式子可得 S 1 + S 4 = S 2 + S 3 = S 1 + S 2 = S 3 + S 4 = ∑ r i 2 S_1+S_4=S_2+S_3=S_1+S_2=S_3+S_4=\frac{\sum r_i}2 S1​+S4​=S2​+S3​=S1​+S2​=S3​+S4​=2∑ri​​，同时因为最终所有弧会链接闭合，角度和为360°，所以4个部分里圆弧个数的奇偶性一定相等，那么任意2个部分的圆弧个数和一定是偶数。
综上所述，如果存在至少4种方法，使得我们从所有圆弧中选出偶数个圆弧的半径和，为总半径和的一半时，那我们一定有办法将所有圆弧首尾相连形成闭环。
采用dp， d [ 0 / 1 ] [ s ] d[0/1][s] d[0/1][s]表示选择偶数 / / /奇数个弧且半径和为 s s s的方案数，当 d [ 0 ] [ ∑ r i 2 ] ≥ 4 d[0][\frac{\sum r_i}2]\ge4 d[0][2∑ri​​]≥4时为Yes。复杂度 O ( n ∑ r i ) O(n\sum r_i) O(n∑ri​)。

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson (k<<1)
#define rson (k<<1)+1
#define mid ((l+r)/2)
#define sz(x) int(x.size())
#define pii pair<ll,ll>
using namespace std;
const int MAX=500010;
const int MOD=1e9+7;
const double PI=acos(-1.0);
typedef long long ll;
int d[2][MAX];
int solve()
{
    int n;
    cin>>n;
    vector<int>a;
    a.resize(n);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    int m=accumulate(a.begin(),a.end(),0);
    if(m%2)return puts("No");
    memset(d,0,sizeof d);
    d[0][0]=1;
    m/=2;
    for(int i=0;i<n;i++)
    for(int j=m;j>=a[i];j--)
    {
        d[0][j]=min(d[0][j]+d[1][j-a[i]],4);
        d[1][j]=min(d[1][j]+d[0][j-a[i]],4);
    }
    return puts(d[0][m]==4?"Yes":"No");
}
int main()
{

    int T=1;
//    cin>>T;
    while(T--)solve();
    return 0;
}

G. Remodeling the Dungeon

思路:图为一棵树，入口和出口之间只有一条唯一路径，以入口为根节点建图，那我们只需要从出口开始枚举删除出口至入口路径上的边，删一条边会将图分割为底部和根2棵子树，因为是从底部向根枚举，所以底部每次都会新加入一些点，在删边的时候，我们只需要枚举这些新加入的点对答案的贡献即可。复杂度 O ( h ∗ w ) O(h*w) O(h∗w)。

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson (k<<1)
#define rson (k<<1)+1
#define mid ((l+r)/2)
#define sz(x) int(x.size())
#define pii pair<int,int>
#define bit bitset<100000>
using namespace std;
const int MAX=3e5+10;
const int MOD=998244353; //G=3
const int INF=INT_MAX;
const double PI=acos(-1.0);
typedef int64_t ll;
vector<int>e[MAX];
vector<int>wall[MAX];
int fa[MAX],vis[MAX],d[MAX];
void dfs(int k,int f)
{
    d[k]=d[f]+1;
    fa[k]=f;
    vis[k]=1;
    for(int son:e[k])if(son!=f)dfs(son,k);
}
void get(int k,int from, vector<int> &v)
{
    vis[k]=0;
    v.push_back(k);
    for(int son:e[k])
    {
        if(son==fa[k]||son==from)continue;
        get(son,from,v);
    }
}
int ans=0;
void cal(int k,int from,int dep)
{
    if(k==0)return;
    vector<int>v;
    get(k,from,v);
    for(int i:v)
    for(int j:wall[i])
    {
        if(vis[j]==0)continue;
        ans=max(ans,d[j]+d[i]-d[k]+dep-d[k]+1);
    }
    cal(fa[k],k,dep);
}
int solve()
{
    int n,m;
    cin>>n>>m;
    vector<string>s;
    s.resize(2*n+1);
    for(string &i:s)cin>>i;
    auto id=[m](int x,int y){return ((x-1)/2)*m+(y-1)/2+1;};
    int h=2*n+1;
    int w=2*m+1;
    memset(wall,0,sizeof wall);
    for(int i=1;i<h;i+=2)
    for(int j=1;j<w;j+=2)
    {
        if(j+2<w)
        {
            int x=id(i,j),y=id(i,j+2);
            if(s[i][j+1]=='.')
            {
                e[x].push_back(y);
                e[y].push_back(x);
            }
            else
            {
                wall[x].push_back(y);
                wall[y].push_back(x);
            }
        }
        if(i+2<h)
        {
            int x=id(i,j),y=id(i+2,j);
            if(s[i+1][j]=='.')
            {
                e[x].push_back(y);
                e[y].push_back(x);
            }
            else
            {
                wall[x].push_back(y);
                wall[y].push_back(x);
            }
        }
    }
    memset(d,0,sizeof d);
    memset(fa,0,sizeof fa);
    memset(vis,0,sizeof vis);
    dfs(1,0);
    ans=d[n*m];
    cal(n*m,0,d[n*m]);
    return printf("%d\n",ans);
}
int main()
{
    int T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}

H. Cake Decoration

思路:考虑构造四个数 a , b , c , d a,b,c,d a,b,c,d  并使  a < b < c < d a<b<c<d a<b<c<d。我们枚举 a , b a,b a,b，可以得到 c ∗ d c*d c∗d的值为 s = X a ∗ b s=\frac X{a*b} s=a∗bX​，要满足  b < c < d b<c<d b<c<d 那么 c c c的值域即为 [ b + 1 , ⌊ s ⌋ ] [b+1,\lfloor\sqrt s\rfloor] [b+1,⌊s ​⌋]。然后考虑计算以下6情况的方案数

  1. L ≤ a + b < R L\le a+b\lt R L≤a+b<R
  2. L ≤ a + c < R L\le a+c\lt R L≤a+c<R
  3. L ≤ a + d < R L\le a+d\lt R L≤a+d<R
  4. L ≤ b + c < R L\le b+c\lt R L≤b+c<R
  5. L ≤ b + d < R L\le b+d\lt R L≤b+d<R
  6. L ≤ c + d < R L\le c+d\lt R L≤c+d<R

其中1-5种方案均包含 a , b a,b a,b，我们可以通过 L , R , a , b L,R,a,b L,R,a,b反推出方案数。
第6种方案只知道 c c c的值域，因为 c < d c<d c<d 且  c + d c+d c+d 的和满足单调性，可以用二分求出上下界得出方案数。枚举 a , b a,b a,b复杂度 O ( X ) O(\sqrt X) O(X ​)，二分复杂度 O ( log ⁡ 2 X ) O(\log_2X) O(log2​X)，总复杂度 O ( X log ⁡ 2 X ) O(\sqrt X\log_2X) O(X ​log2​X)。

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson (k<<1)
#define rson (k<<1)+1
#define mid ((l+r)/2)
#define sz(x) int(x.size())
#define pii pair<ll,ll>
#define bit bitset<100000>
using namespace std;
const int MAX=1e7+10;
const int MOD=998244353; //G=3
const int INF=INT_MAX/2;
const double PI=acos(-1.0);
typedef int64_t ll;
void add(ll &x,ll y){x=(x+max(0ll,y%MOD))%MOD;}
ll cal(ll X,ll R)
{
    R--;
    ll ans=0;
    for(ll a=1;a*(a+1)*(a+2)*(a+3)<=X;a++)
    for(ll b=a+1;a*b*(b+1)*(b+2)<=X;b++)
    {
        ll s=X/a/b;
        ll m=sqrt(s);
        while(m*(m+1)<=s)m++;
        while(m*(m+1)>s)m--;
        if(m<=b)continue;
        if(a+b<=R)add(ans,m-b);//a,b
        add(ans,min(m,R-a)-b); //a,c
        add(ans,min(m,R-b)-b); //b,c
        if(a<R)
        {
            ll l=max(b+1,s/(R-a));
            l+=(s/l+a>R);
            add(ans,m-l+1); //a,d
        }
        if(b<R)
        {
            ll l=max(b+1,s/(R-b));
            l+=(s/l+b>R);
            add(ans,m-l+1); //b,d
        }
        ll l=b+1,r=m,down=m+1;
        while(r>=l)
        {
            ll x=mid,y=s/mid;
            if(x+y>R)l=mid+1;
            else down=mid,r=mid-1;
        }
        add(ans,m-down+1);// c,d
    }
    return 4*ans%MOD;
}
int solve()
{
    ll X,L,R;
    cin>>X>>L>>R;
    return printf("%lld\n",(cal(X,R)-cal(X,L)+MOD)%MOD);
}
int main()
{
    int T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}

I. Quiz Contest

思路:先按照正常思路解题，然后考虑优化。依次遍历第 i i i个competitor，假设该选手在第 k k k题获胜，那么第 i i i个选手获胜的方案数为 A k − b i ∗ ( k − 1 ) ! ∗ b i ∗ C a i b i ∗ ( m − 1 − k ) ! \red{A_{k-b_i}*(k-1)!}*b_i*C_{a_i}^{bi}* \green{(m-1-k)!} Ak−bi​​∗(k−1)!∗bi​∗Cai​bi​∗(m−1−k)!其中红色部分式子代表 [ 1 , k − 1 ] [1,k-1] [1,k−1]题的排列数，中间黑色式子代表第 k k k题的排列数，绿色部分代表 [ k + 1 , m ] [k+1,m] [k+1,m]题目的排列数。
而 A k − b i \red{A_{k-b_i}} Ak−bi​​代表从除 a i a_i ai​之外的其余题目中选出 k − b i k-b_i k−bi​个题目，且其他选手均不会比 i i i提前获胜的方案数(其他选手不可以提前答对所有 b b b个题目)。那么 A A A就需要dp来求了，用 d [ j ] [ g ] d[j][g] d[j][g]表示从前 j j j个选手的题目中选出 g g g个题目的合法方案数，转移方程如下： d j , g = ∑ p = 0 b j − 1 d j − 1 , g − p ∗ C a j p d_{j,g}=\sum_{p=0}^{b_j-1} d_{j-1,g-p}*C_{a_j}^p dj,g​=p=0∑bj​−1​dj−1,g−p​∗Caj​p​知道了在第 k k k题获胜的方案数后，那么选手 i i i获胜的总方案数为 = ∑ k = b i A k − b i ∗ ( k − 1 ) ! b i ∗ C a i b i ∗ ( m − 1 − k ) ! = b i ∗ C a i b i ∗ ∑ k = b i A k − b i ∗ ( k − 1 ) ! ∗ ( m − 1 − k ) ! \begin{aligned}&=\sum_{k=b_i}A_{k-b_i}*(k-1)!b_i*C_{a_i}^{bi}* (m-1-k)!\\ &=b_i*C_{a_i}^{bi}*\sum_{k=b_i}A_{k-b_i}*(k-1)!*(m-1-k)!\end{aligned} ​=k=bi​∑​Ak−bi​​∗(k−1)!bi​∗Cai​bi​∗(m−1−k)!=bi​∗Cai​bi​∗k=bi​∑​Ak−bi​​∗(k−1)!∗(m−1−k)!​其中 d p dp dp复杂度是 O ( n ∗ m ∗ b j ) O(n*m*b_j) O(n∗m∗bj​)，后面统计答案还需要遍历 k k k，复杂度 O ( n ∗ k ) O(n*k) O(n∗k)，无法通过。
观察上面2个式子，均满足卷积性质，于是我们可以先通过分治NTT，预处理出 A A A，并记录分治的中间结果(因为 ∑ b i ≤ ∑ a i = m \sum b_i\le \sum a_i=m ∑bi​≤∑ai​=m，所以时间和空间复杂度均为 O ( m log ⁡ 2 2 ( m ) ) O\big(m\log_2^2(m)\big) O(mlog22​(m))。
预处理出 A A A的分治结果后，再第二次通过分治，利用NTT结合第一次分治处理的 A A A结果，依次计算出每个玩家 i i i的获胜总方案数，因为这次是从上至下计算， A A A的结果数量是逐渐减小的，所以每次NTT计算出来的结果有很多对一下层都是无用的，可以优化删掉，复杂度 O ( m log ⁡ 2 2 ( m ) ) O\big(m\log_2^2(m)\big) O(mlog22​(m))。

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson (k<<1)
#define rson (k<<1)+1
#define mid ((l+r)/2)
#define sz(x) int(x.size())
#define pii pair<ll,ll>
#define bit bitset<100000>
using namespace std;
const int MAX=2e6+10;
const int MOD=998244353; //G=3
const int INF=INT_MAX/2;
const double PI=acos(-1.0);
typedef int64_t ll;
ll POW(ll x,ll n)
{
    ll ret=1;
    while(n)
    {
        if(n&1)ret=ret*x%MOD;
        x=x*x%MOD;
        n>>=1;
    }
    return ret;
}
void NTT(vector<ll>& p,ll len,int tag)
{
    auto rev=[](ll x,ll len){
        ll ret=0;
        for(ll i=0;(1<<i)<len;i++)
        {
            ret<<=1;
            if(x&(1<<i))ret|=1;
        }
        return ret;
    };
    for(int i=0;i<len;i++)
    {
        ll x=rev(i,len);
        if(i<x)swap(p[i],p[x]);
    }
    for(int i=1;i<len;i<<=1)
    {
        ll wn=POW(3,(MOD-1)/(2*i));
        if(tag==-1)wn=POW(wn,MOD-2);
        for(int j=0;j<len;j+=i*2)
        {
            ll w=1;
            for(int k=0;k<i;k++)
            {
                ll x=p[j+k];
                ll y=w*p[j+k+i]%MOD;
                p[j+k]=(x+y)%MOD;
                p[j+k+i]=(x-y+MOD)%MOD;
                w=w*wn%MOD;
            }
        }
    }
    if(tag==-1)for(int i=0,x=POW(len,MOD-2);i<len;i++)p[i]=p[i]*x%MOD;
}
vector<ll> mul(vector<ll> a,vector<ll> b)
{
    int n=a.size();
    int m=b.size();
    ll len=1;
    while(len<n+m)len*=2;
    a.resize(len);
    b.resize(len);
    NTT(a,len,1);
    NTT(b,len,1);
    for(int i=0;i<len;i++)a[i]=a[i]*b[i]%MOD;
    NTT(a,len,-1);
    a.resize(n+m-1);
    return a;
}
ll fac[MAX],inv[MAX];
ll C(int n,int m){return fac[n]*inv[m]%MOD*inv[n-m]%MOD;}
ll a[MAX],b[MAX];
vector<ll>A[MAX];
void init(int k,int l,int r) //预处理出dp结果
{
    if(l==r)
    {
        for(int i=0;i<b[r];i++)A[k].push_back(C(a[r],i));
        return;
    }
    init(lson,l,mid);
    init(rson,mid+1,r);
    A[k]=mul(A[lson],A[rson]);
}
vector<ll>ans;
void cal(int k,int l,int r,const vector<ll> &p)
{
    if(l==r)return ans.push_back(C(a[r],b[r])%MOD*b[r]%MOD*p[b[r]-1]%MOD);
    vector<ll> L=p,R=p;
    reverse(A[lson].begin(),A[lson].end());
    reverse(A[rson].begin(),A[rson].end());
    L=mul(L,A[rson]);
    R=mul(R,A[lson]);
    L.erase(L.begin(),L.begin()+A[rson].size()-1);//删除无用结果
    R.erase(R.begin(),R.begin()+A[lson].size()-1);
    L.resize(A[lson].size()); //精简优化结果
    R.resize(A[rson].size());
    cal(lson,l,mid,L);
    cal(rson,mid+1,r,R);
}
int solve()
{
    int n,m;
    cin>>n>>m;
    fac[0]=inv[0]=inv[1]=1;
    for(int i=1;i<=m;i++)fac[i]=fac[i-1]*i%MOD;
    for(int i=2;i<=m;i++)inv[i]=inv[MOD%i]*(MOD-MOD/i)%MOD;
    for(int i=1;i<=m;i++)inv[i]=inv[i]*inv[i-1]%MOD;
    for(int i=1;i<=n;i++)scanf("%lld",a+i);
    for(int i=1;i<=n;i++)scanf("%lld",b+i);
    init(1,1,n);
    vector<ll>p;
    for(int i=0;i<m;i++)p.push_back(fac[i]*fac[m-1-i]%MOD);
    cal(1,1,n,p);
    for(ll i:ans)printf("%lld\n",i);
    return 0;
}
int main()
{
    int T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}

J. Traveling Salesperson in an Island

题解

K. New Year Festival

思路:首先将所有 x x x坐标排序去重，可以想到最终状态所有事件会被分组，且每一组一定是由一件件首尾相接的事件组合而成，且该组事件的起点或终点一定是恰好位于某个 x i x_i xi​上。
n ≤ 11 n\le11 n≤11，考虑状压dp，先预处理出

  1. l [ i ] [ S ] l[i][S] l[i][S]，代表以 x i x_i xi​为事件起点，事件状态为 S S S的一组事件的最小花费，转移方程为 l i , S = min ⁡ k + 2 j = S ( l i , k + l c o s t j ) l_{i,S}=\min_{k+2^j=S}(l_{i,k}+lcost_j) li,S​=k+2j=Smin​(li,k​+lcostj​)
  2. r [ i ] [ S ] r[i][S] r[i][S]，代表以 x i x_i xi​为事件终点，事件状态为 S S S的一组事件的最小花费，转移方程为 r i , S = min ⁡ k + 2 j = S ( r i , k + r c o s t j ) r_{i,S}=\min_{k+2^j=S}(r_{i,k}+rcost_j) ri,S​=k+2j=Smin​(ri,k​+rcostj​)
  3. f [ i ] [ j ] [ S ] f[i][j][S] f[i][j][S]，代表在 [ x i , x j ] [x_i,x_j] [xi​,xj​]区间的两个端点处，安排状态为 S S S的所有事件的最小花费，转移方程为 f i , j , S = min ⁡ g + h = S ( l i , g + r j , h ) f_{i,j,S}=\min_{g+h=S}(l_{i,g}+r_{j,h}) fi,j,S​=g+h=Smin​(li,g​+rj,h​)

预处理好后，我们用 d [ i ] [ S ] d[i][S] d[i][S]代表在区间 [ x 0 , x i ] [x_0,x_i] [x0​,xi​]内安排好状态为 S S S的所有事件的最小花费，来进行最后的dp处理，转移方程如下: d j , S = min ⁡ g + h = S ( d i , g + f i , j , h ) d_{j,S}=\min_{g+h=S} (d_{i,g}+f_{i,j,h}) dj,S​=g+h=Smin​(di,g​+fi,j,h​)
因为事件的结束时间可以超出 x i x_i xi​，所以最终答案为 a n s = min ⁡ g + h = 2 n − 1 d i , g + l i , h ans=\min_{g+h=2^n-1} d_{i,g}+l_{i,h} ans=g+h=2n−1min​di,g​+li,h​
其中枚举子集复杂度为 O ( 3 n ) O(3^n) O(3n)，枚举区间端点复杂度为 O ( ∑ 2 m i ) O(\sum^2 m_i) O(∑2mi​)，总复杂度 O ( 3 n ∗ ∑ 2 m i ) O(3^n*\sum^2 m_i) O(3n∗∑2mi​)。

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson (k<<1)
#define rson (k<<1)+1
#define mid ((l+r)/2)
#define sz(x) int(x.size())
#define pii pair<ll,ll>
#define bit bitset<100000>
using namespace std;
const int MAX=2e6+10;
const int MOD=998244353; //G=3
const int INF=INT_MAX;
const double PI=acos(-1.0);
typedef int64_t ll;
void Min(ll &x,ll y,ll z)
{
    if(y<0||z<0)return;
    if(x<0)x=y+z;
    x=min(x,y+z);
}
struct lenka
{
    ll m,d;
    vector<pii>p;
    void read(vector<ll> &s)
    {
        scanf("%lld%lld",&m,&d);
        p.resize(m);
        for(auto &kv:p)scanf("%lld%lld",&kv.fi,&kv.se);
        for(auto &kv:p)s.push_back(kv.fi);
        sort(s.begin(),s.end());
        s.erase(unique(s.begin(),s.end()),s.end());
    }
    ll cost(ll x)
    {
        if(m==1)return x==p[0].fi?p[0].se:-1;
        for(int j=0;j+1<m;j++)
        {
            ll k=(p[j+1].se-p[j].se)/(p[j+1].fi-p[j].fi);
            if(x>=p[j].fi&&x<=p[j+1].fi)return p[j].se+k*(x-p[j].fi);
        }
        return -1;
    }
}a[11];
ll d[60][1<<11];
ll f[60][1<<11];
ll l[60][1<<11];
ll r[60][1<<11];
ll sum[1<<11];
int solve()
{
    vector<ll>s;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)a[i].read(s);
    memset(d,-1,sizeof d);
    memset(l,-1,sizeof l);
    memset(r,-1,sizeof r);
    memset(sum,0,sizeof sum);
    for(int i=0;i<(1<<n);i++)
    for(int j=0;j<n;j++)
    {
        if((1<<j)&i)sum[i]+=a[j].d;
    }

    for(int i=0;i<sz(s);i++)d[i][0]=l[i][0]=r[i][0]=0;
    for(int i=0;i<sz(s);i++)
    for(int j=0;j<(1<<n);j++)
    {
        ll len=0;
        for(int k=0;k<n;k++)if((1<<k)&j)len+=a[k].d;
        for(int k=0;k<n;k++)
        {
            if((1<<k)&j)continue;
            Min(l[i][j+(1<<k)],l[i][j],a[k].cost(s[i]+len));
            Min(r[i][j+(1<<k)],r[i][j],a[k].cost(s[i]-len-a[k].d));
        }
    }
    for(int i=0;i<sz(s);i++)
    {
        memset(f,-1,sizeof f);
        for(int j=i;j<sz(s);j++)f[j][0]=0;
        for(int j=i;j<sz(s);j++)
        for(int k=0;k<(1<<n);k++)
        {
            int S=(1<<n)-1-k;
            for(int h=S;h;h=(h-1)&S)
            {
                if(s[j]-s[i]<sum[k+h])continue;
                Min(f[j][k+h],l[i][k],r[j][h]);
            }
            if(s[j]-s[i]>=sum[k])Min(f[j][k],l[i][k],r[j][0]);
        }
        for(int j=i;j<sz(s);j++)
        for(int k=0;k<(1<<n);k++)
        {
            int S=(1<<n)-1-k;
            for(int h=S;h;h=(h-1)&S)Min(d[j][k+h],d[i][k],f[j][h]);
            Min(d[j][k],d[i][k],f[j][0]);
        }
    }
    ll ans=-1;
    for(int i=0;i<sz(s);i++)
    for(int j=0;j<(1<<n);j++)Min(ans,d[i][j],l[i][(1<<n)-1-j]);
    return printf("%lld\n",ans);
}
int main()
{
    int T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/309999.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

数据结构02附录02：哈希表[C++]

数据结构02附录02：哈希表[C++]

图源&#xff1a;文心一言 上机题目练习整理~&#x1f95d;&#x1f95d; 本篇作为线性表的代码补充&#xff0c;每道题提供了优解和暴力解算法&#xff0c;供小伙伴们参考~&#x1f95d;&#x1f95d; 第1版&#xff1a;在力扣新手村刷题的记录&#xff0c;优解是Bard老师提…
阅读更多...
pyqt treeWidget树生成

pyqt treeWidget树生成

生成treeWidget树与获取treeWidget树节点的数据 # encodingUTF-8 import sys from PyQt5.QtCore import Qt from PyQt5.QtWidgets import QApplication, QTreeWidgetItem, QLineEdit, QSpinBox, QComboBox from PyQt5.QtWidgets import QWidget from release_test import Ui_F…
阅读更多...
11Spring IoC注解式开发(上)(元注解/声明Bean的注解/注解的使用/负责实例化Bean的注解)

11Spring IoC注解式开发(上)(元注解/声明Bean的注解/注解的使用/负责实例化Bean的注解)

注解的存在主要是为了简化XML的配置。Spring6倡导全注解开发。 注解开发的优点:提高开发效率 注解开发的缺点:在一定程度上违背了OCP原则&#xff0c;使用注解的开发的前提是需求比较固定&#xff0c;变动较小。 1 注解的注解称为元注解 自定义一个注解: package com.sunspl…
阅读更多...
说说微信小程序的登录流程？

说说微信小程序的登录流程？

面试官&#xff1a;说说微信小程序的登录流程&#xff1f; 一、背景 传统的web开发实现登陆功能&#xff0c;一般的做法是输入账号密码、或者输入手机号及短信验证码进行登录 服务端校验用户信息通过之后&#xff0c;下发一个代表登录态的 token 给客户端&#xff0c;以便进行…
阅读更多...
抖店怎么筛选达人？团队实操，百用不厌！

抖店怎么筛选达人？团队实操，百用不厌！

我是电商珠珠 在抖店入驻之后&#xff0c;品也选好了&#xff0c;就卡到了选达人这方面。 要么选的达人带不起来自己的品&#xff0c;要么就是被达人骗样品&#xff0c;要么就是没有达人愿意搭理自己。 我做抖店也已经三年时间了&#xff0c;这种情况遇到过很多&#xff0c;…
阅读更多...
python爬虫实战(9)--获取澎pai热榜

python爬虫实战(9)--获取澎pai热榜

1. 需要的类包 import pandas as pd import requests2. 请求地址 通过分析&#xff0c;数据可以直接从接口获取&#xff0c;无需解析页面标签&#xff0c;直接取出我们需要的数据即可。 def fetch_hot_news(api_url):response requests.get(api_url)if response.status_cod…
阅读更多...
高级路由学习试题

高级路由学习试题

文章目录 高级路由学习试题一.高级路由题目答案 二.OSPF 相关答案 三.基础知识答案 高级路由学习试题 一.高级路由题目 1.以下属于ITOIP特性的有&#xff08;&#xff09; A、智能 B、开放 C、融合 D、标准 2.层级化网络模型将网络划分为&#xff08;&#xff09; A、汇…
阅读更多...
SpringMVC工作原理

SpringMVC工作原理

文章目录 Spring MVC 概述组件介绍Spring MVC的工作原理 Spring MVC 概述 SpringMVC是一个基于MVC模式的Web框架&#xff0c;它是Spring Framework的一部分。SpringMVC主要用于在Java Web应用程序中实现Web层&#xff0c;提供了一套与平台无关的、可重用的Web组件。 Spring MV…
阅读更多...
虚拟商城与社交购物：Facebook的新零售策略

虚拟商城与社交购物：Facebook的新零售策略

随着数字科技的迅猛发展&#xff0c;虚拟商城和社交购物逐渐成为零售业的重要趋势。在这一潮流中&#xff0c;Facebook作为全球最大社交媒体平台之一&#xff0c;积极拥抱新零售&#xff0c;推动了虚拟商城和社交购物的融合。本文将深入探讨Facebook的新零售策略&#xff0c;以…
阅读更多...
如何创建自己的小程序？零编程一键创建实战指南

如何创建自己的小程序？零编程一键创建实战指南

当今瞬息万变的数字世界中&#xff0c;拥有一个属于自己的小程序已成为企业与个人展示、服务和互动的重要途径。无需编码知识&#xff0c;通过便捷的云端可视化平台&#xff0c;也可以轻松创建一款符合自身需求且功能丰富的小程序。下面给大家分享如何创建自己的小程序。 1、选…
阅读更多...
【uview2.0】Keyboard 键盘 与 CodeInput 验证码输入 结合使用 uview

【uview2.0】Keyboard 键盘 与 CodeInput 验证码输入 结合使用 uview

https://www.uviewui.com/components/codeInput.html &#xff08;CodeInput 验证码输入&#xff09; https://www.uviewui.com/components/keyboard.html &#xff08;Keyboard 键盘&#xff09; <u-keyboard mode"number" :dotDisabled"true" :show&q…
阅读更多...
【活动系列】视频生成前沿研究与应用

【活动系列】视频生成前沿研究与应用

写在前面 在视频生成即将迎来技术和应用大爆发之际&#xff0c;为了帮助企业和广大从业者掌握技术前沿&#xff0c;把握时代机遇&#xff0c;机器之心AI论坛就将国内的视频生成技术力量齐聚一堂&#xff0c;共同分享国内顶尖力量的技术突破和应用实践。 基本信息 论坛名称&…
阅读更多...
创意天堂：25个聚焦艺术、设计和创意的网站推荐

创意天堂：25个聚焦艺术、设计和创意的网站推荐

1、即时设计 说到即时设计&#xff0c;每个人都应该熟悉它。不久前&#xff0c;即时设计开启了世界上第一个可以使用人工智能完成UI设计草案的即时设计「即时AI」大规模的内部测试也给产品设计行业带来了新的发展方向。事实上&#xff0c;对于产品设计师来说&#xff0c;即时设…
阅读更多...
C语言中的指针变量p,特殊表达式p[0] ，(*p)[0]，(px+3)[2] ,(*px)[3]化简方法

C语言中的指针变量p,特殊表达式p[0] ，(*p)[0]，(px+3)[2] ,(*px)[3]化简方法

一.已知以下代码&#xff0c;请问以下 式子p[0] &#xff0c;p[1] &#xff0c;(*p)[0] &#xff0c;(*p)[1] 是什么意思&#xff1f; int A[3] {1,2,3}; int (*p)[3] &A; 因为前面的嵌入式C语言基础的章节中说过&#xff0c;数组下标其实就是数组首元素的地址往上偏…
阅读更多...
网络服务DHCP与DNS

网络服务DHCP与DNS

一 DHCP的工作原理&#xff08;租约过程&#xff09; 分类 1&#xff09;自动分配&#xff1a;分配到一个IP地址后永久使用 &#xff08;2&#xff09;手动分配&#xff1a;由DHCP服务器管理员指定IP&#xff08;打印机、报销系统&#xff09;把mac地址和ip地址做一个一一对…
阅读更多...
Leetcode 1049 最后一块石头的重量II

Leetcode 1049 最后一块石头的重量II

题意理解&#xff1a; 有一堆石头&#xff0c;用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合&#xff0c;从中选出任意两块石头&#xff0c;然后将它们一起粉碎。假设石头的重量分别为 x 和 y&#xff0c;且 x < y。 思路转化&#xff1a;我们可…
阅读更多...
JAVA销售数据决策管理系统源码

JAVA销售数据决策管理系统源码

JAVA销售数据决策管理系统源码 基于BS&#xff08;Extjs Strus2springhibernate Mysql&#xff09;的销售数据的决策支持 主要的功能有 系统功能具体内容包括基础资料、进货管理、出货管理、库存管理、决策分析、系统管理。
阅读更多...
Flink-CEP 实战教程

Flink-CEP 实战教程

文章目录 1. 基本概念1.1 CEP 是什么1.2 模式&#xff08;Pattern&#xff09;1.3 应用场景 2. 快速上手2.1 引入依赖2.2 入门实例 3. 模式API&#xff08;Pattern API&#xff09;3.1 个体模式3.1.1 基本形式3.1.2 量词&#xff08;Quantifiers &#xff09;3.1.3 条件&#x…
阅读更多...
当心这46个重要漏洞！微软发布1月补丁日安全通告

当心这46个重要漏洞！微软发布1月补丁日安全通告

近日&#xff0c;亚信安全CERT监测到微软1月补丁日发布了针对48个漏洞的修复补丁&#xff0c;其中&#xff0c;2个漏洞被评为紧急&#xff0c;46个漏洞被评为重要&#xff0c;共包含10个权限提升漏洞&#xff0c;11个远程代码执行漏洞&#xff0c;3个欺骗漏洞&#xff0c;11个信…
阅读更多...
HTML---JavaScript操作DOM对象

HTML---JavaScript操作DOM对象

目录 文章目录 本章目标 一.DOM对象概念 二.节点访问方法 常用方法&#xff1a; 层次关系访问节点 三.节点信息 四.节点的操作方法 操作节点的属性 创建节点 删除替换节点 五.节点操作样式 style属性 class-name属性 六.获取元素位置 总结 本章目标 了解DOM的分类和节点间的…
阅读更多...
最新文章

Copyright @ 2022~2023