戰(zhàn)隊(duì)：Computer room white give (CRWG)

隊(duì)員：劉凱 董海錚 馬鴻儒

A: Birthday Cake

B: Bumped!

問題描述：
Peter returned from the recently held ACM ICPC World finals only to find that his return flight was overbooked and he was bumped from the flight! Well, at least he wasn’t beat up by the
airline and he’s received a voucher for one free flight between any two destinations he wishes.
He is already planning next year’s trip. He plans to travel by car where necessary, but he may be using his free flight ticket for one leg of the trip. He asked for your help in his planning.
He can provide you a network of cities connected by roads, the amount it costs to buy gas for traveling between pairs of cities, and a list of available flights between some of those cities. Help Peter by finding the minimum amount of money he needs to spend to get from his hometown to next year’s destination!
輸入
The input consists of a single test case. The first line lists five space-separated integers n, m, f, s, and t, denoting the number of cities n (0 < n ≤ 50 000), the number of roads m (0 ≤ m ≤ 150 000), the number of flights f (0 ≤ f ≤ 1 000), the number s (0 ≤ s < n) of the city in which Peter’s trip starts, and the number t (0 ≤ t < n) of the city Peter is trying to travel to. (Cities are numbered from 0 to n ? 1.)
The first line is followed by m lines, each describing one road. A road description contains three space-separated integers i, j, and c (0 ≤ i, j < n, i 6= j and 0 < c ≤ 50 000), indicating there is a road connecting cities i and j that costs c cents to travel. Roads can be used in either direction for the same cost. All road descriptions are unique.
Each of the following f lines contains a description of an available flight, which consists of two space-separated integers u and v (0 ≤ u, v < n, u 6= v) denoting that a flight from city u to city v is available (though not from v to u unless listed elsewhere). All flight descriptions are unique.
輸出
Output the minimum number of cents Peter needs to spend to get from his home town to the competition,using at most one ?ight. You may assume that there is a route on which Peter can reach his destination.
INPUT:
8 11 1 0 5
0 1 10
0 2 10
1 2 10
2 6 40
6 7 10
5 6 10
3 5 15
3 6 40
3 4 20
1 4 20
1 3 20
4 7
OUTPUT:
45

題意，peter要從一個(gè)地點(diǎn)S到地點(diǎn)T求最小花費(fèi)，每條道路都是可以雙向走的茬祷，且都有一個(gè)花費(fèi)豪筝。另外peter可以從f條免費(fèi)的航線選一條可以不花錢直接從點(diǎn)A飛到點(diǎn)B可帽，求peter到終點(diǎn)的最小花費(fèi)际邻。

