2022牛客寒假集训营4

题目链接：link

E.真假签到题

题目

小红拿到了一份代码：

long long f(long long x)
{
    if(x == 1)
        return 1;
    return f(x / 2) + f(x / 2 + x % 2);
}

给定一个正整数 \(x\) ，求 \(f(x)\)

分析

猜想 \(f(x)=x\) ，用归纳法：

  • \(x=1\) 时， \(f(1)=1\) 成立

  • 若 \(x\leq k\) 时，\(f(x)=x\) 都成立

    那么 \(x=k+1\) 时， \(f(x)=f(\lfloor\frac{x}{2}\rfloor)+f(\lfloor\frac{x}{2}\rfloor+x\bmod 2)=2\lfloor\frac{x}{2}\rfloor+x\bmod 2=x\) 也成立

综上， \(f(x)=x\) 对 \(x\in\mathbb{N^*}\) 都成立

代码
#include
using namespace std;

int main()
{
    long long x;
    cin >> x;
    cout << x << endl;
    return 0;
}

H.真真真真签到题

题目

小红和紫被困在一个正方体的内部

紫先选择了一个位置，然后小红选择一个位置，紫希望离小红尽可能近，小红希望离紫尽可能远

两人都会选择最优策略，已知她们最终的距离为 \(x\) ，小红想知道正方体的体积是多少？

分析

紫先选择，由于小红会尽可能离他远，所以他的最优策略是使距离的最大值最小，那么他一定会在正方体中心，小红在正方体的八个端点之一

所以 \(x=\frac{\sqrt{3}}{2}a,V=a^3=\frac{8}{3\sqrt3}x^3\)

代码
#include
using namespace std;

int main()
{
    double x;
    cin >> x;
    cout << (8.0 * x * x * x / 3.0 / sqrt(3.0)) << endl;
    return 0;
}

K.小红的真真假假签到题

题目

给定一个正整数 \(x\leq 10^9\) ，构造一个正整数 \(y\) 满足以下性质：

  • \(x\mid y\) 且 \(x\not= y\)
  • \(1\leq y\leq 10^{19}\)
  • 在二进制表示下， \(x\) 是 \(y\) 的一个子串，且 \(x\) 和 \(y\) 在二进制表示下的 \(1\) 的个数不能相同
分析

设 \(x\) 的二进制表示为 \(\overline{a_1a_2\cdots a_n},n=\lfloor\log_2{x}\rfloor+1\)

那么 \(y=\overline{a_1a_2\cdots a_na_1a_2\cdots a_n}=(2^n+1)x\) 满足第一个和第三个条件，且 \(y\leq x(2x+1)\leq 2\cdot10^{18}+10^9\leq 10^{19}\) 满足第二个条件

#include
using namespace std;

int main()
{
    long long x;
    cin >> x;
    cout << x * (1ll << (int)(log2(x) + 1)) + x << endl;
    return 0;
}

F.小红的记谱法

题目

简谱有 2 种记谱的方法：

  1. 用 1234567 分别表示 do re me fa so la si
  2. 用 CDEFGAB 分别表示 do re me fa so la si

对于第一种记谱法，在一个数字后面加 \(x\) 个 * 表示升高了 \(x\) 个八度，在一个音后面加 \(x\) 个 . 表示减少了 \(x\) 个八度

而第二种记谱法和第一种不同的在于，尖括号 < 代表后面所有的音比前面的音低 8 度，反尖括号 > 则代表后面所有的音比前面的音高 8 度

现在给出一段第二种记谱法表示的简谱，输出对应的第一种记谱法

分析

模拟题

代码
#include
using namespace std;

int main()
{
    int cnt = 0;
    string s;
    cin >> s;
    for(int i = 0; i < s.length(); i++) {
        if(s[i] == '>')
            cnt++;
        else if(s[i] == '<')
            cnt--;
        else{
            if(s[i] == 'C') cout << 1;
            if(s[i] == 'D') cout << 2;
            if(s[i] == 'E') cout << 3;
            if(s[i] == 'F') cout << 4;
            if(s[i] == 'G') cout << 5;
            if(s[i] == 'A') cout << 6;
            if(s[i] == 'B') cout << 7;
            if(cnt > 0)
                for(int j = 0; j < cnt; j++)
                    cout << '*';
            else
                for(int j=cnt;j<0;j++)
                    cout<<'.';
        }
    }
    cout << endl;
}

