头像

笙笙笙笙




离线:16小时前


最近来访(56)
用户头像
kaiwandao
用户头像
-浪漫主义狗-
用户头像
觅星
用户头像
麓笙_bool
用户头像
无名小子
用户头像
_memory_
用户头像
江南诗诗
用户头像
no_one
用户头像
北海没有WA
用户头像
magpieeeee
用户头像
洛琪xii
用户头像
菜狗一枚
用户头像
不拿牌牌不改名
用户头像
Fatin
用户头像
Rainbow_jzy
用户头像
一万小时定律
用户头像
XY.
用户头像
iteg
用户头像
ryanryanryan
用户头像
mengM

活动打卡代码 AcWing 4218. 翻转

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

using namespace std;
const int N = 16;
int bg[N][N];
int g[N][N];
int s[N][N];
int ans[N][N];
int n,m;

void turn(int x, int y){
    int dx[5] = {1, 0, -1, 0, 0};
    int dy[5] = {0, 1, 0, -1, 0};
    for (int i = 0; i < 5; i ++){
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= m) continue;
        g[a][b] ^= 1;
    }
    s[x][y] = 1;
}

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

    int res = 0x3f3f3f3f;
    for(int k = 0 ; k < 1 << m ; k++){
        int cnt = 0;
        memcpy(g,bg,sizeof bg);
        memset(s,0,sizeof s);
        for(int i = 0 ; i < m ; i++)
            if(k >> i & 1){
                turn(0,i);
                cnt++;
            }
        for(int i = 0 ; i < n - 1 ; i ++)
            for(int j = 0 ; j < m ; j++){
                if(g[i][j] == 1){
                    turn(i + 1,j);
                    cnt++;
                }
            }

        bool success = true;
        for(int i = 0 ; i < m ; i++) if(g[n - 1][i] == 1) success = false;
        if(success && res > cnt){
            res = cnt;
            memcpy(ans,s,sizeof s);
        }
    }
    if(res == 0x3f3f3f3f) puts("IMPOSSIBLE");
    else {
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < m ; j++)
                cout << ans[i][j] <<' ';

            cout << endl;
        }


    }
    return 0;
}



活动打卡代码 AcWing 1100. 抓住那头牛

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

using namespace std;
const int N = 100010;

int n,m;
int d[N];

void bfs(){
    queue<int> q;
    q.push(n);
    while(q.size()){
        int t = q.front();
        q.pop();
        if(t == m) return;

        for(int i = 1 ; i <= 3 ; i++){
            int a = 0;
            if(i == 1) a = t + 1;
            else if(i == 2) a = t - 1;
            else if(i == 3) a = t * 2;

            if(a < 0 || a > N || d[a]) continue;
            d[a] = d[t] + 1;
            q.push(a);
        }
    }
}

int main()
{
    cin >> n >> m;
    bfs();
    cout << d[m] << endl;
}


活动打卡代码 AcWing 1096. 地牢大师

#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 = 10010;
int n,m,k;
char s[N][110]; // 存储字符
PII start;
PII en;
int d[N][110]; //dist距离

void bfs(){
    queue<PII> q;
    q.push(start);
    //移动层 在数据存储方面可以看成 +n 行 和 -n 行
    int dx[6]={-1,0,1,0,n,-n}; //偏移量数组 
    int dy[6]={0,1,0,-1,0,0}; 

    while(q.size()){
        auto t = q.front();
        q.pop();
        //搜索到终点直接退出
        if(s[t.x][t.y] == 'E') return;

        for(int i = 0 ; i <= 5 ; i++){
            if(i == 0 && t.x % n == 1) continue; //如果当前点在某一层的第一行的话 移动到0行是不合法的
            if(i == 2 && t.x % n == 0) continue; //如果当前点在某一层的第n行的话 移动到 n+行是不合法的
            int a = t.x + dx[i];
            int b = t.y + dy[i];

            if(a <= 0 || a > n * k || b <= 0 || b > m || s[a][b] == '#' || d[a][b]) continue;
            d[a][b] = d[t.x][t.y] + 1;

            q.push({a,b});
        }
    }
}

