头像

Jocelin




离线:9小时前


活动打卡代码 AcWing 429. 奖学金

Jocelin
9小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310;

int n;
struct Person
{
    int id, sum, a, b, c;
    bool operator< (const Person& t) const
    {
        if (sum != t.sum) return sum > t.sum;
        if (a != t.a) return a > t.a;
        return id < t.id;
    }
}q[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        q[i] = {i, a + b + c, a, b, c};
    }

    sort(q + 1, q + n + 1);

    for (int i = 1; i <= 5; i ++ )
        cout << q[i].id << ' ' << q[i].sum << endl;

    return 0;
}




活动打卡代码 AcWing 422. 校门外的树

Jocelin
10小时前

1、刷数组 nm的复杂度与

#include<iostream>


using namespace std;


#define N 10010

int a[N];

int L,n;
int main()
{
    cin >> L >> n;
    for(int i =0;i<=L;i++)
    {
        a[i] = 1;
    }

    while(n--)
    {
        int l,r;
        cin >> l >> r;
        for(int j = l; j <=r;j++)
        {
            a[j] = 0;
        }

    }
    int res=0;
    for(int i =0;i<=L;i++)
    {
        if(a[i])
         res++;
    }
    cout << res << endl;
    return 0;
}

2、区间合并 mlogm

合并区间后就可以得到一些互不相交的区间

#include<bits/stdc++.h>


using namespace std;


#define N 10010

int a[N];

int L,n;
pair<int,int> rec[110];

vector<pair<int,int>> mer;
int main()
{
    cin >> L >> n;
    for(int i =0;i<=L;i++)
    {
        a[i] = 1;
    }

    for(int i =0;i<n;i++)
    {
        int l,r;
        cin >> l >> r;
        rec[i].first = l;
        rec[i].second = r;

        // cout << rec[i].first << " " << rec[i].second << endl; 
    }

    sort(rec,rec+n); //按照左端点排序
    int start = rec[0].first;
    int end = rec[0].second;
    for(int i = 1; i <n;i++)
    {
        if( rec[i].first > end)  //当前当前区间的左端点大于上一个区间的右端点
        {
            mer.push_back(make_pair(start,end)); //插入到结果中
            start = rec[i].first ; //更新start 和end 起点
            end = rec[i].second; 
        }
        else //否则更新一下右端点,因为我们只排序了左边,右边没有排序,我们还是放最大的那一个右端点
        {
            end = max(rec[i].second,end);
        }
    }
    mer.push_back(make_pair(start,end));

    int cnt = 0;
    for(int i = 0; i < mer.size();i++)
    {

        cnt += mer[i].second - mer[i].first + 1;
    }


    cout << L+1 - cnt << endl;
    return 0;
}


活动打卡代码 AcWing 756. 蛇形矩阵

Jocelin
12小时前
//撞墙: 重复+边界 
//改变方向即可


#include<iostream>


using namespace std;


#define N 
int res[100][100];


