Wannafly挑战赛27

xiaohejun

发布于 2020-02-18 09:26:26

2680

发布于 2020-02-18 09:26:26

文章被收录于专栏：xiaohejun的算法知识分享xiaohejun的算法知识分享

A 灰魔法师

AC

题目大意:

给出长度为n的序列a, 求有多少对数对 (i, j) (1 <= i < j <= n) 满足 ai + aj 为完全平方数。

题解

先找出1到21e5之间所有的完全平方数.有400多个.然后二分计算答案.注意long long.注意$a_i$可能重复.注意计算答案的时候需要分开计算的地方. 一个神奇的事情.以为int转成long long.只要一个int数1LL就行了.后面发现是1LL*int.还有一个就是昨天发现的一个神奇的地方.默认返回了ASCII码值.活久见.

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

int fun(char c){}

int main(){
   // freopen("in.txt", "r", stdin);
   cout << fun('a') << endl;
   cout << fun('b') << endl;
   return 0;
}

输出: 97 98

回到正题.正经代码.复杂度$O((400+)*nlogn)$

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

 
typedef long long LL;
const int MAX_N = 1e5;
int n;
vector<int> a;
vector<int> num;
LL len[MAX_N];
 
void init(){
    for(int i = 1;i <= 2*MAX_N; ++i){
        int x = sqrt(i);
        if(x*x == i) num.push_back(i);
    }
}
 
int main(){
   // freopen("in.txt", "r", stdin);
    init();
    int x;
    while(cin >> n){
        memset(len, 0, sizeof len);
        a.clear();
        for(int i = 0; i < n; ++i){
            cin >> x;
            ++len[x];
            if(len[x] == 1) a.push_back(x);
        }
        sort(a.begin(), a.end());
        int sz = a.size();
        LL res = 0;
        LL ans = 0;
        for(int i = 0; i < num.size(); ++i){
            int v = num[i];
            for(int j = 0; j < sz; ++j){
                if(a[j] > v) continue;
                vector<int>::iterator idx = lower_bound(a.begin(), a.end(), v - a[j]);
                if(idx != a.end()) {
                    if(*idx == v - a[j]) {
                        int x = a[j], y = v-a[j];
                        if(x == y) ans += len[x] * (len[x]-1) / 2LL;
                        else res += len[x] * len[y];
                    }
                }
            }
        }
        cout << res/2LL + ans << endl;
    }
    return 0;
}

B 紫魔法师

AC

题目大意

给一个图(每条边最多被包含于一个环，无自环，无重边，保证连通)，要求用最少的颜色对其顶点染色，满足每条边两个端点的颜色不同，输出最小颜色数即可

题解

如果$n==1$.一种颜色.如果是二分图.$2$种颜色.否则.就是有奇数环.就需要$3$种颜色.所以.二分染色即可.emmm.第一次二分染色写错.orz.

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


const int MAX_N = 1e5+100;
int color[MAX_N];
vector<int> G[MAX_N];
int n,m;

bool dfs(int u, int c){
    color[u] = c;
    int sz = G[u].size();
    for(int i = 0; i < sz; ++i){
        int v = G[u][i];
        if(!color[v]) {
            if(!dfs(v, 3-c)) return false;
        }
        if(color[v] == color[u]) return false;
    }
    return true;
}

int main(){
    //freopen("in.txt", "r", stdin);
    int u,v;
    while(cin >> n >> m){
        for(int i = 1; i <= n; ++i) G[i].clear();
        memset(color, 0 ,sizeof color);
        for(int i = 1; i <= m; ++i){
            cin >> u >> v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        if(n == 1) {puts("1"); continue;}
        if(dfs(1, 1)) puts("2");
        else puts("3");
    }
    return 0;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018-10-262，如有侵权请联系 cloudcommunity@tencent.com 删除

int

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

int

登录后参与评论

0 条评论

热度