首页 > 其他分享 >CF1305F Kuroni and the Punishment 题解

CF1305F Kuroni and the Punishment 题解

时间:2022-09-07 13:23:07浏览次数:83  
标签:rand zxc int 题解 qwe asd Kuroni text Punishment

一道比较简单的题,我居然调了这么久。

思路

看一眼这个题,发现好像没有什么思路。

考虑来用一些巧妙的手法,比如随机化。

首先证明一个结论,至少有一半的数只会被操作一次或者不操作。

这个结论比较好证明。

可以知道,答案一定小于等于 \(\text{n}\)。

所以如果有超过一半的数会被操作两次。

那么这个答案必然不是最优的答案。

所以,我们可以随即选出一个数 \(\text{x}\),将 \(\text{x}\),\(x+1\),\(x-1\) 分解质因数,来判断这个质数是否可以更新答案,每次找到最优的概率是 \(\frac{1}{2}\)。

这样,就可以随机找出 \(\text{50}\) 个数来判断即可。

错误的概率为 \(\frac{1}{2^{50}}\)。

一个细节

这个细节让我调了特别久。

当你在用 \(\text{rand}\) 调用随机数时,请不要这样写。

x = rand() % n + 1;

请这样写。

x = rand() * rand() % n + 1;

一个惨痛的教训。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
const int N = 200010;
 
int n , ans , top , a[N] , stk[N];
 
inline int read()
{
    int asd = 0 , qwe = 1; char zxc;
    while(!isdigit(zxc = getchar())) if(zxc == '-') qwe = -1;
    while(isdigit(zxc)) asd = asd * 10 + zxc - '0' , zxc = getchar();
    return asd * qwe;
}
 
inline void calc(int x)
{
    for(int i = 2;i * i <= x;i++)
    {
        if(x % i == 0)
            stk[++top] = i;
        while(x % i == 0)
            x /= i;
    }
    if(x != 1) stk[++top] = x;
}
 
inline void solve(int x)
{
    int sum = 0;
    for(int i = 1;i <= n;i++)
        sum += min((a[i] >= x ? a[i] % x : (int)1e17) , x - a[i] % x);
    ans = min(ans , sum);
}
 
signed main()
{
    n = read() , srand(time(0));
    for(int i = 1;i <= n;i++)
        a[i] = read() , ans += (a[i] & 1);
    int res = 50;
    while(res--)
    {
        int x = rand() * rand() % n + 1;
        calc(a[x]) , calc(a[x] + 1) , calc(a[x] - 1);
    }
    sort(stk + 1 , stk + top + 1);
    top = unique(stk , stk + top + 1) - stk - 1;
    for(int i = 1;i <= top;i++) solve(stk[i]);
    cout << ans << endl;
    return 0;
}

标签:rand,zxc,int,题解,qwe,asd,Kuroni,text,Punishment
From: https://www.cnblogs.com/mfeitveer/p/16665042.html

相关文章

  • CF1715E Long Way Home 题解
    CF1715E题解题意一个带边权无向图,可以沿着边走,需要边权的花费或从任意点\(u\)飞到\(v\),需要\((u-v)^2\)的花费。求从点\(1\)到所有\(i\)的最少花费。最多飞\(......
  • CF1515E Phoenix and Computers 题解
    感觉这样的\(\text{dp}\)题还比较多,思路都比较的神奇。个人感觉比较像区间\(\text{dp}\)的一类变种。但又和区间\(\text{dp}\)的维护方式极不一样。对于此类\(\t......
  • P5999 [CEOI2016] kangaroo 题解
    感觉这样的\(\text{dp}\)题还比较多,思路都比较的神奇。个人感觉比较像区间\(\text{dp}\)的一类变种。但又和区间\(\text{dp}\)的维护方式极不一样。对于此类\(\t......
  • MySQL5.7完整安装教程及相关问题解决
    1 下载安装1.1下载直接官网下载https://www.mysql.com/①拉倒最下面,点community server②选择之前的版本③选5.7,通过压缩包来安装,点download1.2解压安装①下......
  • CF222C Reducing Fractions 题解
    虽然是朴素的筛法,但是跑的比希儿的Pollard-rho快。\(\mathcalO(n\sqrtn)\)的质因数分解是不行的,Pollard-rho的码量也过于麻烦,直接在线性筛里筛出每个数的最小质因子......
  • 2022/09/26小测 题解
    (本文将笔者测试时的想法及赛后想法均写出来了)题目:话说某某在\(cj\)校运会上异军突起,其实不是偶然,而是有历史原因的。时光回溯到\(XX\)年前,某某为了心中的理想,每天爬......
  • C#、IIS获取时间带星期或日期问题解决
    cmd   regedit打开注册表,进入到[HKEY_USERS\.DEFAULT\Control Panel\International]  ,然后1、将键 sDate 的值由 / 改为 - 2、将键 sShortDate 的值由 yyyy......
  • 题解【CF1316E Team Building】网络流做法
    题目传送门。一眼费用流。然后发现题解区竟然全是状压DP?????推销一下本题状压DP的题解。那么我就来yy一下我的网络流做法吧,我会尽量把网络流的想法讲得自然一点。考......
  • CSP集训题解
    CSP集训题解Summer已经完结了于是新开一个,而且旧的已经很卡了9.5CSP-S短赛1(开小灶1)T1ZZH的游戏实际上把策略想明白就很简单。以一次连续的移动为一个阶段,每个阶段都必......
  • CF1615F LEGOndary Grandmaster 题解
    CF1615FLEGOndaryGrandmaster对于两个长度为\(n\)的\(01\)串\(s,t\),你可以对\(s\)进行两种操作:把相邻两个\(0\)变成\(1\)或把相邻两个\(1\)变成\(0\),......