洛谷 P3373 【模板】线段树 2

发表评论

总算写出来了。。。线段树同时维护乘法和加法，欢迎体验！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
using namespace std;
struct segmentTree{
    typedef long long ll;
    const static int MAX=100000;
    ll MOD;
    ll v[4*MAX],aTg[4*MAX],mTg[4*MAX];
    inline static ll lson(ll r){return r*2;}
    inline static ll rson(ll r){return r*2+1;}
    void build(ll r,ll* a,ll s,ll e){
        aTg[r]=0;mTg[r]=1;
        if(s==e){v[r]=a[s]%MOD;return;}
        ll m=(s+e)>>1;
        build(lson(r),a,s,m);
        build(rson(r),a,m+1,e);
        v[r]=(v[lson(r)]+v[rson(r)])%MOD;
    }
    void pushDown(ll r,ll s,ll e){
        if(aTg[r]==0&&mTg[r]==1)return;
        ll m=(s+e)>>1;
        v[lson(r)]=(v[lson(r)]*mTg[r]%MOD+aTg[r]*(m-s+1)%MOD)%MOD;
        v[rson(r)]=(v[rson(r)]*mTg[r]%MOD+aTg[r]*(e-m)%MOD)%MOD;
        aTg[lson(r)]=(aTg[lson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
        aTg[rson(r)]=(aTg[rson(r)]*mTg[r]%MOD+aTg[r]%MOD)%MOD;
        mTg[lson(r)]=(mTg[lson(r)]*mTg[r])%MOD;
        mTg[rson(r)]=(mTg[rson(r)]*mTg[r])%MOD;
        aTg[r]=0;mTg[r]=1;
    }
    ll query(ll r,ll cs,ll ce,ll qs,ll qe){
        if(qe<cs||ce<qs)return 0;
        if(qs<=cs&&ce<=qe)return v[r]%MOD;
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        return (query(lson(r),cs,cmd,qs,qe)+query(rson(r),cmd+1,ce,qs,qe))%MOD;
    }
    void update(ll r,ll cs,ll ce,ll us,ll ue,ll addv=0,ll mulv=1){
        if(ue<cs||ce<us)return;
        if(us<=cs&&ce<=ue){
            v[r]=(v[r]*mulv%MOD+addv*(ce-cs+1))%MOD;
            aTg[r]=(aTg[r]*mulv%MOD+addv)%MOD;
            mTg[r]=(mTg[r]*mulv)%MOD;
            return;
        }
        pushDown(r,cs,ce);
        ll cmd=(cs+ce)>>1;
        update(lson(r),cs,cmd,us,ue,addv,mulv);
        update(rson(r),cmd+1,ce,us,ue,addv,mulv);
        v[r]=(v[lson(r)]+v[rson(r)])%MOD;
    }
}ST;
typedef long long ll;
ll n,m,p;
ll a[100005];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++)cin>>a[i];
    ST.MOD=p;
    ST.build(1,a,1,n);
    for(int i=1;i<=m;i++){
        ll op,x,y,k;
        cin>>op;
        if(op==1||op==2){
            cin>>x>>y>>k;
            if(op==1)ST.update(1,1,n,x,y,0,k);
            else ST.update(1,1,n,x,y,k);
        }else{
            cin>>x>>y;
            cout<<ST.query(1,1,n,x,y)%p<<endl;
        }
    }
}

洛谷 P3368 【模板】树状数组 2

发表评论

看起来实际上也挺好做的，就是只要把树状数组维护的对象改成原序列的差分数组即可。这样每次树状数组所谓的query求1到n的前缀和也就变成了就单点n的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<cstring>
using namespace std;
struct BTA{//Update Section,Query Single Point
    const static int MAX=500000;
    int C[MAX+5];
    BTA(){
        memset(C,0,sizeof(C));
    }
    int lowbit(int i){
        return i&(-i);
    }
    int query(int x){
        int sum=0;
        while(x>0){
            sum+=C[x];
            x-=lowbit(x);
        }
        return sum;
    }
    void update(int i,int v){
        while(i<=MAX){
            C[i]+=v;
            i+=lowbit(i);
        }
    }
    void updateSection(int l,int r,int v){
        update(l,v);
        update(r+1,-v);
    }
}TA;
int n,m;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int v;
        cin>>v;
        TA.updateSection(i,i,v);
    }
    for(int i=1;i<=m;i++){
        int op,v1,v2,v3;
        cin>>op;
        if(op==1){
            cin>>v1>>v2>>v3;
            TA.updateSection(v1,v2,v3);
        }
        else{
            cin>>v1;
                cout<<TA.query(v1)<<endl;
        }
    }
}

洛谷 P1197 [JSOI2008]星球大战

发表评论