分析胯究，若沒有免費(fèi)航線蚊伞，就跑一邊最短路dijkstra就可以沿癞，有免費(fèi)航線可以這么考慮援雇，比如有一條免費(fèi)航線是從A到B，那么起點(diǎn)S到終點(diǎn)T的最小花費(fèi)有兩種情況椎扬，一種是直接從S到T熊杨，另一種是S到A，然后經(jīng)過AB免費(fèi)航線從B到T盗舰，那么最小花費(fèi)即是這兩種情況的最小值晶府，因?yàn)橛衒條免費(fèi)航線題目說只能用一條，那么我們把這f條航線都試一遍即可钻趋。其中需要用到B到T的距離川陆，這里在算法開始預(yù)處理出S到所有點(diǎn)的最短路和T到所有點(diǎn)的最短路即可，即跑兩邊最短路蛮位。最后還要注意free的航線是單向的较沪，不是雙向的，我剛開始寫的雙向的失仁，結(jié)果wa了尸曼，如果是雙向的也沒問題，那就是三種情況了萄焦。綜合算法復(fù)雜度：O(2*NlogN+F)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int n, m, s, t, f;
struct edge
{
    int p;
    long long v;
};
struct node
{
    int x;
    long long d;
    bool operator<(const node &a) const
    {
        return d > a.d;
    }
};
struct abc
{
    int l;
    int r;
} e[150010];
vector<edge> P[50010];
long long dis1[50010];
long long dis2[50010];
int vis[50010];
priority_queue<node> Q;
void dij1()
{
    for (int i = 0; i <= n; i++)
        dis1[i] = 9999999900009;
    dis1[s] = 0;
    vis[s] = 1;
    Q.push({s, 0});
    while (!Q.empty())
    {
        node a = Q.top();
        Q.pop();
        if (dis1[a.x] != a.d)
            continue;
        vis[a.x] = 1;
        int maxx = P[a.x].size();
        for (int i = 0; i < maxx; i++)
            if (!vis[P[a.x][i].p])
            {
                if (dis1[P[a.x][i].p] > dis1[a.x] + P[a.x][i].v)
                {
                    dis1[P[a.x][i].p] = dis1[a.x] + P[a.x][i].v;
                    Q.push((node){P[a.x][i].p, dis1[P[a.x][i].p]});
                }
            }
    }
}
void dij2()
{
    for (int i = 0; i <= n; i++)
        dis2[i] = 9999999900009;
    memset(vis, 0, sizeof(vis));
    dis2[t] = 0;
    vis[t] = 1;
    Q.push({t, 0});
    while (!Q.empty())
    {
        node a = Q.top();
        Q.pop();
        if (dis2[a.x] != a.d)
            continue;
        vis[a.x] = 1;
        int maxx = P[a.x].size();
        for (int i = 0; i < maxx; i++)
            if (!vis[P[a.x][i].p])
            {
                if (dis2[P[a.x][i].p] > dis2[a.x] + P[a.x][i].v)
                {
                    dis2[P[a.x][i].p] = dis2[a.x] + P[a.x][i].v;
                    Q.push((node){P[a.x][i].p, dis2[P[a.x][i].p]});
                }
            }
    }
}
int main()
{
    cin >> n >> m >> f >> s >> t;
    for (int i = 0; i < m; i++)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        P[x].push_back({y, z});
        P[y].push_back({x, z});
    }
    for (int i = 0; i < f; i++)
        scanf("%d%d", &e[i].l, &e[i].r);
    dij1();
    dij2();
    long long ans = dis1[t];
    for (int i = 0; i < f; i++)
    {
        long long a = dis1[e[i].l] + dis2[e[i].r];
        ans = min(a, ans);
    }
    cout << ans;
    return 0;
}

C: Canonical Coin Systems

問題描述

A coin system S is a finite (nonempty) set of distinct positive integers corresponding to coin values, also called denominations, in a real or imagined monetary system. For example, the coin system in common use in Canada is {1, 5, 10, 25, 100, 200}, where 1 corresponds to a 1-cent coin and 200 corresponds to a 200-cent (2-dollar) coin. For any coin system S, we assume that there is an unlimited supply of coins of each denomination, and we also assume that S contains 1,since this guarantees that any positive integer can be written as a sum of (possibly repeated) values in S.
Cashiers all over the world face (and solve) the following problem: For a given coin system and a positive integer amount owed to a customer, what is the smallest number of coins required to dispense exactly that amount? For example, suppose a cashier in Canada owes a customer 83 cents. One possible solution is 25+25+10+10+10+1+1+1, i.e.,8 coins, but this is not optimal, since the cashier could instead dispense 25 + 25 + 25 + 5 + 1 + 1 + 1, i.e., 7 coins (which is optimal in this case). Fortunately, the Canadian coin system has the nice property that the greedy algorithm always yields an optimal solution, as do the coin systems used in most countries. The greedy algorithm involves repeatedly choosing a coin of the
largest denomination that is less than or equal to the amount still owed, until the amount owed reaches zero. A coin system for which the greedy algorithm is always optimal is called canonical.
Your challenge is this: Given a coin system S = {c1, c2, . . . , cn }, determine whether S is canonical or non-canonical. Note that if S is non-canonical then there exists at least one counterexample, i.e., a positive integer x such that the minimum number of coins required to dispense exactly x is less than the number of coins used by the greedy algorithm. An example of a non-canonical coin system is {1, 3, 4}, for which 6 is a counterexample, since the greedy algorithm yields 4 + 1 + 1 (3 coins), but an optimal solution is 3 + 3 (2 coins). A useful fact (due to Dexter Kozen and Shmuel Zaks) is that if S is non-canonical, then the smallest counterexample is less than the sum of the two largest denominations.
輸入
Input consists of a single case. The ?rst line contains an integer n (2 ≤ n ≤ 100), the number of denominations in the coin system. The next line contains the n denominations as space-separated integers c1 c2 . . . cn, where c1 = 1 and c1 < c2 < . . . < cn ≤ 10⁶.
輸出
Output “canonical” if the coin system is canonical, or “non-canonical” if the coin system is non-canonical.

