头像

合计飞

中北大学




离线:10分钟前


活动打卡代码 AcWing 1405. 牛奶量取

#include<bits/stdc++.h>

using namespace std;

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

int n, m;
int f[N][M], v[N];
vector<int> ans, path;

void dfs(int i, int j)
{
    if(!i)
    {
        if(ans.empty() || ans > path) ans = path;
        return ;
    }
    if(f[i][j] == f[i - 1][j]) dfs(i - 1, j);

    path.push_back(v[i]);
    for(int k = j - v[i]; k >= 0; k -= v[i])
        if(f[i][j] == f[i - 1][k] + 1)
            dfs(i - 1, k);
    path.pop_back();
}

int main()
{
    cin >> m >> n;
    for(int i = 1; i <= n; i ++) cin >> v[i];
    sort(v + 1, v + n + 1, greater<int>());
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 0; j < v[i]; j ++)
        {
            int mf = INF;
            for(int k = j; k <= m; k += v[i])
            {
                f[i][k] = min(f[i - 1][k], mf + 1);
                mf = min(mf, f[i - 1][k]);
            }
        }
    }

    cout << f[n][m];
    dfs(n, m);
    for(auto x : ans) cout << ' ' << x;
    return 0;
}


活动打卡代码 AcWing 3493. 最大的和

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 100010;

ll a[N], b[N], sum[N];

int main()
{
    ll n, k, res = 0;
    cin >> n >> k;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) 
    {
        cin >> b[i];
        if(b[i] == 1) 
        {
            res += a[i];
            a[i] = 0;
        }
        sum[i] = sum[i - 1] + a[i];
    }

    ll rr = 0;
    for(int i = 1; i <= n - k; i ++)
        rr = max(rr, sum[i + k - 1] - sum[i - 1]);
    cout << res + rr << endl;
    return 0;
}


活动打卡代码 AcWing 1404. 蜗牛漫步

#include<bits/stdc++.h>

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

typedef pair<int, int> PII;
const int N = 130;

int n, b, dis;
int g[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};  

void dfs(int sx, int sy, int d, int k)
{
    if(sx < 0 || sx >= n || sy < 0 || sy >= n || g[sx][sy]) return ;
    stack<PII> s;
    while(sx >= 0 && sx < n && sy >= 0 && sy < n && g[sx][sy] == 0)
    {
        s.push({sx, sy});
        g[sx][sy] = 2;
        sx += dx[d], sy += dy[d];
        k ++;
    }
    dis = max(k, dis);
    if(sx < 0 || sx >= n || sy < 0 || sy >= n || g[sx][sy] == 1)
    {
        sx -= dx[d], sy -= dy[d];
        for(int i = 0; i < 4; i ++)
            if((i + d) & 1)
                dfs(sx + dx[i], sy + dy[i], i, k);
    }

    while(s.size())
    {
        auto t = s.top();
        g[t.x][t.y] = 0;
        s.pop();
    }
}

int main()
{
    cin >> n >> b;
    while(b --)
    {
        char c;
        int d;
        cin >> c >> d;
        c -= 'A';
        g[d - 1][c] = 1;
    }

    dfs(0, 0, 1, 0);
    dfs(0, 0, 2, 0);
    cout << dis << endl; 
    return 0;
} 


活动打卡代码 AcWing 1403. 音乐主题

#include<bits/stdc++.h>

#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 5010;

int n;
int a[N], f[N][N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];

    int res = 0;
    for(int i = n; i ; i --)
        for(int j = n; j > i; j --)
        {
            if(j ==  n || a[j] - a[i] != a[j + 1] - a[i + 1])
                f[i][j] = 1;
            else 
                f[i][j] = f[i + 1][j + 1] + 1;
            res = max(res, min(f[i][j], j - i));                                                
        }
    if(res < 5) res = 0;
    cout << res << endl;
    return 0;
} 


活动打卡代码 AcWing 1402. 星空之夜

#include<bits/stdc++.h>

#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 110;

int n, m, top, cnt;
char g[N][N];
PII q[N * N];
double hs[N];

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

double get_hash()
{
    double res = 0;
    for(int i = 0; i < top; i ++)
        for(int j = i + 1; j < top; j ++)
            res += get_dist(q[i], q[j]); 
    return res;
}

char get_id(double x)
{
    for(int i = 0; i < cnt; i ++)
        if(fabs(x - hs[i]) < 1e-6)
            return i + 'a';
    hs[cnt ++] = x;
    return cnt - 1 + 'a';
}

void dfs(int a, int b)
{
    g[a][b] = 0;
    q[top ++] = {a, b};
    for(int i = a - 1; i <= a + 1; i ++)
        for(int j = b - 1; j <= b + 1; j ++)
            if(i != a || j != b)
                if(i >= 0 && i < n && j >= 0 && j < m && g[i][j] == '1')
                    dfs(i, j);
}

