《看了受制了》第三十天，9道题，合计157道

2023年9月29日

Awcing244 迷一样的牛

题目大意

• 有n头牛，身高是1 ~ n
• 给出了n头牛，每头牛前面有多少个比它高的牛
• 求它们的身高是多少？

题目理解

将题目转化成，倒着去枚举，在现在的序列中，二分去找第k + 1小的值，每次输出一个身高，把身高弹出。

代码实现

const int N = 1e5 + 10;
int n, a[N], tr[N];

int lowbit(int u) { return u & -u; }

int sum(int a)
{
    int val = 0;
    for (int i = a; i; i -= lowbit(i))
        val += tr[i];
    return val;
}

void add(int a, int c)
{
    for (int i = a; i <= n; i += lowbit(i))
        tr[i] += c;
}

int main()
{
    cin >> n;

    for (int i = 2; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++)
        add(i, 1);

    vector<int> res;
    for (int i = n; i >= 1; i--)
    {
        int l = 1, r = n;
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(sum(mid) >= a[i] + 1) r = mid;
            else l = mid + 1;
        }
        res.push_back(l);       // 把下标当作了，第`k + 1`大的数
        add(l, -1);
    }

    for (int i = res.size() - 1; i >= 0; i--)
        cout << res[i] << endl;

    return 0;
}

Acwing242 一个简单的整数问题

题目大意

把区间里面的所有值，加d，然后求第x个值。

题目理解

用树状数组维护原序列的差分序列，因为树状数组求的是前缀和，那么原序列的差分数组的前缀和就是原序列。

代码实现

const int N = 1e5 + 10;

int tr[N], num[N];
int n, m;

int lowbit(int a){return a & -a;}

void add(int a, int c)
{
    for(int i = a; i <= N; i += lowbit(i)) tr[i] += c;
}

int sum(int a)
{
    int val = 0;
    for(int i = a; i >= 1; i -= lowbit(i)) val+=tr[i];
    return val;
}

int main() {

    cin >> n >> m;

    for(int i = 1; i <= n; i++) cin >> num[i];
    for(int i = 1; i <= n; i++) add(i, num[i] - num[i - 1]);

    while(m -- )
    {
        string op;
        cin >> op;
        if(op == "C"){
            int l, r, c;
            cin >> l >> r >> c;
            add(l, c);
            add(r + 1, -c);
        }else{
            int c;
            cin >> c;
            cout << sum(c)<< endl;
        }   
    }

    return 0;
}

Div.4 Round886 To My Critics

题目大意

有没有任意两个数的和大于10。

题目理解

就模拟即可。

代码实习

void solve()
{
    int a, b, c;
    cin >> a >> b >> c;

    if(a + b >= 10) cout << "YES" << endl;
    else if(a + c >= 10) cout << "YES" << endl;
    else if(b + c >= 10) cout << "YES" << endl;
    else cout << "NO" << endl;

    return;
}

Div.4 Round886 Ten Words of Wisdom

题目大意

在a小于等于10的情况下，最大的b。

题目理解

模拟即可，就是读入a,b，只有在a小于等于10，更新b

代码实现

void solve()
{
    int n, flag, now = 0;
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        int a, b;
        cin >> a >> b;
        if (a <= 10 && b > now)
        {
            flag = i;
            now = b;
        }
    }

    cout << flag << endl;
    return;
}

Div.4 Round886 Word on the Paper

题目大意

一列的字母形成的字符串是什么？

题目理解

直接竖着遍历即可。

代码实现

void solve()
{
    vector<string> vec(8);

    for(int i = 0; i < 8; i++) cin >> vec[i];

    string s = "";

    for(int i = 0; i < 8; i++)
    {
        for(int j = 0; j < 8; j++)
            if(vec[j][i] != '.') s += vec[j][i];
        if(s != "") break;
    }
    cout << s << endl;
    return;
}

Div.4 Round886 Balanced Round

题目大意

给了一个序列，要让序列里面的每个数差不大于k，问要最少删除多少个数

题目理解

