标签归档：洛谷

洛谷 寻找道路

发表评论

题号：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;
        }
    }
}

洛谷 尼克的任务

发表评论

题号：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];
}

洛谷 金明的预算方案

发表评论

题号：P1064
一维滚动数组优化。

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
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
int n,m;
int v[65],p[65],q[65],w[65];
int q1[65],q2[65];
int iptr;
int f[35000];
void insert_subgood(int main,int sub){
    if(q1[main]==0)q1[main]=sub;
    else q2[main]=sub;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>v[i]>>p[i]>>q[i];
        w[i]=v[i]*p[i];
        if(q[i]!=0){
            insert_subgood(q[i],i);
        }
    }
    for(int i=1;i<=m;i++){
        if(q[i]!=0)continue;
        for(int j=n;j>=0;j--){
            if(j-v[i]>=0)
                f[j]=max(f[j],f[j-v[i]]+w[i]);
            if(q1[i]!=0&&j-v[i]-v[q1[i]]>=0)
                f[j]=max(f[j],f[j-v[i]-v[q1[i]]]+w[i]+w[q1[i]]);
            if(q2[i]!=0&&j-v[i]-v[q2[i]]>=0)
                f[j]=max(f[j],f[j-v[i]-v[q2[i]]]+w[i]+w[q2[i]]);
            if(q1[i]!=0&&q2[i]!=0&&j-v[i]-v[q1[i]]-v[q2[i]]>=0)
                f[j]=max(f[j],f[j-v[i]-v[q1[i]]-v[q2[i]]]+w[i]+w[q1[i]]+w[q2[i]]);
        }
    }
    cout<<f[n];
}

洛谷 八皇后

发表评论

题号1219

感觉写的非常满意……哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
n=13都不用打表啦！

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
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
int n;
int cnt;//情况计数器
bool line[14],row[14],left_diagonal[26],right_diagonal[26];
//占用情况数组：行；列；左上-右下对角线；右上-左下对角线
int pos[14];
//记录每一行的棋子放在哪一列
inline int calculate_left_dia(int x,int y){//计算x行y列的棋子在第几个左上-右下对角线上
    return x+y-1;
}
inline int calculate_right_dia(int x,int y){//计算x行y列的棋子在第几个右上-左下对角线上
    return (n+1-x)+y-1;
}
void search(int level){//dfs搜索：行
    if(level==n+1){//递归基
        cnt++;
        if(cnt>3)return;
        for(int i=1;i<=n;i++){//输出结果
            cout<<pos[i]<<" ";
        }
        cout<<endl;
    }
    for(int i=1;i<=n;i++){//遍历列
        if(!line[i]&&!row[i]&&!left_diagonal[calculate_left_dia(level,i)]&&!right_diagonal[calculate_right_dia(level,i)]){//满足要求
            pos[level]=i;
            line[i]=true;row[i]=true;
            left_diagonal[calculate_left_dia(level,i)]=true;
            right_diagonal[calculate_right_dia(level,i)]=true;
            search(level+1);//继续深搜
            line[i]=false;row[i]=false;//回溯
            left_diagonal[calculate_left_dia(level,i)]=false;
            right_diagonal[calculate_right_dia(level,i)]=false;
        }
    }
}
int main(){
    cin>>n;
    search(1);
    cout<<cnt;
}

洛谷 滑雪（重要！）

发表评论

