头像

繁花似锦

南京理工大学




离线:2分钟前


最近来访(157)
用户头像
张肆蕤
用户头像
冷-离
用户头像
夏が終わる...
用户头像
Yeahhh
用户头像
zyitst
用户头像
𝓴𝓸𝓲_9
用户头像
阿白_3
用户头像
亲爱的路人
用户头像
889
用户头像
Vincent.
用户头像
Arthur_5
用户头像
ouyunfeng
用户头像
沙漠之狐
用户头像
Jery2020
用户头像
余火
用户头像
重生之我是小雪菜
用户头像
主子six
用户头像
清水洗脸
用户头像
Oceantaker
用户头像
QQ家族族长


整数二分 (二分:一定满足边界条件,但不一定满足题意!)

此题同时考察了两个模板,真模板题

另外,C++ STL现成函数 lower_bound(a,a + n ,x) 返回第一个>=x的指针,upper_bound(a,a + n,x)返回第一个 > x的指针,减去数组首地址就是下标!

#include <iostream>

using namespace std;

const int N =1e5+10;

int n,q;
int a[N];

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);

    while(q--)
    {
        int x;
        scanf("%d",&x);
        int l=0,r=n-1;
        while(l<r)
        {
            int mid=l+r>>1;
            if(a[mid]>=x) r=mid;
            else l=mid+1;
        }

        if(a[l]!=x) cout<<"-1 -1"<<endl;
        else
        {
            cout<<l<<" ";

            int l=0,r=n-1;
            while(l<r)
            {
                int mid=l+r+1>>1;           //这里l=mid的时候要+1;
                if(a[mid]<=x) l=mid;
                else r=mid-1;
            }
            cout<<l<<endl;
        }
    }


    return 0;
}

STL

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n,q;
int a[N];

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

    while(q -- )
    {
        int x;
        cin >> x;
        int l = lower_bound(a,a + n ,x) - a, r = upper_bound(a,a + n,x) - a;
        if(l ^ r) cout << l << ' ' << r  - 1 << endl;
        else cout << "-1 -1" << endl;
    }
    return 0;
}


活动打卡代码 AcWing 4078. 01串

2.jpg

/*
    读题:01字符串具体是什么不用知道,直接考虑状态

    读清题目:长度在[l, r]的优秀字符串,这里可以用前缀和考虑:S[i]长度不超过i的优秀字符串的数量
        ans = S[r] - S[l - 1];

    定义f[i] : 长度为i的优秀字符串的数量
        最后一位i为0, 那么f[i] += f[i - 1]
        最后一位i为1, f[i] += f[i - k] (条件:i >= k) 

        边界条件:f[0] = 1 (考虑让成立的值:k = 1,f[1] = 2 对应f[1]应该等于1)

        https://www.acwing.com/problem/content/4081/
*/

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

using namespace std;

const int N = 100010;

int f[N];
int mod = 1e9 + 7;
int t, k;

int main()
{
    cin >> t >> k;

    f[0] = 1;
    for(int i = 1;i < N;i ++ )
    {
        f[i] = (f[i] + f[i - 1]) % mod; // 一定存在
        if(i >= k) f[i] = (f[i] + f[i - k]) % mod;
    }

    for (int i = 1; i < N; i ++ ) f[i] = (f[i] + f[i - 1]) % mod;

    while (t -- )
    {
        int l, r;
        cin >> l >> r;
        cout << (f[r] - f[l - 1] + mod) % mod << endl; // 可能为负数,负数取模
    }
    return 0;
}



活动打卡代码 AcWing 4001. 训练

二分

条件1:当且仅当 ra > rb。 (二分int k = lower_bound(b + 1, b + n + 1, a[i]) - b - 1;或者排序)
条件2:两人之间不存在矛盾(用cnt[]来记录满足条件1 但是矛盾的个数) ,比赛时就卡在这里了

if(a[x] > a[y]) cnt[x] ++ ; // 用cnt[]来记录矛盾关系!
if(a[x] < a[y]) cnt[y] ++ ;

https://www.acwing.com/problem/content/4004/

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

using namespace std;

const int N = 200010;

int a[N], b[N], cnt[N]; // b记录 排序后的结果!
int n, k;

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

    for(int i = 1;i <= n;i ++ ) 
    {
        cin >> a[i];
        b[i] = a[i];
    }

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

    for (int i = 0; i < k; i ++ )
    {
        int x, y;
        cin >> x >> y;
        if(a[x] > a[y]) cnt[x] ++ ; // 用cnt[]来记录矛盾关系!
        if(a[x] < a[y]) cnt[y] ++ ;
    }

    for (int i = 1; i <= n; i ++ )
    {
        int k = lower_bound(b + 1, b + n + 1, a[i]) - b - 1;
        cout << k - cnt[i] << ' ';
    }
    return 0;
}


