头像

繁花似锦

南京理工大学




在线 


活动打卡代码 AcWing 2816. 判断子序列

繁花似锦
4小时前
#include <iostream>

using namespace std;

const int N = 100010;

int n,m;
int a[N],b[N];

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

    int i = 0,j = 0;
    while(j < m)
    {
        if(a[i] == b[j]){
            i ++;
        }
        j ++ ;
    }
    if(i == n) cout <<"Yes";
    else cout << "No";

    return 0;
}


活动打卡代码 AcWing 1341. 十三号星期五

繁花似锦
5小时前

考点:枚举,模拟

y总的手法,优美啊,学习

#include <iostream>

using namespace std;

int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int weekday[7];

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

    int year = 1900, days = 0;
    while(n -- )
    {
        for(int i = 1;i <= 12;i ++ )
        {
            weekday[(days + 12) % 7] ++ ; // 每个月的13号
            days += month[i];
            if(i == 2)
                if(year % 4 == 0 && year % 100 || year % 400 == 0) // 判断闰年
                    days ++;
        }
        year ++;
    }

    for(int i = 5, j = 0;j < 7;i ++, j ++ ) // j用来控制循环次数
        cout << weekday[i % 7] <<" ";

    return 0;
}


活动打卡代码 AcWing 1532. 找硬币

扩展题

  1. 2816. 判断子序列(双指针,已做)
  2. 1236. 递增三元组

算法1:哈希表 $O(n)$

写法1:unordered_set

#include <iostream>
#include <unordered_set>

using namespace std;

int n,m;
int v1 = 1e9,v2;

int main()
{
    unordered_set<int> hash;
    cin >> n >> m;
    for(int i = 0;i < n;i ++ )
    {
        int a;
        cin >> a;
        int b = m - a;
        if(hash.count(b))
        {
            if(a > b) swap(a,b);
            if(a < v1) v1 = a,v2 = b;
        }
        hash.insert(a);
    }

    if(v1 == 1e9) cout << "No Solution" << endl;
    else cout << v1 << ' ' << v2;

    return 0;
}

写法2:unordered_map
注意点:相等的时候判断个数是否够

#include <iostream>
#include <unordered_map>

using namespace std;

const int N = 100010;

int n,m;
unordered_map<int,int> cnt;
int v1 = 1e9,v2;
int w[N];

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

    for(int i = 0;i < n;i ++ )
    {
        int a = w[i], b = m - a;
        if(a > b) continue;
        if(a != b && cnt[b] >= 1 || a == b && cnt[b] >= 2)
        {
            if(a < v1) v1 = a,v2 =b;
        }
    }

    if(v1 == 1e9) cout <<"No Solution";
    else cout << v1 << ' ' << v2;

    return 0;
}

算法2:排序 + 双指针 $O(nlogn)$

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n,m;
int w[N];

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

    for(int i = 0, j = n - 1;i < j ;i ++ )
    {
        while(i < j && w[i] + w[j] > m) j -- ;
        if(i < j && w[i] + w[j] == m)
        {
            cout << w[i] <<" " << w[j] << endl;
            return 0;
        }
    }
    cout <<"No Solution";

    return 0;
}


活动打卡代码 AcWing 1208. 翻硬币

考点

递推$O(n)$

扩展题

  1. 95. 费解的开关$O(n * n ^ 2)$
  2. 208. 开关问题$O(n ^ 6)$(高斯消元)
#include <iostream>

using namespace std;

int main()
{
    string s1,s2;
    cin >> s1 >> s2;
    int res = 0;
    for(int i = 0;i < s1.size() - 1;i ++ )
    {
        if(s1[i] != s2[i]){
            res ++;
            s1[i + 1] = s1[i + 1] == 'o' ? '*' : 'o';
        }
    }

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 429. 奖学金

考点:多关键字排序

自定义比较函数

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 310;

struct Student{
    int id;
    int chinese, math, English;
    int sum;
}stu[N];
int n;

bool cmp(Student &a,Student &b)
{
    if(a.sum != b.sum) return a.sum > b.sum;
    else if(a.chinese != b.chinese) return a.chinese > b.chinese;
    return a.id < b.id;
}

int main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++ ) {
        int x,y,z;
        cin >> x >> y >> z;
        stu[i] = {i,x,y,z,x + y + z};
    }

    sort(stu + 1,stu + 1 + n,cmp);

    for(int i = 1;i <= 5;i ++ ){
        cout << stu[i].id << ' ' << stu[i].sum << endl;
    }

    return 0;
}

