投稿
  1. 高性能架构探索首页
  2. C/C++

Daliy Algorithm (greedy, 中心扩展 , 并查集)– day 89

admin • • C/C++ • 阅读 124

Nothing to fear

种一棵树最好的时间是十年前，其次是现在！

那些你早出晚归付出的刻苦努力，你不想训练，当你觉的太累了但还是要咬牙坚持的时候，那就是在追逐梦想，不要在意终点有什么，要享受路途的过程，或许你不能成就梦想，但一定会有更伟大的事情随之而来。 mamba out~

2020.6.27

人一我十，人十我百，追逐青春的梦想，怀着自信的心，永不言弃！

650div3-A

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <cassert>
#include <string>
#include <iomanip>
#include <cmath>
#include <ctime>
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
using namespace std;
typedef long long ll;
const int MAX = 0x7ffffff;
int t;

void slove()
{
    string s , ans;
    cin >> s;
    ans += s[0];
    for(int i = 1;i < s.size();i += 2)
    {
        ans += s[i];
    }
    cout << ans << endl;
}
int main()
{
#ifdef LOCAL
    auto start_time = clock();
    cerr << setprecision(3) << fixed; // 在iomanip中
#endif
    SIS;
    cin >> t;
    while(t--)
    {
        slove();
    }
#ifdef LOCAL
    auto end_time = clock();
    cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

650div3-B

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <cassert>
#include <string>
#include <iomanip>
#include <cmath>
#include <ctime>
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
using namespace std;
typedef long long ll;
const int MAX = 0x7ffffff;
int t;

void slove()
{
    int n;
    cin >> n;
    vector<int> a(n), check(n);
    int odd = 0, even = 0;
    for(int i = 0;i < n ;i ++)
    {
        cin >> a[i];
        if(i & 1 && !(a[i] & 1))odd++;
        if(!(i & 1) && (a[i] & 1)) even++;
    }
    if(odd != even)cout << -1 << endl;
    else cout << (odd + even) / 2 << endl;
}
int main()
{
#ifdef LOCAL
    auto start_time = clock();
    cerr << setprecision(3) << fixed; // 在iomanip中
#endif
    SIS;
    cin >> t;
    while(t--)
    {
        slove();
    }
#ifdef LOCAL
    auto end_time = clock();
    cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

650div3-C

读题意毒了半天 不过树状数组是\(O(nlogn)\)时间复杂度应该比题解上面好一些

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <cassert>
#include <string>
#include <iomanip>
#include <cmath>
#include <ctime>
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
using namespace std;
typedef long long ll;
const int MAX = 0x7ffffff;
const int N = 500005;
int t;
int n , k;
string s;
int tr[N];

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;
}
bool check(int id)
{
    int r = min(n , id+k), l = max(id-k,1) - 1;
    int x = query(r) - query(l);
    return  x == 0;
}
void slove()
{
    int ans = 0;
    cin >> n >> k >> s;
    s = '0' + s;
    memset(tr , 0 , sizeof tr);
    for(int i = 1;i <= n;i ++)add(i , s[i] - '0');
    for(int i = 1;i <= n ;)
    {
        if(check(i))
        {
            add(i,1);ans++;s[i] ^= 1;
            i+=k;continue;
        }else i++;
    }
    cout << ans << endl;
}
int main()
{
#ifdef LOCAL
    auto start_time = clock();
    cerr << setprecision(3) << fixed; // 在iomanip中
#endif
    SIS;
    cin >> t;
    while(t--)
    {
        slove();
    }
#ifdef LOCAL
    auto end_time = clock();
    cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

GPLT- L2-007 家庭房产

太菜了~~~~

  1. 设计数据结构利用data结点保留输入数据node结点用来记录答案

  2. 观察题目可以知道需要用到并查集我们可以在输入的时候对其进行合并。让相同的家族放在一起并且在合并的时候时终让老大指向最小的那个id。得到每个家族的最小id

  3. 合并之后我们需要统计不同价家族的房产和面积

  4. 得出每一个家族的人数。

  5. 按照规则进行排序输出

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

using namespace std;

struct Data{
    int id , fid , mid , num , area;
    int cid[10];
}data[1005];

struct node{
    int id , people;
    double num , area;
    bool flag = false;
}ans[10000];

int f[10000];
bool vis[10000];

int find(int x)
{
    if(x == f[x])return x;
    else return f[x] = find(f[x]);
}   

void Union(int a, int b) {
    int faA = find(a);
    int faB = find(b);
    // 始终让老大指向最小的那一个id
    if(faA > faB)
        f[faA] = faB;
    else if(faA < faB)
        f[faB] = faA;
}

bool cmp(node a,node b)
{
    if(a.area != b.area)return a.area > b.area;
    else return a.id < b.id;
}

int main()
{
    int n , k, cnt = 0;
    cin >> n;
    for(int i = 0;i < 10000;i ++)
        f[i] = i;
    for(int i = 0;i < n ;i ++)
    {
        scanf("%d %d %d %d",&data[i].id,&data[i].fid,&data[i].mid,&k);
        vis[data[i].id] = true;
        if(data[i].fid != -1)
        {
            vis[data[i].fid] = true;
            Union(data[i].fid , data[i].id);
        }
        if(data[i].mid != -1)
        {
            vis[data[i].mid] = true;
            Union(data[i].mid , data[i].id);
        }
        for(int j = 0;j < k;j ++)
        {
            scanf("%d",&data[i].cid[j]);
            vis[data[i].cid[j]] = true;
            Union(data[i].cid[j], data[i].id);
        }
        scanf("%d %d",&data[i].num , &data[i].area);
    }
    // 将不同归属的家族在重新放入一个集合中
    for(int i = 0;i < n;i ++)
    {
        int id = find(data[i].id);
        ans[id].id = id;
        ans[id].num += data[i].num;
        ans[id].area += data[i].area;
        ans[id].flag = true;
    }
    for(int i = 0;i < 10000;i ++)
    {
        if(vis[i])ans[find(i)].people++;
        if(ans[i].flag)cnt++;
    }
    for(int i = 0;i < 10000;i ++)
    {
        if(ans[i].flag)
        {
            ans[i].num = (double)(ans[i].num * 1.0 / ans[i].people);
            ans[i].area = (double)(ans[i].area * 1.0 / ans[i].people);
        }
    }
    sort(ans , ans + 10000 , cmp);
     printf("%d\n", cnt);
    for(int i = 0; i < cnt; i++)
        printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].people, ans[i].num, ans[i].area);
    return 0;
}

GPLT- L2-008 最长对称子串

中心扩展法
从[i , i]扩展 和从[i , i + 1]开始分别向两端进行拓展。
时间复杂度\(O(n^2)\)

等学习了\(O(n)\)的马拉车算法继续补更

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

const int N = 1005;
char a[N];

int expandAroundCenter(string s, int left , int right)
{
    int L = left , R = right;
    while(L >= 0 && R < s.size() && s[L] == s[R])
    {
        L--;R++;
    }
    return R-L-1;
}

void longestPalindrome(string s)
{
    int start = 0,end = 0;
    for(int i = 0;i < s.size() ;i ++)
    {
        int len1 = expandAroundCenter(s , i ,i);
        int len2 = expandAroundCenter(s , i , i + 1);
        int len = max(len1 , len2);
        if(len > end - start)
        {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    cout << end + 1 - start << endl;
}

int main()
{
    string s;
    getline(cin , s);
    longestPalindrome(s);
    return 0;
}

原文链接: https://www.cnblogs.com/wlw-x/p/13200352.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

    Daliy Algorithm (greedy, 中心扩展 , 并查集)-- day 89

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/359574

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年3月2日 下午12:49
下一篇 2023年3月2日 下午12:50

相关推荐