头像

一抹斜阳


访客:4381

离线:9天前


活动打卡代码 AcWing 1219. 移动距离

#include <iostream>
#include <cmath>
using namespace std;

int res;
int w,m,n;
int c1,c2;
int r1,r2;


int main(){

    cin>>w>>m>>n;

    if(m % w == 0)
        r1 =  m / w ;
    else
        r1 = m / w + 1;
    if(n % w == 0)
        r2 =  n / w ;
    else
        r2 = n / w + 1;


    if(r1 % 2 == 0)
        c1 = w - (m - (r1-1) * w) + 1;
    else 
        c1 = m - (r1-1) * w;

    if(r2 % 2 == 0)
        c2 = w - (n - (r2-1) * w) + 1 ;
    else 
        c2 = n - (r2-1) * w;  
    cout<<abs(r1 - r2) + abs(c1 - c2)<<endl;
    return 0;
}



#include <iostream>
#include <cmath>
using namespace std;

int res;
int w,m,n;
int c1,c2;
int r1,r2;


int main(){

    cin>>w>>m>>n;

    if(m % w == 0)
        r1 =  m / w ;
    else
        r1 = m / w + 1;
    if(n % w == 0)
        r2 =  n / w ;
    else
        r2 = n / w + 1;


    if(r1 % 2 == 0)
        c1 = w - (m - (r1-1) * w) + 1;
    else 
        c1 = m - (r1-1) * w;

    if(r2 % 2 == 0)
        c2 = w - (n - (r2-1) * w) + 1 ;
    else 
        c2 = n - (r2-1) * w;  
    cout<<abs(r1 - r2) + abs(c1 - c2)<<endl;
    return 0;
}


活动打卡代码 AcWing 1204. 错误票据

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e4 + 10;
int a[N],t[N];
int n,x,i;
int p,q;

int main(){

    cin>>n;
    while(n--){
        while(cin>>x){
            a[i++] = x;
        }
    }

    sort(a,a+i);

    for(int j = 0;j<i;j++){
        t[a[j]-a[0]]++;
    }
    for(int j = 0;j<i;j++){
        if(t[j] == 0)
            p = a[0] + j;
        if(t[j] == 2)
            q = a[0] + j;

    }

    cout<<p<<" "<<q<<endl;
    return 0;

}


活动打卡代码 AcWing 1245. 特别数的和

include [HTML_REMOVED]

using namespace std;

int n,x;
long long res;

int main(){

cin>>n;
for(int i = 1;i<=n;i++){

    x = i;
    while(x){
        if(x % 10 == 2 || x % 10 == 0 || x % 10 == 9 || x % 10 == 1){
            res += i;
            break;
        }
        x /= 10;
    }
}


cout<<res<<endl;
return 0;

}



活动打卡代码 AcWing 1236. 递增三元组

思路:1≤i,j,k≤N Ai<Bj<Ck可以枚举Bj,然后在Ai中找到最大的满足<Bj的,Ck中找最小满足的(找的时候用二分找)

#include <iostream>
#include <algorithm>

using namespace std;

long long ll = 1;

int n;
const int N = 1e5 + 10;
int a[N],b[N],c[N];
long long res;

int main(){


    cin>>n;
    for(int i = 0;i<n;i++)
        scanf("%d",&a[i]);

    for(int i = 0;i<n;i++)
        scanf("%d",&b[i]);

    for(int i = 0;i<n;i++)
        scanf("%d",&c[i]);

    sort(a,a+n);
    sort(b,b+n);
    sort(c,c+n);

    for(int i = 0;i<n;i++){

        int l = -1,r = n-1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(a[mid] < b[i])
                l = mid ;
            else
                r = mid - 1;

        }

        int t = l + 1;

        l = 0,r = n;
        while(l < r){
            int mid = l + r >> 1;
            if(c[mid] > b[i])
                r = mid;
            else
                l = mid +1;
        }


        res += ll*t * (n-l );

    }

    cout<<res<<endl;
    return 0;
}



思路:1≤i,j,k≤N Ai<Bj<Ck可以枚举Bj,然后在Ai中找到最大的满足<Bj的,Ck中找最小满足的(找的时候用二分找)