題意：題目給出一種算法控轿，對(duì)于一個(gè)錢數(shù)怎么求出搭配需要的最小硬幣數(shù)，問你算法是否是正確的拂封。

解析：參考隊(duì)員HaiZheng Tung 的博客

D: Cat and Mice

E: Company Picnic

F: GlitchBot

題目描述
One of our delivery robots is malfunctioning! The job of the robot is simple; it should follow a list of instructions in order to reach a target destination. The list of instructions is originally correct to get the robot to the target. However, something is going wrong as we upload the instructions into the robot’s memory. During the upload, one random instruction from the list takes on a different value than intended. Yes,there is always a single bad instruction in the robot’s memory and it always results in the robot arriving at an incorrect destination as it finishes executing the list of instructions.
The robot can execute the instructions “Left”, “Right”, and “Forward”. The “Left” and “Right” instructions do not result in spatial movement but result in a 90-degree turn in the corresponding direction. “Forward” is the only instruction that results in spatial movement, causing the robot to move one unit in the direction it is facing. The robot always starts at the origin (0, 0) of a grid and faces north along the positive y-axis.
Given the coordinates of the target destination and the list of instructions that the robot has in its memory, you are to identify a correction to the instructions to help the robot reach the proper destination.
輸入
The first line of the input contains the x and y integer coordinates of the target destination, where ?50 ≤ x ≤ 50 and ?50 ≤ y ≤ 50. The following line contains an integer n representing the number of instructions in the list, where 1 ≤ n ≤ 50. The remaining n lines each contain a single instruction. These instructions may be: “Left”, “Forward”, or “Right”.
輸出
Identify how to correct the robot’s instructions by printing the line number (starting at 1) of an incorrect input instruction, followed by an instruction substitution that would make the robot reach the target destination. If there are multiple ways to fix the instructions, report the fix that occurs for the earliest line number in the sequence of instructions. There is always exactly one unique earliest fix.
INPUT:
3 2
11
Forward
Right
Forward
Forward
Left
Forward
Forward
Left
Forward
Right
Forward
OUTPUT:
8 Right

題意：就是給你一串命令茬射，告訴你其中有一條命令是錯(cuò)的，那么你能不能找出是哪一條命令是錯(cuò)的來冒签，并且把它改正呢在抛？

分析：數(shù)據(jù)量巨小，那么我們就挨個(gè)改改試試唄萧恕？試試就試試刚梭，AC！就是每一步改一次試試能不能走到終點(diǎn)票唆。
(代碼為現(xiàn)場(chǎng)提交代碼朴读，沒再優(yōu)化和美化，可能比較挫)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
int ins[1000];
int fx, fy;
int main()
{
    int t;
    cin >> fx >> fy;
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        string s;
        cin >> s;
        if (s[0] == 'F')
            ins[i] = 1;
        else if (s[0] == 'L')
            ins[i] = 2;
        else if (s[0] == 'R')
            ins[i] = 3;
    }
    int ok = 0;
    int anst;
    int ansk;
    for (int i = 1; i <= t && !ok; i++)
    {
        int d = 4;
        int x = 0, y = 0;
        int key = ins[i];
        for (int j = 1; j <= 3 && !ok; j++)
        {
            d = 4;
            x = 0;
            y = 0;
            ins[i] = j;
            for (int k = 1; k <= t; k++)
            {
                if (ins[k] == 1)
                {
                    if (d == 1)
                        x--;
                    else if (d == 2)
                        x++;
                    else if (d == 3)
                        y--;
                    else if (d == 4)
                        y++;
                }
                else if (ins[k] == 2)
                {
                    if (d == 1)
                        d = 3;
                    else if (d == 2)
                        d = 4;
                    else if (d == 3)
                        d = 2;
                    else if (d == 4)
                        d = 1;
                }
                else if (ins[k] == 3)
                {
                    if (d == 1)
                        d = 4;
                    else if (d == 2)
                        d = 3;
                    else if (d == 3)
                        d = 1;
                    else if (d == 4)
                        d = d = 2;
                }
                if (x == fx && y == fy && k == t)
                {
                    ok = 1;
                    anst = i;
                    ansk = j;
                    break;
                }
            }
        }
        ins[i] = key;
    }
    cout << anst << " ";
    if (ansk == 1)
        cout << "Forward";
    else if (ansk == 2)
        cout << "Left";
    else if (ansk == 3)
        cout << "Right";
    return 0;
}

