whuacm - oak - warmupII - Felix021

uva - 2191 - Potentiometers

POJ

Mar 8

whuacm - oak - warmupII

felix021 @ 2009-3-8 23:56 [IT » 程序设计] 评论(2) , 引用(0) , 阅读(5786) | Via 本站原创

大 | 中 | 小

今天下午在实验室一个人做的。
一共写了5题，3AC，1WA，1没交。

A, Problem 1398 - Stock Exchange
最长递增自序列。因为是n <= 100000的数据量，所以显然N^2的程序是不行的，
google到了一个Nlog(N)的程序，基本上看懂了，自己写了一遍，AC，顺便贴在后面吧。

B, Problem 1399 - Sky Code
不会，嗯。完全没思路。我讨厌纯数学题=.=

C, Problem 1400 - Perfect Election
暴力写了个，没过样例，于是没交。
——2SAT问题，合取，析取，范式，DFS，强联通分量。晚上跑步的时候feli说的。不很懂，详见Baidu Or Google

D, Problem 1401 - Lucky Cities
没看，貌似图论，想必是不会。

E, Problem 1402 - Build Your Home
顺序(顺时针或者逆时针)给出多边形(不一定是凸多边形)的顶点，求面积。
用三角形的方法写了一个，WA了。后来张文说他用的梯形写的，AC了，于是改了一下，我也AC了。
看来还是要注意，sqrt尽量少用，嗯。代码也贴后面吧。

F, Problem 1403 - Quick Answer
并查集，看起来不难阿，代码也写得蛮快，就TMD的总是wa，我郁闷。回头学习下别人的代码吧。。WA的代码就不贴了
＠2009-03-09 AC了，我的思路是基本上是正确的，有2个小错
  a. 输入有点小问题；因为题目的输入数据有一些trailing space，囧。
  b. q x y，当x==y的时候输出的是NO。
  代码也附在后面吧，我不会标准的并查集写法，这是按自己的想法写的。

G, 没看。

H, Problem 1406 - Internet Service Providers
纯数学题，蛮简单，代码贴后面，不写什么了。

I,  Problem 1405 - GCD Determinant
没做，看群里的说法，也是纯数学题=.= 貌似是把欧拉函数乘起来就好了，不要算行列式，嗯。

//Problem 1398
#include<iostream>
#include<algorithm>
using namespace std;

int n = 0, d[10240];

/* N ^ 2 */
int f[10240];
void solve1(){
        fill(f, f + n, 1);
        int maxv = 0;
        for (int i = 1; i < n; ++i){
            for (int j = 0; j < i; ++j){
                if(d[j] < d[i] && f[j] > f[i] - 1){
                    f[i] = f[j] + 1;
                }
            }
            if(f[i] > maxv) maxv = f[i];
        }
        printf("%d\n", maxv);
}

/* N * log(N) */
int b[10240];
void solve2(){
    int len = 1;
    int l, r, m, i;
    b[0] = -1;
    b[1] = d[0];
    for (i = 1; i < n; ++i){
        l = 0; r = len;
        while (l <= r){
            m = (l + r) / 2;
            if(b[m] < d[i]){
                l = m + 1;
            }else{
                r = m - 1;
            }
        }
        b[l] = d[i];
        if (l > len) len++;
    }
    printf("%d\n", len);
}

int main(){
    while (scanf("%d", &n) != EOF && n != 0){
        for(int i = 0; i < n; ++i) scanf("%d", d+i);
        // solve1();
        solve2();
    }
    return 0;
}

//1402_triangel_wa.cpp
#include<iostream>
#include<cmath>
#define EPS (1e-12)
using namespace std;

struct coord{
    double x, y;
} v[1000010], O = {0.0, 0.0};

int cmp(const double &a, const double &b){
    if(fabs(a - b) < EPS) return 0;
    else if (a < b) return -1;
    else return 1;
}

double dist(coord a, coord b){
    return sqrt((a.x - b.x) * (a.x - b.x)
               +(a.y - b.y) * (a.y - b.y));
}

