首页 > 其他分享 >AtCoder Regular Contest 159简要题解

AtCoder Regular Contest 159简要题解

时间：2023-05-07 11:23:15浏览次数：54  
标签：AtCoder cnt Contest int 题解 ps cdots include dp

AtCoder Regular Contest 159

传送门

A - Copy and Paste Graph

图的邻接矩阵为

\[\left( \begin{matrix} A & A & \cdots & A \\ A & A & \cdots & A \\ \cdots & \cdots & \cdots & \cdots\\ A & A & \cdots & A \end{matrix} \right) \]

则

\[{\left( \begin{matrix} A & A & \cdots & A \\ A & A & \cdots & A \\ \cdots & \cdots & \cdots & \cdots\\ A & A & \cdots & A \end{matrix} \right)}^{\infty} = {\left( \begin{matrix} A^{\infty} & A^{\infty} & \cdots & A^{\infty} \\ A^{\infty} & A^{\infty} & \cdots & A^{\infty} \\ \cdots & \cdots & \cdots & \cdots\\ A^{\infty} & A^{\infty} & \cdots & A^{\infty} \end{matrix} \right)} \]

即为图的两点间最短路径矩阵，其中矩阵是在\(\lbrace+,min\rbrace\)下做矩阵乘法。
因此我们只需要用Floyd算法求出\(A^{\infty}\)即可。
时间复杂度\(O(n^3+Q)\)

code：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long

using namespace std;

const int inf=1e9+7;

int n,k,a[105][105];

signed main() {
    scanf("%lld%lld",&n,&k);
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++) 
        for(int j=1;j<=n;j++) {
            scanf("%lld",&a[i][j]);
            if(a[i][j]<=0) {
                a[i][j]=inf;
            }
        }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++) {
                a[i][j]=min(a[i][k]+a[k][j],a[i][j]);
            }
    int T;cin>>T;
    while(T--) {
        int s,t;scanf("%lld%lld",&s,&t);
        if(a[(s-1)%n+1][(t-1)%n+1]<inf) {
            printf("%lld\n",a[(s-1)%n+1][(t-1)%n+1]);
        } else {
            puts("-1");
        }
    }
    return 0;
}

B - GCD Subtraction

不失一般性，假设\(a>b\)，首先\((a-g，b-g)=(a-b，b-g)\)
所以每次操作都是\(a-b\)和\(b^{'}\)在做\(gcd\)运算，然后把\(b^{'}\)减去得到的\(g_{new}\)得到\(b^{''}\)然后继续重复上述过程。
考虑怎么加速这些操作。
注意到\((a-b，b-g)=g\times(\frac{a-b}{g},\frac{b}{g}-1)\)若\((\frac{a-b}{g},\frac{b}{g}-1)=1\)则下一次运算就会变成\((\frac{a-b}{g},\frac{b}{g}-2)\)。
因此我们可以找到距离\(\frac{b}{g}-1\)最近的与\(\frac{a-b}{g}\)最大公约数不为\(1\)的数，这个可以通过预处理出\(a-b\)的所有质因数来实现，这样就保证了每次模拟都会至少缩小\(\frac{1}{2}\)。

code:

#include<algorithm>
#include<iostream>
#include<cstdio>
#define int long long

using namespace std;

int gcd(int o,int p) {return (!p)?o:gcd(p,o%p);}

int prime[200005],a[1000005],cnt=0,divid[2005][2],s=0;

