头像

Value




离线:8小时前


活动打卡代码 AcWing 3194. 最大的矩形

Value
1天前
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1E3 + 10;
int h[N], dp[N][N];
int main(){
    int n;  cin >> n;
    for(int i = 0; i < n; i ++ )    cin >> h[i];
    memset(dp, 0x3f3f3f, sizeof dp);
    for(int i = 0; i < n; i ++ ){
        for(int j = i; j < n; j ++ ){
            if(j == i)  dp[i][j] = h[i];
            else    dp[i][j] = min(dp[i][j - 1], h[j]);
        }
    }
    int res = 0;
    for(int i = 0; i < n; i ++ ){
        for(int j = i; j < n; j ++ ){
            res = max(dp[i][j] * (j - i + 1), res);
        }
    }
    cout << res << endl;
    return 0;
}



Value
1天前

暴力三循环

#include <iostream>
using namespace std;
const int N = 1E3 + 10;
int h[N];
int main(){
    int n;  cin >> n;
    int res = 0;
    for(int i = 0; i < n; i ++ )    cin >> h[i];
    for(int i = 0; i < n; i ++ ){
        for(int j = i + 1; j < n; j ++ ){
            int ans = 0x3f3f3f;
            for(int k = i; k <= j; k ++ ){
                ans = min(h[k], ans);
            }
            res = max(res, (j - i + 1) * ans);
        }
    }
    cout << res << endl;
    return 0;
}

