【题解】小米 OJ 板刷发财计划

突然发现小米有 OJ！

然后发现居然刷题都能得奖品！而且都是水题

就开始板刷（一晚上 20 道题）

刷了 200 多个 OJ 币

然后发现：

也就是说我能兑换的都无库存

不能兑换的我不知道它有没有库存

算了我明天继续板刷，刷到 400 分看 T 恤有没有要是还没有我就打 12315 投诉

不过既然刷了就放出来吧

1. A + B

。。。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    long long a, b;
    scanf("%lld%lld", &a, &b), printf("%lld\n", a + b);
    return 0;
}

2. 找出单独出现的数字

。。。

#include <bits/stdc++.h>

using namespace std;

bool cnt[256];

int main(int argc, char const* argv[])
{
    int a;
    while (~scanf("%d", &a)) cnt[a] ^= 1;
    for (int i = 0; i < 256; i += 1) if (cnt[i]) printf("%d\n", i), exit(0);
    return 0;
}

3. 大数相减

。。。

#include <bits/stdc++.h>

#define NS (10000)

using namespace std;

char str[NS];

struct bigInt
{
    int d[NS], n;
    int& operator [] (const int a) {return d[a];}
    bool input()
    {
        char c; n = 0;
        while (c = getchar(), !isdigit(c));
        while (isdigit(c)) str[n++] = c, c = getchar();
        reverse(str, str + n), n--;
        for (int i = 0; i <= n; i += 1) d[i] = str[i] - '0';
    }
    void print()
    {
        for (int i = n; i >= 0; i -= 1) putchar(d[i] + '0');
        putchar(10);
    }
    void operator -= (bigInt &oth)
    {
        for (int i = 0; i <= oth.n; i += 1) d[i] -= oth[i];
        for (int i = 0; i <= n; i += 1)
            while (d[i] < 0) d[i] += 10, d[i + 1]--;
        while (!d[n]) n--;
    }
} A, B;

int main(int argc, char const* argv[])
{
    A.input(), B.input(), A -= B, A.print();
    return 0;
}

4. 最长连续数列

说好的 $O(n)$呢？

实际上是对 Java/Python 说的吧

（但是 Java 排序也能过。。。）

#include <bits/stdc++.h>

#define NS (500005)

using namespace std;

int n, l, A[NS];

char buff[NS << 1];

void input()
{
    scanf("%s", buff), l = strlen(buff);
    int i = 0;
    while (i < l)
    {
        while (!isdigit(buff[i]) && i < l) i++;
        if (i == l) return;
        n++;
        while (isdigit(buff[i])) A[n] = A[n] * 10 + buff[i++] - '0';
    }
}

int main(int argc, char const* argv[])
{
    input(), sort(A + 1, A + 1 + n);
    int ans = 1, cnt = 1;
    for (int i = 2; i <= n; i += 1)
        if (A[i] == A[i - 1] + 1) cnt++;
        else ans = max(ans, cnt), cnt = 1;
    printf("%d\n", max(ans, cnt));
    return 0;
}

5. 找出旋转有序数列的中间值

就搞不懂了为什么一定要用这么制杖的读入方式

而且和旋转有半毛钱关系吗？

#include <bits/stdc++.h>

#define NS (500005)

using namespace std;

int n, l, A[NS];

char buff[NS << 1];

void input()
{
    scanf("%s", buff), l = strlen(buff);
    int i = 0; bool flag;
    while (i < l)
    {
        flag = 0;
        while (!isdigit(buff[i]) && i < l)
        {
            if (buff[i] == '-') flag = 1;
            i++;
        }
        if (i == l) return;
        n++;
        while (isdigit(buff[i])) A[n] = A[n] * 10 + buff[i++] - '0';
        if (flag) A[n] = -A[n];
    }
}

int main(int argc, char const* argv[])
{
    input(), nth_element(A + 1, A + ((n + 1) >> 1), A + 1 + n);
    printf("%d\n", A[(n + 1) >> 1]);
    return 0;
}

6. 交叉队列

又不告诉数据范围。。。

实际上 $O(n ^ 2)$Dp 就行了

#include <bits/stdc++.h>

#define NS (1000)

