头像

incra

$$\href{https://www.acwing.com/blog/content/22674/}{\Huge\color{blue}{个人主页}}$$$$\Large{封禁家族六年级蒟蒻}$$




离线:9小时前


最近来访(2261)
用户头像
Pathfinder
用户头像
Eden_93
用户头像
workhard_
用户头像
小杰儿_8
用户头像
种花家的兔兔
用户头像
jimmy2021
用户头像
垫底抽風
用户头像
QWQ686
用户头像
Abel51
用户头像
xyh2
用户头像
Finn2009
用户头像
mr_lonely
用户头像
宇宙有边
用户头像
梦若浮生
用户头像
yxc的小迷妹
用户头像
yxc的小迷妹1
用户头像
Reminiscence
用户头像
12345syk
用户头像
墨离
用户头像
闻天语

活动打卡代码 AcWing 1010. 拦截导弹

incra
3天前
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n = 0;
int a[N],f[N];
int main () {
    while (cin >> a[n + 1]) n++;
    int ans = 0;
    for (int i = 1;i <= n;i++) {
        f[i] = 1;
        for (int j = 1;j < i;j++) {
            if (a[j] >= a[i]) f[i] = max (f[i],f[j]+1);
        }
        ans = max (ans,f[i]);
    }
    cout << ans << endl;
    ans = 0;
    for (int i = 1;i <= n;i++) {
        f[i] = 1;
        for (int j = 1;j < i;j++) {
            if (a[j] < a[i]) f[i] = max (f[i],f[j]+1);
        }
        ans = max (ans,f[i]);
    }
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 4226. 非常可乐

incra
3天前
#include <iostream>
using namespace std;
int a,b,c;
int gcd (int x,int y) {
    return y == 0 ? x : gcd (y,x%y);
}
int main () {
    while (cin >> a >> b >> c,a) {
        a /= gcd (b,c);
        if (a&1) cout << "NO" << endl;
        else cout << a-1 << endl;
    }
    return 0;
}


活动打卡代码 AcWing 4225. 石油储备

incra
3天前
#include <iostream>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair <int,int> PII;
const int N = 110;
int n,m,ans;
char g[N][N];
int dx[] = {0,0,1,-1,1,1,-1,-1},dy[] = {1,-1,0,0,1,-1,1,-1};
void bfs (int sx,int sy) {
    queue <PII> q;
    q.push ({sx,sy});
    while (!q.empty ()) {
        PII t = q.front ();
        q.pop ();
        for (int i = 0;i < 8;i++) {
            int x = t.x+dx[i],y = t.y+dy[i];
            if (x < 1 || x > n || y < 1 || y > m || g[x][y] == '*') continue;
            g[x][y] = '*';
            q.push ({x,y});
        }
    }
}
int main () {
    while (cin >> n >> m,n) {
        ans = 0;
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= m;j++) {
                cin >> g[i][j];
            }
        }
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= m;j++) {
                if (g[i][j] == '@') {
                    bfs (i,j);
                    ans++;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}


活动打卡代码 AcWing 4224. 起火迷宫

incra
3天前
#include <iostream>
#include <cstring>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair <int,int> PII;
const int N = 1010;
int t,n,m,sx,sy;
char g[N][N];
int d[N][N];
queue <PII> fire,q;
int dx[] = {0,0,1,-1},dy[] = {1,-1,0,0};
void init () {
    while (!fire.empty ()) fire.pop ();
    while (!q.empty ()) q.pop ();
    memset (d,-1,sizeof (d));
}
void Fire () {
    int k = fire.size ();
    while (k--) {
        PII t = fire.front ();
        fire.pop ();
        for (int i = 0;i < 4;i++) {
            int x = t.x+dx[i],y = t.y+dy[i];
            if (x < 1 || x > n || y < 1 || y > m || d[x][y] != -1 || g[x][y] == '#' || d[x][y] != -1) continue;
            d[x][y] = -2;
            fire.push ({x,y});
        }
    }
}
int bfs () {
    while (!q.empty ()) {
        int s = q.size ();
        Fire ();
        while (s--) {
            PII t = q.front ();
            q.pop ();
            if (t.x == 1 || t.x == n || t.y == 1 || t.y == m) return d[t.x][t.y]+1;
            for (int i = 0;i < 4;i++) {
                int x = t.x+dx[i],y = t.y+dy[i];
                if (x < 1 || x > n || y < 1 || y > m || d[x][y] != -1 || g[x][y] == '#') continue;
                d[x][y] = d[t.x][t.y]+1;
                q.push ({x,y});
            }
        }
    }
    return -1;
}
int main () {
    cin >> t;
    while (t--) {
        cin >> n >> m;
        init ();
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= m;j++) {
                cin >> g[i][j];
                if (g[i][j] == 'J') {
                    q.push ({i,j});
                    d[i][j] = 0;
                }
                else if (g[i][j] == 'F') {
                    fire.push ({i,j});
                    d[i][j] = -2;
                }
            }
        }
        int ans = bfs ();
        if (ans == -1) cout << "IMPOSSIBLE" << endl;
        else cout <<ans << endl;
    }
    return 0;
}


