動態dp初探

来源:https://www.cnblogs.com/nosta/archive/2019/02/23/10423862.html
-Advertisement-
Play Games

動態區間最大子段和問題 給出長度為$n$的序列和$m$次操作，每次修改一個元素的值或查詢區間的最大欄位和（SP1714 GSS3）。 設$f[i]$為以下標$i$結尾的最大子段和，$g[i]$表示從起始位置到$i$以內的最大子段和。 $$ f[i]=\max(f[i 1]+a[i],a[i])\\g ...


動態區間最大子段和問題

給出長度為\(n\)的序列和\(m\)次操作，每次修改一個元素的值或查詢區間的最大欄位和（SP1714 GSS3）。

設\(f[i]\)為以下標\(i\)結尾的最大子段和，\(g[i]\)表示從起始位置到\(i\)以內的最大子段和。
\[ f[i]=\max(f[i-1]+a[i],a[i])\\g[i]=\max(g[i-1],f[i]) \]
定義如下的矩陣乘法，顯然這滿足乘法結合律和分配律。
\[ C=AB\\C[i,j]=\max_{k}(A[i,k]+B[k,j]) \]
將轉移寫為矩陣（註意\(g[i]=\max(g[i-1],f[i-1]+a[i],a[i])\)）
\[ \begin{bmatrix} f[i]\\ g[i]\\ 0\end{bmatrix} = \begin{bmatrix} a[i]&-\infty&a[i]\\ a[i]&0&a[i]\\ -\infty&-\infty&0\end{bmatrix} \begin{bmatrix} f[i-1]\\ g[i-1]\\ 0\end{bmatrix} \]
可知每個元素\(a[i]\)都對應了一個矩陣，可以認為區間\([l,r]​\)的答案所在矩陣正是
\[ (\prod_{i=l}^k \begin{bmatrix} a[i]&-\infty&a[i]\\ a[i]&0&a[i]\\ -\infty&-\infty&0 \end{bmatrix} )\begin{bmatrix} 0\\ -\infty\\ 0\end{bmatrix} \]
因此可以用線段樹維護區間矩陣乘積。

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+10;
const int inf=0x3f3f3f3f;

struct mtr {
    int a[3][3];
    int*operator[](int d) {return a[d];}
    inline mtr() {}
    inline mtr(int val) {
        a[0][0]=a[0][2]=a[1][0]=a[1][2]=val;
        a[0][1]=a[2][0]=a[2][1]=-inf;
        a[1][1]=a[2][2]=0;
    }
    mtr operator*(mtr b) {
        static mtr c;
        memset(&c,-inf,sizeof c);
        for(int i=0; i<3; ++i) 
        for(int k=0; k<3; ++k) 
        for(int j=0; j<3; ++j) 
            c[i][j]=max(c[i][j],a[i][k]+b[k][j]);
        return c; 
    }
} t,a[N<<2];