signed main() {
    for(int i=2;i<=1000000;i++) {
        if(!a[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=1000000;j++) {
            a[i*prime[j]]=1;
            if(i%prime[j]==0) {
                break;
            }
        }
    }
    int a,b;scanf("%lld%lld",&a,&b);
    if((a==1)||(b==1)||(a==b)) {
        puts("1");
        return 0;
    }
    int ans=0,x=min(a,b),g=max(a,b)-min(a,b),gg=g;
    for(int i=1;i<=cnt;i++) {
        if(gg%prime[i]==0) {
            divid[++s][0]=prime[i];
            divid[s][1]=0;
            while(gg%prime[i]==0) {
                gg/=prime[i];
                divid[s][1]++;
            }
        }
        if(prime[i]*prime[i]>=gg) {
            break;
        }
    }
    if(gg>1) {
        divid[++s][0]=gg;
        divid[s][1]=1;
    }
    while((x>0)&&(g>0)) {
        int yu=0;
        for(int i=1;i<=s;i++) {
            if(divid[i][1]==0) {
                continue;
            }
            yu=max(yu,x/divid[i][0]*divid[i][0]);
        }
        ans+=x-yu;
        if(yu<1) break;
        x=yu;
        int g_new=gcd(x,g);
        ans++;
        x/=g_new;
        x--;
        g/=g_new;
        for(int i=1;i<=s;i++) {
            while(g_new%divid[i][0]==0) {
                divid[i][1]--;
                g_new/=divid[i][0];
            }
        } 
    }
    cout<<ans<<endl;
    return 0;
}

C - Permutation Addition

假设做了k次操作，所有数的和即为\(\sum_{i=1}^{n}A_i+k\times\frac{n\times(n+1)}{2}\)。
注意到若k为偶数，则有解的一个必要条件是\(n\mid\sum_{i=1}^{n}A_i\)，注意到我们如果用连续的两次操作
\(\{1,2,3,\cdots,n\}\)
\(\{n,n-1,n-2,\cdots,1\}\)
那么相当于什么操作都没有做，但如果改成
\(\{1,2,3,\cdots,n\}\)
\(\{n-1,n,n-2,\cdots,1\}\)
就相当于选择两个元素一个减一一个加一，这样一定可以在\(10000\)次以内构造出解。
对于\(k\)为奇数的情况下，我们先随便做一次操作，转化成偶数的情况。

code：

#include<iostream>
#include<vector>
#include<cstdio>

using namespace std;

int a[55],sum=0,n,ans[10005][55],cnt=0;

void add(int x,int y) {
    cnt++;
    ans[cnt][x]=2;ans[cnt][y]=1;
    int yu=3;
    for(int i=1;i<=n;i++) {
        if(i==x||i==y) {
            continue;
        }
        ans[cnt][i]=yu++;
    }
    cnt++;
    ans[cnt][x]=n;ans[cnt][y]=n-1;
    yu=n-2;
    for(int i=1;i<=n;i++) {
        if(i==x||i==y) {
            continue;
        }
        ans[cnt][i]=yu--;
    }
}

void work() {
    int avg=sum/n;
    vector<int> mi;
    vector<int> ma;
    for(int i=1;i<=n;i++) {
        if(a[i]<avg) {
            mi.push_back(i);
        } else if(a[i]>avg) {
            ma.push_back(i);
        }
    }
    int p=0;
    for(int i=0;i<mi.size();i++) {
        while(a[mi[i]]<avg) {
            a[mi[i]]++;a[ma[p]]--;
            add(mi[i],ma[p]);
            if(a[ma[p]]<=avg) p++;
        }
    }
    puts("Yes");
    cout<<cnt<<endl;
    for(int i=1;i<=cnt;i++) {
        for(int j=1;j<n;j++) {
            printf("%d ",ans[i][j]);
        }
        printf("%d\n",ans[i][n]);
    }
}

int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    if(sum%n==0) {
        work();
    } else if((sum+n*(n+1)/2)%n==0) {
        sum+=n*(n+1)/2;
        for(int i=1;i<=n;i++) a[i]+=i;
        cnt=1;
        for(int i=1;i<=n;i++) ans[cnt][i]=i;
        work();
    } else {
        puts("No");
    }
    return 0;
}

D - LIS 2

