头像

Jackyc

南昌男子职业技术学院




离线:6分钟前


最近来访(228)
用户头像
企鹅聊天图书馆摇头晃
用户头像
易烊千玺
用户头像
彩色铅笔
用户头像
Jack_FuDan
用户头像
不熬夜
用户头像
RADWIMPS
用户头像
hunzia
用户头像
xiusike1
用户头像
SUPERDOGE
用户头像
crsecent
用户头像
caoyiyang
用户头像
Augety__
用户头像
辉虚元年
用户头像
Peter_5
用户头像
我是傻吊
用户头像
acWing_lbwnb
用户头像
xiaohuahua
用户头像
Randolph
用户头像
会飞的泡泡
用户头像
Linking

活动打卡代码 AcWing 379. 捉迷藏

Jackyc
14小时前

最小路径点覆盖:用最少的互不相交的路径,把所有点覆盖
一边的总点数n-m 为答案

最小路径重复点覆盖:用最少的可相交的路径,把所有点覆盖
答案: 传递闭包+最小路径点覆盖

两者区别的好例子:
Snipaste_2021-09-26_21-09-18.png

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 210, M = 30010;

bool g[N][N];
int match[N];
bool st[N];
int n, m;

bool dfs(int x) {
    for(int i = 1; i <= n; i ++) {
        if(!st[i] && g[x][i]) {
            st[i] = true;
            if(match[i] == -1 || dfs(match[i])) {
                match[i] = x;
                return true;
            }
        }
    }
    return false;
}
int main() {
    scanf("%d%d", &n, &m);
    while(m --) {
        int a, b;
        scanf("%d%d", &a, &b);
        g[a][b] = true;
    }

    for(int k = 1; k <= n; k ++)
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= n; j ++)
                g[i][j] |= g[i][k] & g[k][j];
    int ans = 0;
    memset(match, -1, sizeof match);
    for(int i = 1; i <= n; i ++) {
        memset(st, false, sizeof st);
        if(dfs(i)) ans ++;
    }

    printf("%d\n", n - ans);

    return 0;
}


新鲜事 原文

Jackyc
1天前
1024,工程课会打折吗请问


活动打卡代码 AcWing 240. 食物链

Jackyc
2天前
#include<iostream>
#include<cstring>
#include<algorithm>
#define sd(x) scanf("%d", &x)
#define rep(i, a, b) for(int i = a; i <= b; i ++)

using namespace std;

const int N = 50010;
int p[N];
int rela[N];
int n, k;
int x, y, r;
int ans;

void init() {
    rep(i, 1, N - 1) {
        p[i] = i;
        rela[i] = 0;
    }
}

int find(int x) {
    if(x != p[x]) {
        int root = find(p[x]);
        rela[x] = (rela[x] + rela[p[x]]) % 3;
        p[x] = root;
    }
    return p[x];
}

void merge(int r, int x, int y) {
    int fx = find(x), fy = find(y);
    if(fx != fy) {
        p[fx] = fy;
        rela[fx] = (rela[y] + r + 3 - rela[x]) % 3;
    }
}

bool check(int r, int x, int y) {
    if(x > n || y > n)
        return false;
    if(r == 1 && x == y)
        return false;

    if(find(x) == find(y)) {
        int relation = (rela[x] + 3 - rela[y]) % 3;
        return r == relation;
    }
    else
        return true;
}
int main() {
    init();
    sd(n), sd(k);
    while(k --) {
        scanf("%d%d%d", &r, &x, &y);
        r --;
        if(check(r, x, y))
            merge(r, x, y);
        else ans ++;
    }

    printf("%d\n", ans);
    return 0;
}




Jackyc
17天前

I 三角尼姆

Snipaste_2021-09-09_19-05-03.png
Snipaste_2021-09-09_19-05-10.png

思路

此题教训:多动脑ok?

由于每次操作都是 奇数的操作, 所有的结点总数为 $\frac{n*(n+1)}{2}$, 要把它填满, 我们发现如果总数为奇数时, 则必须操作奇数次 奇数的操作, 否则操作偶数次 奇数的操作

代码

#include<iostream>

using namespace std;

int main(){
    int _;
    cin >> _;
    while(_ --){
        int n;
        cin >> n;
        if(n * (n + 1) / 2 % 2 == 0) puts("Bob");
        else puts("Alice");
    }

    return 0;
}