重载小于号

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 310;

struct Student{
    int id;
    int chinese, math, English;
    int sum;
    bool operator<(const Student& b) const
    {
        if(sum != b.sum) return sum > b.sum;
        else if(chinese != b.chinese) return chinese > b.chinese;
        return id < b.id;
    }
}stu[N];
int n;

bool cmp(Student a,Student b)
{

}

int main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++ ) {
        int x,y,z;
        cin >> x >> y >> z;
        stu[i] = {i,x,y,z,x + y + z};
    }

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

    for(int i = 1;i <= 5;i ++ ){
        cout << stu[i].id << ' ' << stu[i].sum << endl;
    }

    return 0;
}

lambda表达式写法

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 310;

struct Student{
    int id;
    int chinese, math, English;
    int sum;
}stu[N];
int n;


int main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++ ) {
        int x,y,z;
        cin >> x >> y >> z;
        stu[i] = {i,x,y,z,x + y + z};
    }

    sort(stu + 1,stu + 1 + n,[](Student &a,Student &b){
        if(a.sum != b.sum) return a.sum > b.sum;
        else if(a.chinese != b.chinese) return a.chinese > b.chinese;
        return a.id < b.id;
    });

    for(int i = 1;i <= 5;i ++ ){
        cout << stu[i].id << ' ' << stu[i].sum << endl;
    }

    return 0;
}



三分套三分

求$ z = x ^ 2 + y ^2 $的最小值,根据多元函数求偏导,二阶导数大于0,凹函数,存在最小值,有多元函数微分学味了。
固定x,三分求y,一般这样求多个变量的,一般可以先固定一个!

一行语句实现浮点数的四舍五入printf("%d",(int)(check(l) + 0.5)); // 浮点数四舍五入,学到了!
参考资料
时间复杂度$O(logn * logn * n)$

#include <iostream>
#include <cmath>

using namespace std;

const int N = 110;

#define eps 1e-4

int n;
int x[N],y[N];

double dis(double x1,double y1)
{
    double sum = 0.0;
    for(int i =0;i < n;i ++ )
        sum += sqrt((x[i] - x1)*(x[i] - x1) + (y[i] - y1)*(y[i] - y1));
    return sum;
}

double check(double x1) // 三分y,x和y都是凹函数,结构一样
{
    double l = 0.0,r = 10000.0;
    while(r - l > eps)
    {
        double mid = (l + r) / 2;
        double mmid = (mid + r) / 2;
        if(dis(x1, mid) > dis(x1, mmid)) l = mid;
        else r = mmid; // 这里是r = mmid;
    }
    return dis(x1,l);
}

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

    double l = 0.0,r = 10000.0;
    while(r - l > eps)  // 三分x
    {
        double mid = (l + r) / 2;
        double mmid = (mid + r) / 2;
        if(check(mid) > check(mmid)) l = mid;
        else r = mmid; // 这里是r = mmid;
    }

    printf("%d",(int)(check(l) + 0.5)); // 浮点数四舍五入,学到了!

    return 0;
}



三分

不严谨的总结

参考资料:
洛谷 P3382(三分查找凹点和凸点)
AcWing 104. 货仓选址(三分法)
三分法求函数极值(复习)

凸函数

    while(r - l > eps)
    {
        double mid = (l + r) / 2;
        double mmid = (mid + r) / 2;
        if(check(mid) > check(mmid) ) r = mmid;
        else l = mid;
    }

凹函数

 while(l < r - 1) // l < r - 1 ?
    {
        int mid = (l + r) / 2;
        int mmid = (mid + r) / 2;
        if(check(mid) > check(mmid)) l = mid;
        else r = mmid;
    }

13.jpg

  1. 凸函数 P3382 【模板】三分法
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 15;

#define eps 1e-7

int n;
double l,r;
double a[N]; // 系数

double check(double x)
{
    double ans = 1, sum = 0;
    for(int i = n + 1 ;i >= 1;i -- )
    {
        sum += ans * a[i];
        ans *= x;
    }
    return sum;
}

int main()
{
    cin >> n >> l >> r;
    for(int i = 1;i <= n + 1;i ++ ) cin >> a[i];

    while(r - l > eps)
    {
        double mid = (l + r) / 2;
        double mmid = (mid + r) / 2;
        if(check(mid) > check(mmid) ) r = mmid;
        else l = mid;
    }

    printf("%.5lf",l);

    return 0;

}
  1. 凹函数 104. 货仓选址
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N];

