T1准确率
【题目描述】
你是一个骁勇善战、日刷百题的OIer. 今天你已经在你OJ 上提交了y 次，其中x次是正确的，这时，你的准确率是x/y.
然而，你最喜欢一个在[0; 1] 中的有理数p/q（是一个既约分数），所以你希望再进行若干次提交，使你的准确率变为p/q. 当然，由于你的实力很强，你可以随意决定进行多少次正确的提交和多少次错误的提交. 同时，你不希望把一天的时间都用在提交上，所以你想求出最少还要进行多少次提交（包括正确的和错误的），才能达到这一目标.
注意：本题中，0/1 和1/1 都是既约分数.
【输入格式】
从文件rate.in 中读入数据。
输入第一行包含一个正整数t (t <= 5 * 10 ^ 5)，表示数据组数.
接下来t 行，每行4 个整数x, y, p, q (0 <= x <= y <= 10 ^ 9; 0 <= p <= q <= 10 ^ 9; y > 0; q > 0)，含义如题所述.
【输出格式】
输出到文件rate.out 中。
输出t 行，每行一个整数，表示使正确率达到p/q 所需最小提交次数；若无法达到，输出-1.
【样例1 输入】
4
3 10 1 2
7 14 3 8
20 70 2 7
5 6 1 1
【样例1 输出】
4
10
0
-1
【样例1 解释】
第一组数据中，你需要进行4 次正确的提交，使准确率达到7/14，即1/2；
第二组数据中，你需要进行2 次正确的提交，8 次错误的提交，使准确率变为9/24，即3/8；
第三组数据中，你无需进行任何提交，因为你的准确率已为20/70，即2/7；
第四组数据中，在原有的提交中已有一次错误提交，准确率不可能达到1.
【样例2】
见选手目录下的rate/rate2.in 与rate/rate2.ans。
【子任务】
对于30% 的数据，t = 1；
对于另30% 的数据，t <= 1000.
以上两部分数据中，各有50% 的数据保证x, y, p, q <= 10 ^ 4.
题意很明了，然后别想偏了……
首先不要把x, y约分要不然答案肯定不对，这是挺显然的。
然后不要把这题想成数论的不定方程，虽然设完正确提交和错误提交后化简一下确实很像不定方程，然而会有负数，而且这块我有些地方还是不太懂，所以肯定不是这个做法……
实际上，这不过是一道初中不等式，只要将p, q同时扩大n倍后，满足n * p >= x && n * q >= y就行了。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter printf("\n")
#define space printf(" ")
#define Mem(a) memset(a, 0, sizeof(a))
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const int eps = 1e-;
//const int maxn = ;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch))
{
ans = ans * + ch - ''; ch = getchar();
}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) x = -x, putchar('-');
if(x >= ) write(x / );
putchar(x % + '');
} int t; int main() //代码就这么短……
{
freopen("rate.in", "r", stdin);
freopen("rate.out", "w", stdout);
t = read();
while(t--)
{
ll a = read(), b = read(), p = read(), q = read();
if(p == q) printf("%s\n", x == y ? "" : "-1");
else if(p == ) printf("%s\n", x == ? "" : "-1");
else
{
ll n = max((x - ) / p, (y - x - ) / (q - p)) + ;
write(n * q - y); enter;
}
}
return ;
}
T2 模拟赛
【题目描述】
你很快地完成了所有的题目，并且使准确率达到了p/q，于是开始无所事事. 老师看见了，对你说：“你今天做的题够多的了，别再做了. 我们接下来k 天每天都要模拟，我这里有很多题，你去选一些题目编k 场模拟赛吧. ”老师将所有题目都编了序号，还给你了n 种出题方案（所有方案两两不同）. 每种出题方案选择所有编号属于[l; r] 的题目，作为一天的试题. 现在，你需要选出k 种出题方案（一个方案只能选取一次），分别对应k 天的模拟赛. 老师非常强调复习的重要性，因此希望有一些题目每天都出现在模拟赛当中，你需要最大化每天都出现的题目的数量.
【输入格式】
从文件exam.in 中读入数据。
输入第一行包含两个正整数n; k (1 <= k <= n <= 3 * 10 ^ 5)，分别为出题方案数和模拟赛天数.
接下来n 行，每行两个整数l; r (-10 ^ 9 <= l <= r <= 10 ^ 9)，表示一个出题方案（保证所有方案两两不同）.
【输出格式】
输出到文件exam.out 中。
输出一个非负整数，表示每天都出现的题目的数量的最大值.
【样例1 输入】
4 2
1 100
40 70
120 130
125 180
【样例1 输出】
31
【样例1 解释】
选择前两种方案，编号为[40; 70] 的题目在两种方案中均出现，共有31 道题.
【样例2 输入】
3 2
1 12
15 20
25 30
【样例2 输出】
0
【样例2 解释】
所有给出的方案互不相交，所以答案为0.
【子任务】
对10% 的数据，k = n；
对另20% 的数据，k = 2；
对另20% 的数据，1 <= k <= n <= 20；
其余5 组数据，n = 10 ^ 2, 10 ^ 3, 10 ^ 4, 10 ^ 5, 3 * 10 ^ 5.
简单来说，就是让你从给定的n个区间中找出k个区间，使这k个区间的公共部分长度最大。
很容易想到，在所选的区间中，公共部分的长度是由最大的左端点的和最小的右端点控制的。那么如果我们先把所有区间按左端点排序，然后枚举左端点，那么控制公共区间长度的就是当前的左端点和最小的右端点。因此我们只要想办法维护所选区间的右端点就行了。
O(n ^ 2)的做法是，对于每一个区间，从左端点比他小的区间中选出右端点最大的 k-1 个区间，其中右端点第k-1大的就是当前公共区间的右端点。
然后我们就可以用一个堆优化选取这个右端点的过程，把所选的区间的右端点都放到小根堆里，当堆中元素大于k个或是根的右端点比当前左端点小，就删除根，然后当枚举到第i个区间时的答案就是 q.top() - a[i].L +1，并尝试用这个更新答案。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<set>
using namespace std;
#define enter printf("\n")
#define space printf(" ")
#define Mem(a) memset(a, 0, sizeof(a))
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const int eps = 1e-;
const int maxn = 3e5 + ;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch))
{
ans = ans * + ch - ''; ch = getchar();
}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) x = -x, putchar('-');
if(x >= ) write(x / );
putchar(x % + '');
} int n, k;
struct Node
{
int L, R;
bool operator < (const Node& other)const
{
return L < other.L || (L == other.L && R < other.R);
}
}a[maxn]; struct QUE //忘了优先队列的小根堆写法……
{
int l;
bool operator < (const QUE& other)const
{
return l > other.l;
}
};
priority_queue<QUE> q;
int cnt = , ans = ; int main()
{
freopen("exam.in", "r", stdin);
freopen("exam.out", "w", stdout);
n = read(); k = read();
for(int i = ; i <= n; ++i) {a[i].L = read(); a[i].R = read();}
sort(a + , a + n + );
for(int i = ; i <= n; ++i)
{
q.push((QUE){a[i].R}); cnt++;
if(cnt > k) {q.pop(); cnt--;}
while(!q.empty() && a[i].L > q.top().l) {q.pop(); cnt--;}
if(cnt == k) ans = max(ans, q.top().l - a[i].L + );
}
write(ans); enter;
return ;
}
T3还不会呀……（小声）