Educational Codeforces Round 131 (Rated for Div. 2)（A-D，F）（思路解释超详细，代码也有详细注释）

题目可以直接去cf上搜，不再赘述

E暂时还没补题，要是补了就更新

AB直接上代码了，有问题可以在评论里问

A

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include
using namespace std;
#define int long long
#define ll long long
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define per(a,b,c) for(int a=b;a>=c;a--)
const int maxn=1e6+10;
const int maxm=1e3+10;
    int a[maxn],b[maxn];
    int f[maxm][maxm];

signed main(void)
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);

    int t;cin>>t;
    while(t--)
    {
        int sum=0;
        for(int i=1;i<=4;i++)
        {
            int x;cin>>x;sum+=x;
        }
        if(sum==0)cout<<0< 
B
 
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include
using namespace std;
#define int long long
#define ll long long
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define per(a,b,c) for(int a=b;a>=c;a--)
const int maxn=1e6+10;
const int maxm=1e3+10;
    int a[maxn],b[maxn];
    int f[maxm][maxm];
    int vis[maxn];
signed main(void)
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;


            cout<<2<>n;rep(i,1,n)cin>>a[i];


}
 
C题解
 
1.二分答案，对所需的时间进行二分，设该时间间隔为k。
 
2.check部分，探索在k时间内，工人能完成的最大工作总量是否能达到或者超过任务量m。
 
求工人能完成的最大工作总量，就是求每个工人能完成的最大工作量，并加起来。
 
求每个工人能完成的最大工作量，就是先完成擅长的（因为耗时少），再完成不擅长的（如果还有剩余时间的话）。
 
代码：
 
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include 

using namespace std;
#define int long long
#define ll long long
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define per(a,b,c) for(int a=b;a>=c;a--)


using namespace std;

int t[200010];
map mp;
int n, m;
int check(int k){
	int res = 0;//工人能做的最大工作量
	rep(i,1,n){//遍历第1到n工人
		int y = mp[i];//每个工人擅长的工作有多少种
		res += min(k, y);//要么只能花k时间，要么把擅长的工作全做完
		res += max(0ll, k - y) / 2;//要么没时间做不擅长的了，要么在余下的时间内把不擅长的工作给做了。
	}
	if(res >= m)return 1;//工人能做的工作量可以比任务量还要大
	else return 0;
}
void solve(){
	cin >> n >> m;
	for(int i = 1;i <= m;i++){//i表示对应的第i个任务
		cin >> t[i];//第t[i]个工人擅长第i个任务
		mp[t[i]]++;//第t[i]个工人擅长的任务量
	}
	int l = 1, r = 1000000;
	while(l < r){
		int mid = (l + r) >> 1;
		if(check(mid)){//符合条件要取到
			r = mid;
		}
		else{
			l = mid + 1;
		}
	}
	cout << l << "n";
}



signed main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;cin>>t;
    while(t--)
    {
        mp.clear();//千万别忘记清空
        //这边mp清空可以放solve里，单拎出来是想强调一下
        solve();
    }
}
 
D题解
 
思路：
 
对每个i，求出a[i]的范围，用[l,r]表示。
 
注意：最终的答案a[i]只能从1到n里选，而且每个数能且仅能出现一次，而且一定有一种或多种答案。
 
那就对每个区间按从左到右的顺序排好，依次插入1~n。
 
本来想法很简单，以l为第一关键词，r为第二关键词，都从小到大排序。
 
因为我当时只想到这个例子，要插入3的时候，对于区间[3,5]和[3,10]先用哪个，显然先用[3,5]好。
 
但其实并不是这样。
 
举个例子，要插入3的时候，现在还没用，且能放4的区间只有[3,6]和[4,4]，显然要先用[4,4]。
 
那么这里的l其实顺序颠倒了。
 
解决方法就是，先以l为关键词进行排序，然后要插入3的时候，把l为3的r全放到优先队列（r从小到大排序），把r最小的用掉，然后要插入4的时候，把l为4的全放入优先队列，还是r从小到大排序，把最差的区间（即r最小的区间先用掉），因为4的左边已经不需要插入了，所以相当于这么多区间的左边都废掉了，起跑线同步，都为4，然后比优劣，区分出好坏。
 
对区间排序前的i角标是保留的，是和l，r一起封装起来的，然后我们记录对应的第i个区间要插入的数即可。
 
代码：
 
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include
using namespace std;
#define int long long
int n;
typedef pairPII;
typedef tuplettt;
priority_queue,decltype(&cmp)>segs(cmp);
int res[500010];//存储第i个区间（i为输入的顺序）要插入的数
//索引的思想
bool cmp(ttt a,ttt b)
{
    int l1,r1,i1; int l2,r2,i2;
    tie(l1,r1,i1)=a;tie(l2,r2,i2)=b;
    //if(l1==l2)return r1>r2;
    //关于这行为什么注释掉了
    //本以为按l作为第一关键词，按r作为第二关键词，都从小到大排序
    //是可以成功的
    //但当存在区间例如[3,6],[4,4]，且需要插入4的时候，是要[4,5]先来的
    return l1>l2;//优先队列要从小到大排序的话，cmp得写大于号
}

