C
结束发现这题数据很水直接假做也能过
1：
比赛想到了利用log，可以用log（2e19）粗略判断然后再暴力
#include<bits/stdc++.h> using namespace std; #define endl '\n' #define LL long long #define ph push_back #define INF 0x3f3f3f3f #define PII pair<int, int> const double M=log(2e18); double a[100]; int main(){ cin>>a[1]>>a[2]; int ans=3; while(1){ if(a[ans-1]*log(a[ans-2])>M){ cout<<ans-1; break; }//利用log在每次操作粗略判断是否溢出，如果没有溢出，我们知道可以计算出该项 else{ a[ans]=1; for(int i=1;i<=a[ans-1];i++){ a[ans]*=a[ans-2]; } if(a[ans]>1e18){ cout<<ans; break; } } ans++; } return 0; }
2.利用__int128直接做
之前没用过，算是学新知识了，注意__int128不能调用cin，cout，其他用法与int类型基本相同，我们要手写read和print操作(但是好像没用到hhh)
#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> __int128 M=1e18; __int128 read() { __int128 ans = 0; string str; cin >> str; for(int i = 0; i < str.size(); i ++) { ans = ans * 10 + (str[i] - '0'); } return ans; } __int128 qmi(__int128 a , __int128 b){ __int128 res=1; while(b--){ res=res*a; if(res>M)return 1e19; } return res; } void print(__int128 x) { if(x > 9) print(x / 10); putchar(x % 10 + '0'); } __int128 a[100]; void solve(){ int p,q; cin>>p>>q; a[1]=p,a[2]=q; for(int i=3;i<=20;i++){ a[i]=qmi(a[i-2],a[i-1]); } for(int i=1;i<=20;i++){ if(a[i]>M){ cout<<i-1; return ; } } } signed main(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int T=1; while(T--)solve(); }
D
1.按我的思路加上各位大佬的题解结合总算是补出来了QAQ，还挺有成就感，这题我的排序出了问题，应该按找主人期望友善值从小到大排序，并且还要用到一个max数组存储前面出现的最大值，这题我学到的东西是二分的运用
这题二分不是二分答案了，而是找最大满足条件的主人期望友善值得到一个合法的范围，再利用max数组，出现过的最大值满足猫咪这最大值就是我们要的，这最大值不满足那就没咱要的值了
#include <bits/stdc++.h> using namespace std; #define endl '\n' #define LL long long #define ph push_back #define INF 0x3f3f3f3f #define PII pair<int, int> const int N =2e5+10; int t; int n,m; int a[N],c[N]; int mx[N]; struct ren{ int b,d; bool operator<(const ren &W) const { return d==W.d?b>W.b:d<W.d; } } ren[N]; void solve() { cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ cin>>c[i]; } for(int i=1;i<=m;i++) { cin>>ren[i].b; } for(int i=1;i<=m;i++){ cin>>ren[i].d; } sort(ren+1,ren+1+m); // for(int i=1;i<=m;i++){ // cout<<ren[i].b<<' '<<ren[i].d<<endl; // } for(int i=1;i<=m;++i) mx[i]=max(mx[i-1],ren[i].b);//记录下前i个元素下主人最大的友善值 for(int i=1;i<=n;i++){ if(ren[1].d>a[i]){ cout<<-1<<' '; continue; } //二分找到满足猫咪可以配对主人条件中主人期望的最大值，从而得到满足猫咪友善值与主人期望友善值匹配的范围 //由于记录了前i个元素主人最大的友善值，我们在这个范围找到最大值（mx[l]）如果最大值满足猫咪期望友善值这就是我们要找的，如果不满足，则没有满足的 int l=-1,r=m+1; while(l+1!=r){ int mid=(l+r)>>1; if(ren[mid].d<=a[i]) l=mid; else r=mid; } if(mx[l]>=c[i]) cout<<mx[l]<<' '; else cout<<-1<<' '; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr); // cin >> t; t=1; while (t--) { solve(); } return 0; }
2.离线查询，考虑开结构体时加上元素id，这样我们在sort之后存储答案后也能找到对应询问顺序的答案，这是我看视频才知道这叫离线询问的思想，然后我找到了一道codeforces上的题目 Problem - D - Codeforces 这题直接写会超时，我们利用set储存所有可能的查询这样我们每次询问的时候将多次询问问题实际上换成了一次询问的问题
#include <bits/stdc++.h> using namespace std; const int N = 200010; struct T { int x, y,id; }s1[N],s2[N]; bool cmp(T a,T b) { if(a.x!=b.x)return a.x<b.x; if(a.y!=b.y)return a.y<b.y; return a.id < b.id; } int ans[N]; int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++)cin>>s1[i].x; for(int i=1;i<=n;i++)cin>>s1[i].y; for(int i=1;i<=m;i++)cin>>s2[i].y; for(int i=1;i<=m;i++)cin>>s2[i].x; for(int i=1;i<=n;i++)s1[i].id=i; sort(s1+1,s1+n+1,cmp); sort(s2 + 1, s2 + 1 + m, cmp); int t=1,mx=-1; for(int i=1;i<=n;i++){ while(t<=m&&s2[t].x<=s1[i].x){ mx=max(mx,s2[t].y); t++; } if(mx>=s1[i].y)ans[s1[i].id]=mx; else ans[s1[i].id] = -1; } for(int i=1;i<=n;i++) cout << ans[i] << " "; return 0; }
E
#include<bits/stdc++.h> using namespace std; const int N = 2e5 + 17; typedef long long ll; int main() { ll a, b; cin >> a >> b; if(a == b + 1 || a + 1 == b) cout << -1; else if(__gcd(a,b) != 1) cout << 0; else if(a%2 == 1 && b%2 == 1) cout << 1; else { ll m = abs(a - b); ll mi = m - a%m; for(ll i = 2; i * i <= m; i ++) if(m % i == 0) { mi = min(mi, i - a%i); mi = min(mi, m/i - a%(m/i)); } cout << mi; } return 0; }