头像

Anoxia_3


访客:4679

离线:7小时前


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

Anoxia_3
8小时前
#include <iostream>
#include <vector>

using namespace std;

const int  M = 1 << 10;

int n , m;
int g[110];
int f[2][M][M];
vector<int> state;
int cnt[M];

bool check(int state)
{
    return !((state >> 1 & state) || (state << 1 & state) || (state >> 2 & state) || (state << 2 & state));
}

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

    return res;
}

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

    for(int i = 1 ; i <= n ; i++)
        for(int j = 0 ; j < m ; j++)   
        {
            char c;
            cin >> c;
            if(c == 'H') g[i] += 1 << j;
        }

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


    for(int i = 1 ; i <= n + 2 ; i++)
        for(int a = 0 ; a < state.size() ; a++)
            for(int b = 0 ; b < state.size() ; b++)
                for(int c = 0 ; c < state.size() ; c++)
                {
                    int x = state[a] , y = state[b] , z = state[c];
                    if(x & y | x & z | y & z) continue;
                    if(x & g[i] | y & g[i - 1]) continue;
                    f[i & 1][a][b] = max(f[i - 1 & 1][b][c] + cnt[x] , f[i & 1][a][b]);
                }

    cout << f[n + 2 & 1][0][0] << endl;
    return 0;
}


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

Anoxia_3
9小时前
#include <iostream>
#include <vector>

using namespace std;

const int N = 15 , M = 1 << 12 , mod = 1e8;

int n , m;
int g[N];
int f[N][M];
vector<int> state;
vector<int> head[M];

bool check(int state)
{
    return !((state >> 1 & state) && (state << 1 & state));
}

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

    for(int i = 1 ; i <= n ; i++)
        for(int j = 0 ; j < m ; j++)   
        {
            int t;
            cin >> t;
            g[i] += !t * (1 << j);
        }

    for(int i = 0 ; i < 1 << m ; i++)
        if(check(i))
            state.push_back(i);

    for(int i = 0 ; i < state.size() ; i++)
        for(int j = 0 ; j < state.size() ; j++)
        {
            int a = state[i] , b = state[j];
            if(!(a & b))
                head[i].push_back(j);
        }

    f[0][0] = 1;
    for(int i = 1 ; i <= n + 1 ; i++)
        for(int j = 0 ; j < state.size() ; j++)
            if(!(state[j] & g[i]))
                for(auto k : head[j])
                    f[i][j] = (f[i][j] + f[i - 1][k]) % mod;

    cout << f[n + 1][0] << endl;
    return 0;
}


活动打卡代码 AcWing 1064. 骑士

Anoxia_3
9小时前
#include <iostream>
#include <vector>

using namespace std;

const int N = 12 , M = 1 << N , K = 110;

typedef long long LL;

int n , m;
vector<int> state;
vector<int> head[M];
int cnt[M];
LL f[N][K][M];

bool check(int state)
{
    return !((state >> 1 & state) && (state << 1 & state));
}

int count(int state)
{
    int res = 0;
    for(int i = 0 ; i < n ; i++)
        if(state >> i & 1)
            res++;

    return res;
}

int main()
{
    cin >> 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] , b = state[j];
            if(check(a | b) && !(a & b))
                head[i].push_back(j);
        }        

    f[0][0][0] = 1;
    for(int i = 1 ; i <= n + 1 ; i++)
        for(int j = 0 ; j <= m ; j++)
            for(int a = 0 ; a < state.size() ; a++)
                for(int b : head[a])
                {
                    int c = cnt[state[a]];
                    if(c <= j)
                        f[i][j][a] += f[i - 1][j - c][b];
                }

    cout << f[n + 1][m][0] << endl;
    return 0;
}


活动打卡代码 AcWing 1052. 设计密码

Anoxia_3
16小时前
#include <iostream>
#include <cstring>

using namespace std;

const int N = 55 , mod = 1e9 + 7;

char str[N];
int f[N][N];//f[i][j]表示当前串的长度是i,并且可以和给定串匹配前j个字母的方案数
int n , m;
int ne[N];

int main()
{
    cin >> n >> str + 1;
    int m = strlen(str + 1);

    for(int i = 2 , j = 0 ; i <= m ; i++)
    {
        while(j && str[i] != str[j + 1]) j = ne[j];
        if(str[i] == str[j + 1]) j++;
        ne[i] = j;
    }

    f[0][0] = 1;
    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j < m ; j++)
            for(char k = 'a' ; k <= 'z' ; k++)
            {
                int u = j;
                while(u && str[u + 1] != k) u = ne[u];
                if(str[u + 1] == k) u++;
                if(u < m) f[i + 1][u] = (f[i + 1][u] + f[i][j]) % mod;//已经确定了i位,算上现在这位是第i+1位
            }

    int res = 0;
    for(int i = 0 ; i < m ; i++) res = (res + f[n][i]) % mod;

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


