A - Handmaid

Problem Statement

You are given the name SS of a certain person. The first character of SS is an uppercase English letter, and the other characters are lowercase English letters.

The name of this person's handmaid is the string obtained by converting the first letter of SS to lowercase and adding Of to the beginning. Find the name of this handmaid.

Constraints

• SS is a string of length between 11 and 1010, inclusive.
• The first character of SS is an uppercase English letter.
• The characters of SS other than the first are lowercase English letters.

Input

The input is given from Standard Input in the following format: s

Output

Output the answer on one line.

Sample 1

Glen

Ofglen

Converting the first letter of Glen to lowercase gives glen, and adding Of to the beginning gives Ofglen.

答案

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    string s;
    cin>>s;
    s[0]=s[0]+('a'-'A');
    s="Of"+s;
    cout<<s;
}

题解：

将字符串小写的首字母变成大写，所以取s[0]并加上'a'-'A'的ascii值就OK（注意：小写字母的ascii值大于大写字母的）

B - Greedy Draft

Problem Statement

There are NN customers numbered 11 to NN, and MM canned juices numbered 11 to MM.

Customer ii (1≤i≤N1≤i≤N) has a wish list of length LiLi​. The jj-th item (1≤j≤Li1≤j≤Li​) from the top of customer ii's wish list is canned juice Xi,jXi,j​. For any customer ii, the numbers Xi,1,…,Xi,LiXi,1​,…,Xi,Li​​ on customer ii's wish list are distinct.

Customers 1,…,N1,…,N, in this order, will now choose their beverages, following the procedure below.

• If the customer's wish list contains a canned juice that has not yet been chosen by anyone at that point, they choose the canned juice whose number appears earliest in their wish list. Otherwise, they choose water.

Determine which beverage each customer gets.

Constraints

• 1≤N≤1001≤N≤100
• 1≤M≤1001≤M≤100
• 1≤Li≤M1≤Li​≤M (1≤i≤N1≤i≤N)
• 1≤Xi,j≤M1≤Xi,j​≤M (1≤i≤N1≤i≤N, 1≤j≤Li1≤j≤Li​)
• Xi,1,…,Xi,LiXi,1​,…,Xi,Li​​ are distinct. (1≤i≤N1≤i≤N)
• All input values are integers.

Input

The input is given from Standard Input in the following format:

NN MM
L1L1​
X1,1X1,1​ X1,2X1,2​ ⋯⋯ X1,L1X1,L1​​
L2L2​
X2,1X2,1​ X2,2X2,2​ ⋯⋯ X2,L2X2,L2​​
⋮⋮
LNLN​
XN,1XN,1​ XN,2XN,2​ ⋯⋯ XN,LNXN,LN​​

Output

Output NN lines. The ii-th line (1≤i≤N1≤i≤N) should contain the number of the canned juice customer ii gets if they get one, or 0 if customer ii gets water.

Sample 1

4 5
3
3 1 2
3
3 2 1
2
2 3
4
2 5 3 1

3
2
0
5

Among the numbers on customer 11's wish list, the canned juices not yet chosen by anyone are 3,1,23,1,2. The one appearing earliest in the list is 33, so customer 11 chooses canned juice 33.

Among the numbers on customer 22's wish list, the canned juices not yet chosen by anyone are 2,12,1. The one appearing earliest in the list is 22, so customer 22 chooses canned juice 22.

For the numbers on customer 33's wish list, all corresponding canned juices have already been chosen by someone at that point. Thus, customer 33 chooses water.

Among the numbers on customer 44's wish list, the canned juices not yet chosen by anyone are 5,15,1. The one appearing earliest in the list is 55, so customer 44 chooses canned juice 55.

答案

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    vector<int>used(m+1,0);
    while(n--)
    {
        int t;
        cin>>t;
        vector<int>num(t);
        bool j=false;
        for(int i=0;i<t;i++)
        {
            cin>>num[i];
        }
        for(int i=0;i<t;i++)
        {
            if(used[num[i]]==0)
            {
                cout<<num[i]<<endl;
                used[num[i]]=1;
                j=true;
                break;
            }      
        }
        if(!j)
        {
            cout<<0<<endl;
        }
    }
}

题解：

题目要求前面的人选过的罐头 下面的人不可以再选，每个人只选自己心愿单最前面的罐头（如果被选过则向下顺延）所以引入一个used（m+1，0）来记录是否被选，然后再引入一个bool j 来判断每个人是否选，如果没有则输出0，所以在遍历过程中 对于每个数组，如果前面的没有被用的 则输出 被用过则顺延 一直没有则输出0。

C - Omelette Restaurant

Problem Statement

AtCoder Restaurant was open for NN days after opening.