活动打卡代码 AcWing 4222. 罐子

incra
3天前
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 110;
string d[] = {"FILL(1)","FILL(2)","DROP(1)","DROP(2)","POUR(1,2)","POUR(2,1)"};
struct pot {
    int a,b;
    vector <string> ans;
};
bool st[N][N];
int x,y,c;
void bfs () {
    queue <pot> q;
    vector <string> a;
    q.push ({0,0,a});
    while (!q.empty ()) {
        pot t = q.front ();
        q.pop ();
        vector <string> ans = t.ans;
        if (t.a == c || t.b == c) {
            cout << ans.size () << endl;
            for (int i = 0;i < ans.size ();i++) cout << ans[i] << endl;
            return ;
        }
        for (int i = 0;i < 6;i++) {
            int a = t.a,b = t.b;
            switch (i) {
                case 0 : a = x;break;
                case 1 : b = y;break;
                case 2 : a = 0;break;
                case 3 : b = 0;break;
                case 4 :
                    a = max (t.a+t.b-y,0);
                    b = min (y,t.a+t.b);
                    break;
                case 5 :
                    a = min (x,t.a+t.b);
                    b = max (t.a+t.b-x,0);
                    break;
            }
            if (st[a][b]) continue;
            ans.push_back (d[i]);
            st[a][b] = true;
            q.push ({a,b,ans});
            ans.pop_back ();
        }
    }
    cout << "impossible" << endl;
}
int main () {
    cin >> x >> y >> c;
    bfs ();
    return 0;
}


活动打卡代码 AcWing 4220. 质数路径

incra
3天前
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair <int,int> PII;
const int N = 10010;
int n,st,ed;
int vis[N];
bool prime (int x) {
    if (x <= 1) return false;
    for (int i = 2;i <= x/i;i++) {
        if (x%i == 0) return false;
    }
    return true;
}
int bfs () {
    queue <PII> q;
    q.push ({st,0});
    while (!q.empty ()) {
        PII t = q.front ();
        q.pop ();
        if (t.first == ed) return t.second;
        int x = t.first,step = t.second;
        for (int i = 1;i <= 9;i += 2) {
            int s = x/10*10+i;
            if (s != x && !vis[s] && prime (s)) {
                vis[s] = true;
                q.push ({s,step+1});
            }
        }
        for (int i = 0;i <= 9;i++) {
            int s = x/100*100+i*10+x%10;
            if (s != x && !vis[s] && prime (s)) {
                vis[s] = true;
                q.push ({s,step+1});
            }
        }
        for (int i = 0;i <= 9;i++) {
            int s = x/1000*1000+i*100+x%100;
            if (s != x && !vis[s] && prime (s)) {
                vis[s] = true;
                q.push ({s,step+1});
            }
        }
        for (int i = 1;i <= 9;i++) {
            int s = x%1000+i*1000;
            if (s != x && !vis[s] && prime (s)) {
                vis[s] = true;
                q.push ({s,step+1});
            }
        }
    }
    return -1;
}
int main () {
    cin >> n;
    while (n--) {
        memset (vis,false,sizeof (vis));
        cin >> st >> ed;
        int ans = bfs ();
        if (ans == -1) cout << "impossible" << endl;
        else cout << ans << endl;
    }
    return 0;
}


