分类目录归档：贪心

UVA1368 DNA序列 DNA Consensus String

发表评论

解题思路是，统计所有字符串对应位置上出现次数最多的字母，并将其拼接起来作为Hamming距离和最小的DNA序列，也可以算作贪心。

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>
#include<cmath>
#include<cstring>
#include<typeinfo>
using namespace std;
int t, m, n;
int seq[5];
string strArr[1005];
inline void seqSet(char c) {
    switch (c) {
    case 'A':seq[1]++; break;
    case 'C':seq[2]++; break;
    case 'G':seq[3]++; break;
    case 'T':seq[4]++; break;
    }
}
char seqGet[6] = " ACGT";
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> m >> n;
        for (int i = 1; i <= m; i++)cin >> strArr[i];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            memset(seq, 0, sizeof(seq));
            for (int k = 1; k <= m; k++)seqSet(strArr[k][i]);
            int Pmax = 1;
            for (int p = 2; p <= 4; p++)
                if (seq[p] > seq[Pmax])
                    Pmax = p;
            cnt += m - seq[Pmax];
            cout << seqGet[Pmax];
        }
        cout << '\n';
        cout << cnt << '\n';
    }
}

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

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

洛谷 P1233 木棍加工

发表评论

不好做啊……想不出来……看题解……

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<string>
#include<algorithm>
using namespace std;
int n;
struct node {
    int l, w;
    bool operator < (const node& n2) const {
        if (l != n2.l)return l > n2.l;
        if (w != n2.w)return w > n2.w;
        return false;
    }
}arr[5005];
bool visited[5005];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i].l >> arr[i].w;
    }
    sort(arr + 1, arr + n + 1);
    bool flag = false;
    int cnter = 0, ptr = 0;
    do {
        flag = false;
        for (ptr=1;ptr <= n; ptr++) {
            if (!visited[ptr]) {
                flag = true;
                visited[ptr] = true;
                break;
            }
        }
        if (!flag)break;
        cnter++;
        for (int i = ptr+1; i <= n; i++) {
            if (visited[i] || arr[i].l > arr[ptr].l || arr[i].w > arr[ptr].w) continue;
            visited[i] = true;
            ptr = i;
        }
    } while (flag);
    cout << cnter;
}

洛谷 P1080 国王游戏

发表评论

这题不好写，一个问题在贪心怎么排序，再有的难点就是高精乘/除，都不好写。。
这次正经的写了个高精度乘/除。。留下来备用。

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int n;
struct bigInt { //For Non-negative Numbers
private:
    string v;
    static string & bIsort(string & v) { //each char has reduced '0'
        for (int i = 0; i < v.length(); i++) {
            if (v[i] > 9) {
                if (i == v.length() - 1)v.append(1, v[i] / 10);
                else v[i + 1] += v[i] / 10;
                v[i] %= 10;
            }
        }
        return v;
    }
    static string lng2str(long long v) {
        string s = "";
        while (v) {
            s.append(1, v % 10 + '0');
            v /= 10;
        }
        reverse(s.begin(), s.end());
        return s;
    }
    static string& trimPre0(string& v3) {
        while (v3.length() != 0 && (*v3.begin()) == '0')v3.erase(v3.begin());
        if (v3.length() == 0)v3 = "0";
        return v3;
    }
public:
    bigInt() {
        v = "0";
    }
    bigInt(long long n) {
        v = lng2str(n);
    }
    bigInt(string s) {
        v = s;
    }
    bigInt& operator = (const bigInt & bI) {
        this->v = bI.v;
        return *this;
    }
    bigInt operator * (bigInt bI2) const {
        string v1 = v, v2 = bI2.v;
        if (v2.length() > v1.length())swap(v1, v2);
        reverse(v1.begin(), v1.end());
        reverse(v2.begin(), v2.end());
        string v3 = "";
        for (int i = 0; i < v1.length(); i++)v1[i] -= '0';
        for (int i = 0; i < v2.length(); i++)v2[i] -= '0';
        v3.resize(v1.length() + v2.length(), 0);
        for (int i = 0; i < v2.length(); i++) {
            for (int j = 0; j < v1.length(); j++) {
                v3[i + j] += v2[i] * v1[j];
            }
            bIsort(v3);
        }
        for (int i = 0; i < v3.length(); i++)v3[i] += '0';
        reverse(v3.begin(), v3.end());
        trimPre0(v3);
        return bigInt(v3);
    }
    bigInt operator / (long long bI2) const {
        string v1 = v;
        for (int i = 0; i < v1.length(); i++)v1[i] -= '0';
        long long v2 = bI2;
        string v3 = "";
        long long div = 0;
        for (int i = 0; i < v1.length(); i++) {
            div *= 10;
            div += v1[i];
            if (div < v2) {
                v3.append(1, '0');
                continue;
            }
            v3.append(lng2str(div / v2));
            div %= v2;
        }
        return bigInt(trimPre0(v3));
    }
    bool operator < (bigInt bI2) const {
        if (v.length() != bI2.v.length())return v.length() < bI2.v.length();
        for (int i = 0; i < v.length(); i++) {
            if (v[i] != bI2.v[i])return v[i] < bI2.v[i];
        }
        return false;
    }
    friend istream& operator >> (istream& in, bigInt& bI) {
        in >> bI.v;
        return in;
    }
    friend ostream& operator << (ostream& out, bigInt& bI) {
        out << bI.v;
        return out;
    }
};
struct p {
    bigInt a;
    int b;
    bool operator < (const p& p2) {
        return a * b < p2.a*p2.b;
    }
}ps[1005];

