头像

HimenoSena




离线:1个月前


最近来访(5)
用户头像
lpf
用户头像
棉花糖SR
用户头像
封禁用户
用户头像
滑稽_ωノ


HimenoSena
8个月前
#include <bits/stdc++.h>
using namespace std;
int st[30], ed[30], f[30];  //开头、结尾位置
int main() {
    string str; cin >> str;
    for (int i = 0; i < 52; i++) {
        char ch = str[i];
        if (f[ch - 'A' + 1]) ed[ch - 'A' + 1] = i;
        else st[ch - 'A' + 1] = i, f[ch - 'A' + 1] = 1;
    }
    int ans = 0;
    for (int i = 1; i <= 26; i++)
        for (int j = i + 1; j <= 26; j++) {
            if (st[i] < st[j] && ed[i] > st[j] && ed[i] < ed[j]) ans++;
            else if (st[j] < st[i] && ed[j] > st[i] && ed[j] < ed[i]) ans++;
        }
    printf("%d\n", ans);
    return 0;
}






活动打卡代码 AcWing 1801. 蹄子剪刀布

HimenoSena
8个月前
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> PII;


PII arr[110];

void slove(){
    int n; cin >> n;
    for(int i = 1; i <= n; i++) cin >> arr[i].first >> arr[i].second;
    int ans = 0;
    int k = 0;
    for(int i = 1; i <= n; i++){
        if(arr[i].first == 1 && arr[i].second == 2 
        || arr[i].first == 2 && arr[i].second == 3
        || arr[i].first == 3 && arr[i].second == 1) k++;
    }
    ans = max(ans, k);
    k = 0;
    for(int i = 1; i <= n; i++){
        if(arr[i].first == 1 && arr[i].second == 3 
        || arr[i].first == 3 && arr[i].second == 2
        || arr[i].first == 2 && arr[i].second == 1) k++;
        ans = max(ans, k);
    }

    cout << ans << '\n';
}



int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    slove();



}




活动打卡代码 AcWing 1813. 方块游戏

HimenoSena
8个月前
#include<bits/stdc++.h>


using namespace std;
typedef long long ll;

unordered_map<char, int> mp;

pair<string, string> k[110];
void slove(){
    int n; cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> k[i].first >> k[i].second;
    }
    for(int i = 1; i <= n; i++){
        char v[26] = {0}, u[26] = {0};
        for(auto c : k[i].first){
            v[c - 'a']++;
        }
        for(auto c : k[i].second){
            u[c - 'a']++;
        }
        for(int i = 0; i < 26; i++){
            mp['a' + i] += max(v[i], u[i]);
        }
    }
    for(int i = 0; i <= 25; i++){
        cout << mp['a' + i] << '\n';
    }

}


int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    slove();



}





活动打卡代码 AcWing 1826. 农田缩减

HimenoSena
8个月前
#include <bits/stdc++.h>
using namespace std;

int main() {

    int n;
    cin >> n;
    vector<pair<int, int>> v(n);
    vector<int> x(n), y(n); 

    int ret = INT_MAX;

    for(int i = 0; i < n; ++i) {
        cin >> v[i].first >> v[i].second;
        x[i] = v[i].first;
        y[i] = v[i].second;
    }

    sort(x.begin(), x.end());
    sort(y.begin(), y.end());

    for(int i = 0; i < n; ++i) {
        int cx = v[i].first, cy = v[i].second;
        int width = 40000, height = 40000;

        if(cx == x[0]) width = x[n - 1] - x[1];
        else if(cx == x[n - 1]) width = x[n - 2] - x[0];
        else width = x[n - 1] - x[0];

        if(cy == y[0]) height = y[n - 1] - y[1];
        else if(cy == y[n - 1]) height = y[n - 2] - y[0];
        else height = y[n - 1] - y[0];

        ret = min(ret, width * height);
    }

    cout << ret << endl;

    return 0;
}





活动打卡代码 AcWing 1843. 圆形牛棚

HimenoSena
8个月前

暴力即可

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

typedef long long ll;

int a[10100];


void slove(){
    int n; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    ll ans = INF;
    for(int i = 1; i <= n; i++){
        ll sum = 0;
        for(int j = 1; j <= n; j++){
            if(j < i) sum += (n - i + j) * a[j];
            else sum += (j - i) * a[j];
        }
        ans = min(ans, sum);
    }
    cout << ans << '\n';
}


int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    slove();
}

递推 O(N);


#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, ans = 2e9, sum = 0, suma = 0; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
        if(cin >> a[i]) sum += i * a[i], suma += a[i];//记录开第一个房间的门的花费,牛的数量

    for(int i = 0; i < n; i++) sum += a[i] * n - suma, ans = min(ans, sum);
    cout << ans;
    return 0;
}




活动打卡代码 AcWing 1855. 愤怒的奶牛

