99的手速加上1的运气

2133

wo是豪学僧
incra

be_awake_in_dream
Kazimierz

syx123456
cheez
alan69359
Grinder

-浪漫主义狗-
tyjz_yyds
Anohkx

yxc的小迷妹

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 3;

int n, m;

void mul(int c[], int a[], int b[][N])
{
int temp[N] = {0};
for (int i = 0; i < N; i ++ )
for (int j = 0; j < N; j ++ )
temp[i] = (temp[i] + (LL)a[j] * b[j][i]) % m;

memcpy(c, temp, sizeof temp);
}

void mul(int c[][N], int a[][N], int b[][N])
{
int temp[N][N] = {0};
for (int i = 0; i < N; i ++ )
for (int j = 0; j < N; j ++ )
for (int k = 0; k < N; k ++ )
temp[i][j] = (temp[i][j] + (LL)a[i][k] * b[k][j]) % m;

memcpy(c, temp, sizeof temp);
}

int main()
{
cin >> n >> m;

int f1[N] = {1, 1, 1};
int a[N][N] = {
{0, 1, 0},
{1, 1, 1},
{0, 0, 1}
};

n -- ;
while (n)
{
if (n & 1) mul(f1, f1, a);  // res = res * a
mul(a, a, a);  // a = a * a
n >>= 1;
}

cout << f1[2] << endl;

return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 300000;
const double PI = acos(-1);

struct Complex
{
double x, y;
Complex operator+ (const Complex& t) const
{
return {x + t.x, y + t.y};
}
Complex operator- (const Complex& t) const
{
return {x - t.x, y - t.y};
}
Complex operator* (const Complex& t) const
{
return {x * t.x - y * t.y, x * t.y + y * t.x};
}
}a[N], b[N];
char s1[N], s2[N];
int res[N];
int rev[N], bit, tot;

void fft(Complex a[], int inv)
{
for (int i = 0; i < tot; i ++ )
if (i < rev[i])
swap(a[i], a[rev[i]]);
for (int mid = 1; mid < tot; mid *= 2)
{
auto w1 = Complex({cos(PI / mid), inv * sin(PI / mid)});
for (int i = 0; i < tot; i += mid * 2)
{
auto wk = Complex({1, 0});
for (int j = 0; j < mid; j ++, wk = wk * w1)
{
auto x = a[i + j], y = wk * a[i + j + mid];
a[i + j] = x + y, a[i + j + mid] = x - y;
}
}
}
}

int main()
{
scanf("%s%s", s1, s2);
int n = strlen(s1) - 1, m = strlen(s2) - 1;
for (int i = 0; i <= n; i ++ ) a[i].x = s1[n - i] - '0';
for (int i = 0; i <= m; i ++ ) b[i].x = s2[m - i] - '0';
while ((1 << bit) < n + m + 1) bit ++ ;
tot = 1 << bit;
for (int i = 0; i < tot; i ++ )
rev[i] = ((rev[i >> 1] >> 1)) | ((i & 1) << (bit - 1));
fft(a, 1), fft(b, 1);
for (int i = 0; i < tot; i ++ ) a[i] = a[i] * b[i];
fft(a, -1);

int k = 0;
for (int i = 0, t = 0; i < tot || t; i ++ )
{
t += a[i].x / tot + 0.5;
res[k ++ ] = t % 10;
t /= 10;
}

while (k > 1 && !res[k - 1]) k -- ;
for (int i = k - 1; i >= 0; i -- ) printf("%d", res[i]);

return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>

#define x first
#define y second

using namespace std;

typedef long double LD;
typedef pair<int, int> PII;
typedef pair<LD, LD> PDD;
const int N = 10010;
const LD eps = 1e-18;

int n, cnt;
struct Line
{
PDD st, ed;
vector<int> ids;
}line[N];
int ki[N], vi[N];
int q[N], ans[N];

PDD operator-(PDD a, PDD b)
{
return {a.x - b.x, a.y - b.y};
}

int sign(LD x)
{
if (fabs(x) < eps) return 0;
if (x < 0) return -1;
return 1;
}

int dcmp(LD x, LD y)
{
if (fabs(x - y) < eps) return 0;
if (x < y) return -1;
return 1;
}

LD cross(PDD a, PDD b)
{
return a.x * b.y - a.y * b.x;
}

LD area(PDD a, PDD b, PDD c)
{
return cross(b - a, c - a);
}

LD get_angle(const Line& a)
{
return atan2(a.ed.y - a.st.y, a.ed.x - a.st.x);
}

bool cmp(const Line& a, const Line& b)
{
LD A = get_angle(a), B = get_angle(b);
if (!dcmp(A, B)) return area(a.st, a.ed, b.ed) < 0;
return A < B;
}

PDD get_line_intersection(PDD p, PDD v, PDD q, PDD w)
{
auto u = p - q;
LD t = cross(w, u) / cross(v, w);
return {p.x + v.x * t, p.y + v.y * t};
}

PDD get_line_intersection(Line& a, Line& b)
{
return get_line_intersection(a.st, a.ed - a.st, b.st, b.ed - b.st);
}

// 判断bc的交点是否在a的右侧
bool on_right(Line& a, Line& b, Line& c)
{
auto o = get_line_intersection(b, c);
return area(a.st, a.ed, o) < 0;
}

void half_plane_intersection()
{
sort(line, line + cnt, cmp);
int hh = 0, tt = -1;
for (int i = 0; i < cnt; i ++ )
{
if (i && !dcmp(get_angle(line[i - 1]), get_angle(line[i]))) continue;
while (hh + 1 <= tt && on_right(line[i], line[q[tt - 1]], line[q[tt]])) tt -- ;
while (hh + 1 <= tt && on_right(line[i], line[q[hh]], line[q[hh + 1]])) hh ++ ;
q[ ++ tt] = i;
}
while (hh + 1 <= tt && on_right(line[q[hh]], line[q[tt - 1]], line[q[tt]])) tt -- ;
while (hh + 1 <= tt && on_right(line[q[tt]], line[q[hh]], line[q[hh + 1]])) hh ++ ;

int k = 0;
for (int i = hh; i <= tt; i ++ )
for (auto id: line[q[i]].ids)
ans[k ++ ] = id;
sort(ans, ans + k);

printf("%d\n", k);
for (int i = 0; i < k; i ++ ) printf("%d ", ans[i]);
puts("");
}

int main()
{
map<PII, vector<int>> ids;
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &ki[i]);
for (int i = 1; i <= n; i ++ ) scanf("%d", &vi[i]);
for (int i = 1; i <= n; i ++ )
ids[{ki[i], vi[i]}].push_back(i);

line[cnt ++ ] = {{0, 10000}, {0, 0}};
line[cnt ++ ] = {{0, 0}, {10000, 0}};
for (auto& [k, v]: ids)
line[cnt ++ ] = {{0, k.x}, {1, k.x + k.y}, v};

half_plane_intersection();
return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double,double> PDD;
const int N = 510;
const double eps = 1e-8;

int cnt;
struct Line
{
PDD st, ed;
}line[N];
PDD pg[N], ans[N];
int q[N];

int sign(double x)
{
if (fabs(x) < eps) return 0;
if (x < 0) return -1;
return 1;
}

int dcmp(double x, double y)
{
if (fabs(x - y) < eps) return 0;
if (x < y) return -1;
return 1;
}

double get_angle(const Line& a)
{
return atan2(a.ed.y - a.st.y, a.ed.x - a.st.x);
}

PDD operator-(PDD a, PDD b)
{
return {a.x - b.x, a.y - b.y};
}

double cross(PDD a, PDD b)
{
return a.x * b.y - a.y * b.x;
}

double area(PDD a, PDD b, PDD c)
{
return cross(b - a, c - a);
}

bool cmp(const Line& a, const Line& b)
{
double A = get_angle(a), B = get_angle(b);
if (!dcmp(A, B)) return area(a.st, a.ed, b.ed) < 0;
return A < B;
}

PDD get_line_intersection(PDD p, PDD v, PDD q, PDD w)
{
auto u = p - q;
double t = cross(w, u) / cross(v, w);
return {p.x + v.x * t, p.y + v.y * t};
}

PDD get_line_intersection(Line a, Line b)
{
return get_line_intersection(a.st, a.ed - a.st, b.st, b.ed - b.st);
}

// bc的交点是否在a的右侧
bool on_right(Line& a, Line& b, Line& c)
{
auto o = get_line_intersection(b, c);
return sign(area(a.st, a.ed, o)) <= 0;
}

double half_plane_intersection()
{
sort(line, line + cnt, cmp);
int hh = 0, tt = -1;
for (int i = 0; i < cnt; i ++ )
{
if (i && !dcmp(get_angle(line[i]), get_angle(line[i - 1]))) continue;
while (hh + 1 <= tt && on_right(line[i], line[q[tt - 1]], line[q[tt]])) tt -- ;
while (hh + 1 <= tt && on_right(line[i], line[q[hh]], line[q[hh + 1]])) hh ++ ;
q[ ++ tt] = i;
}
while (hh + 1 <= tt && on_right(line[q[hh]], line[q[tt - 1]], line[q[tt]])) tt -- ;
while (hh + 1 <= tt && on_right(line[q[tt]], line[q[hh]], line[q[hh + 1]])) hh ++ ;

q[ ++ tt] = q[hh];
int k = 0;
for (int i = hh; i < tt; i ++ )
ans[k ++ ] = get_line_intersection(line[q[i]], line[q[i + 1]]);
double res = 0;
for (int i = 1; i + 1 < k; i ++ )
res += area(ans[0], ans[i], ans[i + 1]);
return res / 2;
}

int main()
{
int n, m;
scanf("%d", &n);
while (n -- )
{
scanf("%d", &m);
for (int i = 0; i < m; i ++ ) scanf("%lf%lf", &pg[i].x, &pg[i].y);
for (int i = 0; i < m; i ++ )
line[cnt ++ ] = {pg[i], pg[(i + 1) % m]};
}
double res = half_plane_intersection();
printf("%.3lf\n", res);

return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

#define x first
#define y second
using namespace std;

typedef pair<double, double> PDD;
const double eps = 1e-12, PI = acos(-1);
const int N = 50001;

PDD q[N];
int n;
struct circle{
PDD p;
double r;
};

int sign(double x){
if(fabs(x) < eps) return 0;
if(x < 0) return -1;
return 1;
}

int dcmp(double x, double y){
if(fabs(x - y) < eps) return 0;
if(x < y) return -1;
return 1;
}

PDD operator+ (PDD a, PDD b){
return {a.x + b.x, a.y + b.y};
}

PDD operator- (PDD a, PDD b){
return {a.x - b.x, a.y - b.y};
}

PDD operator* (PDD a, double t){
return {a.x * t, a.y * t};
}

PDD operator/ (PDD a, double t){
return {a.x / t, a.y / t};
}

double operator* (PDD a, PDD b){
return a.x * b.y - a.y * b.x;
}

PDD rotate(PDD a, double b){
return {a.x * cos(b) + a.y * sin(b), -a.x * sin(b) + a.y * cos(b)};
}

double dist(PDD a, PDD b){
double dx = a.x - b.x, dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}

PDD line(PDD p, PDD v, PDD q, PDD w){
auto u = p - q;
double t = w * u / (v * w);
return p + v * t;
}

pair<PDD, PDD> get(PDD a, PDD b){
return {(a + b) / 2, rotate(b - a, PI / 2)};
}

circle circ(PDD a, PDD b, PDD c){
auto u = get(a, b), v = get(a, c);
auto p = line(u.x, u.y, v.x, v.y);
return {p, dist(p, a)};
}

int main(){
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%lf%lf", &q[i].x, &q[i].y);
double a, p;
scanf("%lf%lf", &a, &p);
for(int i = 0; i < n; i++){
q[i] = rotate(q[i], a / 180 * PI);
q[i].x /= p;
}
random_shuffle(q, q + n);
circle c({q[0], 0});
for(int i = 1; i < n; i++){
if(dcmp(c.r, dist(c.p, q[i])) < 0){
c = {q[i], 0};
for(int j = 0; j < i; j++){
if(dcmp(c.r, dist(c.p, q[j])) < 0){
c = {(q[i] + q[j]) / 2, dist(q[i], q[j]) / 2};
for(int k = 0; k < j; k++){
if(dcmp(c.r, dist(c.p, q[k])) < 0){
c = circ(q[i], q[j], q[k]);
}
}
}
}
}
}
printf("%.3lf\n", c.r);
return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

#define x first
#define y second
using namespace std;

typedef pair<double, double> PDD;
const int N = 1e5 + 1;
const double eps = 1e-12;
const double PI = acos(-1);

int n;
PDD q[N];
struct circle{
PDD p;
double r;
};

int sign(double x){
if(fabs(x) < eps) return 0;
if(x < 0) return -1;
return 1;
}

int dcmp(double x, double y){
return fabs(x - y) < eps ? 0 : (x < y ? -1 : 1);
}

PDD operator- (PDD a, PDD b){
return {a.x - b.x, a.y - b.y};
}

PDD operator+ (PDD a, PDD b){
return {a.x + b.x, a.y + b.y};
}

PDD operator* (PDD a, double t){
return {a.x * t, a.y * t};
}

PDD operator/ (PDD a, double t){
return {a.x / t, a.y / t};
}

double operator* (PDD a, PDD b){
return a.x * b.y - a.y * b.x;
}

PDD sect(PDD p, PDD v, PDD q, PDD w){
auto u = p - q;
double t = w * u / (v * w);
return p + v * t;
}

PDD rotate(PDD a, double b){
return {a.x * cos(b) + a.y * sin(b), -a.x * sin(b) + a.y * cos(b)};
}

pair<PDD, PDD> line(PDD a, PDD b){
return {(a + b) / 2, rotate(b - a, PI / 2)};
}

double dist(PDD a, PDD b){
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}

circle get(PDD a, PDD b, PDD c){
auto u = line(a, b), v = line(a, c);
auto p = sect(u.x, u.y, v.x, v.y);
return {p, dist(p, a)};
}

int main(){
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%lf%lf", &q[i].x, &q[i].y);
random_shuffle(q, q + n);
circle c = {q[0], 0};
for(int i = 1; i < n; i++){
if(dcmp(c.r, dist(c.p, q[i])) < 0){
c = {q[i], 0};
for(int j = 0; j < i; j++){
if(dcmp(c.r, dist(c.p, q[j])) < 0){
c = {(q[i] + q[j]) / 2, dist(q[i], q[j]) / 2};
for(int k = 0; k < j; k++){
if(dcmp(c.r, dist(c.p, q[k])) < 0){
c = get(q[i], q[j], q[k]);
}
}
}
}
}
}
printf("%.10lf\n", c.r);
printf("%.10lf %.10lf", c.p.x, c.p.y);
return 0;
}


#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

// 注意这里视频中的写法是 M = 150010，数组会越界，可以改成M = N * 3 + 10。
const int N = 50010, M = N * 3 + 10;

int n;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
int q[N];
bool st[N];

void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void spfa()
{
memset(dist, -0x3f, sizeof dist);
dist[0] = 0;
st[0] = true;
int hh = 0, tt = 1;
q[0] = 0;

while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;

for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] < dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j])
{
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
}

int main()
{
scanf("%d", &n);

memset(h, -1, sizeof h);
for (int i = 1; i < N; i ++ )
{
}

for (int i = 0; i < n; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
a ++, b ++ ;
}

spfa();

printf("%d\n", dist[50001]);

return 0;
}


#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;
typedef long long LL;

const int N = 1e5 + 1, M = N * 3;
int h[N], ne[M], e[M], w[M], cnt[N], q[N];
int n, m, idx;
bool st[N];
LL dist[N];

void add(int u, int v, int c){
e[idx] = v, w[idx] = c, ne[idx] = h[u], h[u] = idx++;
}

bool spfa(){
int hh = 0, tt = 1;
memset(dist, -0x3f, sizeof dist);
st[0] = true;
dist[0] = 0;
q[0] = 0;
while(hh != tt){
int t = q[--tt];
if(hh == N) hh = 0;
st[t] = false;
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if(dist[j] < dist[t] + w[i]){
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n + 1) return false;
if(!st[j]){
q[tt++] = j;
st[j] = true;
}
}
}
}
return true;
}

