A - 2^n - 2*n
直接计算即可。
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;cout<<pow(2,n)-2*n;return 0;
}
B - Happy Number
直接模拟即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,t;
bool vis[N];
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;t=n;while(t!=1){int tmp=t,sum=0;while(tmp){sum+=((tmp%10)*(tmp%10));tmp/=10;}t=sum;if(t==1){cout<<"Yes";return 0;} if(vis[t]){cout<<"No";return 0;}vis[t]=1;}cout<<"Yes";return 0;
}
C - 2026
因为 \(n\le 10^7\)，所以 \(x,y\le \sqrt{10^7}\)，两层循环枚举 \(x,y\)，将 \(x^2+y^2\) 的解数 \(+1\)，最后枚举统计解为 \(1\) 的数输出。时间复杂度 \(O(n)\)。
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int n,ans;
int cnt[N];
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n/i;i++){for(int j=i+1;j<=n/j;j++){long long sum;sum=1ll*(1ll*i*i+1ll*j*j);if(sum<=n) cnt[sum]++; }}for(int i=1;i<=n;i++){if(cnt[i]==1) ans++;}cout<<ans<<'\n';for(int i=1;i<=n;i++){if(cnt[i]==1) cout<<i<<' ';;} return 0;
}
D - Kadomatsu Subsequence
注意到第三个条件，\(j\) 只能为三元组中在原数组里第一个或最后一个出现的元素。这是一个很好的性质，启发我们可以用前缀后缀的思想来求解。
接着考虑剩下两个元素，要成 \(3:5:7\) 关系。那么首先 \(j\) 应是 \(5\) 的倍数，且另两个元素应是 \(3,7\) 的倍数，且分别 \(\div 3,\div 5,\div 7\) 的值相等。
那么我们就可以使用两个 map 分别维护 \(j\) 之前值为 \(3\times t,7\times t\) 的元素数量。若 \(A_j=5\times t\)，则根据乘法原理，将 \(3\times t\) 和 \(7\times t\) 的元素个数相乘即是 \(A_j\) 参与构成的三元组数量。
这是 \(j\) 作最后一个出现的元素时的情况，反着求一遍就是另一种情况。
时间复杂度 \(O(n)\)。
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n;
long long ans;
int a[N];
map<int,int> mp3,mp7;
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]%3==0) mp3[a[i]/3]++;if(a[i]%7==0) mp7[a[i]/7]++;if(a[i]%5==0) ans+=1ll*(1ll*mp3[a[i]/5]*1ll*mp7[a[i]/5]);}mp3.clear();mp7.clear();for(int i=n;i>=1;i--){if(a[i]%3==0) mp3[a[i]/3]++;if(a[i]%7==0) mp7[a[i]/7]++;if(a[i]%5==0) ans+=1ll*(1ll*mp3[a[i]/5]*1ll*mp7[a[i]/5]);}cout<<ans;return 0;
}
E - Kite
将线段交叉转化，即可得到合法的两条线段为：
- \(A_i<A_j,B_i<B_j\)
- \(A_i>A_j,B_i>B_j\)
想到按 \(A_i\) 大小升序排序，此时题目转化为了求当前 \(B_i\) 的最长上升子序列。
使用二分优化 LIS 求解。时间复杂度 \(O(n\log n)\)。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct Node{int a,b;
}kt[N];
int n,len;
int f[N];
bool cmp(Node x,Node y){if(x.a==y.a) return x.b>y.b;return x.a<y.a;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>kt[i].a>>kt[i].b;sort(kt+1,kt+1+n,cmp);for(int i=1;i<=n;i++){if(kt[i].b>f[len]) f[++len]=kt[i].b;else{int t=lower_bound(f+1,f+1+len,kt[i].b)-f;f[t]=kt[i].b;}}cout<<len;return 0;
}