活动打卡代码 AcWing 4219. 找倍数

incra
3天前
#include <iostream>
using namespace std;
long long n;
bool flag;
void dfs (int c,long long k) {
    if (flag || c >= 19) return ;
    if (k%n == 0) {
        cout << k << endl;
        flag = true;
        return ;
    }
    dfs (c+1,k*10);
    dfs (c+1,k*10+1);
}
int main () {
    while (cin >> n && n) {
        flag = false;
        dfs (0,1);
    }
    return 0;
}


活动打卡代码 AcWing 4218. 翻转

incra
3天前
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20;
int n,m;
bool hasAns = false;
int g[N][N],ans[N][N],backup[N][N];
int dx[] = {0,0,0,-1,1};
int dy[] = {0,1,-1,0,0};
void turn (int x,int y) {
    for (int i = 0;i < 5;i++) {
        int a = x+dx[i];
        int b = y+dy[i];
        if (a >= 1 && a <= n && b >= 1 && b <= m) g[a][b] ^= 1;
    }
}
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> g[i][j];
            backup[i][j] = g[i][j];
        }
    }
    for (int k = 0;k < 1 << m;k++) {
        memset (ans,0,sizeof (ans));
        for (int i = 1;i <= m;i++) {
            if (k >> (i-1) & 1) turn (1,i),ans[1][i] = 1;
        }
        for (int i = 1;i <= n-1;i++) {
            for (int j = 1;j <= m;j++) {
                if (g[i][j]) turn (i+1,j),ans[i+1][j] = 1;
            }
        }
        bool flag = true;
        for (int i = 1;i <= m;i++) {
            if (g[n][i]) {
                flag = false;
                break;
            }
        }
        memcpy (g,backup,sizeof (g));
        if (flag) {
            hasAns = true;
            break;
        }
    }
    if (!hasAns) {
        cout << "IMPOSSIBLE" << endl;
        return 0;
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (j > 1) cout << ' ';
            cout << ans[i][j];
        }
        cout << endl;
    }
    return 0;
}


活动打卡代码 AcWing 2568. 树链剖分

