头像

粉红色的雪

西北大学


访客:986

离线:7小时前



class Solution {
public:
    vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
        vector<int> res;
        for(int i=0;i<index.size();i++)
        res.insert(res.begin()+index[i],nums[i]);
        return res;
    }
};



主要是分类和string的主要几个函数,大概是吧

https://blog.csdn.net/linwh8/article/details/50752733

#include<iostream>
#include<string>
using namespace std;
int main(){
    string::iterator it;
    int flag=0,sum=0,bitnum=0;//flag判断阶数±
    string s;
    cin>>s;
    int k=s.find("E");
    if(s[0]=='-') printf("-");
    if(s[k+1]=='-') flag=1;
    string a=s.substr(1,k-1);//取得底数
    string b=s.substr(k+2);//取得阶数
    for(int i=0;i<=b.size()-1;i++){
        sum=sum*10+b[i]-'0';
    }//计算阶数
    if(a[1]=='.'){
        it=a.begin()+1;
        a.erase(it);
    }//求有效数字
    bitnum=a.size();
    if(flag==0){
        for(int i=0;i<sum-(bitnum-1);i++){
            a+='0';
        }
        if(sum<bitnum){
            it=a.begin()+sum+1;
            a.insert(it,'.');
        }
    }else{
            for(int i=0;i<sum;i++){
                it=a.begin();
                a.insert(it,'0');
            }
            it=a.begin()+1;
            a.insert(it,'.');
        }
    cout<<a<<endl;
    return 0;
}



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

const int N=510;

int g[N][N];    //为稠密阵所以用邻接矩阵存储
int dist[N];    //用于记录每一个点距离第一个点的距离
bool st[N];     //用于记录该点的最短距离是否已经确定

int n,m;

int Dijkstra()
{
    memset(dist, 0x3f,sizeof dist);     //初始化距离  0x3f代表无限大

    dist[1]=0;  //第一个点到自身的距离为0

    for(int i=0;i<n;i++)      //有n个点所以要进行n次 迭代
    {
        int t=-1;       //t存储当前访问的点

        for(int j=1;j<=n;j++)   //这里的j代表的是从1号点开始
            if(!st[j]&&(t==-1||dist[t]>dist[j]))     
                t=j;

        st[t]=true;   

        for(int j=1;j<=n;j++)           //依次更新每个点所到相邻的点路径值
            dist[j]=min(dist[j],dist[t]+g[t][j]);
    }

    if(dist[n]==0x3f3f3f3f) return -1;  //如果第n个点路径为无穷大即不存在最低路径
    return dist[n];
}
int main()
{
    cin>>n>>m;

    memset(g,0x3f,sizeof g);    //初始化图 因为是求最短路径
                                //所以每个点初始为无限大

    while(m--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        g[x][y]=min(g[x][y],z);     //如果发生重边的情况则保留最短的一条边
    }

    cout<<Dijkstra()<<endl;
    return 0;
}






LL gcd_sub(LL a, LL b)
{
    if (a < b) swap(a, b);
    if (b == 1) return a;
    return gcd_sub(b, a / b);
}
LL gcd(LL a, LL b)
{
    return b ? gcd(b, a % b) : a;
}

gcd_sub的作用是?



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

#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int q[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    while (m -- )
    {
        int x;
        scanf("%d", &x);

        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }

        if (q[l] != x) cout << "-1 -1" << endl;
        else
        {
            cout << l << ' ';

            int l = 0, r = n - 1;
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }

            cout << l << endl;
        }
    }

    return 0;
}


活动打卡代码 AcWing 905. 区间选点

#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct ra{
  int l,r;
  bool operator< (const ra &A)const{
      return  r<A.r;
  }
}rr[100050];
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>rr[i].l>>rr[i].r;
    sort(rr,rr+n);
    int res=0,ed=-1e9;
    for(int i=0;i<n;i++){
        if(ed<rr[i].l){
            res++;
            ed=rr[i].r;
        } 
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 143. 最大异或对

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 3000000;

int n;
int a[N], son[M][2], idx;

void insert(int x)
{
    int p = 0;
    for (int i = 30; i >= 0; i -- )
    {
        int s = son[p][x >> i & 1];
        if (!s) s = ++ idx;
        p = s;
    }
}

int search(int x)
{
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i -- )
    {
        int &s = x >> i & 1;
        if (son[p][!s])
        {
            res += 1 << i;
            p = son[p][!s];
        }
        else p = son[p][s];
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d", &a[i]);
        insert(a[i]);
    }

    int res = 0;
    for (int i = 0; i < n; i ++ ) res = max(res, search(a[i]));

    printf("%d\n", res);

    return 0;
}


活动打卡代码 AcWing 1018. 最低通行费

#include<iostream>
#include<algorithm>
using namespace std;
int f[105][105];
int mp[105][105];
int main(){
        int r,x;
        cin>>r;
        for(int i=1;i<=r;i++){
            for(int j=1;j<=r;j++){
                cin>>x;
                mp[i][j]=x;
            }
        }
        for(int i=1;i<=r;i++){
            for(int j=1;j<=r;j++){
                if(i>1&&j>1)
                f[i][j]=min(f[i][j-1]+mp[i][j],f[i-1][j]+mp[i][j]);
                else if(i==1) f[i][j]=f[i][j-1]+mp[i][j];
                else f[i][j]=f[i-1][j]+mp[i][j];
            }
        }
        cout<<f[r][r]<<endl;
        return 0;
}


活动打卡代码 AcWing 831. KMP字符串

#include<iostream>
using namespace std;
const int N=100010,M=1000010;
int n,m;
char p[N],s[M];
int ne[N];
int main(){
    cin>>n>>p+1>>m>>s+1;
    for(int i=2,j=0;i<=n;i++){
        while(j&&p[j+1]!=p[i]) j=ne[j];
        if(p[i]==p[j+1]) j++;
        ne[i]=j;
    }
    for(int i=1,j=0;i<=m;i++){
        while(j&&s[i]!=p[j+1]) j=ne[j];
        if(s[i]==p[j+1]) j++;
        if(j==n){
            cout<<i-n<<" ";
            j=ne[j];
        }
    }
    return 0;
}


活动打卡代码 AcWing 1015. 摘花生

#include<iostream>
#include<algorithm>
using namespace std;
int f[105][105];
int mp[105][105];
int main(){
    int t;
    cin>>t;
    while(t--){
        int r,c,x;
        cin>>r>>c;
        for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                cin>>x;
                mp[i][j]=x;
            }
        }
        for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                f[i][j]=max(f[i][j-1],f[i-1][j])+mp[i][j];
            }
        }
        cout<<f[r][c]<<endl;
    }
    return 0;
}