int main()
{
    while(cin >> k >> n >> m && n && k && m){

        for(int i = 0 ; i < k ; i++)
            for(int j = 1 ; j <= n ; j++)
                for(int c = 1 ; c <= m ; c++){
                    cin >> s[i * n + j][c];
                    d[i * n + j][c] = 0; // 初始化数组
                    //记录起点和终点
                    if(s[i * n + j][c] == 'S')  start = {i * n + j,c};
                    if(s[i * n + j][c] == 'E') en = {i * n + j,c};
                }

        bfs();
        if(d[en.x][en.y]) printf("Escaped in %d minute(s).\n",d[en.x][en.y]);
        else puts("Trapped!");

    }
    return 0;
}



题目描述

一开始以为是2维的题 就写的2维的偏移 wa了好久 wuuwuw


C++ 代码

#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 = 10010;
int n,m,k;
char s[N][110]; // 存储字符
PII start;
PII en;
int d[N][110]; //dist距离

void bfs(){
    queue<PII> q;
    q.push(start);
    //移动层 在数据存储方面可以看成 +n 行 和 -n 行
    int dx[6]={-1,0,1,0,n,-n}; //偏移量数组 
    int dy[6]={0,1,0,-1,0,0}; 

    while(q.size()){
        auto t = q.front();
        q.pop();
        //搜索到终点直接退出
        if(s[t.x][t.y] == 'E') return;

        for(int i = 0 ; i <= 5 ; i++){
            if(i == 0 && t.x % n == 1) continue; //如果当前点在某一层的第一行的话 移动到0行是不合法的
            if(i == 2 && t.x % n == 0) continue; //如果当前点在某一层的第n行的话 移动到 n+行是不合法的
            int a = t.x + dx[i];
            int b = t.y + dy[i];

            if(a <= 0 || a > n * k || b <= 0 || b > m || s[a][b] == '#' || d[a][b]) continue;
            d[a][b] = d[t.x][t.y] + 1;

            q.push({a,b});
        }
    }
}

int main()
{
    while(cin >> k >> n >> m && n && k && m){

        for(int i = 0 ; i < k ; i++)
            for(int j = 1 ; j <= n ; j++)
                for(int c = 1 ; c <= m ; c++){
                    cin >> s[i * n + j][c];
                    d[i * n + j][c] = 0; // 初始化数组
                    //记录起点和终点
                    if(s[i * n + j][c] == 'S')  start = {i * n + j,c};
                    if(s[i * n + j][c] == 'E') en = {i * n + j,c};
                }

        bfs();
        if(d[en.x][en.y]) printf("Escaped in %d minute(s).\n",d[en.x][en.y]);
        else puts("Trapped!");

    }
    return 0;
}



活动打卡代码 AcWing 1114. 棋盘问题

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

using namespace std;
const int N = 10;
int n,m;
char s[N][N];
bool line[N];
int res;

void dfs(int x ,int k){
    if(k == m){
        res++;
        return;
    }

    if(x == n + 1) return;

    for(int i = 1 ;  i <= n ; i++)
        if(s[x][i] == '#' && !line[i]){
            line[i] = true;
            dfs(x + 1,k + 1);
            line[i] = false;
        }


    dfs(x + 1,k);
}

int main()
{
    while(cin >> n >> m , n != -1 && m != -1){
        res = 0;
        memset(line,false,sizeof line);
        for(int i = 1 ; i <= n ; i++)
            for(int j = 1 ; j <= n ; j++)
                cin >> s[i][j];

        dfs(1,0);
        cout << res << endl;
    }
}


活动打卡代码 AcWing 275. 传纸条

#include <bits/stdc++.h>

using namespace std;

const int N = 55;
int n, m;
int f[N][N], w[N][N];

int main() {
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%d", &w[i][j]);

    for (int k = 2; k <= m + n; ++k) {
        for (int x1 = min(m, k - 1); x1 >= max(1, k - n); --x1) {
            for (int x2 = x1; x2 >= max(1, k - n); --x2) {
                int y1 = k - x1, y2 = k - x2;
                f[x1][x2] = w[x1][y1] + (x1 != x2) * w[x2][y2] + max(
                    {f[x1 - 1][x2], f[x1][x2 - 1], f[x1 - 1][x2 - 1], f[x1][x2]}
                );
            }
        }
    }
    printf("%d\n", f[m][m]);
    return 0;
}





