喜欢的话就坚持吧

10月 16

5.00 avg. rating (96% score) - 1 vote

这次没有题目大意,点击阅读全文了解详情


第一道题目背景是比较社会的小猪佩奇,

题目大意就是说你有3种物品ABC,价值分别为a,b,a+b,然后你要选出不超过n个物品使他们价值和是k,然后让你把这些物品装入一个大小为n的盒子,问有几种装法,对998244353取模。两种方案不同,当且仅当盒子中某个位置放置的物品种类不同,或者一个放了物品而另一个没有。
1≤N≤1e7,0≤K≤1e15,0≤a,b ≤1e5。

一看就是什么sbt,k<=1e15?
反正我是先想到考虑只拿前两种物品,然后用exgcd求出一组解,然后枚举每组解中可以把前两种物品换成几个第三种物品。
然后答案就是
\sum \tbinom{a}{n} \cdot \tbinom{b}{n-a} \tbinom{c}{n-a-b}
发现我需要枚举一个c
复杂度大概是不可以接受的。
发现我们是把c单独考虑的,
但其实我们可以假装没有c,把b无限制的放(可以放有a的位置),那么既有a又有b的位置就是c
那么式子就成了
\sum \tbinom{a}{n} \tbinom{b}{n}
发现我们连exgcd都不用了,直接枚举a有几个,看是否合法就行。
(其实一开始根本不用exgcd好吗?我太菜了,只会这个)
然后毒瘤出题人造了些毒瘤边界数据,需要特判,详细见代码。
值的一提的是这题卡空间,全开long long 会炸

#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long ll;
const int N=10000010;
const ll mod=998244353;

int n,a,b;
inline int ksm(int x,int y)
{
    int res=1;
    for(;y;y>>=1)
    {
        if(y&1) res=(long long)res*x%mod;
        x=(long long)x*x%mod;
    }return res;
}
int jc_inv[N],jcn;

inline void init()
{
    jcn=1;
    for(int i=1;i<=n;++i) jcn=((ll)jcn*i)%mod;
    jc_inv[n]=(ll)ksm(jcn,mod-2);//printf("jc_inv=%d\n",jc_inv[n]);
    for(int i=n-1;i>=0;--i) jc_inv[i]=((ll)jc_inv[i+1]*(i+1))%mod;//,printf("%d\n",jc_inv[i]);
}
inline int C(int x)
{
    int tm=((ll)jc_inv[x]*jc_inv[n-x])%mod;
//  printf("jcn=%d tm=%d\n",jcn,tm);
    tm=((ll)tm*jcn)%mod;
    return tm;
}

ll k;int ans;
signed main()
{
    scanf("%d%d%d%lld",&n,&a,&b,&k);
    if(a==0&&b==0)
    {
        if(k!=0) printf("0");
        else
        {
            int tm=1;
            for(int i=1;i<=n;++i) tm=((ll)tm*4)%mod;
            printf("%d",tm);
        }
        return 0;
    }//printf("1");
    if(b==0) swap(a,b);
    init();//printf("jc[4]=%d\n",jc[4]);
//  printf("C(4,2)=%d\n",C(2));
    for(int i=0;i<=n;++i)
    {
        ll tm=k-1ll*a*i;
        if(tm<0) break;
        if(tm%b) continue;
        tm/=b;if(tm>n) continue;
    //  printf("1");
        ans+=(1ll*C(i)*C(tm))%mod;
        ans%=mod;
    } 
    printf("%lld",ans%mod);
} 

然后是第二道毒瘤题,由于题目过于中二,不再叙述

题目大意:
给你一张9个点n条边的幽香图,每条边连接ui,vi两点,边不仅有边权w_i,还有一个優先级p_i,你走过的边的優先级必须单调不降。多组询问,每次询问会给你s_i个区间和一个起点和一个终点,区间表示这次询问你从起点到终点路径上的優先级必须在区间里。
对于每次询问,你需要回答最短路径长度。
1≤n≤100,000,1≤pi≤2,000,ui≠vi,zi≠ti,1≤wi≤100,000,000,1≤∑si≤10,000。保证每次的区间没有交集.

一看就是一道sbt,刚开始我以为是什么分层图或者是什么tarjan,
发现什么都不是。根本不可做。
然后突然发先,只有9个点?2000个優先级?
那我就对每个優先级上的9个点跑一个floyd,然后就是矩把你询问的矩阵进行floyd矩阵变换?(啊?你不会。去学学矩乘在最短路上的应用,就知道我再说什么了)。
然后发现他询问次数很多,我每次暴力合并是超时的。
但是矩乘具有结合律,我们可以用线段树优化,就是线段树每个点代表一个矩阵,然后就做完了。
(为什么我还是t?因为这题时限2s.抱歉我开O2 0.2s都不用)。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>

#define ls (p<<1)
#define rs (p<<1|1)
using namespace std;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read(){
    int x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
} char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
inline void print(int x){
    if(C>1<<20)Ot();
    if(x==-10) {sr[++C]='\n';return;}
    if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int INF=0x3f3f3f3f;
const int N=2005;
const int M=100005;
int n,S; int T; 
struct mat
{
    int a[10][10];
    mat()
    {
        memset(a,INF,sizeof a);
        for(int i=0;i<9;++i) a[i][i]=0; 
    }
    friend mat operator *(mat x,mat y)
    {
        mat res;
        for(int i=0;i<9;++i)
        {
            for(int k=0;k<9;++k)
            {
                for(int j=0;j<9;++j)
                    res.a[i][j]=min(res.a[i][j],x.a[i][k]+y.a[k][j]);
            }
        }
        return res;
    }
}a[N+5],tr[(N+5)<<2];
inline void build(int p,int l,int r)
{
    if(l==r){tr[p]=a[l];return;}
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    tr[p]=tr[ls]*tr[rs];
}
mat query(int p,int l,int r,int dl,int dr)
{
//  printf("l=%d r=%d\n",l,r); 
    if(dl<=l&&dr>=r) return tr[p];
    int mid=(l+r)>>1; mat res;
    if(dl<=mid)  res=res*query(ls,l,mid,dl,dr);
    if(mid<dr)   res=res*query(rs,mid+1,r,dl,dr);
    return res;
}
struct project
{
    int l,r;
    friend bool operator <(project a,project b){return a.l<b.r;}
}pr[M];
int main()
{

    n=read();S=read();
    for(register int i=1,p,x,y,z;i<=n;++i)
    {
        p=read();x=read();y=read();z=read();
        a[p].a[x][y]=min(a[p].a[x][y],z);
    }
    for(register int p=1;p<=N;++p)
        for(register int k=0;k<9;++k)
            for(register int i=0;i<9;++i)
                for(register int j=0;j<9;++j)
                    a[p].a[i][j]=min(a[p].a[i][j],a[p].a[i][k]+a[p].a[k][j]);
    build(1,1,N);

    T=read();
    for(register int i=1;i<=T;++i)
    {
        int st,ed,si;mat b;
        st=read();ed=read();si=read();
        for(register int i=1;i<=si;++i) pr[i].l=read(),pr[i].r=read();//("%d%d",&pr[i].l,&pr[i].r);
        sort(pr+1,pr+si+1);
        for(register int i=1;i<=si;++i) b=b*query(1,1,N,pr[i].l,pr[i].r);
        b.a[st][ed]^INF?print(b.a[st][ed]):print(-1);
    }
    return Ot(),0;
}
5.00 avg. rating (96% score) - 1 vote
  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

活捉 % 条