dp优化

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1E3 + 10;
int h[N], dp[N][N];
int main(){
    int n;  cin >> n;
    for(int i = 0; i < n; i ++ )    cin >> h[i];
    memset(dp, 0x3f3f3f, sizeof dp);
    for(int i = 0; i < n; i ++ ){
        for(int j = i; j < n; j ++ ){
            if(j == i)  dp[i][j] = h[i];
            else    dp[i][j] = min(dp[i][j - 1], h[j]);
        }
    }
    int res = 0;
    for(int i = 0; i < n; i ++ ){
        for(int j = i; j < n; j ++ ){
            res = max(dp[i][j] * (j - i + 1), res);
        }
    }
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 3193. ISBN号码

Value
1天前
#include <iostream>
#include <map>
using namespace std;
map<int, char> mp;
void init(){
    for(int i = 0; i < 9; i ++ )    mp[i] = '0' + i;
    mp[10] = 'X';
}
int main(){
    init();
    string s;   cin >> s;
    int sum = 0, k = 1;
    for(int i = 0; i < s.size() - 1; i ++ ){
        if(s[i] == '-') continue;
        sum += (s[i] - '0') * (k ++ ); 
    }
    sum %= 11;
    if(mp[sum] != s[s.size() - 1]){
         s[s.size() - 1] = mp[sum];
         cout << s << endl;
    }else   cout << "Right" << endl;
    return 0;
}



Value
1天前
#include <iostream>
#include <map>
using namespace std;
map<int, char> mp;
void init(){
    for(int i = 0; i < 9; i ++ )    mp[i] = '0' + i;
    mp[10] = 'X';
}
int main(){
    init();
    string s;   cin >> s;
    int sum = 0, k = 1;
    for(int i = 0; i < s.size() - 1; i ++ ){
        if(s[i] == '-') continue;
        sum += (s[i] - '0') * (k ++ ); 
    }
    sum %= 11;
    if(mp[sum] != s[s.size() - 1]){
         s[s.size() - 1] = mp[sum];
         cout << s << endl;
    }else   cout << "Right" << endl;
    return 0;
}



Value
1天前
#include <iostream>
using namespace std;
const int N = 1E4 + 10;
int mp[N];
int main(){
    int n;  cin >> n;
    for(int i = 0; i < n; i ++ ){
        int tmp;    cin >> tmp;
        mp[tmp] ++ ;

    }   
    int res = 0, maxv = 0;
    for(int i = N - 1; i >= 1; i -- ){
        if(mp[i] >= maxv){
            maxv = mp[i];
            res = i;
        } 
    }
    cout << res << endl;
    return 0;
}



Value
1天前
#include <iostream>
using namespace std;
const int N = 1E4 + 10;
int mp[N];
int main(){
    int n;  cin >> n;
    for(int i = 0; i < n; i ++ ){
        int tmp;    cin >> tmp;
        mp[tmp] ++ ;

    }   
    int res = 0, maxv = 0;
    for(int i = N - 1; i >= 1; i -- ){
        if(mp[i] >= maxv){
            maxv = mp[i];
            res = i;
        } 
    }
    cout << res << endl;
    return 0;
}


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

Value
1天前
#include <iostream>
#include <queue>
#include <cmath>
#define x first
#define y second
using namespace std;
const int N = 110;
typedef pair<int, int> pii;
int n, m, id;
double mp[N];
int top;
pii q[N * N];
char graph[N][N];
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
double get_hash(){
    double res = 0;
    for(int i = 0; i < top; i ++ ){
        for(int j = i + 1; j < top; j ++ ){
            double xx = q[i].x - q[j].x;
            double yy = q[i].y - q[j].y;
            res += sqrt(xx * xx + yy * yy);
        }
    }
    return res;
}
char get_id(double key){
    for(int i = 0; i < id; i ++ ){
        if(fabs(key - mp[i]) < 1e-6)    return 'a' + i;
    }
    mp[id ++ ] = key;
    return id - 1 + 'a';
}
void bfs(int i, int j){
    queue<pii> qu;
    qu.push({i, j}), q[top ++ ] = {i, j};
    graph[i][j] = '@';
    while(!qu.empty()){
        pii now = qu.front();
        qu.pop();
        for(int i = 0; i < 8; i ++ ){
            int xx = now.x + dx[i];
            int yy = now.y + dy[i];
            if(xx < 0 || xx >= n || yy < 0 || yy >= m || graph[xx][yy] != '1')  continue;
            graph[xx][yy] = '@';
            qu.push({xx, yy}), q[top ++ ] = {xx, yy};
        }
    }
}
int main(){
    cin >> m >> n;
    for(int i = 0; i < n; i ++ )    cin >> graph[i];
    for(int i = 0; i < n; i ++ ){
        for(int j = 0; j < m; j ++ ){
            if(graph[i][j] == '1'){
                top = 0;
                bfs(i, j);
                char c = get_id(get_hash());
                for(int k = 0 ; k < top; k ++ ) graph[q[k].x][q[k].y] = c;
            }
        }
    }
    for(int i = 0; i < n; i ++ ){
        for(int j = 0; j < m; j ++ ){
            cout << graph[i][j];
        }
        cout << endl;
    }
    return 0;
}



Value
1天前
#include <iostream>
#include <queue>
#include <cmath>
#define x first
#define y second
using namespace std;
const int N = 110;
typedef pair<int, int> pii;
int n, m, id;
double mp[N];
int top;
pii q[N * N];
char graph[N][N];
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
double get_hash(){
    double res = 0;
    for(int i = 0; i < top; i ++ ){
        for(int j = i + 1; j < top; j ++ ){
            double xx = q[i].x - q[j].x;
            double yy = q[i].y - q[j].y;
            res += sqrt(xx * xx + yy * yy);
        }
    }
    return res;
}
char get_id(double key){
    for(int i = 0; i < id; i ++ ){
        if(fabs(key - mp[i]) < 1e-6)    return 'a' + i;
    }
    mp[id ++ ] = key;
    return id - 1 + 'a';
}
void bfs(int i, int j){
    queue<pii> qu;
    qu.push({i, j}), q[top ++ ] = {i, j};
    graph[i][j] = '@';
    while(!qu.empty()){
        pii now = qu.front();
        qu.pop();
        for(int i = 0; i < 8; i ++ ){
            int xx = now.x + dx[i];
            int yy = now.y + dy[i];
            if(xx < 0 || xx >= n || yy < 0 || yy >= m || graph[xx][yy] != '1')  continue;
            graph[xx][yy] = '@';
            qu.push({xx, yy}), q[top ++ ] = {xx, yy};
        }
    }
}
int main(){
    cin >> m >> n;
    for(int i = 0; i < n; i ++ )    cin >> graph[i];
    for(int i = 0; i < n; i ++ ){
        for(int j = 0; j < m; j ++ ){
            if(graph[i][j] == '1'){
                top = 0;
                bfs(i, j);
                char c = get_id(get_hash());
                for(int k = 0 ; k < top; k ++ ) graph[q[k].x][q[k].y] = c;
            }
        }
    }
    for(int i = 0; i < n; i ++ ){
        for(int j = 0; j < m; j ++ ){
            cout << graph[i][j];
        }
        cout << endl;
    }
    return 0;
}


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

Value
3天前
#include <iostream>
using namespace std;
const int N = 110;
int a[N][N], sum[N][N];
int main(){
    int n;  cin >> n;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ )   cin >> a[i][j];
    }
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ ){
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
        }
    }
    int maxv = -0x3f3f3f;
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ )
            for(int k = i; k <= n; k ++ )
                for(int m = j; m <= n; m ++ )
                    maxv = max(maxv, sum[k][m] - sum[i - 1][m] - sum[k][j - 1] + sum[i - 1][j - 1]);
    cout << maxv << endl;
    return 0;
}



Value
3天前
#include <iostream>
using namespace std;
const int N = 110;
int a[N][N], sum[N][N];
int main(){
    int n;  cin >> n;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ )   cin >> a[i][j];
    }
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= n; j ++ ){
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
        }
    }
    int maxv = -0x3f3f3f;
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ )
            for(int k = i; k <= n; k ++ )
                for(int m = j; m <= n; m ++ )
                    maxv = max(maxv, sum[k][m] - sum[i - 1][m] - sum[k][j - 1] + sum[i - 1][j - 1]);
    cout << maxv << endl;
    return 0;
}