头像

0918k




离线:2天前


活动打卡代码 AcWing 1532. 找硬币

0918k
17天前

#include<iostream>
#include<algorithm>


using namespace std;

const int N = 100010;
int n, m;
int w[N];

int main(){

    cin >> n >>m;

    for(int i = 0; i < n; i ++) cin >> w[i];
    sort(w, w + n);

    for(int i = 0, j = n - 1; i < j; i ++){
        while(i < j && w[i] + w[j] > m) j --;
        if(i < j && w[i] + w[j] == m){
            cout << w[i] << " " << w[j] << endl;
            return 0;
        }
    }
    puts("No Solution");
    return 0;
}


活动打卡代码 AcWing 1208. 翻硬币

0918k
17天前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N =310;

string a, b;
void turn(int i){
    if(a[i] == '*') a[i] = 'o';
    else a[i] = '*';
}

int main(){
    cin >> a >> b;

    int res = 0;

    for(int i = 0; i + 1 < a.size(); i ++)
         if(a[i] != b[i]){
             res ++;
             turn(i), turn(i + 1);
         }

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 1098. 城堡问题

0918k
29天前

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

using namespace std;

const int N = 51, M = N * N;

int n, m;
typedef pair<int, int> PII;
PII q[M];
int g[N][N];
bool st[N][N];
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
int bfs(int nx, int ny){

    q[0] = {nx, ny};
    st[nx][ny] = true;
    int hh = 0, tt = 0;
    int area  = 0;
    while(hh <= tt){

        PII t = q[hh ++];
        area ++;
        for(int i = 0; i < 4; i ++){
           int a = t.first + dx[i], b = t.second + dy[i];
           if(a < 0 || a >= n || b < 0 || b >= m) continue;
           if(st[a][b]) continue;
           if(g[t.first][t.second] >> i & 1) continue;

           q[++ tt] = {a, b};
           st[a][b] = true;
        }
    }
    return area;
}

int main(){

    int cnt = 0;
    int area = 0;
    cin >> n >> m;

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

    for(int i = 0; i < n ;i ++)
       for(int j = 0; j < m; j ++){
           if(!st[i][j]){
               area = max(area, bfs(i, j));
               cnt ++;
           }
       }

    cout << cnt << endl;
    cout << area << endl;

    return 0;
}


活动打卡代码 AcWing 1097. 池塘计数

0918k
30天前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 1010, M = N * N;
int n, m;
char g[N][N];
PII q[M];
bool st[N][N];

void bfs(int nx, int ny){
    int hh = 0, tt = 0;
    q[0] = {nx, ny};
    st[nx][ny] = true;

    while(hh <=  tt){
        PII t = q[hh ++];

        for(int i = t.first - 1;  i <= t.first + 1; i ++)
          for(int j = t.second - 1; j <= t.second + 1; j ++){
              if(i == t.first &&  j == t.second) continue;
              if(i < 0 || i >= n || j < 0|| j >= m) continue;
              if(g[i][j] =='.' || st[i][j]) continue;
              q[++ tt] = {i , j};
              st[i][j] = true;
          }
    }
}


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

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

    int cnt = 0;
    for(int i = 0; i < n; i ++)
       for(int j = 0; j < m; j ++)
         if(g[i][j] == 'W' && !st[i][j]){
             bfs(i, j);
             cnt ++;
         }


    cout << cnt << endl;

    return 0;
}



活动打卡代码 AcWing 422. 校门外的树

0918k
1个月前
#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 10010;
int L, n;
bool st[N];