题号:P1434
这道题需要留着细细品味……
这道题也挺恶心，用尽各种优化方法……
需要写一下注释，省得我以后看不懂自己写的代码……

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
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int array[105][105];
int memory[105][105];
bool check[105][105];
struct s{
    int x,y,n;
    bool operator < (s& s2){
        return this->n>s2.n;
    }
}ss[11025];
int r,c;
int shift_x[5]={0,-1,1,0,0},shift_y[5]={0,0,0,-1,1};//left,right,up,down
int safe_array(int x,int y){
    if(x>=1&&x<=r&&y>=1&&y<=c)return array[x][y];
    else return -1;
}//保证数组不越界
int dfs(int x,int y,int last){//dfs是从截止点step为0推到起始点的
    if(safe_array(x,y)==-1||last<=array[x][y]||check[x][y])return 0;
    if(memory[x][y]!=-1)return memory[x][y];
    check[x][y]=true;
    int max_=-1;
    for(int i=1;i<=4;i++){
        int t=dfs(x+shift_x[i],y+shift_y[i],array[x][y]);
        if(t>max_)max_=t;
    }
    check[x][y]=false;
    return memory[x][y]=max_+1;
}
int main(){
    memset(memory,-1,sizeof(memory));
    cin>>r>>c;
    int ptr=0;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>array[i][j];
            ss[ptr].x=i;
            ss[ptr].y=j;
            ss[ptr].n=array[i][j];
            ptr++;
        }
    }
    int max_=-1;
    sort(ss,ss+ptr);//先排序，由坡高到坡低去进行dfs，这样坡低的在刚一开始就会因为记忆化搜索直接return
    for(int i=0;i<ptr;i++){
        int t=dfs(ss[i].x,ss[i].y,ss[i].n+1);
        if(t>max_)max_=t;//收集最长路径
    }
    cout<<max_;
}

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
42
43
44
45
46
47
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<functional>
using namespace std;
int r,c;
int arr[105][105];
int f[105][105];
struct node{
    int x,y;
    int v;
    bool operator < (const node& n2){
        return v<n2.v;
    }
}narr[10005];
int narrptr=0;
int main() {
    ios::sync_with_stdio(false);
    memset(arr,0x7f,sizeof(arr));
    cin>>r>>c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>arr[i][j];
            narr[++narrptr].v=arr[i][j];
            narr[narrptr].x=i;
            narr[narrptr].y=j;
        }
    }
    sort(narr+1,narr+r*c+1);
    for(int i=1;i<=narrptr;i++){
        if(narr[i].v>arr[narr[i].x-1][narr[i].y])f[narr[i].x][narr[i].y]=max(f[narr[i].x][narr[i].y],f[narr[i].x-1][narr[i].y]+1);
        if(narr[i].v>arr[narr[i].x+1][narr[i].y])f[narr[i].x][narr[i].y]=max(f[narr[i].x][narr[i].y],f[narr[i].x+1][narr[i].y]+1);
        if(narr[i].v>arr[narr[i].x][narr[i].y-1])f[narr[i].x][narr[i].y]=max(f[narr[i].x][narr[i].y],f[narr[i].x][narr[i].y-1]+1);
        if(narr[i].v>arr[narr[i].x][narr[i].y+1])f[narr[i].x][narr[i].y]=max(f[narr[i].x][narr[i].y],f[narr[i].x][narr[i].y+1]+1);
    }
    int mmax=0;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            mmax=max(mmax,f[i][j]);
        }
    }
    cout<<mmax+1;
}

洛谷 [USACO06FEB]数字三角形Backward Digit Su…

发表评论

题号：P1118

必须用杨辉三角/组合数的方法做，同时要剪枝……这样才能A。不用这个只能60，剩下的全部TLE。

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
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int n,sum;
bool check[13];
int current[13];
int current_temp[13];
int yanghui[13];
int calculate(int k){
    int sum=0;
    for(int i=0;i<k;i++){
        sum+=yanghui[i]*current[i];
    }
    return sum;
}
void search(int level){
    if(level==n&&calculate(n)==sum){
        for(int i=0;i<n;i++){
            cout<<current[i]<<" ";
        }
        exit(0);
    }
    for(int i=1;i<=n;i++){
        if(!check[i]){
            check[i]=true;
            current[level]=i;
            if(calculate(level)<sum)search(level+1);
            check[i]=false;
        }
    }
}
int main(){
    memset(check,false,sizeof(check));
    cin>>n>>sum;
    //calculate yanghui
    yanghui[0]=1;
    for(int i=1;i<n;i++){
        yanghui[i]=(n-i)*yanghui[i-1]/i;
    }
    //end calculate
    search(0);
}

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
#include<iostream>
using namespace std;
int n,sum;
bool visited[15];
int ansarr[15];
int triangle[15][15];
void triangle_init(){
    for(int i=0;i<15;i++){
        triangle[i][0]=1;
        triangle[i][i]=1;  
    }
    for(int i=2;i<15;i++){
        for(int j=1;j<i;j++){
            triangle[i][j]=triangle[i-1][j]+triangle[i-1][j-1];
        }
    }
}
bool dfs(int pos,int s){
    if(pos==n+1)return s==sum;
    if(s>sum)return false;
    for(int i=1;i<=n;i++){
        if(visited[i])continue;
        visited[i]=true;
        ansarr[pos]=i;
        if(dfs(pos+1,s+i*triangle[n-1][pos-1]))return true;
        visited[i]=false;
    }
    return false;
}
int main() {
    triangle_init();
    cin>>n>>sum;
    if(dfs(1,0))for(int i=1;i<=n;i++)cout<<ansarr[i]<<" ";
}

洛谷 拼数

发表评论

题号：1012

这题也挺逗的，没有想到能这么做……
看了别人的题解……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
bool cmp(string & s1,string & s2){
    return s1+s2>s2+s1;
}
int main(){
    int n;
    cin>>n;
    string s[20];
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    sort(s,s+n,cmp);
    for(int i=0;i<n;i++){
        cout<<s[i];
    }
}