TopCoder 2019线下比赛

Love The Way You Lie 2022-01-14 07:47 171阅读 0赞

### 文章目录 ###

*  warmup
 *   *  解法代码1
     *  解题代码2
 *  1 描述
 *   *  解答
 *  2 描述
 *   *  解答
 *  3 描述
 *  4 描述

# warmup #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdHk5NDUuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70]  
可以在牛客这里查看更多的内容：  
[https://ac.nowcoder.com/acm/contest/921\#question][https_ac.nowcoder.com_acm_contest_921_question]

## 解法代码1 ##

NB解法——出自楼天城, 不过说实话，没怎么看懂的啊

#ifdef _MSC_VER
    #define _CRT_SECURE_NO_WARNINGS
    #endif
     
    #include <bits/stdc++.h>
     
    using namespace std;
     
    typedef long long int64;
    typedef unsigned long long uint64;
    #define two(X) (1<<(X))
    #define twoL(X) (((int64)(1))<<(X))
    #define contain(S,X) (((S)&two(X))!=0)
    #define containL(S,X) (((S)&twoL(X))!=0)
    const double pi=acos(-1.0);
    const double eps=1e-9;
    template<class T> inline void ckmin(T &a,T b){if(b<a) a=b;}
    template<class T> inline void ckmax(T &a,T b){if(b>a) a=b;}
    template<class T> inline T sqr(T x){return x*x;}
    typedef pair<int,int> ipair;
    #define SIZE(A) ((int)A.size())
    #define LENGTH(A) ((int)A.length())
    #define MP(A,B) make_pair(A,B)
    #define PB(X) push_back(X)
    #define FOR(i,a,b) for(int i=(a);i<(b);++i)
    #define REP(i,a) for(int i=0;i<(a);++i)
    #define ALL(A) A.begin(),A.end()
    using VI=vector<int>;
     
    int main()
    {
    #ifdef _MSC_VER
        freopen("input.txt","r",stdin);
    #endif
        std::ios::sync_with_stdio(false);
        double sx,sy;
        while (cin>>sx>>sy)
        {
            double x,y;
            cin>>x>>y;
            double angle;
            cin>>angle;
            double dx=cos(angle/180.0*pi);
            double dy=sin(angle/180.0*pi);
            int ok=0;
            REP(step,1000000)
            {
                double lx=1e100;
                double ly=1e100;
                if (dx>eps)
                    lx=(sx-x)/dx;
                else if (dx<-eps)
                    lx=x/(-dx);
                if (dy>eps)
                    ly=(sy-y)/dy;
                else if (dy<-eps)
                    ly=y/(-dy);
                double l=min(lx,ly);
                x+=l*dx;
                y+=l*dy;
                if ((abs(x)<=eps || abs(x-sx)<=eps) && (abs(y)<=eps || abs(y-sy)<=eps))
                {
                    ok=1;
                    break;
                }
                if (abs(x)<=eps || abs(x-sx)<=eps) dx=-dx;
                if (abs(y)<=eps || abs(y-sy)<=eps) dy=-dy;
            }
            if (ok)
                printf("Yes\n");
            else
                printf("No\n");
    #ifndef _MSC_VER
            break;
    #endif
        }
        return 0;
    }

## 解题代码2 ##

这个代码可能更适合凡人去用吧

#include<bits/stdc++.h>
    using namespace std;
    int h,w,x,y,d;
    
    int main()
    {
        //freopen("input.txt","r",stdin);
        cin >> h >> w >> x >> y >> d;
        if (d==45||d==225){
            if (abs(x-y)%__gcd(h,w)==0) puts("Yes"); else puts("No");
        } else if (d==135||d==315){
            if (abs(x+y)%__gcd(h,w)==0) puts("Yes"); else puts("No");
        } else puts("No");
        return 0;
    }

# 1 描述 #

Problem Statement
        
    You are in charge of programming the hotel elevator.
    Many hotel guests consider the digit 4 unlucky. To make their stay more comfortable, the hotel has decided that when numbering the floors it will skip all numbers that contain the digit 4. Thus, the sequence of floor numbers starts as follows: 0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 28, 29, 30, 31, 32, 33, 35, 36, 37, 38, 39, 50, 51, ...
    Suppose a guest entered the elevator in the lobby of the hotel (i.e., floor 0) and pushed the button buttonPressed. We want to send the elevator to the desired floor. Calculate and return the number of physical floors the elevator should ascend.
    Definition
        
    Class:
    LuckyElevator
    Method:
    actualFloor
    Parameters:
    int
    Returns:
    int
    Method signature:
    int actualFloor(int buttonPressed)
    (be sure your method is public)
    Limits
        
    Time limit (s):
    2.000
    Memory limit (MB):
    256
    Constraints
    -
    buttonPressed will be between 1 and 100,000, inclusive.
    -
    buttonPressed will not contain the digit 4.
    Examples
    0)
    
        
    3
    Returns: 3
    The floor number 3 is the actual third floor from the bottom.
    1)
    
        
    5
    Returns: 4
    When the guest pushes the button number 5, we should bring them to the floor that's fourth from the bottom. (Remember that there is no floor number 4.)
    2)
    
        
    18
    Returns: 16
    As there is no floor 4 and no floor 14, the button number 18 will bring you to the sixteenth physical floor.
    3)
    
        
    50
    Returns: 36
    
    4)
    
        
    100000
    Returns: 59049
    This is the largest possible input. The button number 100,000 sends the elevator to the 59,049-th actual floor of the building.
    This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

