Rainsheep

1019

HfjNUlYZ

wsh0924
xueshenwudi
max2021

Aigrl

.yxc.
Abel51
zzmm
AvariceZhao

Tito_

tuffynibbles
haeyeon

Rainsheep
13天前

rt

Rainsheep
19天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<bits/stdc++.h>

using namespace std;

int n, m;

const int N = 20;

int w[N], sum[N];
int res;

inline void dfs(int cur,  int k)
{
if(k >= res)
return ;
if(cur == n + 1)
{
res = k;
return ;
}

for(int i(1);i <= k; ++ i)
if(sum[i] + w[cur] <= m)
{
sum[i] += w[cur];
dfs(cur + 1, k);
sum[i] -= w[cur];
}

++ k;
sum[k] = w[cur];
dfs(cur + 1, k);
sum[k] = 0;

return ;
}

int main()
{

scanf("%d %d", &n, &m);
res = n;

for(int i(1);i <= n; ++ i)
scanf("%d", &w[i]);

sort(w + 1, w + 1 + n);
reverse(w + 1, w + 1 + n);

dfs(1, 1);

printf("%d", res);

return 0;
}


Rainsheep
21天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<bits/stdc++.h>

using namespace std;

const int N = 30;
const int M = 20;

int w[N], s[M];
int n, m;

double ans = 1e8;

inline double max(double x, double y)
{
return x > y ? x : y;
}