新鲜事 原文

Anoxia_3
17小时前
来试试新功能qaq


活动打卡代码 AcWing 1058. 股票买卖 V

QQ图片20200602105336.png

#include <iostream>

using namespace std;

const int N = 100010 , INF = 0x3f3f3f3f;

int w[N];
int f[N][3];
int n;

int main()
{
    cin >> n;

    for(int i = 1 ; i <= n ; i++)   cin >> w[i];

    f[0][0] = f[0][1] = -INF , f[0][2] = 0;

    for(int i = 1 ; i <= n ; i++)
    {
        f[i][0] = max(f[i - 1][0] , f[i - 1][2] - w[i]);
        f[i][1] = f[i - 1][0] + w[i];
        f[i][2] = max(f[i - 1][2] , f[i - 1][1]);
    }

    cout << max(f[n][1] , f[n][2]) << endl;
    return 0;
}


活动打卡代码 AcWing 1057. 股票买卖 IV

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010 , M = 110 , INF = 0x3f3f3f3f;

int w[N];
int f[N][M][2];
int n , m;

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

    for(int i = 1 ; i <= n ; i++)    cin >> w[i];

    memset(f , -0x3f , sizeof f);
    for(int i = 0 ; i <= n ; i++)   f[i][0][0] = 0;

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)   
        {
            f[i][j][0] = max(f[i - 1][j][1] + w[i] , f[i - 1][j][0]);
            f[i][j][1] = max(f[i - 1][j][1] , f[i - 1][j - 1][0] - w[i]);
        }

    int res = 0;
    for(int i = 0 ; i <= m ; i++) res = max(res , f[n][i][0]);

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 1049. 大盗阿福

#include <iostream>

using namespace std;

const int N = 100010 , INF = 0x3f3f3f3f;

int f[N][2] , w[N];

int main()
{
    int T;
    cin >> T;

    while(T--)
    {
        int n;
        cin >> n;
        for(int i = 1 ; i <= n ; i++) cin >> w[i];

        for(int i = 1 ; i <= n ; i++)
        {
            f[i][0] = max(f[i - 1][0] , f[i - 1][1]);
            f[i][1] = f[i - 1][0] + w[i];
        }

        cout << max(f[n][1] , f[n][0]) << endl;
    }
    return 0;
}


活动打卡代码 AcWing 734. 能量石

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

using namespace std;

const int N = 10010 , M = 110;

struct Stone{
    int s , e , l;
    bool operator < (const Stone &W) const{
        return s * W.l < l * W.s;
    }
}stone[M];

int f[N];//体积恰好为j,此时除了f[0]外,初始成负无穷,这题不需要
int n;

int main()
{
    int T;
    cin >> T;

    for(int C = 1 ; C <= T ; C++)
    {
        cin >> n;
        int m = 0;

        for(int i = 0 ; i < n ; i++)
        {
            int s , e , l;
            cin >> s >> e >> l;
            stone[i] = {s , e , l};
            m += s;
        }

        sort(stone , stone + n);

        memset(f , -0x3f , sizeof f);
        f[0] = 0;
        for(int i = 0 ; i < n ; i++)
        {
            int s = stone[i].s , e = stone[i].e , l = stone[i].l;
            for(int j = m ; j >= s ; j--)
                f[j] = max(f[j] , f[j - s] + e - (j - s) * l);
        }        

        int res = 0;
        for(int i = 0 ; i <= m ; i++)   res = max(f[i] , res);

        printf("Case #%d: %d\n" , C , res);
    }
    return 0;
}




设刚开始的钱是x,每两个人之间的利率是w
则100=x(w1w2w3..)
要想x最小,就要求w1w2w3..最大
即求log(w1w2w3..)=logw1 + logw2 + .. 最大,
因为w都是小于1的,所以logw都是小于0的,所以将每个数取相反数,
问题转化成求取反后的最小值,即转换成最短路问题

C++ 代码

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int N = 2010 , M = 200010;

int e[M] , ne[M] , h[N] , idx;
double d[M] , w[M];
bool st[N];
int n , m;

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

double spfa(int a , int b)
{
    memset(d , 0x3f , sizeof d);
    queue<int> q;
    q.push(a);
    d[a] = 1;

    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;

        for(int i = h[t] ; ~i ; i = ne[i])
        {
            int j = e[i];
            if(d[j] < d[t] * (1 - w[i]))
            {
                d[j] = d[t] * (1 - w[i]);
                if(!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    return d[b];
}

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

    memset(h , -1 , sizeof h);
    while(m--)
    {
        int a , b ,  c;
        cin >> a >> b >> c;
        add(a , b , 1.0 * c / 100) , add(b , a , 1.0 * c / 100);
    }

    int a , b;
    cin >> a >> b;
    printf("%.8lf\n" , 100 / spfa(a , b));
    return 0;
}