活动打卡代码 AcWing 4002. 构造数组

数学,可重复集-> 不可重复集,隔板法,求组合数

小技巧:当没有思路的时候,可以分步来做(乘法原理),其中每一步可以拆开(加法原理)

1.jpg
2.jpg
3.jpg

https://www.acwing.com/problem/content/4005/

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

using namespace std;

const int N = 1030, M = 30, mod = 1e9 + 7;

int n, m;
int C[N][M];

int main()
{
    cin >> n >> m;
    int a = n + 2 * m - 1, b = 2 * m;

    for(int i = 0;i <= a ;i ++ )
        for(int j = 0;j <= b && j <= i;j ++) // C[i][j] = C[i][i - j] // 求m小的,时间复杂度可以为nm
        {
            if(j == 0) C[i][j] = 1;
            else C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
        }

    cout << C[a][b] << endl;

    return 0;
}


活动打卡代码 AcWing 4005. 取石子游戏

https://www.acwing.com/problem/content/4008/

博弈论,找规律

2个技巧:
1. 当没有思路时,先从简单的开始考虑,比如这题中先不考虑k
2. 找规律也是不错的方法

  1. 只能取1,2
    • 当 n % 3 == 0 时,先手必败
    • 当 n % 3 != 0 时,先手必胜 (更一般的规律 n % (m + 1) == 0, 先手必败)
  2. 接下来考虑k
    • 当 k是3的倍数,找规律得到 (k + 1)个循环,灵茶山艾府 题解
      • n == k , 先手必胜
      • n < k, 按1考虑,n%3==0,先手必败
    • 当 k 不是3的倍数, 按1考虑
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n, k;

int main()
{
    int t;
    cin >> t;
    while (t -- )
    {
        cin >> n >> k;

        if(k % 3 == 0) // k 是3的倍数,(k + 1)为一个循环
        {
            n %= (k + 1);
            if(n == k) 
            {
                cout << "Alice" << endl;
                continue;
            }
        }


        if(n % 3) cout << "Alice";
        else cout << "Bob";

        cout << endl;
    }
}


活动打卡代码 AcWing 4075. 染色

// 怎么统计 并查集属性最多 的一类?

/*
    解题思路:并查集,O(n)
    有m个约束条件, 组成一堆集合,答案即为 每个集合元素个数 - 颜色出现最多的次数 = 最小操作次数
    怎么统计 每个集合中 颜色出现最多的次数? 开哈希表

    https://www.acwing.com/problem/content/description/4078/
*/

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

using namespace std;

const int N = 200010;

int n, m, k;
int c[N];
int p[N];
int cnt[N]; // 统计颜色出现的次数
vector<int> S[N]; // 记录每种颜色的集合

int find(int x)  // 并查集
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{

    cin >> n >> m >> k;
    //for (int i = 1; i <= n; i ++ ) cin >> c[i];
    for (int i = 1; i <= n; i ++ ) scanf("%d", &c[i]);

    for (int i = 1; i <= n; i ++ ) p[i] = i; // 要在n输入之后 才初始化并查集啊!!!
    while (m -- )
    {
        int a, b;
        //cin >> a >> b;
        scanf("%d%d", &a, &b);
        p[find(a)] = find(b);
    }

    for (int i = 1; i <= n; i ++ ) S[find(i)].push_back(i); // 并查集用根节点元素 代表 这个集合

    int res = 0;
    for(int i = 1; i <= n; i ++ )  
        if(S[i].size())
        {
            int t = 0; // 统计这个集合 出现颜色 最多的次数
            for(auto x : S[i]) t = max(t, ++ cnt[c[x]]);
            res += S[i].size() - t;
            for(auto x : S[i]) cnt[c[x]] -- ; // 恢复现场
        }

    //cout << res << endl;
    printf("%d\n", res);
    return 0;
}


活动打卡代码 AcWing 4074. 铁路与公路

// 如何满足约束条件: 每条路线中可重复经过同一条铁路或公路,但是为了避免发生事故,火车和汽车不得同时到达同一个城市 ?

/*
    解题思路:最短路, 时间复杂度: O(n^3)
    先不考虑约束条件,即求 两遍最短路,求max

    再思考 题目条件,1和n没有铁路,就会有公路,所以即求另一条路的最短路(需要 稍微再思考一下)
    由于n=400,所以可以写n^3的floyd算法求最短路,代码短
*/

