大白刷题录

 发表于 March 12, 2015  |  5 分钟  |  886 个字  |  svtter

UVa 11729

#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
struct Ant
{
    int id; int p; int d;
    bool operator < (const Ant& a) const {
        return p < a.p;
    }
};
const int MAXN = 10010;
const char dirName[][10] = {"L", "Turning", "R"};
Ant before[MAXN], after[MAXN];
int order[MAXN];
int main(int argc, const char *argv[])
{
    freopen("input", "r", stdin);
    int t;
    int L, T, n;
    int p, d;
    char c;
    scanf("%d", &t);
    for(int kase = 1; kase <= t; kase++)
    {
        printf("Case #%d:\n", kase);
        scanf("%d%d%d", &L, &T, &n);
        for(int i = ; i < n; i++)
        {
            scanf("%d %c", &p, &c);
            d = c == 'L' ? -1 : 1;
            before[i] = (Ant) {i, p, d};
            after[i] = (Ant) {, p+T*d, d};
        }
        sort(before, before+n);
        for(int i =  ;i < n;i ++)
            order[before[i].id] = i;
        sort(after, after+n);
        for(int i = ; i < n; i++)
            if(after[i].p == after[i+1].p) after[i].d = after[i+1].d = ;
        for(int i = ; i <n; i++)
        {
            int a = order[i];
            if(after[a].p <  || after[a].p > L) puts("Fell off");
            else printf("%d %s\n", after[a].p, dirName[after[a].d+1]);
        }
        printf("\n");
    }
    return ;
}
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
struct Ant
{
    int id; int p; int d;
    bool operator < (const Ant& a) const {
        return p < a.p;
    }
};
const int MAXN = 10010;
const char dirName[][10] = {"L", "Turning", "R"};
Ant before[MAXN], after[MAXN];
int order[MAXN];
int main(int argc, const char *argv[])
{
    freopen("input", "r", stdin);
    int t;
    int L, T, n;
    int p, d;
    char c;
    scanf("%d", &t);
    for(int kase = 1; kase <= t; kase++)
    {
        printf("Case #%d:\n", kase);
        scanf("%d%d%d", &L, &T, &n);
        for(int i = ; i < n; i++)
        {
            scanf("%d %c", &p, &c);
            d = c == 'L' ? -1 : 1;
            before[i] = (Ant) {i, p, d};
            after[i] = (Ant) {, p+T*d, d};
        }
        sort(before, before+n);
        for(int i =  ;i < n;i ++)
            order[before[i].id] = i;
        sort(after, after+n);
        for(int i = ; i < n; i++)
            if(after[i].p == after[i+1].p) after[i].d = after[i+1].d = ;
        for(int i = ; i <n; i++)
        {
            int a = order[i];
            if(after[a].p <  || after[a].p > L) puts("Fell off");
            else printf("%d %s\n", after[a].p, dirName[after[a].d+1]);
        }
        printf("\n");
    }
    return ;
}

UVa 11292 勇士斗恶龙

排序，贪心

#include <stdio.h>
#include <algorithm>
using namespace std;
int main()
{
    // freopen("input", "r", stdin);
    const int MAXN = 20010;
    int dra[MAXN];
    int sol[MAXN];
    int m, n;
    while(scanf("%d%d", &n, &m))
    {
        if(n == m && n == ) break;
        for(int i = ; i < n; i++) scanf("%d", &dra[i]);
        for(int i = ; i < m; i++) scanf("%d", &sol[i]);
        sort(dra, dra+n); sort(sol, sol+m);
        int i, j, cost;
        i = j = cost = ;
        for(;;)
        {
            if(i == n || j == m)
                break;
            if(dra[i] > sol[j]) j++;
            else
            {
                cost += sol[j];
                i++; j++;
            }
        }
        if(i == n) printf("%d\n",  cost);
        else puts("Loowater is doomed!");
    }
    return ;
}

UVa 11300

这个题目很有价值。

一方面通过数学推导得出结论。

