头像

Conan_2009




离线:2小时前


活动打卡代码 AcWing 790. 数的三次方根

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
double n;
double lf(double x){return x*x*x;}
int main(){
    cin>>n;
    double l=-10000,r=10000;
    while(r-l>=1e-7){
        double mid=(l+r)/2;
        if(lf(mid)>=n) r=mid;
        else l=mid;
    }
    cout<<fixed<<setprecision(6)<<l;
    return 0;
}


活动打卡代码 AcWing 789. 数的范围

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
int n,q,a[1000000];
int main(){
    scanf("%d%d",&n,&q);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    while(q--){
        int k;
        scanf("%d",&k);
        int l=0,r=n-1,mid=0;
        while(l<r){
            mid=(l+r)/2;
            if(a[mid]<k) l=mid+1;
            else r=mid;
        }
        if(a[l]!=k){
            printf("-1 -1\n");
            continue;
        }
        int l1=1,r1=n;
        while(l1+1<r1){
            mid=(l1+r1)/2;
            if(a[mid]<=k) l1=mid;
            else r1=mid;
        }
        cout<<l<<' '<<l1<<'\n';
    }
    return 0;
}


活动打卡代码 AcWing 788. 逆序对的数量

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
long long n,a[1000000],tmp[1000000],res;
void merge_sort(long long q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else res+=mid-i+1,tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    merge_sort(a,1,n);
    cout<<res;
    return 0;
}


活动打卡代码 AcWing 787. 归并排序

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
int n,a[1000000],tmp[1000000];
void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    merge_sort(a,1,n);
    for(int i=1;i<=n;i++)
        cout<<a[i]<<" ";
    return 0;
}


活动打卡代码 AcWing 786. 第k个数

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
int n,a[1000000],k;
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[(l+r)/2];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    quick_sort(a,1,n);
    cout<<a[k];
    return 0;
}


活动打卡代码 AcWing 785. 快速排序

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
int n,a[1000000];
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    quick_sort(a,1,n);
    for(int i=1;i<=n;i++)
        cout<<a[i]<<' ';
    return 0;
}