incra
4天前
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1000010,M = 2 * N;
int n,m;
int tmp_w[N];   //原来的点权
int h[N],e[M],ne[M],idx;    //存图
int id[N],w[N],timestamp;   //结点的编号,现在的点权(图中的点权),时间戳
int fa[N],s[N]; //父亲,以当前点位根的子树中有几个节点
int dep[N],son[N],top[N];   //深度,重儿子,重链的最高顶点
struct segment_tree_node {
    int l,r;
    LL sum,add;
}tr[4 * N];
void add (int a,int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void dfs1 (int u,int father,int depth) {    //计算出fa,dep,s,son
    fa[u] = father,dep[u] = depth,s[u] = 1;
    for (int i = h[u];~i;i = ne[i]) {
        int j = e[i];
        if (j == father) continue;
        dfs1 (j,u,depth + 1);
        s[u] += s[j];
        if (s[son[u]] < s[j]) son[u] = j;
    }
}
void dfs2 (int u,int top_node) {    //计算出id,w,top
    id[u] = ++timestamp,w[id[u]] = tmp_w[u],top[u] = top_node;
    if (!son[u]) return ;
    dfs2 (son[u],top_node);
    for (int i = h[u];~i;i = ne[i]) {
        int j = e[i];
        if (j == fa[u] || j == son[u]) continue;
        dfs2 (j,j);
    }
}
void push_up (int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void push_down (int u) {
    auto &root = tr[u],&left = tr[u << 1],&right = tr[u << 1 | 1];
    if (root.add) {
        left.add += root.add,left.sum += root.add * (left.r - left.l + 1);
        right.add += root.add,right.sum += root.add * (right.r - right.l + 1);
        root.add = 0;
    }
}
void build_segment_tree (int u,int l,int r) {
    if (l == r) {
        tr[u] = {l,r,w[l],0};
        return ;
    }
    tr[u] = {l,r};  //千万不要漏掉,否则死得很惨
    int mid = l + r >> 1;
    build_segment_tree (u << 1,l,mid),build_segment_tree (u << 1 | 1,mid + 1,r);
    push_up (u);
}
void modify (int u,int l,int r,int d) {
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].sum += (LL)d * (tr[u].r - tr[u].l + 1);
        tr[u].add += d;
        return ;
    }
    push_down (u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modify (u << 1,l,r,d);
    if (r >= mid + 1) modify (u << 1 | 1,l,r,d);
    push_up (u);
}
LL query (int u,int l,int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    push_down (u);
    int mid = tr[u].l + tr[u].r >> 1;
    LL ans = 0;
    if (l <= mid) ans += query (u << 1,l,r);
    if (r >= mid + 1) ans += query (u << 1 | 1,l,r);
    return ans;
}
void modify_path (int u,int v,int k) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap (u,v);  //u的深度大于v
        modify (1,id[top[u]],id[u],k);  //顺序优先重链,所以直接修改
        u = fa[top[u]]; //往上跳
    }
    if (dep[u] > dep[v]) swap (u,v);    //u的深度小于v
    modify (1,id[u],id[v],k);
}
void modify_subtree (int u,int k) {
    modify (1,id[u],id[u] + s[u] - 1,k);  //一个子树里的所有id是连续的
}
LL query_path (int u,int v) {
    LL ans = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap (u,v);  //u的深度大于v
        ans += query (1,id[top[u]],id[u]);  //顺序优先重链,所以直接修改
        u = fa[top[u]]; //往上跳
    }
    if (dep[u] > dep[v]) swap (u,v);    //u的深度小于v
    ans += query (1,id[u],id[v]);
    return ans;
}
LL query_subtree (int u) {
    return query (1,id[u],id[u] + s[u] - 1);  //一个子树里的所有id是连续的
}
int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> tmp_w[i];
    memset (h,-1,sizeof (h));
    for (int i = 1;i <= n - 1;i++) {
        int a,b;
        cin >> a >> b;
        add (a,b),add (b,a);
    }
    dfs1 (1,-1,1),dfs2 (1,1);
    build_segment_tree (1,1,n);
    cin >> m;
    while (m--) {
        int op,a;
        cin >> op >> a;
        if (op == 1) {
            int b,k;
            cin >> b >> k;
            modify_path (a,b,k);    //包成函数,方便调试(注释一行即就能不运行了)
        }
        else if (op == 2) {
            int k;
            cin >> k;
            modify_subtree (a,k);
        }
        else if (op == 3) {
            int b;
            cin >> b;
            cout << query_path (a,b) << endl;
        }
        else cout << query_subtree (a) << endl;
    }
    return 0;
}


活动打卡代码 AcWing 4727. 摆放棋子

incra
6天前
#include <iostream>
using namespace std;
const int N = 110,MOD = 1e8;
int n1,n2,k1,k2;
int f[N][N][2];
int main () {
    cin >> n1 >> n2 >> k1 >> k2;
    f[n1][n2][0] = f[n1][n2][1] = 1;
    for (int i = n1;i >= 0;i--) {
        for (int j = n2;j >= 0;j--) {
            for (int k = 1;k <= k1;k++) {
                if (i - k >= 0) f[i - k][j][0] = (f[i - k][j][0] + f[i][j][1]) % MOD;
            }
            for (int k = 1;k <= k2;k++) {
                if (j - k >= 0) f[i][j - k][1] = (f[i][j - k][1] + f[i][j][0]) % MOD;
            }
        }
    }
    cout << (f[0][0][0] + f[0][0][1]) % MOD << endl;
    return 0;
}