signed main(void)
{
    cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
    int t;cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            int x;cin>>x;
            int l,r;
            if(x==0){l=i+1,r=n;}
            else {l=i/(x+1)+1,r=i/x;}
            //取出a[i]的范围，把l,r,i放入优先队列
            //把i也放入是因为到时需要做个索引
            segs.push({l,r,i});
        }
        priority_queue,greater>q;
        for(int i=1;i<=n;i++)
        {
            while(!segs.empty())
            {
                int l,r,j;
                tie(l,r,j)=segs.top();
                if(l!=i)break;
                //当l==r时，把r压入优先队列
                q.push({r,j});
                segs.pop();
            }
            auto t=q.top();
            q.pop();
            res[t.second]=i;
        }
        for(int i=1;i<=n;++i)
            printf("%d ",res[i]);
        printf("n");
    }
}
 
F
 
F题思路是看知乎严格鸽博主的题解，然后按自己的线段树模板写了一下
 
#include
using namespace std;
#define ri int
#define INF ((1<<31)-1)
#define inf (-1<<31)
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define pb push_back
#define PII pair
#define ff first
#define ss second
#define int long long
typedef double db;
typedef long long ll;
typedef long long LL;
typedef unsigned long long ull;
const int mod=1000000007;
const int N =2e5+10;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
//head
template inline void read(T& t)
{
    ri rc = getchar(); t = 0;
	ri rf=1;
    while (!isdigit(rc))
	{
		if(rc=='-')rf=-1;
		rc = getchar();
	}
    while (isdigit(rc))t = t * 10 + rc - 48, rc = getchar();
	t*=rf;
}
template  inline void read(T& t, Args&... args)
{
    read(t); read(args...);
}
template < typename T > inline void write ( T x )
{
    if ( x < 0 ) x = -x, putchar ( '-' );
    if ( x > 9 ) write ( x / 10 );
    putchar ( x % 10 + 48 );
}
template  inline void write(T x, Args&... args)
{
    write(x);putchar(' ');write(args...);
}
//speed
#define lr u<<1
#define rr u<<1|1
int n,d;
struct Node
{
    int l, r;
    int cnt,val;
    int lazy;
    // TODO: 需要维护的信息和懒标记
}tr[N * 4];

inline void pushup(int u)
{
    //tr[u].l=tr[lr].l;
    //tr[u].r=tr[rr].r;
    tr[u].cnt=tr[lr].cnt+tr[rr].cnt;
    tr[u].val=tr[lr].val+tr[rr].val;
    // TODO: 利用左右儿子信息维护当前节点的信息
}

inline void pushdown(int u)
{
    if(tr[u].lazy)
    {
        tr[lr].lazy+=tr[u].lazy;
        tr[rr].lazy+=tr[u].lazy;
        tr[lr].val+=tr[u].lazy*tr[lr].cnt;
        tr[rr].val+=tr[u].lazy*tr[rr].cnt;
    }
    tr[u].lazy=0;
    // TODO: 将懒标记下传
    //同时更新其他属性
    //要把root的懒标记清除
}

void build(int u, int l, int r)
{
    tr[u]={l,r};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

void update(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].lazy+=d;
        tr[u].val+=d*tr[u].cnt;
        // TODO: 修改区间
    }
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) update(u << 1, l, r, d);
        if (r > mid) update(u << 1 | 1, l, r, d);
        pushup(u);
    }
}
void modify(int u, int x, int cnt,int val)
{
    if (tr[u].l == x && tr[u].r == x) {
        tr[u].cnt = cnt;
        tr[u].val = val;
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        pushdown(u);
        if (x <= mid) modify(u << 1, x, cnt,val);
        else modify(u << 1 | 1, x, cnt,val);
        pushup(u);
    }
}
int query(int u, int l, int r)//cnt
{
    if(tr[u].rr)return 0;
    if (tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].cnt;  // TODO 需要补充返回值
    }
    int res=0;
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid)res+=query(lr,l,r);
    if(r>mid)res+=query(rr,l,r);
    return res;
}
int query2(int u, int l, int r)
{
    if(tr[u].rr)return 0;
    if (tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].val;  // TODO 需要补充返回值
    }
    else
    {
        pushdown(u);
        int res=0;
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid)res+=query2(lr,l,r);
        if(r>mid)res+=query2(rr,l,r);
        return res;
    }
}
bool vis[N];
signed main()
{
    read(n,d);
    int res=0;
    build(1,1,2e5);
    while(n--)
    {
        int x;read(x);
        if(!vis[x])
        {
            vis[x]=1;
            int cl=query(1,max(1ll,x-d),x-1);
            res+=cl*(cl-1)/2;
            int cr=query(1,x+1,min(200000ll,x+d));
            res+=cr*(cr-1)/2;
            res+=query2(1,max(1ll,x-d),x-1)-query(1,max(1ll,x-d),x-1)*query(1,1,x);
            update(1,max(1ll,x-d),200000ll,1);
            modify(1,x,1,query(1,1,min(200000ll,x+d))+1);
        }
        else {
            vis[x]=0;
            int cl=query(1,max(1ll,x-d),x-1);
            res-=cl*(cl-1)/2;
            int cr=query(1,x+1,min(200000ll,x+d));
            res-=cr*(cr-1)/2;
            res-=query2(1,max(1ll,x-d),x-1)-query(1,max(1ll,x-d),x-1)*query(1,1,x);
            update(1,max(1ll,x-d),200000ll,-1);
            modify(1,x,0,0);
        }
        write(res);
        puts("");
    }
}