灰魔法師
鏈接：https://ac.nowcoder.com/acm/contest/12214/A
來源：牛客網
題目描述
“White shores, and beyond. A far green country under a swift sunrise.”–灰魔法師
給出長度為n的序列a, 求有多少對數對 (i, j) (1 <= i < j <= n) 滿足 ai + aj 為完全平方數，
輸入描述:
第一行一個整數 n (1 <= n <= 105)
第二行 n 個整數 ai (1 <= ai <= 105)
輸出描述:
輸出一個整數，表示滿足上述條件的數對個數，
示例1
輸入
復制
3
1 3 6
輸出
復制
2
說明
滿足條件的有 (1, 2), (2, 3) 兩對，
先把可能的和存盤好，然后排序，依次列舉每個數，看二分出來的可能構成的和減去這個數前面出現過多少次，然后加上即可，，注意的是一個數只可能和前面的數構成大于他小于2倍的完全平方數
/* _
_ooOoo_
o8888888o
88" . "88
(| -_- |)
.' \\| |// `.
/ \\||| : |||// \
/ _||||| -:- |||||_ \
| | \\\ - /'| | |
| \_| `\`---'// |_/ |
\ .-\__ `-. -'__/-. /
___`. .' /--.--\ `. .'___
."" '< `.___\_<|>_/___.' _> \"".
| | : `- \`. ;`. _/; .'/ / .' ; |
\ \ `-. \_\_`. _.'_/_/ -' _.' /
===========`-.`___`-.__\ \___ /__.-'_.'_.-'================
Please give me AC.
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <map>
#include <unordered_map>
#include <vector>
#include <cmath>
//#include <ext/rope>
#include <bits/stdc++.h>
using namespace std;
//using namespace __gnu_cxx;
#define gt(x) x = read()
#define int long long
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl "\n"
//#define x first
//#define y second
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
typedef __int128 INT;
typedef pair<double, int> PDI;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
inline int read(){
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if (ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x<<1) + (x<<3) + (ch^48);
ch = getchar();
}
return x * f;
}
inline void print(INT x) {
if (x < 0) { putchar('-'); x = -x; }
if (x >= 10) print(x / 10);
putchar(x % 10 + '0');
}
const int N = 1e5 + 10;
const int M = 1e7 + 10;
const int mod = 1e9 + 7;
const int PP = 131;
const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-10;
const double PI = acos(-1);
int a[N];
int cnt[N];
int n;
vector<int> v;
int find(int x){
return upper_bound(v.begin(), v.end(), x) - v.begin();
}
signed main(){
ios;
for (int i = 1; i <= N; i ++){
v.push_back(i * i);
}
cin >> n;
int ans = 0;
for (int i = 1; i <= n; i ++) cin >> a[i];
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i ++){
int id = find(a[i]);
for (int j = id; j < v.size(); j ++){
if (v[j] > 2 * a[i]) break;
ans += (cnt[v[j] - a[i]]);
}
cnt[a[i]] ++;
}
cout << ans << endl;
return 0;
}
紫魔法師
鏈接：https://ac.nowcoder.com/acm/contest/12214/B
來源：牛客網
題目描述
“サーヴァント、キャスター、Medea，”–紫魔法師
給出一棵仙人掌(每條邊最多被包含于一個環，無自環，無重邊，保證連通)，要求用最少的顏色對其頂點染色，滿足每條邊兩個端點的顏色不同，輸出最小顏色數即可
輸入描述:
第一行包括兩個整數n,m，表示頂點數和邊數
n <= 100000, m <= 200000
接下來m行每行兩個整數u,v，表示u,v之間有一條無向邊，保證資料合法
輸出描述:
一行一個整數表示最小顏色數
示例1
輸入
復制
3 4
1 2
2 3
3 4
1 4
輸出
復制
2
注意的是如果是二分圖的話兩種顏色就可以解決，就算不是的話，最多需要三種顏色就可以，如果發生矛盾的話那么久三種顏色
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <map>
#include <unordered_map>
#include <vector>
#include <cmath>
#include <ext/rope>
#include <bits/stdc++.h>
using namespace std;
#define gt(x) x = read()
#define int long long
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
//#define x first
//#define y second
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
//typedef __int128 INT;
typedef pair<double, int> PDI;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
inline int read(int out = 0)
{
char c;
while((c=getchar()) < 48 || c > 57);
while(c >= 48 && c <= 57) out=out*10+c-48,c=getchar();
return out;
}
const int N = 1e6 + 10;
const int M = 2e5 + 10;
const int mod = 1000000007;
const int PP = 13331;
const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-10;
const double PI = acos(-1);
int h[N], e[N], ne[N], idx;
int n, m;
//int color[N];
int ans = 2;;
int st[N];
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u, int color){
st[u] = color;
for (int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if (!st[j]) dfs(j, 3 - color);
if (st[j] == color) ans = 3;
}
}
signed main(){
scanf("%lld%lld", &n, &m);
memset(h, -1, sizeof h);
for (int i = 1; i <= m; i ++){
int a, b;
scanf("%lld%lld", &a, &b);
add(a, b), add(b, a);
}
dfs(1, 1);
if (n == 1) cout << "1" << endl;
else cout << ans << endl;
return 0;
}
藍魔法師
鏈接：https://ac.nowcoder.com/acm/contest/12214/C
來源：牛客網
題目描述
“你，你認錯人了，我真的，真的不是食人魔，”–藍魔法師
給出一棵樹，求有多少種刪邊方案，使得刪后的圖每個連通塊大小小于等于k，兩種方案不同當且僅當存在一條邊在一個方案中被洗掉，而在另一個方案中未被洗掉，答案對998244353取模
輸入描述:
第一行兩個整數n,k, 表示點數和限制
2 <= n <= 2000, 1 <= k <= 2000
接下來n-1行，每行包括兩個整數u,v，表示u,v兩點之間有一條無向邊
保證初始圖聯通且合法
輸出描述:
共一行，一個整數表示方案數對998244353取模的結果
示例1
輸入
復制
5 2
1 2
1 3
2 4
2 5
輸出
復制
7
很明顯是樹形dp，如何考慮，如何狀態表示，兒子的狀態如何更新父親的狀態，父親的狀態如何更新兒子的狀態，現在狀態表示為以當前節點為父節點，子節點選了k個的狀態表示，當一個父親列舉到一個兒子的時候，這個兒子如果什么都不選，那么父親節點的每種情況便會在兒子的每種情況都有可能，如果兒子選了k個，父親選了i個，那么父親節點的i+k個便會被更新，注意的是，代碼中的f[u][0表示的是選了任意多個的情況，因為要保證列舉當前兒子的狀態只有上一個兒子的狀態轉移過來，所以要新開一個陣列來表示
/* _
_ooOoo_
o8888888o
88" . "88
(| -_- |)
.' \\| |// `.
/ \\||| : |||// \
/ _||||| -:- |||||_ \
| | \\\ - /'| | |
| \_| `\`---'// |_/ |
\ .-\__ `-. -'__/-. /
___`. .' /--.--\ `. .'___
."" '< `.___\_<|>_/___.' _> \"".
| | : `- \`. ;`. _/; .'/ / .' ; |
\ \ `-. \_\_`. _.'_/_/ -' _.' /
===========`-.`___`-.__\ \___ /__.-'_.'_.-'================
Please give me AC.
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <stack>
#include <map>
#include <unordered_map>
#include <vector>
#include <cmath>
//#include <ext/rope>
#include <bits/stdc++.h>
using namespace std;
//using namespace __gnu_cxx;
#define gt(x) x = read()
#define int long long
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl "\n"
//#define x first
//#define y second
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
//typedef __int128 INT;
typedef pair<double, int> PDI;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
inline int read(){
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if (ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x<<1) + (x<<3) + (ch^48);
ch = getchar();
}
return x * f;
}
inline void print(int x) {
if (x < 0) { putchar('-'); x = -x; }
if (x >= 10) print(x / 10);
putchar(x % 10 + '0');
}
const int N = 2e3 + 10;
const int M = 3 * N;
const int mod = 998244353;
const int PP = 131;
const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-10;
const double PI = acos(-1);
int h[N], e[M], ne[M], idx;
int f[N][N];
int ff[N];
int n, m;
int sum[N];
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u, int father){
sum[u] = 1;
f[u][1] = 1;
for (int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if (j == father) continue;
dfs(j, u);
memset(ff, 0, sizeof ff);
for (int l = 1; l <= sum[u]; l ++){
for (int k = 0; k <= sum[j] && k + l <= m; k ++){
ff[l + k] = (ff[l + k] + (f[u][l] * f[j][k]) % mod) % mod;
}
}
for (int k = 1; k <= m; k ++){
f[u][k] = ff[k];
}
sum[u] += sum[j];
}
f[u][0] = 0;
for (int i = 1; i <= m; i ++){
f[u][0] = (f[u][i] + f[u][0]) % mod;
}
}
signed main(){
ios;
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 1; i < n; i ++){
int a, b, w;
cin >> a >> b;
add(a, b), add(b, a);
}
// cout << "--" << endl;
dfs(1, -1);
cout << (f[1][0] % mod) << endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259872.html
標籤：其他
上一篇：我喜愛的詩詞選編