计蒜客 NOIP模拟赛（一） D1T2

发表评论

原题：https://nanti.jisuanke.com/t/16446
北京市八十中的cjr说（特别感谢cjr提供思路，我进行了一下整理）：考虑每条边对答案的贡献：每条边肯定是一个父亲节点与一个儿子节点相连，该边对答案的贡献是size[i]*(n-size[i])*w，其中i为儿子节点，size[i]为该边的儿子节点所对应的子树大小（包括该儿子节点），w[i]为边权，n为总节点数。可以这样做是利用了乘法原理。想象一下，假设一棵有根树，要计算从Node:n到其它所有节点的最短距离：

该边必然要使用1*(n-1)次，该边对答案的贡献就为1*(n-1)*w[i]了。
子树大小由dfs算得即可，因为这是有根树。如果是图的话就不能这么干了，因为两个节点之间不仅仅又1条路径，这时候多源最短路只能用floyd做了。时间复杂度为O(n^3)。
本题第一次计算任意两点间距离之和：初始化子树大小DFS复杂度O(n)，算每条边的贡献O(n)，更改边长复杂度O(1)。

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<list>
using namespace std;
int n,m;
long long father[100005],w[100005];
list<int> children[100005];
long long treesize[100005];
void dfs(int node){//获得子树大小
    if(children[node].size()==0){
        treesize[node]=1;
        return;
    }
    long long tot=0;
    for(list<int>::iterator i=children[node].begin();i!=children[node].end();i++){
        dfs(*i);
        tot+=treesize[*i];
    }
    treesize[node]=tot+1;
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=2;i<=n;i++){
        cin>>father[i]>>w[i];
        children[father[i]].push_back(i);
    }
    dfs(1);
    long long tot=0;
    for(int i=2;i<=n;i++){
        tot+=treesize[i]*(n-treesize[i])*w[i];
    }
    cout<<tot<<endl;
    cin>>m;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        long long change=treesize[a]*(n-treesize[a])*(b-w[a]);
        tot+=change;
        cout<<tot<<endl;
        w[a]=b;
    }
}

计蒜客 NOIP模拟赛（一） D1T1

发表评论

题库链接：https://nanti.jisuanke.com/t/16445
本程序80分：

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
#include<iostream>
using namespace std;
int prefixsum[2005][2005];
int n,k;
int safe_prefix(int x,int y){
    if(x>=1&&x<=n&&y>=1&&y<=n)return prefixsum[x][y];
    return 0;
}
int pong(int x,int y){
    int morse_cnt=0;
    bool flag=false;
    int cnt=0;
    for(int i=x-k+1;i<=x+k-1;i++){
        if(!flag&&cnt==k)flag=true;
        if(!flag)cnt++;
        else cnt--;
        if(i<1||i>n)continue;
        int jmin=y-cnt+1,jmax=y+cnt-1;
        morse_cnt+=safe_prefix(i,jmax)-safe_prefix(i,jmin-1);
    }
    return morse_cnt;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int t;
            cin>>t;
            prefixsum[i][j]=prefixsum[i][j-1]+t;
        }
    }
    int m=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int t=pong(i,j);
            if(t>m)m=t;
        }
    }
    cout<<m;
}

洛谷 高精度减法

发表评论

题号：2142

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
#include<iostream>
#include<string>
using namespace std;
void reverse(string & s){
    for(int i=0;i<s.size()/2;i++){
        swap(s[i],s[s.size()-1-i]);
    }
}
int main(){
    string s1,s2;
    cin>>s1>>s2;
    bool negative=false;
    if(s1.length()>s2.length())
        swap(s1,s2);
    else if(s1.length()==s2.length()){
        if(s1>=s2)swap(s1,s2);
        else negative=true;
    }else
        negative=true;
    reverse(s1);
    reverse(s2);
    int s1len=s1.length(),s2len=s2.length();
    for(int i=0;i<s1len;i++){
        s2[i]-=s1[i]-'0';
    }
    for(int i=0;i<s2len-1;i++){
        if(s2[i]<'0'){
            s2[i+1]-=1;
            s2[i]+=10;
        }
    }
    if(s2[s2len-1]=='0'){
        s2.erase(s2.end()-1);
    }
    while(s2[s2.size()-1]=='0'&&s2.size()>1)
        s2.erase(s2.end()-1);
    reverse(s2);
    if(negative)cout<<"-";
    cout<<s2;
}

