有的时候应该坚持自己的想法

即使并非最优

首先为南京大屠杀默哀

先留个坑….

懵逼的 题目

传送至 Luogu

扯淡的 题解

D1T1

我终于证明了我的方法是对的…

设一个能达到的数为maxz
而且ans = maxz - 1
那么这个maxz有什么性质呢…
首先maxz == ax + by(他本身必须能被凑出, 要不然他自己就是答案了)

然后观察一个能凑出数(以下称为合法的数, 注意这里的合法是指能够通过a, b凑出) 如何凑出比他小1的数: 减掉几个a, 加上几个b; 或者加上几个a, 减掉几个b;
而这”几个”是怎么得出的呢?
显然是这个样的…
ax1 - by1 = 1: 减去x1a, 加上y1b, 可以让一个合法的数z变为z - 1;
bx2 - ay2 = 1: 减去x2b, 加上x2a, 可以让一个合法的数z变为z - 1;

所以如果我们能求出x1, y1, x2, y2就能让所有的合法的数z变成z - 1辣…………吗?
显然如果一个数z = ax + by, 如果他的a的个数x小于x1, 不能通过减掉几个a, 再加上几个b来让z变成z - 1, 并且他的b的个数y也小于x2, 不能通过减掉几个b, 再加上几个a来让z变成z - 1
他就是maxz, 为什么呢, 因为maxz - 1不能凑出嘛
但是如何保证maxz最大呢?
显然就是让maxz = ax + by, x = x1 - 1, y = x2 - 1就行了….因为一旦又加了一个x或者y, 就都可以让maxz - 1被凑出: 因为可以减掉x1a或者减掉x2b
证毕….?

所以算法就是求ax1 - by1 = 1bx1 - ay1 = 1x1, x2, 答案就是x1 * a + x2 * b - 1

不得不说用exgcd做出D1T1对我意义挺大的…这表明了…我是对的! 我在考场上托腮思考的1.5h没有浪费! 我还是那个宽嫂! 那个不一般的宽嫂!

D1T2

SB模拟…注意几个细节就好了…
考场上输出”ERR”之后没有把这个程序剩下的部分都读完…导致下一次循环从上次”ERR”的地方开始读的…我说怎么当时单个的测样例没问题…一旦多组数据就GG…看了好几遍初始化原来是这个问题….
还有就是x < y的情况比较蛋疼…多注意一下…不要把unused加多了…注意unused一旦不为0就没必要操作了….

D1T3

未完待续…

沙茶的 代码

D1T1

/*
    ax + by = 1
    x0, y0 -> x', y"
    a * (x' - 1) + b * (y" - 1)
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#define pll pair<LL, LL>
#define LL long long
using namespace std;

LL solve(LL, LL, LL);
LL exgcd(LL, LL, LL&, LL&);
int main()
{
    LL a, b;
    scanf("%lld%lld", &a, &b);
    LL maxb = solve(a, b, 1);
    LL maxa = solve(b, a, 1);
    printf("%lld", (a * (maxb - 1) + b * (maxa - 1) - 1));
    return 0;
}
LL solve(LL a, LL b, LL c)
{
    LL x, y;
    LL gcd = exgcd(a, b, x, y);
    y = -y;
    LL tb = b / gcd;
    while (x < 0)
    x += tb;
    return x;
}
LL exgcd(LL a, LL b, LL& x, LL& y)
{
    if (!b)
    {
        x = 1;
        y = 0;
        return a;
    }
    else 
    {
        LL re = exgcd(b, a % b, y, x);
        y -= a / b * x;
        return re;
    }
}

/*
3 5 
7
*/

D1T2

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <stack>
#define MAXN (100 + 5)
#define MAXT (10 + 5)
#define MAXC (26 + 5)

#define PUTSERR cout << "ERR\n"

#define CTI(a) ((a) - '0')
#define CTC(a) ((a) - 'a')

// #define GG 
using namespace std;

bool used[MAXC];

void init();
void solve();
int STI(string&, int);
void qp(int, int);
int main()
{
#ifdef GG
    freopen("in.in", "r", stdin);
#endif
    int t;
    cin >> t;
    while (t--)
    {
        init();
        solve();
    }
    return 0;
}
void init()
{
    memset(used, false, sizeof(used));
}
void solve()
{
    int len;
    string fzd;
    int inw;
    cin >> len >> fzd;
    if (fzd[2] == '1')
        inw = 0;
    else
        inw = STI(fzd, 4);
    int totf = 0;
    int tw = 0;
    int noww = 0;
    int unused = 0;
    string dq;
    stack <char> s;
    stack <int> ins;
    for (int i = 1; i <= len; i++)
    {
        cin >> dq;
        if (dq == "E")
        {
            --totf;
            if (unused > 0)
                --unused;
            if (totf < 0)
            {
                qp(i, len);
                PUTSERR;
                return ;
            }
            if (!s.empty())
            {
                used[CTC(s.top())] = false;
                s.pop();
            }
            if (!unused && !ins.empty())
            {
                noww -= ins.top();
                ins.pop();
            }
        }
        else if (dq == "F")
        {    
            ++totf;
            if (unused)
                ++unused;
            cin >> dq;
            if (used[CTC(dq[0])])
            {
                qp(i, len);
                PUTSERR;
                return ;
            }
            s.push(dq[0]);
            used[CTC(dq[0])] = true;
            string dqxs, dqys;
            cin >> dqxs >> dqys;
            int dqx = STI(dqxs, 0);
            int dqy = STI(dqys, 0);
            if (dqxs == "n" && dqys != "n" && !unused)
            {
                ++unused;
            }
            else if (dqxs != "n" && dqys == "n" && !unused)
            {
                ++noww;
                ins.push(1);
                tw = max(tw, noww);
            }
            else if (dqy < dqx && !unused)// 就是这个地方...n被转成了数字...结果导致unused被多加了几遍...
            {
                ++unused;
            }
            else if (dqy > dqx && !unused)
            {
                ins.push(0);
            }
        }
    }
    if (totf)
    {
        PUTSERR;
        return ;
    }
    if (tw == inw)
    {
        cout << "Yes\n";
    }
    else
    {
        cout << "No\n";
    }
}
int STI(string& x, int be)
{
    int re = 0;
    int xn = x.length();
    for (int i = be; i < xn; i++)
    {
        if (x[i] > '9' || x[i] < '0')
            break;
        re = (re << 1) + (re << 3);
        re += CTI(x[i]);
    }
    return re;
}
void qp(int from, int to)
{
    char a[1000];
    for (int i = from; i <= to; i++)
    {
        cin.getline(a, 1000, '\n');
    }
}

/*
1
4 O(n^2)
F x 5 n
F y 10 n
E
E
*/

By 一个中二病晚期 Cansult