526互联

AtCoder Beginner Contest 318 ABCDE

发布时间 2023-09-22 20:07:30作者: nannan4128

AtCoder Beginner Contest 318

A - Full Moon

思路：等差数列求项数

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n,m,p;
    cin>>n>>m>>p;
    if(n<m)
    {
        cout<<0<<"\n";
        return 0;
    }
    //a1 = m,ak = a1+(k-1)*p;
    //m+(k-1)*p = n
    //(n-m)/p+1
    cout<<(n-m)/p+1<<"\n";
    return 0;
}

B - Overlapping sheets

思路：小规模直接模拟即可。(不会吧不会吧，不会真的有人写扫描线吧，好的是我TAT)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 201000;
vector<int>vx;
vector<array<int,4>>event;;
int n,q,m;

struct info
{
    int minv,mincnt;
};

info operator+(const info &l,const info &r)
{
    info a;
    a.minv = min(l.minv,r.minv);
    if(l.minv==r.minv)a.mincnt = l.mincnt + r.mincnt;
    else if(l.minv<r.minv)a.mincnt = l.mincnt;
    else a.mincnt = r.mincnt;
    return a;
}

struct node{
    int t;
    info val;
}seg[N*8];

void update(int id)
{
    seg[id].val = seg[id*2].val+seg[id*2+1].val;
}

void settag(int id,int t)
{
    seg[id].val.minv = seg[id].val.minv+t;
    seg[id].t = seg[id].t + t;
}

void pushdown(int id)
{
    if(seg[id].t!=0)
    {
        settag(id*2,seg[id].t);
        settag(id*2+1,seg[id].t);
        seg[id].t = 0;
    }
}

void build(int id,int l,int r)
{
    if(l==r)
        seg[id].val = {0,vx[r]-vx[r-1]};//mincnt就是区间长度，比如对于第一段就是第1个端点-第0个端点
    else 
    {
        int mid = (l+r)>>1;
        build(id*2,l,mid);
        build(id*2+1,mid+1,r);
        update(id);
    }
}


void modify(int id,int l,int r,int x,int y,ll t){
    if(l==x&&r==y)
    {
        settag(id,t);
        return;
    }
    int mid = (l+r)/2;
    pushdown(id);
    if(y<=mid) modify(id*2,l,mid,x,y,t);
    else if(x>mid) modify(id*2+1,mid+1,r,x,y,t);
    else{
        modify(id*2,l,mid,x,mid,t),modify(id*2+1,mid+1,r,mid+1,y,t);
    }
    update(id);
}


int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i = 1;i<=n;i++)
    {
        int x1,x2,y1,y2;
        cin>>x1>>x2>>y1>>y2;
        vx.push_back(x1);
        vx.push_back(x2);
        //y坐标,类型0,x坐标
        event.push_back({y1,1,x1,x2});
        event.push_back({y2,-1,x1,x2});
    }
    sort(event.begin(), event.end());
    sort(vx.begin(), vx.end());
    //去重
    vx.erase(unique(vx.begin(), vx.end()),vx.end());
    m = vx.size()-1;//段数=点数-1
    build(1,1,m);
    int prey = 0;
    int totlen = seg[1].val.mincnt;
    ll ans = 0;
    for(auto evt:event)
    {
        int cov = totlen;
        if(seg[1].val.minv==0)
            cov = totlen - seg[1].val.mincnt;
        ans += (ll)(evt[0]-prey)*cov;
        prey = evt[0];
        //第0个端点到第1个端点实际上对应线段树里面是1,1
        //相当于每个节点记录的是(l+1,r)的信息
        int x1 = lower_bound(vx.begin(), vx.end(),evt[2])-vx.begin()+1;
        int x2 = lower_bound(vx.begin(), vx.end(),evt[3])-vx.begin();
        if(x1>x2)continue;
        modify(1,1,m,x1,x2,evt[1]);
    }
    cout<<ans<<endl;
    return 0;
}

附上正常版本

#include <bits/stdc++.h>
using namespace std;

