本系列记录翀翀😐痛苦的刷题日志，所有题目均来自于牛客网OJ题目，坚持刷题谈起来容易做起来难，希望我可以坚持下去，这里仍然分享一段励志文案：每个人都有梦想，然而有些人把梦想变成了现实，有些人的梦想依旧是梦想，只因为他们为梦想付出的努力程度不一样，他们坚持的时间不一样，最终才有这样的结果。

NC13592-武藏牌牛奶促销

题目链接

https://ac.nowcoder.com/acm/problem/13592

题目描述

武藏牌牛奶为了吸引顾客，推出优惠活动，可以使用x个空的瓶身，或者y个瓶盖，去商店换一瓶全新的武藏牌牛奶。注意，一瓶牛奶包含了瓶身和瓶盖。 现在小萌老师有a个空的瓶身和b个瓶盖，她想喝到尽可能多的牛奶，你知道她到底能喝到多少瓶完整的牛奶吗？多组输入 每组数据第一行包含4个正整数x y a b(1<=x,y,a,b<=100)，意义见题目描述。对于每组数据，输出一行，表示小萌老师最多能喝多少瓶完整的牛奶。如果能喝无数瓶，输出"INF"(不要输出引号)。

测试样例

输入

1 3 1 1
4 3 6 4

输出

INF
4

说明

对于第二组测试样例，小萌老师有6个空的瓶身和4个瓶盖，她用4个瓶身和3个瓶盖换了2瓶牛奶并喝完，此时她就有4个空的瓶身和3个瓶盖。之后她再换2瓶牛奶并喝完，此时只有2个空的瓶身和2个瓶盖，就无法继续兑换了，所以答案是4

解题思路

对于有限次兑换，很简单，就是用空瓶和瓶盖尽可能多兑换就好了，只要注意每次兑换一瓶奶以后空瓶和瓶盖都会加1即可。难点在于无限次兑换的条件，有两个，一种是x=1或者y=1的情况即可，另一种是x=2&&y=2且a+b>2。

解题代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int x, y, a, b;
    while (cin >> x >> y >> a >> b)
    {
        int ans = 0;
        if ((x == 1 || y == 1) || ((x == 2 && y == 2) && (a + b >= 2)))
        {
            cout << "INF" << endl;
            continue;
        }
        else
        {
            //否则有限次兑换
            while (a >= x || b >= y)
            {
                //用x个瓶子兑换
                if (a >= x)
                {
                    int tmp1 = a / x;
                    a = a % x;
                    a += tmp1;
                    b += tmp1;
                    ans += tmp1;
                }
                //用y个瓶盖兑换
                if (b >= y)
                {
                    int tmp2 = b / y;
                    b = b % y;
                    a += tmp2;
                    b += tmp2;
                    ans += tmp2;
                }
            }
            cout << ans << endl;
        }
    }
    system("pause");
    return 0;
}

NC13253-子串

题目链接

https://ac.nowcoder.com/acm/problem/13253

题目描述

给出一个正整数n，我们把1..n在k进制下的表示连起来记为s(n,k)，例如s(16,16)=123456789ABCDEF10, s(5,2)=11011100101。现在对于给定的n和字符串t，我们想知道是否存在一个k(2 ≤ k ≤ 16)，使得t是s(n,k)的子串。第一行一个整数n(1 ≤ n ≤ 50,000)。 第二行一个字符串t(长度 ≤ 1,000,000)。"yes"表示存在满足条件的k，否则输出"no"

测试样例

输入

8
01112

输出

yes

解题思路

我们就是暴力枚举对于不同k进制下的1~n的字符串即可，难点在于要自己手写以下进制转换，同时最后要注意字符串是反的，需要手动翻转。最后再用find函数寻找子串即可。

解题代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    string t, s, tmp;
    cin >> n;
    cin >> t;
    //逐一尝试1~n的k进制串表示
    for (int k = 2; k < 17; k++)
    {
        //记录1~n的k进制串
        s = "";
        for (int i = 1; i <= n; i++)
        {
            //从1~n枚举整数值
            int num = i;
            //临时存储i的k进制串，最后不断拼接成为1~n的k进制串
            tmp = "";
            //使用循环取余的方法模拟转换进制
            while (num)
            {
                int cnt = num % k;
                if (cnt < 10)
                {
                    tmp += cnt + '0';
                }
                else
                {
                    //大于9的时候用ABCDE等表示
                    tmp += 'A' + cnt - 10;
                }
                num /= k;
            }
            //最后得到的是反的，要翻转一下字符串
            reverse(tmp.begin(), tmp.end());
            s += tmp;
        }
        //find()函数寻找子串在母串中出现的第一次位置，没有则返还-1
        if (s.find(t) != -1)
        {
            cout << "yes" << endl;
            system("pause");
            return 0;
        }
    }
    cout << "no" << endl;
    system("pause");
    return 0;
}