using namespace std;

char buff[NS], s1[NS], s2[NS], s3[NS];

int l1, l2, l3;

void input(char (&a)[NS], int &l)
{
    char c; l = 0;
    while (c = getchar(), !isalpha(c));
    while (isalpha(c)) a[l++] = c, c = getchar();
}

int f[NS][NS];

bool Dfs(int a, int b)
{
    if (f[a][b]) return f[a][b] - 1;
    f[a][b] = 1;
    if (a > 0 && s3[a + b - 1] == s1[a - 1] && Dfs(a - 1, b)) f[a][b] = 2;
    else if (b > 0 && s3[a + b - 1] == s2[b - 1] && Dfs(a, b - 1)) f[a][b] = 2;
    return f[a][b] - 1;
}

int main(int argc, char const* argv[])
{
    input(s1, l1), input(s2, l2), input(s3, l3);
    if (l1 + l2 != l3) puts("false"), exit(0);
    f[0][0] = 2;
    if (Dfs(l1, l2)) puts("true");
    else puts("false");
    return 0;
}

7. 第一个缺失正数

。。。

#include <bits/stdc++.h>

#define NS (500000)

using namespace std;

int n, l, A[NS];

char buff[NS];

void input()
{
    scanf("%s", buff), l = strlen(buff);
    int i = 0; bool flag;
    while (i < l)
    {
        flag = 0;
        while (!isdigit(buff[i]) && i < l)
        {
            if (buff[i] == '-') flag = 1;
            i++;
        }
        if (i == l) return;
        n++;
        while (isdigit(buff[i])) A[n] = A[n] * 10 + buff[i++] - '0';
        if (flag) A[n] = -A[n];
    }
}

int main(int argc, char const* argv[])
{
    input(), sort(A + 1, A + 1 + n);
    int ans = 1;
    for (int i = 1; i <= n; i += 1) if (A[i] == ans) ans++;
    printf("%d\n", ans);
    return 0;
}

8. 最少交换次数

老套路树状数组模拟

只是没有数据范围

#include <bits/stdc++.h>

#define NS (500000)
#define lowbit(a) ((a) & (-(a)))

using namespace std;

typedef long long LL;

int n, l, A[NS], h[NS], hs, at[NS];

char buff[NS];

void input()
{
    scanf("%s", buff), l = strlen(buff);
    int i = 0; bool flag;
    while (i < l)
    {
        flag = 0;
        while (!isdigit(buff[i]) && i < l)
        {
            if (buff[i] == '-') flag = 1;
            i++;
        }
        if (i == l) return;
        n++;
        while (isdigit(buff[i])) A[n] = A[n] * 10 + buff[i++] - '0';
        if (flag) A[n] = -A[n];
    }
}

int t[NS];

void add(int x, int d)
{
    while (x <= n) t[x] += d, x += lowbit(x);
}

int sum(int x)
{
    int res = 0;
    while (x) res += t[x], x -= lowbit(x);
    return res;
}

void preWork()
{
    memmove(h + 1, A + 1, sizeof(int) * n), sort(h + 1, h + 1 + n);
    h[0] = INT_MIN;
    for (int i = 1; i <= n; i += 1)
        if (h[i] != h[i - 1]) h[++hs] = h[i];
    for (int i = 1; i <= n; i += 1)
    {
        A[i] = lower_bound(h + 1, h + 1 + hs, A[i]) - h;
        at[A[i]] = i, add(i, A[i] - i), add(i + 1, i - A[i]);
    }
}

int main(int argc, char const* argv[])
{
    input(), preWork();
    LL ans = 0;
    for (int i = 1; i <= n; i += 1)
    {
        ans += abs(sum(at[i]));
        add(1, -1), add(at[i], 1);
    }
    printf("%lld\n", ans);
    return 0;
}

9. 移除 K 位得到最小值

贪心，还挺有意思的

如果当前某一位比它后面一位大就删除它

当然被删除的这一位越靠前越好

#include <bits/stdc++.h>

using namespace std;

char str[20];

int l, k;

void scan()
{
    int i = 0;
    while (i < l - 1 && str[i] <= str[i + 1]) i++;
    for (int j = i; j < l - 1; j += 1) str[j] = str[j + 1];
    l--, str[l] = 0;
}