int main() {
    cin >> n;
    for (int i = 1; i <= n + 1; i++) {
        cin >> ps[i].a >> ps[i].b;
    }
    sort(ps + 2, ps + n + 2);
    bigInt multiply = ps[1].a;
    bigInt mmax("0");
    for (int i = 2; i <= n + 1; i++) {
        mmax = max(mmax, multiply / ps[i].b);
        multiply =multiply* ps[i].a;
    }
    cout << mmax;
}

Codeforces Round #494 (Div. 3) 1003 A/C/D题解

发表评论

A题：非常简单，只要找重复数字的最大个数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<algorithm>
using namespace std;
int arr[105];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int tmp;
        cin>>tmp;
        arr[tmp]++;
    }
    int maxn=0;
    for(int i=1;i<=100;i++){
        maxn=max(maxn,arr[i]);
    }
    cout<<maxn;
}

C题：用个前缀和优化一下，剩下的暴力去吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
int n,k;
double arr[5005];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>arr[i];
    for(int i=2;i<=n;i++)arr[i]+=arr[i-1];
    double maxavg=0,curavg;
    for(int i=k;i<=n;i++){
        for(int j=i;j<=n;j++){
            curavg=(arr[j]-arr[j-i])/i;
            maxavg=max(maxavg,curavg);
        }
    }
    printf("%.15lf",maxavg);
}

D题：把所有二的次幂数全部搞到桶里，然后按照次幂由高到低往下减，看最后能不能减到0，如果能即可，不能就不能。

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
int n,q;
int bucket[32];
int powarr[32];
int checkpower(int num){
    if(num==1)return 0;
    int cnter=0;
    while(num!=1){
        num/=2;
        cnter++;
    }
    return cnter;
}
void program_init(){
    powarr[0]=1;
    for(int i=1;i<=30;i++){
        powarr[i]=powarr[i-1]*2;
    }
}
int main(){
    program_init();
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        int num;
        cin>>num;
        bucket[checkpower(num)]++;
    }
    for(int i=1;i<=q;i++){
        int num,cnter=0;
        cin>>num;
        for(int i=30;i>=0;i--){
            cnter+=min(num/powarr[i],bucket[i]);
            num-=min(num/powarr[i],bucket[i])*powarr[i];
        }
        if(num!=0)cout<<-1<<endl;
        else cout<<cnter<<endl;
    }
}

Codeforces 597B Restaurant 餐厅

发表评论

题目地址：http://codeforces.com/contest/597/problem/B
和洛谷P1803一模一样，之前写过的题解：https://renjikai.com/luogu-p1803/
耻辱啊，还要看原来的题解……

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
#include<iostream>
#include<algorithm>
using namespace std;
struct ss{
    int s,e;
    bool operator < (ss s2){
        if(e!=s2.e)return e<s2.e;
        else return s>s2.s;
    }
}sa[500005];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>sa[i].s>>sa[i].e;
    }
    sort(sa+1,sa+1+n);
    int cnter=0,t=0;
    for(int i=1;i<=n;i++){
        if(sa[i].s>t){
            cnter++;
            t=sa[i].e;
        }
    }
    cout<<cnter;
}

