Wannafly挑战赛27
- 2020 年 2 月 18 日
- 筆記
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; }