性质1：在最长不下降子序列问题中，对于值相同的元素的\(dp\)值是单调不减的。
性质2：对于加入的一段连续的\([l,r]\)区间，有\(dp_{l+1}=dp_{l}+1,\quad dp_{l+2}=dp_{l+1}+1,\quad \cdots,\quad dp_r=dp_{r-1}+1\)
我们归纳的证明，若\(dp_{l+1} \neq dp_l+1\)则说明\(dp_{l+1} \gt dp_{l}+1\)，而\(dp_{l+1}\)必然从\([l,r]\)之前的某个元素转移而来，假设是\(x\)若\(x<l\)则说明\(dp_x>dp_l\)那么\(dp_l\)就可以通过\(dp_x\)转移而来得到更优秀的答案，这是矛盾的，若\(x=l\)，就会与性质1矛盾。
有了这些性质对，于一个区间，我们只需要记录\(l\)的\(dp\)值即可。\(dp_l\)可能从\(1,2,\cdots,l-1\)转移而来，若是从\(1,2,\cdots,l-2\)转移而来，依据上面的性质，转移点若非右端点则一定可以右移。剩下的就是线段树优化\(dp\)了。

code：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

int n,a[200005],b[600005],seg[3000005],l[200005],r[200005],f[200005],cnt=0,lazy[3000005],tr[600005];

void pushdown(int s) {
    seg[s<<1]=max(seg[s<<1],lazy[s]);
    seg[s<<1|1]=max(seg[s<<1|1],lazy[s]);
    lazy[s<<1]=max(lazy[s<<1],lazy[s]);
    lazy[s<<1|1]=max(lazy[s<<1|1],lazy[s]);
    lazy[s]=0;
}

void put(int o,int p,int q,int r,int s,int t) {
    seg[s]=max(seg[s],t);
    if((o==q)&&(p==r)) {
        lazy[s]=max(lazy[s],t);
        return;
    }
    int mid=(o+p)>>1;
    if(r<=mid) {
        put(o,mid,q,r,s<<1,t);
    } else if(q>mid) {
        put(mid+1,p,q,r,s<<1|1,t);
    }else {
        put(o,mid,q,mid,s<<1,t);
        put(mid+1,p,mid+1,r,s<<1|1,t);
    }
}

int get(int o,int p,int q,int s) {
    if((o==q)&&(p==q)) {
        return seg[s];
    }
    pushdown(s);
    int mid=(o+p)>>1;
    if(q<=mid) {
        return get(o,mid,q,s<<1);
    } else {
        return get(mid+1,p,q,s<<1|1);
    }
}

void put_tr(int o,int p,int tmp) {
    for(int i=o;i<=tmp;i+=(-i)&i) {
        tr[i]=max(tr[i],p);
    }
}

int get_tr(int o,int tmp) {
    int yu=0;
    for(int i=o;i;i-=(-i)&i) {
        yu=max(yu,tr[i]);
    }
    return yu;
}

int main() {
    memset(tr,0,sizeof(tr));
    memset(seg,0,sizeof(seg));
    memset(lazy,0,sizeof(lazy));
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d%d",&l[i],&r[i]);
        b[++cnt]=l[i];
        b[++cnt]=r[i];
        b[++cnt]=l[i]-1;
    }
    sort(b+1,b+cnt+1);
    int tmp=unique(b+1,b+cnt+1)-b-1;
    int ans=0;
    for(int i=1;i<=n;i++) {
        int yu=lower_bound(b+1,b+tmp+1,l[i]-1)-b;
        int pos=get(1,tmp,yu,1);
        if(pos==0) {
            f[i]=1;
        } else {
            f[i]=f[pos]+min(r[pos],l[i]-1)-l[pos]+1;
        }
        f[i]=max(f[i],get_tr(yu,tmp)+1);
        int ll=lower_bound(b+1,b+tmp+1,l[i])-b;
        int rr=lower_bound(b+1,b+tmp+1,r[i])-b;
        put(1,tmp,ll,rr,1,i);
        ans=max(ans,f[i]+r[i]-l[i]);
        put_tr(rr,f[i]+r[i]-l[i],tmp);
    }
    cout<<ans<<endl;
    return 0;
}

