[L1-009]N个数求和 | PAT GPLT团体程序设计天梯赛

Description

本题的要求很简单,就是求N个数字的和。麻烦的是,这些数字是以有理数“分子/分母”的形式给出的,你输出的和也必须是有理数的形式。

Input

输入第一行给出一个正整数N(<=100)。随后一行按格式“a1/b1 a2/b2 …”给出N个有理数。题目保证所有分子和分母都在长整型范围内。另外,负数的符号一定出现在分子前面。

Output

输出上述数字和的最简形式 —— 即将结果写成“整数部分 分数部分”,其中分数部分写成“分子/分母”,要求分子小于分母,且它们没有公因子。如果结果的整数部分为0,则只输出分数部分。

Sample Input 1

5
2/5 4/15 1/30 -2/60 8/3

Sample Output 1

3 1/3

Sample Input 2

2
4/3 2/3

Sample Output 2

2

Sample Input 3

3
1/3 -1/6 1/8

Sample Output 3

7/24

Hint

利用 LCM 进行计算。

题解

#include "cstdio"
#include "iostream"
#include "cmath"
using namespace std;
int n;
long long num[100][2];
inline long long gcd(long long a, long long b)
{
    if (b == 0) return a;
    return gcd(b, a % b);
}
inline long long lcm(long long a, long long b)
{
    return a*b/gcd(a, b);
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%lld/%lld", &num[i][0], &num[i][1]);
    for (int i = 0; i < n-1; i++)
    {
        long long t_lcm = lcm(num[i][1], num[i+1][1]);
        num[i+1][0] = num[i+1][0] * (t_lcm/num[i+1][1]) + num[i][0] * (t_lcm/num[i][1]);
        num[i+1][1] = t_lcm;
    }
    long long t_gcd = gcd(num[n-1][0], num[n-1][1]);
    while (t_gcd != 1)
    {
        num[n-1][0] /= t_gcd;
        num[n-1][1] /= t_gcd;
        t_gcd = gcd(num[n-1][0], num[n-1][1]);
    }
    bool chk = 1;
    if (num[n-1][0] % num[n-1][1] == 0)
        printf("%lld", num[n-1][0]/num[n-1][1]);
    else
    {
        if (num[n-1][0]/num[n-1][1] != 0)
            printf("%lld", num[n-1][0]/num[n-1][1]), chk = 0;
        num[n-1][0] %= num[n-1][1];
        if (num[n-1][0] != 0)
        {
            while (t_gcd != 1)
            {
                num[n-1][0] /= t_gcd;
                num[n-1][1] /= t_gcd;
                t_gcd = gcd(num[n-1][0], num[n-1][1]);
            }
            printf(chk ? "%lld/%lld": " %lld/%lld", num[n-1][0], num[n-1][1]);
        }
    }
    return 0;
}

北京工业大学程序设计竞赛集训队一群有梦想的年轻人希望能在萌新的带领下走向人生巅峰

地址

OpenJudge – BJUT ACM(已结束)

体会

这是我自高一OI退役以后所参加的第一场算法竞赛。题目总共八道,送分的水题占了一半,考验选手能力的题目只有 C(单向链表的去重函数补写)、D(最大子段和)、E(平衡游戏,欧拉回路问题,HDU5882)、G(邻接表问题)。不过相较于 NOIP 复赛和省选而言,这几道题目的难度是远远没有达到的,不仅没有对多种算法、数据结构与数论的要求,也没有削弱题目结构的特点以模糊解题方向。

很惭愧,告别算法竞赛这么久,几乎完全忘记了之前所学的内容,以至于只完成了水题和平衡游戏。在 C 题的算法实现过程中,由于没有充分考虑到连续的重复元素输入,导致了去重不充分的情况出现。同时由于在 for 循环中大量使用break;以致于破坏了内存结构,并且没有在删除节点后进行 free 操作,导致了内存分配不合理。在 D 题的算法实现过程中,没有仔细读题而误解了命题人的用意,错误的将区间由硬币输入序理解为硬币价格序。对于 G 题,没有彻悟题意并简化模型,而是采用的暴力的方式,最终收获了 TLE、CE。

