头像

wsh_

九江学院




离线:46秒前


最近来访(229)
用户头像
tonngw
用户头像
BT7274
用户头像
ZPOP
用户头像
AcWing2AK
用户头像
gAg
用户头像
123_34
用户头像
Cisyam_4
用户头像
@_55
用户头像
小猪软糖z
用户头像
鼠鼠
用户头像
wanghai673
用户头像
yxc
用户头像
hujiajia
用户头像
人间小甜瓜
用户头像
梦忆晴天
用户头像
被遺忘的回憶_0
用户头像
Behappyeveryday
用户头像
五心先生
用户头像
Shanjw
用户头像
小白_50


wsh_
7小时前
博客:https://blog.csdn.net/qq_61935738/article/details/125468075
/*
解题思路:
1:算出每个小岛在海岸线能被雷达探测到的范围
2:将每个小岛所覆盖的范围的区间进行右端点从小到大排序
3:如果当前区间包含最后一个选择的点,则直接跳过;
4:如果当前区间不包含最后一个选择的点,则在当前区间的右端点的位置选一个新的点

*/
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<double, double> PII;

const int N = 1010;

PII seg[N];

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

    bool fail = false;//判断雷达是否可以探测
    for (int i = 0; i < n; i ++ )
    {
        int x, y;
        scanf("%d %d", &x, &y);
        if (y > d)//说明雷达探测不到
        {
            fail = true;
            break;
        }
        auto len = sqrt(d * d - y * y);
        seg[i] = {x + len, x - len};//计算每个小岛在海岸线能被雷达探测到的范围
    }//seg.first为右端点。

    if (fail) puts("-1");
    else
    {
        sort(seg, seg + n);//右端点排序

        int ans = 0;
        double last = -1e20;
        for (int i = 0; i < n; i ++ )
        {
            if (last < seg[i].second)//若如果当前区间[seg[i].first, seg[i].second]不包含最后一个选择的点
            {//则开新的点并重新更新右端点
                ans ++ ;
                last = seg[i].first;
            }
        }

        cout << ans << endl;
    }


    return 0;
}


活动打卡代码 AcWing 112. 雷达设备

wsh_
7小时前
/*
解题思路:
1:算出每个小岛在海岸线能被雷达探测到的范围
2:将每个小岛所覆盖的范围的区间进行右端点从小到大排序
3:如果当前区间包含最后一个选择的点,则直接跳过;
4:如果当前区间不包含最后一个选择的点,则在当前区间的右端点的位置选一个新的点

*/
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<double, double> PII;

const int N = 1010;

PII seg[N];

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

    bool fail = false;//判断雷达是否可以探测
    for (int i = 0; i < n; i ++ )
    {
        int x, y;
        scanf("%d %d", &x, &y);
        if (y > d)//说明雷达探测不到
        {
            fail = true;
            break;
        }
        auto len = sqrt(d * d - y * y);
        seg[i] = {x + len, x - len};//计算每个小岛在海岸线能被雷达探测到的范围
    }//seg.first为右端点。

    if (fail) puts("-1");
    else
    {
        sort(seg, seg + n);//右端点排序

        int ans = 0;
        double last = -1e20;
        for (int i = 0; i < n; i ++ )
        {
            if (last < seg[i].second)//若如果当前区间[seg[i].first, seg[i].second]不包含最后一个选择的点
            {//则开新的点并重新更新右端点
                ans ++ ;
                last = seg[i].first;
            }
        }

        cout << ans << endl;
    }


    return 0;
}


活动打卡代码 AcWing 111. 畜栏预定

wsh_
8小时前
博客;https://blog.csdn.net/qq_61935738?spm=1010.2135.3001.5421
/*
解题思路:
1:先将吃草区间按左端点排序
2:若当前枚举的区间有交集,用小根堆记录当前最后一头牛的吃草结束区间;
3:若无交集,说明可以从之前枚举过的区间中选择右端点的最小值;
为什么选择最小值呢?
因为如果选择大于最小值的值,则它的右交点可能与当前枚举的区间有交集,使得
答案偏大,因此必须选择最小值,即小根堆的堆顶元素
*/
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

const int N = 50010;

typedef pair<int, int> PII;

