头像

焦亚硫酸钠




离线:13小时前


最近来访(2)
用户头像
浔阳の川崎
用户头像
yxc

活动打卡代码 AcWing 2014. 岛

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int N = 100010;
int n;
int h[N];
typedef pair<int, int> PII;
PII q[N];
#define x first
#define y second
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &h[i]);
    n = unique(h + 1, h + 1 + n) - h - 1;//把读入的高度相邻的都去重,相当于合为一个
    h[n + 1] = 0;//后面可能会用到,去重以后n会变小理论上最右边的山右边的位置没有山高度为0
    for (int i = 1; i <= n; i++)
        q[i] = { h[i],i };//把高度和对应的下标存到q中
    sort(q + 1, q + 1 + n);
    int ans = 1, ls = 1;//正在处理每一个山的时候可能没有把相同高度的处理完,先存到ls中,等到处理完才能更新(水对于同一高度是同步上升的)
    for (int i = 1; i <= n; i++)
    {
        int xb = q[i].y;
        //当前点的实际对应的岛高度和左右高度比较
        if (h[xb] > h[xb - 1] && h[xb]> h[xb + 1])//如果当前下标的高度比左右都高
        {
            ls--;
        }
        else if (h[xb] < h[xb - 1] && h[xb] < h[xb + 1])//如果当前下标的高度比左右地低
        {
            ls++;
        }
        if (q[i].x != q[i + 1].x)//需要处理的高度按顺序
        {
            //当前需要处理的高度和下一个需要处理的高度不同说明
            ans = max(ans, ls);
        }
    }
    printf("%d", ans);

    return 0;
}



#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int N = 100010;
int n;
int h[N];
typedef pair<int, int> PII;
PII q[N];
#define x first
#define y second
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &h[i]);
    n = unique(h + 1, h + 1 + n) - h - 1;//把读入的高度相邻的都去重,相当于合为一个
    h[n + 1] = 0;//后面可能会用到,去重以后n会变小理论上最右边的山右边的位置没有山高度为0
    for (int i = 1; i <= n; i++)
        q[i] = { h[i],i };//把高度和对应的下标存到q中
    sort(q + 1, q + 1 + n);
    int ans = 1, ls = 1;//正在处理每一个山的时候可能没有把相同高度的处理完,先存到ls中,等到处理完才能更新(水对于同一高度是同步上升的)
    for (int i = 1; i <= n; i++)
    {
        int xb = q[i].y;
        //当前点的实际对应的岛高度和左右高度比较
        if (h[xb] > h[xb - 1] && h[xb]> h[xb + 1])//如果当前下标的高度比左右都高
        {
            ls--;
        }
        else if (h[xb] < h[xb - 1] && h[xb] < h[xb + 1])//如果当前下标的高度比左右地低
        {
            ls++;
        }
        if (q[i].x != q[i + 1].x)//需要处理的高度按顺序
        {
            //当前需要处理的高度和下一个需要处理的高度不同说明
            ans = max(ans, ls);
        }
    }
    printf("%d", ans);

    return 0;
}


活动打卡代码 AcWing 2060. 奶牛选美

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int N = 55;
int n, m;
char mp[N][N];
typedef pair<int, int> PII;
vector<PII> points[2];
#define l first
#define r second
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
void dfs(int x, int y, vector<PII>& ps)//传过来一个引用直接对一块的X进行修改
{
    mp[x][y] = '.';//为了避免重复搜索,把找过的点改成'.'
    ps.push_back({ x,y });//把一块的点全部存到一个vector中
    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 && mp[a][b] == 'X')
            dfs(a, b, ps);
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)cin >> mp[i];//把地图读进来,用cin一行一行的读
    for (int i = 0,k=0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (mp[i][j] == 'X')
                dfs(i, j, points[k++]);//因为在dfs中会把一块的X全部找完所以只会在points的前两个数组中存数据
        }
    }
    int ans = 0x3f3f3f3f;
    for (auto &a:points[0])//遍历第一块的点
    {
        for (auto &b:points[1])//遍历第二块的点
        {
            ans = min(ans, abs(a.l - b.l) + abs(a.r - b.r) - 1);//更新最小距离
        }
    }
    cout << ans;
    return 0;
}



#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int N = 55;
int n, m;
char mp[N][N];
typedef pair<int, int> PII;
vector<PII> points[2];
#define l first
#define r second
int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
void dfs(int x, int y, vector<PII>& ps)//传过来一个引用直接对一块的X进行修改
{
    mp[x][y] = '.';//为了避免重复搜索,把找过的点改成'.'
    ps.push_back({ x,y });//把一块的点全部存到一个vector中
    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 && mp[a][b] == 'X')
            dfs(a, b, ps);
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)cin >> mp[i];//把地图读进来,用cin一行一行的读
    for (int i = 0,k=0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (mp[i][j] == 'X')
                dfs(i, j, points[k++]);//因为在dfs中会把一块的X全部找完所以只会在points的前两个数组中存数据
        }
    }
    int ans = 0x3f3f3f3f;
    for (auto &a:points[0])//遍历第一块的点
    {
        for (auto &b:points[1])//遍历第二块的点
        {
            ans = min(ans, abs(a.l - b.l) + abs(a.r - b.r) - 1);//更新最小距离
        }
    }
    cout << ans;
    return 0;
}