int main(int argc, char const* argv[])
{
    scanf("%s%d", str, &k), l = strlen(str);
    for (int i = 1; i <= k; i += 1) scan();
    int i = 0;
    while (str[i] == '0') i++;
    if (i == l) puts("0");
    else
    {
        while (i < l) putchar(str[i++]);
        putchar(10);
    }
    return 0;
}

10. 爬楼梯

斐波那契甚至不取模，都懒得滚动了

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n;

LL f[1000];

int main(int argc, char const* argv[])
{
    IN(n), f[0] = 1, f[1] = 1;
    for (int i = 1; i <= n; i += 1) f[i] = f[i - 1] + f[i - 2];
    printf("%lld\n", f[n]);
    return 0;
}

11. 构建短字符串

亮点在样例输入中

a b
aa ab
aa aab
uak areuok

。。。

#include <bits/stdc++.h>

#define NS (500000)

using namespace std;

char s1[NS], s2[NS];

int l1, l2, cnt[128];

int main(int argc, char const* argv[])
{
    scanf("%s%s", s1, s2), l1 = strlen(s1), l2 = strlen(s2);
    for (int i = 0; i < l2; i += 1) cnt[s2[i]]++;
    for (int i = 0; i < l1; i += 1)
        if (!cnt[s1[i]]) puts("false"), exit(0);
        else cnt[s1[i]]--;
    puts("true");
    return 0;
}

12. 找出可能的合的组合

Dp 真好玩

#include <bits/stdc++.h>

#define NS (500000)

using namespace std;

int n, l, A[NS], m;

char buff[NS << 1];

void input()
{
    scanf("%s", buff), l = strlen(buff);
    int i = 0; bool flag;
    while (i < l)
    {
        flag = 0;
        while (!isdigit(buff[i]) && i < l)
        {
            if (buff[i] == '-') flag = 1;
            i++;
        }
        if (i == l) return;
        n++;
        while (isdigit(buff[i])) A[n] = A[n] * 10 + buff[i++] - '0';
        if (flag) A[n] = -A[n];
    }
}

int f[NS];

int Dfs(int a)
{
    if (f[a] != -1) return f[a];
    f[a] = 0;
    for (int i = 1; i <= n; i += 1)
        if (a >= A[i]) f[a] += Dfs(a - A[i]);
    return f[a];
}

int main(int argc, char const* argv[])
{
    input(), scanf("%d", &m);
    memset(f, -1, sizeof(f)), f[0] = 1;
    printf("%d\n", Dfs(m));
    return 0;
}

13. 出现频率最高的前 K 个元素

。。。

#include <bits/stdc++.h>

#define NS (500000)
#define FIR first
#define SEC second

using namespace std;

typedef pair<int ,int> PII;

int n, l, A[NS];

char buff[NS << 1];

void input()
{
    scanf("%s", buff), l = strlen(buff);
    int i = 0; bool flag;
    while (i < l)
    {
        flag = 0;
        while (!isdigit(buff[i]) && i < l)
        {
            if (buff[i] == '-') flag = 1;
            i++;
        }
        if (i == l) return;
        n++;
        while (isdigit(buff[i])) A[n] = A[n] * 10 + buff[i++] - '0';
        if (flag) A[n] = -A[n];
    }
}

int cnt;

PII P[NS];

bool cmp(PII a, PII b)
{
    if (a.FIR == b.FIR) return a.SEC < b.SEC;
    return a.FIR > b.FIR;
}

int main(int argc, char const* argv[])
{
    input(), sort(A + 1, A + 1 + n), A[0] = INT_MIN;
    for (int i = 1; i <= n; i += 1)
        if (A[i] != A[i - 1]) P[++cnt].FIR = 1, P[cnt].SEC = A[i];
        else P[cnt].FIR++;
    int k; scanf("%d", &k);
    sort(P + 1, P + 1 + cnt, cmp), printf("%d", P[1].SEC);
    for (int i = 2; i <= k; i += 1) printf(",%d", P[i].SEC);
    putchar(10);
    return 0;
}