G: Greeting Card

題目描述
Quido plans to send a New Year greeting to his friend Hugo. He has recently acquired access to an advanced high-precision plotter and he is planning to print the greeting card on the plotter.
Here’s how the plotter operates. In step one, the plotter plots an intricate pattern of n dots on the paper. In step two, the picture in the greeting emerges when the plotter connects by a straight segment each pair of dots that are exactly 2 018 length units apart.
The plotter uses a special holographic ink, which has a limited supply.Quido wants to know the number of all plotted segments in the picture to be sure that there is enough ink to complete the job.
輸入
The first line of input contains a positive integer n specifying the number of plotted points. The following n lines each contain a pair of space-separated integer coordinates indicating one plotted point. Each coordinate is non-negative and less than 231. There are at most 105 points, all of them are distinct.
In this problem, all coordinates and distances are expressed in plotter length units, the length of the unit in the x-direction and in the y-direction is the same.
輸出
The output contains a single integer equal to the number of pairs of points which are exactly 2018 length units apart.
INPUT：
4
20180000 20180000
20180000 20182018
20182018 20180000
20182018 20182018
OUTPUT:
4
題意 給你N個(gè)點(diǎn)惰说，讓你求有多少對(duì)點(diǎn)之間的距離是2018磨德，Haizheng第一感覺缘回，2018之下有多少隊(duì)數(shù)可以平方和再開方是2018呢吆视，結(jié)果只有1118和1680 典挑，那爽了，直接開個(gè)桶判斷對(duì)于某個(gè)點(diǎn)是否有這種情況就是了啦吧，這里注意要把2維的點(diǎn)轉(zhuǎn)化為1維的數(shù)字...開map您觉，把一個(gè)二維點(diǎn)hash成一個(gè)數(shù)即可。一發(fā)AC授滓，對(duì)于這個(gè)想法有一個(gè)需要注意的地方就是點(diǎn)對(duì)是成對(duì)關(guān)系的所以最后答案要除以2輸出

#include <iostream>
#include <map>
using namespace std;
long long p = 2147483648;
int a[500];
int n;
struct edge
{
    long long x;
    long long y;
} e[100010];
map<unsigned long long, int> m;
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> e[i].x >> e[i].y;
        m[e[i].x * p + e[i].y]++;
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        unsigned long long x = e[i].x * p + e[i].y + 2018;
        ans += m[x];
        x = e[i].x * p + e[i].y - 2018;
        ans += m[x];
        x = (e[i].x + 2018) * p + e[i].y;
        ans += m[x];
        x = (e[i].x - 2018) * p + e[i].y;
        ans += m[x];
        x = (e[i].x - 1118) * p + (e[i].y - 1680);
        ans += m[x];
        x = (e[i].x + 1118) * p + (e[i].y - 1680);
        ans += m[x];
        x = (e[i].x + 1118) * p + (e[i].y + 1680);
        ans += m[x];
        x = (e[i].x - 1118) * p + (e[i].y + 1680);
        ans += m[x];
        x = (e[i].x - 1680) * p + (e[i].y - 1118);
        ans += m[x];
        x = (e[i].x + 1680) * p + (e[i].y - 1118);
        ans += m[x];
        x = (e[i].x - 1680) * p + (e[i].y + 1118);
        ans += m[x];
        x = (e[i].x + 1680) * p + (e[i].y + 1118);
        ans += m[x];
    }
    cout << ans / 2;
    return 0;
}

H: Imperfect GPS

