分类目录归档：算法

洛谷 智力大冲浪

发表评论

题号：1230
一开始想排完序之后直接从前到后由时间1到时间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
#include<iostream>
#include<algorithm>
using namespace std;
int m, n;
struct s{
    int t;
    int w;
    bool operator < (s & s1){
        if (w != s1.w)return w>s1.w;
        else return t < s1.t;
    }
}arr[505];
bool occupied[505];
int main(){
    ios::sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 1; i <= n; i++){
        cin >> arr[i].t;
    }
    for (int i = 1; i <= n; i++){
        cin >> arr[i].w;
    }
    sort(arr + 1, arr + n + 1);
    for (int i = 1; i <= n; i++){
        if (!occupied[arr[i].t])occupied[arr[i].t] = true;
        else{
            bool flag = false;
            for (int j = arr[i].t - 1; j >= 1;j--){
                if (!occupied[j]){
                    occupied[j] = true;
                    flag = true;
                    break;
                }
            }
            if (!flag)m -= arr[i].w;
        }
    }
    cout << m;
}

洛谷 封锁阳光大学

发表评论

题号：1330
这个属于搜索中的染色问题，之前不会，以后要多多学习。

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<algorithm>
#include<list>
#include<queue>
using namespace std;
list<int> edge[100005];
int n, m;
int point[100005];
inline int color(int x){
    if (x == 1)return 2;
    else return 1;
}
int BFS(int i){
    int cnter1 = 0, cnter2 = 0;
    queue<pair<int, int>> q;
    q.push(pair<int, int>(i, 1));
    while (!q.empty()){
        pair<int, int> cur = q.front(); q.pop();
        if (point[cur.first] != 0){
            if (point[cur.first] != cur.second)return -1;
            continue;
        }
        point[cur.first] = cur.second;
        if (cur.second == 1)cnter1++;
        if (cur.second == 2)cnter2++;
        for (auto iter = edge[cur.first].begin(); iter != edge[cur.first].end(); iter++){
            q.push(pair<int, int>((*iter), color(cur.second)));
        }
    }
    return cnter1 < cnter2 ? cnter1 : cnter2;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    int sum = 0;
    for (int i = 1; i <= n; i++){
        if (point[i] == 0){
            int t=BFS(i);
            if (t == -1){
                cout << "Impossible";
                return 0;
            }
            else
                sum += t;
        }
    }
    cout << sum;
}

20180806：基本上自己做出来了！！哈哈！有个小细节忽略了：是每个互不联通子图分别找出最小值加起来，不是整图统计。

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int n, m;
vector<int> edges[10005];
int color[10005];
inline int getOppoColor(int x) {
    if (x == 1)return 2;
    else return 1;
}
int BFS(int s) {
    int color1 = 0, color2 = 0;
    queue<int> q;
    color[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int node = q.front();
        if (color[node] == 1)color1++;
        else color2++;
        q.pop();
        for (int i = 0; i < edges[node].size(); i++) {
            if (color[edges[node][i]] == 0) {
                color[edges[node][i]] = getOppoColor(color[node]);
                q.push(edges[node][i]);
            }
            else if (color[edges[node][i]] == color[node]) {
                return 0;
            }
        }
    }
    return min(color1, color2);
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    int cnter = 0;
    for (int i = 1; i <= n; i++) {
        if (color[i] == 0 && edges[i].size() != 0) {
            int cur = BFS(i);
            if (cur == 0) {
                cout << "Impossible";
                return 0;
            }
            cnter += cur;
        }
    }

    cout << cnter;
}

计蒜客 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;
}

洛谷 【模板】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];
}