On day ii (1≤i≤N1≤i≤N) after opening, the following actions were performed.

• In the morning of day ii, AiAi​ eggs are purchased.
• At noon on day ii, BiBi​ eggs are used. Here, eggs in stock are used in the order they were purchased.
• In the evening of day ii, all eggs that have been stocked for DD or more days are discarded.

There were no eggs in stock before the morning of day 11, and eggs never ran out at noon on any day.

Find how many eggs remain in the restaurant after the evening action on day NN.

TT test cases are given; solve each.

Constraints

• 1≤T≤2×1051≤T≤2×105
• 1≤D≤N≤2×1051≤D≤N≤2×105
• 1≤Ai,Bi≤101≤Ai​,Bi​≤10
• Eggs never run out at noon on any of the NN days.
• For each input, the sum of NN over all test cases is at most 2×1052×105.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

TT
case1case1​
case2case2​
⋮⋮
caseTcaseT​

caseicasei​ represents the ii-th test case.
Each test case is given in the following format:

NN DD
A1A1​ A2A2​ …… ANAN​
B1B1​ B2B2​ …… BNBN​

Output

Output TT lines.
The ii-th line (1≤i≤T1≤i≤T) should contain the answer for the ii-th test case.

Sample 1

3
3 1
7 2 3
1 3 2
3 2
7 2 3
1 3 2
2 1
2 1
1 2

3
5
0

In the first test case, the following actions are performed.

• Initially, AtCoder Restaurant has no eggs.
• In the morning of day 11, 77 eggs are purchased. The restaurant has 77 eggs stocked on day 11.
• At noon on day 11, 11 egg is used. The restaurant has 66 eggs stocked on day 11 remaining.
• In the evening of day 11, no eggs are discarded. The restaurant has 66 eggs stocked on day 11 remaining.
• In the morning of day 22, 22 eggs are purchased. The restaurant has 66 eggs stocked on day 11 and 22 eggs stocked on day 22.
• At noon on day 22, 33 eggs are used. The restaurant has 33 eggs stocked on day 11 and 22 eggs stocked on day 22 remaining.
• In the evening of day 22, the eggs stocked on day 11 are discarded. The restaurant has 22 eggs stocked on day 22 remaining.
• In the morning of day 33, 33 eggs are purchased. The restaurant has 22 eggs stocked on day 22 and 33 eggs stocked on day 33.
• At noon on day 33, 22 eggs are used. The restaurant has 33 eggs stocked on day 33 remaining.
• In the evening of day 33, no eggs are discarded. (This is because all eggs stocked on day 22 have already been used.) The restaurant has 33 eggs stocked on day 33 remaining.

Thus, 33 eggs remain after the evening action on day 33, so output 33 on the first line.

For the second test case, remember to output the number of eggs after discarding the eggs stocked on day 11 in the evening of day 33.

答案

#include<iostream>
#include<vector>
#include<deque>
using namespace std;
struct egg
{
    int cun_day;
    int count;
};
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,day;
        cin>>n>>day;
        vector<int>a(n),b(n);
        for(int i=0;i<n;i++){cin>>a[i];}
        for(int i=0;i<n;i++){cin>>b[i];}
        deque<egg>remain_egg;
        for(int i=0;i<n;i++)
        {
            int current_day=i+1;
            if(a[i]>0)
            {
                remain_egg.push_back({current_day,a[i]});
            }
            int need=b[i];
            while(!remain_egg.empty()&&need>0)
            {
                if(remain_egg.front().count<=need)
                {
                    need-=remain_egg.front().count;
                    remain_egg.pop_front();
                }
                else
                {
                    remain_egg.front().count-=need;
                    need=0;
                }
            }
            while(!remain_egg.empty())
            {
                if(current_day - remain_egg.front().cun_day >= day)
                {
                    remain_egg.pop_front();
                }
                else
                {
                    break;
                }
            }
        }
        long long re_count=0;
        for(const auto&num:remain_egg)
        {
            re_count+=num.count;
        }
        cout<<re_count<<endl;
    }
}

题解

知识点：双端队列（deque)，前端插入/删除 push_front()/pop_front()，后端插入push_back()/pop_back()

题解：

由于是先进先出 但还需要后端补充数据 所以我们选择双端队列，首先先定义一个结构体，表示哪天鸡蛋是存入的时间，并且买来多少鸡蛋。然后用两个数组a，b分别来存买来多少鸡蛋，以及中午用掉多少鸡蛋，然后用一个队列deque<egg>remain_egg来存储这些鸡蛋，按照时间顺序来排前后。

