头像

dys

qq:1115410174 西北大学




离线:19小时前



dys
3天前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10,M = 2e5 + 10,INF = 1e9;
int h[N],e[M],ne[M],f[M],idx;
int n,m,S,T;
int q[N];
int cur[N];
int d[N];
void add(int a,int b,int c){
    e[idx] = b,ne[idx] = h[a],f[idx] = c,h[a] = idx++;
    e[idx] = a,ne[idx] = h[b],f[idx] = 0,h[b] = idx++;
}
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(f[i],limit-flow));
            if(!t) d[ver] = -1;
            f[i] -= t,f[i^1] += t,flow += t;
        }
    }
    return flow;
}
int dinic(){
    int r = 0,flow;
    while(bfs()) while(flow = find(S,INF)) r+=flow;
    return r;
}
int main(){
    memset(h,-1,sizeof h);
    cin >> n >> m >> S >> T;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
    }
    cout << dinic() << endl;
    return 0;
}


活动打卡代码 AcWing 3068. 扫描线

dys
16天前
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e3 + 10;
int n;
pii l[N],r[N],q[N];
vector<int>xs;
ll range_area(int a,int b){
    int cnt = 0;
    for(int i=0;i<n;i++){
        if(l[i].x<=a && r[i].x >= b){
            q[cnt++] = {l[i].y,r[i].y};
        }
    }
    if(!cnt) return 0;
    sort(q,q+cnt);
    ll res = 0;
    int st = q[0].x,ed = q[0].y;
    for(int i=1;i<cnt;i++){
        if(q[i].x <= ed) ed = max(q[i].y,ed);
        else{
            res += ed - st;
            st = q[i].x,ed = q[i].y;
        }
    }
    res += ed - st;
    return res * (b - a);
}
int main(){
    cin >> n;
    for(int i=0;i<n;i++){
        scanf("%d%d%d%d",&l[i].x,&l[i].y,&r[i].x,&r[i].y);
        xs.push_back(l[i].x);
        xs.push_back(r[i].x);
    }
    sort(xs.begin(),xs.end());
    ll res = 0;
    for(int i=0;i<xs.size() - 1;i++){
        if(xs[i] != xs[i + 1]){
            res += range_area(xs[i],xs[i+1]);
        }
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 499. 聪明的质监员

dys
17天前


活动打卡代码 AcWing 122. 糖果传递

dys
17天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 1000010;

int n;
LL s[N], c[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }

    LL b = s[n] / n;
    int k = 0;
    for (int i = 1; i < n; i ++ ) c[k ++ ] = i * b - s[i];
    c[k ++ ] = 0;

    nth_element(c, c + k / 2, c + k);
    LL res = 0;
    for (int i = 0; i < k; i ++ )
        res += abs(c[i] - c[k / 2]);

    printf("%lld\n", res);
    return 0;
}



活动打卡代码 AcWing 1230. K倍区间

dys
17天前
include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 100010;

int n, k;
LL s[N];
int cnt[N];

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &s[i]);
        s[i] += s[i - 1];
    }

    LL res = 0;
    cnt[0] ++ ;
    for (int i = 1; i <= n; i ++ )
    {
        res += cnt[s[i] % k];
        cnt[s[i] % k] ++ ;
    }

    printf("%lld\n", res);
    return 0;
}



活动打卡代码 AcWing 703. 数独检查

dys
18天前


活动打卡代码 AcWing 417. 不高兴的津津

dys
18天前
#include <iostream>
using namespace std;


int main(){
    //w代表具体的天,t代表最大学习时长
    int w = 0 , t = 0;

    for (int i = 1 ; i <= 7 ; i ++){
        int a ,b ;
        cin >> a >> b;
        if (a + b > 8 && a + b > t){
            t = a + b;
            w = i;
        }
    }

    cout << w;
    return 0;



活动打卡代码 AcWing 1262. 鱼塘钓鱼

dys
18天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int a[N], d[N], l[N], spend[N];

int get(int k)
{
    return max(0, a[k] - d[k] * spend[k]);
}

int work(int n, int T)
{
    int res = 0;
    memset(spend, 0, sizeof spend);
    for (int i = 0; i < T; i ++ )
    {
        int t = 1;
        for (int j = 1; j <= n; j ++ )
            if (get(j) > get(t))
                t = j;
        res += get(t);
        spend[t] ++ ;
    }
    return res;
}

int main()
{
    int n, T;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i <= n; i ++ ) cin >> d[i];
    for (int i = 2; i <= n; i ++ )
    {
        cin >> l[i];
        l[i] += l[i - 1];
    }
    cin >> T;

    int res = 0;
    for (int i = 1; i <= n; i ++ )
        res = max(res, work(i, T - l[i]));

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 257. 关押罪犯

dys
19天前
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20010, M = 100100;

int n,m;
int p[N*2];

struct node{
    int a,b,w;
    bool operator<(const node& x){
        return w>x.w;
    }
}e[M];

int find(int x){
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    scanf("%d%d",&n,&m);

    for(int i = 1; i<=n*2; i++) p[i] = i;

    for(int i = 0; i<m; i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        e[i] = {a,b,c};
    }
    sort(e,e+m);

    for(int i = 0; i<m; i++){
        int x = find(e[i].a),y = find(e[i].b);   //a和b在监狱x和y
        int opposite_x = find(e[i].a+n), opposite_y = find(e[i].b+n); //a和b的敌人所在的监狱
        if(x==y){   //两名罪犯关在同一个监狱内,冲突不可避免,直接输出答案
            printf("%d\n",e[i].w);
            return 0;
        }
        p[x] = opposite_y;  //a放在b的敌人的监狱中
        p[y] = opposite_x;  //b放在a的敌人的监狱中
    }
    printf("0\n");
    return 0;
}



dys
22天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

#define x first
#define y second

using namespace std;

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

int n, m;
char g[N][N];
int dist[N][N];

int bfs(PII start)
{
    queue<PII> q;
    q.push(start);
    memset(dist, -1, sizeof dist);
    dist[start.x][start.y] = 0;

    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        for (int i = 0; i < 4; i ++ )
        {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] != '#' && dist[x][y] == -1)
            {
                dist[x][y] = dist[t.x][t.y] + 1;
                if (g[x][y] == 'E')
                    return dist[x][y];
                q.push({x, y});
            }
        }
    }
    return -1;
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        cin >> n >> m;

        PII start;
        for (int i = 0; i < n; i ++ )
        {
            cin >> g[i];
            for (int j = 0; j < m; j ++ )
                if (g[i][j] == 'S') start = {i, j};
        }

        int res = bfs(start);
        if (res == -1) puts("oop!");
        else cout << res << endl;
    }

    return 0;
}