ACM-ICPC Asia Regional Changchun 2015

A - Too Rich

HDU - 5527

题意：现在有需要的金额p，每种面值所拥有的数量c_1, c_5, c_{10}, c_{20}, c_{50}, c_{100}, c_{200}, c_{500}, c_{1000}, c_{2000}。现在要用尽可能多的纸币来组成p。
思路：贪心 + DFS
比赛后期读了一下题还以为是类似于多重背包什么的…
现在要用尽可能多的纸币来组成p，一开始正着暴搜搜T了…
这里其实应该反过来想，理解为：用尽量少的纸币凑成sum - p ( sum是所有纸币的面额之和 )，用纸币总数num - ans就是答案。而这部分用尽量少的纸币凑sum-p就是很普通的贪心，尽量先选面额大的，用DFS搜索即可，但是这里应该注意一个问题是：题目给出的这些面额1,20,50,100,200,500,1000,2000里，除了<20,50>和<200,500>这两个关系以外，每个面值都是比它大的所有面值的因子，也就是说，要选尽量少的纸币，那么面值大的能拿就拿走，否则还要用小面值的来凑它，比如能拿50就拿50，否则以后还要拿5个10凑成50。而对于那两个特殊的关系，20不是50的因子，200不是500的因子，但是20却是50+50的因子，200却是500+500的因子，那么就会出现奇偶性质的讨论，这意味着拿50和500的时候，还要考虑拿少一张的情况，给20或200的纸币留空间，否则将会漏掉情况，如20,20,20,50凑60块，20,20,20,50,50凑110块等 ，都需要这样多搜一层来处理。DFS的时候同时记录用最多和少用一个的情况往下递归，这样就避免了奇偶性造成的错误。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 15;
int tp[maxn] = {1,5,10,20,50,100,200,500,1000,2000};
int cost[maxn];
int ans, p;

void dfs(int now, int num, int remain) {
    if(remain == 0) {
        //cout << "in" << endl;
        ans = min(ans, num);
        return;
    }
    if(remain < 0 || now < 0)
       return;
    int cnt = min(remain/tp[now], cost[now]);
    //cout << cnt << endl;
    dfs(now - 1, num + cnt, remain - cnt*tp[now]);
    if(cnt >= 1) {
        cnt -= 1;
        dfs(now - 1, num + cnt, remain - cnt*tp[now]);
    }
    return;
}

int main() {
    int T, _num, sum, num;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &p);
        sum = 0, ans = INF, num = 0;
        for(int i = 0; i < 10; ++i) {
            scanf("%d", &_num);
            cost[i] = _num;
            num += _num;
            sum += _num * tp[i];
        }
        if(sum < p) {
            printf("-1\n");
            continue;
        }
        dfs(9, 0, sum-p);
        if(ans == INF)
            printf("-1\n");
        else
            printf("%d\n", num - ans);
    }
    return 0;
}

B - Count a * b

HDU - 5528
积性函数 推导

C - Play a game

HDU - 5529

D - Pipes selection

HDU - 5530

E - Rebuild

HDU - 5531

题意：按顺序给出一些点，并将相邻（1和2，2和3，……，n和1）的两点连线，现在对于每两个相邻点组成的线段，都要以点为圆心，构造出两个相切的圆。对于给出的所有点，若能构造出来，输出所有圆的面积之和，并按输入顺序输出这些圆的半径；若无法构造出来，则输出IMPOSSIBLE
思路：三分查找

二分：适用于单调函数（不一定严格单调）中逼近求解某点的值
三分：凹性函数或凸性函数求凹/凸点

三分查找