进行遍历数组将每天的买入的鸡蛋和购买时间存进队列，并用current_day纪录当前是第几天，同时看每日鸡蛋的消耗，用need来记录，然后将remain_egg.front()与need进行比较（第一个数据，因为先进先出）如果不够减，则need减去remain_egg.front()，并让remain_egg.front()出队并继续进行循环；如果够减，则反过来，用remain_egg.front()减去need，表示剩下的，然后将need清零，跳出循环。

同时我们还要判断鸡蛋是不是放的时间过长（也就是>=day）存放的时间如何表示呢？用当前的天数减去放入的日期（之前我们存储过）如果这个时间大于等于设置的时长，那么就出队，如果不是就跳出循环，来到下一天。

最后遍历将数量加加在一起即可

D - Max Straight

Problem Statement

You are given an integer sequence A=(A1,A2,…,AN)A=(A1​,A2​,…,AN​) of length NN.

Find the maximum length of a subsequence B=(B1,B2,…,B∣B∣)B=(B1​,B2​,…,B∣B∣​) of integer sequence AA that satisfies the following condition.

• Bi+1=Bi+1Bi​+1=Bi+1​ for all integers ii satisfying 1≤i≤∣B∣−11≤i≤∣B∣−1.

What is a subsequenceA subsequence of sequence AA is a sequence obtained by choosing zero or more elements of AA to delete, and arranging the remaining elements in their original order.

Constraints

• 1≤N≤2×1051≤N≤2×105
• 1≤Ai≤1091≤Ai​≤109
• All input values are integers.

Input

The input is given from Standard Input in the following format:

NN
A1A1​ A2A2​ …… ANAN​

Output

Output the answer.

Sample 1

7
3 4 3 5 7 6 2

4

B=(3,4,5,6)B=(3,4,5,6) is a subsequence of AA that satisfies the condition, and its length is 44.

There is no subsequence satisfying the condition with length greater than 44, so output 44.

答案

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
int main()
{
    int n;
    cin>>n;
    map<int,int>dp;
    int count=0;
    for(int i=0;i<n;i++)
    {
        int m;
        cin>>m;
        dp[m]=dp[m-1]+1;
        count=max(count,dp[m]);
    }
    cout<<count;
}

题解

我们为什么选择字典，因为数据存在10e9的情况，如果选用数组，则无法储存，题目要求这个子序列需要满足数字是后面的比前面大1，而且有一个前后关系，我们需要保证这个前后顺序，并且我们不能只一次循环比较下标以及数字大小，因为中间会有重复的数字，然后我们进行一个嵌套循环 虽然可以达到目的 但肯定会超时，所以需要转变一下思路，我们可以记录一下每个数字当前的长度，然后后面进行读取并加上自己的长度，这样保证了前后顺序，所以我们用dp[m]=dp[m-1]+1，这样也不会怕中断，比如案例3435762，dp[3]=1,dp[4]=2,dp[3]=1,dp[5]=3...，然后比较一下长度取出最大值即可。

G - Sugoroku Destination

Problem Statement

There are NN cells, cell 1,1, cell 2,…,2,…, cell NN, arranged in a line. Cell ii has an integer Ai (i≤Ai≤N)Ai​ (i≤Ai​≤N) written on it.

For each of s=1,2,…,Ns=1,2,…,N, solve the following problem.

• Initially, place a piece on cell ss. After performing the operation "let xx be the integer written on the cell where the piece is placed, and then move the piece to cell xx" 1010010100 times, output the number of the cell where the piece is placed.

Constraints

• 1≤N≤5×1051≤N≤5×105
• i≤Ai≤N (1≤i≤N)i≤Ai​≤N (1≤i≤N)
• All input values are integers.

Input

The input is given from Standard Input in the following format:

NN
A1A1​ A2A2​ …… ANAN​

Output

Output the answers for s=1,2,…,Ns=1,2,…,N in this order on a single line, separated by spaces.

Sample 1

7
2 4 7 5 5 6 7

5 5 7 5 5 6 7

For s=1s=1, the piece moves as shown in the following figure.

答案

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int>nums(n+1);
    vector<int>ans(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>nums[i];
    }
    for(int i=n;i>0;i--)
    {
        if(i==nums[i])
        {
            ans[i]=nums[i];
        }
        else{
            ans[i]=ans[nums[i]];
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i];
        if(i!=n)
        {
            cout<<" ";
        }
    }
}

题解

由题意可知如果想停止循环则必须为序号与数字相等的时候，而题目要求Ai大于等于序号i，并且小于等于N，所以最后一位一定等于n，所以我们从这个已知条件入手，存储时从后往前存储，如果序号和数字相等那么就存进答案，如果不相等，也就是数字大于序号，因为后面的存储过了，所以直接可以归并到后面了，所以有ans[i]=ans[nums[i]]，然后再遍历输出即可。