线段覆盖

贡献法 $map$

分析

需要好好练习贡献法了，首先题目问的是覆盖 $k$ 条线段的点的数量，因此就要求出这 $n$ 个点组成的线段造出多少个点，对于第 $i$ 个点，其左边有 $i$ 个线段，其右边有 $(n-i-1)$ 个线段，左右相乘刚好是线段的条数，对于 $a_{i},a_{i-1}$ 刚好有 $i*(n-i)$ 条线段覆盖了 $a_{i}-a_{i-1}$个点。

#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve()
{
    int n,q;
    cin>>n>>q;
    vector<int>a(n);
    for(int &x:a)cin>>x;
    map<int,int>mp;
    for(int i=0;i<n;i++)
    {
        mp[i*(n-i-1)+n-1]++;
        if(i)mp[i*(n-i)]+=a[i]-a[i-1]-1;
    } 
    while(q--)
    {
        int k;
        cin>>k;
        cout<<mp[k]<<' ';
    }
    cout<<endl;
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

牌堆分配

贪心

分析

牌堆大小范围就在 $[1,n]$，那么枚举大小看是否符合即可，不重复那就是最多数量的牌至少需要相应数量的牌堆，总牌数去除枚举的大小即为牌堆的数量，以牌数来作为比较标准，找最大可能的牌堆大小。

代码

//题意：n张卡片数量，k个可购卡片，问最大size 
//牌堆大小[1,n]
    //形成大小i的牌堆，总的卡片需要
    //maxn是最多数量的卡片，要不重复的话需要分散到i个牌堆中
    //所以至少需要maxn个牌堆保证牌堆内是1个，maxn是数量，那乘以大小，不就是总卡片数量吗
    //所以i*maxn是总卡片数
    //总的卡片数sum/i，是将卡片分成i大小，可以分成的牌堆数量，再乘上牌堆大小那么就是总卡片数量
    //(sum+i-1)/i是sum/i向上取整
    //直接从宏观本质去考虑，而不是局部的是否重复 
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl '\n'
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
void solve()
{
    int n,k;
    cin>>n>>k;
    vector<int>a(n+1);
    int maxn=0,sum=0;
    rep(i,1,n)
    {
        cin>>a[i];
        maxn=max(maxn,a[i]);
        sum+=a[i];
    }
    int ans=-1;
    rep(i,1,n)
    {
     int res=max(maxn*i,(sum+i-1)/i*i);
     if(res<=k+sum)ans=max(ans,i);  
    }
    cout<<ans<<endl;
}
signed main()
{
    ios
    int t;  
    cin>>t;
    while(t--)solve();
    return 0;
}

城市征服

差分

分析

更新初始不可占领位置部分的思路还是不懂

代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); 
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
typedef pair<int,int>P;
const int N=2e5+10;
int n,a[N],c[N],ans,id[N],s[N];
void work(int a,int b)
{
    a=max(a,1ll);
    b=min(b,n);
    if(a<=b)
    {
        c[a]++;
        c[b+1]--;
    }
}
bool cmp(int x,int y)
{
    return x-a[x]+1<y-a[y]+1;
}
void init()
{
    memset(c,0,sizeof c);
    memset(s,0,sizeof s);
    ans=0;
}
void solve()
{
    int n;
    cin>>n;
    init();
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        work(1,i-a[i]);
        work(i+a[i],n);
        id[i]=i;
    }
    sort(id+1,id+n+1,cmp);
    int nw=1;
    for(int i=1;i<=n;i++)
    {
        while(nw<=n&&nw<id[i]-a[id[i]]+1)
        {
            int st=nw+a[nw];
            for(;st<=n;st++)
            {
                if(s[st])break;
                s[st]=nw; 
            }
            nw++;
        }
        if(s[id[i]])
        work(s[id[i]],id[i]);
    }
    for(int i=2;i<=n;i++)
    c[i]+=c[i-1];
    for(int i=1;i<=n;i++)
    if(!c[i])ans++;
    cout<<ans<<endl;
}
signed main()
{
    ios
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}
//nw是初始位置
//将城市按照i-(ai-1)左边界排序
//st是从起始位置nw开始到征服nw最晚时间所能走的最远距离就是nw+a[nw]
//利用差分和前缀和处理出来不可作为起始点的城市