如图所示，已知左右端点L、R，要求找到凸点的位置。
思路：通过不断缩小 [L,R] 的范围，无限逼近凸点。
做法：先取 [L,R] 的中点 mid，再取 [mid,R] 的中点 mmid，通过比较 f(mid) 与 f(mmid) 的大小来缩小范围。
当最后 L = R-1 时，再比较下这两个点的值，我们就找到了答案。
1. 当 f(mid) > f(mmid) 的时候，我们可以断定 mmid 一定在凸点的右边。
反证法：假设 mmid 在凸点的左边，则 mid 也一定在凸点的左边，又由 f(mid) > f(mmid) 可推出 mmid < mid，与已知矛盾，故假设不成立。
所以，此时可以将 R = mmid 来缩小范围。
2. 当 f(mid) < f(mmid) 的时候，我们可以断定 mid 一定在凸点的左边。
反证法：假设 mid 在凸点的右边，则 mmid 也一定在凸点的右边，又由 f(mid) < f(mmid) 可推出 mid > mmid，与已知矛盾，故假设不成立。
同理，此时可以将 L = mid 来缩小范围。

int SanFen(int l, int r) {
   while(l < r-1) {
       int mid  = (l+r)/2;  //与二分法类似，先取整个区间的中间值mid
       int mmid = (mid+r)/2; //再取右侧区间的中间值mmid，从而把区间分为三个小区间
       if( f(mid) > f(mmid) ) //若mid比mmid更靠近最值，舍弃右区间
           r = mmid;
       else  //否则舍弃左区间
           l = mid;
   }
   return f(l) > f(r) ? l : r;
}

另一种三分写法

const double eps = 1e-10; 
double Ternary_Search(double low, double up) {
   double m1,m2;
   while(up - low >= eps) {
       m1 = low + (up - low) / 3;
       m2 = up - (up - low) / 3;
       if(f(m1) <= f(m2))
           low = m1;
       else
           up = m2;
   }
   return (m1+m2)/2;
}

当构成的多边形边数为奇数时，可列下式：
d{_1} = r{_1} + r{_2}
d{_2} = r{_2} + r{_3}
d{_3} = r{_3} + r{_4}
……
d{_n} = r{_n} + r{_1}
可得：r{_1} = \frac{d{_1} - d{_2} + d{_3} - d{_4} + … - d_{n-1} + d{_n}}{2}
这样可以直接算得r1，再由r{_2} = d{_1} - r{_1} , r{_3} = d{_2} - r{_2} , … , r{_n} = d_{n-1} - r_{n-1} 得到其它的半径，注意，若其中有半径 < 0， 可以直接判断为IMPOSSIBLE

当构成的多边形边数为偶数时：
上述式子恰好能把两边的r_{1}消掉，但是依旧可以得到一个等式d_{1} - d_{2} + d_{3} - d_{4} + … + d_{n-1} - d_{n} = 0
首先我们可以判断这个式子是否成立，若不成立则直接判断为IMPOSSIBLE。
由于我们最后要求的面积是一个凹性函数\pi r^2，故我们可以用三分法 去查找，第一步是要确定三分的左右边界left和right，通过推导我们可以列出如下式子：
r{_1} \geq 0
r{_2} = d{_1} - r{_1} \geq 0 \to r{_1} \leq d{_1}
r{_3} = d{_2} - r{_2} = d{_2} - d{_1} + r{_1} \geq 0 \to r{_1} \geq d_{2} - d_{1}
r{_4} = d{_3} - r{_3} = d{_3} - d{_2} + d{_1} - r{_1} \geq 0 \to r{_1} \leq d{_3} - d{_2} + d{_1}
……
通过这样的计算来不断约束左右边界left、right
然后做三分查找即可
注意 - #define eps 1e-8 PI = acos(-1.0)

AC代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
const int INF = 0x3f3f3f3f;
#define PI acos(-1.0)
#define eps 1e-8
using namespace std;
const int maxn = 1e4+5;
struct point {
    double x, y;
}p[maxn];
double d[maxn], r[maxn];
int n;

double f_(double x) {
    r[0] = x;
    double area = r[0] * r[0];
    for(int i = 1; i < n; ++i) {
        r[i] = d[i-1] - r[i-1];
        area += r[i] * r[i];
    }
    return area;
}

