头像

向往阳光的月光




离线:2个月前


最近来访(89)
用户头像
polarbearch
用户头像
芒果黄桃冰
用户头像
伊利强
用户头像
伊蕾娜我的伊蕾娜
用户头像
hysbetter
用户头像
zhangyuzhe
用户头像
Mark1St
用户头像
Joyasa
用户头像
鲶鱼饭
用户头像
这道题有点难耶
用户头像
最后
用户头像
小陈要努力
用户头像
Transcend
用户头像
光風霽月
用户头像
Hyperspace
用户头像
Unstoppable_Pikachu
用户头像
lgvc
用户头像
Atacama_Dessert
用户头像
@xixi@
用户头像
Epiphyllum

活动打卡代码 AcWing 1209. 带分数

向往阳光的月光
2021-03-12 20:17

暴力+剪枝法

#include <bits/stdc++.h>

using namespace std;


string str = "123456789";
bool st[10];
int n, ans, len;

void check(string a)
{

    for(int i = 1;i <= 8 && i <= len ;i ++)
    {
        string ta = a.substr(0, i);
        int na, nb, nc;
        na = atoi(ta.c_str());
        if(na >= n) continue;
        for(int j = 8 - i;j >= 1;j --)
        {
            if(j < 9 - i - j) continue;
            string tb = a.substr(i, j), tc = a.substr(i + j);
            nb = atoi(tb.c_str());
            nc = atoi(tc.c_str());
            //cout << na << " " << nb << " " << nc << endl;
            if(nb / nc < n - na) break;
            if(nb % nc != 0) continue;
            if(n == na + nb / nc) ans ++;
        }
    }
}

void dfs(int cur)
{
    if(cur == 9)
    {
        check(str);
        return;
    }

    for(int i = 1;i <= 9;i ++)
    {
        if(!st[i])
        {
            st[i] = true;
            str[cur] = i + '0';
            dfs(cur + 1);
            st[i] = false;
        }
    }
}


int main()
{
    cin >> n;

    string tmp = to_string(n);
    len = tmp.size();

    dfs(0);
    cout << ans << endl;
    return 0;
}
#include <bits/stdc++.h>

using namespace std;


string str = "123456789";
bool st[10];
int n, ans, len;

void check(string a)
{

    for(int i = 1;i <= 8 && i <= len ;i ++)
    {
        string ta = a.substr(0, i);
        int na, nb, nc;
        na = atoi(ta.c_str());
        if(na >= n) continue;
        for(int j = 8 - i;j >= 1;j --)
        {
            if(j < 9 - i - j) continue;
            string tb = a.substr(i, j), tc = a.substr(i + j);
            nb = atoi(tb.c_str());
            nc = atoi(tc.c_str());
            //cout << na << " " << nb << " " << nc << endl;
            if(nb / nc < n - na) break;
            if(nb % nc != 0) continue;
            if(n == na + nb / nc) ans ++;
        }
    }
}

void dfs(int cur)
{
    if(cur == 9)
    {
        check(str);
        return;
    }

    for(int i = 1;i <= 9;i ++)
    {
        if(!st[i])
        {
            st[i] = true;
            str[cur] = i + '0';
            dfs(cur + 1);
            st[i] = false;
        }
    }
}


int main()
{
    cin >> n;

    string tmp = to_string(n);
    len = tmp.size();

    dfs(0);
    cout << ans << endl;
    return 0;
}




向往阳光的月光
2021-03-11 22:21
#include <bits/stdc++.h>

using namespace std;

const int maxn = 30;

bool st[maxn];
int arr[maxn];
int n, m;

void dfs(int cur, int pre)
{
    if(cur == m + 1)
    {
        for(int i = 1;i <= m;i ++)
        {
            if(i != 1) cout << " ";
            cout << arr[i];
        }
        puts("");
        return;
    }

    for(int i = pre + 1;i <= n;i ++)
        if(!st[i])
        {
            st[i] = true;
            arr[cur] = i;
            dfs(cur + 1, i);
            st[i] = false;
        }

}

int main()
{
    cin >> n >> m;
    dfs(1, 0);
    return 0;
}


