头像

zwu_2020015020




离线:10小时前


最近来访(7)
用户头像
edgdcgxgbx
用户头像
心安_7
用户头像
阳光大帅哥
用户头像
guankunkun
用户头像
古の回
用户头像
OneMorePuzzle
用户头像
旧尘丶


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6+5;

int primes[N],cnt;
int phi[N];
bool st[N];

void get_eulers(int n)  
{
   phi[1]=1;
   for(int i=2;i<=n;i++){
       if(!st[i]){
           primes[cnt++]=i;
           phi[i]=i-1;
       }
       for(int j=0;primes[j]<= n/i;j++){
           st[primes[j]*i]=true;
           if(i%primes[j]==0){
               phi[primes[j]*i] = phi[i]* primes[j]; 
               break;
           }
           phi[primes[j] * i] = phi[i] * (primes[j] - 1);
       }
   }
}

int main()
{
    int n;
    cin>>n;
    get_eulers(n);
    long long sum=0;
    for (int i = 1; i <= n; i ++ ) sum+=phi[i];
    cout << sum<<endl;
    return 0;
}



活动打卡代码 AcWing 873. 欧拉函数

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--){
        int a;
        cin>>a;
        int res=a;
        for (int i = 2; i <= a/i; i ++ ){
            if(a%i==0){
                res = res/i*(i - 1);
                while(a%i==0) a/=i;
            }
        }
        if(a>1) res=res/a*(a-1);
        cout<<res<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 873. 欧拉函数

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--){
        int a;
        cin>>a;
        int res=a;
        for (int i = 2; i <= a/i; i ++ ){
            if(a%i==0){
                res = res/i*(i - 1);
                while(a%i==0) a/=i;
            }
        }
        if(a>1) res=res/a*(a-1);
        cout<<res<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 872. 最大公约数

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int gcd(int a,int b){
    if(a%b==0) return b;
    return gcd(b,a%b);
}

int main()
{
    int n;
    cin>>n;
    while (n -- ){
        int a,b;
        cin>>a>>b;
        cout<<gcd(a,b)<<endl;
    }
}


活动打卡代码 AcWing 1934. 贝茜放慢脚步

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

vector<int>d,t;

int main()
{
    int n;
    cin>>n;
    char c;
    int x;
    while(n--){
        cin>>c>>x;
        if(c=='T') t.push_back(x);
        else d.push_back(x);
    }
    sort(t.begin(),t.end());
    sort(d.begin(),d.end());
    int v=1;
    int i=0,j=0;
    double T=0,len=0;
    while(i<d.size()&&j<t.size()){
        double t1 =  t[j] - T;
        double t2 = (d[i] - len)*v;
        if(t1==t2){
            T = t[j];
            len = d[i];
            v += 2;
            i++;
            j++;
        }
         else if(t1 < t2){//先到达减速时间
            len += (t[j] - T) / v;
            T = t[j];
            v++, j++;
        }
        else{//先到达减速位置
            T += (d[i] - len) * v;
            len = d[i];
            v++, i++;
        }
    }
    while(i<d.size()){
        T += (d[i] - len) * v;
        len = d[i];
        v++, i++;
    }
    while(j<t.size()){
        len += (t[j] - T) / v;
        T = t[j];
        v++, j++;
    }
    cout<<(int)(T + (1000 - len) * v + 0.500001)<<endl;
    return 0;
}


活动打卡代码 AcWing 2014. 岛

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>


using namespace std;

const int N = 1e5+5;
int a[N];
map<int,int>b;

int main()
{
    int n;
    cin>>n;
    for (int i = 1; i <= n; i ++ ){
        cin>>a[i];
        if(a[i]>a[i-1]){
            b[a[i-1]]++,b[a[i]]--;
        }
    }
    int ans=0,sum=0;
    for(auto &[x,v]:b){
        sum+=v;
        ans=max(sum,ans);
    }
    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 871. 约数之和

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>


using namespace std;

typedef long long LL;
const int mod =  1e9+7;

unordered_map<int,int> mp;

int main()
{
    int n;
    cin>>n;
    int x;
    while (n -- ){
        cin>>x;
        for(int i=2;i<=x/i;i++){
            while(x%i==0){
                x/=i;
                mp[i]++;
            }
        }
        if(x>1) mp[x]++;
    }
    LL ans=1;
    for(auto &[x,v]:mp){
       LL t=1;
       while(v--) t=(t*x+1)%mod;
       ans=ans*t%mod;
    }
    cout<<ans<<endl;
}


活动打卡代码 AcWing 870. 约数个数

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>


using namespace std;

typedef long long LL;
const int mod =  1e9+7;

unordered_map<int,int> mp;

int main()
{
    int n;
    cin>>n;
    int x;
    while (n -- ){
        cin>>x;
        for(int i=2;i<=x/i;i++){
            while(x%i==0){
                x/=i;
                mp[i]++;
            }
        }
        if(x>1) mp[x]++;
    }
    LL ans=1;
    for(auto &[x,v]:mp){
      ans=ans*(v+1)%mod;  
    }
    cout<<ans<<endl;
}


活动打卡代码 AcWing 2005. 马蹄铁

#include<bits/stdc++.h>
using namespace std;
const int N= 10;
char s[N][N];
int n;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
bool st[N][N];
int ans=0;
void dfs(int x,int y,int l,int r)
{

    if(l>0&&l==r)
    {
        ans=max(ans,l+r);
        return ;
    }
        for(int i=0;i<4;i++)
        {
            int xx=x+dx[i],yy=y+dy[i];
            if(xx<1||yy<1||xx>n||yy>n||st[xx][yy])continue;

            if(r>0&&s[xx][yy]=='(')
            {
                continue;
            }

            st[xx][yy]=true;

            if(s[xx][yy]=='(')dfs(xx,yy,l+1,r);
            else dfs(xx,yy,l,r+1);

            st[xx][yy]=false;//回溯

        }

    return ;

}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s[i]+1);
    }
    if(s[1][1]==')')
    {
        puts("0");
        return 0;
    }
    st[1][1]=true;
    dfs(1,1,1,0);
    cout<<ans<<endl;
    return 0;
}



算法1

(暴力枚举+二分查找)

先暴力枚举X和Y 然后通过条件确定中间的范围 然后找几头奶牛的位置在这个范围中间

时间复杂度

O(n^2*logn)

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e3+5;

int a[N];

int main()
{
    int n;
    cin>>n;
    int ans=0;
    for (int i = 0; i < n; i ++ ) cin>>a[i];
    sort(a,a+n);
    int l,r; //l=左边界 r=右边界
    for (int i = 0; i < n-2; i ++ ){ 
        for (int j = i+1; j < n-1; j ++ ){
            l=lower_bound(a,a+n,a[j]+a[j]-a[i])-a; //lower 找大于等于该数 输出地址 所以-a 就输出下标
            r=upper_bound(a,a+n,a[j]+2*(a[j]-a[i]))-a; //upper 找大于该数 输出地址 如果用lower找那还要判断这个点是不是在右边界
            ans+=r-l; //简化前:r-1 此时才是我们需要的下标 r-1-l+1 加上减去l 此时多减了一个l点 所以是r-l
        }
    }
    cout<<ans<<endl;
}