## 解答 ##

class LuckyElevator:
        def actualFloor(self, buttonPressed):
            n = buttonPressed
            res = []
            for i in range(n):
                if '4' not in str(i):
                    res.append(i)
                else:
                    pass
            return len(res)

# 2 描述 #

Problem Statement
        
    Basha promised her friend Mel that she will come for a visit somewhere between the firstDay of the firstMonth and the lastDay of the lastMonth in 2019. Basha and Mel live in countries separated by the sea, so Basha has to buy plane tickets.
    Airlines are using many tricks when pricing their tickets. One of the important ones is the "Saturday night stay" concept: if your stay at the destination includes the night from a Saturday to a Sunday, you are unlikely to be a business traveler and thus they will give you a lower price for your tickets. Basha would like to have cheap plane tickets (who wouldn't), so she wants to plan her trip in such a way that it will include at least one Saturday night.
    To summarize:
    Basha's day of arrival must be on the firstDay of the firstMonth 2019 or later.
    Basha's day of departure must be on the lastDay of the lastMonth 2019 or earlier.
    Basha must stay at Mel's place for at least one Saturday night.
    Two trip schedules are considered different if Basha arrives and/or departs on a different day. Count all possible trip schedules, and return the answer.
    Definition
        
    Class:
    SaturdayNightStay
    Method:
    countOptions
    Parameters:
    integer, integer, integer, integer
    Returns:
    integer
    Method signature:
    def countOptions(self, firstDay, firstMonth, lastDay, lastMonth):
    
    Limits
        
    Time limit (s):
    2.000
    Memory limit (MB):
    256
    Notes
    -
    The year 2019 is not a leap year. The number of days in the individual months of 2019 is 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, and 31.
    -
    The 1st of January 2019 was a Tuesday.
    -
    As explained in the statement, "Saturday night" is short for "the night that starts on a Saturday and ends on a Sunday".
    Constraints
    -
    firstMonth and lastMonth will each be between 1 and 12, inclusive.
    -
    firstDay will be between 1 and the number of days in firstMonth, inclusive.
    -
    lastDay will be between 1 and the number of days in lastMonth, inclusive.
    -
    The firstDay of the firstMonth will not be later in 2019 than the lastDay of the lastMonth.
    Examples
    0)
    
        
    15
    6
    16
    6
    Returns: 1
    The earliest day on which Basha can arrive is today: the 15th of June. This is a Saturday.
    The latest day on which she can leave is the 16th of June: the Sunday tomorrow.
    In order to spend the Saturday night in her destination, Basha must arrive on the 15th and depart on the 16th.
    1)
    
        
    16
    6
    22
    6
    Returns: 0
    Regardless of when she arrives and departs, her trip will not include any Saturday nights.
    Note that the trip which arrives on the 16th and departs on the 22nd includes both a Saturday (the 22nd) and a Sunday (the 16th) but that is not enough: the trip does not contain any Saturday night.
    2)
    
        
    1
    1
    31
    1
    Returns: 382
    There are many viable options in January 2019, including the longest one: arriving on the 1st and departing on the 31st of January. (This trip contains four different Saturday nights. Additional Saturday nights do not matter, the only requirement is that there has to be at least one of them.)
    3)
    
        
    7
    8
    19
    10
    Returns: 2485
    
    This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