int s[200][200];
int main() {
    int n;
    cin >> n;
    int a, b, c, d;
    for (int i = 1; i <= n; i++) {
        cin >> a >> b >> c >> d;
        for (int j = a; j < b; j++) {
            for (int k = c; k < d; k++) {
                s[j][k]++;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= 100; i++) {
        for (int j = 0; j <= 100; j++) {
            if (s[i][j] > 0) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

C - Blue Spring

思路：排序+贪心。如果当前买通票比普通票便宜，那就一定买通票，否则普通票。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll f[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    ll n,d,p;
    cin>>n>>d>>p;
    for(int i = 1;i <= n; i++)
        cin>>f[i];
    sort(f+1,f+1+n);
    ll ans = 0,cnt = 0,sum = 0;
    for(int i = n;i >= 1;i--)
    {
        cnt++,sum+=f[i];
        if(cnt==d)
        {
            if(sum>p)
                ans += p;
            else ans += sum;
            cnt = 0,sum = 0;
        }
    }
    if(sum>p)
        ans += p;
    else ans += sum;
    cout<<ans<<"\n";
    return 0;
}

D - General Weighted Max Matching

思路：看到\(N\)只有\(16\)，一眼状压。枚举当前状态，\(1\)表示选了，\(0\)表示还没选，然后开始\(dp\).

考虑如何转移，在现在的状态下，要再选两个之前没选过的点且这两个点不能一样那就可以选。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll f[20][20];

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin>>n;
    for(int i = 0;i < n; i++)
        for(int j = i+1;j < n; j++)
            cin>>f[i][j],f[j][i] = f[i][j];
    vector<ll>dp(1<<n);
    for(int st = 0; st < (1<<n); st++)
    {
        for(int i = 0; i < n; i++)
        {
            if((st>>i)&1)continue;
            for(int j = 0;j < n; j++)
            {
                if(i==j)continue;
                if((st>>j)&1)continue;
                int nst = st|(1<<i)|(1<<j);
                dp[nst] = max(dp[nst],dp[st]+f[i][j]);
            }
        }
    }
    cout<<dp[(1<<n)-1]<<"\n";
    return 0;
}

E - Sandwiches

思路：这个题一开始没整出来。其实做法很简单。

方法一：枚举\(j\)。

对于一个三元组\((i,j,k)\)其中\(A_i=A_k,A_i\neq A_j\)。问有多少满足条件的。

其实很容易想到去枚举\(j\)。

我们用\(idx\)数组存每一种数的下标。对于数\(i\)有\(idx[i].size()\)个。我们去\(for\)每一个。

对于\(idx[i][j-1]\)到\(idx[i][j]\)之间有\(d = idx[i][j]-idx[i][j-1]-1\)个数(都不等于\(i\))，在这一些数的左边有\(j\)个\(i\)（vector下标从0开始的所以是j），右边有\(sz-j\)个\(i\)，这些\(i\)和这\(d\)个数都能构成三元组，方案数是\(j*d*(sz-j)\)

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 3e5 + 10;
vector<int>idx[N];
ll a[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin>>n;
    for(int i = 1;i <= n; i++)
        cin>>a[i],idx[a[i]].push_back(i);
    ll ans = 0;
    for(int i = 1;i <= n; i++)
    {
        int sz = idx[i].size();
        for(ll j = 1;j < sz; j++)
        {
            ans += j*(idx[i][j]-idx[i][j-1]-1)*(sz-j);
        }
    }
    cout<<ans<<"\n";

    return 0;
}

方法二：扫描线思想

该部分引用自

我们以\(k\)为扫描线，统计在\(k\)左侧的满足条件的三元组。

我们用\(idx\)维护每种数的下标。

图1

我们令当前扫描线位置是\(t\)，所有在\(t\)左侧且与\(t\)相同的元素的下标是\(idx_i\)。那么除了这些元素其他的元素一定和\(a_t\)不一样。我们统计每个\(idx_i\)到\(t\)之间的贡献：长度-一样的

\(idx_1\)的贡献：\(t-idx_1-1-2\)

\(idx_2\)的贡献：\(t-idx_2-1-1\)

\(idx_3\)的贡献：\(t-idx_1-1-0\)

\(...\)

\(idx_i\)的贡献：\(t-idx_i-1-(m-i)\)(其中m为i的最大编号)

总贡献就是：\(m\times t - \sum_{i = 1}^{m}idx_i-m-\dfrac{(m-1)m}{2} = m(t-1)-\dfrac{(m-1)m}{2}-\sum_{i = 1}^{m}idx_i\)

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 3e5 + 10;
ll a[N],sumidx[N],cntidx[N];

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin>>n;
    set<int>s;
    for(int i = 1; i <= n; i++)
        cin>>a[i];
    ll ans = 0;
    for(ll i = 1;i <= n; i++)
    {
        ans += cntidx[a[i]]*(i-1)-sumidx[a[i]]-(cntidx[a[i]]-1)*cntidx[a[i]]/2;
        cntidx[a[i]]++;
        sumidx[a[i]]+=i;
    }
    cout<<ans<<"\n";
    return 0;
}