int check(int x)
{
    int res = 0;
    for(int i = 0 ;i < n;i ++ ) res += abs(a[i] - x);
    return res;
}

int main()
{
    cin >> n;
    for(int i = 0 ;i < n;i ++ ) cin >> a[i];
    sort(a, a + n);
    int l = a[0], r = a[n - 1];
    while(l < r - 1) // l < r - 1 ?
    {
        int mid = (l + r) / 2;
        int mmid = (mid + r) / 2;
        if(check(mid) > check(mmid)) l = mid;
        else r = mmid;
    }
    cout << min(check(l),check(r)) << endl;

    return 0;
}


活动打卡代码 AcWing 422. 校门外的树

区间合并 $O(MlogM)$, M 为区间的数量

模板题 - 803. 区间合并
扩展题 - 1343. 挤牛奶

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

const int N = 110;

int n,m;
PII seg[N];

int main()
{
    cin >> m >> n;
    for(int i = 0;i < n;i ++ ) cin >> seg[i].first >> seg[i].second;
    sort(seg,seg + n); // 区间合并要先排序

    int st = seg[0].first, ed = seg[0].second;
    int res = m + 1; // 总共有m+1棵树
    for(int i = 1;i < n;i ++ )
    {
        if(seg[i].first <= ed){
            ed = max(ed,seg[i].second);
        }else{
            res -= ed - st + 1;
            st = seg[i].first, ed = seg[i].second;
        }
    }

    res -= ed - st + 1; // 减去最后一段
    cout << res << endl;

    return 0;
}

枚举 $O(ML)$

#include <iostream>

using namespace std;

const int N = 100010;

int l,m;
int a[N];

int main()
{
    cin >> l >> m;
    while(m -- )
    {
        int x,y;
        cin >> x >> y;
        for(int i = x ;i <= y;i ++) a[i] = 1;
    }
    int res = 0;
    for(int i = 0; i<= l;i ++ ) 
        if(!a[i]) res ++;
    cout << res << endl;
}



考点:flood fill算法找连通块

注意点:
1. 输入g[][]是字符数组,判断的时候是‘1’
2. 输出格式

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

int T;
int R,C;
char g[N][N]; // 输入g[][]是字符数组,判断的时候是'1'
bool st[N][N];
int op;
int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};

void dfs(int x,int y) 
{
    st[x][y] = 1;
    for(int i = 0;i < 4;i ++ )
    {
        int a = x + dx[i],b = y + dy[i];
        if(a >= 0 && a < R && b >= 0 && b < C && g[a][b] == '1' && !st[a][b])
            dfs(a,b);
    }
}

int query()
{
    memset(st,0,sizeof st);
    int cnt = 0;
    for(int i = 0;i <R;i ++ )
        for(int j = 0;j < C;j ++)
            if(g[i][j] == '1' && !st[i][j])
            {
                cnt ++ ;
                dfs(i,j);
            }
    return cnt;
}



int main()
{
    cin >> T;
    for(int k = 1;k <= T;k ++ )
    {
        cin >> R >> C;
        for(int i = 0;i < R;i ++ ) cin >> g[i];

        //for(int i = 0;i < R;i ++ ) cout << g[i] << endl;

        cin >> op;
        bool is_cout = false; // 输出格式
        for(int i = 1;i <= op;i ++ )
        {
            char c;
            cin >> c;
            if(c == 'Q')
            {
                if(!is_cout) printf("Case #%d:\n",k), is_cout = true;
                printf("%d\n",query());
            }else{
                int x,y,z;
                cin >> x >> y >> z;
                if(z == 1) g[x][y] = '1';
                else g[x][y] = '0';
            }
        }
    }

    return 0;
}


活动打卡代码 AcWing 1227. 分巧克力

考点

整数二分

扩展题

  1. 789. 数的范围
  2. 22. 旋转数组的最小数字,不具有单调性,但具有二段性
  3. 113. 特殊排序,没有单调性,但可以二分
#include <iostream>

using namespace std;

const int N = 100010;

int n,k;
int h[N],w[N];

bool check(int mid)
{
    int res = 0;
    for(int i = 0;i < n;i ++) res += (h[i] / mid) * (w[i] / mid);
    return res >= k;
}

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

    int l = 0, r = 1e5;
    while(l < r)
    {
        int mid = l + r  + 1 >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << r << endl;

    return 0;
}