本期F为群论题,很有难度。
为了避免精度问题,采用二分推算。但是要小心结果为1的地方。
R
2
?
k
2
≥
x
2
+
y
2
R^2*k^2\geq x^2+y^2
R2?k2≥x2+y2
# -*- coding: utf-8 -*-
# @time : 2023/6/2 13:30
# @file : atcoder.py
# @software : PyCharm
import bisect
import copy
import sys
from itertools import permutations
from sortedcontainers import SortedList
from collections import defaultdict, Counter, deque
from functools import lru_cache, cmp_to_key
import heapq
import math
sys.setrecursionlimit(100010)
def main():
items = sys.version.split()
fp = open("in.txt") if items[0] == "3.10.6" else sys.stdin
r, x, y = map(int, fp.readline().split())
d = x ** 2 + y ** 2
r = r ** 2
# r^2 * k^2 >= d^2 (first k)
lo, hi = 0, 100000001
while lo < hi:
mi = (lo + hi) >> 1
if mi ** 2 * r >= d:
hi = mi
else:
lo = mi + 1
if hi == 1:
if r != d:
hi = 2
print(hi)
if __name__ == "__main__":
main()
还不错的搜索题,硬做就好了。
一开始思路不好,半小时写了个搜索WA,
因为没有想到答案应该有long long类型。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <map>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
#define LT(x) (x * 2)
#define RT(x) (x * 2 + 1)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
const ll inf = ll(1e15);
const ld pi = 3.1415926535897932384626;
string sa, sb, sc;
int na, nb, nc, n;
bool vis[10];
int dig[256];
set<char> ss;
bool ac;
int ansa, ansb, ansc;
void gene() {
if (dig[sa[sa.size() - 1]] == 0 || dig[sb[sb.size() - 1]] == 0 || dig[sc[sc.size() - 1]] == 0)
{
ac = 0;
return;
}
for (int i = 0; i < sa.size(); ++ i) {
char c = sa[sa.size() - 1 - i];
ansa = ansa * 10 + dig[c];
}
for (int i = 0; i < sb.size(); ++ i) {
char c = sb[sb.size() - 1 - i];
ansb = ansb * 10 + dig[c];
}
for (int i = 0; i < sc.size(); ++ i) {
char c = sc[sc.size() - 1 - i];
ansc = ansc * 10 + dig[c];
}
}
void dfs(int pos, int row, int c) {
if (pos == n) {
if (c == 0) {
ac = 1;
gene();
}
return;
}
if (ac)
return;
if (row == 0) {
int da = pos < na ? dig[sa[pos]] : 0;
if (da == -1) {
for (int i = 0; i < 10; ++i) {
if (!vis[i]) {
vis[i] = 1;
dig[sa[pos]] = i;
dfs(pos, row + 1, c + i);
dig[sa[pos]] = -1;
vis[i] = 0;
}
}
}
else {
dfs(pos, row + 1, c + da);
}
}
else if (row == 1) {
int db = pos < nb ? dig[sb[pos]] : 0;
if (db == -1) {
for (int i = 0; i < 10; ++i) {
if (!vis[i]) {
vis[i] = 1;
dig[sb[pos]] = i;
dfs(pos, row + 1, c + i);
dig[sb[pos]] = -1;
vis[i] = 0;
}
}
}
else {
dfs(pos, row + 1, c + db);
}
}
else {
int dc = pos < nc ? dig[sc[pos]] : 0;
if (dc == -1) {
int next_c = c / 10;
dc = c % 10;
if (!vis[dc]) {
dig[sc[pos]] = dc;
vis[dc] = 1;
dfs(pos + 1, 0, next_c);
vis[dc] = 0;
dig[sc[pos]] = -1;
}
}
else {
int tc = c % 10, next_c = c / 10;
if (tc == dc) {
dfs(pos + 1, 0, next_c);
}
}
}
}
int main() {
//freopen("in.txt", "r", stdin);
cin >> sa >> sb >> sc;
sa = string(sa.rbegin(), sa.rend());
sb = string(sb.rbegin(), sb.rend());
sc = string(sc.rbegin(), sc.rend());
na = sa.length(), nb = sb.length(), nc = sc.length();
n = max(max(na, nb), nc);
memset(dig, 0xff, sizeof(dig));
for (char x : sa)
ss.insert(x);
for (char x : sb)
ss.insert(x);
for (char x : sc)
ss.insert(x);
if (ss.size() > 10) {
printf("UNSOLVABLE\n");
return 0;
}
dfs(0, 0, 0);
if (!ac) {
printf("UNSOLVABLE\n");
}
else {
printf("%d\n%d\n%d\n", ansa, ansb, ansc);
}
return 0;
}
后来看了题解,发现有简便的permutation做法。
p数组是每个字母代表的数字。
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <map>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
#define LT(x) (x * 2)
#define RT(x) (x * 2 + 1)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
const ll inf = ll(1e15);
const ld pi = 3.1415926535897932384626;
string sa, sb, sc;
set<char> ss;
int main() {
//freopen("in.txt", "r", stdin);
cin >> sa >> sb >> sc;
for (char x : sa)
ss.insert(x);
for (char x : sb)
ss.insert(x);
for (char x : sc)
ss.insert(x);
if (ss.size() > 10) {
printf("UNSOLVABLE\n");
return 0;
}
vector<char> v(ss.begin(), ss.end());
int mp[256] = { 0 };
for (int i = 0; i < v.size(); ++i) {
mp[v[i]] = i;
}
vi p;
for (int i = 0; i < 10; ++i) p.push_back(i);
do {
bool ac = 1;
ll a = 0, b = 0, c = 0;
for (int i = 0; i < sa.size(); ++i) {
a = a * 10 + p[mp[sa[i]]];
if (i == 0 && p[mp[sa[i]]] == 0) ac = 0;
}
for (int i = 0; i < sb.size(); ++i) {
b = b * 10 + p[mp[sb[i]]];
if (i == 0 && p[mp[sb[i]]] == 0) ac = 0;
}
for (int i = 0; i < sc.size(); ++i) {
c = c * 10 + p[mp[sc[i]]];
if (i == 0 && p[mp[sc[i]]] == 0) ac = 0;
}
if (ac && a + b == c) {
printf("%lld\n%lld\n%lld\n", a, b, c);
return 0;
}
} while (next_permutation(p.begin(), p.end()));
printf("UNSOLVABLE\n");
return 0;
}
搜索
记录一个当前搜索到的颜色数量vis
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
#define LT(x) (x * 2)
#define RT(x) (x * 2 + 1)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
int n;
int a[100020];
vi g[100020];
int vis[100020];
int ans = 0;
vi ansl;
void dfs(int u, int fa) {
if (vis[a[u]] == 0) {
ansl.push_back(u);
ans++;
}
vis[a[u]] ++;
for (int v : g[u]) {
if (v == fa) continue;
dfs(v, u);
}
vis[a[u]] --;
}
int main() {
//freopen("in.txt", "r", stdin);
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
for (int i = 0; i < n - 1; ++i) {
int u, v;
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
//printf("%d\n", ans);
sort(ansl.begin(), ansl.end());
for (int x : ansl)
printf("%d\n", x);
return 0;
}
Polya定理,暂无