头像

Rainsheep




离线:1天前


最近来访(29)
用户头像
HfjNUlYZ
用户头像
白茶坔乌龙
用户头像
wsh0924
用户头像
xueshenwudi
用户头像
max2021
用户头像
AraneaDawn
用户头像
陈奕含
用户头像
Aigrl
用户头像
数集低微分方程
用户头像
深入浅出
用户头像
种花家的市长
用户头像
.yxc.
用户头像
Abel51
用户头像
zzmm
用户头像
AvariceZhao
用户头像
执笔抉择
用户头像
Tito_
用户头像
想去偷脑子
用户头像
tuffynibbles
用户头像
haeyeon


Rainsheep
13天前

rt



活动打卡代码 AcWing 165. 小猫爬山

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;
}


活动打卡代码 AcWing 2680. 均分数据

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;
}



活动打卡代码 AcWing 2424. 保龄球

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;
}



活动打卡代码 AcWing 3167. 星星还是树

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;
}



活动打卡代码 AcWing 292. 炮兵阵地

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("-fthread-jumps")
#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("-fhoist-adjacent-loads")
#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;
}


活动打卡代码 AcWing 1064. 小国王

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> head[S]; // 所有可从i转移到的状态
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))
                head[i].push_back(j);
        }

    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 t = head[a][b];
                    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;
}


活动打卡代码 AcWing 327. 玉米田

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; //所有可行的状态
vector<int>head[S]; //可以从状态i转移到的状态

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;
                head[i].push_back(j);
            }
        }

    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)
            {
                int t = head[a][b];
                dp[i][a] = (dp[i][a] + dp[i - 1][t]) % mod; 
            }
        }

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

    return 0;
}



活动打卡代码 AcWing 2534. 树上计数2

Rainsheep
24天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
/*
需要用到的算法:
离散化,欧拉序,LCA,树上莫队,
*/

#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 head[N], idx = 0;
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;
    edges[idx] = {to, head[from]};
    head[from] = idx;
    return ;
}

int top = 0;

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

    for(int i(head[cur]);i;i = edges[i].nxt)
    {
        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];

    for(int i(head[cur]);i;i = edges[i].nxt)
    {
        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];
}

inline void add(int x)
{
    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);
        link(from, to);
        link(to, from);
    }

    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)
            add(seq[lptr ++ ]);
        while(lptr > l)
            add(seq[-- lptr]);
        while(rptr < r)
            add(seq[++ rptr]);
        while(rptr > r)
            add(seq[rptr --]);

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

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

    return 0;
}


活动打卡代码 AcWing 2521. 数颜色

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];

inline void add(int x)
{
    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)
            add(w[-- lptr]);
        while(rptr < r)
            add(w[++ rptr]);
        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]);
                add(upd[tptr].x);
            }
            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]);
                add(upd[tptr].x);
            }
            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;
}