头像

小星星xxx




离线:1天前


最近来访(6)
用户头像
大饺子
用户头像
有恒
用户头像
Tingting
用户头像
Sputnik
用户头像
喵喵酱
用户头像
过儿_2

活动打卡代码 AcWing 680. 剪绳子

二分法:
二分的是剪出的绳子长度
情况1: mid成立
长度为mid时,如果可以裁,那么答案就是[mid, r];

情况2:不成立,裁剪不出m条。
那么任意大于mid的数都不成立。答案就在[l, mid]

如果二分要保留k位小数,那么直到R-L < 10^-(k+2)就可以了

#include <iostream>

using namespace std;

const int N = 1e5+10;
int n, m;
int w[N];

bool check(double mid)
{
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        cnt += w[i]/mid;
    }
    return cnt>=m;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> w[i];

    double l = 0, r = 1e9;
    while(r - l > 1e-4)
    {
        double mid = (l+r)/2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    printf("%.2f", l);
    return 0;
}


活动打卡代码 AcWing 107. 超快速排序

答案:给定任意一个序列,把它变成有序的,最少操作次数,就是逆序对的数量。
每一次交换操作,都会使逆序对数量-1

merge_sort()函数:
1. 如果递归数组长度为1了,返回0(0个逆序对)
2. 定义mid, res, 递归左右
3. 归并排序

#include <iostream>

using namespace std;

typedef long long LL;
const int N = 5e5+10;

LL q[N], tmp[N];
int n;

LL merge_sort(int l, int r)
{
    if (l == r) return 0;

    int mid = l + r >> 1;
    LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else
        {
            res += mid - i + 1;
            tmp[k ++ ] = q[j ++ ];
        }
    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];

    return res;
}

int main()
{
    while(cin >> n, n)
    {
        for(int i = 0; i < n; i++) cin >> q[i];
        cout << merge_sort(0, n-1) << endl;
    }
    return 0;
}


活动打卡代码 AcWing 113. 特殊排序

二分:没有单调性也可以用二分
1. 本题不具有传递性
2. 本题只需要输出一种答案即可。

main():
1. 首先将第一个元素压入向量中
2. 然后二分查找适合的位置:
这里用栈,所以只能从后往前遍历,所以顺序为true, false, false, false
并且true的点在r,然后进行交换,将这个点交换到r+1(下标为r)

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int N) {
        //用于排序的vector,先插入1,后面的数就能和1做比较
        vector<int> res(1, 1);

        //依次把2~N插进去
        for(int i = 2; i <= N; i++)
        {
            //二分,找到一个数比当前数小,就插到这个数后面
            int l = 0, r = res.size()-1;
            while(l<r)
            {
                int mid = (l+r+1)>>1;
                if(compare(res[mid], i)) l = mid;
                else
                    r = mid-1;
            }

            //先将这个数插入到最后
            res.push_back(i);
            //然后依次
            for(int j = res.size() - 2; j > r; j--) swap(res[j], res[j+1]);
            //如果这个数小于res[r]
            if(compare(i, res[r])) swap(res[r], res[r+1]);
        }
        return res;
    }
};


分享 vector

(1) vector [HTML_REMOVED] a(10);
//定义了10个整型元素的向量(尖括号中为元素类型名,它可以是任何合法的数据类型),但没有给出初值,其值是不确定的。

(2) vector[HTML_REMOVED] a(10,1);
//定义了10个整型元素的向量,且给出每个元素的初值为1

(3) vector[HTML_REMOVED] a(b);
//用b向量来创建a向量,整体复制性赋值

(4) vector[HTML_REMOVED] a(b.begin(),b.begin()+3);
//定义了a值为b中第0个到第2个(共3个)元素

(5) int b[7]={1,2,3,4,5,9,8};
vector[HTML_REMOVED] a(b,b+7);
//从数组中获得初值



活动打卡代码 AcWing 1068. 环形石子合并

区间dp:
一维,迭代式:
第一层 循环区间长度,第二层 循环左端点,第三层
,记忆化搜索


区间dp + 环形区间

如何将环转化为区间?
假设每个点合并的过程为,在两个点之间连一条边
n堆石子,全部合并完,会连 n-1 条边,最后还会有一个缺口
枚举每个缺口,把这个题转化为 求n条长度为n的链上的,石子合并问题
把两条链首尾相连,得到一条长度为 2n 的链,那么上面的n条链都在这条2n链上。


