头像

我也想成为钢铁侠呀

嘻嘻




离线:1小时前


最近来访(5)
用户头像
北海没有WA
用户头像
小余锅锅
用户头像
acwhr
用户头像
吸猪


//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



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

using namespace std;

const int N = 110;
const double eps = 1e-8;

int n;
double a[N][N];

int gauss()  // 高斯消元,答案存于a[i][n]中,0 <= i < n
{
    int c, r;//col表示哪一列,row表示行
    for (c = 0, r = 0; c < n; c ++ )
    {
        int t = r;
        for (int i = r; i < n; i ++ )  // 找绝对值最大的行
            if (fabs(a[i][c]) > fabs(a[t][c]))
                t = i;

        //如果最大的值也是零,
        if (fabs(a[t][c]) < eps) continue;
        //经过上述操作,我们找到了第r行中第j列的最大值

        //把有最大值的这一行跟顶端交换 
        for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]);  // 将绝对值最大的行换到最顶端
        //换完之后我们要把当前的第一个值变成1
        //后面的值做对应的变换 
        for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c];  // 将当前行的首位变成1
        //变完之后我们开始消
        for (int i = r + 1; i < n; i ++ )  // 用当前行将下面所有的列消成0
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; j -- )
                    a[i][j] -= a[r][j] * a[i][c];

        r ++ ;
    }

    if (r < n)
    {
        for (int i = r; i < n; i ++ )
            if (fabs(a[i][n]) > eps)
                return 2; // 无解
        return 1; // 有无穷多组解
    }

    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] -= a[i][j] * a[j][n];

    return 0; // 有唯一解
}


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

    int t = gauss();
    if (t == 2) puts("No solution");
    else if (t == 1) puts("Infinite group solutions");
    else
    {
        for (int i = 0; i < n; i ++ )
        {
            if (fabs(a[i][n]) < eps) a[i][n] = 0;  // 去掉输出 -0.00 的情况
            printf("%.2lf\n", a[i][n]);
        }
    }

    return 0;
}



活动打卡代码 AcWing 4518. 最低票价

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<vector> 
#include<stack>


using namespace std;

const int N = 367;

int days[N], f[N], costs[4];

int get(int i, int cnt)
{
    int day = i;//这个day是我要更改的 day[i] - days[day] 
    while(day >= 1 && cnt>= days[i] - days[day] + 1) day--;
    return day;
}


int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> days[i];
    for(int i = 1; i <= 3; i++) cin >> costs[i];

    for(int i = 1; i <= n; i++)
    {
        f[i] = f[i - 1] + costs[1];
        f[i] = min(f[i], f[get(i, 7)] + costs[2]);
        f[i] = min(f[i], f[get(i, 30)] + costs[3]);
    }

    cout << f[n] << endl;


    return 0;
} 






[AcWing1530]

这道题可以使用前缀和+将一维数组转为环状。
因为我们求的是两点之间的最短距离,由于这是一个环,所以两点之间的距离有两种走法,因而对这两种走法取min。例min(2->5,5->2)那么问题就再于如何将这两种方式表示出来。
- 首先我们要保证 a < b如果不满足则使用swap,这样是为了我们的值为正数
- 第一种情况比较简单我们之间使用s[b-1]-s[a-1]即可,该情况比如2->5
- 第二种情况则为5->2,那么将2转换为对应的坐标即为2+n。
- 所以我们可以写成min(s[b - 1] - s[a - 1],[a + n - 1] - s[b - 1])

AC代码

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<vector> 
#include<stack>


using namespace std;

const int N = 2e5 + 10;

int n,m;
int a[N],s[N];

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

    for(int i = 1; i <= 2 * n; i++)
        s[i] = s[i- 1] + a[i];

    cin >> m;
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        if(a > b) swap(a,b);
        cout << min(s[b - 1] - s[a - 1],s[a + n - 1] - s[b - 1]) << endl;
    }

    return 0;
} 






[AcWing4498]

有关于二进制枚举的题,先mark一下,日后研究

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 20;

int n;
int w[N];



int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> w[i];


    bool res = false;
    for(int i = 0; i < 1 << n; i++)//枚举所有状态
    {
        int s = 0;
        for(int j = 0; j < n; j++)
            if(i >> j & 1)//i的第j位是1的话
                s += w[j];
            else
                s -= w[j];
        if(s % 360 == 0)
        {
            res = true;
            break;
        }
    }
    if(res) puts("YES");
    else puts("NO");
    return 0;
} 



[AcWing4500]

有关于map的使用,我不太熟练

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



using namespace std;

int main()
{
    int n;
    cin >> n;
    map<int, int> pos;
    for(int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        pos[x] = i;//i表示的是下标
    }
    if(pos.size() < 3) puts("-1 -1 -1");
    else
    {
        vector<int> res;
        for(auto [k, v]: pos) res.push_back(v);
        for(int i =0; i < 3; i++) cout << res[i] << " ";
        cout << endl;
    }
    return 0;
}



[AcWing4501]

#include<iostream>
#include<algorithm>



using namespace std;

const int N = 1e5 + 10;

int n, m;
int cnt[N];


int main()
{
    cin >> n >> m;

    int tot = 0;
    while(m--)
    {
        int x;
        cin >> x;
        if(!cnt[x]) tot++;
        cnt[x] ++;

        //注意这里tot只是表示总类
        if(tot == n)
        {
            cout << "1";
            for(int i = 1; i <= n; i++)
            {
                cnt[i] --;
                if(!cnt[i]) tot --;//如果当前类型的牌没,tot--
            }
        }
        else{
            cout << "0";
        }
    }


    return 0;
}


活动打卡代码 AcWing 885. 求组合数 I

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<vector> 
#include<stack>


using namespace std;

const int N = 2010, mod = 1e9+7;

int c[N][N];


void init()
{
    for(int i = 0; i < N; i++)
        for(int j = 0; j <= i; j++)
            if(!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}

int main()
{
    init();

    int n;
    cin >> n;
    while(n--)
    {
        int a, b;
        cin >> a >> b;
        cout << c[a][b] << endl;
    }

    return 0;
} 





活动打卡代码 AcWing 2070. 自行车之旅

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<vector> 
#include<stack>


using namespace std;

const int N = 110;

int a[N];

int solve(int a[],int n)
{
    int res = 0;
    for(int i = 2; i <= n - 1; i++)
        if(a[i] > a[i - 1] && a[i] > a[i + 1])
            res++;
    return res;
}

int main()
{
    int T;
    cin >> T;
    for(int cases = 1; cases <= T; cases++)
    {
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
        int res = solve(a,n);
        printf("Case #%d: %d\n",cases,res);
    }

    return 0;
} 





活动打卡代码 AcWing 902. 最短编辑距离

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<vector> 
#include<stack>


using namespace std;

const int N = 1010;

int n, m;
char a[N], b[N];
int f[N][N];


int main()
{
    scanf("%d%s",&n, a + 1);
    scanf("%d%s",&m, b + 1);

    for(int i = 0; i <= m; i++) f[0][i] = i;
    for(int i = 0; i <= n; i++) f[i][0] = i;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            f[i][j] = min(f[i-1][j] + 1, f[i][j - 1] + 1);
            if(a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
            else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
        }
    cout << f[n][m];

    return 0;
}