14. 在一个有序的经过旋转的数组里查找一个数

。。。

#include <bits/stdc++.h>

#define NS (500005)

using namespace std;

int n, l, A[NS], q;

char buff[NS << 1];

void input()
{
    scanf("%s", buff), l = strlen(buff);
    int i = 0; bool flag;
    while (i < l)
    {
        flag = 0;
        while (!isdigit(buff[i]) && i < l)
        {
            if (buff[i] == '-') flag = 1;
            i++;
        }
        if (i == l) return;
        n++;
        while (isdigit(buff[i])) A[n] = A[n] * 10 + buff[i++] - '0';
        if (flag) A[n] = -A[n];
    }
}

int main(int argc, char const* argv[])
{
    input(), scanf("%d", &q);
    for (int i = 1; i <= n; i += 1)
        if (A[i] == q) printf("%d\n", i - 1), exit(0);
    puts("-1");
    return 0;
}

15. 和为零的三元组

map 瞎搞一通

#include <bits/stdc++.h>

#define NS (500005)

using namespace std;

int n, l, A[NS];

char buff[NS << 1];

void input()
{
    scanf("%s", buff), l = strlen(buff);
    int i = 0; bool flag;
    while (i < l)
    {
        flag = 0;
        while (!isdigit(buff[i]) && i < l)
        {
            if (buff[i] == '-') flag = 1;
            i++;
        }
        if (i == l) return;
        n++;
        while (isdigit(buff[i])) A[n] = A[n] * 10 + buff[i++] - '0';
        if (flag) A[n] = -A[n];
    }
}

typedef pair<int, int> PII;
typedef pair<int, PII> PIP;

map<int, int> mp;
map<PIP, bool> book;

int main(int argc, char const* argv[])
{
    input(), sort(A + 1, A + 1 + n);
    for (int i = 1; i <= n; i += 1) mp[-A[i]] = i;
    int ans = 0;
    for (int i = 1; i <= n; i += 1)
        for (int j = 1; j <= n; j += 1)
            if (i < j && mp[A[i] + A[j]] && j < mp[A[i] + A[j]])
            {
                if (book[PIP(A[i], PII(A[j], A[mp[A[i] + A[j]]]))])
                    continue;
                ans++;
                book[PIP(A[i], PII(A[j], A[mp[A[i] + A[j]]]))] = 1;
            }
    printf("%d\n", ans);
    return 0;
}

16. 四则运算

。。。后缀表达式

直接贴的以前的代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>

int ints[10000];
int intt;//ints 的 top 
char chas[10000];
int chat;//chas 的 top 
int i=0, ii=1;
char c;
char get[10000];//输入的中缀表达式 
char get2[10000];//计算得出的后缀表达式 

void intpush(int x)//整型栈压栈 
{
    intt++; ints[intt]=x;
}
void chapush(char x)//字符型栈压栈 
{
    chat++; chas[chat]=x;
}
int intpop()//整型栈弹出 
{
    intt--; return ints[intt+1];
}
char chapop()//字符型栈弹出 
{
    chat--; return chas[chat+1];
}
void intadd(int x)//整型栈栈顶元素加入新的个位数字 
{
    ints[intt]*=10; ints[intt]+=x;
}

int find()//get2 加入操作符 
{
    c=chapop();
    get2[ii]=' ';
    get2[ii+1]=c;
    ii+=2;
    if(chat==0) return 0;
    return 1;
}