#define ls (x<<1)
#define rs (x<<1|1)
void build(int x,int l,int r) {
    if(l==r) {
        scanf("%d",&r);
        a[x]=mtr(r);
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    a[x]=a[ls]*a[rs];
}
void modify(int x,int l,int r,int p,int val) {
    if(l==r) {
        a[x]=mtr(val);
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid) modify(ls,l,mid,p,val);
    else modify(rs,mid+1,r,p,val);
    a[x]=a[ls]*a[rs];
}
mtr query(int x,int l,int r,int L,int R) {
    if(L<=l&&r<=R) return a[x];
    int mid=(l+r)>>1;
    if(R<=mid) return query(ls,l,mid,L,R);
    if(mid<L) return query(rs,mid+1,r,L,R);
    return query(ls,l,mid,L,R)*query(rs,mid+1,r,L,R); 
}

int main() {
    memset(&t,-inf,sizeof t); //notice
    t[0][0]=t[2][0]=0;
    int n,q;
    scanf("%d",&n);
    build(1,1,n);
    scanf("%d",&q);
    for(int op,l,r; q--; ) {
        scanf("%d%d%d",&op,&l,&r);
        if(op==0) modify(1,1,n,l,r);
        else {
            mtr ret=query(1,1,n,l,r)*t;
            printf("%d\n",max(ret[0][0],ret[1][0]));
        } 
    }
    return 0;
}

動態樹上最大權獨立集

註意斷句 給出一棵\(n​\)個節點樹和\(m​\)次操作，每次操作修改一個點權並計算當前樹上的最大權獨立集的權值。

重鏈剖分，設\(y\)為\(x\)的某個兒子，\(s\)是重兒子，\(f[x,t]\)表示在以\(x\)為根的子樹中不選/選\(x\)時的最大權獨立集權值，\(g[x,t]\)表示在以\(x\)的為根的子樹中除去以\(s\)為根的子樹部分內不選/選\(x\)的最大權獨立集權值，。
\[ g[x,0]=\sum_{y\not=s}\max(f[y,0],f[y,1])\\ g[x,1]=a[x]+\sum_{y\not=s} f[y,0]\\ f[x,0]=g[x,0]+\max(f[s,0],f[s,1])\\ f[x,1]=g[x,1]+f[s,0] \]
然後改寫為矩陣乘法
\[ \begin{bmatrix} f[x,0]\\ f[x,1] \end{bmatrix}= \begin{bmatrix} g[x,0]&g[x,0]\\ g[x,1]&-\infty \end{bmatrix} \begin{bmatrix} f[s,0]\\ f[s,1] \end{bmatrix} \]
當\(s\)不存在時，欽定\(f[s,0]=0\)、\(f[s,1]=-\infty\)。進一步可發現在一條鏈內，鏈頂的\(f[,t]​\)值正是鏈上所有的“G矩陣”（應該明白指的是那個吧）乘起來的第一列值。

因此我們可以樹剖維護重鏈上這些矩陣的乘積，更新時從修改點跳到每條重鏈的鏈頂，計算鏈頂部\(f[,t]\)，更新他父親的\(g[,t]\)（顯然他不是父親的重兒子）,然後再跳往父親所在重鏈……。

也可以lct來做，（試了一下樹剖發現麻煩爆了）每次access修改點到根，然後對這部分重計算就好了。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f;

struct mtr {
    int a[2][2];
    int*operator[](int d) {return a[d];}
    mtr() {memset(a,-inf,sizeof a);}
    mtr operator*(mtr b) {
        mtr c;
        for(int i=0; i<2; ++i) 
        for(int k=0; k<2; ++k) 
        for(int j=0; j<2; ++j) 
            c[i][j]=max(c[i][j],a[i][k]+b[k][j]);
        return c; 
    }
} G[N],PG[N]; 

int n,m,a[N];
int head[N],to[N<<1],last[N<<1];
int fa[N],ch[N][2],dp[N][2];

void add_edge(int x,int y) {
    static int cnt=0;
    to[++cnt]=y,last[cnt]=head[x],head[x]=cnt;
}
void dfs(int x) {
    dp[x][1]=a[x];
    for(int i=head[x]; i; i=last[i]) {
        if(to[i]==fa[x]) continue;
        fa[to[i]]=x;
        dfs(to[i]);
        dp[x][0]+=max(dp[to[i]][0],dp[to[i]][1]);
        dp[x][1]+=dp[to[i]][0];
    }
    G[x][0][0]=G[x][0][1]=dp[x][0];
    G[x][1][0]=dp[x][1];
    PG[x]=G[x];
} 
void update(int x) {
    PG[x]=G[x];
    if(ch[x][0]) PG[x]=PG[ch[x][0]]*PG[x]; //無交換律 
    if(ch[x][1]) PG[x]=PG[x]*PG[ch[x][1]];
}
int get(int x) {
    return ch[fa[x]][0]==x?0:(ch[fa[x]][1]==x?1:-1);
}
void rotate(int x) {
    int y=fa[x],k=get(x);
    if(~get(y)) ch[fa[y]][get(y)]=x;
    fa[x]=fa[y];
    fa[ch[y][k]=ch[x][k^1]]=y;
    fa[ch[x][k^1]=y]=x;
    update(y);
    update(x); 
}
void splay(int x) {
    while(~get(x)) {
        int y=fa[x];
        if(~get(y)) rotate(get(x)^get(y)?x:y);
        rotate(x);
    }
} 
void access(int x) {
    for(int y=0; x; x=fa[y=x]) {
        splay(x);
        if(ch[x][1]) { //舊的重兒子 
            G[x][0][0]+=max(PG[ch[x][1]][0][0],PG[ch[x][1]][1][0]);
            G[x][1][0]+=PG[ch[x][1]][0][0];
        }
        if(y) { //新的重兒子 
            G[x][0][0]-=max(PG[y][0][0],PG[y][1][0]);
            G[x][1][0]-=PG[y][0][0];
        }
        G[x][0][1]=G[x][0][0]; //別忘了 
        ch[x][1]=y;
        update(x);
    }
}
void modify(int x,int y) {
    access(x);
    splay(x);
    G[x][1][0]+=y-a[x];
    update(x);
    a[x]=y;
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i) scanf("%d",a+i);
    for(int x,y,i=n; --i; ) {
        scanf("%d%d",&x,&y);
        add_edge(x,y);
        add_edge(y,x);
    }
    dfs(1); //所有連邊是輕邊 
    for(int x,y; m--; ) {
        scanf("%d%d",&x,&y);
        modify(x,y);
        splay(1);
        printf("%d\n",max(PG[1][0][0],PG[1][1][0]));
    }
    return 0;
}