double eval(int a, int b){
    double ca, cb, A, B, C, S, p;
    A = dist(v[a], O);
    B = dist(v[b], O);
    C = dist(v[a], v[b]);
    p = (A + B + C) / 2;
    S = sqrt(p * (p - A) * (p - B) * (p - C));
    ca = atan2(v[a].y, v[a].x);
    cb = atan2(v[b].y, v[b].x);
    if(cmp(ca, cb) <= 0) return S;
    else return -S;
}

int main(){
    int i, n;
    double ans;
    while (scanf("%d", &n), n != 0){
        for (i = 0; i < n; ++i){
            scanf("%lf%lf", &v[i].x, &v[i].y);
        }
        if (n <= 2){
            printf("0\n");
            continue;
        }
        ans = 0.0;
        for(i = 0; i < n; ++i){
            double t = eval(i, (i + 1) % n);
            ans += t;
        }
        ans = fabs(ans);
        if((ans - (int)ans) - 0.5 > EPS){
            printf("%d\n", (int)ans + 1);
        }else{
            printf("%d\n", (int)ans);
        }
    }
    return 0;
}

//1402_梯形_ac.cpp
#include<iostream>
#include<cmath>
#define EPS (1e-12)
using namespace std;

struct coord{
    double x, y;
} v[1000010], O = {0.0, 0.0};

double eval(int a, int b){
    return (v[a].y + v[b].y) * (v[a].x - v[b].x) / 2;
}

int main(){
    int i, n;
    double ans;
    while (scanf("%d", &n), n != 0){
        for (i = 0; i < n; ++i){
            scanf("%lf%lf", &v[i].x, &v[i].y);
        }
        if (n <= 2){
            printf("0\n");
            continue;
        }
        ans = 0.0;
        for(i = 0; i < n; ++i){
            double t = eval(i, (i + 1) % n);
            ans += t;
        }
        ans = fabs(ans);
        if((ans - (int)ans) - 0.5 > EPS){
            printf("%d\n", (int)ans + 1);
        }else{
            printf("%d\n", (int)ans);
        }
    }
    return 0;
}

//1403 Quick Answer
#include<iostream>
#include<algorithm>
using namespace std;

int t[10010], n, N1, N2, maxs;

void myflush(){
    char t;
    while(t = getchar(), t != '\n' && t != '\t' && t != EOF);
}

void connect(){
    int a, b;
    scanf("%d%d", &a, &b);
    if(t[a] == -1 && t[b] == -1){
        maxs++;
        t[a] = t[b] = maxs;
    }else if(t[a] == -1 && t[b] != -1){
        t[a] = t[b];
    }else if(t[a] != -1 && t[b] == -1){
        t[b] = t[a];
    }else /* t[a] != -1 && t[b] != -1 */{
        int tmp = t[b];
        for(int i = 1; i <= n; ++i){
            if(t[i] == tmp) t[i] = t[a];
        }
    }
}

void query(){
    int a, b;
    scanf("%d%d", &a, &b);
    if(a == b || (t[a] == t[b] && t[a] != -1)){
        N1++;
    }else{
        N2++;
    }
}

void del(){
    int a;
    scanf("%d", &a);
    if(t[a] == -1) return;
    t[a] = -1;
}

int main(){
    char c;
    while (scanf("%d", &n) != EOF){
        myflush();
        fill(t, t + n + 5, -1);
        N1 = 0, N2 = 0, maxs = 0;
        while(true){
            c = getchar();
            switch(c){
                case 'c':
                    connect();break;
                case 'q':
                    query();break;
                case 'd':
                    del();break;
            }
            myflush();
            if(c == 'e') break;
        }
        printf("%d , %d\n", N1, N2);
    }
    return 0;
}

//H  Problem 1406 - Internet Service Providers
#include<stdio.h>

int main(){
    long long c, n, t1, t2, p1, p2;
    while(scanf("%lld%lld", &n, &c) != EOF){
        if(n == 0){
            printf("0\n");
            continue;
        }
        if(c % (2 * n) == 0){
            printf("%lld\n", c / (2 * n));
        }else{
            t1 = c / (2 * n);
            t2 = c / (2 * n) + 1;
            p1 = -n * t1 * t1 + c * t1;
            p2 = -n * t2 * t2 + c * t2;
            if (p1 >= p2){
                printf("%lld\n", t1);
            }else{
                printf("%lld\n", t2);
            }
        }
    }
    return 0;
}

欢迎扫码关注：