int n;
int id[N];//id[i]为第i头牛所在的畜栏为id[i];
pair<PII, int> cows[N];//三个变量分别为吃草开始的时间,吃草结束的时间,以及当前牛是第几个牛

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d %d", &l, &r);
        cows[i].y = i;
        cows[i].x.x = l;
        cows[i].x.y = r;
    }

    sort(cows, cows + n);

    priority_queue<PII, vector<PII>, greater<PII>> heap;

    for (int i = 0; i < n; i ++ )
    {
        if (heap.empty() || heap.top().x >= cows[i].x.x)//若当前堆中为空,或者枚举过的区间的最小值大于等于
        {//当前区间的左端点,则需要新加一个畜栏,即将次畜栏加入堆中
            PII stall = {cows[i].x.y, heap.size()};
            id[cows[i].y] = stall.y;
            heap.push(stall);
        }
        else//说明枚举过的区间的右端点的最小值大于当前左区间最小值,即安排进以前枚举过的右端点最小值的畜栏
        {
            PII stall = heap.top();//将右端点的最小值拿出
            heap.pop();//删去最小值;
            stall.x = cows[i].x.y;//更新右端点的最小值
            id[cows[i].y] = stall.y;
            heap.push(stall);
        }
    }

    cout << heap.size() << endl;//heap.size()里面即存了可以选择的畜栏
    for (int i = 0; i < n; i ++ ) printf("%d\n", id[i] + 1);//因为heap.size()从0开始所以每个树要加一

    return 0;
}


活动打卡代码 AcWing 111. 畜栏预定

wsh_
8小时前
/*
解题思路:
1:先将吃草区间按左端点排序
2:若当前枚举的区间有交集,用小根堆记录当前最后一头牛的吃草结束区间;
3:若无交集,说明可以从之前枚举过的区间中选择右端点的最小值;
为什么选择最小值呢?
因为如果选择大于最小值的值,则它的右交点可能与当前枚举的区间有交集,使得
答案偏大,因此必须选择最小值,即小根堆的堆顶元素
*/
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define x first
#define y second

using namespace std;

const int N = 50010;

typedef pair<int, int> PII;

int n;
int id[N];//id[i]为第i头牛所在的畜栏为id[i];
pair<PII, int> cows[N];//三个变量分别为吃草开始的时间,吃草结束的时间,以及当前牛是第几个牛

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d %d", &l, &r);
        cows[i].y = i;
        cows[i].x.x = l;
        cows[i].x.y = r;
    }

    sort(cows, cows + n);

    priority_queue<PII, vector<PII>, greater<PII>> heap;

    for (int i = 0; i < n; i ++ )
    {
        if (heap.empty() || heap.top().x >= cows[i].x.x)//若当前堆中为空,或者枚举过的区间的最小值大于等于
        {//当前区间的左端点,则需要新加一个畜栏,即将次畜栏加入堆中
            PII stall = {cows[i].x.y, heap.size()};
            id[cows[i].y] = stall.y;
            heap.push(stall);
        }
        else//说明枚举过的区间的右端点的最小值大于当前左区间最小值,即安排进以前枚举过的右端点最小值的畜栏
        {
            PII stall = heap.top();//将右端点的最小值拿出
            heap.pop();//删去最小值;
            stall.x = cows[i].x.y;//更新右端点的最小值
            id[cows[i].y] = stall.y;
            heap.push(stall);
        }
    }

    cout << heap.size() << endl;//heap.size()里面即存了可以选择的畜栏
    for (int i = 0; i < n; i ++ ) printf("%d\n", id[i] + 1);//因为heap.size()从0开始所以每个树要加一

    return 0;
}



wsh_
22小时前
博客:https://blog.csdn.net/qq_61935738/article/details/125463439?spm=1001.2014.3001.5501
/*
解题思路:1:区间按左端点递减排序
2:spf按递减排序
3:选出spf中小于等于区间右端点的最大值
*/
#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 2510;

PII cow[N];
map<int, int> spfs;

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
    {
        int x, y;
        scanf("%d %d", &x, &y);
        cow[i] = {x, y};
    }

    sort(cow, cow + n);

    for (int i = 0; i < m; i ++ )
    {
        int spf, cover;
        scanf("%d %d", &spf, &cover);
        spfs[spf] += cover;//可能重复出现
    }

    int res = 0;
    spfs[0] = spfs[1001] = n;//哨兵:spf最低为1, 最高为1000
                            //将spf为0,1001定义为n是因为循环最多比较n次
    for (int i = n - 1; i >= 0; i -- )
    {
        auto spf = spfs.upper_bound(cow[i].second);//找出spfs中大于右端点的最小值
        spf -- ;//map数据结构自动排序,所以spfs从小到大排序,所以spf -- 是找出spfs中小于等于右端点的最大值

        if (spf -> first >= cow[i].first)//若在范围内
        {
            res ++ ;
            if (-- spf -> second == 0) spfs.erase(spf);//若用完了
        }
    }

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 110. 防晒