E - Difference Sum Query

\(m=\lfloor\frac{a_{t mod M}\times l+b_{t mod M}\times r}{a_{t mod M}+b_{t mod M}}\rfloor=l+\lfloor\frac{b_{t mod M}}{a_{t mod M}+b_{t mod M}}\rfloor \times (r-l)\)
这个形式类似于二分，每次取的点构成一棵二叉搜索树。
题目要求的就是\(ans=\sum_{i=c}^{d-1} [二叉搜索树上从i走到i+1的路径长度]\)。
而\(ans\)加上从\(c\)到\(d\)的路径长度其实就是\(c,c+1,\cdots,d\)这些点构成的虚树的边数的两倍。
虚树上的点又由两部分构成，一部分是\(c,c+1,\cdots,d\)另一部是\(c\)到\(d\)路径上不属于\(c,c+1,\cdots,d\)的点。
题目中还有一个条件\(\max\{\frac{a_i}{b_i},\frac{b_i}{a_i}\}\leq2\)这保证了二叉搜索树的高度不超过\(\log_{\frac{3}{2}}n\)。

code：

#include<iostream>
#include<cstdio>
#define int long long

using namespace std;

int a[1005],b[1005],n,m,l1,l2,x1[105],x2[105];

void work(int *f,int &len,int target) {
    len=0;
    int l=1,r=n,t=0,mid=l+(r-l)*b[0]/(a[0]+b[0]);
    while(mid!=target) {
        f[++len]=mid;
        if(mid<target) {
            l=mid+1;
        } else {
            r=mid-1;
        }
        t=(t+1)%m;
        mid=l+(r-l)*b[t]/(a[t]+b[t]);
    }
    f[++len]=mid;
}

signed main() {
    scanf("%lld%lld",&n,&m);
    for(int i=0;i<m;i++) {
        scanf("%lld%lld",&a[i],&b[i]);
    }
    int T;cin>>T;
    while(T--) {
        int ai,bi;scanf("%lld%lld",&ai,&bi);
        work(x1,l1,ai);
        work(x2,l2,bi);
        int pos=-1,sum=bi-ai+1;
        for(int i=1;i<=min(l1,l2);i++) {
            if(x1[i]==x2[i]) {
                pos=i;
            } else {
                break;
            }
        }
        for(int i=pos;i<=l1;i++) {
            if(x1[i]<ai||x1[i]>bi) {
                sum++;
            }
        }
        for(int i=pos;i<=l2;i++) {
            if(x2[i]<ai||x2[i]>bi) {
                sum++;
            }
        }
        printf("%lld\n",sum*2-2-(l1-pos)-(l2-pos));
    }
    return 0;
}