洛谷 高精度加法

发表评论

题号：1601

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
#include<iostream>
#include<string>
using namespace std;
void reverse(string & s){
    for(int i=0;i<s.size()/2;i++){
        swap(s[i],s[s.size()-1-i]);
    }
}
int main(){
    string s1,s2;
    cin>>s1>>s2;
    if(s1.length()>s2.length()){
        swap(s1,s2);
    }
    reverse(s1);
    reverse(s2);
    int s1len=s1.length(),s2len=s2.length();
    for(int i=0;i<s1len;i++){
        s2[i]+=s1[i]-'0';
    }
    for(int i=0;i<s2len-1;i++){
        if(s2[i]>'9'){
            s2[i+1]+=(s2[i]-'0')/10;
            s2[i]='0'+(s2[i]-'0')%10;
        }
    }
    if(s2[s2len-1]>'9'){
        s2.append(1,'0'+(s2[s2len-1]-'0')/10);
        s2[s2len-1]='0'+(s2[s2len-1]-'0')%10;
    }
    reverse(s2);
    cout<<s2;
}

洛谷 寻找道路

发表评论

题号：P2296

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<cstring>
#include<queue>
#define MapLoop(e,node) for(int e=first[node];e!=-1;e=_next[e])
#define MapLoopRvs(e,node) for(int e=first_rvs[node];e!=-1;e=_next_rvs[e])
using namespace std;
int n,m,s,t;
int first[10005],u[200005],v[200005],_next[200005];//两个图，一个正图，一个反图
int first_rvs[10005],u_rvs[200005],v_rvs[200005],_next_rvs[200005];
int _distance[10005];
bool OK[10005],OK2[10005];
bool visited[10005];
bool inqueue[10005];
queue<int> q,q1;
void bfs(int node){//反图用来遍历与终点不联通的点
    q1.push(node);
    visited[node]=true;
    OK[node]=true;
    while(!q1.empty()){
        int cur=q1.front();
        q1.pop();
        OK[cur]=true;
        MapLoopRvs(e,cur){
            if(!visited[v_rvs[e]]){
                visited[v_rvs[e]]=true;
                q1.push(v_rvs[e]);
            }
        }
    }
    memcpy(OK2,OK,sizeof(OK));//将与终点不联通的点的邻接点全部删除
    for(int i=1;i<=n;i++){
        if(OK[i]==false){
            MapLoopRvs(e,i){
                OK2[v_rvs[e]]=false;
            }
        }
    }
    memcpy(OK,OK2,sizeof(OK));
}
void SPFA(){//SPFA求最短路
    int cnt=0;
    memset(_distance,0x7f,sizeof(_distance));
    q.push(s);
    _distance[s]=0;
    inqueue[s]=true;
    while(!q.empty()){
        int cur=q.front();
        q.pop();
        inqueue[cur]=false;
        MapLoop(e,cur){
            if(_distance[v[e]]>_distance[u[e]]+1&&OK[v[e]]){//注意只能要没有删去的点
                _distance[v[e]]=_distance[u[e]]+1;
                if(!inqueue[v[e]]){
                    inqueue[v[e]]=true;
                    q.push(v[e]);
                    cnt++;
                }
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    memset(first,-1,sizeof(first));
    memset(first_rvs,-1,sizeof(first_rvs));
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i];
        v_rvs[i]=u[i];
        u_rvs[i]=v[i];
        if(u[i]==v[i]){
            i--;
            m--;
            continue;
        }
        _next[i]=first[u[i]];
        first[u[i]]=i;
        _next_rvs[i]=first_rvs[u_rvs[i]];//建反图
        first_rvs[u_rvs[i]]=i;
    }
    cin>>s>>t;
    bfs(t);
    SPFA();
    if(_distance[t]>1e9)cout<<"-1";
    else cout<<_distance[t];
}

洛谷 逆序对

发表评论

题号：1908

讲道理，这个是我之前在洛谷上做的，今天突然看到逆序对这个问题，感觉很重要，然后就回洛谷翻评测记录把逆序对这道题找出来把代码贴到博客上。

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
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
int n,arr[40005],arr_temp[40005];
int cnt;
void MergeSort(int start,int end){//[start,end]
    if(start==end)return;
    MergeSort(start,(start+end)/2);
    MergeSort((start+end)/2+1,end);
    memcpy(arr_temp+start,arr+start,sizeof(int)*(end-start+1));
    int ptr1=start,ptr2=(start+end)/2+1,ptr_main=start;
    while(ptr1<=(start+end)/2&&ptr2<=end){
        if(arr_temp[ptr1]<arr_temp[ptr2]){
            arr[ptr_main]=arr_temp[ptr1];
            ptr1++;
        }else{
            arr[ptr_main]=arr_temp[ptr2];
            ptr2++;
            cnt+=(start+end)/2-ptr1+1;
        }
        ptr_main++;
    }
    for(;ptr1<=(start+end)/2;ptr1++){
        arr[ptr_main]=arr_temp[ptr1];
        ptr_main++;
    }
    for(;ptr2<=end;ptr2++){
        arr[ptr_main]=arr_temp[ptr2];
        ptr_main++;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>arr[i];
    MergeSort(1,n);
    cout<<cnt;
}

20180730更新：又写了一遍，再贴代码：

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<functional>
using namespace std;
int n;
int arr[40005];
int tmparr[40005], tmparr2[40005];
int rop = 0;
void mergeSort(int l, int r) {
    if (l == r)return;
    int ls = l, le = (l + r) / 2, rs = (l + r) / 2 + 1, re = r;
    mergeSort(ls, le);
    mergeSort(rs, re);
    int lp = ls, rp = rs, cp = l;
    while (lp <= le && rp <= re) {
        if (tmparr[lp] < tmparr[rp])tmparr2[cp++] = tmparr[lp++];
        else {
            tmparr2[cp++] = tmparr[rp++];
            rop += le - lp +1;
        }
    }
    for (; lp <= le; lp++)tmparr2[cp++] = tmparr[lp];
    for (; rp <= re; rp++)tmparr2[cp++] = tmparr[rp];
    memcpy(tmparr + l, tmparr2 + l, sizeof(int)*(r - l + 1));
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> arr[i];
    memcpy(tmparr, arr, sizeof(arr));
    mergeSort(1, n);
    cout << rop;
}

20200409更新：题目更新了，数据加强了。做了小小改动。

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
#include<iostream>
#include<cstring>
using namespace std;
long long n;
long long arr[500005];
long long tmparr[500005], tmparr2[500005];
long long rop = 0;
void mergeSort(long long l, long long r) {
    if (l == r)return;
    long long ls = l, le = (l + r) / 2, rs = (l + r) / 2 + 1, re = r;
    mergeSort(ls, le);
    mergeSort(rs, re);
    long long lp = ls, rp = rs, cp = l;
    while (lp <= le && rp <= re) {
        if (tmparr[lp] <= tmparr[rp])tmparr2[cp++] = tmparr[lp++];
        else {
            tmparr2[cp++] = tmparr[rp++];
            rop += le - lp + 1;
        }
    }
    for (; lp <= le; lp++)tmparr2[cp++] = tmparr[lp];
    for (; rp <= re; rp++)tmparr2[cp++] = tmparr[rp];
    memcpy(tmparr + l, tmparr2 + l, sizeof(long long) * (r - l + 1));
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (long long i = 1; i <= n; i++)cin >> arr[i];
    memcpy(tmparr, arr, sizeof(arr));
    mergeSort(1, n);
    cout << rop;
}

洛谷 【模板】树状数组 1

发表评论

题号：3374

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
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
struct treearray{
    const static int MAX=500005;
    int C[MAX];
    treearray(){
        memset(C,0,sizeof(C));
    }
    int lowbit(int i){
        return i&(-i);
    }
    void update(int i,int n){
        while(i<=MAX){
            C[i]+=n;
            i+=lowbit(i);
        }
    }
    int sum(int k){
        int sum=0;
        while(k>0){
            sum+=C[k];
            k-=lowbit(k);
        }
        return sum;
    }
}ta;
int main(){
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        ta.update(i,t);
    }
    for(int i=1;i<=m;i++){
        int p1,p2,p3;
        cin>>p1>>p2>>p3;
        switch(p1){
        case 1:
            ta.update(p2,p3);
            break;
        case 2:
            cout<<(ta.sum(p3)-ta.sum(p2-1))<<endl;
            break;
        }
    }
}

洛谷 【模板】KMP字符串匹配

发表评论

题号：3375

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
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
int _next[10000];
void buildNext(char * P){
    int m=strlen(P),j=0;
    int t=_next[0]=-1;
    while(j<m){
        if(t<0||P[j]==P[t]){
            _next[++j]=++t;
        }else
            t=_next[t];
    }
}
void KMP(char * P,char * T){
    int n=strlen(T),i=0;
    int m=strlen(P),j=0;
    while(i<n){
        if(j<0||T[i]==P[j]){
            i++;j++;
        }else
            j=_next[j];
        if(j==m){
            printf("%d\n",i-j+1);
            j=_next[j];
        }
    }
}
int main(){
    char P[10000],T[20000000];
    scanf("%s%s",T,P);
    buildNext(P);
    int lenP=strlen(P);
    KMP(P,T);
    for(int i=1;i<=lenP;i++){
        printf("%d ",_next[i]);
    }
}

KMP算法经典代码

发表评论
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int _next[10000];
void buildNext(char * P){
    int m=strlen(P),j=0;
    int t=_next[0]=-1;
    while(j<m){
        if(t<0||P[j]==P[t]){
            _next[++j]=++t;
        }else
            t=_next[t];
    }
}
int KMP(char * P,char * T){
    int n=strlen(T),i=0;
    int m=strlen(P),j=0;
    while(i<n&&j<m){
        if(j<0||T[i]==P[j]){
            i++;j++;
        }else
            j=_next[j];
    }
    return i-j;
}

洛谷 尼克的任务

发表评论

题号：P1280
参考：http://blog.csdn.net/zhhx2001/article/details/52213855
https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1280
作者: Radium_ 更新时间: 2016-08-25 12:58

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
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
int n,k;
struct s{
int start;
int duration;
bool operator < (s & o1){
    return start<o1.start;
}
}info[10005];
int f[10005];
int taskptr;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=k;i++)cin>>info[i].start>>info[i].duration;
    sort(info+1,info+k+1);
    taskptr=k;
    for(int i=n;i>=1;i--){
        if(info[taskptr].start!=i)
            f[i]=f[i+1]+1;
        else
            while(info[taskptr].start==i){
                f[i]=max(f[i],f[i+info[taskptr].duration]);
                taskptr--;
            }
    }
    cout<<f[1];
}

20180802更新：
查看的题解：https://www.luogu.org/blog/user3573/solution-p1280

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<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n, k;
struct task {
    int p, t;
    bool operator < (const task& t2) const {
        return p > t2.p;
    }
}ts[10005];
int f[10005];
int main(){
    cin >> n >> k;
    for (int i = 1; i <= k; i++)cin >> ts[i].p >> ts[i].t;
    sort(ts + 1, ts + k + 1);
    int tsptr = 1;
    for (int i = n; i > 0; i--) {
        if (ts[tsptr].p != i) {
            f[i] = f[i + 1] + 1;
            continue;
        }
        while (ts[tsptr].p == i) {
            f[i] = max(f[i], f[i + ts[tsptr].t]);
            tsptr++;
        }
    }
    cout << f[1];
}