当前位置:网站首页>2020 CCPC 威海 - A. Golden Spirit(思维),D. ABC Conjecture(大数分解 / 思维)
2020 CCPC 威海 - A. Golden Spirit(思维),D. ABC Conjecture(大数分解 / 思维)
2022-07-05 20:08:00 【小酒窝.】
A. Golden Spirit
题意
一道河上有座桥,两岸分别有 n n n 个人。
现这 2 n 2n 2n 个人都要到对岸去,游玩至少 x x x 分钟后回到原来的河岸。
要帮助这 2 n 2n 2n 个人渡河。
每次渡河最多带一个人,时间为 t t t。
问,满足所有人的要求最少花多少时间?
思路
在最理想的情况下,帮助者没有一点时间浪费,当他把所有人都运到其对应对岸后,立即可以将该河岸首次运过来的人运回去。
但是可能甚至首次运过来的人都没有到所需的游玩时间,所以帮助者可能需要等待。
假设有河岸 A 和 B,起初帮助者在河岸 A,那么将所有人分别运到其对应河岸后,帮助者位于河岸 A。
这时就面临一个问题,帮助者是继续在该河岸 A 等待首次运到河岸 A 的人,还是自己到对岸 B 去等首次运到河岸 B 的人?
前者所需时间为:运输所有人的时间 4nt
+ 等待时间
(最少游玩时间 x
- 首人已经游玩时间 2nt-2t
)
后者所需时间为:运输所有人的时间 4nt
+ 自己到对岸的时间 t
+ 等待时间
(最少游玩时间 x
- 首人已经游玩时间 2nt + t - t
)
因为不确定两者的大小,所以需要将两者取 min。
Code:
#include<bits/stdc++.h>
using namespace std;
const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];
signed main(){
cin >> T;
while(T--)
{
int x, t;
cin >> n >> x >> t;
int ans1 = 4*n*t + t + max(0ll, x - (2*n*t + t - t));
int ans2 = 4*n*t + max(0ll, x - (2*n*t - 2*t));
cout << min(ans1, ans2) << endl;
}
return 0;
}
经验
- 当不确定所有情况哪种最优时,需要将所有情况的答案取最小值;
- 有些情况下不要写太多的 if else,而是尽量将其抽象到一种大情况中。
D. ABC Conjecture
题意
给定一个数 c,判断是否存在 a, b 满足下面条件:
- a + b = c
- abc 的所有质因子的乘积 不超过 c
1 ≤ c ≤ 1 0 18 1≤c≤10^{18} 1≤c≤1018
思路
打表发现:能够满足的 c 分解的所有质因子都只出现一次。
所以对于给定的 c,只需判断其是否存在出现不止一次的质因子即可。
但是 c 很大,而常用的分解质因数代码的时间复杂度为O(logn),会超时。
所以需要用特殊的方法来做。
方法1:
- 按照分解质因数的思路将 c 的所有不超过 1e6 的质因数分解,判断其个数是否出现两次及以上。
- 如果 1e6 内的质因数筛完之后发现 c 不为1,那么说明 c 还存在最多两个大于 1e6 的质因数(假设存在3个,那么相乘后大于1e18,矛盾)。
我们不是要求出这两个质因子,而只是想判断这两个质因子是否相同。所以将最后的 c 取根号取整,判断其是否为平方数。如果是平方数,那么最后的两个质因子就是相同的。
Code1:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 1000010, mod = 1e9+7;
int T, n, m;
int a[N];
int f[N];
int prim[N];
int cnt;
int maxa = 1e6;
signed main(){
Ios;
cin >> T;
while(T--)
{
cin >> n;
int flag = 0;
for(int i=2; i<=maxa; i++)
{
if(n % i == 0)
{
int cnt = 0;
while(n % i == 0) n /= i, cnt++;
if(cnt != 1) flag = 1;
}
}
if(n != 1){
int sq = sqrt(n);
if(sq * sq == n) flag = 1;
}
if(flag) cout << "yes\n";
else cout << "no\n";
}
return 0;
}
方法2
直接上大数质因子分解模板,判断是否有质因子出现两次及以上。
Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll pr;
ll pmod(ll a, ll b, ll p) {
return (a * b - (ll)((long double)a / p * b) * p + p) % p; }
ll gmod(ll a, ll b, ll p)
{
ll res = 1;
while (b)
{
if (b & 1)
res = pmod(res, a, p);
a = pmod(a, a, p);
b >>= 1;
}
return res;
}
inline ll gcd(ll a, ll b)
{
if (!a)
return b;
if (!b)
return a;
int t = __builtin_ctzll(a | b);
a >>= __builtin_ctzll(a);
do
{
b >>= __builtin_ctzll(b);
if (a > b)
{
ll t = b;
b = a, a = t;
}
b -= a;
} while (b);
return a << t;
}
bool Miller_Rabin(ll n)
{
if (n == 46856248255981ll || n < 2)
return false;
if (n == 2 || n == 3 || n == 7 || n == 61 || n == 24251)
return true;
if (!(n & 1) || !(n % 3) || !(n % 61) || !(n % 24251))
return false;
ll m = n - 1, k = 0;
while (!(m & 1))
k++, m >>= 1;
for (int i = 1; i <= 20; ++i)
{
ll a = rand() % (n - 1) + 1, x = gmod(a, m, n), y;
for (int j = 1; j <= k; ++j)
{
y = pmod(x, x, n);
if (y == 1 && x != 1 && x != n - 1)
return 0;
x = y;
}
if (y != 1)
return 0;
}
return 1;
}
ll Pollard_Rho(ll x)
{
ll n = 0, m = 0, t = 1, q = 1, c = rand() % (x - 1) + 1;
for (ll k = 2;; k <<= 1, m = n, q = 1)
{
for (ll i = 1; i <= k; ++i)
{
n = (pmod(n, n, x) + c) % x;
q = pmod(q, abs(m - n), x);
}
t = gcd(x, q);
if (t > 1)
return t;
}
}
map<long long, int> m;
void fid(ll n)
{
if (n == 1)
return;
if (Miller_Rabin(n))
{
pr = max(pr, n);
m[n]++;
return;
}
ll p = n;
while (p >= n)
p = Pollard_Rho(p);
fid(p);
fid(n / p);
}
int main()
{
int T;
ll n;
scanf("%d", &T);
while (T--)
{
m.clear();
scanf("%lld", &n);
pr = 0;
fid(n);
int flag = 0;
for (map<long long, int>::iterator c = m.begin(); c != m.end(); c++)
if(c->second != 1) flag = 1;
if(flag) printf("yes\n");
else printf("no\n");
}
return 0;
}
打表代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define endl '\n'
const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];
vector<int> v, v1, v2;
set<int> st, s;
void div(int x, vector<int> &v)
{
v.clear();
for(int i=2;i<=x/i;i++)
{
if(x%i == 0)
{
while(x%i == 0) x /= i;
v.push_back(i);
}
}
if(x != 1) v.push_back(x);
}
signed main(){
for(int i=1;i<=1000;i++)
{
st.clear();
div(i, v);
for(int x : v) st.insert(x);
int flag = 0;
for(int j=1;j<i;j++)
{
s = st;
int x = j, y = i - x;
div(x, v1);
div(y, v2);
for(int x : v1) s.insert(x);
for(int x : v2) s.insert(x);
int sum = 1;
for(int x : s){
sum *= x;
}
if(sum < i){
flag = 1;
break;
}
}
if(!flag){
cout << i << ":";
for(int x : st) cout << x << " ";
cout << endl;
}
}
return 0;
}
经验
- 没有思路的时候先打个表;
- 判断一个数是不是平方数,sqrt(n)要取整之后再相乘;
- 大数质因子分解模板。
边栏推荐
- Securerandom things | true and false random numbers
- Leetcode brush question: binary tree 14 (sum of left leaves)
- 618 "low key" curtain call, how can baiqiushangmei join hands with the brand to cross the "uncertain era"?
- 零道云新UI设计中
- Notes on key vocabulary in the English original of the biography of jobs (12) [chapter ten & eleven]
- Leetcode skimming: binary tree 10 (number of nodes of a complete binary tree)
- A solution to PHP's inability to convert strings into JSON
- Database logic processing function
- Debezium series: record the messages parsed by debezium and the solutions after the MariaDB database deletes multiple temporary tables
- 再忙不能忘安全
猜你喜欢
leetcode刷题:二叉树13(相同的树)
95后阿里P7晒出工资单:狠补了这个,真香...
[untitled]
Go language | 02 for loop and the use of common functions
深度學習 卷積神經網絡(CNN)基礎
【数字IC验证快速入门】8、数字IC中的典型电路及其对应的Verilog描述方法
Autumn byte interviewer asked you any questions? In fact, you have stepped on thunder
Interviewer: what is the internal implementation of set data types in redis?
实操演示:产研团队如何高效构建需求工作流?
Leetcode: binary tree 15 (find the value in the lower left corner of the tree)
随机推荐
Analysis of openh264 decoded data flow
银河证券在网上开户安全吗?
Solve the problem that the database configuration information under the ThinkPHP framework application directory is still connected by default after modification
Jvmrandom cannot set seeds | problem tracing | source code tracing
Debezium series: record the messages parsed by debezium and the solutions after the MariaDB database deletes multiple temporary tables
Multi branch structure
1: Citation;
Zero cloud new UI design
Gstreamer中的task
Android interview classic, 2022 Android interview written examination summary
国信证券在网上开户安全吗?
CADD课程学习(7)-- 模拟靶点和小分子相互作用 (半柔性对接 AutoDock)
处理文件和目录名
How to select the Block Editor? Impression notes verse, notation, flowus
c——顺序结构
走入并行的世界
浮动元素与父级、兄弟盒子的关系
Hong Kong stocks will welcome the "best ten yuan store". Can famous creative products break through through the IPO?
Wildcard selector
淺淺的談一下ThreadLocalInsecureRandom