头像

Arroganceの浓


访客:1216

离线:6小时前



题意

给n个数,你可以选任意两个数a,b 计算出 a&b 和 a|b 赋值给两个数。
求n个数的平方和最大。

思路

随便举两个二进制数:

    11001
    10101
and:10001
or: 11101

只有01的位数会交换,交换是把所有1交换到同一个数上。另一个数这些位都是0.
要求平方和最大,需要换出最大的数,所以只要记录每一位1的次数,每次都找最大的数求平方和。

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 200010;

int a[N];
int cnt[35];

void solve()
{
    int n;
    cin >> n;
    for(int i=0;i<n;i++)
    {
        int x;
        cin >>x;
        for(int j=0; (x>>j) ; j++)
            if((x >> j) & 1)cnt[j]++;
    }
    long long ans = 0;
    while(1)
    {
        LL x = 0;
        bool flag=1;
        for(int i=0;i<21;i++)
            if(cnt[i])flag=0, x += (1 << i),cnt[i]--;
        ans += x * x;
        if(flag)break;
    }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

   /*int t;
   cin >> t;
   while(t--)*/
    solve();

}



建议

首先我用手机登录一般是为了看视频。
先提一个手机端的建议。视频全屏不会自动横屏,要开自动旋转。但是躺着的时候不方便。。我懒别打我

用户名和密码

用户名 是你在acwing里的昵称,不知道为什么用邮箱显示用户名不存在。
我最开始用的qq登录后面绑定手机号。这个时候其实你是没有密码的!!
也就是说你用账号密码是登录不上的,显示密码错误。我没试过密码空着能不能上。。

关于浏览器

QQ浏览器不能看视频,原因是不支持加密点播。
edge浏览器的QQ一键登录总是显示QQ不是最新版(我是),没试过微信。
火狐目前看来是效果最好的。

解决

电脑端设置密码之后,用账号密码登录edge。
换浏览器




卡特兰数:

公式:catalan.png
应用:在n个元素出栈的可能性次数;二叉树的中序序列已知,求二叉树的种类的个数;n个节点的二叉树有多少种。



活动打卡代码 AcWing 872. 最大公约数

欧几里得算法(辗转相除法)

#include<iostream>
#include<algorithm>
using namespace std;

int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int a,b;
        cin >> a >> b;
       // cout <<__gcd(a,b)<<endl;      //直接调用库里的函数
        cout <<gcd(a,b)<<endl;
    }
}


活动打卡代码 AcWing 871. 约数之和

约数之和

每个质因子从0次方加到这个质因子个数的次方的乘积即为这个数约数的和。

#include<iostream>
#include<unordered_map>

using namespace std;

const int mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;
    unordered_map<int,int> primes;
    while(n--)
    {
        int x;
        cin >> x;
        for(int i=2;i <=x/i; i++)
            while(x % i == 0)
            {
                x /= i;
                primes[i] ++;
            }
        if(x > 1) primes[x]++;
    }
    long long ans = 1;
    for(auto p : primes)
    {
        long long t = 1;
        while(p.second --) t = (t * p.first + 1) % mod;
        ans = ans * t % mod;
    }
    cout << ans << endl;
}


活动打卡代码 AcWing 870. 约数个数

约数个数

每个质因子的个数加一(1也包括)的乘积即为这个数约数的个数。

#include<iostream>
#include<unordered_map>

using namespace std;

const int mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;
    unordered_map<int,int> primes;  //记录质因子的个数
    while(n--)
    {
        int x;
        cin >> x;
        for(int i=2;i <= x/i; i++)
            while(x % i == 0)
            {
                x /= i;
                primes[i] ++;
            }
        if(x > 1) primes[x] ++;
    }
    long long ans = 1;
    for(auto p:primes)
        ans = ans * (p.second + 1) % mod;
    cout << ans << endl;
}



匈牙利算法(渣男算法)

记录每个男生对哪些女生有意思。(链表)
让每个男生去找喜欢的女生,如果这个女生没有男朋友(还没被匹配)他们就在一起(匹配);如果这个女生有男朋友了,就找她男朋友看看他能不能在其他的喜欢的女生里换一个(渣男),只要有一个成立当前的男生和女生就在一起了。
vis的作用:退出递归,保证集合中的点只使用一次,每次都要初始化。

时间复杂度O(n*m) 实际运行时间一般远小于O(nm),

#include<cstring>
#include<iostream>

using namespace std;