int main()
{
    intt=0; chat=0;
    fgets(get, 1000000, stdin);
    int lengets=strlen(get);
    for(i=0;i<=lengets-1;i++)//逐个读取输入的中缀表达式 
    {
        if (isdigit(get[i]))//当 get[i] 为数字时 
        {
            get2[ii]=get[i];
            ii++;
        }
        else
        {
            if(get[i]=='(')chapush('(');
            if(get[i]=='^')chapush('^');
            if(get[i]==')')
            {
                c=chapop();
                while(c!='(')
                {
                    get2[ii]=' ';
                    get2[ii+1]=c;
                    ii+=2;
                    c=chapop();
                }
            }
            if(get[i]=='+')
            {
                while(chas[chat]=='+'||chas[chat]=='-'||chas[chat]=='*'||chas[chat]=='/'||chas[chat]=='^')
                {
                    if(find()==0)break;
                }
                chapush('+');
            }
            if(get[i]=='-')
            {
                while(chas[chat]=='+'||chas[chat]=='-'||chas[chat]=='*'||chas[chat]=='/'||chas[chat]=='^')
                {
                    if(find()==0)break;
                }
                chapush('-');
            }
            if(get[i]=='*')
            {
                while(chas[chat]=='*'||chas[chat]=='/'||chas[chat]=='^')
                {
                    if(find()==0)break;
                }
                chapush('*');
            }
            if(get[i]=='/')
            {
                while(chas[chat]=='*'||chas[chat]=='/'||chas[chat]=='^')
                {
                    if(find()==0)break;
                }
                chapush('/');
            }
            get2[ii]=' ';
            ii++;
        }

    }
    while(chat>0)//输出栈内剩余的操作符 
    {
        int c=chapop();
        get2[ii]=' ';
        get2[ii+1]=c;
        ii+=2;
    }
    get2[ii]='@';//加入结束符 
    i=1;
    while(get2[i]!='@')//当看到结束符停止计算 
    {
        if(get2[i]=='+'||get2[i]=='-'||get2[i]=='*'||get2[i]=='/'||get2[i]=='^')
        {
            int a=intpop();int b=intpop();int c;
            if(get2[i]=='+') c=a+b;
            if(get2[i]=='-') c=b-a;
            if(get2[i]=='*') c=a*b;
            if(get2[i]=='/')
            {
                if (!a)puts("err"),exit(0);
                c=b/a;
            }
            if(get2[i]=='^') c=pow(b,a);
            intpush(c);
        }
        else
        {
            if(get2[i]!=' ')
            {
                intpush(get2[i]-48);
                ii=1;
                while(get2[i+ii]!=' ')
                {
                    intadd(get2[i+ii]-48);
                    ii++;
                }
                i+=ii-1;
            }
        }
        i++;
    }
    printf("%d\n",ints[1]);
    return 0;
}

17. 小写数字转大写数字

这题就是恶心人的，真没意思

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

char *QAQ[] = {"", "拾", "佰", "仟", "万", "拾", "佰", "仟", "亿", "拾", "佰"};
char *OvO[] = {"零", "壹", "贰", "叁", "肆", "伍", "陆", "柒", "捌", "玖"};

LL n;

bool zero, vis;

void Orz(LL a, int b)
{
    if (a >= 10) Orz(a / 10, b + 1);
    if (b % 4 == 3) zero = 0, vis = 0;
    if (a % 10 == 0)
    {
        zero = 1;
        if (b % 4 == 0 && vis) printf("%s", QAQ[b]);
        return;
    }
    if (zero) printf("零"), zero = 0;
    printf("%s%s", OvO[a % 10], QAQ[b]), zero = 0, vis = 1;
}

int main(int argc, char const* argv[])
{
    IN(n);
    if (!n) puts("零元整"), exit(0);
    Orz(n, 0), puts("元整");
    return 0;
}

18. 帮小学生排队

如果从高到低排序，每次把当前的插入，那低的一定不会影响高的 “前面比他高的人数”

相同高度的 “前面比他高的人数” 小的站前面

$O(n ^ 2)$的

#include <bits/stdc++.h>

#define NS (5000)

#define FIR first
#define SEC second

using namespace std;

typedef pair<int, int> PII;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

bool cmp(PII a, PII b)
{
    if (a.FIR == b.FIR) return a.SEC < b.SEC;
    return a.FIR > b.FIR;
}

int n, id[NS];

PII P[NS];

void insert(int x, int d)
{
    memmove(id + x + 1, id + x, sizeof(int) * (n - x));
    id[x] = d;
}

int main(int argc, char const* argv[])
{
    IN(n);
    for (int i = 1; i <= n; i += 1) IN(P[i].FIR), IN(P[i].SEC);
    sort(P + 1, P + 1 + n, cmp);
    for (int i = 1; i <= n; i += 1) insert(P[i].SEC, i);
    for (int i = 0; i < n; i += 1)
        printf("%d %d ", P[id[i]].FIR, P[id[i]].SEC);
    putchar(10);
    return 0;
}