G切圈圈

Snipaste_2021-09-09_19-49-43.png

思路

真是妙蛙种子吃着妙脆角走进了米奇妙妙屋,妙到家了。
想到了,但没有完全想到。

思维题。
求一遍前缀和, 答案取 所有数中 某个数出现次数最大的个数

#include<iostream>
#include<unordered_map>

using namespace std;

unordered_map<int, int> mp;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int _;
    cin >> _;
    while(_ --){
        int sum = 0, ans = 0;
        mp.clear();
        int n;
        cin >> n;
        while(n --){
            int x;
            cin >> x;
            ans = max(ans, ++ mp[sum += x]);
        }

        cout << ans << endl;
    }

    return 0;
}



Jackyc
18天前

C dd爱科学2.0

Snipaste_2021-09-08_16-35-51.png
Snipaste_2021-09-08_16-35-57.png

思路

sorry,简单DP, 为什么我只想到贪心, 赏自己两巴掌.

状态表示dp[i][j] : 已经处理前i个字母,且当前末尾字符是j的最小花费
状态计算: 划分集合, 每个小集合都是决策,即前一个字母是A~Z的最优情况, 前提要保持非递减
边界:f[0][0~26] = 0

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define rep(a, b) for(int i = a; i <= b; i ++)
using namespace std;

const int N = 1000010;

int a[N];
char str[N];
int dp[N][26];

int main(){
    int n;
    cin >> n >> str + 1;

    rep(1, n){
        for(int j = 0; j < 26; j ++){
            dp[i][j] = 1e9;
            for(int k = 0; k <= j; k ++){
                dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(str[i]-'A'-j));
            }
        }
    }

    int res = 1e9;
    rep(0, 25){
        res = min(res, dp[n][i]);
    }

    cout << res << endl;

    return 0;
}


分享 DP理解

Jackyc
18天前

DP适用

dp一般用于解决多阶段决策问题,即每个阶段都要做一个决策,全部的决策是一个决策序列,要你求一个

所以有多阶段决策类问题,麻烦我脑子能想到 DP算法,而不是傻了吧唧 贪心

最好的决策序列使得这个问题有最优解

!!该问题具有最优子结构。

DP硬核解释

DP的正规解释是:动态规划(英语:Dynamic programming,DP)是一种在数学、计算机科学和经济学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再合并子问题的解以得出原问题的解。 通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量: 一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

动态规划问题的三大性质(也是dp能用的三大条件):

!!1.最优子结构性质:

如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。

2.子问题重叠性质:

子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的效率。

3.无后效性:

将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性。

最优子结构?

问题拥有最优子结构:一个问题的最优解可由子问题的最优解有效构造出来。
比如:(采花生, 走到终点或者随便某个点, 它可由左边或者上面的最优解推导而来)。

最优子结构保证了动态规划中原问题的最优解可以由子问题的最优解推导而来。

因此一个问题必须拥有最优子结构,才能用动态规划解决。

DP需要的三要素

  • 状态表示
  • 状态计算
  • 边界

转载+个人理解



分享 define偷懒

Jackyc
19天前
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#define dbg(a)  cout<<#a<<" : "<<a<<endl;
#define IOS std::ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define PAUSE   system("pause")
#define sd(a)       scanf("%d",&a)
#define sll(a)      scanf("%intd",&a)
#define sdd(a,b)    scanf("%d%d",&a,&b)
#define sddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define sf(a)       scanf("%lf",&a)
#define sff(a,b)    scanf("%lf%lf",&a,&b)