#include <iostream>
#include <algorithm>

using namespace std;

long long ll = 1;

int n;
const int N = 1e5 + 10;
int a[N],b[N],c[N];
long long res;

int main(){


    cin>>n;
    for(int i = 0;i<n;i++)
        scanf("%d",&a[i]);

    for(int i = 0;i<n;i++)
        scanf("%d",&b[i]);

    for(int i = 0;i<n;i++)
        scanf("%d",&c[i]);

    sort(a,a+n);
    sort(b,b+n);
    sort(c,c+n);

    for(int i = 0;i<n;i++){

        int l = -1,r = n-1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(a[mid] < b[i])
                l = mid ;
            else
                r = mid - 1;

        }

        int t = l + 1;

        l = 0,r = n;
        while(l < r){
            int mid = l + r >> 1;
            if(c[mid] > b[i])
                r = mid;
            else
                l = mid +1;
        }


        res += ll*t * (n-l );

    }

    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 1210. 连号区间数

#include <iostream>
using namespace std;

int n,res;
const int N = 1e4 + 10;
int p[N];
int maxp,minp;

int main(){



    cin>>n;
    for(int i = 1;i<=n;i++)
        scanf("%d",&p[i]);

    for(int i = 1;i<=n;i++){
        maxp = p[i];
        minp = p[i];
        for(int j = i;j<=n;j++){

            maxp = max(maxp,p[j]);
            minp = min(minp,p[j]);
            if(maxp - minp == j - i)
                res++;
        }
    }



    cout<<res;
    return 0;
}



活动打卡代码 AcWing 1230. K倍区间

#include <iostream>
using namespace std;

int n,k;
const int N = 1e5 + 10;
int a[N];
long long sum[N];
int ans[N];

int main(){

    cin>>n>>k;
    for(int i = 1;i<=n;i++){
        scanf("%d",&a[i]);
        sum[i] = sum[i-1] + a[i];
    }

    //l  1-n,  r 1-n   (r - l)%k == 0 即r%k == l%k 时,可以让r固定,找左端点中与r%k相等的

    long long res = 0;
    ans[0] = 1;
    for(int i = 1;i<=n;i++){

        res += ans[sum[i] % k];     //l在0 - r-1之间余数为k的
        ans[sum[i] % k]++;

    }

    cout<<res<<endl;
    return 0;
}



活动打卡代码 AcWing 1227. 分巧克力

#include <iostream>
#include <algorithm>

using namespace std;

int n,k;
const int N = 1e5 + 10;

int h[N],w[N],ans[N];

bool check(int a){
    int sum = 0;
    for(int i = 0;i<n;i++){
        sum += (h[i]/a) * (w[i]/a);
        if(sum >= k)
            return true;
    }

    return false;


}
int main(){

    cin>>n>>k;
    for(int i = 0;i<n;i++)
        scanf("%d %d",&h[i],&w[i]);

    int l = 1,r = 1e5;
    while(r > l){
        int mid = l + r + 1>> 1;
        if(check(mid))
            l = mid;
        else
            r = mid - 1;
    }

    cout<<l<<endl;
    return 0;
}



活动打卡代码 AcWing 1221. 四平方和

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int n,m;


const int N = 2500010;

struct sum{
    int s,c,d;
    bool operator <(const sum &t) const{
        if(s != t.s)
            return s < t.s;
        if(c != t.c)
            return c < t.c;
        return d < t.d;
    }
}sum[N];



int main(){


    cin>>n;
    for(int c = 0;c*c<=n;c++)
        for(int d = c;d*d + c*c <=n;d++)
            sum[m++] = {c*c + d*d,c,d};
    sort(sum,sum+m);

    for(int a = 0;a<=n;a++)
        for(int b = a;b*b + a*a <= n;b++){
            int t = n - a*a - b*b;

            int l = 0,r = m-1;
            while(l < r){
                int mid = l + r >> 1;
                if(sum[mid].s >= t)
                    r = mid;
                else
                    l = mid + 1;
                if(sum[l].s == t){

                    printf("%d %d %d %d",a,b,sum[l].c,sum[l].d);

                    return 0;
                }
            }
        }

    return 0;
}