头像

莫德歪奇




离线:11小时前


最近来访(78)
用户头像
ghghf
用户头像
源泉
用户头像
Mhbfy
用户头像
kzyz
用户头像
今宵酒醒何处
用户头像
4733
用户头像
一人舛木
用户头像
hiahia_6
用户头像
z-x-y
用户头像
eric_fyq
用户头像
一笑奈何_0
用户头像
liaoyanxu
用户头像
黎耀辉
用户头像
世蒂
用户头像
风吹过就吹过
用户头像
ssy_
用户头像
没那么简单_5
用户头像
big_go
用户头像
落月成孤倚灬
用户头像
flow_21

活动打卡代码 AcWing 891. Nim游戏

莫德歪奇
11小时前
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n;
    scanf("%d", &n);
    int res = 0;
    while (n -- )
    {
        int x;
        scanf("%d", &x);
        res ^= x;
    }
    if (res) puts("Yes");
    else puts("No");
    return 0;
}


活动打卡代码 AcWing 887. 求组合数 III

莫德歪奇
12小时前

留坑,不太理解

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
int C(int a, int b, int p)
{
    if (b > a) return 0;

    int res = 1;
    for (int i = 1, j = a; i <= b; i ++, j -- )
    {
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2, p) % p;
    }
    return res;
}
int lucas(LL a, LL b, int p)
{
    if (a < p && b < p) return C(a, b, p);
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}
int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        LL a, b;
        int p;
        cin >> a >> b >> p;
        cout << lucas(a, b, p) << endl;
    }
    return 0;
}


活动打卡代码 AcWing 841. 字符串哈希

莫德歪奇
13小时前
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N=100010,P=131;//p=131经验
int n,m;
char op[N];
ULL h[N],p[N];
ULL get(int l,int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%s",op+1);
    p[0]=1;
    for(int i=1;i<=n;i++)
    {
        h[i]=h[i-1]*P+op[i];
        p[i]=p[i-1]*P;
    }
    while(m--)
    {
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(get(l1,r1)==get(l2,r2))puts("Yes");
        else puts("No");
    }
    return 0;
}


活动打卡代码 AcWing 3302. 表达式求值

莫德歪奇
14小时前
#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;
stack<int> num;
stack<char> op;
unordered_map<char,int>h{{'+',1},{'-',1},{'*',2},{'/',2}};
void eval()
{
    int b=num.top();
    num.pop();
    int a=num.top();
    num.pop();
    char p=op.top();
    op.pop();
    int r=0;
    if (p == '+') r = a + b;
    if (p == '-') r = a - b;
    if (p == '*') r = a * b;
    if (p == '/') r = a / b;
    num.push(r);//结果入栈
}
int main()
{
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        if(isdigit(s[i]))
        {
            int x=0,j=i;
            while(j<s.size()&&isdigit(s[j]))
            {
                x=x*10+s[j]-'0';
                j++;
            }
            num.push(x);
            i=j-1;//多加一个位置
        }
        else if(s[i]=='(')
        {
            op.push((s[i]));
        }
        else if(s[i]==')')
        {
            while(op.top()!='(')
                eval();
            op.pop();
        }
        else
        {
            while(op.size()&&h[op.top()]>=h[s[i]])
                eval();
            op.push(s[i]);
        }
    }
    while(op.size())eval();
    cout<<num.top()<<endl;
    return 0;
}



莫德歪奇
19小时前

A(floyd)

O(n^3)n=100
//错误:字符转换忘记
atoi (表示 ascii to integer)
是把字符串转换成整型数的一个函数。
在头文件<stdlib.h>中
就是我们在cmd中输入的是字符,我们计算需要的是数值int,
所以这个函数的功能就是把我们在cmd中输入的数字(以字符的形式存储)转换成真正的数字
#include<stdio.h>
#include<iostream>
#include<cstring>
using namespace std;
const int INF = 1e9;
int v[101][101];
int n;
void floyd()
{
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            if(v[i][k]!=INF)
                for(int j=1; j<=n; j++)
                    if(v[i][j]>v[i][k]+v[k][j])
                        v[i][j]=v[i][k]+v[k][j];
}
int main()
{

    while(cin>>n)
    {
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
        {
            if(i==j) v[i][j]=0;
            else v[i][j]=INF;
        }
        for(int i=2; i<=n; i++)
            for(int j=1; j<i; j++)
        {
            char t[10];
            scanf("%s",t);
            if(t[0]!='x')
                v[i][j]=v[j][i]=atoi(t);    
        }
        floyd();
        int s=-1;
        for(int i=1;i<=n;i++)
            s=max(s,v[1][i]);
        printf("%d\n",s);
    }
    return 0;
}