活动打卡代码 AcWing 2041. 干草堆

#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_set>
using namespace std;
typedef long long int ll; 
int a[1000010];
int b[1000010];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        a[l]++;
        a[r+1]--;
    }
    for (int i = 1; i <= n; i++)
    {
        b[i] = b[i - 1]+a[i];
    }
    sort(b + 1, b + 1 + n);
    cout << b[(n + 1) / 2] << endl;
    return 0;
}


活动打卡代码 AcWing 2058. 笨拙的手指

#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_set>
using namespace std;
typedef long long int ll; 
unordered_set<int> s;
int get(string s, int b)//秦九韶算法将b进制的s转换为10进制
{
    int res = 0;
    for (auto c: s)//从最高位遍历s
    {
        res = res * b + c - '0';//秦九韶算法
    }
    return res;
}
int main()
{
    string a, b;
    cin >> a>> b;
    for (auto &c : a)//遍历a
    {
        c ^= 1;//当前位置写错,异或成另一个数
        s.insert(get(a, 2));//把转换过去的十进制数存到哈希表中
        c ^= 1;//异或回来
    }
    for (auto &c : b)
    {
        int t = c;//原本的数存到t中
        for (int i = 0; i < 3; i++)//遍历c的3中情况
        {
            if (i + '0' != t)//原本的数不是i的值
            {
                c = i + '0';//把c存为可能错的数
                int x = get(b, 3);//把改过以后的3进制数存到x当中
                if (s.count(x))
                {
                    cout << x << endl;//如果2进制中x出现过那么直接输出
                    return 0;
                }
            }
        }
        c = t;//再把c变回去
    }
    return 0;
}



#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_set>
using namespace std;
typedef long long int ll; 
unordered_set<int> s;
int get(string s, int b)//秦九韶算法将b进制的s转换为10进制
{
    int res = 0;
    for (auto c: s)//从最高位遍历s
    {
        res = res * b + c - '0';//秦九韶算法
    }
    return res;
}
int main()
{
    string a, b;
    cin >> a>> b;
    for (auto &c : a)//遍历a
    {
        c ^= 1;//当前位置写错,异或成另一个数
        s.insert(get(a, 2));//把转换过去的十进制数存到哈希表中
        c ^= 1;//异或回来
    }
    for (auto &c : b)
    {
        int t = c;//原本的数存到t中
        for (int i = 0; i < 3; i++)//遍历c的3中情况
        {
            if (i + '0' != t)//原本的数不是i的值
            {
                c = i + '0';//把c存为可能错的数
                int x = get(b, 3);//把改过以后的3进制数存到x当中
                if (s.count(x))
                {
                    cout << x << endl;//如果2进制中x出现过那么直接输出
                    return 0;
                }
            }
        }
        c = t;//再把c变回去
    }
    return 0;
}


活动打卡代码 AcWing 1010. 拦截导弹

#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int mp[N], dp[N], g[N];
int main()
{
    int t = 1, res = 0;
    while (cin >> mp[t])t++;//全部读进来
    t--;
    for (int i = t; i >= 1; i--)//遍历求最长下降子序列
    {
        dp[i] = 1;
        for (int j = t; j > i; j--)
        {
            if (mp[i] >= mp[j])
                dp[i] = max(dp[i], dp[j] + 1);
        }
        res = max(res, dp[i]);
    }
    cout << res << endl;
    int cnt = 0;
    for (int i = 1; i <= t; i++)//从第一个物品开始遍历
    {
        int k = 0;//遍历所有的下降序列
        while (k < cnt && g[k] < mp[i]) k++;//如果下降序列还合法,并且如果下降序列的最小值仍比当前值大就继续往后遍历
        g[k] = mp[i];//把当前位置放入当前值
        if (k >= cnt)cnt++;//如果所有下降序列的最小值都比当前值小就重新开一个下降序列
    }
    cout << cnt << endl;
    return 0;
}



#include <bits/stdc++.h>
using namespace std;
const int N = 5010;
int mp[N], dp[N];
int main()
{
    int n,res=0;
    cin >> n;
    for (int i = 1; i <= n; i++)scanf("%d", &mp[i]);
    for (int i = 1; i <= n; i++)
    {
        dp[i] = mp[i];
        for (int j = 1; j < i; j++)
        {
            if (mp[i] > mp[j])
                dp[i] = max(dp[i], dp[j] + mp[i]);
        }
        res = max(res, dp[i]);
    }
    cout << res;
    return 0;
}


活动打卡代码 AcWing 1012. 友好城市

#include <bits/stdc++.h>
using namespace std;
const int N=5010;
int n;
int dp[N];
pair<int,int> mp[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d%d",&mp[i].first,&mp[i].second);
    sort(mp+1,mp+1+n);
    int res=0;
    for(int i=1;i<=n;i++)
    {
        dp[i]=1;
        for(int j=1;j<i;j++)
        {
            if(mp[i].second>mp[j].second)
                dp[i]=max(dp[i],dp[j]+1);
        }
        res=max(res,dp[i]);
    }
    cout<<res;
    return 0;
}