活动打卡代码 AcWing 717. 简单斐波那契

向往阳光的月光
2021-03-11 21:44
#include <bits/stdc++.h>

using namespace std;

const int maxn = 50;
int arr[maxn];

int main()
{
    int n;
    cin >> n;
    arr[1] = 0, arr[2] = 1;
    for(int i = 3;i <= n;i ++)
        arr[i] = arr[i - 1] + arr[i - 2];

    for(int i = 1;i <= n ;i ++)
    {
        if(i != 1) cout << " ";
        cout << arr[i];
    }
    puts("");
    return 0;
}



向往阳光的月光
2021-03-11 21:41
#include <bits/stdc++.h>

using namespace std;

const int maxn = 10;

bool st[maxn];
int arr[maxn];
int n;


void dfs(int cur)
{
    if(cur == n + 1)
    {
        for(int i = 1;i <= n;i ++)
        {
            if(i != 1) cout << " ";
            cout << arr[i];
        }
        cout << endl;
        return ;
    }

    for(int i = 1;i <= n;i ++)
        if(!st[i])
        {
            st[i] = true;
            arr[cur] = i; 
            dfs(cur + 1);
            st[i] = false;
        }
}

int main()
{
    cin >> n;
    dfs(1);
    return 0;
}



向往阳光的月光
2021-03-11 20:34
#include <iostream>

using namespace std;

const int maxn = 20;

bool arr[maxn];
int n;

void dfs(int cur)
{
    if(cur == n + 1)
    {
        bool flag = false;
        for(int i = 1;i <= n;i ++)
        {
            if(arr[i])
            {
                if(flag) cout << " ";
                else flag = true;
                cout << i;
            }
        }
        cout << endl;
        return;
    }

    dfs(cur + 1);
    arr[cur] = true;
    dfs(cur + 1);
    arr[cur] = false;
}

int main()
{

    cin >> n;
    dfs(1);
    return 0;
}


活动打卡代码 AcWing 1477. 拼写正确

向往阳光的月光
2020-11-08 16:49
#include <iostream>

using namespace std;


int main()
{
    string num;
    cin >> num;

    int sum = 0;
    for(auto c : num) sum += c - '0';


    char str[10][10] = {
        "zero", "one", "two", "three", "four", "five",
        "six", "seven", "eight", "nine"
    };

    string ans = to_string(sum);
    bool flag = false;
    for(auto c : ans)
        if(!flag) cout << str[c - '0'], flag = true;
        else cout << " " << str[c - '0'];
    cout << endl;
}


活动打卡代码 AcWing 1473. A + B 格式

向往阳光的月光
2020-11-08 16:27
#include <bits/stdc++.h>

using namespace std;


int main()
{
    int a, b;
    cin >> a >> b;
    int c = a + b;
    string d = to_string(c);

    string res;
    for(int i = d.size() - 1, j = 0;i >= 0;i --)
    {
        res = d[i] + res;
        j ++;
        if(j % 3 ==0  && i && d[i - 1] != '-') res = "," + res;
    }

    cout << res <<endl;
    return 0;
}


活动打卡代码 AcWing 1183. 电力

向往阳光的月光
2020-10-27 20:27
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int maxn = 10010, maxm = 30010;

int h[maxn], e[maxm], ne[maxm], idx;
int dfn[maxn], low[maxn], timestamp;
int root, ans;
int n, m;

void init()
{
    memset(h, -1, sizeof h);
    memset(dfn, 0, sizeof dfn);
    memset(low, 0, sizeof low);
    idx = 0, timestamp = 0;
    ans = 0;
}

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

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;

    int cnt = 0;
    for(int i = h[u];~i;i = ne[i])
    {
        int ver = e[i];
        if(!dfn[ver])
        {
            tarjan(ver);
            low[u] = min(low[u], low[ver]);
            if(low[ver] >= dfn[u]) cnt ++;
        }
        else low[u] = min(low[u], dfn[ver]);
    }

    if(u != root) cnt ++;

    ans = max(ans, cnt);
}

