A、兰子哥哥的一万粉丝女装照!!
关注B站账号观看视频讲解
https://space.bilibili.com/414380929
#include<bits/stdc++.h> using namespace std; const int MAXN = 100005; long long a[MAXN], c[MAXN], h[MAXN], m, ans[MAXN], nowm, nowcnt, maxm; int n; //log_a(x) int Mylog(long long a, long long x) { assert(a > 1); int ret = 0; while (x >= a)x /= a, ++ret; return ret; } bool i128leq(long long a, long long b, long long c, long long d) { __int128 _a = a, _b = b, _c = c, _d = d; return _a * _b <= _c * _d; } long long div_ceil(long long a, long long b) { return a / b + (!!(a % b)); } long long cnt_to_nearest_log_number(long long a, long long h, long long nowcnt, long long limit) { if (nowcnt > limit)return -1; long long temp = a; while (i128leq(temp, a, limit, h) && temp <= nowcnt * h)temp *= a; if (temp <= nowcnt * h)return -1; long long ret = div_ceil(temp, h); assert(ret > nowcnt); return ret - nowcnt; } struct node { long long next_cnt; int id; long long cnt; node(long long next_cnt = 0, int id = 0, long long cnt = 0) { this->next_cnt = next_cnt; this->id = id; this->cnt = cnt; } friend bool operator < (node a, node b) { return a.next_cnt > b.next_cnt; } }; priority_queue<node>q; vector<pair<int, int> > v; int main() { //freopen("192.in","r",stdin); scanf("%d%lld", &n, &m); for (int i = 1; i <= n; ++i) { scanf("%lld", &c[i]); } for (int i = 1; i <= n; ++i) { scanf("%lld", &a[i]); } for (int i = 1; i <= n; ++i) { scanf("%lld", &h[i]); } for (int i = 1; i <= n; ++i) { maxm += Mylog(a[i], c[i] * h[i]); } if(maxm<m) { printf("QAQ,lan zi bu nv zhuang\n"); return 0; } for (int i = 1; i <= n; ++i) { int mlg = Mylog(a[i], h[i]); if (mlg >= 1) { v.emplace_back(mlg, i); long long next_cnt_num = cnt_to_nearest_log_number(a[i], h[i], 1, c[i]); if (next_cnt_num != -1) { q.push(node(next_cnt_num, i, 1)); } } else { long long next_cnt_num = cnt_to_nearest_log_number(a[i], h[i], 0, c[i]); if (next_cnt_num != -1) { q.push(node(next_cnt_num, i, 0)); } } } sort(v.begin() , v.end()); for (auto it = v.rbegin(); it != v.rend(); ++it) { if (nowm < m) { nowm += it->first; ans[it->second]++; nowcnt++; } } if (nowm >= m) { for (int i = 1; i <= n; ++i) { printf("%d%c", ans[i], i == n ? '\n' : ' '); } return 0; } while(nowm<m && !q.empty()) { node now=q.top(); q.pop(); ans[now.id]+=now.next_cnt; now.cnt+=now.next_cnt; now.next_cnt=cnt_to_nearest_log_number(a[now.id],h[now.id],now.cnt,c[now.id]); nowm++; if(now.next_cnt!=-1) { q.push(now); } } /* for(int i=1;i<=n;++i) { cout<<Mylog(a[i],ans[i]*h[i])<<" cmp "<<Mylog(a[i],c[i]*h[i])<<endl; if(Mylog(a[i],ans[i]*h[i])!=Mylog(a[i],c[i]*h[i])) { cout<<"this error "<<a[i]<<" "<<c[i]<<" "<<h[i]<<endl; } } */ assert(nowm>=m); for (int i = 1; i <= n; ++i) { printf("%d%c", ans[i], i == n ? '\n' : ' '); } return 0; }
B、acmer 上下一心
虽然很多人都直接rand过了哈,但是这个题原本的想法灵感是在某纺大比赛中 出了一个题 他给定你3个数字让你输出答案。
大家可以感受一下几个数据然后猜猜看
input case 1:13 14 1 case 2:2 3 5 case 3:3 5 3 output case 1:14 case 2:21 case 3:13
然后当时一眼看出来之后一下秒了,但是不知道为什么直到赛后都没多少人过这个题,所以我便出了一下这个题
首先在题目中可以发现
链接:https://ac.nowcoder.com/acm/contest/26086/B 来源:牛客网 输入1 黑盒将输出1 输入2 黑盒将输出2 输入4 黑盒将输出5 输出100000 黑盒将输出918
我们可以猜测第一项为1 第二项为2 第四项为5
这个时候就发挥我们的数学猜想:
递推式可不可能是dp[i]=dp[i-1]+dp[i-2]
然后在通过给定的100000大数来推测他的模数
最后我们可以测出不超过10个数的mod值,不管取那个mod都可以正确。
至于为什么给定918这个数字,因为我们暴力对拍之后,得到的第一个模数是
1097
可以得到一个答案为365的争取答案,并且k*366+365都是正确答案。寓意这不管是平年还是闰年,大家年年都可以想今天跨年一样找到写题的快乐。
#include<iostream> using namespace std; const int N=1e5+7; int mod=919; int dp[N]; void f(){ dp[1]=1,dp[2]=2; for(int i=3;i<N;i++) dp[i]=dp[i-1]+dp[i-2],dp[i]%=mod; if(dp[100000]==918){ for(int i=1;i<N;i++)if(dp[i]==0){ cout<<i; exit(0); } } mod++; } int main(){ while(true)f(); }
当然你也可以这样过
#include<bits/stdc++.h> using namespace std; int main(){ long long *a=new long long; long long p=(long long&)a; mt19937 rng(p*time(0)); for(int i=1;i<=10;i++)cout<<rng()%100001<<" "; }
大家可以经常用这个方法,他可以在多线程测评下一样随机(
C、最大值求和
考虑reverse
一下数组a, pos
,再令pos[i] = n - pos[i] + 1
,那么问题将会变为求。
从头往后做,维护一个递减的单调栈stk
(stk
中存放的是下标),
假设当前栈的大小为sz
,那么对于所有i in [1, sz]
,都有j in (stk[i - 1], stk[i]]
,。
由此我们维护单调栈的时候,可以维护一个前缀答案,然后二分stk
数组即可在单次的时间内查找答案。
#include <bits/stdc++.h> using namespace std; const int N = 5e5 + 10; int a[N], p[N], stk[N], tot, n; long long sum[N]; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= n; i++) { cin >> p[i]; p[i] = n - p[i] + 1; } reverse(a + 1, a + 1 + n); reverse(p + 1, p + 1 + n); long long ans = 0; for (int i = 1; i <= n; i++) { while (tot && a[stk[tot]] <= a[i]) { tot--; } stk[++tot] = i, sum[tot] = 1ll * (i - stk[tot - 1]) * a[i] + sum[tot - 1]; int pos = lower_bound(stk + 1, stk + 1 + tot, p[i]) - stk; ans += sum[pos - 1] + 1ll * (p[i] - stk[pos - 1]) * a[stk[pos]]; } cout << ans << "\n"; return 0; }
D、小红玩幂塔
引理:
若 (其中 为素数),那么 的因子数量是 。
证明:
显然 的某个因子一定是一个或多个 的组合,其中幂可以从 到 中任意选择,共有 种选项。根据乘法原理,总方案数为:。证毕。
根据上述引理,我们要计算 的因子数量,即计算 的因子数量,可以先把 写成 的形式,那么也就是求:
的因子数量,答案是:
所以本题的关键就是如何算出 在模 意义下的值。
如果 和 互素,则可以直接使用费马小定理进行降幂。但本题需要降 次幂,所以要用到欧拉定理(费马小定理的一般形式):
其中 为欧拉函数,代表不超过 且与 互素的正整数数量。
参考代码:
#include<bits/stdc++.h> using namespace std; #define size 1000011 #define int long long int phi[size]; void Init() { memset(phi,0,sizeof(phi)); phi[1]=1; for(int i=2;i<size;i++) if(!phi[i]) for(int j=i;j<size;j+=i) { if(!phi[j]) phi[j]=j; phi[j]=phi[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出 } } int ksm(int a,int b,int p){ int res=1; while(b){ if(b&1) res=res*a%p; a=a*a%p; b>>=1; } return res; } int qs(int a,int b,int p){ if(b==0)return 1; if(b==1||p==1) return a%p; return ksm(a,qs(a,b-1,phi[p])+phi[p],p); } signed main(){ // freopen("./兰子的跨年毒瘤题/11.in","r",stdin); // freopen("./兰子的跨年毒瘤题/11.out","w",stdout); long long n,i,a,b,p=1000007; Init(); cin>>a>>b; long long temp=qs(a,b-1,p); // cout<<temp<<endl; long long res=1; for(i=2;i*i<=a;i++){ if(a%i==0){ long long cnt=0; while(a%i==0)a/=i,cnt++; res=res*(cnt*temp%p+1+p)%p; } } if(a!=1)res=res*(temp+1+p)%p; cout<<res; }
E、New Year and Chemistry
本来想作为一个 750 的 Div.2A 来着,但属实出成了阅读理解题(
Solution
我们考虑任意一种原子,我们把正确答案(即 序列)填入后左右该种原子计量数之和必定相等,我们把这个数值记作 。
那么我们把所有 都变成 , 于是我们发现对于这个原子,这个数值变成了 ,当然左右仍然相等,符合要求。
所以我们得出了一个关键的结论:
数列 合法当且仅当 ,其中 是定值。
由于反应前后不可能存在同种单质,所以任意一种原子都会影响到其他某一种原子,容易证明上述结论。
那么 的值能取到多少呢?我们发现,由题目可知任意 。
而这个关系式需要对任意 都成立,所以得出
容易发现 的可能取值个数就是最终可能方案数,即
Code
注意开 long long。
#include <cstdio> #define N 200010 #define ll long long #define INF (1e18 + 10) #define Min(a, b) ((a) > (b) ? (b) : (a)) using namespace std; ll u[N], a[N]; int n; ll ans = INF; int main(){ int T; scanf("%d", &T); while(T--){ ans = INF; scanf("%d", &n); for(int i = 1 ; i <= n ; i++) scanf("%lld", &a[i]); for(int i = 1 ; i <= n ; i++) scanf("%lld", &u[i]); for(int i = 1 ; i <= n ; i++) ans = Min(ans, (ll)u[i] / a[i]); printf("%lld\n", ans); } return 0; }
F、Cherry Sigma
展开式子得:
使用平方和公式得:
注意取模即可
G、新年快乐
群友博弈游戏,当大家题目都写的差不多时,这个题就是最后的博弈了,由于题目是spj判断时间,但是提交按提交时间算,所以你可以延迟spj测评的时间,让你的提交时间提前,所以你可以用很多卡常博弈的方法来提交。
但是正解当然只有等到点后
#include<bits/stdc++.h> using namespace std; #define ll long long int main() { cout<<"Happy New Year!"<<endl; }
小沙:祝大家新年快乐啦~
H、将idea煎至两面金黄
如果仅煎一面,不翻面,那么煎 T 个单位时间之后,被煎面的成熟度提高
$$
设w1,w2分别为T(T > 0),T - 1时刻被煎面 (仅煎一面) 提高的成熟度。该情况下选2个不同时刻t1,t2 (0 <= t1, t2 <= T)翻面煎一个单位时间再翻回。因为 F(t) = t,可使得 (t1 + t2) / 2 等于 小于w2 - w1 的任意正整数(0时刻翻面再翻回视为不翻面),所以想提高大于w1且小于等于w2的成熟度,需要T时间,暴力即可(偷懒。
代码:
#include <iostream> #include <fstream> #define min(x,y) (x)>(y)?(y):(x) #define Happy 1 #define New * #define Year 0 using namespace std; signed main() { long long n, maxn = 0x3f3f3f3f3fll; cin >> n; for (int i = 1; i <= n * 2; ++ i) { for (int j = 1; j <= n; ++ j) { long long num; cin >> num; if (num <= 2022) maxn = min(maxn, 2022 - num); else maxn = min(maxn, 4294969318ll - num); // 4294967296 - num + 2022 } } long long ans = 0; for (int i = 0; ; ++ i) { ans += i; if (ans >= maxn) { cout << i; break; } } return Happy New Year; }
I、公平公正的风行迷踪
根据题意,即可看成一个以猎手为圆心的动圆在地图上扫描处于顶点的游侠,很容易可以想到,可将猎手作为动点,游侠作为定圆。那么,猎手运动就是射线,每次判断动点是否在圆内,或者射线与向量方向上最近圆的交点,即可得到下一步行动方向及路线,之后按照题意进行模拟即可。当然,精度非常重要,所以最好使用精度高的浮点数进行运算。
涉及计算几何的知识有:点在圆内(上),直线圆交。
J、Simple Number
#include<iostream> using namespace std; int main() { cout << "277777788888899" << endl; }
K、dala mani mi movo?
是一个长度为的字符串,观察到其中各有两个,而各有一个。又因为是个人发轮,所以最后的情况必定是每个人张卡片。
那么我们取模之后分析(或者打表)可以得到如下结论:模相同的收到卡片也相同
的时候,每个人恰好拿一套,因为能遍历剩余系
的时候,有
两个种情况,但是拿到的糖果一样多
而只有当的时候,
这时候第三种情况下会比前两种少1颗
时
一样多
的时候种情况分别为各个。
的时候种情况是每个位置拿个字符次。
也就是说,当的时候,除了的倍数位会少一颗;其他情况下,所有人拿到的糖果数量都是一致的。
所以只要不输出3的倍数,其他的都对
全部评论
(5) 回帖