那我们排个序，然后求出，最长的差不大于k的序列长度即可。然后用n - len

代码实现

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<int> vec;

    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        int b;
        cin >> b;
        if (b == 0)
            res++;
        else
            vec.push_back(b);
    }

    sort(vec.begin(), vec.end());


    int len = 0;
    int idx = 1;
    for(int i = 1; i < vec.size(); i++)
    {
        if(vec[i] - vec[i - 1] > k)
        {
            len = max(len, idx);
            idx = 1;
        }else{
            idx++;
        }
    }

    len = max(len, idx);
    cout << res + (vec.size() - len)<< endl;
    return;
}

Div.4 Round886 Cardboard for Pictures

题目大意

给了多张照片，然后给这些照片做了框框。做框框一共用了c面积的纸，框框和照片的间距是多少。

题目理解

这个题目可以直接二分就行。

• 因为给定了用的面积
• 然后我们二分模拟答案，因为每张照片适用的面积就是(2 * w + a[i])^2

代码实现

bool check(ll u)
{
    ll total = 0;

    for(int i = 1; i <= n; i++)
    {
        total += (a[i] + u + u) * (a[i] + u + u);
        if(total > s) return false;
    }

    return true;
}

void solve()
{
  
    cin >> n >> s;
    for(int i = 1; i <= n; i++) cin >> a[i];

    ll l = 1, r = 1e9;

    while(l < r)
    {
        ll mid = (l + r + 1) >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l <<endl;
    return;
}

Div.4 Round886 We Were Both Children

题目大意

每个青蛙从1开始，可以跳不同的远度，我们可以从1 ~ n的地方放置一个陷阱，问这个陷阱能捕到多少青蛙。那么问题就是，1 ~ n中的哪个数是青蛙跳到的次数最多的地方

题目理解

• 注意我们只能从1 ~ n中放置陷阱，所以有的青蛙一下跳的大于n我们都不管了。
• 然后因为n是2e5，那么就可以枚举所有青蛙的跳远的倍数即可
• 对于1做特殊处理
  思路优化：
• 用map存储，相同远度的青蛙，可以减少时间复杂度。不然全是2那个倍数太多了会tle

代码实现

const int N = 2e5 + 10;
int a[N];
void solve()
{
    int n;
    cin >> n;

    vector<int> vec;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        int b;
        cin >> b;
        if (b <= n)
        {
            if (b == 1)
                cnt++;
            else
                vec.push_back(b);
        }
    }

    

    if (vec.size() == 0 && cnt == 0)
    {
        cout << 0 << endl;
        return;
    }
    memset(a, 0, sizeof a);
    unordered_map<int, int> mp;

    for(int i = 0; i < vec.size(); i++)
        if(!mp.count(vec[i]))
            mp[vec[i]] = 1;
        else
            mp[vec[i]]+=1;
    
    sort(vec.begin(), vec.end());  //去重
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    for (int i = 0; i < vec.size(); i++)
        for (int j = vec[i]; j <= n; j += vec[i])
            a[j] += mp[vec[i]];
        
    int res = 0;

    for (int i = 2; i <= n; i++)
        res = max(a[i], res);

    cout << res + cnt << endl;
    return;
}

Div.4 Round886 The Morning Star

题目大意

给了很多坐标，问有多少组合两两点可以共线。

题目理解

因为只有8个方向，其实就是4条线。它们共线无疑就4个可能

• x == x
• y == y
• x + y == x + y
• x - y == x - y
  那么求和就行了，最后再乘2

代码实现

const int N = 2e5 + 10;
int a[N];
void solve()
{

    int n;
    scanf("%d", &n);

    map<int, ll> mp[4];

    ll ans = 0;
    int a, b;
    for(int i = 1; i <= n; i++)
    {
        
        scanf("%d%d", &a, &b);

        ans += mp[0][a]++;
        ans += mp[1][b]++;
        ans += mp[2][a + b]++;
        ans += mp[3][a - b]++;
    }

    printf("%lld\n", ans * 2);

    return;
}