526互联

《看了受制了》第二十八天，7道题，合计141道题

发布时间 2023-09-28 01:50:41作者: wxzcch

2023年9月27日
今天学会线段树、树状数组（只是板子），我们还是要多敲!!!加油，自己催眠自己。。虽然我们菜，但是我们肝。

Acwing1265 数星星

题目理解

因为是以y递增的形式给出的。我们动态求，在它的左面有多少星星即可。即动态区间和(树状数组板子题)。

代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int N = 32010;
int tr[N],n,leave[N];

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

void add(int x)
{
    for(int i=x;i <N; i += lowbit(i)) tr[i] += 1;
}

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

int main()
{
    cin>>n;
    int x = n;
    while(n--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x++;                    //因为X是从0开始的，但是树状数组一定是从1开始的！！
        leave[sum(x)]++;
        add(x);
    }
    for(int i=0; i<= x -1;i++)
        cout<<leave[i]<<endl;
    return 0;
}

Acwing1215 小朋友排队

题目理解

该题目可以转换为以下几点来理解：

  • 我们交换的最小次数就是k次，通过冒泡、即可得到该答案。
  • 每个小朋友需要交换的次数为：左边比他大的数的个数\(k_1\)已经右边比他小的个数\(k_2\)
  • 那么每个小朋友的仇恨值就是\(1 + 2 + .. + (k_1 + k_2)\)

所以这个\(k_1 + k_2\)就可以用树状数组求得，求两次，一次求从左往右的\(k_1\),第二次求从右往左的\(k_2\)

代码实现

const int N = 1e6 + 10;
int h[N], tr[N], n;
ll cnt[N];
ll lowbit(ll x){return x & -x;}

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

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

int main() {

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

    // 求每个数前面有多少个数比它大
    for(int i = 0; i < n; i++)
    {
        cnt[i] = query(N - 1) - query(h[i]);
        add(h[i], 1);
    }

    memset(tr, 0, sizeof tr);
    // 求后面有多少个数比他小
    for(int i = n - 1; i >= 0; i--)
    {
        cnt[i] += query(h[i] - 1);
        add(h[i], 1);
    }
    ll res = 0;
    for(int i = 0; i < n; i++)
        res += cnt[i] * (cnt[i] + 1) / 2;

    cout << res;
    return 0;
}

Div.3 Round900 E Iva & Pav

题目理解

这个题是昨天晚上，没有A掉的线段树！！板子题！！今天学到了！！练手！！拿下!!!
昨晚上二分的check超时了，因为每次都&到底，是不行的。所以我们选择线段树解决区间问题！！！

  • 利用越与越小的性质
  • 我们用线段树存区间&的值
  • 然后二分找r
  • 注意存在与，所以我们用一下中的INT_MAX

代码实现

const int N = 2e5 + 10;

struct Node
{
    int l, r;
    int val;
}tr[N * 5];

int w[N];

void pushup(int u)
{
    tr[u].val = tr[u << 1].val & tr[u <<  1 | 1].val;
}

void build(int u, int l, int r)
{
    if(l == r) tr[u] = {l, r, w[r]};    // 如果已经是叶子节点了
    else{
        tr[u] = {l, r};
        int mid = (l + r) >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].val;

    int val = INT_MAX;
    int mid = (tr[u].l + tr[u].r) >> 1;

    if(l <= mid) val = query(u << 1, l, r);
    if(r > mid) val &= query(u << 1 | 1, l, r);

    return val;

}

void solve()
{

    int n;
    cin >> n;

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

    build(1, 1, n);
    
    int m;
    cin >> m;

    for(int i = 1; i <= m; i++)
    {
        int l, k;
        cin >> l >> k;
        int tmpl = l;
        int r = n;
        
        while(l < r)
        {
            int mid = (l + r + 1) >> 1;
            if(query(1, tmpl, mid) >= k) l = mid;
            else r = mid - 1;
        }
        if(tmpl == l && w[l] < k)l = -1;
        
        cout << l << " ";
    }

    cout << endl;
    return;
}

Div.3 Round894 A Gift Carpet

题目理解

竖着匹配是否存在vika即可

代码实现

void solve()
{
    int n, m;
    cin >> n >> m;
    int falg = 0;
    vector<string> q(n);
    for(int i = 0; i < n; i++)
        cin >> q[i];
    
    string tmp = "vika";
    int flag = 0;
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(q[j][i] == tmp[flag])
            {
                flag ++;
                break;
            }
        }
        if(flag == 4){
            cout << "YES" << endl;
            return;
        } 
    }
    cout << "NO" << endl;
    return;
}

Div.3 Round894 B Sequence Game

题目理解

  • 第一个数正常输出
  • 用vector来存答案数组
  • 从第二个数开始如果，a[i] < b[b.size() - 1]，那么多放一个a[i]即可

代码实现

const int N  = 2e5 + 10;

int a[N];
void solve()
{
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++)
        cin >> a[i];
    
    vector<int> b;
    b.push_back(a[1]);

    for(int i = 2; i <= n; i++)
        if(a[i] < b[b.size() - 1])
        {
            b.push_back(a[i]);
            b.push_back(a[i]);
        }else{
            b.push_back(a[i]);
        }
    
    cout << b.size() << endl;

    for(int i = 0; i < b.size(); i++)
        cout << b[i] << " ";
    cout << endl;
    return ;
}

Div.3 Round894 C Flower City Fence

题目理解

题目重点：如果a[i] > n那么必然不可能对称。有了上述条件我们便可进行如下操作

  • 那么高度限制就是n的限制为1 ~ n
  • 利用差分得到，翻转后的篱笆
  • 如果翻转后和没反转相同，即为对称

代码实现

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1000);
    bool ok = true;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        if (a[i] > n) ok = false;
    }
    if (!ok) {
        cout << "NO\n";
        return ;
    }
    for (int i = 1; i <= n; i ++) {
        b[1] ++;
        b[a[i] + 1] --;
    }
    for (int i = 1; i <= n; i ++) b[i] += b[i - 1];
    for (int i = 1; i <= n; i ++) if (a[i] != b[i]) ok = false;
    if (ok) cout << "YES\n";
    else cout << "NO\n";
}

Div.3 Round894 D Ice Cream Balls

题目理解

要的是最少的雪糕球的种类，在这个条件下达到组合为k。

  • 如果x个不同的雪糕球，那么可以做出来x * (x - 1) / 2种雪糕
  • 如果，我们再在1 - x的区间中，添加p个，互不相同的数，那么组合又会多出来p种。
  • 所以如果x * (x - 1) / 2 == k那就输出x
  • 不然就为，x - 1 + n - ((x - 1) * (x - 2) / 2)个，因为我们还缺一些。
  • 然后我们的x用二分就能找到

代码实现


void solve()
{
    ll n;
    cin >> n;
 
    ll l = 1, r = 2e9;
 
    while (l < r)
    {
        ll mid = (l + r) >> 1;
        if (mid * (mid - 1) / 2 >= n)
            r = mid;
        else
            l = mid + 1;
    }
 
    if(l * (l - 1) / 2 == n) cout << l << endl;
    else
	{
		ll t = l - 1, s = t * (t - 1) / 2;
		printf("%lld\n", t + n - s);
	}
    return;
}