#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int,int> Pair; // 值与下标 
const int N=100010;
int n,m,query;
int h[N],e[N<<1],ne[N<<1],idx; // 邻接表 
int dist[N][2]; // 长度 
Pair q[N*2]; // 队列 
void add(int a,int b){ // 邻接表加边
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void bfs(){ // 预处理(BFS) 
    memset(dist,0x3f,sizeof(dist)); // 初距离始化为正无穷 
    int hh=0,tt=0;
    q[0]={1,0},dist[1][0]=0; // 初始化队列起点 
    while(hh<=tt){ // 遍历 
        Pair t=q[hh++];
        int ver=t.first,type=t.second; // ver与type为当前点编号
        for(int i=h[ver];~i;i=ne[i]){ // 遍历邻接表表邻边 
            int j=e[i]; // 取出邻边编号 
            if(dist[j][type^1]>dist[ver][type]+1){ // 如果走一步的长度大于dist[j][type]+1
                /*注:由于走一步就会变一下奇偶性,所以要用type^1*/ 
                dist[j][type^1]=dist[ver][type]+1;
                q[++tt]={j,type^1};
                /* 刷新并将点更新到队列中 */ 
            }
        }
    }
} 
int main(){
    cin.tie(0);
    memset(h,-1,sizeof(h)); // 邻接表初始化 
    cin>>n>>m>>query;
    for(int i=1;i<=m;i++){  
        int a,b;
        cin>>a>>b;
        add(a,b); // 加边 
        add(b,a); // 无向图加两次 
    }
    bfs(); // 预处理(BFS)
    while(query--){ // 循环处理工单 
        int a,l;
        cin>>a>>l; 
        if(a==1&&h[1]==-1) puts("No"); // 特判
        else if(dist[a][l&1]<=l) puts("Yes"); // 如果存在与L同奇偶性且比L小的路径,表示需要提供原材料 
        else puts("No"); // 如果不存在,表示不需要生产原材料
    }
    return 0;
}
/*
    注:本程序使用拆点法,将一个点拆成一个偶点和
    一个奇点,然后预处理偶点到偶点的最短距离与偶点
    到奇点的最短距离,最后再进行判断 
*/

/*
在新图中(拆点后的图),所有从1(偶)走到v(偶)的路径,对应的是原图中所有从1走到v的长度是偶数的路径。 
在新图中(拆点后的图),所有从1(偶)走到v(奇)的路径,对应的是原图中所有从1走到v的长度是奇数的路径。 

因此,在新图中,从1(偶)走到v(偶)的最短路,就是从1走到v的长度是偶数的所有路径中的最短路径, 
从1(偶)走到v(奇)的最短路,就是从1走到v的长度是奇数的所有路径中的最短路径

dist[v][0] : 1 ~ v 偶数路径最短路
dist[v][1] : 1 ~ v 奇数路径最短路
a,L
L是奇数,L>=dist[a][0]
L是偶数  L>=dist[a][1]
*/


活动打卡代码 AcWing 1164. 加工零件

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int,int> Pair; // 值与下标 
const int N=100010;
int n,m,query;
int h[N],e[N<<1],ne[N<<1],idx; // 邻接表 
int dist[N][2]; // 长度 
Pair q[N*2]; // 队列 
void add(int a,int b){ // 邻接表加边
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void bfs(){ // 预处理(BFS) 
    memset(dist,0x3f,sizeof(dist)); // 初距离始化为正无穷 
    int hh=0,tt=0;
    q[0]={1,0},dist[1][0]=0; // 初始化队列起点 
    while(hh<=tt){ // 遍历 
        Pair t=q[hh++];
        int ver=t.first,type=t.second; // ver与type为当前点编号
        for(int i=h[ver];~i;i=ne[i]){ // 遍历邻接表表邻边 
            int j=e[i]; // 取出邻边编号 
            if(dist[j][type^1]>dist[ver][type]+1){ // 如果走一步的长度大于dist[j][type]+1
                /*注:由于走一步就会变一下奇偶性,所以要用type^1*/ 
                dist[j][type^1]=dist[ver][type]+1;
                q[++tt]={j,type^1};
                /* 刷新并将点更新到队列中 */ 
            }
        }
    }
} 
int main(){
    cin.tie(0);
    memset(h,-1,sizeof(h)); // 邻接表初始化 
    cin>>n>>m>>query;
    for(int i=1;i<=m;i++){  
        int a,b;
        cin>>a>>b;
        add(a,b); // 加边 
        add(b,a); // 无向图加两次 
    }
    bfs(); // 预处理(BFS)
    while(query--){ // 循环处理工单 
        int a,l;
        cin>>a>>l; 
        if(a==1&&h[1]==-1) puts("No"); // 特判
        else if(dist[a][l&1]<=l) puts("Yes"); // 如果存在与L同奇偶性且比L小的路径,表示需要提供原材料 
        else puts("No"); // 如果不存在,表示不需要生产原材料
    }
    return 0;
}
/*
    注:本程序使用拆点法,将一个点拆成一个偶点和
    一个奇点,然后预处理偶点到偶点的最短距离与偶点
    到奇点的最短距离,最后再进行判断 
*/

/*
在新图中(拆点后的图),所有从1(偶)走到v(偶)的路径,对应的是原图中所有从1走到v的长度是偶数的路径。 
在新图中(拆点后的图),所有从1(偶)走到v(奇)的路径,对应的是原图中所有从1走到v的长度是奇数的路径。 

因此,在新图中,从1(偶)走到v(偶)的最短路,就是从1走到v的长度是偶数的所有路径中的最短路径, 
从1(偶)走到v(奇)的最短路,就是从1走到v的长度是奇数的所有路径中的最短路径

dist[v][0] : 1 ~ v 偶数路径最短路
dist[v][1] : 1 ~ v 奇数路径最短路
a,L
L是奇数,L>=dist[a][0]
L是偶数  L>=dist[a][1]
*/


活动打卡代码 AcWing 1163. 纪念品

#include <iostream>
#include <cstring>
using namespace std;
int t,n,m;
int p[1000][1000],tmp[100000];
int main(){
    cin.tie(0);
    scanf("%d%d%d",&t,&n,&m);
    for(int i=1;i<=t;i++)
        for(int j=1;j<=n;j++)
            cin>>p[i][j];
    for(int i=1;i<t;i++){
        memset(tmp,0,sizeof(tmp));
        for(int j=1;j<=n;j++)
            if(p[i+1][j]>p[i][j])
                for(int k=p[i][j];k<=m;k++)
                    tmp[k]=max(tmp[k],tmp[k-p[i][j]]+p[i+1][j]-p[i][j]);
        m+=tmp[m];
    }
    cout<<m;
    return 0;
}


活动打卡代码 AcWing 1162. 公交换乘

#include <iostream>
#include <cstdio>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
struct huangxutao{ int time,price,flag; }a[100000];
int n,ans;
inline void debug(int x){cout<<x<<'\n';}
int main(){
    cin.tie(0);
    cin>>n;
    int l=1,r=0;
    for(int i=1;i<=n;i++){
        int chuxing,Time,Price;
        cin>>chuxing>>Price>>Time;
        if(!chuxing)
            a[++r]={Time,Price,1},ans+=Price;
        else{
            while(l<r&&Time-a[l].time>45) l++;
            bool pan=true;
            for(int j=l;j<=r;j++)
                if(a[j].price>=Price&&a[j].flag){
                    pan=false;
                    a[j].flag=0;
                    break;
                }
            if(pan)
                ans+=Price;
        }
//      debug(ans);
    }
    cout<<ans;
    return 0;
}