Cat Party (Easy Edition)

Problem - 1163B2 - Codeforces

The meaning of the topic ： Let you find the maximum length x,1 - x Between （ You can delete perhaps Don't delete ） A number , Give Way 1-x All numbers between are the same , Find the longest position .

Their thinking ：

One ：

1  The number of occurrences of each color is 1.

2 Only one color appears the most , And the number of occurrences is I.

3 The number of occurrences of a color is 1, Other colors appear the same number of times .

4 One color appears more times than any other color 1 Time

#include <iostream>
#include <stdio.h>
using namespace std;
const int N = 1e5 + 10;
int n, color, ans, mx, f[N], cnt[N];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        scanf("%d", &color);
        cnt[f[color]]--;
        f[color]++;
        cnt[f[color]]++;
        mx = max(mx, f[color]);
        bool ok = false;
        if (cnt[1] == i)
            ok = true;
        else if (cnt[i] == 1)
            ok = true;
        else if (cnt[1] == 1 && cnt[mx] * mx == i - 1)
            ok = true;
        else if (cnt[mx - 1] * (mx - 1) == i - mx && cnt[mx] == 1)
            ok = true;
        if (ok)
            ans = i;
    }
    printf("%d", ans);
    return 0;
}

Solution 2 ：

This is a good feeling after reading the problem-solving ideas of other bloggers

Link to the original text ：https://blog.csdn.net/Tc_To_Top/article/details/90179927

Their thinking

The main idea of the topic ： Find a maximum number x, bring u[1]~u[x] Under the condition that a position must be deleted , The frequency of other numbers is the same

Topic analysis ： set up u[i] The frequency of occurrence is a, frequency a stay 1~i The number of occurrences in is b, Subject requirements 1~i You must delete a position in , So if a*b=i-1 The current i feasible , There is also a case like example 1 , namely a*b=i, If at this time i+1<=n, Then bring it i+1 Also meet the requirements of the topic
 

#include"bits/stdc++.h"
#define ll long long
#define pi pair<int,int>
#define inf 0x3f3f3f3f
#define  _for(i,a,b) for(int i=a;i<=b;i++)
#define  for_(i,a,b) for(int i=a;i<b;i++)
#define _fr(i,a,b) for(int i=a;i>=b;i--)
#define fr_(i,a,b) for(int i=a;i>b;i--)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 1e5+5;
const ll mod = 1e9+7;
const double lp=1.000000011;
map<char,int>mp;
int n,x;
int a[N],b[N];
void solve(){
    cin >> n;
    int ans = 1;
    _for(i,1,n){
        cin >> x;
        a[x]++;
        b[a[x]]++;
        if(i != n && a[x] * b[a[x]] == i){
            ans = i+1;
        }else if(a[x] * b[a[x]] == i-1){
            ans = i;
        }
    }
    cout << ans << endl;
}

int main()
{
    IOS;
    solve();
    return 0;
}