Codeforces Round #339 (Div. 1) ABC
30235 단어 codeforcesRound-#339
다각형과 중심의 가장 먼 거리는 큰 원을 만들고 가장 가까운 거리는 작은 원을 만든다. 답은 큰 원의 면적에서 작은 원의 면적을 줄이는 것이다.중심이 다각형 안에 있는지 확인하십시오. 가장 가까운 거리가 0이면.가장 먼 거리는 점에만 나타나고 가장 가까운 거리는 점과 모서리에 나타날 수 있으니 주의하세요.이 문제는 별 재미가 없는데 계산 기하학적 틀을 붙이는 것이다.
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
class Point {
double x;
double y;
Point(double x, double y) {
this.x = x;
this.y = y;
}
double Cross(Point point) {
return x * point.y - y * point.x;
}
double Dot(Point point) {
return x * point.x + y * point.y;
}
double Distance(Point point) {
return Math.sqrt((x - point.x) * (x - point.x) + (y - point.y)
* (y - point.y));
}
Point Sub(Point point) {
return new Point(x - point.x, y - point.y);
}
}
int n;
Point pt;
Point[] pts;
void Solve() {
FastScanner scan = new FastScanner();
n = scan.nextInt();
int px = scan.nextInt();
int py = scan.nextInt();
pt = new Point(px, py);
pts = new Point[n + 1];
for (int i = 0; i < n; i++) {
int x = scan.nextInt();
int y = scan.nextInt();
pts[i] = new Point(x, y);
}
pts[n] = pts[0];
boolean positive = false;
boolean negative = false;
for (int i = 0; i < n; i++) {
Point vec = pts[i + 1].Sub(pts[i]);
double X = vec.Cross(pt.Sub(pts[i]));
if (X < 0) {
negative = true;
}
if (X > 0) {
positive = true;
}
}
double maxDist = 0;
double minDist = Double.MAX_VALUE;
if (!(positive && negative)) {
minDist = 0;
}
for (int i = 0; i < n; i++) {
double p2p = pt.Distance(pts[i]);
maxDist = Math.max(maxDist, p2p);
minDist = Math.min(minDist, p2p);
double a = pts[i].Distance(pts[i + 1]);
double b = pts[i].Distance(pt);
double c = pts[i + 1].Distance(pt);
double p = (a + b + c) / 2;
double S = Math.sqrt(p * (p - a) * (p - b) * (p - c));
double p2l = S * 2 / a;
if (pt.Sub(pts[i]).Dot(pts[i + 1].Sub(pts[i]))
* pt.Sub(pts[i + 1]).Dot(pts[i].Sub(pts[i + 1])) >= 0)
minDist = Math.min(minDist, p2l);
}
double ans = Math.PI * (maxDist * maxDist - minDist * minDist);
System.out.print(ans);
}
public static void main(String[] args) {
new Main().Solve();
}
public static class FastScanner {
BufferedReader br;
StringTokenizer st;
public FastScanner(String s) {
try {
br = new BufferedReader(new FileReader(s));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
public FastScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String nextToken() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
public boolean EOF() {
if (st != null && st.hasMoreTokens()) {
return false;
} else {
String line = null;
try {
line = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
if (line == null)
return true;
st = new StringTokenizer(line);
return false;
}
}
int nextInt() {
return Integer.parseInt(nextToken());
}
long nextLong() {
return Long.parseLong(nextToken());
}
double nextDouble() {
return Double.parseDouble(nextToken());
}
}
}B Skills
먼저 정렬한 다음에 가득 채운 기술의 수량을 일일이 열거한다.매번 매거에 대해 2점으로 계산하면 최저급 기술을 얼마나 추가할 수 있는지, 총점의 최대치를 취하면 된다.쓸 때는 세심해야 한다. 그렇지 않으면 버그가 생기기 쉽다.또한 스킬을 가득 채운 수량->총점은 철함수인 줄 알았는데 3점 세트 2점을 써서 WA를 계속했다.나중에 3분의 1을 수정해서 구간이 어느 정도 작을 때 일일이 열거해 버렸다.나중에 그것이 반드시 철함수가 아니라는 사실이 증명되었기 때문이다.다 쓴 후에 자변수 이산(정수만 얻을 수 있기 때문)과 연속의 3분의 1이 다르다는 것을 발견했다.
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
class Node implements Comparable<Node> {
long val;
int id;
@Override
public int compareTo(Node o) {
// TODO Auto-generated method stub
if (val < o.val) {
return -1;
} else if (val == o.val) {
return 0;
} else {
return 1;
}
}
}
int n;
long A, cf, cm;
long m;
Node[] a;
long[] rsum;
long[] lsum;
long BinerySearch(int l, int r, long val) {
int mid;
int pos = 0;
while (l <= r) {
mid = (l + r) >> 1;
if (lsum[mid] <= val) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
val -= lsum[pos];
long res = a[pos].val + val / (pos + 1);
res = Math.min(res, A);
return res;
}
void Solve() {
FastScanner scan = new FastScanner();
n = scan.nextInt();
A = scan.nextLong();
cf = scan.nextLong();
cm = scan.nextLong();
m = scan.nextLong();
a = new Node[n + 1];
lsum = new long[n + 1];
rsum = new long[n + 1];
for (int i = 0; i < n; i++) {
a[i] = new Node();
a[i].val = scan.nextLong();
a[i].id = i;
}
Arrays.sort(a, 0, n);
for (int i = 1; i < n; i++) {
lsum[i] = lsum[i - 1] + (a[i].val - a[i - 1].val) * i;
}
lsum[n] = Long.MAX_VALUE;
int leftMost = 0;
for (int i = n - 1; i >= 0; i--) {
rsum[i] = rsum[i + 1] + (A - a[i].val);
if (rsum[i] > m) {
leftMost = i + 1;
break;
}
}
long maxP = 0;
int left = leftMost;
long MIN = A;
for (int i = n; i >= leftMost; i--) {
long mm = m - rsum[i];
long tmp = BinerySearch(0, i - 1, mm);
long power = tmp * cm + (n - i) * cf;
if (tmp == A) {
power = A * cm + n * cf;
}
if (power >= maxP) {
maxP = power;
left = i;
MIN = tmp;
}
}
long[] ans = new long[n + 1];
for (int i = 0; i < n; i++) {
int id = a[i].id;
ans[id] = a[i].val;
if (i >= left) {
ans[id] = A;
} else if (ans[id] < MIN) {
ans[id] = MIN;
}
}
PrintWriter out = new PrintWriter(System.out);
out.println(maxP);
for (int i = 0; i < n; i++) {
out.print(ans[i] + " ");
}
out.println();
out.flush();
}
public static void main(String[] args) {
new Main().Solve();
}
public static class FastScanner {
BufferedReader br;
StringTokenizer st;
public FastScanner(String s) {
try {
br = new BufferedReader(new FileReader(s));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
public FastScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String nextToken() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
public boolean EOF() {
if (st != null && st.hasMoreTokens()) {
return false;
} else {
String line = null;
try {
line = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
if (line == null)
return true;
st = new StringTokenizer(line);
return false;
}
}
int nextInt() {
return Integer.parseInt(nextToken());
}
long nextLong() {
return Long.parseLong(nextToken());
}
double nextDouble() {
return Double.parseDouble(nextToken());
}
}
}C Necklace
이 문제는 내가 비교적 번거롭게 썼다.우선 규칙을 찾아보면 2개 이상의 홀수가 나타나면 회문이 형성되지 않는다는 것을 알 수 있다.그렇지 않으면 이 수의 GCD가 정답입니다.구성할 때, 컴파일링 (gcd 섹션으로 분리하여 현재 문자와 다른 문자를 교체할 수 있습니다.)이 과정은 비교적 복잡하니, 상세한 것은 코드를 보십시오.
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main {
int n;
int[] a;
char[] chars;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
StringBuilder Construct(int[] arr, int s) {
if (s > n) {
return new StringBuilder("");
}
StringBuilder res = new StringBuilder();
int odd = 0;
for (int i = s; i <= n; i++) {
if (arr[i] % 2 == 1) {
odd++;
// swap
int tmp = arr[i];
arr[i] = arr[s];
arr[s] = tmp;
char tmp2 = chars[i];
chars[i] = chars[s];
chars[s] = tmp2;
}
}
if (odd > 1 || s == n) {
for (int i = s; i <= n; i++) {
for (int j = 1; j <= arr[i]; j++) {
res.append(chars[i]);
}
}
return res;
}
int GCD = arr[s];
for (int i = s + 1; i <= n; i++) {
GCD = gcd(GCD, arr[i]);
}
int end = arr[s] / GCD;
int[] newArr = new int[n + 1];
for (int i = 1; i <= n; i++) {
newArr[i] = arr[i] / GCD;
}
StringBuilder sbS = new StringBuilder();
for (int i = 1; i <= end; i++) {
sbS.append(chars[s]);
}
StringBuilder others = Construct(newArr, s + 1);
String left = others.toString();
String right = others.reverse().toString();
if (arr[s] % 2 == 0) {
res.append(right);
for (int t = 1; t <= GCD / 2; t++) {
res.append(sbS);
res.append(sbS);
if (t != GCD / 2) {
res.append(left);
res.append(right);
} else {
res.append(left);
}
}
} else {
left = left.substring(0, left.length() / 2);
right = new StringBuilder(left).reverse().toString();
res.append(right);
for (int t = 1; t <= GCD; t++) {
res.append(sbS);
if (t != GCD) {
res.append(left);
res.append(right);
} else {
res.append(left);
}
}
}
return res;
}
void Solve() {
FastScanner scan = new FastScanner();
PrintWriter out = new PrintWriter(System.out);
n = scan.nextInt();
a = new int[n + 1];
chars = new char[n + 1];
chars[1] = 'a';
for (int i = 2; i <= n; i++) {
chars[i] = (char) (chars[i - 1] + 1);
}
int odd = 0;
for (int i = 1; i <= n; i++) {
a[i] = scan.nextInt();
if (a[i] % 2 == 1) {
odd++;
}
}
int GCD = a[1];
for (int i = 2; i <= n; i++) {
GCD = gcd(GCD, a[i]);
}
StringBuilder sb = new StringBuilder();
if (odd > 1) {
out.println(0);
} else {
out.println(GCD);
}
sb = Construct(a, 1);
out.println(sb);
out.flush();
}
public static void main(String[] args) {
new Main().Solve();
}
public static class FastScanner {
BufferedReader br;
StringTokenizer st;
public FastScanner(String s) {
try {
br = new BufferedReader(new FileReader(s));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
public FastScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String nextToken() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
public boolean EOF() {
if (st != null && st.hasMoreTokens()) {
return false;
} else {
String line = null;
try {
line = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
if (line == null)
return true;
st = new StringTokenizer(line);
return false;
}
}
int nextInt() {
return Integer.parseInt(nextToken());
}
long nextLong() {
return Long.parseLong(nextToken());
}
double nextDouble() {
return Double.parseDouble(nextToken());
}
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