## 解答 ##

# -*- coding: utf-8 -*-
    
    # !/usr/bin/env python
    
    # Time: 2019/6/15 15:22
    
    # Author: sty
    
    # File: 2.py
    
    # class SaturdayNightStay:
    
    import datetime
    
    class SaturdayNightStay:
    
        def countOptions(self, firstDay, firstMonth, lastDay, lastMonth):
            def get_day_list(start='2019-01-01', end='2019-12-31'):
                '''
                得到设置时间段内的所有时间日期
                :return:以列表形式返回所有时间日期
                '''
                daylist = []  # daylist 存放这个时间段所有的日期
                # 将日期格式化
                datestart = datetime.datetime.strptime(start, '%Y-%m-%d')
                dateend = datetime.datetime.strptime(end, '%Y-%m-%d')
                while datestart <= dateend:
                    daylist.append(datestart.strftime('%Y,%m,%d'))
                    datestart += datetime.timedelta(days=1)
                return daylist
    
            def get_week_num(month, day):
                return datetime.datetime(2019, month, day).weekday() + 1
    
            res_num = 0
            star_day = str(2019)+'-'+str(firstMonth)+'-'+str(firstDay)
            end_day = str(2019)+'-'+str(lastMonth)+'-'+str(lastDay)
            day_list = get_day_list(star_day, end_day)
            day_res = []
            for i in day_list:
                date = i.split(',')
                month = date[1]
                day = date[2]
                # print(date, get_week_num(int(month), int(day)))
                day_res.append(get_week_num(int(month), int(day)))
            index_list = []
            day_res_len = len(day_res)
            for i in range(day_res_len):
                if int(day_res[i]) == 6:
                    index_list.append(i+1)
            # print(index_list, len(day_res))
            sum = 0
            for i in range(len(index_list)):
                a = 0
                b = 0
                if i == 0:
                    a = index_list[i]
                else:
                    a = index_list[i] - index_list[i - 1]
                    # sum += (index_list[i] - index_list[i - 1] + 1) * (day_res_len - i)
                b = day_res_len - index_list[i]
                # print(a, b)
                sum += a * b
            # print(sum)
            return sum
    a = SaturdayNightStay()
    print(a.countOptions(7, 8, 19, 10))

# 3 描述 #