題目描述
Lots of runners use personal Global Positioning System (GPS) receivers to track how many miles they run. No GPS is perfect,
though: it only records its position periodically rather than continuously, so it can miss parts of the true running path. For this problem we’ll consider a GPS that works in the following way when tracking a run:
? At the beginning of the run, the GPS ?rst records the runner’s starting position at time 0.
? It then records the position every t units of time.
? It always records the position at the end of the run, even if the total running time is not a multiple of t.
The GPS assumes that the runner goes in a straight line between each consecutive pair of recorded positions. Because of this, a GPS can underestimate the total distance run.
For example, suppose someone runs in straight lines and at constant speed between the positions on the left side of Table 1. The time they reach each position is shown next to the position. They stopped running at time 11. If the GPS records a position every 2 units of time, its readings would be the records on the right side of Table 1.

image

The total distance run is approximately 14.313708 units, while the GPS measures the distance as approximately 11.650281 units. The difference between the actual and GPS distance is approximately 2.663427 units, or approximately 18.607525% of the total run distance.
Given a sequence of positions and times for a running path, as well as the GPS recording time interval t, calculate the percentage of the total run distance that is lost by the GPS. Your computations should assume that the runner goes at a constant speed in a straight line between consecutive positions.
輸入
The input consists of a single test case. The first line contains two integers n (2 ≤ n ≤ 100) and t(1 ≤ t ≤ 100), where n is the total number of positions on the running path, and t is the recording time interval of the GPS (in seconds).
The next n lines contain three integers per line. The i-th line has three integers xi, yi (?10⁶ ≤ xi, yi ≤10⁶), and ti (0 ≤ ti ≤ 10⁶), giving the coordinates of the i-th position on the running path and the time (in seconds) that position is reached. The values of ti’s are strictly increasing. The first and last positions are the start and end of the run. Thus, t1 is always zero.
It is guaranteed that the total run distance is greater than zero.
輸出
Output the percentage of the actual run distance that is lost by the GPS. The answer is considered correct if it is within 10^?5 of the correct answer.
INPUT:
6 2
0 0 0
0 3 3
-2 5 5
0 7 7
2 5 9
0 3 11
OUTPUT:
18.60752550117103

解析：from mhr :題目題意遠(yuǎn)大于題目本身難度琳水，實(shí)際上就是求原先的記錄與后來的記錄的偏差，后來的記錄因?yàn)槭且粋€(gè)給定的范圍的T般堆，所以如果要跟原來的記錄扯上關(guān)系在孝，那么應(yīng)該最先想到用點(diǎn)與方向向量的方式表示一個(gè)向量然后計(jì)算這個(gè)方向上對(duì)應(yīng)位置的點(diǎn)。也就是Q=P+t*v這樣把t算出來Q算出來就是GPS偏差的點(diǎn)然后算距離求差值算百分?jǐn)?shù)就行了

#include <bits/stdc++.h>
using namespace std;
double sum1, sum2;
struct v
{
    double x, y, t;
} num[6666];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> num[i].x >> num[i].y >> num[i].t;
    for (int i = 2; i <= n; i++)
        sum1 += hypot((num[i].x - num[i - 1].x), (num[i].y - num[i - 1].y));
    v st = num[1];
    for (int i = 1; i <= n - 1; i++)
    {
        while (st.t + m <= num[i + 1].t)
        {
            sum2 += hypot(num[i].x + (num[i + 1].x - num[i].x) / (num[i + 1].t - num[i].t) * (st.t + m - num[i].t) - st.x, num[i].y + (num[i + 1].y - num[i].y) / (num[i + 1].t - num[i].t) * (st.t + m - num[i].t) - st.y);
            st.x = num[i].x + (num[i + 1].x - num[i].x) / (num[i + 1].t - num[i].t) * (st.t + m - num[i].t);
            st.y = num[i].y + (num[i + 1].y - num[i].y) / (num[i + 1].t - num[i].t) * (st.t + m - num[i].t);
            st.t += m;
        }
    }
    sum2 += hypot(num[n].x - st.x, num[n].y - st.y);
    cout << fixed << setprecision(14) << (sum1 - sum2) / sum1 * 100;
}

I: Odd Gnome