B

思路:判断这个位置是否属于棋盘区域和这一行内有没有放过棋子即可。
坑:又可能这行就不放,和n皇后不一样,可以直接跳过一行因为(k<=n)

要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列

#include<bits/stdc++.h>
using namespace std;
int n,k,ans,sum;
char a[10][10];
bool st[10][10];
void dfs(int u)
{
    if(sum==k)
    {
        ans++;
        return ;
    }
    else
    {
        if(u>n)return;
        else
        {
            for(int i=1;i<=n;i++)
            {
                if(a[u][i]=='#'&&!st[u][i])
                {
                    sum++,st[u][i]=true;
                    dfs(u+1);
                    sum--,st[u][i]=false;
                }
            }
            dfs(u+1);//这行不放,直接跳过
            //因为k<=n,可能已经没有棋子
        }
    }
}
int main()
{
    while(cin>>n>>k)
    {
        if(n==-1&&k==-1)break;
        memset(st,false,sizeof st);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                cin>>a[i][j];
        ans=0;//方案数
        sum=0;//棋子放置个数
        dfs(1);
        cout<<ans<<endl;
    }
    return 0;
}

C

(一直死循环,应考虑不撞石头的最优解,不得不撞石头再去step+1和回溯)
#include <stdio.h>
#include<string.h>
int w,h;//记录场地的宽和高
int sx,sy,ex,ey;//记录起点和终点坐标
int dx[4]={0,0,-1,1};//存方向变化量
int dy[4]={1,-1,0,0};
int maps[30][30],best;//best记录最优解。maps存地图

void dfs(int cx,int cy,int step)//cx,cy记录当前位置。step表示已走多少步
{
    int nx,ny,i;
    if(step>best)//剪枝如果大于目前最优解直接返回
        return;
    for(i=0;i<4;i++)
    {
        nx=cx+dx[i];
        ny=cy+dy[i];//跑最优解肯定先不跑障碍物
        if(nx>=h||nx<0||ny>=w||ny<0||maps[nx][ny]==1)//越界或立即有阻挡物剪枝
            continue;
        while(nx<h&&nx>=0&&ny<w&&ny>=0&&maps[nx][ny]!=1)//一直滑
        {
            if(nx==ex&&ny==ey)//若到终点
            {
                if(step+1<best)
                    best=step+1;
                break;
            }
            nx+=dx[i];
            ny+=dy[i];
        }
        if(nx==ex&&ny==ey)//终点
            continue;
        if(nx<h&&nx>=0&&ny<w&&ny>=0)
        {
            maps[nx][ny]=0;//若是碰到阻挡物。阻挡物消失。
            dfs(nx-dx[i],ny-dy[i],step+1);//继续搜索
            maps[nx][ny]=1;//还原阻挡物。回溯
        }
    }
}
int main()
{
    int i,j;
    while(scanf("%d%d",&w,&h),w||h)
    {
        best=12;//初始化best
        for(i=0;i<h;i++)//读取地图
            for(j=0;j<w;j++)
        {
            scanf("%d",&maps[i][j]);
            if(maps[i][j]==2)
                sx=i,sy=j;
            if(maps[i][j]==3)
                ex=i,ey=j;
        }
        dfs(sx,sy,0);//深搜
        if(best<=10)
            printf("%d\n",best);
        else
            printf("-1\n");
    }
    return 0;
}


