8.21DAY5

Posted on 2020-08-21 Edited on 2022-09-19 In qbxt一次

小鱼

题目描述

大鱼生活在一座海底的宫殿，宫殿里的交易货币只有\(2\)元，\(5\)元，\(10\)元，\(20\)元，50元，\(100\)元六种纸币。现在大鱼想买一根恰好\(n\)元的拐杖，不能找零，那么大鱼至少要带多少张纸币去呢？输入格式

一行一个整数 \(n\)。

输出格式

一行一个整数表示答案。

样例数据

input

output

1
2

样例解释

带\(2\)张\(2\)元，一张\(5\)元。

数据规模与约定

对于 \(30\%\) 的数据，\(n \leq 100\)。

对于 \(60\%\) 的数据，\(n \leq 10^9\)。

对于 \(100\%\) 的数据，\(4 \leq n \leq 10^{18}\)。

时间限制：\(1 \text{s}\)

空间限制：\(512 \text{MB}\)

模拟就完事了

那么多人都出锅了，他们好菜

#include <bits/stdc++.h>
#define int long long
// #define debug
using namespace std;
//东方之珠 整夜未眠！

inline int thestars()
{
    int n, liu, wu, si, san, er, yi, pd(0); 
    cin >> n;
    if (n & 1) n -= 5, pd = 1;
    liu = n / 100; n %= 100;
    wu = n / 50, n %= 50;
    si = n / 20, n %= 20;
    san = n / 10, n %= 10;
    er = n / 5; n = n - er * 5; if (n%2 != 0) n += er * 5; er = 0;
    yi = n / 2, n %= 2;
    if (pd) ++ er;
#ifdef debug
cout << "100---->" << liu << '\n';
cout << "50---->" << wu << '\n';
cout << "20---->" << si << '\n';
cout << "10---->" << san << '\n';
cout << "5---->" << er << '\n';
cout << "2---->" << yi << '\n';
#endif
    cout << liu + wu + si + san + er + yi << '\n';
    fclose (stdin), fclose (stdout);
    return 0;
}

int youngore = thestars();

signed main() {;}
/*
2147483647214748364
100---->21474836472147483
50---->1
20---->0
10---->1
5---->0
2---->2
1---->0
21474836472147487
*/

小黑

题目描述

小黑初始有一个\(1\)到\(n\)的排列构成的序列，之后有\(m\)次修改，每次可以在任意位置删掉一个元素或者插入一个之前被删掉了的元素（即保证序列中元素各不相同）。

然后有\(Q\)次查询，每次给出一个序列，问这个序列在这\(m\)次修改的结果（不包括初始序列）中，是其中多少个的子串。

输入格式

第\(1\)行\(3\)个整数 \(n,m,Q\)。

接下来\(1\)行\(n\)个整数，表示初始的\(1\)到\(n\)排列。

接下来\(m\)行，每行形式为\(1,x\)或\(2,x,y\)，分别表示删除数\(x\)和在数\(x\)后面插入数\(y\)，保证操作合法，插入操作中\(x=0\)表示在序列开头插入，操作过程中序列可能为空。

接下来\(Q\)行，每行第\(1\)个正整数\(k\)，表示查询序列的长度，接下来\(k\)个数，表示查询序列，保证序列的元素在\(1\)到\(n\)中且各不相同。\(k \geq 2\)。

输出格式

\(Q\)行，每行一个整数表示答案。

样例数据

input

output

1
2
3

3
1

样例解释

序列的变化如下：

\(3,1,2,4 \rightarrow 3,2,4 \rightarrow 3,4 \rightarrow 1,3,4 \rightarrow 1,2,3,4\)

\(3,4\)是其中\(3\)个的子串，\(1,3\)是其中\(1\)个的子串。

数据规模与约定

对于 \(30\%\) 的数据，\(1 \leq n,m \leq 70\)。

对于\(60\%\) 的数据，\(1 \leq n,m \leq 500\)。

对于 \(100\%\) 的数据，\(1 \leq n,m \leq 100000\)，\(1 \leq Q \leq 100\) ，查询序列的总长度不超过\(1000000\)。

时间限制：\(1 \text{s}\)

空间限制：\(512 \text{MB}\)

题目保证元素不重复，所以相邻元素组成的序对在序列中是唯一的

一个长度为k的序列是模式序列的字串，当且仅当它的k-1个相邻元素组成的序对都在模式序列中出现过

所以我们在修改过程中，需要维护模式序列相邻元素组成的序对。询问序列的序对出现了k-1次，就说明它现在是模式序列的字串

用链表维护模式序列，开一个数组记录序对，用cnt记录出现次数即可