題目描述
According to the legend of Wizardry and Witchcraft, gnomes live in burrows underground, known as gnome holes. There they dig
up and eat the roots of plants, creating little heaps of earth around gardens, causing considerable damage to them.
Mrs. W, very annoyed by the damage, has to regularly de-gnome her garden by throwing the gnomes over the fence. It is a lot of work to throw them one by one because there are so many. Fortunately, the species is so devoted to their kings that each group always follows its king no matter what. In other words, if she were to throw just the king over the fence, all the other gnomes in that group would leave.
So how does Mrs. W identify the king in a group of gnomes? She knows that gnomes travel in a certain order, and the king, being special, is always the only gnome who does not follow that order.
Here are some helpful tips about gnome groups:
? There is exactly one king in a group.
? Except for the king, gnomes arrange themselves in strictly increasing ID order.
? The king is always the only gnome out of that order.
? The king is never the first nor the last in the group, because kings like to hide themselves.
Help Mrs. W by finding all the kings!
輸入
The input starts with an integer n, where 1 ≤ n ≤ 100, representing the number of gnome groups. Each of the n following lines contains one group of gnomes, starting with an integer g, where 3 ≤ g ≤ 1 000,representing the number of gnomes in that group. Following on the same line are g space-separated integers, representing the gnome ordering. Within each group all the integers (including the king) are unique and in the range [0, 10 000]. Excluding the king, each integer is exactly one more than the integer preceding it.
輸出
For each group, output the king’s position in the group (where the ?rst gnome in line is number one).

解析：簽到題淮摔，找出那個(gè)破壞升序排列的家伙私沮！
wa了一次，是因?yàn)榘褦?shù)組開小了和橙，WTF仔燕？！

#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <iostream>
using namespace std;
int a[110000];
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        memset(a, 0, sizeof(a));
        int n;
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> a[i];
        for (int i = 1; i < n - 1; i++)
            if (a[i] - a[i - 1] != 1)
            {
                cout << i + 1 << endl;
                break;
            }
    }
    return 0;
}

J: Progressive Scramble

題目描述
You are a member of a naive spy agency. For secure communication,members of the agency use a very simple encryption algorithm – which changes each symbol in the message ‘progressively’, i.e., based on the symbols preceding it. The allowed symbols are space and the 26 lowercase English letters. For encryption purposes we assign them the values 0 (for space) and 1 through 26 (for a–z). We’ll let v(s) represent the numeric value of symbol s.
Consider a message with symbols s1, s2, . . . , sn. The encryption algorithm starts by converting the ?rst symbol s1 into its associated value u1 = v(s1). Then for each subsequent symbol si in the message, the computed value is ui = v(si) + ui?1 — the sum of its associated value and the computed value for the previous symbol. (Note that when there is a space in the input
message, the previous scrambled letter is repeated.) This process continues until all the ui are computed.
At this point, the message is a sequence of numeric values. We need to convert it back to symbols to print it out. We do this by taking the value ui modulo 27 (since there are 27 valid symbols), and replacing that value with its corresponding symbol. For example, if ui = 32, then 32 mod 27 = 5, which is the symbol ‘e’ (since v(e) = 5).
Let’s look at an example. Suppose we want to encrypt the string “my pie”.

1. First, convert each symbol si into v(si): [13, 25, 0, 16, 9, 5].
2. Next, compute each ui: [13, 38, 38, 54, 63, 68].
3. Then, use modulus on the ui: [13, 11, 11, 0, 9, 14].
4. Finally, convert these back to symbols: “mkk in”.
   Create a program that takes text and encrypts it using this algorithm, and also decrypts text that has been encrypted with this algorithm.
   輸入
   The input to your program consists of a single integer 1 ≤ n ≤ 100 on its own line. This number is followed by n lines, each containing the letter ‘e’ or ‘d’, a single space, and then a message made up of lowercase letters (a–z) and spaces, continuing to the end of the line. Each message is between 1 and 80 characters long. The letters ‘d’ and ‘e’ indicate that your program decrypts or encrypts the subsequent string, respectively.
   輸出
   Output the result of encrypting or decrypting each message from the input on its own separate line. Note that differences in whitespace are significant in this problem. Therefore your output must match the correct output character-for-character, including spaces.

