日度归档：15 8 月, 2018

洛谷 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;
}