活动打卡代码 AcWing 4605. 最大周长

笙笙笙笙
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 3000010,INF = 1e9;
int x[N],y[N];
int n;
int main(){
    cin >> n;
    int u = -INF , d = INF , l = INF , r = -INF;
    for(int i = 0 ; i < n ; i++){
        cin >> x[i] >> y[i];
        u = max(u,y[i]) , d = min(d,y[i]);
        l = min(l,x[i]) , r = max(r,x[i]);
    }

    int res = 0;

    for(int i = 0 ; i < n ; i++)
        res = max(res,max(u - y[i],y[i] - d) + max(x[i] - l , r - x[i]));
    cout << res * 2 << ' ';

    for(int i = 4 ; i <= n ; i++)
        cout << (u - d + r - l) * 2 << ' ';


}


活动打卡代码 AcWing 1074. 二叉苹果树

笙笙笙笙
1个月前

^^^^

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 110, M = N * 2;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int f[N][N];

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

void dfs(int u, int father){
for(int i = h[u] ; ~i ; i = ne[i])
{
if (e[i] == father) continue;
dfs(e[i], u);
for(int j = m ; j >= 0 ; j– )
for(int k = 0 ; k + 1 <= j ; k++)
f[u][j] = max(f[u][j], f[u][j - k - 1] + f[e[i]][k] + w[i]);
}
}

int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 1 ; i <= n - 1 ; i ++){
int a , b , c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}

dfs(1,-1);

cout << f[1][m] << endl;
return 0;

}

```



活动打卡代码 AcWing 1075. 数字转换

笙笙笙笙
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010 , M = 2000010;
int n;
int h[N], e[M], ne[M], idx;

int sum[N];
bool st[N];
int ans;
void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}


int dfs(int u){
    st[u] = true;
    int dist = 0;
    int d1 = 0;
    int d2 = 0;
    for(int i = h[u] ; ~i ; i = ne[i]){
        int j = e[i];
        if(!st[j]){
            int d = dfs(j);
            dist = max(dist, d);
            if(d >= d1) d2 = d1 , d1 = d;
            else if(d > d2 ) d2 = d;
        }
    }
    ans = max(ans, d1 + d2);

    return dist + 1;
}

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i ++)
        for(int j = 2 ; j <= n / i ; j ++)
            sum[i * j] += i;
    memset(h, -1, sizeof h);
    for(int i = 2 ; i <= n ; i++)
        if(sum[i] < i)
            add(sum[i],i);
    for (int i = 1; i <= n; i ++ )
        if (!st[i])
        dfs(i);

    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 1073. 树的中心

笙笙笙笙
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010 , M =  2000010 , INF = 0x3f3f3f3f;
int h[N], e[M], w[M], ne[M], idx;
int d1[N],d2[N],p1[N],up[N];
int n;

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

int dfs_d(int u , int f){

    d1[u] = d2[u] = -INF;
    for(int i = h[u] ; ~i ; i = ne[i]){
        int j = e[i];
        if(j == f ) continue;
        int d = dfs_d(j,u) + w[i];
        if(d >= d1[u]){
            d2[u] = d1[u];
            d1[u] = d;
            p1[u] = j;
        }else if(d > d2[u])
            d2[u] = d;


    }

    if(d1[u] == -INF) d1[u] = d2[u] = 0;
    return d1[u];
}

void dfs_up(int u ,int f){
    for(int i = h[u] ; ~i ; i = ne[i]){
        int j = e[i];
        if(j == f) continue;

        if(p1[u] == j) up[j] = max(up[u], d2[u]) + w[i];
        else up[j] = max(up[u], d1[u]) + w[i];

        dfs_up(j, u);
    }
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n - 1 ; i ++) {
        int a , b ,c ;
        cin >> a >> b >> c ;
        add(a, b, c);
        add(b , a ,c);

    }
    dfs_d(1,-1);
    dfs_up(1,-1);

    int res = INF;
    for (int i = 1; i <= n; i ++ ) res = min(res, max(d1[i], up[i]));

    cout << res << endl;
}