总算是没看题解自己A了一道题，呜呜呜。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<vector>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;
int father[400005];
int _find(int node){
    if(father[node]==-1)return node;
    return father[node]=_find(father[node]);
}
bool _union(int x,int y){
    if(_find(x)==_find(y))return false;
    father[_find(x)]=_find(y);
    return true;
}
int n,m,k;
bool alive[400005];
vector<int> edges[400005];
stack<int> ans;
stack<int> q;
int cnt,cntn;
int main(){
    ios::sync_with_stdio(false);
    memset(father,-1,sizeof(father));
    memset(alive,true,sizeof(alive));
    cin>>n>>m;
    cnt=0;cntn=n;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    cin>>k;
    for(int i=1;i<=k;i++){
        int v;
        cin>>v;
        alive[v]=false;
        q.push(v);
        cntn--;
    }
    for(int i=0;i<n;i++){
        if(!alive[i])continue;
        for(int j=0;j<edges[i].size();j++){
            if(!alive[edges[i][j]])continue;
            if(_union(i,edges[i][j]))cnt++;
        }
    }
    ans.push(cntn-cnt);
    while(!q.empty()){
        int cur=q.top();q.pop();
        cntn++;
        alive[cur]=true;
        for(int i=0;i<edges[cur].size();i++){
            if(!alive[edges[cur][i]])continue;
            if(_union(cur,edges[cur][i]))cnt++;
        }
        ans.push(cntn-cnt);
    }
    while(!ans.empty()){
        cout<<ans.top()<<endl;
        ans.pop();
    }
}

洛谷 P1199 三国游戏

发表评论

https://www.luogu.org/blog/user23248/solution-p1199

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;
int n,a[501][501],maxV;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            cin>>a[i][j];
            a[j][i]=a[i][j];   
        }
    }
    for(int i=1;i<=n;i++){
        sort(a[i]+1,a[i]+n+1);
        maxV=max(maxV,a[i][n-1]);
    }
    cout<<1<<endl<<maxV;
}

洛谷 P1373 小a和uim之大逃离

发表评论

自己博客上好像全是代码了，正经的题解还没多少。。。
代码还都是一堆看别人题解写出来的。
https://www.luogu.org/blog/yh1127/solution-p1373

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<cstring>
#define MOD 1000000007
using namespace std;
int f[805][805][17][2],a[805][805];
int n,m,k,ans;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    k++;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        cin>>a[i][j];
        f[i][j][a[i][j]][0]=1;
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)for(int p=0;p<=k-1;p++){
        f[i][j][p][1]+=f[i][j-1][(p+a[i][j])%k][0];
        f[i][j][p][1]%=MOD;
        f[i][j][p][1]+=f[i-1][j][(p+a[i][j])%k][0];
        f[i][j][p][1]%=MOD;
        f[i][j][p][0]+=f[i][j-1][(p-a[i][j]+k)%k][1];
        f[i][j][p][0]%=MOD;
        f[i][j][p][0]+=f[i-1][j][(p-a[i][j]+k)%k][1];
                f[i][j][p][0]%=MOD;
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
        ans+=f[i][j][0][1];
        ans%=MOD;
    }
    cout<<ans;
}

洛谷 P2279 [HNOI2003]消防局的设立

发表评论

看了下题解，用贪心写的。动规真心不会。贪心还凑和。
参见题解：https://waautomaton.blog.luogu.org/solution-p2279

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int n;
vector<int> edges[1005];
int depth[1005],father[1005],grandfather[1005];
struct node{
    int i,dep;
    node(int ii,int depp){i=ii;dep=depp;}
    bool operator < (const node& n2) const{
        return dep<n2.dep;
    }
};
priority_queue<node> pq;
bool visited[1005];
void dfsRange2(int pos,int dep){
//为什么这里不能发现visited之后就return呢，是因为有可能一个点虽被visited，但其周围的点未被扩展完全，所以其实visited在这里面没有任何作用，如果把注释去掉是20分的。
    //if(visited[pos])return;
    visited[pos]=true;
    if(dep==2)return;
    for(int i=0;i<edges[pos].size();i++){
        //if(visited[edges[pos][i]])continue;
        dfsRange2(edges[pos][i],dep+1);
    }
}
void dfsAll(int pos,int f,int gf,int dep){
    if(visited[pos])return;
    visited[pos]=true;
    father[pos]=f;
    grandfather[pos]=gf;
    depth[pos]=dep;
    for(int i=0;i<edges[pos].size();i++){
        if(visited[edges[pos][i]])continue;
        dfsAll(edges[pos][i],pos,f,dep+1);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=2;i<=n;i++){
        int v;
        cin>>v;
        edges[i].push_back(v);
        edges[v].push_back(i);
    }
    memset(visited,false,sizeof(visited));
    dfsAll(1,1,1,1);
    memset(visited,false,sizeof(visited));
    for(int i=1;i<=n;i++)pq.push(node(i,depth[i]));
    int cnter=0;
    while(!pq.empty()){
        if(visited[pq.top().i]){
            pq.pop();
            continue;
        }
        node cur=pq.top();pq.pop();
        dfsRange2(grandfather[cur.i],0);
        cnter++;
    }
    cout<<cnter;
}

洛谷 P1220 关路灯

发表评论