HimenoSena
8个月前

暴力模拟就像

#include<bits/stdc++.h>

using namespace std;

const int N = 110, INF = 2e9;

int p[N];



int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n; cin >> n;
    p[0] = -INF, p[n + 1] = INF;
    for(int i = 1; i <= n; i++) cin >> p[i];
    sort(p + 1, p + 1 + n);
    int ans = 0;
    for(int i = 1; i <= n; i++){
        int l = 1, r = 1, a = i, b = i;
        while(p[a] - p[a-1] <= l){
            int k = a;
            while(p[a] - p[k-1] <= l){
                k--;
            }
            a = k;
            l++;
        }
        while(p[b + 1] - p[b] <= r){
            int k = b;
            while(p[k + 1] - p[b] <= r){
                k++;
            }
            b = k;
            r++;
        }
        ans = max(ans, b - a + 1);
    }
    cout << ans << '\n';

}





活动打卡代码 AcWing 1875. 贝茜的报复

HimenoSena
8个月前

分类讨论奇偶 注意 负的奇数 % 2 = -1 例如 -3 % 2 == -1


#include<bits/stdc++.h>

using namespace std;

int b[3], e[3], s[3], i[3], g[3], o[3], m[3];

typedef long long ll;
void solve(){
    int n; cin >> n;
    for(int j = 1; j <= n; j++){
        char c; int  v; cin >> c >> v;
        if(c == 'B') {
            if(v % 2 == 1 || v % 2 == -1) b[1]++;
            else b[2]++;
        }
        if(c == 'E') {
            if(v % 2 == 1 || v % 2 == -1) e[1]++;
            else e[2]++;
        }
        if(c == 'S') {
            if(v % 2 == 1 || v % 2 == -1) s[1]++;
            else s[2]++;
        }
        if(c == 'I') {
            if(v % 2 == 1 || v % 2 == -1) i[1]++;
            else i[2]++;
        }
        if(c == 'G') {
            if(v % 2 == 1 || v % 2 == -1) g[1]++;
            else g[2]++;
        }
        if(c == 'O') {
            if(v % 2 == 1 || v % 2 == -1) o[1]++;
            else o[2]++;
        }
        if(c == 'M') {
            if(v % 2 == 1 || v % 2 == -1) m[1]++;
            else m[2]++;
        }
    }
    // cout << b[1]  << ' ' << b[2] << '\n';
    // cout << e[1]  << ' ' << e[2] << '\n';
    // cout << s[1]  << ' ' << s[2] << '\n';
    // cout << i[1]  << ' ' << i[2] << '\n';
    // cout << g[1]  << ' ' << g[2] << '\n';
    // cout << o[1]  << ' ' << o[2] << '\n';
    // cout << m[1]  << ' ' << m[2] << '\n';

    ll y1 = b[1] * i[2] + b[2] * i[1];
    ll y2 = g[1] * o[2] * e[2] * s[2] + g[2] * o[1] * e[2] * s[2] 
    + g[2] * o[2] * e[1] * s[2] + g[2] * o[2] * e[2] * s[1] + g[2] * o[1] * e[1] * s[1]
    + g[1] * o[2] * e[1] * s[1] + g[1] * o[1] * e[2] * s[1] + g[1] * o[1] * e[1] * s[2];
    ll y3 = m[1];
    // cout << y1 << ' ' << y2 << " " << y3 << '\n';
    cout << (b[1] + b[2]) * (i[1] + i[2]) * (e[1] + e[2]) * (s[1] + s[2]) * (g[1] + g[2]) 
    * (o[1] + o[2]) * (m[1] + m[2]) - y1 * y2 * y3 << '\n';
}


int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    solve();






}







活动打卡代码 AcWing 378. 骑士放置

HimenoSena
10个月前
#include<iostream>
#include<cstring>
#include<algorithm>

#define x first
#define y second

using namespace std;
typedef pair<int,int> PII;
const int N=110;
int n,m,k;
PII match[N][N];
bool g[N][N],st[N][N];

int dirs[8][2] = {{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2}};

bool find(int x,int y)
{
    for(int i = 0;i<8;i++)
    {
        int nx = x+dirs[i][0],ny = y+dirs[i][1];
        if(nx<1 || nx>n || ny<1 || ny>m || g[nx][ny] || st[nx][ny]) continue;
        st[nx][ny] = true;//男[x,y] 找到女[nx,ny]
        PII t = match[nx][ny];//t为女[nx,ny]现在匹配的对象
        if(t.x==0||find(t.x,t.y))//如果女[nx,ny]没有匹配对象或者现配t可以去找其他妹子 那就把[nx,ny]给[x,y]
        {
            match[nx][ny] = {x,y};
            return true;
        }
    }
    return false;
}