解析：因?yàn)檫@題有坑魔招，出了點(diǎn)小差錯(cuò)晰搀，導(dǎo)致我隊(duì)mhr同學(xué)....算了，不說了办斑，很氣外恕，

#include <bits/stdc++.h>
using namespace std;
long long num[6666], pre[6666], ans[6666], now;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    while (n--)
    {
        char x;
        cin >> x;
        string a;
        getline(cin, a);
        a.erase(0, 1);
        if (x == 'e')
        {
            for (int i = 0; i < a.size(); i++)
            {
                if (isspace(a[i]))
                    num[i] = 0;
                else
                    num[i] = a[i] - 'a' + 1;
            }
            for (int i = 0; i < a.size(); i++)
            {
                if (i == 0)
                    pre[i] = num[i];
                else
                    pre[i] = pre[i - 1] + num[i];
                pre[i] %= 27;
            }
            for (int i = 0; i < a.size(); i++)
            {
                if (pre[i])
                    cout << char(pre[i] + 'a' - 1);
                else
                    cout << ' ';
            }
            cout << "\n";
        }
        else
        {
            string t = "";
            for (int i = 0; i < a.size(); i++)
            {
                if (isspace(a[i]))
                    num[i] = 0;
                else
                    num[i] = a[i] - 'a' + 1;
            }
            for (int i = 0; i < a.size(); i++)
            {
                if (i == 0)
                    pre[i] = num[i], now = pre[i] / 27;
                else
                {
                    long long re = 27 * now + num[i];
                    if (re < pre[i - 1])
                        re += 27;
                    pre[i] = re;
                    now = re / 27;
                }
            }
            ans[0] = pre[0];
            for (int i = 1; i < a.size(); i++)
                ans[i] = pre[i] - pre[i - 1];
            for (int i = 0; i < a.size(); i++)
            {
                if (ans[i])
                    t += char(ans[i] + 'a' - 1);
                else
                    t += ' ';
            }
            cout << t << "\n";
        }
    }
}

K: Space Probe

L: Suspension Bridges

題目描述
Mountain villages like to attract tourists by building suspension bridges, such as the one depicted here in the Harz Mountains in Germany. These bridges allow adventurously-inclined people to seek their thrills by crossing over deep gorges. To make sure that everyone gets just the right amount of excitement, the sag at the deepest point of the bridge should be significant relative to the distance the bridge covers.
Given the distance between the anchor points where the bridge is attached, and given a desired amount of sag, compute how long each of the cables holding the suspension bridge needs to be!
To help you solve this task, here is some background: A free-hanging suspension bridge will take on the form of a catenary curve (catena is Latin for chain), just like a free-hanging chain between two poles. Given the horizontal distance d between two anchor points and the desired amount s the cable is sagging in the center, there exists a positive parameter a such that a + s = a · cosh(d/2a). The length of the cable is then given by `(a, d) = 2a · sinh(d/2a).
The functions sinh and cosh denote the hyperbolic sine and hyperbolic cosine, respectively, which are defined as follows:
輸入
The input consists of a single test case with two space-separated integers d and s given on a single line such that 0 < d ≤ 1 000 and 0 < s ≤ 1 000. The number d denotes the distance between the anchor points and s is the desired sag at the center of the bridge.
輸出
Output the length of cable needed to cover the distance between the anchor points to achieve the desired sag. Your answer should be correct within an absolute error of 10?4.
INPUT:
400 40
OUTPUT:
410.474747252
這二分不能更裸了，只是當(dāng)時(shí)沒人做乡翅，我也沒敢做這題啊吁讨，又被帶偏節(jié)奏了。峦朗。建丧。

#include <bits/stdc++.h>
using namespace std;
double d, s;
double check(double x)
{
    return x + s - x * cosh(d / 2.0 / x);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> d >> s;
    double l = 0, r = INT_MAX;
    for (int i = 0; i < 100; i++)
    {
        double mid = (r + l) / 2.0;
        if (check(mid) < 1e-9)
            l = mid;
        else
            r = mid;
    }
    cout << fixed << setprecision(10) << (2.0 * l * sinh(d / 2.0 / l));
}

M: Umbral Decoding