int main(){
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while(m--){
int x, a, b;
scanf("%d%d%d", &x, &a, &b);
else if(x == 2) add(a, b, 1);
else if(x == 3) add(b, a, 0);
else if(x == 4) add(b, a, 1);
}
for(int i = 1; i <= n; i++) add(0, i, 1);

if(!spfa()) puts("-1");
else{
LL res = 0;
for(int i = 1; i <= n; i++) res += dist[i];
printf("%lld\n", res);
}
return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 25, M = 10;
int n, m;
int w[N], s[M];
double ans = 1e8;

double calc(){
memset(s, 0, sizeof s);
for(int i = 0; i < n; i++){
int k = 0;
for(int j = 0; j < m; j++){
if(s[j] < s[k])
k = j;
}
s[k] += w[i];
}

double avg = 0;
for(int i = 0; i < m; i++) avg += s[i] * 1.0 / m;
double res = 0;
for(int i = 0; i < m; i++) res += (s[i] - avg) * (s[i] - avg);
res = sqrt(res / m);
ans = min(ans, res);
return res;
}

void ysy(){
random_shuffle(w, w + n);

for(double t = 1e6; t >= 1e-6; t *= 0.99){
int a = rand() % n, b = rand() % n;
double x = calc();
swap(w[a], w[b]);
double y = calc();
double delta = y - x;
if(exp(-delta / t) < (double)rand() / RAND_MAX) swap(w[a], w[b]);
}
}

int main(){
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> w[i];
for(int i = 0; i < 100; i++) ysy();
printf("%.2lf\n", ans);
return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <ctime>

using namespace std;
#define x first
#define y second

typedef pair<int, int> PII;
const int N = 55;
PII q[N], p[N];
int n, m, ans;

int calc(){
int res = 0;
for(int i = 0; i < m; i++){
res += q[i].x + q[i].y;
if(i < n){
if(q[i].x == 10) res += q[i + 1].x + q[i + 1].y;
else if(q[i].x + q[i].y == 10)
res += q[i + 1].x;
}
}
ans = max(ans, res);
return res;
}

void simulate(){
for(double t = 1e4; t > 1e-4; t *= 0.99){
int a = rand() % m, b = rand() % m;
int x = calc();
swap(q[a], q[b]);
if(n + (q[n - 1].x == 10) == m){
int y = calc();
int delta = y - x;
if(exp(delta / t) < (double)rand() / RAND_MAX) swap(q[a], q[b]);
}
else swap(q[a], q[b]);
}
}

int main(){
cin >> n;
for(int i = 0; i < n; i++) cin >> q[i].x >> q[i].y;
if(q[n - 1].x == 10) m = n + 1, cin >> q[n].x >> q[n].y;
else m = n;
while((double)clock() / CLOCKS_PER_SEC < 0.8) simulate();
cout << ans << endl;
return 0;
}