wsh_
22小时前
/*
解题思路:1:区间按左端点递减排序
2:spf按递减排序
3:选出spf中小于等于区间右端点的最大值
*/
#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 2510;

PII cow[N];
map<int, int> spfs;

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
    {
        int x, y;
        scanf("%d %d", &x, &y);
        cow[i] = {x, y};
    }

    sort(cow, cow + n);

    for (int i = 0; i < m; i ++ )
    {
        int spf, cover;
        scanf("%d %d", &spf, &cover);
        spfs[spf] += cover;//可能重复出现
    }

    int res = 0;
    spfs[0] = spfs[1001] = n;//哨兵:spf最低为1, 最高为1000
                            //将spf为0,1001定义为n是因为循环最多比较n次
    for (int i = n - 1; i >= 0; i -- )
    {
        auto spf = spfs.upper_bound(cow[i].second);//找出spfs中大于右端点的最小值
        spf -- ;//map数据结构自动排序,所以spfs从小到大排序,所以spf -- 是找出spfs中小于等于右端点的最大值

        if (spf -> first >= cow[i].first)//若在范围内
        {
            res ++ ;
            if (-- spf -> second == 0) spfs.erase(spf);//若用完了
        }
    }

    cout << res << endl;

    return 0;
}



wsh_
1天前
博客地址:https://blog.csdn.net/qq_61935738/article/details/125461607?spm=1001.2014.3001.5502
/*
大概思路:
使用倍增的方法先求出区间[L, L + len]的校验值
若成立则令L += len , len <<= 1
若不成立则令len >>= 1直到len为0循环结束

每对数的差的平方”之和最大因此要使它最大则应该是
最小的数与最大的数配对,次小的数与次大的数配对
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 500010;

LL T;
int n, m;
int a[N], temp[N], t[N];
//a[N]为A数组,temp为归并排序中的临时数组, t[N]为当前正在倍增的数组
LL sq(int x)
{
    return (LL)x * x;
}

bool check(int l, int mid, int r)
{
    for (int i = mid; i < r; i ++ ) t[i] = a[i];//因为[l, mid)在上一轮以及被排序计算过,所以直接从mid开始

    sort(t + mid, t + r);//将t的区间排序

    int i = l, j = mid, k = 0;
    while (i < mid && j < r)//将排好序的t放入temp中,此时temp里面的数都是从小到大排序的
    {
        if (t[i] < t[j]) temp[k ++ ] = t[i ++ ];
        else temp[k ++ ] = t[j ++ ];
    }

    while (i < mid) temp[k ++ ] = t[i ++ ];
    while (j < r) temp[k ++ ] = t[j ++ ];

    LL sum = 0;
    for (int i = 0; i < m && i < k; i ++, k -- )//检查校验值是否符合要求,题目说了校验值是
        sum += sq(temp[i] - temp[k - 1]);       //每对数的差的平方”之和最大因此要使它最大则应该是
                                                //最小的数与最大的数配对,次小的数与次大的数配对
    return sum <= T;                            //因为temp从小到大排序因此选择第一个与最后一个配对
}

int main()
{
    int cnt;
    cin >> cnt;
    while (cnt -- )
    {
        scanf("%d %d %lld", &n, &m, &T);
        for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

        int ans = 0, len;
        int start = 0, last = 0;
        while (last < n)
        {
            len = 1;
            while (len)
            {
                if (last + len <= n && check(start, last, last + len))//判断[start, last + len)是否符合要求
                {
                    last += len, len <<= 1;//若成立利用倍增思想扩大范围

                    if (last >= n) break;//若last >= n,则last + len比大于n + 1题解结束

                    for (int i = start; i < last; i ++ )//经过check后数组temp中的[start, len]以及被排序过
                        t[i] = temp[i - start];//将他放入倍增数组t以免重复排序
                }
                else len >>= 1;//若不成立缩小范围
            }

            start = last;//当len == 0说明该区间[start, last]已选得最大区间长度的符合要求的校验值
            ans ++ ;//所以开始下一个区间的选取
        }

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


活动打卡代码 AcWing 109. 天才ACM

wsh_
1天前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 500010;

LL T;
int n, m;
int a[N], temp[N], t[N];

LL sq(int x)
{
    return (LL)x * x;
}

bool check(int l, int mid, int r)
{
    for (int i = mid; i < r; i ++ ) t[i] = a[i];

    sort(t + mid, t + r);

    int i = l, j = mid, k = 0;
    while (i < mid && j < r)
    {
        if (t[i] < t[j]) temp[k ++ ] = t[i ++ ];
        else temp[k ++ ] = t[j ++ ];
    }

    while (i < mid) temp[k ++ ] = t[i ++ ];
    while (j < r) temp[k ++ ] = t[j ++ ];

    LL sum = 0;
    for (int i = 0; i < m && i < k; i ++, k -- )
        sum += sq(temp[i] - temp[k - 1]);

    return sum <= T;
}

int main()
{
    int cnt;
    cin >> cnt;
    while (cnt -- )
    {
        scanf("%d %d %lld", &n, &m, &T);
        for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

        int ans = 0, len;
        int start = 0, last = 0;
        while (last < n)
        {
            len = 1;
            while (len)
            {
                if (last + len <= n && check(start, last, last + len))
                {
                    last += len, len <<= 1;

                    if (last >= n) break;

                    for (int i = start; i < last; i ++ )
                        t[i] = temp[i - start];
                }
                else len >>= 1;
            }

            start = last;
            ans ++ ;
        }

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



wsh_
1天前
博客地址:https://blog.csdn.net/qq_61935738/article/details/125455796?spm=1001.2014.3001.5502
/*
大概思路:将二维的奇数码转化为一维奇数码(除去0),
若当前状态与目标状态奇偶型相同则说明可以转变为目标状态
否则则不能转变为目标状态
*/
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 250010;