int main()
{
    cin >> n >> m >> k;
    for(int i = 0;i<k;i++)
    {
        int x,y;
        cin >> x >> y;
        g[x][y] = true;
    }
    int res =0;
    for(int i =1;i<=n;i++)
    {
        for(int j = 1;j<=m;j++)
        {
            if(g[i][j] || (i+j)%2)continue;
            memset(st,0,sizeof st);
            if(find(i,j))res++;
        }
    }
    cout << n*m - k - res << endl;
    return 0;
}






活动打卡代码 AcWing 377. 泥泞的区域

HimenoSena
10个月前
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5,inf=1<<29;
const double eps=1e-6;
typedef long long ll;
typedef pair<int,int> pii;
#define mk(a,b) make_pair(a,b)
struct Node{ int ver,next;}edge[maxn] ;
char ar[110][110]; 
int n,m,tot,head[maxn],cnt1=1,cnt2=1,
    a[110][110],b[110][110],match[maxn],vis[maxn];
void add(int u,int v) {
    edge[++tot].ver=v; edge[tot].next=head[u]; head[u]=tot;
}
bool dfs(int x) {  //运行匈牙利算法 
    for(int i=head[x],y;i;i=edge[i].next) {
        if(!vis[y=edge[i].ver]) {
            vis[y]=1;
            if(!match[y]||dfs(match[y])) {
                match[y]=x; return true;
            }
        }
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) 
            cin>>ar[i][j]; 
    for(int i=1;i<=n;i++) {  //行块号 
        for(int j=1;j<=m;j++) {
            if(ar[i][j]=='*') a[i][j]=cnt1 ;
            else cnt1++ ;
        } cnt1++; 
    }
    for(int j=1;j<=m;j++) {  //列块号 
        for(int i=1;i<=n;i++) {
            if(ar[i][j]=='*') b[i][j]=cnt2 ;
            else cnt2++ ;
        } cnt2++;
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) { //行号 、列号 
            if(ar[i][j]=='*') add(a[i][j],b[i][j]); //连边 
        }
    }
    int ans=0;
    for (int i=1;i<=cnt1;i++) { //行号 
        memset(vis,0,sizeof(vis) ); //最大匹配边 
        if(dfs(i)) ans++;
    }
    cout<<ans<<endl;
    return 0;
}








HimenoSena
10个月前

题目描述

有两台机器 A,B 以及 K 个任务。

机器 A 有 N 种不同的模式(模式 0∼N−1),机器 B 有 M 种不同的模式(模式 0∼M−1)。

两台机器最开始都处于模式 0。

每个任务既可以在 A 上执行,也可以在 B 上执行。

对于每个任务 i,给定两个整数 a[i] 和 b[i],表示如果该任务在 A 上执行,需要设置模式为 a[i],如果在 B 上执行,需要模式为 b[i]。

任务可以以任意顺序被执行,但每台机器转换一次模式就要重启一次。

求怎样分配任务并合理安排顺序,能使机器重启次数最少。
输入格式
输入包含多组测试数据。

每组数据第一行包含三个整数 N,M,K。

接下来 K 行,每行三个整数 i,a[i] 和 b[i],i 为任务编号,从 0 开始。

当输入一行为 0 时,表示输入终止。

输出格式
每组数据输出一个整数,表示所需的机器最少重启次数,每个结果占一行。

数据范围
N,M<100,K<1000
0≤a[i]<N
0≤b[i]<M

样例

输入样例:
5 5 10
0 1 1
1 1 2
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
0
输出样例:
3

因为AB机器开始状态是0,所以只要是可以用A或B机器的0状态解决的任务,可以不重启直接解决。
A机器重启的次数等于选择A机器的任务的数量。
B机器重启的次数等于选择B机器的任务的数量。
总重启次数等于覆盖所有边的点的数量。
求重启次数最小值就是二分图最小点覆盖。
二分图最小点覆盖等于二分图最大匹配的边数

C++ 代码


#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m, k, t;
int mp[1220][1220];
int vis[1220], match[1220];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int maps[1010][1010];

bool dfs(int x){
    for(int i = 1; i <= m; i++){
        if(!vis[i] && mp[x][i]){
            vis[i] = 1;
            if(!match[i] || dfs(match[i])){
                match[i] = x; return true;
            }
        }
    }
    return false;
}

void solve(){
    while(cin >> n && n){
        memset(match, 0, sizeof(match));
        memset(mp, 0, sizeof(mp));
        cin >> m >> k;
        for(int i = 1; i <= k; i++){
            int t, u, v; cin >> t >> u >> v;
            mp[u][v] = 1;
        }
        int ans = 0;
        for(int i = 1; i <= n; i++){
            memset(vis, 0, sizeof(vis));
            if(dfs(i)) ans++;
        }
        cout << ans << '\n';
    }
}

int main(){
    solve();


}