double sanfen(double l, double r) {
    double mid, mmid;
    while(r - l > eps) {
        mid = (l+r)/2.0;
        mmid = (r+mid)/2.0;
        if(f_(mid) - f_(mmid) <= eps) {
            r = mmid;
        }
        else {
            l = mid;
        }
    }
    return (l+r)/2.0;
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 0; i < n; ++i) {
            scanf("%lf%lf", &p[i].x, &p[i].y);
            if(i > 0)
                d[i-1] = sqrt((p[i].x-p[i-1].x)*(p[i].x-p[i-1].x) + (p[i].y-p[i-1].y)*(p[i].y-p[i-1].y));
        }
        d[n-1] = sqrt((p[n-1].x-p[0].x)*(p[n-1].x-p[0].x) + (p[n-1].y-p[0].y)*(p[n-1].y-p[0].y));
        if(n&1) {
            double fz = 0;
            for(int i = 0; i < n; ++i) {
                //printf("%d -> %f\n", i, d[i]);
                if(i&1) fz -= d[i];
                else    fz += d[i];
            }
            double area = 0;
            r[0] = fz / 2.0;
            if(r[0] < 0) {
                puts("IMPOSSIBLE");
                continue;
            }
            area += r[0] * r[0];
            bool flag = true;
            for(int i = 1; i < n; ++i) {
                r[i] = d[i-1] - r[i-1];
                //printf("%f\n", r[i]);
                if(r[i] < 0) {
                    flag = false;
                    break;
                }
                area += r[i] * r[i];
            }
            if(!flag) {
                puts("IMPOSSIBLE");
                continue;
            }
            printf("%.2f\n", area*PI);
            for(int i = 0; i < n; ++i) {
                printf("%.2f\n", r[i]);
            }
        }
        else {
            double judge = 0;
            double left = 0, right = (double)INF;
            for(int i = 0; i < n; ++i) {
                //printf("**%.2f\n", d[i]);
                if(i&1) {
                    judge -= d[i];
                    left = max(left, judge);
                }
                else {
                    judge += d[i];
                    right = min(right, judge);
                }
            }
            //printf("** %.2f %.2f\n", left, right);
            //printf("** %.2f\n", judge);
            if(judge - 0 > eps || left - right > eps) {
                puts("IMPOSSIBLE");
                continue;
            }
            //cout << "in" << endl;
            r[0] = sanfen(left, right);
            //cout << "out" << endl;
            printf("%.2f\n", f_(r[0])*PI);
            for(int i = 0; i < n; ++i) {
                printf("%.2f\n", r[i]);
            }
        }
    }
    return 0;
}

F - Almost Sorted Array

HDU - 5532

题意：给出一个序列，判断删除一个数字，能否构成不上升或者不下降的序列
思路：LIS
AC代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
const int maxn = 1e5 + 10;

int a[maxn], n;

bool solve() {
    int pos[2] = {-1, -1};
    for(int i = 1; i < n; i++) {
        if(a[i] < a[i - 1]) {
            pos[0] = i - 1;
            pos[1] = I;
            break;
        }
    }
    if(pos[0] == -1)
        return true;

    int prev = 0, cnt = 0;
    for(int i = 0; i < n; i++) {
        if(pos[0] != i) {
            if(prev == 0)
                prev = a[i];
            else {
                if(a[i] < prev) {
                    cnt++;
                    break;
                }
                else
                    prev = a[i];
            }
        }
    }
    prev = 0;
    for(int i = 0; i < n; i++) {
        if(pos[1] != i) {
            if(prev == 0)
                prev = a[i];
            else {
                if(a[i] < prev) {
                    cnt++;
                    break;
                }
                else
                    prev = a[i];
            }
        }
    }
    if(cnt < 2)
        return true;
    else
        return false;
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 0; i < n; I++)
            scanf("%d", &a[I]);
        if(solve())
            printf("YES\n");
        else {
            for(int i = 0; i < n / 2; I++)
                swap(a[i], a[n - i - 1]);
            if(solve())
                printf("YES\n");
            else
                printf("NO\n");
        }
    }
    return 0;
}