main()
1. 输入每堆石子数,注意链长为2n
2. 区间dp 需要 初始化 前缀和数组
3. 第一层枚举区间长度,区间长度为1~n;(第二层循环增加条件,长度为1时,该次合并的得分为0)
4. 第二层枚举左端点:右端点这里可以到2n
5. 第三层枚举分割点(每种情况)(当作石子合并模版来做)
6. 循环完后,重新枚举左端点,求最大/最小值

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

using namespace std;

const int N = 410, INF = 0x3f3f3f3f;
int w[N], s[N];
int n;
int f[N][N], g[N][N];

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> w[i];
        w[i+n] = w[i];
    }
    for(int i = 1; i <= 2*n; i++) s[i] = s[i-1] + w[i];

    memset(f, 0x3f, sizeof f);//求最小值,初始化为正无穷
    memset(g, -0x3f, sizeof g);

    for(int len = 1; len <= n; len++)
        for(int i = 1; i+len-1 <= 2*n; i++)
        {
            int j = i+len-1;
            if(len == 1)
                f[i][j] = g[i][j] = 0;
            else
            {
                for(int k = i; k < j; k++)
                {
                    f[i][j] = min(f[i][j], f[i][k]+f[k+1][j]+s[j]-s[i-1]);
                    g[i][j] = max(g[i][j], g[i][k]+g[k+1][j]+s[j]-s[i-1]);
                }
            }
        }

    int minv = INF, maxv = -INF;
    for(int i = 1; i <= n; i++)//枚举区间左端点
    {
        minv = min(minv, f[i][i+n-1]);
        maxv = max(maxv, g[i][i+n-1]);
    }
    cout << minv << endl << maxv << endl;
    return 0;
}


活动打卡代码 AcWing 1113. 红与黑

dfs()
遍历上下左右四个格子,哪个格子没有被搜过,而且是陆地,那么就遍历过去
1. 将xy标记为已开发
2. 枚举四个邻格
3. 如果邻格可以走,就dfs(这个邻格)
4. 这道题不需要回溯
main()函数:
因为有多组数据,需要初始化 标记数组st[]

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

using namespace std;

const int N = 25;

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

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int dfs(int x, int y){
    int cnt = 1;

    st[x][y] = true;

    for(int i = 0; i < 4; i++){
        int a = x+dx[i], b = y+dy[i];
        if(a>=0 && a<n && b>=0 && b<m && !st[a][b] && g[a][b]=='.'){
            cnt+=dfs(a, b);
        }
    }
    return cnt;
}


int main(){
    while(cin >> m >> n, n || m)
    {
        for(int i = 0; i < n; i++) cin >> g[i];

        int x, y;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                if(g[i][j] == '@'){
                    x = i;
                    y = j;
                }
        memset(st, 0, sizeof st);
        cout << dfs(x, y) << endl;

    }
    return 0;
}


活动打卡代码 AcWing 1117. 单词接龙

第一层枚举,所有以给定字母开头的单词。
对于每个单词分别向下递归搜索,每一次枚举 可以接在后面的所有单词
继续往下递归,直到不能搜为止,更新一下最大值。
再回溯。
为了让龙的长度最长,两个单词重合的部分越短越好

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

using namespace std;

const int N = 21;
string word[N];
int n;
int g[N][N];//初始化,单词a和单词b重合部分长度的最小值
int used[N];//每个单词当前用了多少次
int ans;

void dfs(string dragon, int last)
{
    ans = max((int)dragon.size(), ans);

    used[last]++;

    for(int i = 0; i < n; i++)
        if(g[last][i] && used[i] < 2)//last的后面可以接i这个单词
            dfs(dragon + word[i].substr(g[last][i]) ,i);

    used[last]--;
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> word[i];
    char start;
    cin >> start;

    //初始化,某个单词能否接到另一个单词后面
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
        {
            string a = word[i], b = word[j];
            //枚举两个单词的重合长度k
            for(int k = 1; k < min(a.size(), b.size()); k++)
                if(a.substr(a.size()-k, k) == b.substr(0, k))
                {
                    g[i][j] = k;
                    break;
                }
        }

    for(int i = 0; i < n; i++)
        if(word[i][0] == start)
            dfs(word[i], i);

    cout << ans;
    return 0;
}



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

