白书-初出茅庐-初级篇

白书《挑战程序设计竞赛》第2版 准备篇+初级篇

题目链接 https://cn.vjudge.net/article/426

POJ 1852 Ants

思维：俩蚂蚁碰头后回头走，在这一问题里等效于不回头

//菜到窒息
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;



int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int l, n, val, tem_first, first = 0, mmin = 0x3f3f3f3f, mmax = -1;
        scanf("%d%d", &l, &n);
        for(int i = 0; i < n; ++i)
        {
            scanf("%d", &val);
            if(val > mmax)
                mmax = val;
            if(val < mmin)
                mmin = val;
            tem_first = min(val, l - val);
            if(tem_first > first)
                first = tem_first;
        }
        cout << first << ' ';
        cout << max(l - mmin, mmax) << '\n';
    }
    return 0;
}

POJ 2386 Lake Counting

DFS八个方位

//菜到窒息
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n, m;
string s[105];
int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};

void DFS(int x, int y)
{
    s[x][y] = '.';
    for(int i = 0; i < 8; ++i)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(xx < 0 || xx >= n || yy < 0 | yy >= m || s[xx][yy] == '.')
            continue;
        s[xx][yy] = '.';
        DFS(xx, yy);
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; ++i)
        cin >> s[i];
    int ans = 0;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            if(s[i][j] == 'W')
            {
                DFS(i, j);
                ans++;
            }
    cout << ans << '\n';
    return 0;
}

POJ 3617 Best Cow Line

贪心

//菜到窒息
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    char ch;
    cin >> n;
    getchar();
    string s, t, ss;
    for(int i = 0; i < n; ++i)
    {
        scanf("%c", &ch);
        getchar();
        s += ch;
    }
    for(int i = 0; i < n; ++i)
    {
        ///下标从0开始，放在前面是每80，放在后面是每81
        if(i % 80 == 0 && i != 0)
            cout << '\n';
        ss = s;
        reverse(ss.begin(), ss.end());
        if(s <= ss)
            putchar(s[0]), s.erase(s.begin());
        else
            putchar(ss[0]), s.erase(s.end() - 1);
    }
    cout << '\n' ;
    return 0;
}

POJ 3253 Fence Repair

贪心，好像跟简单的石子合并不是一回事儿

//菜到窒息
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

int main()
{
    vector<int> vec;
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
    {
        int tem;
        scanf("%d", &tem);
        ///vector据大小插入
        vec.insert(lower_bound(vec.begin(), vec.end(), tem), tem);
    }
    long long ans = 0;/// >= 2个int可能超int
    while(vec.size() > 1)
    {
        int t = vec[0] + vec[1];
        ans += t;
        vec.erase(vec.begin());
        vec.erase(vec.begin());
        vec.insert(lower_bound(vec.begin(), vec.end(), t), t);
    }
    cout << ans << '\n';
    return 0;
}

POJ 2431 Expedition

贪心 + 思维

转换一些基本的思路, 在到达加油站i时, 其实就可以认为获得了一次在i之后的任何时候都可以加油a[i].val的机会

//菜到窒息
#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

struct node
{
    int pos, val;
    bool vis;
} a[10005];

bool cmp(node a, node b)
{
    return a.pos < b.pos;
}

int main()
{
    int n, ans = 0, over, init;
    cin >> n;
    priority_queue<int, vector<int>, less<int> >q;
    for(int i = 0; i < n; ++i)
        scanf("%d%d", &a[i].pos, &a[i].val);
    scanf("%d%d", &over, &init);
    for(int i = 0; i < n; ++i)
        a[i].pos = over - a[i].pos;
    sort(a, a + n, cmp);
    bool flag = 1;
    while(init < over)
    {
        for(int i = 0; a[i].pos <= init; ++i)
        {
            if(a[i].vis)
                continue;
            else
                a[i].vis = 1, q.push(a[i].val);
        }
        if(q.size())
            init += q.top(), q.pop(), ans++;
        else
        {
            flag = 0;
            break;
        }
    }
    if(!flag)
        cout << "-1" << '\n';
    else
        cout << ans << '\n';
    return 0;
}