头像

Bear_King




离线:1小时前



Bear_King
1小时前

奖学金

结构体重载运算符拟定排序规则

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 310
int n;
struct Person
{
    int id , sum , a,b,c;
    bool operator< (const Person& t) const
    {
        if(sum != t.sum)    return sum > t.sum;
        if(a != t.a)    return a > t.a;
        return id < t.id;
    }
}q[N];

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

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

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

    return 0;
}

用户自定义Rules设置排序规则

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 310
int n;
struct Person
{
    int id , sum , a,b,c;
}q[N];

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

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

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

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

    return 0;
}

在C++得特性中添加了λ表达式写法

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 310
int n;
struct Person
{
    int id , sum , a,b,c;

}q[N];


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

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

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

    return 0;
}



Bear_King
23小时前

找硬币

哈希表存储查找

直接用哈希表存储并查找i-1个面额里是否存在m-ai的面额,然后更新要输出的v1为最小

时间复杂度:O(n)

#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_set>
#define INF 10000
using namespace std;

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    unordered_set<int> hash;

    int v1 = INF, v2;//v2较小值最小的方案
    //判断前面i-1个面额里面是否存在m - ai的面额->查询操作
    for(int i = 0;i < n;i ++)
    {
        int a,b;
        scanf("%d",&a);

        b = m - a;
        if(hash.count(b))//判断b(另一个数)是否存在,且a不在其中的情况下防止冲突
        {
            hash.insert(a);//先将a插到哈希表里面
            //结果要v1最小,所以要交换a为小的
            if(a > b)   swap(a,b);
            if(a < v1)  v1 = a, v2 = b;
        }
        else    hash.insert(a);
    }

    if(v1 == INF)   puts("No Solution");
    else    printf("%d %d\n",v1,v2);

    return 0;
}

双指针遍历性质

存在一个满足ai+aj >= m 的最大为: ai + aj = m
说人话:当i从左往右变大,j从右往左变小,利用单调性构建双指针

因为要满足单调性,那么少不了排序,因此时间复杂度:O(nlogn)

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

using namespace std;

const int N = 100010;

int n, m;
int w[N];

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

    for (int i = 0, j = n - 1; i < j; i ++ )//我们只需要找最小的ai结果所以就直接从小到大扫i
    {
        while (i < j && w[i] + w[j] > m) j -- ;//每一个i都从后往前扫j,找到ai+aj>m为止,且i!=j
        if (i < j && w[i] + w[j] == m)//把每一个ai+aj>m的情况作比较,查看是否等于m符合则打印
        {
            printf("%d %d\n", w[i], w[j]);
            return 0;
        }
    }

    puts("No Solution");
    return 0;
}

虽然,用哈希表时间复杂度很理想,但大多数情况下,双指针比哈希表快,毕竟unordered_set常数大




直接桶插法$O(L*n)$

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

using namespace std;

const int N = 10010;

int L, n;
bool st[N];

int main()
{
    cin >> L >> n;
    for (int i = 0; i <= L; i ++ ) st[i] = true;
    while (n -- )
    {
        int a, b;
        cin >> a >> b;
        for (int i = a; i <= b; i ++ ) st[i] = false;
    }

    int res = 0;
    for (int i = 0; i <= L; i ++ ) res += st[i];
    cout << res << endl;

    return 0;
}

贪心法:区间合并$O(nlogn)$

注意细节:不要忘记+1

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

using namespace std;

const int N = 110;

int m, n;
struct Segment
{
    int l, r;
    bool operator< (const Segment& t) const//重载小于号实现结构体数组排序规则
    {
        return l < t.l;//谁左端点小谁排前
    }
}seg[N];

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

    int sum = 0;//只要L(i) > R就再sum中记录上一个区间
    int L = seg[0].l, R = seg[0].r;
    for (int i = 1; i < n; i ++ )
        if (seg[i].l <= R) R = max(R, seg[i].r);//如果L(i)在上一个区间里则直接取两个区间最大右端点
        else
        {
            sum += R - L + 1;
            L = seg[i].l, R = seg[i].r;
        }
    sum += R - L + 1;
    cout << m + 1 - sum << endl;

    return 0;
}






数星星

创建一个树状数组存储的是当前得前面有多少个星星,用level数组存储每一行得星星数目

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 32010;
int n;
int tr[N] , level[N];//level每个横坐标下有多少个星星

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

void add(int x)
{
    for(int i = x;i <= N;i += lowbit(i)) tr[i] ++;
}

int sum(int x)
{
    int res = 0;
    for(int i = x;i;i -= lowbit(i)) res += tr[i];
    return res;
}

int main()
{
    scanf("%d",&n);
    for(int i = 0;i < n;i ++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x ++;
        level[sum(x)] ++;
        add(x);
    }

    for(int i = 0;i < n;i ++)   printf("%d\n",level[i]);
}