核心代码
int find(int x){ //如果x不是根结点 if(p[x] != x){ //找到根节点 int tmp = find(p[x]); //d[x]表示第i个结点到其父结点的距离 d[x] += d[p[x]]; //把他的祖宗节点设为父结点 p[x] = tmp; } return p[x]; }

#include <iostream>

using namespace std;
const int N = 50010;
int n, m;
int p[N], d[N];

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

int main(){
    //初始化
    cin >> n >> m;
    //每个结点都为祖宗结点
    for(int i = 1; i <= n; i++) p[i] = i;
    //要求输出假话的总数
    int res = 0;

    //开始输入结点间的关系
    while(m--)
    {
        int t, x, y;
        cin >> t >> x >> y;

        if(x>n || y>n) res++;
        else
        {
            int px = find(x), py = find(y);
            //t == 1,表示x和y是同类
            if(t == 1)
            {
                if(px == py && (d[x] - d[y])%3)//祖宗相同,且距离相减后,取余的结果不为0,则不为同类
                    res++;
                else if(px != py)//没有相同的祖宗
                {
                    p[px] = p[y];//x的祖宗认y的祖宗为祖宗
                    d[px] = d[y] - d[x];
                }
            }
            // t == 2,表示x吃y,y是x的根节点
            else
            {
                if(px == py && (d[x] - d[y] - 1)%3)
                    res++;
                else if(px != py){
                    p[px] = p[y];
                    d[px] = d[y] + 1 - d[x];
                }
            }
        }
    }
    printf("%d\n", res);

    return 0;
}



欧拉函数:

1∼N 中与 N 互质的数的个数被称为欧拉函数,记为 ϕ(N)。
若在算数基本定理中,N = p1^a1*p2^a2…pm^am(分解质因数)
,则:ϕ(N) = N × p1−1/p1 × p2−1/p2 × … × pm−1/pm

求1~n中,每个数的欧拉函数之和
1. 质数i的欧拉函数即为phi[i] = i-1(1~i-1均与i互质,共i-1个)

  1. phi[primes[j]*i]分两种情况:

1⃣ i%primes[j] == 0
primes[j]就是i的最小质因子,也是i*primes[j]的最小质因子,
这一项在phi[i]中已经计算过了,只需要将 N 修正为 primes[j] 倍,
即 phi[i] * primes[j]

2⃣ i%primes[j] != 0
primes[j]不是i的最小质因子,但是是i*primes[j]的最小质因子
不仅需要将 N 修正为 primes[j] 倍,还需要补上 (primes[j] - 1)/primes[j]
所以这项的结果为 phi[i] * (primes[j] - 1)

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1e6+10;
int primes[N], cnt;
bool st[N];
int phi[N];


void isPrime(int n){
    phi[1] = 1;
    for(int i = 2; i <= n; i++){
        if(!st[i]){
            primes[cnt++] = i;
            phi[i] = i-1;
        }

        for(int j = 0; primes[j] <= n/i; j++){
            st[i*primes[j]] = true;
            if(i%primes[j] == 0){
                phi[i*primes[j]] = phi[i] * primes[j];
                break;
            }
            phi[i*primes[j]] = phi[i] * (primes[j] - 1);
        }
    }
}

int main(){
    int n;
    cin >> n;

    isPrime(n);
    long long res = 0;
    for(int i = 1; i <= n; i++) res += phi[i];
    cout << res;
    return 0;
}



n的二进制表示中,第k位是几?
1. (右移运算)把n的第k位数字移到个位 n >> k
2. 看一下个位是几 x&1
3. 即:x >> k & 1;

lowbit(x): 返回x的最后一位1
例如:x = 101000, lowbit(x)返回1000
表达式: x&-x = x&(~x+1)
x = 1010…1000, ~x = 0101…0111, ~x+1 = 0101…1000
x&~x+1 = 0000…1000

求二进制中1的个数
用lowbit求出x的最后一位1
x每次减去x的最后一位1
减了多少次,就说明里面有多少位1

#include <iostream>

using namespace std;

int lowbit(int x){
    return x&-x;
}

int main(){
    int n;
    cin >> n;
    while(n--){
        int x;
        cin >> x;

        int res = 0;
        while(x) x -= lowbit(x), res++;

        cout << res << ' ';
    }
    return 0;
}