int main()
{
    cin >> m >> n;
    for(int i = 0; i < n; i ++) cin >> g[i];

    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m;  j ++)
            if(g[i][j] == '1')
            {
                top = 0;
                dfs(i, j);

                char c = get_id(get_hash());
                for(int k = 0; k < top; k ++)
                    g[q[k].x][q[k].y] = c;
            }
    for(int i = 0; i < n; i ++) cout << g[i] << endl;  
    return 0;
} 


活动打卡代码 AcWing 1401. 围住奶牛

#include<bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;
const int N = 10010;

int n;
PDD q[N];
int s[N], tt;
bool st[N];

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

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

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

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

double get_convex()
{

    sort(q, q + n);
    for(int i = 0; i < n; i ++)
    {
        while(tt >= 2 && area(q[s[tt - 1]], q[s[tt]], q[i]) <= 0)
            if(area(q[s[tt - 1]], q[s[tt]], q[i]) < 0)
                st[s[tt --]] = false;
            else tt --;
        s[++ tt] = i;
        st[i] = true;
    }
    st[s[0]] = false;

    for(int i = n - 1; i >= 0; i --)
    {
        if(st[i]) continue;
        while(tt >= 2 && area(q[s[tt - 1]], q[s[tt]], q[i]) <= 0)
            tt --;
        s[ ++ tt] = i;

    }
//  cout << "#" << endl;
    double res = 0;
    for(int i = 0; i < tt; i ++)
        res += get(q[s[i]], q[s[i + 1]]);
    return res;
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++) scanf("%lf%lf", &q[i].x, &q[i].y);
    printf("%.2lf\n", get_convex());
    return 0;
}


活动打卡代码 AcWing 1400. 堆叠相框

#include<bits/stdc++.h>

using namespace std;

const int N = 40;

int n, m;
char str[N][N];
bool g[N][N], st[N];
int d[N];
string path;

void work(int x1, int y1, int x2, int y2, char c)
{
    for(int i = x1; i <= x2; i ++)
        for(int j = y1; j <= y2; j ++)
            if(str[i][j] != c && str[i][j] != '.')
            {
                int a = c - 'A', b = str[i][j] - 'A';
                if(!g[a][b])
                {
                    g[a][b] = true;
                    d[b] ++;
                }
            }

}

void dfs(string s)
{
    if(s.empty())
    {
        cout << path << endl;
        return ;
    }
    sort(s.begin(), s.end());
    for(int i = 0; i < s.size(); i ++)
    {
        char c = s[i];
        path += c;
        string w = s.substr(0, i) + s.substr(i + 1);
        for(int j = 0; j < 26; j ++) 
            if(g[c - 'A'][j] && --d[j] == 0) 
                w += j + 'A';
        dfs(w);
        for(int j = 0; j < 26; j ++)
            if(g[c - 'A'][j])
                d[j] ++;
        path.pop_back();
    }
}

void topsort()
{
    string s;
    for(int i = 0; i < 26; i ++)
        if(st[i] && !d[i])
            s += i + 'A';
        dfs(s);
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++) cin >> str[i];
    for(int i = 'A'; i <= 'Z'; i ++)
    {
        int x1 = N, x2 = -1, y1 = N, y2 = -1;
        for(int j = 0; j < n; j ++)
            for(int k = 0; k < m; k ++)
                if(str[j][k] == i)
                {
                    x1 = min(x1, j), x2 = max(x2, j);
                    y1 = min(y1, k), y2 = max(y2, k);
                }
        if(x1 == N) continue;
        work(x1, y1, x1, y2, i);
        work(x1, y1, x2, y1, i);
        work(x1, y2, x2, y2, i);
        work(x2, y1, x2, y2, i);
        st[i - 'A'] = true;
    }

    topsort();

    return 0;
}


活动打卡代码 AcWing 1399. 控制污染奶

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 40, M = 2010, K = 10000;
const ll INF = 1e18;

int n, m, S, T;
int h[N], e[M], ne[M], idx;
int d[N], cur[N];
ll f[M];

void init()
{
    for(int i = 0; i < idx; i += 2)
    {
        f[i] += f[i ^ 1];
        f[i ^ 1] = 0;
    }
}

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

//建分层图 
bool bfs()
{
    memset(d, -1, sizeof d);
    queue<int> q;
    q.push(S);
    d[S] = 0;
    cur[S] = h[S];
    while(q.size())
    {
        auto t = q.front();
        q.pop();

        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if(f[i] && d[j] == -1)
            {
                cur[j] = h[j]; 
                d[j] = d[t] + 1;
                if(j == T) return true;
                q.push(j);
            }
        }
    }
    return false;
}

//增广 
ll dfs(int s, ll mf)
{
    if(s == T) return mf;
    for(int i = cur[s]; ~i; i = ne[i])
    {
        cur[s] = i;
        int j = e[i];
        if(f[i] <= 0 || d[j] != d[s] + 1) continue;
        ll cf = dfs(j, min(mf, f[i]));
        if(cf <= 0) continue;
        f[i] -= cf;
        f[i ^ 1] += cf;
        return cf;
    }
    return 0;
}

