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

于 2024-01-11 00:05:41 发布
阅读量1.8k 收藏 25
点赞数 23
分类专栏： ACM-ICPC 文章标签： ACM ICPC
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/Mitsuha_/article/details/135328572
版权

2022-2023 ICPC, Asia Yokohama Regional Contest 2022

文章目录

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;
}
博客
对称加密算法模式简介
weixin_56255413的博客
12-12 1846
在对称加密算法中，我们常用的AES和SM4是不是可以满足所有的应用需求的数据块加密呢？答案是否定的，如果简单的使用AES去加密所有的信息，则比较容易被破解，因为相同的数据块加密后的结果是一样的。假设我们将数据分为多块，每一块的数据加密后同时又影响到另一块的数据加密，然后依次影响后面的数据加密，这样的加密方案才是更加安全的，于是诞生了多种加密模式。不同加密需求适用于不同的加密模式；---------先开个头，后面介绍下所有的加密模式-----，可能会给出一种模式的python代码（如果有golden数据）
博客
密码学基础-数据加密
最新发布
wangyx1234的博客
08-05 2081
安全的话题可以从完整性、机密性、合法性、不可否认性四个方面进行讨论；不同的安全风险需要不同的安全组件来抵抗风险。机密性保护可以使用对称密钥、非对称密钥来实施保护方案。对称加密有着执行速率快，资源消耗小的特点，但是前提是通信双方提前知道密钥；非对称加密有可以让初次通信的双方立即建立加密通信的优势，但是通信过程复杂，加解密比较消耗资源；AES XTS 分组加密模式使用两个 AES 密钥。一个密钥用于执行 AES 块加密;另一个用于加密所谓的“调整值”。
博客
XTS-AES
Lou's Knowledge Base
05-04 1596
AES加密算法， 不说了。 block cipher的各种工作模式，ECB、CBC、Counter等，不说了。   Cipher在用作disk encryption的时候，也有许多问题要考虑。主要是ECB模式不行（很明显），CBC模式也不好（无法随机访问），所以IEEE标准化了一个P1619标准，IEEE Standard for Cryptographic Protection of...
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值