Problem Statement
        
    You are given a String N that contains the decimal representation of a (possibly very large) positive integer. In order to keep the input size low, you have to generate this number N on your own. You are given the int digits, the String prefN, and the int seed. Use the following pseudocode to generate N:
    A[0] = seed
    for i = 1 to digits-1:
    	A[i] = (A[i-1] * 1009 + 10009) modulo 100019
    
    for i = 0 to length(prefN)-1:
            N[i] = prefN[i]
    
    for i = length(prefN) to digits-1:
    	N[i] = N[ A[i] modulo i ]
    We are going to swap two digits of the large number stored in N. The digits to swap will be chosen uniformly at random. More precisely, we will consider all pairs of indices (i, j) such that 0 <= i < j <= digits-1, we will select one of these pairs of indices uniformly at random, and then we will swap the digits N[i] and N[j].
    Let E be the expected value of the number we will obtain. (In other words, E is the average of all possible outcomes.) Then, let F = E * digits * (digits - 1). It can be shown that F is always an integer. As the value F can be very large, please calculate and return the value (F modulo 1,000,000,007).
    Definition
        
    Class:
    TheUnexpectedSwap
    Method:
    findExpectedResult
    Parameters:
    int, String, int
    Returns:
    int
    Method signature:
    int findExpectedResult(int digits, String prefN, int seed)
    (be sure your method is public)
    Limits
        
    Time limit (s):
    2.000
    Memory limit (MB):
    256
    Notes
    -
    The reference solution would correctly solve any N that matches the constraints. It does not depend on the properties of the pseudorandom generator.
    Constraints
    -
    digits will be between 2 and 200,000, inclusive.
    -
    The length of prefN will be between 1 and min(1000,digits), inclusive.
    -
    Each character of prefN will be a digit ('0'-'9').
    -
    Character 0 of prefN will not be '0'.
    -
    seed will be between 0 and 100,018, inclusive.
    Examples
    0)
    
        
    2
    "32"
    0
    Returns: 46
    The number is N = "32". There is exactly one possible swap: we swap the characters N[0] and N[1], producing the new number "23".
    As there is only one outcome, we get that E = 23, and then F = 23 * 2 * 1 = 46.
    1)
    
        
    2
    "60"
    0
    Returns: 12
    After the swap the number obtained from N can have a leading zero. This is allowed. In this case the only possible swap will produce the number "06". The value of this number is simply 6.
    2)
    
        
    10
    "1"
    0
    Returns: 999999297
    The number you'll generate is N = "1111111111". There are 45 different pairs of digits we can swap. Regardless of which two digits we swap, the value of the new number will always be 1,111,111,111. Thus, we get that E = 1,111,111,111, and then F = 1,111,111,111 * 10 * 9 = 99,999,999,990. Make sure you correctly compute and return the value F modulo 10^9 + 7.
    3)
    
        
    6
    "123"
    47
    Returns: 5331084
    When generating N, you should first compute the sequence A = { 47, 57432, 47896, 27896, 51734, 99716 } and then use that to obtain N = "123332".
    There are 15 possible swaps. The average of their outcomes is E = 177702.8.
    This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

# 4 描述 #

Problem Statement
        
    A slash maze is a rectangular table of characters, each being either a slash or a backslash. Example:
    \\/\/
    \\//\
    \//\/
    \\/\\
    Each character represents a square cell with penetrable walls but an impenetrable diagonal wall. The entrance to the maze is always on the leftmost unit segment of the top side, and the exit is always on the rightmost unit segment of the bottom side. Thus, the slashes shown above correspond to the following maze:
     
    You start outside of the maze and you must end outside of the maze. Entering the maze takes one step, and leaving the maze takes one step. In each other step you can move from your current triangle across the side of a square into an adjacent triangle. The above figure shows a 17-step path through the maze.
    You are given the int steps. Construct any rectangular slash maze with the following properties:
    the number of rows is between 1 and 50, inclusive
    the number of colums is between 1 and 50, inclusive
    steps is exactly equal to the smallest number of steps needed to cross the maze from start to finish
    Return the maze as a String[]. If there is no maze with the desired properties, return an empty String[] instead.
    Definition
        
    Class:
    SlashPath
    Method:
    construct
    Parameters:
    int
    Returns:
    String[]
    Method signature:
    String[] construct(int steps)
    (be sure your method is public)
    Limits
        
    Time limit (s):
    2.000
    Memory limit (MB):
    256
    Constraints
    -
    steps will be between 1 and 3000, inclusive.
    Examples
    0)
    
        
    7
    Returns: {"\\\\/\\", "/\\\\\\", "\\\\\\\\" }
    A nicer formatting for the returned maze:
    \\/\
    /\\\
    \\\\
    (Note that in all example outputs the backslashes in strings are escaped: each \\ represents a single backslash.)
    1)
    
        
    17
    Returns: {"\\\\/\\/", "\\\\//\\", "\\//\\/", "\\\\/\\\\" }
    The example from the problem statement. The return value shown above corresponds to the figure in the statement.
    2)
    
        
    1234
    Returns: { }
    
    This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdHk5NDUuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdHk5NDUuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70]: /images/20220114/53c3283c2ed6445885287d22007b8f97.png
[https_ac.nowcoder.com_acm_contest_921_question]: https://ac.nowcoder.com/acm/contest/921#question
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdHk5NDUuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 1]: /images/20220114/d5a7a266254e4808aaf33344f6d0a9ff.png