编号为i的人初始有$A_i$枚金币。对于1号，给了4号$x_1$枚金币，自己还有$A_1-x_1$枚。然后从2号拿走$x_2$枚金币，现在有$A_1-x_1+x_2$枚金币，另外，设平均金币值为$A_1-x_1+x_2=M$。

由此可类推得到

$A_n-x_n+x_1 \Rightarrow x_n=M-A_n+x_1=x_n-C_n$

我们可以得到类推公式

$$C_i = C_{i-1} + A_i – M $$

证明:

$$x_2 = x_1 – C_1$$

$$x_3 = M-A_2+x_2 =2M-A_1-A_2+x_1=x_1-C_2$$\

以此类推。

可以求得，需要求的结果为:

$$|x_1|+|x_1-C_1|+|x_1-C_2|….|x_1-C_n-1|$$

即求这个式子值最小，即求$C_1, C_2, …C_n$的中位数。

#include <stdio.h>
#include <algorithm>
#include <math.h>
#define lln long long
using namespace std;
const int MAXN = 1000000 + 10;
lln gold[MAXN], C[MAXN];
int main()
{
    // freopen("input", "r", stdin);
    lln n, sum, per, cnt;
    while(~scanf("%lld", &n))
    {
        sum = ;
        for(int i = ; i < n; i++)
        {
            scanf("%lld", &gold[i]);
            sum += gold[i];
        }
        per = sum / n;
        C[] = ;
        for(int i = ; i < n; i++) C[i] = C[i-1] + gold[i] - per;
        sort(C, C+n);
        cnt = ;
        lln x1 = C[n/2];
        for(int i = ; i < n; i++)
            cnt += abs(x1 - C[i]);
        printf("%lld\n", cnt);
    }
    return ;
}

LA 3708

这个题目也是比较有水平

使用了按比例缩小的技巧。其中，按逆时针编号，固定一个点作为原点，建立新坐标。原来的位置呈现在新坐标的位置为$pos = i/n*(n+m)$，如此，求移动距离则是$fabs(pos – floor(pos+0.5))/(n+m)$

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
    // freopen("input", "r", stdin);
    int n, m;
    double pos, ans;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        ans = ;
        for(int i = 1; i < n; i++)
        {
            pos = (double)i / n * (n+m);
            ans += fabs(pos - floor(pos+0.5))/(n+m);
        }
        printf("%.4lf\n", ans*10000);
    }
    return ;
}

UVa 10881

蓝桥杯去年山东省的初赛题目，的确有点意思= =

转换方向可以不必在意，因为最终看到的结果已经不知道最初的蚂蚁是哪一只了，所以不用纠结方向的问题。主要要考虑的是最终的位置，以及最初蚂蚁位置的存储，before，after的对应关系。

#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
struct Ant
{
    int id; int p; int d;
    bool operator < (const Ant& a) const {
        return p < a.p;
    }
};
const int MAXN = 10010;
const char dirName[][10] = {"L", "Turning", "R"};
Ant before[MAXN], after[MAXN];
int order[MAXN];
int main(int argc, const char *argv[])
{
    freopen("input", "r", stdin);
    int t;
    int L, T, n;
    int p, d;
    char c;
    scanf("%d", &t);
    for(int kase = 1; kase <= t; kase++)
    {
        printf("Case #%d:\n", kase);
        scanf("%d%d%d", &L, &T, &n);
        for(int i = ; i < n; i++)
        {
            scanf("%d %c", &p, &c);
            d = c == 'L' ? -1 : 1;
            before[i] = (Ant) {i, p, d};
            after[i] = (Ant) {, p+T*d, d};
        }
        sort(before, before+n);
        for(int i =  ;i < n;i ++)
            order[before[i].id] = i;
        sort(after, after+n);
        for(int i = ; i < n; i++)
            if(after[i].p == after[i+1].p) after[i].d = after[i+1].d = ;
        for(int i = ; i <n; i++)
        {
            int a = order[i];
            if(after[a].p <  || after[a].p > L) puts("Fell off");
            else printf("%d %s\n", after[a].p, dirName[after[a].d+1]);
        }
        printf("\n");
    }
    return ;
}