活动打卡代码 AcWing 1265. 数星星

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 32010;
int n;
int tr[N] , level[N];//level每个横坐标下有多少个星星

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

void add(int x)
{
    for(int i = x;i <= N;i += lowbit(i)) tr[i] ++;
}

int sum(int x)
{
    int res = 0;
    for(int i = x;i;i -= lowbit(i)) res += tr[i];
    return res;
}

int main()
{
    scanf("%d",&n);
    for(int i = 0;i < n;i ++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x ++;
        level[sum(x)] ++;
        add(x);
    }

    for(int i = 0;i < n;i ++)   printf("%d\n",level[i]);
}



树状数组操作

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100010;

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

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

void add(int x,int v)
{
    for(int i = x; i <= n ;i += lowbit(i))   tr[i] += v;
}

int query(int x)
{
    int res = 0;
    for(int i = x; i ;i -= lowbit(i))   res += tr[i];
    return res;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++)  scanf("%d",&a[i]);
    for(int i = 1;i <= n;i ++)  add(i,a[i]);//建树

    while(m --)
    {
        int k,x,y;
        scanf("%d%d%d",&k,&x,&y);
        if(k == 0)  printf("%d\n",query(y) - query(x-1));
        else    add(x,y);

    }

    return 0;
}



#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100010;

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

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

void add(int x,int v)
{
    for(int i = x; i <= n ;i += lowbit(i))   tr[i] += v;
}

int query(int x)
{
    int res = 0;
    for(int i = x; i ;i -= lowbit(i))   res += tr[i];
    return res;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i ++)  scanf("%d",&a[i]);
    for(int i = 1;i <= n;i ++)  add(i,a[i]);//建树

    while(m --)
    {
        int k,x,y;
        scanf("%d%d%d",&k,&x,&y);
        if(k == 0)  printf("%d\n",query(y) - query(x-1));
        else    add(x,y);

    }

    return 0;
}



日期问题

直接把所求段区间所有的回文序列拿出来,套上判断日期是否合法的模板,最后判断是否符合题意即可

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

using namespace std;

//模板:
int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check_valid(int year,int month,int day)
{
    if(month < 1 || month > 12)    return false;
    if(day <= 0)    return false;
    if(month != 2)//不是二月
    {    
        if(day > days[month])   return false;
    }
    else
    {
        int leap = year % 100 && year % 4 == 0 || year % 400 == 0;
        if(day > 28 + leap) return false;
    }
    return true;
}

int main()
{
    int a , b , c;
    scanf("%d/%d/%d",&a,&b,&c);

    for(int date = 19600101; date <= 20591231; date ++)
    {
        int year = date / 10000 , month = date % 10000 / 100 , day = date % 100;

        if(check_valid(year , month , day))
        {
            if (year % 100 == a && month == b && day == c ||    //年月日
                month == a && day == b && year % 100 == c ||    //月年日
                day == a && month == b && year % 100 == c)      //日月年
                printf("%d-%02d-%02d\n",year , month , day);
        }
    }


}


活动打卡代码 AcWing 1229. 日期问题

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

using namespace std;

int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

bool check_valid(int year,int month,int day)
{
    if(month < 1 || month > 12)    return false;
    if(day <= 0)    return false;
    if(month != 2)//不是二月
    {    
        if(day > days[month])   return false;
    }
    else
    {
        int leap = year % 100 && year % 4 == 0 || year % 400 == 0;
        if(day > 28 + leap) return false;
    }
    return true;
}

int main()
{
    int a , b , c;
    scanf("%d/%d/%d",&a,&b,&c);

    for(int date = 19600101; date <= 20591231; date ++)
    {
        int year = date / 10000 , month = date % 10000 / 100 , day = date % 100;

        if(check_valid(year , month , day))
        {
            if (year % 100 == a && month == b && day == c ||    //年月日
                month == a && day == b && year % 100 == c ||    //月年日
                day == a && month == b && year % 100 == c)      //日月年
                printf("%d-%02d-%02d\n",year , month , day);
        }
    }


}



移动距离

没啥可说,找规律O(1)

主要是细节处理,所有楼号自减之后,可以利用cpp向下取整得语法特性来求出行列号
#include<iostream>
using  namespace std;
const int N = 10010;
int q[N];
int w,n,m;

int main()
{
    cin>>w>>m>>n;//输入的两个楼号,减一方便计算行号,而且不影响结果
    m --,n --;
    //按题目规律来写
    int x1 = m / w , x2 = n / w;//楼号直接除以w得行号
    int y1 = m % w , y2 = n % w;//楼号取模属于正序得列号
    if(x1&1) y1 = w - 1 - y1;
    if(x2&1) y2 = w - 1 - y2;

    cout<<abs(x1-x2)+abs(y1-y2)<<endl;

    return 0;
}