19. 大数的加法运算与大小判断

python 真好用

（第一次写 python）

def solution(line):
    if '<' in line:
        a, b = line.strip().split('<')
        if int(a) < int(b):
            return 'Y'
        else:
            return 'N'
    if '>' in line:
        a, b = line.strip().split('>')
        if int(a) > int(b):
            return 'Y'
        else:
            return 'N'
    a, b = line.strip().split('+')
    return str(int(a) + int(b))

20. 有多少个等差数列？

枚举序列结束为止与公差，Dp 即可

#include <bits/stdc++.h>

#define NS (205)

using namespace std;

int n, l, A[NS];

char buff[NS << 1];

void input()
{
    fgets(buff, NS, stdin), l = strlen(buff);
    int i = 0; bool flag;
    while (i < l)
    {
        flag = 0;
        while (!isdigit(buff[i]) && i < l)
        {
            if (buff[i] == '-') flag = 1;
            i++;
        }
        if (i == l) return;
        n++;
        while (isdigit(buff[i])) A[n] = A[n] * 10 + buff[i++] - '0';
        if (flag) A[n] = -A[n];
    }
}

int f[NS][405], ans;

int main(int argc, char const* argv[])
{
    input();
    for (int i = 1; i <= n; i += 1)
        for (int j = 1; j < i; j += 1)
            f[i][A[i] - A[j] + 200]++;
    for (int i = 1; i <= n; i += 1)
    {
        for (int j = 1; j < i; j += 1)
            f[i][A[i] - A[j] + 200] += f[j][A[i] - A[j] + 200];
        for (int j = 0; j <= 400; j += 1) ans += f[i][j];
    }
    printf("%d\n", ans);
    return 0;
}

21. 按序组合成最大的数

$n ^ 3$ DP

怕爆精度直接写 (chao) 的 python

def solution(line):
    buff = line.split(' ')
    a = buff[0].split(',')
    b = buff[1].split(',')
    k = int(buff[2])
    f = []
    l1 = len(a)
    l2 = len(b)
    for i in range(l1):
        a[i] = int(a[i])
    for i in range(l2):
        b[i] = int(b[i])
    for i in range(l1 + 1):
        f.append([])
        for j in range(l2 + 1):
            f[i].append([])
            for k in range(k + 1):
                f[i][j].append(0)
    for i in range(1, l1 + 1):
        f[i][0][1] = a[i - 1]
    for i in range(1, l2 + 1):
        f[0][i][1] = b[i - 1]
    for i in range(l1 + 1):
        for j in range(l2 + 1):
            for k in range(1, k + 1):
                if i > 0:
                    f[i][j][k] = max(f[i][j][k], max(f[i - 1][j][k], f[i - 1][j][k - 1] * 10 + a[i - 1]))
                if j > 0:
                    f[i][j][k] = max(f[i][j][k], max(f[i][j - 1][k], f[i][j - 1][k - 1] * 10 + b[j - 1]))
    return f[l1][l2][k]

22. 找到第 N 个数字

等差数列，解下方程就行了

（题目说的 20 位是不存在的，用 long long 就行了）

#include <bits/stdc++.h>

typedef long long LL;

using namespace std;

LL n;

char s[] = "1234567898765432";

int main(int argc, char const* argv[])
{
    scanf("%lld", &n);
    LL x = ceil((sqrt((double)1 + (n << 3)) - 1) / 2) - 1;
    n -= (x * x + x) / 2 + 1;
    putchar(s[n % 16]);
    return 0;
}

23. 找到第 N 个数字 II

这次 $n$比较小，懒得二分直接 $\sqrt n$找

然后找所在位置就行了

#include <bits/stdc++.h>

typedef long long LL;

using namespace std;

LL n, l = 1, k = 1;