ll dinic()
{
    ll res = 0, flow;
    while(bfs()) 
        while(flow = dfs(S, INF)) 
            res += flow;
    return res;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    S = 1, T = n;
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, (ll)c * K + 1);
    } 

    ll res = dinic();

    cout << res / K << ' ' << res % K << endl;
    for(int i = 0; i < idx; i += 2)
    {
        init();
        ll t = f[i];
        f[i] = 0;
        ll r = dinic();
        if(r == res - t)
        {
            cout << i / 2 + 1 << endl;
            res = r;
        }
        else f[i] = t;
    }
    return 0;
}


活动打卡代码 AcWing 1398. 穿梭谜题

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

int cnt = N, n;
int ans[N], path[N];
string sta, ed;

void dfs(int p, int k)
{
    if(k >= cnt - 1) return ;
    if(sta == ed)
    {
        memcpy(ans, path, k * 4);
        cnt = k;
        return ;
    }
    if(p - 2 >= 0 && sta[p - 2] == 'w' && sta[p - 1] == 'b')
    {
        path[k] = p - 2;
        swap(sta[p - 2], sta[p]);
        dfs(p - 2, k + 1);
        swap(sta[p - 2], sta[p]);
    }
    if(p - 1 >= 0 && sta[p - 1] == 'w')
    {
        path[k] = p - 1;
        swap(sta[p - 1], sta[p]);
        dfs(p - 1, k + 1);
        swap(sta[p - 1], sta[p]);
    }
    if(p + 2 <= 2 * n && sta[p + 2] == 'b' && sta[p + 1] == 'w')
    {
        path[k] = p + 2;
        swap(sta[p + 2], sta[p]);
        dfs(p + 2, k + 1);
        swap(sta[p + 2], sta[p]);
    }
    if(p + 1 <= 2 * n && sta[p + 1] == 'b')
    {
        path[k] = p + 1;
        swap(sta[p + 1], sta[p]);
        dfs(p + 1, k + 1);
        swap(sta[p + 1], sta[p]);
    }
}

int main()
{
    cin >> n;
    sta = string(n, 'w') + " " + string(n, 'b');
    ed = sta;
    reverse(ed.begin(), ed.end());
    dfs(n, 0);
    for(int i = 0; i < cnt; i ++)
    {
        cout << ans[i] + 1;
        if((i + 1) % 20 == 0) cout << endl;
        else cout << ' ';
    }
    return 0;
}


活动打卡代码 AcWing 1397. 字母游戏

#include<bits/stdc++.h>

using namespace std;

const int N = 5100;

char dk[] = "qwertyuiopasdfghjklzxcvbnm";
int dv[] = {
    7, 6, 1, 2, 2, 5, 4, 1, 3, 5,
    2, 1, 4, 6, 5, 5, 7, 6, 3,
    7, 7, 4, 6, 5, 2, 5
};
int v[200], cnt[200], n;

string s, ss, str[N];

int get(string x)
{
    int res = 0;
    for(int i = 0; i < x.size(); i ++)
        res += v[x[i]];
    return res;
}

bool check(string a, string b)
{
    bool f = true;
    for(int i = 0; i < a.size(); i ++)
        cnt[a[i]] --;
    for(int i = 0; i < b.size(); i ++)
        if(-- cnt[b[i]] < 0) f = false;
    for(int i = 0; i < a.size(); i ++)
        cnt[a[i]] ++;
    for(int i = 0; i < b.size(); i ++)
        cnt[b[i]] ++;
    return f;
}

int main()
{
    cin >> s;
    for(int i = 0; i < 26; i ++) v[dk[i]] = dv[i];
    for(int i = 0; i < s.size(); i ++) cnt[s[i]] ++;

    while(cin >> ss, ss != ".")
    {
        bool flag = true;
        for(int i = 0; i < ss.size(); i ++)
            if(-- cnt[ss[i]] < 0) flag = false;
        for(int i = 0; i < ss.size(); i ++)
            cnt[ss[i]] ++;
        if(flag) str[n ++] = ss;
    }
    int res = 0;
    for(int i = 0; i < n; i ++)
    {
        int sc = get(str[i]);
        res = max(res, sc);

        for(int j = i + 1; j < n; j ++)
        {
            if(check(str[i], str[j]))
                res = max(res, sc + get(str[j]));
        }
    }
    cout << res << endl;
    for(int i = 0; i < n; i ++)
        {
            int sc = get(str[i]);
            if(sc == res)
            {
                cout << str[i] << endl;
                continue;
            }

            for(int j = i + 1; j < n; j ++)
            {
                if(check(str[i], str[j]) && res == sc + get(str[j]))
                    cout << str[i] << ' ' << str[j] << endl;
            }
        }
    return 0;
}