inline double calc()
{
//random_shuffle(w + 1, w + 1 +n);
memset(s, 0, sizeof s);

for(int i(1);i <= n; ++ i)
{
int k = 1;
for(int j(2);j <= m; ++ j)
if(s[j] < s[k])
k = j;
s[k] += w[i];
}

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

inline void simulate_anneal()
{
random_shuffle(w + 1, w + 1 + n);

for(double t(1e6);t > 1e-6; t *= 0.99)
{
int x = rand() % n + 1;
int y = rand() % n + 1;
double pre = calc();
swap(w[x], w[y]);
double now = calc();
double delta = now - pre;

if(exp(- delta / t) < (double)rand() / RAND_MAX)
swap(w[x], w[y]);
}

return ;
}

int main()
{
//srand(time(0));

scanf("%d %d", &n, &m);

for(int i(1);i <= n; ++ i)
scanf("%d", &w[i]);

while((double)clock() / CLOCKS_PER_SEC < 0.98)
simulate_anneal();

printf("%.2lf", ans);

return 0;
}



Rainsheep
21天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second

const int N = 55;
int n, m;

typedef pair<int, int> PII;

PII a[N];
int ans = 0;

inline int max(int x, int y)
{
return x > y ? x : y;
}

inline int calc()
{

int res = 0 ;
for(int i(1);i <= m; ++ i)
{
res += a[i].x + a[i].y;
if(a[i].x == 10)
res += a[i + 1].x + a[i + 1].y;
else if(a[i].x + a[i].y == 10)
res += a[i + 1].x;
}

ans = max(ans, res);

return res;
}

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

int main()
{

scanf("%d", &n);

m = n;

for(int i(1);i <= n; ++ i)
scanf("%d %d", &a[i].x, &a[i].y);

if(a[n].x == 10 and a[n].y == 0)
++ m, scanf("%d %d", &a[m].x, &a[m].y);

//while((double)clock() / CLOCKS_PER_SEC < 0.8)
//  simulate_anneal();

for (int i = 1; i <= 100; i ++ ) simulate_anneal();

printf("%d", ans);

return 0;
}



Rainsheep
21天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;

const int N = 110;
const double X = 10000.00;
const double Y = 10000.00;

PDD pt[N];

int n;

double res = 1e8;

inline double min(double x, double y)
{
return x < y ? x : y;
}

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

inline double calc(PDD p)
{
double t = 0.00;
for(int i(1);i <= n; ++ i)
t += get_dist(p, pt[i]);
res = min(res, t);
return t;
}

inline double rand(double l, double r)
{
return (double)rand() / RAND_MAX * (r - l) + l;
}

inline void simulate_anneal()
{
PDD cur(rand(0, X), rand(0, Y)); // 初始点
for(double t = 1e4;t > 1e-4; t *= 0.9) // 初温
{
PDD np (rand(cur.x - t, cur.x + t), rand(cur.y - t, cur.y + t));
double delta = calc(np) - calc(cur);
if(exp(- delta / t) > rand(0, 1))
cur = np;
}
return ;
}

int main()
{

scanf("%d", &n);

for(int i(1);i <= n; ++ i)
scanf("%lf %lf", &pt[i].x, &pt[i].y);

for(int i = 1;i <= 100; ++ i)
simulate_anneal();

printf("%.0lf", res);

return  0;
}



Rainsheep
21天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include<bits/stdc++.h>

using namespace std;

const int N(101);
const int M(12);
const int S(1024);

int n, m;
int dp[2][S][S]; //摆放前i行，第i行状态为j，第i - 2行状态是k的方案中的最大值
int g[N];
int cnt[N];
vector<int>state;

inline bool check(int state)
{
for(register int i(0);i < m ; ++ i)
if((state >> i & 1) and ((state >> i + 1 & 1) or (state >> i + 2 & 1)))
return false;
return true;
}

inline int count(int state)
{
int res = 0 ;
for(int i(0);i < m; ++ i)
res += state >> i & 1;
return res;
}

int main()
{
scanf("%d %d", &n, &m);
for(register int i(1);i <= n; ++ i)
for(register int j(0);j < m; ++ j)
{
char c;
cin >> c;
if(c == 'H')
g[i] |= 1 << j;
}

for(register int i(0);i < 1 << m; ++ i)
if(check(i))
{
//cerr << "114514" << endl;
state.push_back(i);
cnt[i] = count(i);
}

for(register int i(1);i <= n + 2; ++ i)
for(register int j(0);j < state.size(); ++ j)
for(register int k(0);k < state.size(); ++ k)
for(register int l(0);l < state.size(); ++ l)
{
int a(state[j]);
int b(state[k]);
int c(state[l]);
if(a & g[i] or b & g[i - 1])
continue;
if((a & b) or (a & c) or (b & c))
continue;
dp[i & 1][j][k] = max(dp[i & 1][j][k], dp[i - 1 & 1][k][l] + cnt[a]);
}

printf("%d", dp[n + 2 & 1][0][0]);

return 0;
}


Rainsheep
22天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 20;
const int M = 110; // 国王的个数
const int S = 1 << 10; //最大的状态

ll dp[N][M][S]; //前i行摆放j个皇后并且第i - 1行是k的所有方案数
int n, m;
int cnt[S]; //方案i所含的1数量

vector<int>state; // 所有合法的状态

inline bool check(int state)
{
//有连续的两个1即为不合法
for(int i(0);i < n; ++ i)
if((state >> i & 1) and (state >> (i + 1) & 1))
return false;
return true;
}

inline int count(int x)
{
int res = 0;
for(int i(0);i < n; ++ i)
res += x >> i & 1;
return res;
}

int main()
{

scanf("%d %d", &n, &m);

for(int i(0);i < 1 << n; ++ i)
if(check(i))
{
state.push_back(i);
cnt[i] = count(i);
}

//枚举所有合法的状态

for(int i(0);i < state.size(); ++ i)
for(int j(0);j < state.size(); ++ j)
{
int a = state[i];
int b = state[j];
if((a & b) == 0 and check(a | b))
}

dp[0][0][0] = 1;

for(int i(1);i <= n + 1; ++ i) //前i排
for(int j(0);j <= m; ++ j) // j皇后
for(int a(0); a < state.size(); ++ a) //枚举所有状态
for(int b(0); b < head[a].size(); ++ b) // 枚举所有能从a转移过来的其他状态
{
//更新方案
int c = cnt[state[a]];
if(j >= c)
dp[i][j][a] += dp[i - 1][j - c][t];
}

printf("%lld", dp[n + 1][m][0]);

return 0;
}


Rainsheep
22天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<bits/stdc++.h>

using namespace std;

const int N = 20;
const int S = 1 << 12;
const int mod = 100000000;

int n, m;
int dp[N][S]; // 种植了i行，且第i行的状态为j的所有方案数
int g[N];
vector<int>state; //所有可行的状态

inline bool check(int state)
{
/*
for(int i(0);i < n; ++ i)
if((state >> i & 1) and (state >> i + 1))
return false;
return true;
*/
return !(state & state << 1);
}

int main()
{

scanf("%d %d", &n, &m);

for(int i(1);i <= n; ++ i)
for(int j(0);j < m; ++ j)
{
int t;
scanf("%d", &t);
g[i] |= !t << j;
}

//预处理下所有的状态
for(int i(0);i < 1 << m; ++ i)
if(check(i))
{
state.push_back(i);
//cerr << i << endl;
}

for(int i(0);i < state.size(); ++ i)
for(int j(0);j < state.size(); ++ j)
{
int a = state[i];
int b = state[j];
if((a & b) == 0) //没有上下都种的地方
{
//cerr << "GET!" << endl;
}
}

dp[0][0] = 1;

for(int i(1);i <= n + 1; ++ i)
for(int a(0);a < state.size(); ++ a) // 枚举转移过来的状态
{
if(state[a] & g[i]) // 选的状态不能和贫瘠土地重合
continue;

for(int b(0);b < head[a].size(); ++ b)
{
dp[i][a] = (dp[i][a] + dp[i - 1][t]) % mod;
}
}

printf("%d", dp[n + 1][0]);

return 0;
}



Rainsheep
24天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
/*

*/

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
const int M = 1e5 + 10;

int len, n, m;
int depth[N], fa[N][25];
int seq[N];
int res = 0, ans[M], cnt[N], st[N];
int first[N], last[N];
int w[N];
int lptr = 1, rptr = 0;
vector<int> nums;

struct Edge
{
int to;
int nxt;
} edges[N << 1];

inline int get(int x)
{
return x / len;
}

struct Query
{
int id;
int l, r;
int p;

bool operator < (const Query &W)const
{
return get(l) == get(W.l) ? r < W.r : get(l) < get(W.l);
}
} q[M];

inline void link(int from, int to)
{
++ idx;
return ;
}

int top = 0;

inline void dfs_Euler(int cur, int pa) // 处理欧拉序
{
seq[++ top] = cur;
first[cur] = top;

{
int to = edges[i].to;

if(to == pa)
continue;

dfs_Euler(to, cur);
}

seq[++ top] = cur;
last[cur] = top;

return ;
}

inline void dfs(int cur, int pa)
{

depth[cur] = depth[pa] + 1;
fa[cur][0] = pa;

for(int i(1);i <= 20; ++ i)
fa[cur][i] = fa[fa[cur][i -1]][i - 1];

{
int to = edges[i].to;
if(to == pa)
continue;
dfs(to, cur);
}

return ;
}

inline int lca(int from, int to)
{
if(depth[from] < depth[to])
{
from = from ^ to;
to = from ^ to;
from = from ^ to;
}

int d = depth[from] - depth[to];

for(int i(0);i <= 20; ++ i)
{
if(d & 1)
from = fa[from][i];
d >>= 1;
}

if(from == to)
return from;

for(int i(20);i >= 0; -- i)
{
if(fa[from][i] == fa[to][i])
continue;

from = fa[from][i];
to = fa[to][i];
}

return fa[from][0];
}

{
st[x] = ~ st[x];

if(st[x])
{
if(!cnt[w[x]])
++ res;
++ cnt[w[x]];
}
else
{
-- cnt[w[x]];
if(!cnt[w[x]])
-- res;
}

return ;
}

int main()
{

memset(st, 0, sizeof st);

scanf("%d %d", &n, &m);

for(int i(1);i <= n; ++ i)
{
scanf("%d", &w[i]);
nums.push_back(w[i]);
}

//离散化

sort(nums.begin(), nums.end());

nums.erase(unique(nums.begin(), nums.end()), nums.end());

for(int i(1);i <= n; ++ i)
w[i] = lower_bound(nums.begin(), nums.end(), w[i]) - nums.begin();

for(int i(1);i <= n - 1; ++ i)
{
int from, to;
scanf("%d %d", &from, &to);
//printf("%d %d\n", from, to);
}

dfs(1, 0); // 跑一遍lca
dfs_Euler(1, 0); //跑一遍欧拉序

/*
puts("err");
for(int i(1);i <= n; ++ i)
printf("%d\n", fa[i][0]);
*/

len = sqrt(top);

for(int i(1);i <= m; ++ i)
{
int a, b;
scanf("%d %d", &a, &b);

if(first[b] < first[a])
{
a = a ^ b;
b = a ^ b;
a = a ^ b;
}

if(lca(a, b) == a) //询问的两个点在一条链上
q[i] = {i, first[a], first[b], 0};
else //不在一条链上，欧拉序中缺少lca
q[i] = {i, last[a], first[b], lca(a, b)};

}

sort(q + 1, q + 1 + m);

for(int i(1);i <= m; ++ i)
{
int id = q[i].id;
int l = q[i].l, r = q[i].r;
int p = q[i].p;

while(lptr < l)
while(lptr > l)
while(rptr < r)
while(rptr > r)

if(p)
ans[id] = res;
if(p)
}

for(int i(1);i <= m; ++ i)
{
printf("%d", ans[i]);
putchar('\n');
}

return 0;
}


Rainsheep
25天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
const int M = 1e5 + 10;
const int S = 1e6 + 10;

int lptr = 1, rptr = 0, tptr = 0;
int len;
int w[S], cnt[S], res = 0;
int n, m;
int mq = 0, mu = 0;
int ans[S];

inline int get(int x)
{
return x / len;
}

struct Query
{
int l, r;
int t; // 时间戳
int idx;

bool operator < (const Query &W)const
{
int al = get(l), ar = get(r);
int bl = get(W.l), br = get(W.r);

if(al != bl)
return al < bl;
if(ar != br)
return ar < br;
return t < W.t;
}
} q[S];

struct Update
{
int pos;
int x;
} upd[S];

{
if(!cnt[x])
++ res;
++ cnt[x];
return ;
}

inline void del(int x)
{
-- cnt[x];
if(!cnt[x])
-- res;
return ;
}

int main()
{

scanf("%d %d", &n, &m);

for(int i(1);i <= n; ++ i)
scanf("%d", &w[i]);

char op[2];
int l,  r;

for(int i(1);i <= m; ++ i)
{
scanf("%s %d %d", op, &l, &r);

if(*op == 'Q')
q[++ mq] = {l, r, mu, mq};
else
upd[++ mu] = {l, r};
}

len = sqrt(n);

sort(q + 1, q + 1 + mq);

for(int i(1);i <= mq; ++ i)
{
int idx = q[i].idx;
int l = q[i].l, r = q[i].r;
int t = q[i].t;

while(lptr < l)
del(w[lptr ++ ]);
while(lptr > l)
while(rptr < r)
while(rptr > r)
del(w[rptr -- ]);

while(tptr < t) //更新版本
{
++ tptr;
if(upd[tptr].pos >= lptr and upd[tptr].pos <= rptr)
{
del(w[upd[tptr].pos]);
}
w[upd[tptr].pos] = w[upd[tptr].pos] ^ upd[tptr].x;
upd[tptr].x = w[upd[tptr].pos] ^ upd[tptr].x;
w[upd[tptr].pos] = w[upd[tptr].pos] ^ upd[tptr].x;
}

while(tptr > t) //追踪旧版本
{
if(upd[tptr].pos >= lptr and upd[tptr].pos <= rptr)
{
del(w[upd[tptr].pos]);
}
w[upd[tptr].pos] = w[upd[tptr].pos] ^ upd[tptr].x;
upd[tptr].x = w[upd[tptr].pos] ^ upd[tptr].x;
w[upd[tptr].pos] = w[upd[tptr].pos] ^ upd[tptr].x;
-- tptr;
}

ans[idx] = res;
}

for(int i(1);i <= mq; ++ i)
{
printf("%d", ans[i]);
putchar('\n');
}

return 0;
}