P.S:这场不想补啦。
F.Final Exam
题意：
有(n)门课即将进行考试，现在有(m)分用于分配，如果一门课程的分值为(x)，那么那就需要(x+1)个小时来复习。
现在你的目标是过(k)门课，问怎么分配复习时间可以保证过(k)门课并且复习时间最少。
P.S：老师可以根据你的复习时间来针对你。
思路：
令人自闭的一道题...
- 老师十分真实地不考你复习最多的(k-1)门课程，转而把分分配给其余的(n-k+1)门课程；
- 你清晰认识到了这一点，并且制定对策：复习最少的(n-k+1)门课程分配(m+1)小时，想着就能逃过一劫；
- 老师现在也拿你没办法了，你赢了。
- 但最少时间为多少？
- 肯定我这(n-k+1)门课程平均分配可以使得最大值最小，机智的你一算，最大复习时间为(frac{m}{n-k+1}+1)即可。
- 所以答案为((k-1)(frac{m}{n-k+1}+1)+m-1)。
老师来田忌赛马，幸好你有足够的时间...
Code
Please write it by yourself.
J.Just Repeat
题意：
两个人玩博弈游戏。
现在每个人手中都有一些有颜色的牌，两个人依次轮流打出一张牌，但不能打出已经被对手打出来了的颜色的牌。
问最终谁会获胜。
思路：
一个人打出一张牌过后另一个人就不能用这种颜色的牌，等价于另一个人依旧可以用，但我们多出了一些牌。
所以按(cnt1[i]+cnt2[i])排序，之后模拟这个过程即可。
Code
#include <bits/stdc++.h>
#define MP make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
int T, n, m, p;
ull k1, k2;
ull rng() {
ull k3 = k1, k4 = k2;
k1 = k4;
k3 ^= k3 << 23;
k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
return k2 + k4;
}
int a[N], b[N], c[N];
int cnta[N], cntb[N];
pii d[N];
int resa, resb, mod;
void Hash() {
c[0] = 0;
for(int i = 1; i <= n; i++) c[++c[0]] = a[i];
for(int i = 1; i <= m; i++) c[++c[0]] = b[i];
sort(c + 1, c + c[0] + 1);
c[0] = unique(c + 1, c + c[0] + 1) - c - 1;
for(int i = 1; i <= c[0]; i++) cnta[i] = cntb[i] = 0;
for(int i = 1; i <= n; i++) a[i] = lower_bound(c + 1, c + c[0] + 1, a[i]) - c, cnta[a[i]]++;
for(int i = 1; i <= m; i++) b[i] = lower_bound(c + 1, c + c[0] + 1, b[i]) - c, cntb[b[i]]++;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> T;
while(T--) {
cin >> n >> m >> p;
if(p == 1) {
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= m; i++) cin >> b[i];
} else {
cin >> k1 >> k2 >> mod;
for(int i = 1; i <= n; i++) a[i] = rng() % mod;
cin >> k1 >> k2 >> mod;
for(int i = 1; i <= m; i++) b[i] = rng() % mod;
}
Hash();
int tot = 0;
for(int i = 1; i <= c[0]; i++) {
if(cnta[i] && cntb[i]) {
d[++tot] = MP(cnta[i] + cntb[i], cnta[i]);
}
}
sort(d + 1 , d + tot + 1);
int cur = 1; resa = n, resb = m;
for(int i = tot; i; i--) {
if(cur & 1) {
resa--, resb -= d[i].first - d[i].second;
} else {
resb--, resa -= d[i].second;
}
cur ^= 1;
}
if(cur) {
if(resa > resb) cout << "Cuber QQ" << '
';
else cout << "Quber CC" << '
';
} else {
if(resb > resa) cout << "Quber CC" << '
';
else cout << "Cuber QQ" << '
';
}
}
return 0;
}
K.Kejin Player
挺套路的一个期望递推题。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 500005, MOD = 1e9 + 7;
struct Istream {
template <class T>
Istream &operator >>(T &x) {
static char ch;static bool neg;
for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
x=neg?-x:x;
return *this;
}
}fin;
struct Ostream {
template <class T>
Ostream &operator <<(T x) {
x<0 && (putchar('-'),x=-x);
static char stack[233];static int top;
for(top=0;x;stack[++top]=x%10+'0',x/=10);
for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
return *this;
}
Ostream &operator <<(char ch) {
putchar(ch);
return *this;
}
}fout;
int T, n, q;
ll sum[N];
ll qp(ll a, ll b) {
ll ans = 1;
while(b) {
if(b & 1) ans = ans * a % MOD;
a = a * a % MOD ;
b >>= 1;
}
return ans;
}
int main() {
// ios::sync_with_stdio(false); cin.tie(0);
fin >> T;
while(T--) {
fin >> n >> q;
for(int i = 1; i <= n; i++) {
ll r, s, x, a;
fin >> r >> s >> x >> a;
ll p = r * qp(s, MOD - 2) % MOD;
ll ans = (a * qp(p, MOD - 2) % MOD + ((1 - p) * qp(p, MOD - 2) % MOD * (sum[i - 1] - sum[x - 1]) % MOD + MOD) % MOD) % MOD;
sum[i] = (ans + sum[i - 1]) % MOD;
}
while(q--) {
int l, r; fin >> l >> r; r--;
fout << ((sum[r] - sum[l - 1]) % MOD + MOD) % MOD << '
';
}
}
return 0;
}