F - Good Division

  • 对于一段区间，可以消去变为空的条件是，区间长度为偶数，且区间内不存在超过区间长度一半的数。
  • 题目变成求有多少个分割方法满足分割出来的区间长度为偶数且不存在绝对众数。
    我们把\(a_{2i-1},a_{2i}\)看成一个\(pair\quad p_i\)
  • 考虑动态规划，\(dp_i\)表示以\(p_i\)结尾的满足条件的分割数量。答案就是\(dp_n\)。
  • 对于一个\(d\)，我们对所有\(d\)出现的位置染色，然后从左往右对每个\(d\)出现的位置找到左边和右边第一个未染色的位置染色，这个可以用并查集在\(O(n\alpha(n))\)内完成。我们观察每个连续的染色段，只有被包含在段内的区间才有可能出现\(d\)是绝对众数的情况。因此我们后续的维护只需要在段内维护即可。
  • 所有段的长度之和是\(O(n)\)的。
  • 对于一个\(d\)，我们考虑令\(b_{d,i}=1\)，若\(p_i\)中两个数都等于\(d\)；\(b_{d,i}=-1\)，若\(p_i\)中两个数都不等于\(d\)；其他的情况\(b_{d,i}=0\)。那么一段区间有绝对众数\(d\)的充要条件是区间\(b_{d,i}\)的和大于\(0\)。
  • 我们记录每个\(d\)的\(b\)的前缀和\(pre_{d,i}=\sum_{j=1}^{i}b_{d,j}\)，因此一段区间\([l,r]\)有绝对众数\(d\)的条件是\(pre_{d,r}>pre_{d,l-1}\)
  • 令\(c_{d,i}\)为所有满足\(pre_{d,x}=i\)的\(x\)的\(dp_x\)的总和，维护\(blk_{d,i}=\sum_{j=-\infin}^{i}c_{d,j}\)
  • 每次\(pre\)的变化只有\(\pm1\)。我们的转移策略是先令\(dp_i=\sum_{j=1}^{i-1}dp_j\)再减去不满足条件的转移。
  • 这样可以做到\(O(n)\)但实际上跑的贼慢(

code：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<map>

using namespace std;

const int mo=998244353;

int n,a[1000005],sum[1000005],dp[500005],fa[1000005],siz[1000005];
int cnt[1000005],tmp[1000005],pre[1000005],len[1000005],wh[1000005];
vector<int> upd[500005];
vector<int> ed[500005];
vector<int> bg[500005];
vector<int> ed_pos[1000005];
vector<int> pos[1000005];
vector<int> blk[1000005];

inline int getfa(int o) {return (fa[o]==o)?o:(fa[o]=getfa(fa[o]));}

void work_left(int p,vector<int> & p_i) {
    vector<int> sche;
    sche.clear();
    for(auto j:pos[p]) {
        if(j==1) {
            sche.push_back(1);
            cnt[1]++;
            continue;
        }
        int ps=getfa(j-1);
        fa[j]=ps;siz[ps]++;
        if(!cnt[ps]) {
            sche.push_back(ps);
        }
        cnt[ps]++;
        if(ps==1) {
            continue;
        }
        if(ps!=j-1) {
            fa[ps]=ps-1;siz[ps-1]+=siz[ps];
            if(!cnt[ps-1]) {
                sche.push_back(ps-1);
            }
            cnt[ps-1]++;
            ps--;
        }
        if(ps==1) continue;
        if(a[ps-1]==p) {
            fa[ps]=getfa(ps-1);
            siz[getfa(ps-1)]+=siz[ps];
        }
    }
    for(auto j:sche) {
        if(fa[j]==j) {
            for(int i=j;i<j+siz[j];i++) {
                if(!tmp[(i+1)>>1]) {
                    p_i.push_back((i+1)>>1);
                }
                tmp[(i+1)>>1]++;
            }
        }
        fa[j]=j;siz[j]=1;
        cnt[j]=0;
    }
    for(auto j:pos[p]) {
        fa[j]=j;siz[j]=1;
        cnt[j]=0;
    }
}

void work_right(int p,vector<int> & p_i) {
    vector<int> sche;
    sche.clear();
    for(auto j:pos[p]) {
        if(j==(n<<1)) {
            sche.push_back(n<<1);
            cnt[n<<1]++;
            continue;
        }
        int ps=getfa(j+1);
        fa[j]=ps;siz[ps]++;
        if(!cnt[ps]) {
            sche.push_back(ps);
        }
        cnt[ps]++;
        if(ps==(n<<1)) {
            continue;
        }
        if(ps!=j+1) {
            fa[ps]=ps+1;siz[ps+1]+=siz[ps];
            if(!cnt[ps+1]) {
                sche.push_back(ps+1);
            }
            cnt[ps+1]++;
            ps++;
        }
        if(ps==(n<<1)) continue;
        if(a[ps+1]==p) {
            fa[ps]=getfa(ps+1);
            siz[getfa(ps+1)]+=siz[ps];
        }
    }
    for(auto j:sche) {
        if(fa[j]==j) {
            for(int i=j;i>j-siz[j];i--) {
                if(!tmp[(i+1)>>1]) {
                    p_i.push_back((i+1)>>1);
                }
                tmp[(i+1)>>1]++;
            }
        }
        fa[j]=j;siz[j]=1;
        cnt[j]=0;
    }
    for(auto j:pos[p]) {
        fa[j]=j;siz[j]=1;
        cnt[j]=0;
    }
}

pair<int,int> get(int num,int beg) {
    int x=pre[num];
    int mi=1e9+7;
    int ma=-mi;
    for(int i=beg;i<=ed_pos[num][wh[num]];i++) {
        if((a[i<<1]==num)&&(a[(i<<1)-1]==num)) {
            x++;
        } else if((a[i<<1]!=num)&&(a[(i<<1)-1]!=num)) {
            x--;
        }
        ma=max(ma,x);
        mi=min(mi,x);
    }
    return make_pair(mi,ma);
}

int main() {
    scanf("%d",&n);
    for(int i=1;i<=n<<1;i++) {
        scanf("%d",&a[i]);
        pos[a[i]].push_back(i);
        fa[i]=i;
        siz[i]=1;
    }
    memset(tmp,0,sizeof(tmp));
    for(int i=1;i<=n<<1;i++) {
        vector<int> p_i;
        work_left(i,p_i);
        reverse(pos[i].begin(),pos[i].end());
        work_right(i,p_i);
        for(int j:p_i) {
            upd[j].push_back(i);
            if((j==n)||(!tmp[j+1])) {
                ed[j].push_back(i);
            }
            if((j==1)||(!tmp[j-1])) {
                bg[j].push_back(i);
            }
        }
        for(int j:p_i) tmp[j]=0;
    }
    for(int i=1;i<=n;i++) {
        for(int j:ed[i]) {
            ed_pos[j].push_back(i);
            wh[j]=0;
        }
    }
    dp[0]=1;
    for(auto i:upd[1]) {
        pair<int,int> yu=get(i,1);
        yu.first=min(yu.first,0);
        len[i]=-yu.first;
        for(int j=1;j<=yu.second-yu.first+1;j++) {
            blk[i].push_back(0);
        }
        blk[i][len[i]]++;
    }
    memset(sum,0,sizeof(0));
    memset(pre,0,sizeof(pre));
    memset(dp,0,sizeof(dp));
    int s=1;
    for(int i=1;i<=n;i++) {
        if(i>1) {
            for(auto j:bg[i]) {
                pair<int,int> yu=get(j,i);
                len[j]=-yu.first;
                for(int k=1;k<=yu.second-yu.first+1;k++) {
                    blk[j].push_back(0);
                }
            }
        }
        for(auto j:upd[i]) {
            if((a[i<<1]!=j)&&(a[(i<<1)-1]!=j)) {
                pre[j]--;                
                sum[j]=((sum[j]-blk[j][pre[j]+len[j]])%mo+mo)%mo;
            } else if((a[i<<1]==j)&&(a[(i<<1)-1]==j)) {
                sum[j]=(sum[j]+blk[j][pre[j]+len[j]])%mo;
                pre[j]++;
            }
            dp[i]=((dp[i]-sum[j])%mo+mo)%mo;
        }
        dp[i]=(dp[i]+s)%mo;
        s=(s+dp[i])%mo;
        for(auto j:upd[i]) {
            blk[j][pre[j]+len[j]]+=dp[i];
            blk[j][pre[j]+len[j]]%=mo;
        }
        for(auto j:ed[i]) {
            sum[j]=0;
            blk[j].clear();
            wh[j]++;
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}

标签：AtCoder,cnt,Contest,int,题解,ps,cdots,include,dp
From： https://www.cnblogs.com/clapp/p/17379056.html

相关文章

  • AtCoder Regular Contest 134 E Modulo Nim
    洛谷传送门AtCoder传送门It'sallMAGIC这种题目一般先考虑局面要满足什么条件能必胜，然后根据这个性质来计数。如果把黑板上的数写成一个集合\(S\)，那么：\(\varnothing\)为必胜态，\(\{1\},\{2\}\)显然为必败态，打表发现其他单元素集合都为必胜态；如果\(\existsx\inS,x......
  • P8655 [蓝桥杯 2017 国 B] 发现环 题解
    题目概述题目传送门在一棵树中新增一条边，使得这个图产生一个环，求在环上的点。思路：拓补排序对于这道题显然不能生搬硬套拓补排序的模板。这道题中的图是一个无向图，而拓补排序却是处理有向图的一种思想。不难想到可以将无向图转化为有向图，即将对于每条无向边变换为双向建边，就......
  • AtCoder Beginner Contest 242
    A-T-shirt#include<bits/stdc++.h>usingnamespacestd;int32_tmain(){doublea,b,c,x; cin>>a>>b>>c>>x; if(x<=a)cout<<"1.000000000000"; elseif(x>b)cout<<&qu......
  • AtCoder Beginner Contest 285（B,D,E,F)
    AtCoderBeginnerContest285（B,D,E,F)B（暴力，非二分）B这道题其实很简单，但是我在\(vp\)的过程，有了一个错误的认识，纠正一下那就是，我把这个当成了一个二分题，并且还有点坚定不移，后来细想，发现不对二分，适用于那种边界分明的那种题（左边一定是符合条件，右边一定符合条件，也可表达为线性......
  • ABC297F 题解
    容斥萌萌题给你一个\(H\timesW\)的棋盘，问在棋盘上随机撒\(k\)个点，能够围住这\(k\)个点的最小子矩形的期望面积考虑枚举子矩形可以直接转成计数问题转变为在\(n\timesm\)的矩形中撒\(k\)个点，有多少种方案使得四条边上均至少有一个点答案乘上矩形面积再除以所有撒点......
  • Mac M系列芯片 vue前端node-sass兼容问题解决
    0、由于M系列芯片是arm架构，在使用brew安装node时都是arm的node，但是[email protected]版本中不支持arm架构的出现如下报错：Error:NodeSassdoesnotyetsupportyourcurrentenvironment:OSXUnsupportedarchitecture(arm64)withUnsupportedruntime(88)Formoreinfor......
  • LVJR2 赛后题解
    赛后补题请到洛谷比赛。A考虑分类讨论。显然当\(a=0,b=0\)时，答案等于\(0\)。当\(a=0\)或\(b=0\)时，直接将等于\(0\)的数乘以一个很大的数字，将不等于零的数除以一个很大的数字，答案为\(v\)。当\(a,b\)均不为\(0\)时，可以选择先将一个数字减到\(0\)，或将一个数字除......
  • [Luogu-P1007]题解(C++)
    PartIPreface原题目(Luogu)PartIISketch给定一个正整数\(L\)，表示独木桥长度。给定一个正整数\(N\)，表示桥上士兵的数量。给定\(N\)个整数，分别表示每个士兵的坐标。规定走到\(0\)坐标或\(L+1\)的位置为下桥，两个士兵相遇时不能走过去，他们会各自回头走。求出所有士......
  • 【HarmonyOS】【FAQ】HarmonyOS应用开发相关问题解答（一）
     【前提简介】本文档主要总结HarmonyOS开发过程中可能遇到的一些问题解答，主要围绕HarmonyOS展开，包括但不限于不同API版本HarmonyOS开发、UI组件、DevEcoStudio、Gitee示例代码等，并将持续更新哦。 【官方FAQ】【FAQ】HarmonyOS应用及服务开发常见问题汇总（官方总结，持续更新）：ht......
  • [AtCoder-AT_ABC108_B]题解(C++)
    PartIPreface原题目(Luogu)原题目(AtCoder)PartIISketchPartIIIAnalysis观察这道题，我们很容易想到，必须推导出\(x1,y1,x2,y2\)与\(x3,y3,x4,y4\)之间的关系。我们观察下图。可以发现：\(\begin{aligned}\begin{cases}x3=x2-(y2-y1)\\y3=y2+(x2-......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99