int main(int argc, char const* argv[])
{
    scanf("%lld", &n);
    int i = 1, d = 1, p = 10;
    while ("orz litble")
    {
        if (n <= l) break;
        n -= l;
        if ((++i) % p == 0) p *= 10, d++;
        l += d;
    }
    l = 1;
    while ("Orz litble")
    {
        LL p = l * (k * 10 - k);
        if (n <= p)
        {
            LL x = ceil((double)n / l) + k - 1;
            n = ceil((double)n / l) * l - n;
            while (n) x /= 10, n--;
            printf("%lld\n", x % 10);
            break;
        }
        n -= p, l++, k *= 10;
    }
    return 0;
}

24. 海盗分赃

数据这么大咋整。。。

于是就写了模拟退火，居然 AC 了=。=

但是那些写背包的也 AC 了，数据太水了吧

#include <bits/stdc++.h>

#define NS (105)
#define Rand() ((double)rand() / RAND_MAX)
#define ABS(a) ((a) < 0 ? (-(a)) : a)

using namespace std;

int n, l, A[NS];

char buff[NS << 1];

void input()
{
    scanf("%s", buff), l = strlen(buff);
    int i = 0; bool flag;
    while (i < l)
    {
        flag = 0;
        while (!isdigit(buff[i]) && i < l)
        {
            if (buff[i] == '-') flag = 1;
            i++;
        }
        if (i == l) return;
        n++;
        while (isdigit(buff[i])) A[n] = A[n] * 10 + buff[i++] - '0';
        if (flag) A[n] = -A[n];
    }
}

int sum, f, vis[NS], ans = INT_MAX;

int main(int argc, char const* argv[])
{
    srand(19260817), input();
    for (int i = 1; i <= n; i += 1) sum += A[i];
    if (sum & 1) puts("false"), exit(0);
    f = sum, sum >>= 1, memset(vis + 1, -1, sizeof(int) * n);
    double T = 10000;
    while (T > 1e-6)
    {
        for (int C = 1; C <= 50; C += 1)
        {
            int a = rand() % n + 1;
            int dt = ABS(f - sum) - ABS(f + vis[a] * A[a] - sum);
            if (dt > 0 || exp((double)dt / T) > Rand())
                f += vis[a] * A[a], vis[a] *= -1;
            ans = min(ans, ABS(f - sum));
        }
        T *= 0.98;
    }
    if (!ans) puts("true");
    else puts("false");
    return 0;
}

28. 组长偏头痛

二分答案

#include <bits/stdc++.h>

#define NS (100005)

using namespace std;

int k, n, l, A[NS];

char buff[NS << 1];

void input()
{
    scanf("%s", buff), l = strlen(buff);
    int i = 0; bool flag;
    while (i < l)
    {
        flag = 0;
        while (!isdigit(buff[i]) && i < l)
        {
            if (buff[i] == '-') flag = 1;
            i++;
        }
        if (i == l) return;
        n++;
        while (isdigit(buff[i])) A[n] = A[n] * 10 + buff[i++] - '0';
        if (flag) A[n] = -A[n];
    }
}

int main(int argc, char const* argv[])
{
    scanf("%d", &k), input();
    int l = 0, r = 0, mid;
    for (int i = 1; i <= n; i += 1) l = max(l, A[i]), r += A[i];
    while (l < r)
    {
        mid = (l + r) >> 1;
        bool flag = 1;
        for (int i = 1, rem = mid, x = k - 1; i <= n; i += 1)
        {
            if (A[i] > rem)
            {
                if (!x) { flag = 0; break; }
                x--, rem = mid;
            }
            rem -= A[i];
        }
        if (flag) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", l);
    return 0;
}

32. 判断是否为连乘数字串

暴搜

#include <bits/stdc++.h>

#define NS (105)

using namespace std;

typedef long long LL;

int n;

char s[NS];

bool Dfs(int a, LL x, LL y, LL z, int c)
{
    if (a > n) return (c >= 3 && !z);
    z = z * 10 + s[a] - '0';
    if (z > 1e9) return 0;
    bool res = 0;
    if (z == x * y || x == -1) res |= Dfs(a + 1, y, z, 0, c + 1);
    return (res | Dfs(a + 1, x, y, z, c));
}

int main(int argc, char const* argv[])
{
    scanf("%s", s + 1), n = strlen(s + 1);
    puts(Dfs(1, -1, -1, 0, 0) ? "true" : "false");
    return 0;
}

（未完待续）