// https://www.acwing.com/problem/content/description/4077/

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

using namespace std;

const int N = 410, INF = 0x3f3f3f3f;

int n, m;
int f[N][N], g[N][N];

int floyd(int d[][N])
{
    if(d[1][n] == 1) return 1;  // 一定有
    for(int k = 1; k <= n; k ++ )
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    return d[1][n];
}

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

    memset(f, 0x3f, sizeof f);
    memset(g, 0x3f, sizeof g);

    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        f[a][b] = f[b][a] = 1;
    }

    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ )
            if(f[i][j] == INF)
                g[i][j] = g[j][i] = 1;

    int res = max(floyd(f), floyd(g));
    if(res == INF) cout << -1;
    else cout << res;

    return 0;
}


活动打卡代码 Linux 7.9. homework_9

0

vim mydu # 没有.sh
任意路径都能执行,把目录写在 ~/.bashrc文件里,从左往右覆盖,:分割
export PATH=/home/acs/homework/lesson_7/homework_0:$PATH # 路径以:分割,从左往右匹配

1

chmod +r * -R
find . -name '*.cpp' | wc -l > ans.txt

2

find . -name '*.cpp' | xargs cat | wc -l > ans1.txt
find . -name '*.py' | xargs cat | grep thrift | wc -l > ans2.txt

3

find . -name '*.py' | xargs rm

4

cat scores.txt | cut -d ' ' -f 1 > names.txt
...

5

cat scores.txt | cut -d ' ' -f 1 | sort > names.txt

6

head -5 scores.txt > top.txt
tail -4 scores.txt > bottom.txt

7

md5sum scores.txt | cut -c 1-32 > ans.txt

8

tar -zcvf project_a.tar.gz dir_a # 压缩
tar -zxvf project_b.tar.gz # 解压

9

ipython3  # 进入ipython环境
res = 2 ** 112 + 3 ** 78 # 计算,python自带高精度
!echo $res > ans.txt # ipython里面加! 也可以执行shell命令


活动打卡代码 Linux 7.8. homework_8

0

vim mydu # 没有.sh
任意路径都能执行,把目录写在 ~/.bashrc文件里,从左往右覆盖,:分割
export PATH=/home/acs/homework/lesson_7/homework_0:$PATH # 路径以:分割,从左往右匹配

1

chmod +r * -R
find . -name '*.cpp' | wc -l > ans.txt

2

find . -name '*.cpp' | xargs cat | wc -l > ans1.txt
find . -name '*.py' | xargs cat | grep thrift | wc -l > ans2.txt

3

find . -name '*.py' | xargs rm

4

cat scores.txt | cut -d ' ' -f 1 > names.txt
...

5

cat scores.txt | cut -d ' ' -f 1 | sort > names.txt

6

head -5 scores.txt > top.txt
tail -4 scores.txt > bottom.txt

7

md5sum scores.txt | cut -c 1-32 > ans.txt

8

tar -zcvf project_a.tar.gz dir_a # 压缩
tar -zxvf project_b.tar.gz # 解压

9

ipython3  # 进入ipython环境
res = 2 ** 112 + 3 ** 78 # 计算,python自带高精度
!echo $res > ans.txt # ipython里面加! 也可以执行shell命令


活动打卡代码 Linux 7.7. homework_7

0

vim mydu # 没有.sh
任意路径都能执行,把目录写在 ~/.bashrc文件里,从左往右覆盖,:分割
export PATH=/home/acs/homework/lesson_7/homework_0:$PATH # 路径以:分割,从左往右匹配

1

chmod +r * -R
find . -name '*.cpp' | wc -l > ans.txt

2

find . -name '*.cpp' | xargs cat | wc -l > ans1.txt
find . -name '*.py' | xargs cat | grep thrift | wc -l > ans2.txt

3

find . -name '*.py' | xargs rm

4

cat scores.txt | cut -d ' ' -f 1 > names.txt
...

5

cat scores.txt | cut -d ' ' -f 1 | sort > names.txt

6

head -5 scores.txt > top.txt
tail -4 scores.txt > bottom.txt

7

md5sum scores.txt | cut -c 1-32 > ans.txt

8

tar -zcvf project_a.tar.gz dir_a # 压缩
tar -zxvf project_b.tar.gz # 解压

9

ipython3  # 进入ipython环境
res = 2 ** 112 + 3 ** 78 # 计算,python自带高精度
!echo $res > ans.txt # ipython里面加! 也可以执行shell命令