赛后经过与 licw 的讨论,终于明白了此题的神秘。根据题面,“定义:如果一个队伍里面,可以找到三个人,这三个人任意两两相互认识,或者任意两两相互不认识,那么这个队伍是缺乏创新力的;否则,这个队伍是富于创新力的。”假设我们现在有用户{a,b,c,...},那么对于用户a来说,剩下的人可以被分成“与A相识”和“与A不识”两个部分。由于鸽巢定理,我们易知,当n >= 6时,人群中至少存在三人且三个人任意两两相互认识或者任意两两相互不识。即对于任意n >= 6的情况,都是
Uncreative 的。所以我们只需要对n <= 6的情况进行判断即可。

在不可信网络下基于iodine建立DNS隧道

场景

不受信任的公共网络(如安装了审计设备的内网)、开启了WEB Portal认证的网络(如CMCC、ChinaNet)等。
注意:Win下直接使用iodine需要安装OpenVPN并且可能存在兼容性问题,建议通过虚拟机连接服务器然后开启端口转发。此外,网络速率与质量不会很高,延迟也会达到上百或数百毫秒。

原理

通过iodine将数据包封装为DNS请求,直接传输或通过DNS递归传输给自建的服务器再传送至互联网。当然,这个隧道只是联通了客户机与服务器,如果需要连接互联网,我们需要将本机通过位于服务器上的SS或SSH Tunnel等服务代理出去。

步骤

  • 获取iodine服务端与客户端,拥有一个公网IP地址的VPS服务器及域名。
  • 建立一个NS记录,如a.example.com值为b.example.com.
  • 建立一个A记录b.example.com,值为SERVER_IP
  • 服务端:执行iodined -f a.example.com,设置一个连接密码。
  • 客户端:执行iodine a.example.com,输入连接密码。
  • 完成连接,通过ipconfig(win)或ifconfig(Xnix)等命令即可看到一个名为dnsX的网络接口(X为连接序数,可以有多个DNS隧道在运行)。
  • 扩展

    iodine初步研究 – 小西的博客 | Xiaoxi’s Blog
    iodine README
    GitHub – yarrick/iodine: Official git repo for iodine dns tunnel

    None

    如果神明让我选择,
    我希望能“预知未来”
    还是“记住过去”?
    我选择后者。

    人类因为看不到未来,
    所以以为未来有无限可能性;
    因为能记住过去,
    所以会以回忆为食粮,
    让自己不断成长为一个更好的人。

    我们都是会出生、会死亡的凡人。
    我们用尽全力,
    也留不下那些注定要消逝的东西。
    但至少,
    我希望你所珍视过的东西,
    能以它最美好、最光彩夺目的姿态
    存在于你的记忆里。

    最后我要说,
    是我过去遇到的人们
    成就了今天的我。
    谢谢你们。

    ——Ocrine

    Status

    掠过两人之间的风
    捎来不知来处的寂寞
    哭泣过后眺望的天空
    有种格外的通透
    对温柔、笑容以及梦想的讲述方式都一无所知
    我只是跟随着你 做你的影子

    只要一点点时间就好
    再给我一点点时间就好
    真的只要一点点就好
    只要一点点时间就好
    再给我一点点时间就好

    我们是时间旅行者
    追逐时光的攀缘者
    厌倦了与时间的躲猫猫
    逃避时间的流逝
    喜极而泣 抑或是含泪欢笑
    都是因为你听从了内心的声音啊

    想要实现的梦想到今天就满100个了
    拿出一个来跟未来某天做交换吧
    平日里不曾交谈过的人
    今天放学后却对我说“明天见”
    偶尔有这种小惊喜也不错

    只要一点点时间就好
    再给我一点点时间就好
    真的只要一点点就好
    只要一点点时间就好
    再给我一点点时间就好

    我们是时间旅行者
    你的故事早已熟稔于心
    在比我记得我的名字 还要久远的以前
    你所不存在的那个世界 一定也存在着什么意义
    但是你所不存在的那个世界 就像没有暑假的八月
    你所不存在的那个世界 就像没有笑容的圣诞老爷爷
    你所不存在的那个世界啊

    我们是时间旅行者
    追逐时光的攀缘者
    厌倦了与时间的躲猫猫
    逃避时间的流逝
    别来无恙
    我这里一切都好

    我们是时间旅行者
    追逐时光的攀缘者
    厌倦了与时间的躲猫猫、逃避时间的流逝
    你真是个爱哭鬼啊
    我试图去阻止那眼泪落下
    但是你拒绝了我

    用那不断落下的泪滴
    喜极而泣 抑或是含泪欢笑
    都是因为我听从我内心的声音啊。
    ——《なんでもないや (movie ver.)》