int dx[4] = {0,1,0,-1}; //四个xy排列顺序是按照螺旋方式排列的 左->下->右->上
int dy[4] = {1,0,-1,0};
int n,m;
int main()
{
    cin >> n >> m;

    for(int x =0,y=0,d=0,k=1;k<=n*m;k++)
    {
        res[x][y] = k;
        int a = x + dx[d],b = y+ dy[d];
        if(a < 0 || a>=n || b < 0 || b>=m || res[a][b]!=0 ) //求出当前的a,b不符合要求
        {
            d = (d+1)%4; //改变方向
            a = x + dx[d],b = y+ dy[d]; //重新计算一下坐标
        }
        x = a;
        y = b; 
    }

    //打印
    for(int i = 0 ; i < n;i++)
    {
        for(int j = 0 ; j < m;j++)
        {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}


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

Jocelin
12小时前
#include<bits/stdc++.h>


using namespace std;
typedef pair<int,int> PII;
#define  x first
#define  y second

#define N 100010
PII rec[N];



int n,k;

int check(int len)
{
    int res = 0;
    for(int i = 0; i < n;i++)
    {
        res+= ( rec[i].x / len ) *  ( rec[i].y / len );
    }
    return res;
}

int main()
{
    cin >> n >> k;
    for(int i = 0; i < n;i++)
    {
        scanf("%d%d",&rec[i].x,&rec[i].y);
    }
    int left = 1;
    int right = 1e5;

    while(left < right) //右边边界二分
    {
        int mid = ( left+ right ) / 2;

        if( check(mid) >= k)
            left = mid + 1;
        else 
            right = mid;

    }

    cout << left-1  << endl;

    return 0;
}


活动打卡代码 AcWing 680. 剪绳子

Jocelin
14小时前
//转换成 求出 多长的绳子可以切除多少条

#include<iostream>

using namespace std;
#define N 100010

int l[N];
int n,m;

int check(double len) //可以减多少条
{
    int res = 0;
    for(int i = 0; i < n;i++)
    {
        res += l[i] / len;
    }
    return res;
}

int main()
{


    cin >> n >> m;

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

    double left = 0;
    double right = 1e9;

    while( right - left > 1e-4)
    {
        double mid = left + (right - left) / 2;
        if( check(mid) < m ) //当前减的条数不够
            right = mid;
        else
            left = mid;
    }

    printf("%.2lf",left);


    return 0;
}




活动打卡代码 AcWing 1346. 回文平方

Jocelin
15小时前

1、10进制转换成其他进制 (短除法) 下面的base函数
2、其他进制转换成10进制 (秦九韶算法) 下面的base_n_to_10函数
(1101)2转换成10进制 (x =2 )
an an-1 …a1 a0 = an * 2^n + an-1 * 2^n-1 + … + a1 * 2^1 + a0 * 2^0
= ( (anx + an-1)x + an-2 ) * x + an-1 …
3、其他进制转化成其他进制
(1) 用十进制过渡
(2) 短除法
(3) 扩展题:AcWing 124. 数的进制转换

#include<bits/stdc++.h>
#include <cstdlib>


using namespace std;

char get(int n) //如果是11 就返回B
{
    if( n <= 9)
        return n + '0';
    return n - 10 + 'A';
}

string base(int n,int b)//一个数n在B进制下的表示
{
    string num;
    while(n)
    {
        num += get(n % b); //一个数模上b进制 也就是除以这个b进制的余数,get把当前数字转换成char
        n /= b;
    }
    reverse(num.begin(),num.end());
    return num;
}
/****   其他进制转换成
int uget(char c) //字符转换成数字
{
    if( c <= '9' )
        return c - '0';
    return c - 'A' + 10;
}

string base_n_to_10(string num,int b) //一个进制的数转换成10进制
{
    int res = 0;
    for(auto c : num )
    {
        res = res * b + uget(c);
    }
    return res;
}


bool check(string num) //判断回文数
{
    //双指针对撞判断
    for(int i = 0 ,j = num.size() -1 ; i<j ;i++,j--)
    {
        if(num[i] != num[j])
            return false;
    }
    return true;
}

int main()
{

    int b;
    cin >> b;
    for(int i = 1;i <=300;i++)
    {
        auto num = base(i*i,b); //一个数的平方在B进制下的结果  
        if( check(num) ) //这个数数的平方转化为 B 进制后,其 B 进制表示是回文数字。
        {
            cout << base(i,b) << " " << num << endl;
        }

    }

    return 0;
}


活动打卡代码 AcWing 1113. 红与黑

Jocelin
20小时前
#include<bits/stdc++.h>

using namespace std;

const int N = 25;

typedef pair<int,int> PII;
#define x first
#define y second

int n,m; //n表示行,h表示列

char g[N][N];
bool st[N][N];

int dx[4] = {-1,1,0,0}; 
int dy[4] = { 0,0,1,-1};



int bfs(PII start)
{
    int res = 1;
    queue<PII> q;

    memset(st,0,sizeof st);

    q.push(start);
    st[start.x][start.y] = 1;
    while(q.size())
    {

        int que_size = q.size();

        for(int i = 0; i <que_size;i++)
        {
            PII temp = q.front();
            q.pop();
            int x = temp.x;
            int y = temp.y;
            for(int j =0; j<4;j++)
            {
                int a = x + dx[j];
                int b = y + dy[j];
                if( a <0 || a>=n || b<0||b>=m || st[a][b] ) continue;
                if( g[a][b] !='.' ) continue;

                q.push({a,b});
                st[a][b] = 1;
                res++;
            }

        }


    }
    return res;

}


int main()
{ 
   while(scanf("%d%d",&m,&n), n|m)
   {
       PII start;

        for(int i=0;i<n;i++)
        {
            scanf("%s",g[i]);
        }
        for(int i=0;i<n;i++)
        {
            for(int j =0;j<m;j++)
            {
                // printf("%c",g[i][j]);
                if(g[i][j] == '@')
                {
                    start = {i,j};
                    break;
                }
            }
            // cout << endl;
        }


        cout << bfs(start) << endl;


   }

    return 0;
}




活动打卡代码 AcWing 756. 蛇形矩阵

Jocelin
21小时前
//撞墙: 重复+边界 
//改变方向即可


#include<iostream>


using namespace std;


#define N 
int res[100][100];


int dx[4] = {0,1,0,-1}; //四个xy排列顺序是按照螺旋方式排列的 左->下->右->上
int dy[4] = {1,0,-1,0};
int n,m;
int main()
{
    cin >> n >> m;

    for(int x =0,y=0,d=0,k=1;k<=n*m;k++)
    {
        res[x][y] = k;
        int a = x + dx[d],b = y+ dy[d];
        if(a < 0 || a>=n || b < 0 || b>=m || res[a][b]!=0 ) //求出当前的a,b不符合要求
        {
            d = (d+1)%4; //改变方向
            a = x + dx[d],b = y+ dy[d]; //重新计算一下坐标
        }
        x = a;
        y = b; 
    }

    //打印
    for(int i = 0 ; i < n;i++)
    {
        for(int j = 0 ; j < m;j++)
        {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}


活动打卡代码 AcWing 755. 平方矩阵 III

Jocelin
21小时前
#include<iostream>


using namespace std;


int main()
{
    int n;
    while (scanf("%d",&n) ,n!=0)
    {
        for(int i = 1; i <=n;i++)
        {
            for(int j = 1; j <=n;j++)
            {
                cout << (1<<(i+j-2)) << " ";
            }
            cout << endl;
        }

        cout << endl;
    }


    return 0;
}




活动打卡代码 AcWing 754. 平方矩阵 II

Jocelin
21小时前
//直接求当前到斜对角线的距离即可
#include<iostream>


using namespace std;


int main()
{
    int n;
    while (scanf("%d",&n) ,n!=0)
    {
        for(int i = 1; i <=n;i++)
        {
            for(int j = 1; j <=n;j++)
            {
                cout << abs( j-i) + 1 << " ";
            }
            cout << endl;
        }

        cout << endl;
    }


    return 0;
}