B 君的任务(task)
【题目描述】
与君初相识，犹如故人归。
B 君看到了Z 君的第一题，觉得很难。
于是自己出了一个简单题。
你需要完成n 个任务，第i 任务有2 个属性ai; bi。其中ai 是完成这
个任务所需要花费的时间，bi 为如果你在t 时间完成该任务，那么你受到的
损失便是bit。
初始时间是0，你最终收到的损失等于每个任务造成的损失之和，你需
要最小化自己受到的损失。
你只能一个任务接着一个任务的完成，不能同时做多个任务，所以说相
当于你只需要决定一个任务完成的顺序。
【输入格式】
第一行一个整数n。
以下n 行，每行两个整数ai; bi。
【输出格式】
一行一个整数表示答案。
【样例输入】
4
1 4
2 3
3 2
4 1
【样例输出】
35
【数据规模与约定】
对于100% 的数据，满足1 n 105; 0 ai 103; 0 bi 103。
对于30% 的数据，满足1 n 10。
对于70% 的数据，满足1 n 103。
数据没有梯度。
【题解】
国王游戏弱化版。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm> inline void read(long long &x)
{
x = ;char ch = getchar(), c = ch;
while(ch < '' || ch > '') c = ch, ch = getchar();
while(ch <= '' && ch >= '') x = x * + ch - '', ch = getchar();
if(c == '-')x = -x;
} const long long INF = 0x3f3f3f3f;
const long long MAXN = + ; struct Node
{
long long a,b;
Node(long long _a, long long _b){a = _a;b = _b;}
Node(){}
}node[MAXN]; long long cmp(Node t1, Node t2)
{
return t1.a * t2.b < t2.a * t1.b;
} long long n;
long long T, ans; int main()
{
read(n);
for(register long long i = ;i <= n;++ i)
read(node[i].a), read(node[i].b);
std::sort(node + , node + + n, cmp);
for(register long long i = ;i <= n;++ i)
{
T += node[i].a;
ans += T * node[i].b;
}
printf("%lld", ans);
return ;
}
T1
B 君的病症(ocd)
【题目描述】
享国之日浅，国家无事。
B 君看到了Z 君的第二题，觉得很难。
于是自己出了一个简单题。
大A 是一名强迫症患者，现在他要给一群带颜色的珠子排成一列，现
在有n 种颜色，其中第i 种颜色的珠子有ai 个。要求排列中第i 种颜色
珠子的所有珠子，一定要排在第i + 1 种颜色的第一个和最后一个珠子之
间。问有多少种排列珠子的方案，因为方案数会很大，所以请输出答案对
1000000007 取模之后的结果。
【输入格式】
第一行一个整数n。
以下n 行，每行一个整数ai。
【输出格式】
一行一个整数表示答案。
【样例输入】
【样例输出】
【数据规模与约定】
对于100% 的数据，满足1 n 104; 2 ai 15。
对于70% 的数据，满足1 n 102。
【题解】
会了上次模拟的那个这个也会，详见上一篇NOIP模拟博客
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm> inline void read(long long &x)
{
x = ;char ch = getchar(), c = ch;
while(ch < '' || ch > '') c = ch, ch = getchar();
while(ch <= '' && ch >= '') x = x * + ch - '', ch = getchar();
if(c == '-')x = -x;
} const long long INF = 0x3f3f3f3f;
const long long MAXN = + ;
const long long MOD = ; long long n,num[MAXN],sum[MAXN],f[MAXN]; long long pow(long long a, long long b)
{
long long r = , base = a%MOD;
for(;b;b >>= )
{
if(b & )r *= base, r %= MOD;
base *= base, base %= MOD;
}
return r;
} long long ni(long long a)
{
return pow(a, MOD - );
} long long C(long long n, long long m)
{
return f[n] * ni(f[n - m])%MOD * ni(f[m])%MOD;
} int main()
{
read(n);
for(register long long i = ;i <= n;++ i)
read(num[i]), sum[i] = sum[i - ] + num[i];
f[] = ;
for(register long long i = ;i <= MAXN;++ i)
f[i] = f[i - ] * i % MOD;
long long ans = ;
for(register long long i = ;i <= n;++ i)
ans = ans * C(sum[i] - , num[i] - ) % MOD;
printf("%lld", ans);
return ;
}
T2
B 君的方差(variance)
【题目描述】
相逢是问候，分手是祝愿。
B 君看到了Z 君的第三题，觉得很难。
于是自己出了一个简单题。
有一个长度为n 的数组faig，下标从1 开始。你需要支持2 种操作。
1. 1 x y，将第x 个元素修改为y。
2. 2 l r，询问下标l 到r 之间所有数的方差，因为方差可能不是整数，
所以输出时请乘(r