模拟赛1
好久没写博客了。。。。看着博客粉丝的增多，我还是很欣慰的。（虽然几乎都是本校学长学姐同门）
把题目全部放到洛谷上了,想做一下的同学可以去下面的链接提交.
T1
题目链接:https://www.luogu.org/problemnew/show/U45350
无语了,感觉题解都不是正解.
如果m再大一些,题解直接GG.
显然,直接找到第m大值,即可.
如何找到.
快速选择算法.(O(n))寻找第k大元素
感兴趣的可以学习一下.
也可以用STL中的(nth\_element)水过去.
题解就是用堆.然后不断与堆顶比较.
时间复杂度:(O(nlogm))
My CODE:
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#define rep(i,x,p) for(register ll i = x;i <= p;++ i)
const int maxN = 1e7 + 7;
const int mod = 1e9;
#define ll long long
using namespace std;
ll a[maxN];
inline ll read() {
ll x = 0, f = 1;char c = getchar();
while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
inline void swap(ll &x,ll &y) {
ll tmp = x;
x = y;
y = tmp;
return;
}
ll quick_select(ll *a, ll l, ll r, ll k)
{
swap(a[l], a[(l + r) >> 1]);
ll tmp = a[l];
ll l_ = l, r_ = r;
while (l < r)
{
while (l < r)
{
if (a[r] > tmp)r-- ;
else
{
a[l] = a[r];
l++;
break;
}
}
while (l < r)
{
if (a[l] < tmp) l++;
else
{
a[r] = a[l];
r--;
break;
}
}
}
a[l] = tmp;
if (k == l - l_ + 1) return a[l];
if (k < l - l_ + 1) return quick_select(a, l_, l - 1, k);
if (k > l - l_ + 1) return quick_select(a, r + 1, r_, k - (l - l_ + 1));
}
int main() {
freopen("shop.in","r",stdin);
freopen("shop.out","w",stdout);
ll n,m,x,y;
cin >> n >> m >> x >> y;
a[1] = x;
rep(i,2,n) a[i] = ( y * a[i - 1] + x) % mod;
ll tmp = quick_select(a,1,n,m);
ll sum = 0;
ll num = 0;
rep(i , 1, n) {
if(a[i] <= tmp) {
num ++;
sum += a[i];
if(num == m) break;
}
}
std::cout << sum;
fclose(stdin);
fclose(stdout);
return 0;
}
STD_CODE:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define MOD 1000000000LL
using namespace std;
typedef long long LL;
int n, m;
LL x, y, v = 0, s = 0;
priority_queue<int> pq;
int main()
{
freopen("shop.in", "r", stdin);
freopen("shop.out", "w", stdout);
scanf("%d%d", &n, &m);
scanf("%lld%lld", &x, &y);
for (int i = 1; i <= m; i++)
{
v = (v * y + x) % MOD;
pq.push(v);
}
for (int i = m+1; i <= n; i++)
{
v = (v * y + x) % MOD;
if (v < pq.top())
{
pq.pop();
pq.push(v);
}
}
for (int i = 1; i <= m; i++)
{
s += pq.top();
pq.pop();
}
printf("%I64d
", s);
return 0;
}
T2
题目链接:https://www.luogu.org/problemnew/show/U45353
非常有趣的一道题.....还是不敢做期望啊.
我发现期望DP非常难.而且无从下手.
然后转为求概率.
像这种二进制,一眼知道要按位DP的好吧.
设(f[i][j])表示第(i)位二进制(j)为1的概率
大力讨论一下就完成了...
具体看考试的代码.
// & : and
// | : or
// ^ : xor
// f[i][j] 表示第i位二进制j为1的概率
// 分类讨论一下.
// 会消失的概率: c[i]
// 不会 消失的概率: 1 - 1c[i]
// 会消失直接继承,不会消失就DP.
#include <iostream>
#include <cstdio>
#define rep(i,x,p) for(int i = x;i <= p;++ i)
const int maxN = 100000 + 7;
inline int read() {
int x = 0,f = 1;char c = getchar();
while(c < '0' || c > '9') {if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}
return x * f;
}
double f[maxN][34];//f[i][j] 表示第i位 二进制位j 为1的概率.
int a[maxN],b[maxN];
double c[maxN];//a是运算符,b是数值,c是概率
int main() {
freopen("exp.in","r",stdin);
freopen("exp.out","w",stdout);
int n;
scanf("%d",&n);
rep(i,1,n) a[i] = read();
rep(i,1,n) b[i] = read();
rep(i,1,n) scanf("%lf",&c[i]);
rep(i,1,n) {
rep(j,0,31) {
if(a[i] == 0) {
if(b[i] & (1 << j)) {
f[i][j] = (1 - c[i]) * f[i - 1][j];//不会消失
f[i][j] += c[i] * f[i - 1][j]; //会消失
}
else {
f[i][j] = 0;//不消失
f[i][j] += c[i] * f[i - 1][j];//消失
}
}
if(a[i] == 1) {
if(b[i] & (1 << j)) {
f[i][j] = (1 - c[i]);//不消失
f[i][j] += c[i] * f[i - 1][j];//消失
}
else {
f[i][j] = (1 - c[i]) * f[i - 1][j];//不消失
f[i][j] += c[i] * (f[i - 1][j]);//消失
}
}
if(a[i] == 2) {
if(b[i] & (1 << j)) {
f[i][j] = (1 - c[i]) * (1 - f[i - 1][j]) ;//不消失
f[i][j] += c[i] * (f[i - 1][j]);//消失
}
else {
f[i][j] = (1 - c[i]) * f[i - 1][j]; //不消失
f[i][j] += c[i] * f[i - 1][j]; //不消失
}
}
// and 两位全为1的时候才为1 3 5 -> 1
// or 只要有一位是1 值就为1 3 5 -> 7
// xor 相同为0 不同为1 3 5 -> 6
//0 表示 and，1 表示 or，2 表示 xor
}
}
double ans = 0;
rep(i,0,32) {
ans += (1 << i) * f[n][i];
}
printf("%.1lf",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
T3
题目链接:https://www.luogu.org/problemnew/show/U45355
这个题考察知识点就是:卡常,暴力.
神仙题解.
看不懂,交个题解,溜了.溜了
考察算法：LCA，压位
算 LCA 是显然的， 由于两个点之间可能要走很多步， 所以我们预处理每一个点往上连续
走六步会出现的各种情况，便能控制常数，从而在 8 秒内出解。由于边权只有两种，所以一
个点往上走六步遇到的边权只有 2^6 = 64 种情况。
Last
发现这次考试码力仍有欠缺,而且对于期望不算太熟悉.
继续做一下(DP)