int cnt;//cnt为当前已记录了多少个数(除去0)
int ans1;//若当前状态与目标状态奇偶性,则说明他们的逆序对之和为偶数
int n, a[N];
int temp[N];//归并排序临时数组

void merge_sort(int l, int r)
{
    if (l >= r) return ;

    int mid = l + r >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
    {
        if (a[i] <= a[j]) temp[k ++ ] = a[i ++ ];
        else 
        {
            ans1 += mid - i + 1;
            temp[k ++ ] = a[j ++ ];
        }
    }

    while (i <= mid) temp[k ++ ] = a[i ++ ];
    while (j <= r) temp[k ++ ] = a[j ++ ];

    for (int i = l, j = 0; i <= r; i ++ , j ++ ) a[i] = temp[j];
}

int main()
{
    while (scanf("%d", &n) != EOF)
    {
        cnt = 0;
        for (int i = 0; i < n * n; i ++ )//读入当前状态的奇数码
        {
            int x;
            scanf("%d", &x);
            if (x != 0) a[cnt ++ ] = x;
        }

        ans1 = 0;
        merge_sort(0, cnt - 1);

        cnt = 0;
        for (int i = 0; i < n * n; i ++ )//读入目标状态的奇数码
        {
            int x;
            scanf("%d", &x);
            if (x != 0) a[cnt ++ ] = x;
        }

        merge_sort(0, cnt - 1);

        if (ans1 % 2) puts("NIE");//若他们的逆序对之和为偶数
        else puts("TAK");
    }

    return 0;
}


活动打卡代码 AcWing 108. 奇数码问题

wsh_
1天前
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 250010;

int cnt;
int ans1;
int n, a[N];
int temp[N];

void merge_sort(int l, int r)
{
    if (l >= r) return ;

    int mid = l + r >> 1;
    merge_sort(l, mid);
    merge_sort(mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
    {
        if (a[i] <= a[j]) temp[k ++ ] = a[i ++ ];
        else 
        {
            ans1 += mid - i + 1;
            temp[k ++ ] = a[j ++ ];
        }
    }

    while (i <= mid) temp[k ++ ] = a[i ++ ];
    while (j <= r) temp[k ++ ] = a[j ++ ];

    for (int i = l, j = 0; i <= r; i ++ , j ++ ) a[i] = temp[j];
}

int main()
{
    while (scanf("%d", &n) != EOF)
    {
        cnt = 0;
        for (int i = 0; i < n * n; i ++ )
        {
            int x;
            scanf("%d", &x);
            if (x != 0) a[cnt ++ ] = x;
        }

        ans1 = 0;
        merge_sort(0, cnt - 1);

        cnt = 0;
        for (int i = 0; i < n * n; i ++ )
        {
            int x;
            scanf("%d", &x);
            if (x != 0) a[cnt ++ ] = x;
        }

        merge_sort(0, cnt - 1);

        if (ans1 % 2) puts("NIE");
        else puts("TAK");
    }

    return 0;
}