全局平衡二叉樹

然後講一講這道題的毒瘤加強版。傳送門

數據加強並且經過特殊構造，樹剖和LCT都過不了了。樹剖本身複雜度太大， O(\(m\log^2n\))過不了百萬是很正常的；而LCT雖然只有一個\(\log\) ，但由於常數過大也被卡了。

樹剖的兩個 \(\log\) 基本上可以放棄治療了。但是我們不禁要問，LCT究竟慢在哪裡？

仔細想想，LCT的access複雜度之所以是一個 \(\log​\) ，是由於splay的勢能分析在整棵LCT上依然成立，也就是說可以把LCT看作一棵大splay，在這棵大splay上的一次access只相當於一次splay。

話雖然是這麼說，但是實際上當我們不停地隨機access的時候，要調整的輕重鏈數量還是很多的。感受一下，拿極端情形來說，如果樹是一條鏈，一開始全是輕邊，那麼對鏈末端的結點access一次顯然應該是 \(O(n)\)的。所以其實LCT的常數大就大在它是靠勢能法得到的 \(O(\log n)\)，這麼不靠譜的玩意是容易gg的。

但是如果我們不讓LCT放任自由地access，而是一開始就給它構造一個比較優雅的姿態並讓它靜止（本來這棵樹也不需要動），那麼它也許就有救了。我們可以按照樹鏈剖分的套路先劃分出輕重邊，然後對於重鏈建立一棵形態比較好的splay，至於輕兒子就跟原來的LCT一樣直接用輕邊掛上即可。什麼叫“形態比較好”呢？我們給每個點 \(x​\) 定義其權重為 size[x]-size[son[x]]，其中 son[x] 是它的重兒子，那麼對於一條重鏈，我們可以先找到它的帶權重心作為當前節點，然後對左右分別遞歸建樹。

by GKxx blog

似乎較lct常數更小，也蠻好些的。

#include <bits/stdc++.h> /*卡著時限過*/
using namespace std;