洛谷10月月赛R2·浴谷八连测R3 -Chtholly- Chtholly Nota Seniorious

发表评论

洛谷题号：3933
乱搞、二分答案+贪心，根本想不出来，打暴力30分……

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
int n, m;
int arr[2005][2005];
int arr_rotate[2005][2005];
int pos[2005];
int minnum = 2e9, maxnum = 0;
bool check(int value){
    int limit = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (arr[i][j] >minnum+value)limit = max(limit, j + 1);
        }
        for (int j = 1; j <= m; j++){
            if (maxnum - value > arr[i][j])if (j < limit)return false;
        }
    }
    return true;
}
/*check问题搞不懂可以仔细阅读T2题解
check的等效写法：
bool check(int value){
    int limit = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (arr[i][j] < maxnum - value)limit = max(limit, j + 1);
        }
        for (int j = 1; j <= m; j++){
            if (minnum + value < arr[i][j])if (j < limit)return false;
        }
    }
    return true;
}
*/
void rotate90degrees(){
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            arr_rotate[j][n-i+1] = arr[i][j];
        }
    }
    memcpy(arr, arr_rotate, sizeof(arr));
    swap(n, m);
}

int solve(){
    int low = 0, high = maxnum - minnum,mid;
    while (low < high){
        mid = (low + high) / 2;
        if (check(mid)){
            high= mid;
        }
        else{
            low = mid + 1;
        }
    }
    return low;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> arr[i][j];
            maxnum = max(maxnum,arr[i][j]);
            minnum = min(minnum,arr[i][j]);
        }
    }
    int re = 2e9;
    for (int i = 1; i <= 4; i++){
        re = min(re, solve());
        rotate90degrees();
    }
    cout << re;
    return 0;
}

洛谷 删数问题

发表评论
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<algorithm>
#include<string>
using namespace std;
int n;
string s;
int main(){
    ios::sync_with_stdio(false);
    cin >> s;
    cin >> n;
    for (int i = 0; i < s.length(); i++){
        if (s[i]>s[i + 1]&&n>0){
            s.erase(i, 1);
            n--;
            i=-1;//注意这里不是i--;因为有可能不符合顺序的数字出现在前面，需要重新返回头去找！
        }
        if (n == 0)break;
    }
    while (n--){
        s.erase(s.length() - 1, 1);
    }
    while (s[0] == '0')s.erase(s.begin());
    if(!s.empty())cout << s;
    else cout << "0";
}

洛谷 凌乱的yyy

发表评论

题号：1803
首先贴一种我一开始的错误做法。

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
#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct s{
    int start;
    int end;
    bool operator < (s & s1){
        if (end != s1.end)return end < s1.end;
        else return start < s1.start;
    }
}arr[1000005];
bool occupied[1000005];
int cnt;
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> arr[i].start >> arr[i].end;
    sort(arr + 1, arr + n + 1);
    for (int i = 1; i <= n; i++){
        if (!occupied[arr[i].start]){
            for (int j = arr[i].start; j < arr[i].end; j++){
                occupied[j] = true;
            }
            cnt++;
        }
    }
    cout << cnt;
}

这里的21行条件判断是错的。为什么呢？仅判断比赛开头有空闲是不能保证后面的时间有空闲的。那么我写一个正确的代码：

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
#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct s{
    int start;
    int end;
    bool operator < (s & s1){
        if (end != s1.end)return end < s1.end;
        else return start > s1.start;
    }
}arr[1000005];
int cnt;
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> arr[i].start >> arr[i].end;
    sort(arr + 1, arr + n + 1);
    int t = 0;
    for (int i = 1; i <= n; i++){
        if (t<=arr[i].start){
            cnt++;
            t = arr[i].end;
        }
    }
    cout << cnt;
}

这次的21行与之前的上一个比赛结束时间进行比较，如果在结束时间后面才能开始这个比赛。
注意：数组是排过序的，以结束时间、开始时间分别升序排序。