int read()
{
    int x = 0, fx = 1; char c = getchar();
    while (c < '0' || c > '9') { fx ^= ((c == '-') ? 1 : 0); c = getchar(); }
    while ('0' <= c && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
    if (!fx) return -x;
    return x;
}

#include <bits/stdc++.h>
#include <unordered_set>
//#include <unordered_map>
//#include <regex>
using namespace std;
#define ll long long
#define debug(x) cerr<<#x<<" : "<<x<<endl
//#define rep(i,_begin,_end) for (auto i=(_begin),_step=1-2*((_begin)>(_end));i!=_end;i+=_step)
#define MOD 1000000007
const double PI = acos(-1);
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<pii, int> piii;
typedef unsigned long long ull;
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 };
const int ddx[] = { -1, -1, -1, 0, 0, 1, 1, 1 }, ddy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
// INPUT
template<typename T>
inline void in(T& x) {
    T s = 0, w = 1; char ch = getchar();
    while (ch < '0' || ch>'9') { if (ch == '-')w = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    x = s * w;
}
// gcd
template<typename T>
T gcd(T a, T b) { return (!b) ? a : gcd(b, a % b); }
// min
template<class T>
T min(const vector<T>& v) { return *min_element(v.begin(), v.end()); }
// max
template<class T>
T max(const vector<T>& v) { return *max_element(v.begin(), v.end()); }
// lowbit
inline int lowbit(int x) { return x & (-x); }
// modadd
inline int modadd(int x, int y) { return (x + y >= MOD ? x + y - MOD : x + y); }
// sgn
inline int sgn(int x) { return (x < 0 ? -1 : (x > 0 ? 1 : 0)); }
// ab
inline ll ab(ll x) { return x < 0 ? -x : x; }
#define modu MOD



Jackyc
21天前

D 位运算之谜

链接:https://ac.nowcoder.com/acm/contest/7412/D
来源:牛客网

Snipaste_2021-09-05_19-51-21.png
Snipaste_2021-09-05_19-51-29.png

输入

1
2 1

输出

0

输入

1
2 2

输出

-1

思路

结论:x + y = x ^ y + (x & y) << 1
将x + y = a, x & y = b, 代入
x ^ y = a - (b << 1)

代码

#include<iostream>

using namespace std;

typedef long long LL;

int main(){
    int T;
    scanf("%d", &T);
    while(T --){
        LL x, y;
        scanf("%lld%lld", &x, &y);
        LL ans = x - (y << 1);
        if(ans < 0 || ans & y) cout << -1 << endl;
        else cout << ans << endl;
    }

    return 0;
}

G 牛牛和字符串的日常

Snipaste_2021-09-05_19-58-44.png
Snipaste_2021-09-05_19-58-50.png

思路

字符串匹配问题, KMP模板题

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010;

char p[N], s[N];
int ne[N];
int main(){
    scanf("%s", p + 1);
    int n = strlen(p + 1);
    for(int i = 2, j = 0; i <= n; i ++){
        while(j && p[j + 1] != p[i]) j = ne[j];
        if(p[i] == p[j + 1]) j ++;
        ne[i] = j;
    }

    int T;
    int ans = 0;
    scanf("%d", &T);
    while(T --){
        scanf("%s", s + 1);
        int m = strlen(s + 1);
        int res = 0;
        for(int i = 1, j = 0; i <= m; i ++){
            while(j && s[i] != p[j + 1]) j = ne[j];
            if(s[i] == p[j + 1]) j ++;
            res = max(res, j);
        }
        ans += res;
    }

    printf("%d\n", ans);

    return 0;
}

J树上行走

Snipaste_2021-09-05_20-10-32.png
Snipaste_2021-09-05_20-10-39.png
Snipaste_2021-09-05_20-10-47.png

思路

找连通块元素个数最大值,可以用dfs, 也可以并查集

#include<iostream>
#include<cstring>
#include<algorithm>
#define rep(a, b) for(int i = a; i <= b; i ++)
using namespace std;

const int N = 200100;

int p[N];
int w[N];
int Size[N];
int n;
int ans[N];

int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main(){
    scanf("%d", &n);
    rep(1, n){
        int x;
        scanf("%d", &x);
        w[i] = x;
        p[i] = i;
        Size[i] = 1;
    }

    rep(1, n - 1){
        int a, b;
        scanf("%d%d", &a, &b);
        if(w[a] == w[b]) {
            int pa = find(a), pb = find(b);
            if(pa == pb) continue;
            Size[pb] += Size[pa];
            p[pa] = pb;
        }
    }
    int maxv = 0;
    rep(1, n){
        maxv = max(maxv, Size[find(p[i])]);
    }

    int cnt = 0;
    rep(1, n){
        if(Size[find(p[i])] == maxv) ans[cnt ++] = i;
    }

    sort(ans, ans + cnt);
    printf("%d\n", cnt);
    rep(0, cnt - 1){
        printf("%d ", ans[i]);
    }
    cout << endl;
}



Jackyc
23天前

C 杨辉三角

链接:https://ac.nowcoder.com/acm/contest/11213/C
来源:牛客网

小F对杨辉三角颇有研究,他把杨辉三角第$n$行的数提出来,从左到右分别为$a[0],a[1],…,a[n−1]$。
现在他想知道$\sum_{i=0}^{n-1}i^2 * a[i]$的值是多少,答案对$99824353$取模。

输入描述

输入一个正整数$n$,$n\leq 10^{18}$

输出描述

输出题目中式子的值,答案对$99824353$取模。

输入样例

3

输出样例

6

QQ图片20210904095357.jpg

代码

#include<iostream>

using namespace std;

typedef long long LL;

const int mod = 99824353;

LL qmi(LL a, LL b){
    if(b < 0) return 1;
    LL res = 1;
    while(b){
        if(b & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        b >>= 1;
    }

    return res % mod;
}
int main(){
    LL n;
    cin >> n;
    if(n == 2) {
        cout << 1 << endl;
        return 0;
    }
    n --;
    cout << n % mod * (n + 1) % mod * qmi(2, n - 2) % mod << endl;
}

B最短串

链接:https://ac.nowcoder.com/acm/contest/11213/B
来源:牛客网

题目描述
给定$2$个由小写字母和问号组成的字符串$a$与$b$,问号代表你想要的任何字符。
请你找出最短的字符串$s$,要求$s$包含$a$和$b$两个字符串,你只需要输出$s$的长度即可。
输入描述:
第一行一个字符串$a$,$|a| \leq 5000$

第二行一个字符串$b$,$|b| \leq 5000$

输出描述:
输出最短字符串$s$的长度。

示例1
输入

abc
?de

输出

5

思路

双指针, 对a串和b串分别作为主串跑一遍双指针, 若满足if(a[i] == '?' || b[j] == '?' || a[i] == b[j]); 则另一个串即子串指针可以后移一位,注意当j=0时需要再判断一次,并且若子串匹配成功,及时break

代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 5010;
string a, b;

bool check(int i, int j){
    if(a[i] == '?' || b[j] == '?' || a[i] == b[j]) return true;
    return false;
}

int main(){
    cin >> a >> b;

    int j = 0;
    for(int i = 0; i < a.size(); i ++){
        if(j == (int)b.size()) break;
        if(check(i, j)) j ++;
        else {
            j = 0;
            if(check(i, j)) j ++;
        }
    }

    int ans1 = a.size() + (b.size() - j);

    j = 0;
    for(int i = 0; i < b.size(); i ++){
        if(j == (int)a.size()) break;
        if(check(j, i)) j ++;
        else {
            j = 0;
            if(check(j, i)) j ++;
        }
    }

    int ans2 = b.size() + (a.size() - j);

    int ans = min(ans1, ans2);

    cout << ans << endl;


    return 0;
}

H卷王之王

链接:https://ac.nowcoder.com/acm/contest/11213/H
来源:牛客网

题目描述
牛卷风是养蛊大学著名的小镇做题家,每天早上6点半起床,凌晨2点半睡觉,除了一日三餐,其他时间均用来学习,因此考试从未低于90分,人送外号“养蛊大学不眠传说”。

你从四处打听到,牛卷风如此之强的原因在于他有一套练习计算能力的秘诀,该秘诀如下:首先给出$n$个数字,第$i$个数字为$a[i]$。接下来进行mm次操作,每次操作给出一个数字xx,练习者在心中将所有值小于等于$x$的数字都加$x$。当进行完这$m$次操作后,练习者再按顺序给出这$n$个数字。

话不多说,你立马着手练习。首先你让朋友给出一开始的$n$个数字和$m$次操作的$x$,请你给出进行完$m$次操作后的$n$个数字。

输入描述:
第一行两个正整数$n$, $m$, $n \leq 10^5$, $m \leq 10^5$

第二行$n$个非负整数$a[i]$, $a[i] \leq 10^9$

接下来$m$行,每行一个非负整数$x$, $x \leq 10^9$

输出描述:

输出进行完$m$次操作后的$n$个数字。

输入

5 2
1 2 3 4 5
2
3

输出

6 4 6 4 5

思路

卷吧,都给我卷。
线段树维护区间最小值, 区间最小值要大于 $x$, 直接返回。

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define pre(i, a, b) for(int i = a; i >= b; i --)
#define N 100005
using namespace std;
struct Node{
    int l, r;
    int val;
}tr[N << 2];
int n, m, a[N];
#define L tr[u].l
#define R tr[u].r
#define ls (u << 1)
#define rs (ls | 1)
#define S tr[u].val

void build(int u, int l, int r){
    L = l, R = r;
    if(l == r) S = a[l];
    else {
        int mid = l + r >> 1;
        build(ls, l, mid);
        build(rs, mid + 1, r);
        //pushup
        S = min(tr[ls].val, tr[rs].val);
    }
}

void modify(int u, int val){
    if(S > val) return;
    if(L == R) S += val;
    else {
        if(tr[ls].val <= val) modify(ls, val);
        if(tr[rs].val <= val) modify(rs, val);
        S = min(tr[ls].val, tr[rs].val);
    }
}

void query(int u){
    if(L == R) printf("%d ", S);
    else query(ls), query(rs);
}

int main(){
    scanf("%d%d", &n, &m);
    rep(i, 1, n) scanf("%d", &a[i]);
    build(1, 1, n);
    while(m --){
        int x;
        scanf("%d", &x);
        if(x == 0) continue;
        modify(1, x);
    }

    query(1);

    return 0;
}

哥三好

Snipaste_2021-09-06_21-25-32.png
Snipaste_2021-09-06_21-25-39.png

解法:

朴素三维DP, 可发现每个人花钱都是300 || 450 || 750, 则一开始都可以除150, 降低开销。
状态表示: f[i][j][k] a花i元,b花j元,c花k元,的方案种数
答案: f[a][b][c]
状态转移:
6种情况, a人 花 2, 3, 5 b人 花 2, 3, 5, c人花2, 3,5

#include<iostream>

using namespace std;

const int N = 110, mod = 1000000007;
int f[N][N][N];
int main(){
    int a, b, c;
    cin >> a >> b >> c;
    a /= 150;
    b /= 150;
    c /= 150;

    for(int i = 0; i <= 1; i ++)
        for(int j = 0; j <= 1; j ++)
            for(int k = 0; k <= 1; k ++)
                f[i][j][k] = 1;

    for(int i = 0; i <= a; i ++)
        for(int j = 0; j <= b; j ++)
            for(int k = 0; k <= c; k ++){
                if(i >= 2) f[i][j][k] = (f[i][j][k] + f[i - 2][j][k]) % mod;
                if(i >= 3) f[i][j][k] = (f[i][j][k] + f[i - 3][j][k]) % mod;
                if(i >= 5) f[i][j][k] = (f[i][j][k] + f[i - 5][j][k]) % mod;

                if(j >= 2) f[i][j][k] = (f[i][j][k] + f[i][j - 2][k]) % mod;
                if(j >= 3) f[i][j][k] = (f[i][j][k] + f[i][j - 3][k]) % mod;
                if(j >= 5) f[i][j][k] = (f[i][j][k] + f[i][j - 5][k]) % mod;

                if(k >= 2) f[i][j][k] = (f[i][j][k] + f[i][j][k - 2]) % mod;
                if(k >= 3) f[i][j][k] = (f[i][j][k] + f[i][j][k - 3]) % mod;
                if(k >= 5) f[i][j][k] = (f[i][j][k] + f[i][j][k - 5]) % mod;
            }

    cout << f[a][b][c] % mod<< endl;

    return 0;
}



Jackyc
23天前

B擅长解密的小红同学

在这里插入图片描述

思路

因为每次输入会重置,求期望也就是求尝试多少次能成功,等价于求这些数字有多少种排列组合。

也就是多重排列数的问题。

多重排列数

设$S= {n_1a_1,n_2a_2,…,n_ka_k}$是由$n_1$个$a_1$,$n_2$个$a_2$,$n_k$个$a_k$组成的多重集。

多重集排列数
多重集$S$的全排列,不考虑相同的元素,其全排列个数为$(\sum_{i=1}^kn_i)!$,但是因为存在若干个相同的元素,因此要把相同元素的贡献给除掉。

对于每种排列的每个$a_{i,j}$,我们都可以从$n_i$个$a_i$中挑选任意一个,其对答案的贡献满足乘法原理为$n_i!$
因此方案数为
$$
\frac{(\sum_{i=1}^{k}n_i)!}{\prod_{i=0}^{k}n_i!}
$$
注意: 该题$fact[N]$, $N$能取到$10^7$, 若$infact[N]$也也算出来,复杂度达到$O(10^7 * log(10^6))$ 会超时, 所以infact[N]不需做枚举

代码

#include<iostream>

using namespace std;

const int mod = 1e9 + 7;
const int N = 1e7 + 10;
typedef long long LL;

int a[10];
LL fact[N], infact[N];

LL qmi(LL a, LL b){
    LL res = 1;
    while(b){
        if(b & 1) res = (LL)res * a % mod;
        a = (LL) a * a % mod;
        b >>= 1;
    }
    return res;
}

void init(){
    fact[0] = infact[0] = 1;
    for(int i = 1; i < N; i ++){
        fact[i] = (LL)fact[i - 1] * i % mod;
    }

}
int main(){
    for(int i = 0; i < 10; i ++)
        cin >> a[i];

    init();

    LL fz = 0;
    LL ans = 1;
    for(int i = 0; i < 10; i ++){
        fz = (LL)(fz + a[i]) % mod;
        ans = (LL)ans * fact[a[i]] % mod;
    }
    ans = (LL)fact[fz] * qmi(ans, mod - 2) % mod;

    cout << ans << endl;

    return 0;
}

在这里插入图片描述

H 漂亮数

思路

通过两个质数相乘得到漂亮数, 可以直接打表并计算前缀和即可

代码

#include<iostream>
#include<cstring>

using namespace std;

const int N = 50000010;

typedef long long LL;
LL primes[N];
int cnt;
LL st[N];
int s[N * 2];

void init(){
    for(int i = 2; i < N; i ++){
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; (LL)primes[j] * i < N; j ++){
            st[(LL)primes[j] * i] = 1;
            if(i % primes[j] == 0) break;
        }
    }
    for(int i = 0; i < cnt; i ++)
        for(int j = 0; j < cnt; j ++){
            if((LL)primes[i] * primes[j] >= N * 2) break;
            s[(LL)primes[i] * primes[j]] = 1;
        }

    for(int i = 1; i <= N * 2; i ++)
        s[i] += s[i - 1];
}

int main(){
    init();
    int T;
    cin >> T;
    while(T --){
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}

I 加减

链接:https://ac.nowcoder.com/acm/contest/11214/I
来源:牛客网

题目描述

小红拿到了一个长度为 img 的数组。她每次操作可以让某个数加 1 或者某个数减 1 。
小红最多能进行 img 次操作。她希望操作结束后,该数组出现次数最多的元素次数尽可能多。
你能求出这个最大的次数吗?

输入描述

第一行两个正整数 和
第二行有 个正整数

$1≤n≤10^5$
$1≤k≤10^{12}$
$1≤ai≤10^9$

输出描述:

不超过  次操作之后,数组中可能出现最多次数元素的次数。

示例1

输入

5 3
6 3 20 8 1

输出

2

说明

共 3 次操作如下:
第一个数加一。
第二个数加一。
第四个数减一。
数组变成了 7 4 20 7 1 ,共有 2 个相同的数: 7 。
可以证明, 2 为最优解。另外,此上操作并不是唯一的操作。 

思路(贪心,前缀和,二分)

定理: 一个数组每次操作可以让一个数加一或者减一,使所有都相等的操作最小次数的方式是所有数都变成中位数。

排序,求前缀和,枚举区间[L, R], 枚举L, 二分R, 即枚举所有排好序的区间,判断该区间是否达到该区间的中位数的操作小于等于k

代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;
const int N = 100010;

LL a[N];
LL s[N];
LL n, k;

bool check(int l, int r){
    int mid = l + r >> 1;
    LL left_op = a[mid] * (mid - l + 1) - (s[mid] - s[l - 1]);
    LL right_op = (s[r] - s[mid]) - a[mid] * (r - mid);
    return (left_op + right_op) <= k;
}

int main(){
    scanf("%lld%lld", &n, &k);

    for(int i = 1; i <= n; i ++){
        scanf("%lld", &a[i]);
    }

    sort(a + 1, a + n + 1);

    for(int i = 1; i <= n; i ++)
        s[i] = s[i - 1] + a[i];
    int res = 1;
    for(int i = 1; i <= n; i ++){
        //枚举左端点
        int l = i, r = n;
        //二分右端点
        while(l < r){
            int mid = l + r + 1>> 1;
            if(check(i, mid)){
                l = mid;
            }
            else r = mid - 1;
        }

        res = max(res, r - i + 1);
    }

    cout << res << endl;
}