int main()
{
    while(scanf("%d%d", &n, &m), n || m)
    {
        init();
        while(m --)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            add(a, b), add(b, a);
        }

        int cnt = 0;
        for(root = 0;root < n;root ++)
            if(!dfn[root])
            {
                cnt ++;
                tarjan(root);
            }

        printf("%d\n", ans + cnt - 1);
    }
    return 0;
}



活动打卡代码 AcWing 395. 冗余路径

向往阳光的月光
2020-10-27 17:38
#include <iostream>
#include <cstring>
using namespace std;

const int maxn = 5010, maxm = 20010;


int h[maxn], e[maxm], ne[maxm], idx;
int dfn[maxn], low[maxn], timestamp;
int dcc_cnt, id[maxn], dg[maxn];
int stk[maxn], tt;
bool is_bridge[maxm];
int n, m;

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

void tarjan(int u, int from)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[++ tt] = u;

    for(int i = h[u];~i;i = ne[i])
    {
        int ver = e[i];
        if(!dfn[ver])
        {
            tarjan(ver, i);
            low[u] = min(low[ver], low[u]);
            if(dfn[u] < low[ver])
                is_bridge[i] = is_bridge[i ^ 1] = true;
        }
        else if(i != (from ^ 1))
            low[u] = min(low[u], low[ver]);
    }

    if(dfn[u] == low[u])
    {
        dcc_cnt ++;
        int y;
        do
        {
            y = stk[tt --];
            id[y] = dcc_cnt;
        }while(y != u);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while(m --)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    tarjan(1, -1);

    for(int i = 0;i < idx;i ++)
        if(is_bridge[i])
            dg[id[e[i]]] ++;

    int cnt = 0;
    for(int i = 1;i <= dcc_cnt;i ++)
        if(dg[i] == 1)
            cnt ++;
    printf("%d\n", (cnt + 1)/2);
    return 0;
}



活动打卡代码 AcWing 2280. 最优标号

向往阳光的月光
2020-10-08 12:47
#include <iostream>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 510, maxm = (maxn + maxn + 3010) * 2, INF = 1e8;

int h[maxn], e[maxm], ne[maxm], f[maxm], idx;
int cur[maxn], d[maxn], q[maxn];
int n, m, k, S, T;
pii edge[maxm];
int id[maxn];

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

void build(int c)
{
    memset(h, -1, sizeof h);
    idx = 0;
    for(int i = 1;i <= m;i ++)
    {
        int a = edge[i].x, b = edge[i].y;
        add(a, b, 1, 1);
    }

    for(int i = 1;i <= n;i ++)
    {
        if(id[i] >= 0) 
        {
            if(id[i] >> c & 1) add(i, T, INF, 0);
            else add(S, i, INF, 0);
        }
    }
}

bool bfs()
{
    int hh = 0, tt = 0;
    memset(d, -1 ,sizeof d);
    q[0] = S, d[S] = 0, cur[S] = h[S];
    while(hh <= tt)
    {
        int t = q[hh ++];
        for(int i = h[t];~i; i =ne[i])
        {
            int ver = e[i];
            if(d[ver] == -1 && f[i])
            {
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if(ver == T) return true;
                q[++ tt] = ver;
            }
        }
    }
    return false;
}

int find(int u, int limit)
{
    if(u == T) return limit;
    int flow = 0;
    for(int i = cur[u];~i && flow < limit; i = ne[i])
    {
        cur[u] = i;
        int ver = e[i];
        if(d[ver] == d[u] + 1 && f[i])
        {
            int t = find(ver, min(limit - flow, f[i]));
            if(!t) d[ver] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

ll dinic(int c)
{
    build(c); 
    int t = 0, flow;
    while(bfs()) while(flow = find(S, INF)) t += flow;
    return t;
}

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

    S = 0, T = n + 1;
    for(int i = 1;i <= m;i ++)
        scanf("%d%d", &edge[i].x, &edge[i].y);

    scanf("%d", &k);
    memset(id, -1, sizeof id);
    for(int i = 1;i <= k;i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        id[a] = b;
    }

    ll res = 0;
    for(int i = 0;i <= 30;i ++)
        res += dinic(i) << i;
    printf("%lld\n", res);
    return 0;
}