牛客小白月赛61题解-创新互联

这个代码以我现在一个cf绿名的码力写不出来，估摸着起码得蓝名才能写出这。这个代码是出题人的，但是注释是我自己加的，让我写我写不出来，等我上了蓝名再回来自己写一遍。

#includeusing namespace std;
typedef long long ll;
const int M = 1e5+5;
const ll linf = 0x3f3f3f3f3f3f3f3f;
//即4557430888798830600，4.557×10^18
//long long大9223372036854775807，9.223×10^18
int n, ec, et, p; ll s;
int t[M];
void work()
{scanf("%d %d %d %d %lld", &n, &ec, &et, &p, &s);
	for (int i = 1; i<= n; ++i) scanf("%d", &t[i]);
	if (s< ec) {printf("-1\n");return;}
	//如果初始金额小于造一名工程师的金额，就不可能实现
	//那么下面的就是一开始的钱至少够造一个工程师
	queueq; //存储工程师占领油田的时间
	ll cur_time = 0;//当前时间为0
	for (int i = 1, oil_cnt = 0; i<= n; ++i) {//第i个油田，占领油田数一开始为0
	    ll next_time;//下一次可以开始训练工程师的最小时间点
		if(i==1)next_time=0;//如果从第1个油田算起，那就是现在就可以开始训练
		else next_time=cur_time+et;//如果不是第一个油田，那就是当前时间点+et秒训练时间
		//当前工程师占领油田的时间点，在下一次可以开始训练工程师的最小时间点及以前
		while (!q.empty() && q.front()<= next_time) {//计算从当前到next_time的金额收益
		    //如果金额没爆long long,才接着收钱，否则就不收了，不然爆了没法存
			//虽然linf不是long long大值，但大于这个值再存金币也没有意义
			//之所以不设置long long大值，还是为了大得适当，防止意外溢出
			if(s< linf) s += oil_cnt * (q.front() - cur_time) * p;
			//当前的油田数乘p金额是一秒的；
			//经历的时间是下一名工程师占领油田的时间点-当前工程师占领油田的时间点
			//因为在这一段时间油田数是固定的
			cur_time = q.front();//更新当前工程师占领油田的时间点
			q.pop();//因为已经用了，所以弹出队列
			oil_cnt++;//占领的油田数加1，因为更新一次当前时间，就被占领一个油田
		}
		if (cur_time< next_time) {	//如果当前工程师占领油田的时间点，小于可以训练下一名工程师的最小时间点
			if(s< linf) s += oil_cnt * (next_time - cur_time) * p;
			//当前的油田数乘p金额是一秒的；
			//经历的时间是可以训练下一名工程师的最小时间点-当前工程师占领油田的时间点
			cur_time = next_time;//更新当前时间点为可以训练下一名工程师的最小时间点
		}
		if (s< ec) {	//如果当前金额不足以训练一名工程师
			while (!q.empty() && s + oil_cnt * (q.front() - cur_time) * p< ec) {		//如果当前工程师占领油田时，金额不足以训练下一名工程师
				s += oil_cnt * (q.front() - cur_time) * p;//先把这段时间的钱加上
				cur_time = q.front();//先更新当前时间
				q.pop();//当前工程师占领油田的时间点已经用过了，因此弹出队列
				oil_cnt++;//占领的油田数加1
			}
			//金额不足，需要等待
			ll wait_time = (ec - s + (ll)oil_cnt * p - 1) / (oil_cnt * p);
			//需要等待wait_time的时间
			//还需要金额ec-s，
			s += oil_cnt * wait_time * p;//加上等待时间内生产的钱
			cur_time += wait_time;//更新当前时间
		}
		s -= ec;//更新当前金额
		q.push(cur_time + et + t[i]);//工程师占领油田的时间点等于
		//当前时间点+et秒训练时间+工程师去油田的时间
		//注意，每次循环结束后才加入队列
		//因此最后一次循环的cur_time+et+t[n]就是答案
	}
	printf("%lld\n", cur_time + et + t[n]);
}
int main()
{work();
	return 0;
}

就是分三类，正序数，负序数，零序数。有对称性知正序数和负序数数量相同，那么求出全排列，再减去零序数的数量，最后除2就是逆序数的数量。

零序数的数量用排列组合求。

#includeusing namespace std;
typedef unsigned long long ll;
const int N=1e5+10;
const ll mod=1e9+7;
ll cnt[N],a[N],j[N];
ll js(ll x){if(x!=0){return x*(x-1)/2;
	}
	return 0;
}
int main()
{ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	ll n;cin>>n;
	for(int i=0;icin>>a[i];
		cnt[a[i]]++;
	}
	ll sum=n*(n-1)/2;
	for(int i=0;isum-=js(cnt[i]);
	}
	sum%=mod;
	for(int i=3;i<=n;i++)
	{sum*=i;
		sum%=mod;
	}
	if(n==1)sum/=2;
	cout<

#includeusing namespace std;
#define int long long
const int maxn=1e5+5;
const int mod=1e9+7;
int n,m;
vectorv[maxn];
int cnt[maxn],deta[maxn],fac[maxn];
void add(int id, int &now){for(auto u:v[id]){cnt[u]++;
        if(cnt[u]==1)now++;
    }
}
void del(int id, int &now){for(auto u:v[id]){cnt[u]--;
        if(cnt[u]==0)now--;
    }
}
signed main(){cin>>n>>m;
    for(int i=1;i<=3;i++){for(int j=1;j<=m;j++){int u;
            cin>>u;
            v[u].push_back(j);
        }
    }
    int now=0;
    memset(deta,0,sizeof(deta));
    for(int i=1,j=1;i<=n;i++){while(j<=n&&nowint L=(j-1)-i+1;
            int R=n-i+1;
            deta[L]++;
            deta[R+1]--;
        }
        del(i,now);
        if(i==j)j++;
    }
    fac[0]=fac[1]=1;
    for(int i=2;i<=n;i++){fac[i]=fac[i-1]*i%mod;
    }
    for(int i=1;i<=n;i++){deta[i]=deta[i]+deta[i-1]%mod;
        cout<