T1 CF575E Spectator Riots
给定整点集 (mathcal S = {(x,y)|x,y in [0,10^5]})。给定另外 n个整点集 (mathcal P_{1dots n})，对于 ii∈[1,n]，给定 (mathcal P_i = mathcal S cap {(x,y)||x-x_i|+|y-y_i| in [0,v_i]})。有 n 个整点 (p_{1dots n})，对于 (i in [1,n])，p_i 在 P_i 中等概率随机。你需要从点集 (igcup_{i=1}^n mathcal P_i) 中选择三个不共线的点，使这三个点的外接圆期望所覆盖（包括圆周上）的 p 点最多。如果有多种方案，则要求这个外接圆的半径最大。如果还有多种方案，任何一种都可以。你求出的半径与答案的误差应 ≤0.01，答案的半径 (10^{10})。n≤10^5，((x_i,y_i) in mathcal S) 且不全都共线，(v_i le 10^3)。
求一个凸包将这若干个菱形或不规则图形抱起来，再枚举相邻的三个点计算半径即可。~ _ ~
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
const int N = 1e5+10 , V = 1e5;
inline int read()
{
register int x = 0 , f = 0; register char c = getchar();
while(c < '0' || c > '9') f |= c == '-' , c = getchar();
while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();
return f ? -x : x;
}
int n , tot , top;
struct point{ int x , y; }p[N * 10] , s[N * 10];
point operator - (const point &A , const point &B) { return (point){ A.x - B.x , A.y - B.y}; }
inline void add(int x , int y) { p[++tot].x = x; p[tot].y = y; }
inline double accross(point A , point B) { return (double)A.x * B.y - (double)A.y * B.x; }
inline double dis(point A , point B) { return (double)(A.x - B.x) * (A.x - B.x) + (double)(A.y - B.y) * (A.y - B.y); }
inline bool cmp1(const point &A , const point &B) { return A.x == B.x ? A.y < B.y : A.x < B.x; }
inline bool cmp2(const point &A , const point &B) { return A.x == B.x && A.y == B.y; }
inline bool cmp3(const point &A , const point &B)
{
double res = accross(A - p[1] , B - p[1]);
if(res > 0) return true;
else if(res == 0 && dis(A , p[1]) < dis(B , p[1])) return true;
return false;
}
void Get_TB()
{
for(int i = 2 ; i <= tot ; ++i) if(p[1].y > p[i].y || (p[1].y == p[i].y && p[1].x > p[i].x)) swap(p[i] , p[1]);
sort(p + 2 , p + tot + 1 , cmp3); s[1] = p[1]; s[2] = p[2]; top = 2;
for(int i = 3 ; i <= tot ; ++i)
{
while(top > 1 && accross(p[i] - s[top-1] , s[top] - s[top-1]) >= 0) top--;
s[++top] = p[i];
}
return ;
}
inline double len(point &A) { return sqrt((double)A.x * A.x + (double)A.y * A.y); }
double calc(point A , point B , point C)
{
point x = A - B , y = C - B , z = C - A;
double res = len(x) * len(y) * len(z) / (accross(y , x) * 2);
return res;
}
int main()
{
n = read();
for(int i = 1 ; i <= n ; ++i)
{
int x = read(), y = read(), v = read();
if(x < v) add(0 , min(V , y + v - x)) , add(0 , max(0 , y - v + x)); else add(x - v , y);
if(y < v) add(max(0 , x - v + y) , 0) , add(min(V , x + v - y) , 0); else add(x , y - v);
if(x + v > V) add(V , min(V , y + x + v - V)) , add(V , max(0 , y - x - v + V)); else add(x + v , y);
if(y + v > V) add(min(V , x + y + v - V) , V) , add(max(0 , x - y - v + V) , V); else add(x , y + v);
}
sort(p + 1 , p + 1 + tot , cmp1);
tot = unique(p + 1 , p + 1 + tot , cmp2) - p - 1;
Get_TB();
int id = 0; double ans = -1e9 , tmp; s[0] = s[top]; s[top+1] = s[1];
for(int i = 1 ; i <= top ; ++i)
{
point a = s[i - 1] , b = s[i] , c = s[i + 1];
if((tmp = calc(a , b , c)) > ans) ans = tmp , id = i;
}
cout << s[id - 1].x << ' ' << s[id - 1].y << '
';
cout << s[id].x << ' ' << s[id].y << '
';
cout << s[id + 1].x << ' ' << s[id + 1].y << '
';
return 0;
}
AT5140 [AGC035C] Skolem XOR Tree
构造一个2*n个节点的树，这个树上点i和点i+n的权值都是i，要求生成的树，对于任意的i满足 i 和 i+n 之间的点的异或和为 i 。 n <= 100000
考虑异或的性质，对于一个偶数x，有x ^ (x+1) = 1;
对于每个偶数，连边 (1 , i) , (1 , i + 1) , (i , i + 1 + n) , (i + 1 , i + n)
大概是这样，
然后对于1要进行特殊构造。
(1 , 2) , (2 , 3) , (3 , n + 1) , (n + 1 , n + 2) , (n + 2 , n + 3);
若n是偶数，那么n也得特殊构造
找到两个点x,y满足x ^ y ^ n = 1连起来即可。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
inline int read()
{
register int x = 0 , f = 0; register char c = getchar();
while(c < '0' || c > '9') f |= c == '-' , c = getchar();
while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();
return f ? -x : x;
}
int n;
int main()
{
n = read();
if(!(n & (n - 1))) puts("No");
else
{
puts("Yes");
puts("1 2");
puts("2 3");
cout << 3 << " " << n+1 << '
';
cout << n+1 << " " << n+2 << '
';
cout << n+2 << " " << n+3 << '
';
for(int i = 4 ; i + 1 <= n ; i += 2)
{
int j=i+1;
cout << 1 << " " << i << '
';
cout << 1 << " " << j << '
';
cout << i << " " << j+n << '
';
cout << j << " " << i+n << '
';
}
if(n%2==0)
{
for(int i = 4 ; i <= n ; ++i)
{
int j = n ^ i ^ 1;
if (j != 3 && j < n)
{
cout << i << " " << n << '
';
cout << j << " " << 2*n << '
';
return 0;
}
}
}
}
return 0;
}
AGC026F - Manju Game
两个人博弈，一堆石子，每个都有权值，先手第一次可以任意取，之后每个人都要取前一个人取得旁边的石子，两个人都采用最优策略使自己取到的石子权值和最大，求最后先手后手都有多少分。
n <= 3e5 .
首先，先手有优势，具体的我也不知道，意会吧。。
再按n的奇偶分类。
若n是偶数
那么若先手不选两边的话就一定会有一遍是偶数个，然后后手就可以选偶数那边的，那么后手就会夺得先手的优势，那么先手还不如直接从两边选，这样还能保持先手权，并且在那偶数的那一段和前一种方案取到的一样。
否则
由于要保持珍贵的先手权，那么可以得知，先手的最优策略是先取偶数位置上的，之后选择一段取端点，得到这一段上奇数位上的和，结束游戏。
可以这样计算。
先加上所有偶数位上的数 ， 然后维护一个奇数加偶数减得前缀和。在这前缀和上求得最大的一段 ， 其实也就是求是否有一种划分方式，使得最小的一段也 >= mid（哎呀，不小心说出了要二分啊），为哈是最小的一段呢？因为后手也绝顶聪明。。。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
const int N = 3e5+10;
inline int read()
{
register int x = 0 , f = 0; register char c = getchar();
while(c < '0' || c > '9') f |= c == '-' , c = getchar();
while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0' , c = getchar();
return f ? -x : x;
}
int n;
int a[N] , s[N];
inline bool check(int mid) // 本质是dp、、、
{
int k = 0;
for(int i = 1 ; i < n ; i += 2) if(s[i] - k >= mid) k = min(k , s[i+1]);
return s[n] - k >= mid;
}
int main()
{
n = read();
for(int i = 1 ; i <= n ; ++i) a[i] = read();
if(n % 2 == 0)
{
int sum1 = 0 , sum2 = 0;
for(int i = 1 ; i <= n ; ++i) if(i & 1) sum1 += a[i]; else sum2 += a[i];
cout << max(sum1 , sum2) << ' ' << min(sum1 , sum2) << '
';
return 0;
}
for(int i = 1 ; i <= n ; ++i) s[i] = s[i-1] + ((i&1) ? 1 : -1) * a[i];
int l = 0 , r = n * 1000 , mid , ans;
while(l <= r)
{
mid = (l + r) >> 1;
if(check(mid)) l = mid + 1 , ans = mid; else r = mid - 1;
}
int sum = 0;
for(int i = 1 ; i <= n ; ++i) sum += a[i];
for(int i = 1 ; i <= n ; ++i) if(i % 2 == 0) ans += a[i];
cout << ans << ' ' << sum - ans << '
';
return 0;
}