const int N = 505, M = 100010;

int e[M], ne[M], h[N], idx;
int n1, n2, m;
int match[N];       //match[i] = x, 右半部分第i个点 匹配的是左半部分第x个点。女生和哪个男生在一起了
bool vis[N];

void add(int a,int b)
{
    e[idx] = b, ne[idx] = h[a] , h[a] = idx ++;
}

bool find(int x)
{
    for(int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(vis[j]) continue;
        vis[j] =1;
        if(!match[j] || find(match[j]))     //女生没被匹配 || 找她男朋友换一个
        {
            match[j] = x;
            return true;
        }
    }
    return false;
}


int main()
{
    cin >> n1 >> n2 >> m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b;
        cin >> a >> b;
        add(a,b);
    }
    int ans = 0;
    for(int i=1;i<=n1;i++)
    {
        memset(vis, 0, sizeof vis); 
        if(find(i)) ans ++ ;
    }
    cout << ans << endl;
}



染色法判定二分图

二分图:将图中所有点分成两个集合,同一集合内的点不存在边。图中不存在奇数环则是二分图。
找到没搜过的点,向下遍历,将每次遍历的点都用1,2轮流染色。若搜到的下一个点和当前点的颜色一样则不是二分图。

#include<cstring>
#include<iostream>

using namespace std;

const int N = 100010;

int n,m;
int color[N];       //染色
int e[2*N], ne[2*N], h[N], idx;

void add(int a,int b)
{
    e[idx] = b, ne[idx] = h[a] , h[a] = idx++;
}

bool dfs(int t,int c)
{
    color[t] = c;
    for(int i=h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if(color[j] == c)return true;       
        else if(!color[j]) dfs(j,3-c);
    }
    return false;
}

int main()
{
    cin >> n>> m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b;
        cin >> a >> b;
        add(a,b);
        add(b,a);
    }
    bool flag=1;
    for(int i=1;i<=n;i++)
    if(!color[i] && dfs(i,1))
    {
        flag = 0;
        break;
    }
    if(flag) puts("Yes");
    else puts("No");
}



kruskal算法

应用的并查集思想,从小到大遍历边,询问所连的两个点是否在同一个集合中。
若不在则合并,这条边加入答案,同时记录加入的边数。
最后有n-1条边则可以构成最小生成树。

时间复杂度O(mlog(m))

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 400010;

struct Edge
{
    int a,b,c;
    bool operator < (Edge x)
    {
        return c < x.c;
    }
}edge[N];

int p[N];
int n, m;

int find(int x)     //并查集查找
{
    if(p[x] != x)
        p[x] = find(p[x]);

    return p[x];
}

int main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        p[i] = i;
    for(int i=0; i<m; i++)      
    {
        int a,b,c;
        cin >> a >> b >> c;
        edge[i] = {a,b,c};
    }
    sort(edge, edge+m);
    int ans = 0, cnt = 0;
    for(int i=0;i<m;i++)
    {
        auto t = edge[i];
        int x = find(t.a), y = find(t.b); 
        if(x != y)
        {
            cnt ++;
            ans += t.c;
            p[x] = y;
        }
    }
    if(cnt == n - 1) 
    cout << ans << endl;
    else cout << "impossible" << endl;
}



prim算法

做法和dijkstra算法几乎一样。
不同的地方是d[]代表的是到源点集的距离,也就是未标记点中到标记的点集的距离。
在未加入到源点的点中找到离源点集最近的点将他加入源点集。
时间复杂度O(n^2)

#include<cstring>
#include<iostream>

using namespace std;

const int N = 550;

int g[N][N], d[N];
bool vis[N];
int n,m, ans;

bool prim()
{
    memset(d, 0x3f, sizeof d);

    for(int i=0;i<n;i++)
    {
        int t = 0;
        for(int j=1; j<=n; j++)     //找到未标记的点里 距离最小的点
            if(!vis[j] && (!t || d[j] < d[t])) t = j;

        if(i && d[t] == 0x3f3f3f3f) return false;   //没找到下一个点
        if(i) ans += d[t];
        vis[t] = 1;           //加入源点集
        for(int j=1;j<=n;j++)       //更新其他点
            d[j] = min(d[j], g[t][j]);
    }
    return true;
}

int main()
{
    cin >> n >> m;
    memset(g,0x3f, sizeof g);
    while(m--)
    {
        int a,b,c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    if(prim()) cout << ans << endl;
    else puts("impossible");
}