namespace IO {
    const unsigned Buffsize=1<<24,Output=1<<24;
    static char Ch[Buffsize],*St=Ch,*T=Ch;
    inline char getc() {
        return((St==T)&&(T=(St=Ch)+fread(Ch,1,Buffsize,stdin),St==T)?0:*St++);
    }
    static char Out[Output],*nowps=Out;
    inline void flush() {
        fwrite(Out,1,nowps-Out,stdout);
        nowps=Out;
    }
    template<typename T>inline void read(T&x) {
        x=0;
        static char ch;
        T f=1;
        for(ch=getc(); !isdigit(ch); ch=getc())if(ch=='-')f=-1;
        for(; isdigit(ch); ch=getc())x=x*10+(ch^48);
        x*=f;
    }
    template<typename T>inline void write(T x,char ch='\n') {
        if(!x)*nowps++=48;
        if(x<0)*nowps++='-',x=-x;
        static unsigned sta[111],tp;
        for(tp=0; x; x/=10)sta[++tp]=x%10;
        for(; tp; *nowps++=sta[tp--]^48);
        *nowps++=ch;
        flush();
    }
}
using IO::read;
using IO::write;

const int N=1e6+10;
const int inf=0x3f3f3f3f;

struct mtr {
    int a[2][2];
    int*operator[](int x) {return a[x]; }
    inline mtr() {}
    inline mtr(int g0,int g1) {
        a[0][0]=a[0][1]=g0;
        a[1][0]=g1;
        a[1][1]=-inf;
    }
    inline mtr operator*(mtr b) {
        mtr c;
        c[0][0]=max(a[0][0]+b[0][0],a[0][1]+b[1][0]);
        c[0][1]=max(a[0][0]+b[0][1],a[0][1]+b[1][1]);
        c[1][0]=max(a[1][0]+b[0][0],a[1][1]+b[1][0]);
        c[1][1]=max(a[1][0]+b[0][1],a[1][1]+b[1][1]);
        return c;
    }
    void print() {
        printf("%d %d\n%d %d\n\n",a[0][0],a[0][1],a[1][0],a[1][1]); 
    }
};

int n,m,a[N];
int head[N],to[N<<1],last[N<<1];
int siz[N],son[N],g[N][2];
inline void add_edge(int x,int y) {
    static int cnt=0;
    to[++cnt]=y,last[cnt]=head[x],head[x]=cnt;
}
void dfs1(int x,int pa) {
    siz[x]=1;
    g[x][1]=a[x];
    for(int i=head[x]; i; i=last[i]) {
        if(to[i]==pa) continue;
        dfs1(to[i],x);
        siz[x]+=siz[to[i]];
        if(siz[to[i]]>siz[son[x]]) son[x]=to[i];
        g[x][0]+=max(g[to[i]][0],g[to[i]][1]);
        g[x][1]+=g[to[i]][0];
    }
}
void dfs2(int x,int pa) {
    if(!son[x]) return;
    g[x][0]-=max(g[son[x]][0],g[son[x]][1]);
    g[x][1]-=g[son[x]][0];
    for(int i=head[x]; i; i=last[i]) 
        if(to[i]!=pa) dfs2(to[i],x); 
}

mtr G[N],PG[N];
int root,fa[N],ch[N][2];
int stk[N],tp;
bool is_root[N];