链表模拟，两个坑点

一定给后继赋初值，另外一定要先更新last后更新nex

#include <bits/stdc++.h>
#define LL long long
#define debug
using namespace std;
//东方之珠 整夜未眠！
const int N = 1e5+66;

int n, m, Q;
int opt[N], x[N], y[N], a[N];
int last[N], pre[N], nex[N];
int cnt, res;

inline void charu(int x) {if (pre[x] == last[x]) ++ cnt;}

inline void shanchu(int x) {if (pre[x] == last[x]) -- cnt;}

inline void yhm()
{
    memset(last, 0, sizeof last);
    memset(pre, 0, sizeof pre);
    memset(nex, 0, sizeof nex);
    int u(n + 3), v, i, k;
    scanf ("%d", &k);
    for (i = 1; i <= k; ++ i)
    {
        scanf ("%d", &v);
        pre[v] = u;
        u = v;
    }
    pre[n + 4] = u, cnt = res = 0;//keng
    for (i = 0; i <= n; ++ i)
    {
        nex[a[i]] = a[i + 1];
        last[a[i + 1]] = a[i];
        charu(a[i + 1]);
    }
    for (i = 1; i <= m; ++ i)
    {
        u = x[i], v = y[i];
        if (opt[i] == 1)
        {
            shanchu(u); shanchu(nex[u]);
            nex[last[u]] = nex[u];
            last[nex[u]] = last[u];
            charu(nex[u]);
        } else
        {
            if (! u) u = n + 1;
            shanchu(nex[u]);
            last[v] = u, nex[v] = nex[u];
            last[nex[u]] = v, nex[u] = v;//keng
            charu(v), charu(nex[v]);
        }
        if (cnt == k - 1) ++ res;
    }
    cout << res << '\n';
}

inline int thestars()
{
    int i;
    scanf ("%d%d%d", &n, &m, &Q);
    a[0] = n + 1, a[n + 1] = n + 2;
    for (i = 1; i <= n; ++ i) scanf ("%d", &a[i]);
    for (i = 1; i <= m; ++ i)
    {
        scanf ("%d%d", &opt[i], &x[i]);
        if (opt[i] != 1) scanf ("%d", &y[i]);
    }
    while (Q --) yhm();
    return 0;
}

int youngore = thestars();

signed main() {;}

小鱼

题目描述

小鱼遇到了一个组合问题，给定正整数\(n\)，求 \[ \sum_{i=1}^{n} \frac{n}{gcd(i,n)} \] 输入格式

第\(1\)行一个整数\(T\)，表示有\(T\)个询问。

接下来\(T\)行，每行一个数\(n\)。

输出格式

\(T\)行，每行对应一个询问的答案。

样例数据

input

output

数据规模与约定

对于 \(40\%\) 的数据，\(1 \leq n \leq 2000\)。

对于另外 \(10\%\) 的数据，保证\(n\)是质数。

对于另外 \(10\%\) 的数据，保证\(n\)是两个质数的乘积。

对于 \(100\%\) 的数据，\(1 \leq T \leq 300000,1 \leq n \leq 10000000\)。

时间限制：\(2 \text{s}\)

空间限制：\(512 \text{MB}\)

#include <bits/stdc++.h>
#define int long long
#define debug
using namespace std;
//东方之珠 整夜未眠！
const int N = 1e7+66;

inline int gcd(int x, int y){return !y ? x : gcd(y, x%y);}

int g[N], w[N], last[N];

int v[N], pri[N];

inline int thestars()
{
    int T, i, j, n, cnt(0);
    w[1] = 1;
    for (i = 2; i <= N; ++ i)
    {
        if (! v[i])
        {
            pri[++ cnt] = last[i] = i;
            g[i] = w[i] = i * (i - 1) + 1;
        }
        for (j = 1; j <= cnt && i * pri[j] <= N; ++ j)
        {
            v[i * pri[j]] = 1;
            if (! (i % pri[j]))
            {
                g[i * pri[j]] = g[i] * pri[j] * pri[j] - pri[j] + 1;
                w[i * pri[j]] = w[i / last[i]] * g[i * pri[j]];
                last[i * pri[j]] = last[i] * pri[j];
                break;
            }
            g[i * pri[j]] = pri[j] * (pri[j] - 1) + 1;
            w[i * pri[j]] = w[i] * w[pri[j]];
            last[i * pri[j]] = pri[j];
        }
    }
    cin >> T;
    while (T --)
    {
        scanf ("%d", &i);
        cout << w[i] << '\n';
    }
    return 0;
}

int youngore = thestars();

signed main() {;}