C.蓝慧星

题目

天上有两种彗星：红彗星和蓝慧星，每颗彗星会在出现 \(t\) 秒后消失，小红想知道有多少秒只能看到蓝慧星而看不到红彗星

分析

用两个数组 \(sum1,sum2\) 分别表示蓝彗星和红彗星，如果这个时段没有蓝慧星那么 \(sum1[i]=0\) ，红彗星同理

再转化为差分数列，所以区间修改就变为了两个单点修改，最后再还原原数列， \(sum1[0]\not= 0\) 且 \(sum2[i]=0\) 的时刻是符合条件的

代码
#include
using namespace std;

const int MAX_N = 200000 + 5;
int n, k;
string s;
int sum1[MAX_N], sum2[MAX_N];

int main()
{
    cin >> n >> k >> s;
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        if(s[i] == 'B') {
            sum1[x]++;
            sum1[x + k]--;
        } else {
            sum2[x]++;
            sum2[x + k]--;
        }
    }
    int ans = 0;
    for(int i = 1; i <= 2e5; i++) {
        sum1[i] += sum1[i - 1];
        sum2[i] += sum2[i - 1];
        ans += (sum1[i] && !sum2[i]);
    }
    cout << ans << endl;
}

I.爆炸的符卡洋洋洒洒

题目

小红有 \(n\) 种符卡，第 \(i\) 个符卡魔力为 \(a_i\) ，威力为 \(b_i\)

如果将多个符卡进行组合，则可以发动一个组合魔法，组合魔法的魔力消耗为选择的符卡的魔力消耗的总和，其威力为选择的符卡的威力的总和
小红必须保证最终符卡的魔力消耗总和为 \(k\) 的倍数，否则小红将受到魔力反噬而发动魔法失败
小红想知道，自己能发动的组合魔法最大的威力是多少

分析

01背包变形，要注意的是初始化时要为所有状态赋一个极小的初值，代表无法取到

\[dp[i][j]=\max(dp[i-1][j],dp[i-1][(j+k-a[i]\bmod k)\bmod k]+b[i]) \]

代码
#include
#define ll long long
using namespace std;

const int MAX_N = 1000 + 5;
ll dp[MAX_N][MAX_N];
ll a[MAX_N], b[MAX_N];
int n, k;

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= k; j++)
            dp[i][j] = -1e16;
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < k; j++)
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][(j + k - a[i] % k) % k] + b[i]);
    cout << (dp[n][0] > 0 ? dp[n][0] : -1) << endl;
    return 0;
}

J.区间合数的最小公倍数

题目

求 \([l,r]\) 内所有合数的最小公倍数，对 \(10^9+7\) 取模

分析

先用线性筛筛出 \([1,r]\) 内所有素数，区间内的合数的最小公倍数一定由其中的一部分素数的次幂组成，对于每个素数 \(p\) ，判断它是否能被 \([l,r]\) 内的数整除，且能整除它的数不是它本身

\[l\leq kp\leq r\Rightarrow \lceil\frac{l}{p}\rceil\leq k\leq\lfloor\frac{r}{p}\rfloor \]

若存在两个或以上的 \(k\) ，则符合条件，若只存在一个 \(k\) 且 \(k\not=1\) ，也符合条件

对于符合条件的素数，计算它的最高次幂，最后将所有项相乘取模即可

代码
#include
#define ll long long
using namespace std;

const int MAX_N = 100000 + 5;
const int MOD = 1e9 + 7;
ll ans = 1;
bool is_prime[MAX_N];
int prime[MAX_N];
int cnt;

