写题记录1

记录一些有意思的题

1

题意：求\(\sum_{i=1}^{n}f(i)\),其中\(f(x)\)是能够整除\(x\)的数的中位数向下取整的大小

我们知道除了平方因子，其他因子都是成对出现的，显然我们可以直接通过筛法找因子的过程中把这些成对的因子动态更新一下就好了，复杂度\(\mathcal{O}({n\log{n}\log{n}})\)

#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

题意：求\(A\le x\le B\le y\le C\le z\le D\)中\((x,y,z)\)组成三角形的数量。数量级：\(5·10^5\)

思路，我们先枚举\(x\)，然后可以发现\(x+y\in[i+B,i+C]\)，这种式子显然可以直接差分维护，之后再跑一次前缀和，枚举\(y\)即可。

#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

题意：给出一些点\((n \le 1000)\),且这些点按\(x\)排序给出，从\(1\)点出发，到达\(n\)点再经过其他点回到\(1\)点，经过其他点仅一次的方案数。

可以通过dp，设\(dp[i][j]\)表示当前在\(i,j(i > j)\)的两个人，那么显然状态只能转移到\(dp[i+1][j]+dis(p_i,p_{i+1})\)和\(dp[i+1][i]+dis(p_j,p_{i+1})\)，然后注意边界\(dp[n][n] = dp[n-1][i] + dis(p_{n-1},p_{n})+dis(p_i,p_{n})\)即可。

#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

题意：求满足\(\gcd(i,j) = (i \space xor \space j),1\le i,j \le 3e7\)的\((i,j)\)的对数\((i < j)\).

显然我们有\(a \space xor \space b = c \rightarrow a \space xor \space c = b\)，那么我们又有\(c |a\)，我们就只需要类似筛法的过程把a和c弄出来再检查一下是否满足\(\gcd(a,b) = a \space xor \space b\)即可。这样做的复杂度是\(\mathcal{O}(n(\log{n})^2)\),然后再预处理一下处理询问就好了。

然而这样的复杂度还是过不了的。我们再继续观察一下。稍微打一下表能发现\(j-i = \gcd(i,j)\),那么我们还是用上面的方法只是判断的时候不需要看其\(\gcd\)的值而只需check是否满足\(（j-i)xor\space j = i\)即可。复杂度\(\mathcal{O}(n\log{n})\).

#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

题意：求\(n(n \le 1000)\)个点，\(m(m\le\frac{n\times (n+1)}{2})\)条边的生成树中，最大边权-最小边权最小的那个生成树。

只需要把边排序以后用尺取法暴力弄一下就好了。

#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;
}