inline void update(int x) {
    PG[x]=G[x];
    if(ch[x][0]) PG[x]=PG[ch[x][0]]*PG[x];
    if(ch[x][1]) PG[x]=PG[x]*PG[ch[x][1]];
}
int chain(int l,int r) {
    if(r<l) return 0;
    int sum=0,pre=0;
    for(int i=l; i<=r; ++i) sum+=siz[stk[i]]-siz[son[stk[i]]];
    for(int i=l; i<=r; ++i) {
        pre+=siz[stk[i]]-siz[son[stk[i]]];
        if((pre<<1)>=sum) {
            int x=stk[i];
            ch[x][0]=chain(l,i-1);
            ch[x][1]=chain(i+1,r);
            if(ch[x][0]) fa[ch[x][0]]=x;
            if(ch[x][1]) fa[ch[x][1]]=x;
            update(x);
            return x;
        }
    }
    return 2333;
}
int tree(int top,int pa) {
    for(int x=top; x; x=son[pa=x]) {
        for(int i=head[x]; i; i=last[i]) {
            if(to[i]!=son[x]&&to[i]!=pa) {
                fa[tree(to[i],x)]=x;
            }
        } 
        G[x]=mtr(g[x][0],g[x][1]);
    }
    tp=0;
    for(int x=top; x; x=son[x]) stk[++tp]=x;
    return chain(1,tp);
}
inline void build() {
    root=tree(1,0);
    for(int i=1; i<=n; ++i) {
        is_root[i]=ch[fa[i]][0]!=i&&ch[fa[i]][1]!=i;
    }
}
inline int solve(int x,int y) {
    g[x][1]+=y-a[x];
    a[x]=y;
    for(int f0,f1; x; x=fa[x]) {
        f0=PG[x][0][0];
        f1=PG[x][1][0];
        G[x]=mtr(g[x][0],g[x][1]);
        update(x);
        if(fa[x]&&is_root[x]) {
            g[fa[x]][0]+=max(PG[x][0][0],PG[x][1][0])-max(f0,f1);
            g[fa[x]][1]+=PG[x][0][0]-f0;
        }
    }
    return max(PG[root][0][0],PG[root][1][0]);
}

int main() {
    read(n);
    read(m);
    for(int i=1; i<=n; ++i) read(a[i]);
    for(int x,y,i=n; --i; ) {
        read(x);
        read(y);
        add_edge(x,y);
        add_edge(y,x);
    }
    dfs1(1,0);
    dfs2(1,0);
    build();
    int lastans=0;
    for(int x,y; m--; ) {
        read(x);
        read(y);
        x^=lastans;
        lastans=solve(x,y);
        write(lastans);
    }
    return 0;
}

NOIP18 保衛王國

給出一棵\(n​\)個節點樹和\(m​\)次詢問，每次詢問強制選/不選兩個點然後計算當前樹上的最小覆蓋集，詢問互相獨立。

提示：強制選一個點就是把它的點權改成0，強制不選就是改成 \(\infty\)；最小覆蓋權值+最大獨立集權值=總權值。

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+10;
const long long inf=1e10;

struct mtr {
    long long a[2][2];
    long long*operator[](int x) {return a[x]; }
    inline mtr() {} 
    inline mtr(long long g0,long long g1) {
        a[0][0]=a[0][1]=g0;
        a[1][0]=g1;
        a[1][1]=-inf;
    }
    inline mtr operator*(mtr b) {
        mtr c;
        c[0][0]=max(a[0][0]+b[0][0],a[0][1]+b[1][0]);
        c[0][1]=max(a[0][0]+b[0][1],a[0][1]+b[1][1]);
        c[1][0]=max(a[1][0]+b[0][0],a[1][1]+b[1][0]);
        c[1][1]=max(a[1][0]+b[0][1],a[1][1]+b[1][1]);
        return c;
    }
};

int n,m;
long long a[N],g[N][2];
int head[N],to[N<<1],last[N<<1];
int prt[N],siz[N],son[N];
inline void add_edge(int x,int y) {
    static int cnt=0;
    to[++cnt]=y,last[cnt]=head[x],head[x]=cnt;
}
void dfs1(int x,int pa) {
    siz[x]=1;
    g[x][1]=a[x];
    for(int i=head[x]; i; i=last[i]) {
        if(to[i]==pa) continue;
        prt[to[i]]=x;
        dfs1(to[i],x);
        siz[x]+=siz[to[i]];
        if(siz[to[i]]>siz[son[x]]) son[x]=to[i];
        g[x][0]+=max(g[to[i]][0],g[to[i]][1]);
        g[x][1]+=g[to[i]][0];
    }
}
void dfs2(int x,int pa) {
    if(!son[x]) return;
    g[x][0]-=max(g[son[x]][0],g[son[x]][1]);
    g[x][1]-=g[son[x]][0];
    for(int i=head[x]; i; i=last[i]) 
        if(to[i]!=pa) dfs2(to[i],x); 
}