活动打卡代码 AcWing 890. 能被整除的数

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 20;
int p[N];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i ++ ) cin >> p[i];
    int res = 0;
    for (int i = 1; i < 1 << m; i ++ )
    {
        int t = 1, s = 0;
        for (int j = 0; j < m; j ++ )
            if (i >> j & 1)
        {
            if ((LL)t * p[j] > n)
            {
                t = -1;
                break;
            }
            t *= p[j];
            s ++ ;
        }   
        if (t != -1)
        {
            if (s % 2) res += n / t;
            else res -= n / t;
        }
    }   
    cout << res << endl;

    return 0;
}



A

1e9,直接用vector存
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<int>a;
int main()
{
    a.push_back(0);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        a.push_back(x);
    }
    while (m--)
    {
        int x;
        scanf("%d", &x);
        printf("%d\n", a[x]);
    }
    return 0;
}

B

刚开始没写出来,用栈记录,每次放入栈的是下标而不是符号
1.先判断是不是右括号,再从栈中提取之前放的,如果为空跳过,不为空进行比较,配对成功就打上两个位置的true
#include<bits/stdc++.h>
using namespace std;
int b[105];
bool st[105];
int main()
{
    stack<int>s;
    string a;
    cin >> a;
    for (int i = 0; i < a.size(); i++)
    {
        if (a[i] == ']')
        {
            if (s.empty())continue;
            int x = s.top();
            if (a[x] == '[')
            {
                st[x]=st[i] = true;//记录两个位置
                s.pop();
            }
        }
        else if (a[i] == ')')
        {
            if (s.empty())continue;
            int x = s.top();
            if (a[x] == '(')
            {
                st[x] = st[i] = true;
                s.pop();
            }
        }
        else s.push(i);
    }
    for (int i = 0; i < a.size(); i++)
    {
        if (st[i])cout << a[i];
        else
        {
            if (a[i] == '(' || a[i] == ')')cout << "()";
            else cout << "[]";
        }
    }
    return 0;
}

C

经典队列做
#include<bits/stdc++.h>
using namespace std;
int cnt = 0, k = 1;
int main()
{
    int n, m;
    cin >> n >> m;
    queue<int>q;
    for (int i = 1; i <= n; i++)
        q.push(i);
    while (!q.empty())
    {
        if (cnt == n)break;
        int x = q.front();
        q.pop();
        if (k == m)
        {
            k = 1;
            cnt++;
            cout << x << ' ';
        }
        else
        {
            q.push(x);
            k++;
        }
    }
    return 0;
}


活动打卡代码 AcWing 886. 求组合数 II

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010, mod = 1e9 + 7;
int fact[N], infact[N];
int n;
int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1)res = (LL)a * res % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
int main()
{
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i++)
    {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
    int n;
    cin >> n;
    while (n--)
    {
        int a, b;
        cin >> a >> b;
        printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
    }
    return 0;
}


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

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 2010,MOD = 1e9 + 7;
int n = 2000;
LL C[N][N];
int main () 
{
    for (int i = 1;i <= n;i++) 
    {
        C[i][0] = C[i][i] = 1;
        for (int j = 1;j <= i - 1;j++) 
        {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
        }
    }
    cin >> n;
    while (n--) 
    {
        int a,b;
        cin >> a >> b;
        cout << C[a][b] << endl;
    }
    return 0;
}



#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int a[N][N];
int gauss()
{
    int c, r;
    for (c = 0, r = 0; c < n; c ++ )
    {
        int t = r;
        for (int i = r; i < n; i ++ )
            if (a[i][c])
                t = i;
        if (!a[t][c]) continue;
        for (int i = c; i <= n; i ++ ) swap(a[r][i], a[t][i]);
        for (int i = r + 1; i < n; i ++ )
            if (a[i][c])
                for (int j = n; j >= c; j -- )
                    a[i][j] ^= a[r][j];
        r ++ ;
    }
    if (r < n)
    {
        for (int i = r; i < n; i ++ )
            if (a[i][n])
                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()
{
    cin >> n;

    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n + 1; j ++ )
            cin >> a[i][j];
    int t = gauss();
    if (t == 0)
    {
        for (int i = 0; i < n; i ++ ) cout << a[i][n] << endl;
    }
    else if (t == 1) puts("Multiple sets of solutions");
    else puts("No solution");
    return 0;
}