写题记录1
记录一些有意思的题
1
题意:求,其中是能够整除的数的中位数向下取整的大小
我们知道除了平方因子,其他因子都是成对出现的,显然我们可以直接通过筛法找因子的过程中把这些成对的因子动态更新一下就好了,复杂度
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double dd;
const int N = 1e6+5;
const dd eps = 1e-8;
const int mod = 1e9+7;
ll f[N],vis[N];
int x,n;
int main(){
// freopen("input.txt","r",stdin);
for(int i = 2;i <= 1e6;i++){
if(!vis[i]) f[i] = (1+i)/2;
for(int j = i+i;j <= 1e6;j+=i){
vis[j] = 1;
if(i <= sqrt(j)){
f[j] = (i + j/i)/2;
}
}
}
f[1] = 1;
for(int i = 1;i <= 1e6;i++){
f[i] = (f[i-1] + f[i]%mod)%mod;
}
scanf("%d",&n);
while(n--){
scanf("%d",&x);
printf("%lld\n",f[x]);
}
return 0;
}
2
题意:求中组成三角形的数量。数量级:
思路,我们先枚举,然后可以发现,这种式子显然可以直接差分维护,之后再跑一次前缀和,枚举即可。
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double dd;
const int N = 1e6+50;
const dd eps = 1e-8;
const int mod = 1e9+7;
ll sum[N],a,b,c,d;
int main(){
// freopen("input.txt","r",stdin);
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
for(int i = a;i <= b;i++){
sum[i+b]++;sum[i+c+1]--;
}
for(int i = 1;i <= 1e6+10;i++){
sum[i] += sum[i-1];
}
for(int i = 1;i <= 1e6+10;i++){
sum[i] += sum[i-1];
}
ll ans = 0;
for(int i = c;i <= d;i++){
ans += sum[N-40] - sum[i];
}
printf("%lld\n",ans);
return 0;
}
3
题意:给出一些点,且这些点按排序给出,从点出发,到达点再经过其他点回到点,经过其他点仅一次的方案数。
可以通过dp,设表示当前在的两个人,那么显然状态只能转移到和,然后注意边界即可。
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double dd;
const int N = 1e5+5;
const dd eps = 1e-8;
const int mod = 1e9+7;
int n;
struct node{
dd x,y;
}a[1025];
dd dp[1025][1025];
dd dis(node p1,node p2){
dd dx = p1.x - p2.x;
dd dy = p1.y - p2.y;
dd ans = sqrt(dx*dx+dy*dy);
return ans;
}
int main(){
// freopen("input.txt","r",stdin);
while(scanf("%d",&n) == 1){
memset(dp,0x7a,sizeof(dp));
for(int i = 1;i <= n;i++){
scanf("%lf%lf",&a[i].x,&a[i].y);
}
dp[1][1] = 0;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= i;j++){
dp[i+1][j] = min(dp[i][j]+dis(a[i],a[i+1]),dp[i+1][j]);
dp[i+1][i] = min(dp[i][j]+dis(a[j],a[i+1]),dp[i+1][i]);
}
}
for(int i = 1;i <= n;i++) dp[n][n] = min(dp[n][n],dp[n-1][i]+dis(a[n-1],a[n])+dis(a[i],a[n]));
printf("%.2f\n",dp[n][n]);
}
return 0;
}
4
题意:求满足的的对数.
显然我们有,那么我们又有,我们就只需要类似筛法的过程把a和c弄出来再检查一下是否满足即可。这样做的复杂度是,然后再预处理一下处理询问就好了。
然而这样的复杂度还是过不了的。我们再继续观察一下。稍微打一下表能发现,那么我们还是用上面的方法只是判断的时候不需要看其的值而只需check是否满足即可。复杂度.
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double dd;
const int N = 3e7+5;
const dd eps = 1e-8;
const int mod = 1e9+7;
int t,n;
ll a[N];
int main(){
// freopen("input.txt","r",stdin);
for(int i = 1;i <= 3e7;i++){
for(int j = i+i;j <= 3e7;j+=i){
int b = (j-i);
if((b^j) == i){
a[j]++;
}
}
}
for(int i = 1;i <= 3e7;i++){
a[i] += a[i-1];
}
scanf("%d",&t);
int kase = 1;
while(t--){
scanf("%d",&n);
printf("Case %d: %lld\n",kase++,a[n]);
}
return 0;
}
5
题意:求个点,条边的生成树中,最大边权-最小边权最小的那个生成树。
只需要把边排序以后用尺取法暴力弄一下就好了。
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double dd;
const int N = 1e5+5;
const dd eps = 1e-8;
const int mod = 1e9+7;
int n,m,fa[1000];
struct node{
int u,v,w;
}a[N];
int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}
int main(){
// freopen("input.txt","r",stdin);
while(scanf("%d%d",&n,&m) == 2 and n){
for(int i = 1;i <= m;i++) scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
sort(a+1,a+1+m,[](node p1,node p2){return p1.w < p2.w;});
int ans = INT_MAX;
for(int i = 1;i <= m;i++){
for(int k = 1;k <= n;k++) fa[k] = k;
int j = i;
int cnt = n;
while(cnt > 1 and j <= m){
int x = find(a[j].u),y = find(a[j].v);
if(x != y){fa[x] = y;cnt--;}
j++;
}
j--;
if(cnt == 1) ans = min(ans,a[j].w-a[i].w);
}
if(ans == INT_MAX) puts("-1");
else printf("%d\n",ans);
}
return 0;
}