void sieve(int n)
{
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[1] = false;
    cnt = 0;
    for(int i = 2; i <= n; i++) {
        if(is_prime[i])
            prime[++cnt] = i;
        for(int j = 1; j <= cnt && i * prime[j] <= n; j++) {
            is_prime[i * prime[j]] = false;
            if(i % prime[j] == 0)
                break;
        }
    }
}


int main()
{
    int l, r, n;
    cin >> l >> r;
    n = max(l ,r);
    sieve(n);
    bool fnd = false;
    for(int i = l; i <= r; i++) {
        if(!is_prime[i]) {
            fnd = true;
            break;
        }
    }
    if(!fnd) {
        cout << -1 << endl;
        return 0;
    }
    for(int i = 1; i <= cnt; i++) {
        if(r / prime[i] - ceil(l / prime[i]) + 1 > 1 || r / prime[i] != 1) {
            ans = ans * prime[i] % MOD;
            cout << prime[i] << endl;
        }
    }
    cout << ans << endl;
    return 0;
}

A.R

题目

给定一个长度为 \(n\) 的仅含大写字母的字符串，取一个连续子串，该子串至少包含 \(k\) 个 R 字符且不能包含 P 字符，求有多少符合条件的子串

分析

设 \(r\) 为包括第 \(i\) 个字符向后出现的第 \(k\) 个 R 的位置，\(p\) 为包括第 \(i\) 个字符向后出现第 \(1\) 个 P 的位置，当 \(r 时会对答案产生 \(p-r\) 的贡献，从 \(1\) 到 \(n\) 遍历每一个字符并更新 \(r,p\) 即可

代码
#include
using namespace std;

int n, k;
char s[200000 + 5];

int find_ch(int st, char ch, int x)
{
    int cnt = 0;
    for(int i = st; i <= n; i++) {
        if(s[i] == ch) {
            cnt++;
            if(cnt == x)
                return i;
        }
    }
    return -1;
}

int main()
{
    scanf("%d%d\n%s", &n, &k, s + 1);
    s[++n] = 'P';
    long long ans = 0;
    int r = find_ch(1, 'R', k), p = find_ch(1, 'P', 1);
    if(r < p && r != -1)
        ans += p - r;
    for(int i = 2; i <= n; i++) {
        if(s[i - 1] == 'R')
            r = find_ch(r + 1, 'R', 1);
        else if(s[i - 1] == 'P')
            p = find_ch(i, 'P', 1);
        if(r < p && r != -1)
            ans += p - r;
        if(r == -1)
            break;
    }
    printf("%lld\n", ans);
    return 0;
}

B.进制

题目

小红拿到了一个长度为 \(n\) 的数字串（只包含 \(0\sim9\) ），她有 \(q\) 次操作

第一种： 1 x y ，表示修改第 \(x\) 个数字为 \(y\)

第二种： 2 x y ，表示查询区间 \([x,y]\) 所能代表的某进制的最小值

分析

用线段树维护区间 \([x,y]\) 内的最大值和区间代表的 \(2\sim10\) 进制的值，对于第二种操作，先查询区间内的最大值 \(maxx\) ，那么代表的最小值就是 \(maxx+1\) 进制下的值

#include
#define ll long long
#define ls(k) k << 1
#define rs(k) k << 1 | 1
using namespace std;

const int MOD = 1e9 + 7;
const int MAX_N = 100000 + 5;
int n, q;
int maxx[MAX_N * 4], s[MAX_N];
ll num[MAX_N * 4][11];
char str[MAX_N];

ll qpow(ll a, ll b)
{
    ll res = 1;
    for(; b; b >>= 1) {
        if(b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
    }
    return res;
}

void build(int k, int l, int r)
{
    if(l == r) {
        maxx[k] = s[l];
        for(int i = 2; i <= 10; i++)
            num[k][i] = s[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(ls(k), l, mid);
    build(rs(k), mid + 1, r);
    maxx[k] = max(maxx[ls(k)], maxx[rs(k)]);
    for(int i = 2; i <= 10; i++) {
        num[k][i] = (num[ls(k)][i] * qpow(i, r - mid) % MOD + num[rs(k)][i]) % MOD;
    }
}

void modify(int k, int l, int r, int x, int y)
{
    if(l == r && l == x) {
        maxx[k] = y;
        for(int i = 2; i <= 10; i++)
            num[k][i] = y;
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid)
        modify(ls(k), l, mid, x, y);
    else
        modify(rs(k), mid + 1, r, x, y);
    maxx[k] = max(maxx[ls(k)], maxx[rs(k)]);
    for(int i = 2; i <= 10; i++) {
        num[k][i] = (num[ls(k)][i] * qpow(i, r - mid) % MOD + num[rs(k)][i]) % MOD;
    }
}

int query1(int k, int l, int r, int x, int y)
{
    if(l >= x && r <= y)
        return maxx[k];
    int mid = (l + r) >> 1;
    int res = 0;
    if(x <= mid)
        res = query1(ls(k), l, mid, x, y);
    if(mid + 1 <= y)
        res = max(res, query1(rs(k), mid + 1, r, x, y));
    return res;
}

ll query2(int k, int l, int r, int x, int y, int p)
{
    if(l >= x && r <= y)
        return num[k][p] * qpow(p, y - r) % MOD;
    int mid = (l + r) >> 1;
    ll lres = 0, rres = 0;
    if(x <= mid)
        lres = query2(ls(k), l, mid, x, y, p) % MOD;
    if(mid + 1 <= y)
        rres = query2(rs(k), mid + 1, r, x, y, p) % MOD;
    return (lres + rres) % MOD;
}

int main()
{
    scanf("%d%d\n%s", &n, &q, str + 1);
    for(int i = 1; i <= n; i++)
        s[i] = str[i] - '0';
    build(1, 1, n);
    while(q--) {
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if(opt == 1) {
            modify(1, 1, n, x, y);
        } else {
            int p = query1(1, 1, n, x, y);
            printf("%lld\n", query2(1, 1, n, x, y, p + 1));
        }
    }
    return 0;
}

G.子序列权值乘积

题目

定义一个数组的权值为数组内的最大值乘最小值

给定一个长度为 \(n\) 的数组，求所有非空序列的权值乘积

分析

由于乘积内项的顺序可以任意改变，所以我们可以把最大值和最小值分别计算，先对数组 \(a\) 进行排序，对于 \(a[i]\) ，它作为最大值时，可以和前 \(i-1\) 个数的任意子集组成序列，对答案的贡献就是：

\[a_i^{2^{i-1}} \]

同理，它作为最小值时，可以和后 \(n-i\) 个数的任意子集组成序列，对答案的贡献是：

\[a_i^{2^{n-i}} \]

对于每一项分别计算即可，指数取模时需要用到费马小定理

代码
#include
#define ll long long
using namespace std;

const int MOD = 1e9 + 7;
const int MAX_N = 200000 + 5;
int a[MAX_N];
int n;

ll qpow(ll a, ll b, ll p)
{
    ll res = 1;
    for(; b; b >>= 1) {
        if(b & 1)
            res = res * a % p;
        a = a * a % p;
    }
    return res;
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) 
        scanf("%d", &a[i]);
	sort(a + 1, a + n + 1);
	ll ans = 1;
	for(int i = 1; i <= n; i++) {
		ans = ans * qpow(a[i], (qpow(2, i - 1, MOD - 1)), MOD) % MOD;
		ans = ans * qpow(a[i], (qpow(2, n - i, MOD - 1)), MOD) % MOD;
	}
	printf("%lld\n", ans);
}
ACM题解

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

Ubuntu 断网问题解决

[SQL] SQL Server 2019 中LocalDB 报错的问题解决

题解 Count on a tree II/【模板】树分块

HttpURLConnection发送中文乱码问题解决

1675: [Usaco2005 Feb]Rigging the Bovine Election 竞选划区（题解第一弹）

acm讲解

P7715 「EZEC-10」Shape 题解

Proguard混淆之后行数LineNumber对不上问题解决

ZYNQ xilinx_axienet CPU软中断占用过高问题解决记录

题解 P6345 [CCO 2017]接雨滴

魔咒词典 - 题解【暴搜】

标签