mtr G[N],PG[N];
int root,fa[N],ch[N][2];
int stk[N],tp;
bool is_root[N];

inline void update(int x) {
    PG[x]=G[x];
    if(ch[x][0]) PG[x]=PG[ch[x][0]]*PG[x];
    if(ch[x][1]) PG[x]=PG[x]*PG[ch[x][1]];
}
int chain(int l,int r) {
    if(r<l) return 0;
    int sum=0,pre=0;
    for(int i=l; i<=r; ++i) sum+=siz[stk[i]]-siz[son[stk[i]]];
    for(int i=l; i<=r; ++i) {
        pre+=siz[stk[i]]-siz[son[stk[i]]];
        if((pre<<1)>=sum) {
            int x=stk[i];
            ch[x][0]=chain(l,i-1);
            ch[x][1]=chain(i+1,r);
            if(ch[x][0]) fa[ch[x][0]]=x;
            if(ch[x][1]) fa[ch[x][1]]=x;
            update(x);
            return x;
        }
    }
    return 2333; 
}
int tree(int top,int pa) {
    for(int x=top; x; x=son[pa=x]) {
        for(int i=head[x]; i; i=last[i]) {
            if(to[i]!=son[x]&&to[i]!=pa) {
                fa[tree(to[i],x)]=x;
            }
        } 
        G[x]=mtr(g[x][0],g[x][1]);
    }
    tp=0;
    for(int x=top; x; x=son[x]) stk[++tp]=x;
    return chain(1,tp);
}
inline void build() {
    root=tree(1,0);
    for(int i=1; i<=n; ++i) {
        is_root[i]=ch[fa[i]][0]!=i&&ch[fa[i]][1]!=i;
    }
}
long long tot,res;
inline void solve(int x,long long y) {
    tot+=y;
    g[x][1]+=y;
    for(long long f0,f1; x; x=fa[x]) {
        f0=PG[x][0][0];
        f1=PG[x][1][0];
        G[x]=mtr(g[x][0],g[x][1]);
        update(x);
        if(fa[x]&&is_root[x]) {
            g[fa[x]][0]+=max(PG[x][0][0],PG[x][1][0])-max(f0,f1);
            g[fa[x]][1]+=PG[x][0][0]-f0;
        }
    }
}
inline void solve(int x,int p,int y,int q) {
    long long sx,sy;
    if(!p&&!q) sx=inf,sy=inf,res=0;
    else if(!p&&q) sx=inf,sy=0,res=a[y];
    else if(p&&!q) sx=0,sy=inf,res=a[x];
    else sx=0,sy=0,res=a[x]+a[y];
    solve(x,sx-a[x]);
    solve(y,sy-a[y]);
    res+=tot-max(PG[root][0][0],PG[root][1][0]);
    solve(x,a[x]-sx);
    solve(y,a[y]-sy);
}

char type[10]; 
int main() { //此代碼 在-O2時極快
    freopen("defense.in","r",stdin);
    freopen("defense.ans","w",stdout); 
    scanf("%d%d%s",&n,&m,type);
    for(int i=1; i<=n; ++i) {
        scanf("%lld",a+i);
        tot+=a[i];
    }
    for(int x,y,i=n; --i; ) {
        scanf("%d%d",&x,&y);
        add_edge(x,y);
        add_edge(y,x);
    }
    dfs1(1,0);
    dfs2(1,0);
    build();
    for(int x,p,y,q; m--; ) {
        scanf("%d%d%d%d",&x,&p,&y,&q);
        if(!p&&!q&&(prt[x]==y||prt[y]==x)) {
            puts("-1");
            continue;
        }
        solve(x,p,y,q);
        printf("%lld\n",res);
    }
    return 0;
}