G - Dancing Stars on Me

HDU - 5533

题意：给出n个坐标(x,y)（x,y是正整数），问由这些点构成的图形是否是正n边形。
思路：由于坐标都是正整数，故只有正方形有可能构成。计算四个边长是否相等且对角线相等即可。
AC代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <map>
using namespace std;
const int maxn = 5;
typedef long long ll;
struct point {
    int x, y;
}p[maxn];

int main() {
    int T, n;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 0; i < n; ++i) {
            scanf("%d%d", &p[i].x, &p[i].y);
        }
        if(n != 4) {
            printf("NO\n");
            continue;
        }
        map<int, int> mp;
        for(int i = 0; i < n; ++i) {
            for(int j = i+1; j < n; ++j) {
                int d = (p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y);
                ++mp[d];
            }
        }
        if(mp.size() == 2) {
            bool flag = true;
            map<int, int>::iterator it = mp.begin();
            for( ;it != mp.end(); ++it) {
                if(it->second != 2 && it->second != 4) {
                    flag = false;
                    break;
                }
            }
            if(flag) {
                printf("YES\n");
            }
            else {
                printf("NO\n");
            }
        }
        else {
            printf("NO\n");
        }
    }
    return 0;
}

H - Partial Tree

HDU - 5534

题意：给n个点，现在要构造出一棵树（n-1个点），现在给出度数为1、2、3、……、n-1的点权f(i)，现在要让这个树的点权之和尽量的大，并将其输出。
思路：完全背包

I - Chess Puzzle

HDU - 5535

J - Chip Factory

HDU - 5536

题意：给出一个数列，求\max_{i,j,k} (s_i+s_j) \oplus s_k
思路：直接暴
AC代码：

#include <iostream>
using namespace std;
const int MAX = 1e3 + 5;
int n, s[MAX];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--) {
        cin >> n;
        for(int i = 0; i < n; I++)
            cin >> s[i];
        int ans = 0;
        for(int i = 0; i < n; I++)
            for(int j = i + 1; j < n; j++)
                for(int k = 0; k < n; k++)
                    if(k != i && k != j)
                        ans = max(ans, ((s[i] + s[j]) ^ s[k]));

        cout << ans << endl;
    }
}

K - Maximum Spanning Forest

HDU - 5537

L - House Building

HDU - 5538
题意：给出一个n*m的格子，每个格子里的数字就是立方体的高度。求用多少瓷砖能把这些立方体都盖住。
思路：求表面积（不算底部）。
AC代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>

using namespace std;
const int maxn = 55;
int a[maxn][maxn];
int turn[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int main() {
    int T;
    int n, m;
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        memset(a, 0, sizeof a);
        int ans = 0;
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= m; ++j) {
                scanf("%d", &a[i][j]);
                if(a[i][j]) ++ans;
            }
        }
        int ii, jj;
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= m; ++j) {
                for(int k = 0; k < 4; ++k) {
                    ii = i + turn[k][0];
                    jj = j + turn[k][1];
                    if(a[i][j] > a[ii][jj]) {
                        ans += a[i][j] - a[ii][jj];
                    }
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

M - Security Corporation

HDU - 5539

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 218,284评论 6赞 506
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 93,115评论 3赞 395
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 164,614评论 0赞 354
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,671评论 1赞 293
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,699评论 6赞 392
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,562评论 1赞 305
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,309评论 3赞 418
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,223评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,668评论 1赞 314
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,859评论 3赞 336
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,981评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,705评论 5赞 347
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,310评论 3赞 330
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,904评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,023评论 1赞 270
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,146评论 3赞 370
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,933评论 2赞 355

推荐阅读更多精彩内容