首页 > 其他 > 详细

[XDFZ集训]NOI2020模拟1

时间:2019-12-10 21:23:40      阅读:128      评论:0      收藏:0      [点我收藏+]

[XDFZ集训]NOI2020模拟

假的NOI模拟,真的CSP-J模拟

T1 :Stone

小D 正在玩取石子游戏。
小D 共有n 堆石子,依次编号为1, 2, · · · , n,其中第i 堆有ai 颗石子。
小D 每次会等概率随机选择一颗石子,并取完它所在的那一堆石子。
小D 想要知道,第1 堆石子被取走的时间的期望。如果你不知道期望是什么,你
可以把它理解为所有情况下,这堆石子被取走的时间的平均数。
但是小D 并不会,请你帮帮他。
n<=1e5

是个人都会做到期望题

E = 1 + ∑ ai / (a1+ai)

直接考虑新加一个的概率即可

正式题解:

技术分享图片

 

 代码:

#include<bits/stdc++.h>
 
using namespace std;
 
#define LL long long
 
inline int read()
{
    int f = 1,x = 0;
    char ch;
    do
    {
        ch = getchar();
        if(ch == -) f = -1;
    }while(ch<0||ch>9);
    do
    {
        x = (x<<3) + (x<<1) + ch - 0;
        ch = getchar();
    }while(ch>=0&&ch<=9);
    return f*x;
}
 
const int MAXN = 1e5 + 10;
 
int n;
int a[MAXN];
//bitset<MAXN>a;
LL sum;
bool flag2 = 0;
double dp[MAXN],dsum                                                                                                                    ;
double ans = 0;
 
int main()
{
    n = read();
    for(int i=1;i<=n;i++)
    {
        a[i] = read();sum+=a[i];
        if(a[i] != 1)  flag2 = 1;
    }
    if(!flag2)
    {
        dp[1] = a[1] * 1.0/ sum;
        dsum += dp[1];
        for(int i=2;i<=n;i++)
        {
            dp[i] = (1.0 - dsum)/(n-i+1);
            dsum += dp[i];
        }
        for(int i=1;i<=n;i++)
        {
            ans += dp[i] * i;
        }
        printf("%.6f\n",ans);
        return 0;
    }
    ans = 0;
    for(int i=2;i<=n;i++)
    {
        ans += 1.0*a[i]/(a[i]+a[1]);
    }
    printf("%.6f\n",ans+1);
}

T2:memory

小D 正在研究信息在内存中的存储。
小D 共有n 条信息,依次编号为1, 2, · · · , n,第i 条信息的大小为ai。
小D 可以将这些信息分为连续的k 组,每组存入一个内存单元,每组需要的存
储空间为这组中所有信息大小之和。
小D 可以使用压缩技术将每条信息的大小同时从ai 变为(ai + x) mod m,其中
x 为一个小D 自己选定的整数。
小D 想要知道,这k 组信息需要的存储空间最大值最小可以是多少。
但是小D 并不会,请你帮帮他。
n<=1e5

直接贴题解:

技术分享图片

事实上,直接倒序就可以A了,万恶卡常,100 --》 70

代码:

#include<bits/stdc++.h>
 
using namespace std;
 
#define LL long long
#define re register
 
inline int read()
{
    int f = 1,x = 0;
    char ch;
    do
    {
        ch = getchar();
        if(ch == -) f = -1;
    }while(ch<0||ch>9);
    do
    {
        x = (x<<3) + (x<<1) + ch - 0;
        ch = getchar();
    }while(ch>=0&&ch<=9);
    return f*x;
}
 
const int MAXN = 100000 + 10;
 
int n,m,k;
LL a[MAXN],b[MAXN];
LL ans,sum;
 
inline bool check(int x)
{
       LL tot = 0,val = 0;
    for(re int i=1;i<=n;i++) if(b[i]>x) return false;
    for(re int i=1;i<=n;i++)
    {
        if(val + b[i] > x)
        {
            val = b[i];
            tot++;
        }
        else val += b[i];
    }
    if(val) tot++;
    return tot <= k;
}
 
inline LL solve()
{
    int l = 1,r = ans-1;
    int res = 0;
    while(r>=l)
    {
        int mid = (l+r)>>1;
        if(check(mid))
        {
        //  if(mid == 6)
        //  {
        //      for(int i=1;i<=n;i++) cout << b[i] << " ";
        //      exit(0);
        //  }
            r = mid - 1;
            res = mid;
        }
        else l = mid + 1;
    }
    //cout << res << endl;
    return res;
}
 
int main()
{
    srand(time(NULL));
    n = read(),m = read(),k = read();ans = 1<<30;
    for(re int i=1;i<=n;i++) a[i] = read();
    for(re int i=m;i>=0;i--)
    {
        sum = 0;
        for(re int j=1;j<=n;j++)
        {
            b[j] = (a[j] + i)%m,sum+=b[j];if(b[j]>ans) continue;
        }
    //  for(int j=1;j<=n;j++) cout << b[j] << " ";
    //  cout << endl;
        if(!check(ans-1)) continue;
        ans = min(ans , solve()); 
    }
    cout << ans << endl;
}

T3 :subset

小D 正在研究集合。
小D 想要知道,对于给定的n,有多少个集合{1, 2, · · · , n} 的子集满足最大公约
数为1,而最小公倍数为n。
但是小D 并不会,请你帮帮他。因为答案可能很大,所以你只要输出这样的子集
个数对998244353 取模的结果即可。
n<=1e18

不会,直接贴题解:

技术分享图片

 

 

 

 

[XDFZ集训]NOI2020模拟1

原文:https://www.cnblogs.com/wlzs1432/p/12018657.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!