更多習(tian)題(keng)

bzoj4911 [Sdoi2017]切樹游戲

bzoj4721 洪水


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 創建二維圖
    以下示例演示如何在 MATLAB® 中創建各種二維圖。 線圖 plot 函數用來創建由 x 和 y 值繪製而成的簡單線圖。 x = 0:0.05:5; y = sin(x.^2); figure plot(x,y) 線圖可顯示多組 x 和 y 數據。 y1 = sin(x.^2); y2 = cos ...
  • 雜篇章
    表達式中運算數據類型不一致怎麼辦？ 參數傳遞：就是調用方法的時候，向方法內傳入數據的動作。 形式參數：在定義方法的時候，寫在小括弧之內的參數。(被動接收數據的) eg：public static int sum(int a,int b)//這裡的a和b，是在定義的時候寫的，所以是形式參數即形參。 實 ...
  • Python練手例子（14）
    79、字元串排序。 80、海灘上有一堆桃子，五隻猴子來分。第一隻猴子把這堆桃子平均分為五份，多了一個，這隻猴子把多的一個扔入海中，拿走了一份。第二只猴子把剩下的桃子又平均分成五份，又多了一個，它同樣把多的一個扔入海中，拿走了一份，第三、第四、第五隻猴子都是這樣做的，問海灘上原來最少有多少個桃子？ 8 ...
  • SpringMvc 請求中日期類型參數接收一二事兒
    首先說明：以版本為Spring 4.3.0為測試對象； 開啟<mvc:annotation-driven /> 測試場景一：請求中含有date屬性，該類型為日期類型，SpringMvc採用@RequestParam來接受作為方法入參。 代碼很簡單，第一反應是不能將字元串的date屬性賦給d; 先嘗試 ...
  • 簡單版AC自動機
    簡單版$AC$自動機 學之前聽別人說起一直以為很難，今天學了簡單版的$AC$自動機，感覺海星，只要理解了$KMP$一切都好說。 前置知識： "$KMP$" （有鏈接） 前置知識：$Trie$樹 字典樹（$Trie$樹）比較簡單，就是把許多個單詞通過樹連接起來。每個點記錄一下兒子個數以及是否是單詞結尾 ...
  • 『ACM C++』Virtual Judge | 兩道基礎題 - The Architect Omar && Malek and Summer Semester
    這幾天一直在宿舍跑PY模型，學校的ACM寒假集訓我也沒去成，來學校的時候已經18號了，突然加進去也就上一天然後排位賽了，沒學什麼就去打怕是要被虐成渣，今天開學前一天，看到最後有一場大的排位賽，就上去試了一下，果然被虐成渣，十二道題目在有限時間內就做了四道，還有一道瘋狂的WA，拿出兩道一些有趣的想法出 ...
  • 洛谷P4438 [HNOI/AHOI2018]道路(dp)
    題意 "題目鏈接" Sol ~~每當出題人想起他出的HNOI 2018 Day2T3，他都會激動的拍打著輪椅~~ 讀題比做題用時長系列。。。 $f[i][a][b]$表示從根到$i$的路徑上，有$a$條公路未被翻修，$b$條鐵路未被翻修 然後xjb轉移一下 比較好奇為啥不會MLE.. cpp inc ...
  • 一分鐘快三要怎麼看走勢規律。怎麼看大小單雙走勢呢？
    導師企鵝-359213571如果你此刻十分困難，不要灰心，放平心態，先想想此刻對你來說，到底什麼最為重要，是技術還是本金，是心態還是人脈，把自己梳理清晰，然後設定好步驟，不要慌不要亂，天無絕人之路，勇敢的站起來，你可以的。技術可以通過學習獲得，經驗可以通過實戰得到，心態可以通過調節增強，每一個人都不 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類