我递推啥都不会写垃圾死了，一道对我来说用递推非常难以解决的、难以思考的DP题目被我用记忆化递归解决了，0ms，高兴死我啦！
哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈，代码写的那么长。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<cstring>
using namespace std;
int n,c;
int pos[55],power[55];
int prefixPower[55];
int f[55][55][2];
inline int getEnergy(int l,int r){
    return prefixPower[n]-prefixPower[r]+prefixPower[l-1];
}
int dp(int l,int r,int d){
    if(f[l][r][d]!=-1)return f[l][r][d];
    if(l==1&&r==n)return f[l][r][d]=0;
    if(l==1&&r<n)return f[l][r][d]=getEnergy(l,r)*(d?pos[r+1]-pos[r]:pos[r+1]-pos[l])+dp(l,r+1,1);
    if(l>1&&r==n)return f[l][r][d]=getEnergy(l,r)*(d?pos[r]-pos[l-1]:pos[l]-pos[l-1])+dp(l-1,r,0);
    else return f[l][r][d]=min(getEnergy(l,r)*(d?pos[r]-pos[l-1]:pos[l]-pos[l-1])+dp(l-1,r,0),getEnergy(l,r)*(d?pos[r+1]-pos[r]:pos[r+1]-pos[l])+dp(l,r+1,1));
}
int main(){
    ios::sync_with_stdio(false);
    memset(f,-1,sizeof(f));
    cin>>n>>c;
    for(int i=1;i<=n;i++)cin>>pos[i]>>power[i];
    for(int i=1;i<=n;i++)prefixPower[i]=prefixPower[i-1]+power[i];
    cout<<min(dp(c,c,0),dp(c,c,1));
}

洛谷 P1290 欧几里德的游戏

发表评论

又是一道博弈论：题解：
https://www.luogu.org/blog/DJCreeper/p1290-ti-xie

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<algorithm>
using namespace std;
void Stan(int,int);
void Ollie(int,int);
void Stan(int i,int j){
    if(i==j||i/j>=2)cout<<"Stan wins"<<endl;
    else Ollie(max(i-j,j),min(i-j,j));
}
void Ollie(int i,int j){
    if(i==j||i/j>=2)cout<<"Ollie wins"<<endl;
        else Stan(max(i-j,j),min(i-j,j));
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int v1,v2;
        cin>>v1>>v2;
        if(v1<v2)swap(v1,v2);
        Stan(v1,v2);
    }
}

洛谷 P1441 砝码称重

发表评论

先写了个两层搜索，后来又参考题解改了个搜索+动态规划。
题解：https://www.luogu.org/blog/yeyangrui/solution-p1441
60分搜索：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<algorithm>
#include<cstring>
#define NINF 0x80000000
using namespace std;
int n,m;
bool mass[2005];
int weight[25];
bool visited[25];
void dfs(int pos,int num){
    if(pos==n+1)return;
    if(visited[pos]){
        dfs(pos+1,num);
        return;
    }
    mass[num+weight[pos]]=true;
    dfs(pos+1,num+weight[pos]);
    mass[num]=true;
    dfs(pos+1,num);
}
int getMassCounts(){
    memset(mass,false,sizeof(mass));
    dfs(1,0);
    int cnter=0;
    for(int i=1;i<=n*100;i++)if(mass[i])cnter++;
    return cnter;
}
int genCombination(int pos,int num){
    if(num==m)return getMassCounts();
    if(pos>n)return NINF;
    int maxC=NINF;
    visited[pos]=true;
    maxC=max(maxC,genCombination(pos+1,num+1));
    visited[pos]=false;
    maxC=max(maxC,genCombination(pos+1,num));
    return maxC;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>weight[i];
    cout<<genCombination(1,0);
}

100分动规：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<algorithm>
#include<cstring>
#define NINF 0x80000000
using namespace std;
int n,m;
int f[2005];
int weight[25];
bool visited[25];
int getMassCounts(){
    memset(f,0,sizeof(f));
    f[0]=1;
    for(int i=1;i<=n;i++){
        if(visited[i])continue;
        for(int j=2000;j>=0;j--){
            if(j+weight[i]<=2000&&f[j]!=0)f[j+weight[i]]=1;
        }
    }
    int cnter=0;
    for(int i=1;i<=2000;i++)if(f[i])cnter++;
    return cnter;
}
int genCombination(int pos,int num){
    if(num==m)return getMassCounts();
    if(pos>n)return NINF;
    int maxC=NINF;
    visited[pos]=true;
    maxC=max(maxC,genCombination(pos+1,num+1));
    visited[pos]=false;
    maxC=max(maxC,genCombination(pos+1,num));
    return maxC;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>weight[i];
    cout<<genCombination(1,0);
}

洛谷 P2320 [HNOI2006]鬼谷子的钱袋

发表评论

想不出来：参考题解：
https://www.luogu.org/blog/user50514/solution-p2320
https://www.luogu.org/blog/user26625/solution-p2320

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll ans,n,z[70];
int main(){
    cin>>n;
    while(n){
        z[++ans]=(n+1)/2;
        n/=2;
    }
    sort(z+1,z+ans+1);
    cout<<ans<<endl;
    for(int i=1;i<=ans;i++)cout<<z[i]<<" ";
}