int main(){
    cin >> L >> n;
    for(int i = 0; i <= L; i ++) st[i] = true;

    while(n --){
        int a, b;
        cin >> a >> b;
        for(int i = a; i <= b; i ++) st[i] =false;
    }
    int res = 0;
    for(int i = 0; i <= L; i ++) res += st[i];

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 1227. 分巧克力

0918k
1个月前
#include<iostream>

using namespace std;

const int N = 100010;
typedef long long  LL;
int n, m;
int h[N], w[N];

bool check(int mid){
    LL res = 0;

    for(int i = 0; i <n ;i ++){
        res += (LL) (h[i] / mid) * (w[i] / mid);
        if( res >= m) return  true;
    }
    return false;
}

int main(){

    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> h[i] >> w[i];

    LL l = 1, r = 1e9;
    while(r > l){
        int mid = l + r + 1 >> 1;
        if(check(mid)) l = mid;
        else  r = mid - 1;
    }
    cout << r << endl;
    return 0;
}


活动打卡代码 AcWing 680. 剪绳子

0918k
1个月前
#include<iostream>

using namespace std;

const int N = 1000010;

int n, m;

int w[N];


bool check(double mid){
    int cnt = 0;

    for(int i = 0; i <n ;i ++){
        cnt += w[i] / mid;
    }
    return cnt >= m;
}

int main(){

    cin >> n >> m;

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

    double l, r = 1e9;

    while(r - l > 1e-4){
        double mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    printf("%.2lf", r);

    return 0;
}



活动打卡代码 AcWing 1346. 回文平方

0918k
1个月前
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

char get(int x){
    if(x <= 9) return x + '0';
    return x - 10 + 'A';
}
//改为b进制的数
string base(int n, int b){
    string res;
    //十进制n转换为b进制
    while(n) res += get(n % b), n /= b;
    //将字符串颠倒
    reverse(res.begin(), res.end());
    return res;
}
//判断是否是回文子串
bool check(string s){
    for(int i = 0, j = s.size() -1; i < j; i ++, j --){
        if(s[i] != s[j]) return false;
    }
    return true;
}

int main(){

    int b;
    cin >>b;

    for(int i = 1; i <= 300; i ++){
        string num = base(i * i, b);
        if(check(num)){
            cout << base(i, b) << " " << num << endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 1113. 红与黑

0918k
1个月前
#include<iostream>
#include<cstring>


using namespace std;

const int N =25;
int n, m;
char g[N][N];
bool st[N][N];

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

int dfs(int x, int y){

    int cnt = 1;

    st[x][y] = true;

    for(int i = 0; i < 4; i ++){

        int a = x + dx[i], b = y + dy[i];


        if(a < 0 || a >= n || b < 0 || b >= m) continue;

        if(g[a][b] != '.') continue;

        if(st[a][b]) continue;

        cnt += dfs(a, b);
    }

    return cnt;

}

int main(){

    while(cin >> m >> n ,n || m){

        for(int i = 0; i < n; i ++) cin >> g[i];
        int x, y;
        for(int i = 0; i < n; i ++)
           for(int j = 0; j < m; j ++)
              if(g[i][j] == '@')
                {
                    x = i;
                    y = j;
                }


       memset(st, 0, sizeof st);

       cout << dfs(x, y) << endl;
    }

    return 0;

}


活动打卡代码 AcWing 756. 蛇形矩阵

0918k
1个月前
#include<iostream>

using namespace std;

const int N = 110;
int g[N][N];
int main(){

    int n,m;
    cin >> n >> m;

    int x = 0, y = 0;
    int cnt = 0;
    g[x][y] = ++ cnt;
    while(cnt < n * m){
        //向右走
        while(y < m - 1 && !g[x][y + 1]){
            y ++;
            g[x][y] = ++ cnt;
        }
        //向下
        while(x < n - 1 && !g[x + 1][y]){
            x ++;
            g[x][y] = ++ cnt;
        }
        //向左
        while(y > 0 && !g[x][y -1]){
            y --;
            g[x][y] = ++cnt;
        }
        //向上
        while(x > 0 && !g[x-1][y]){
            x --;
            g[x][y] = ++ cnt;
        }
    }
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < m;j  ++){
            cout << g[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}