头像

吴鑫




离线:8小时前


最近来访(9)
用户头像
plzzz
用户头像
YikN
用户头像
彭华成
用户头像
陌默
用户头像
黑炭保安
用户头像
牛子不怕困难
用户头像
用户头像
acwing_4197
用户头像
灵茶山艾府


吴鑫
3个月前
#include <iostream>
#include <vector>

using namespace std;

vector<int> Add(vector<int> A, vector<int> B)
{
    int t = 0;
    vector<int> C;
    for (int i = 0; i < A.size() || i < B.size(); i++)
    {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t%10);
        t /= 10;
    }

    if (t > 0) C.push_back(1);

    return C;
}

int main()
{
    vector<int> f[65];
    f[0].push_back(0);
    f[1].push_back(1);
    for (int i = 2; i <= 60; i++)
    {
        f[i] = Add(f[i - 1], f[i - 2]); 
    }

    int n;
    cin >> n;
    while (n--)
    {
        int x;
        cin >> x;
        printf("Fib(%d) = ", x);
        for (int i = f[x].size() - 1; i >= 0; i--) cout << f[x][i];
        cout << endl;
    }
    return 0;
}



吴鑫
4个月前
#include<iostream>
#include<cstring>
#define get_hash(l,r) Hash[r]-Hash[l-1]*p[r-l+1]

using namespace std;
typedef unsigned long long ULL;
const int N=1000010,P=131;
char DNA[N];
ULL Hash[N],p[N];
int m;
int main()
{
    cin>>DNA+1>>m;
    int n=strlen(DNA+1);
    p[0]=1;
    for(int i=1;i<=n;i++)
    {
        Hash[i]=Hash[i-1]*P+DNA[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_hash(l1,r1)==get_hash(l2,r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}


活动打卡代码 AcWing 138. 兔子与兔子

吴鑫
4个月前
#include<iostream>
#include<cstring>
#define get_hash(l,r) Hash[r]-Hash[l-1]*p[r-l+1]

using namespace std;
typedef unsigned long long ULL;
const int N=1000010,P=131;
char DNA[N];
ULL Hash[N],p[N];
int m;
int main()
{
    cin>>DNA+1>>m;
    int n=strlen(DNA+1);
    p[0]=1;
    for(int i=1;i<=n;i++)
    {
        Hash[i]=Hash[i-1]*P+DNA[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_hash(l1,r1)==get_hash(l2,r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}


活动打卡代码 AcWing 165. 小猫爬山

吴鑫
4个月前
#include<iostream>
#include<algorithm>
using namespace std;

const int N=20;
int car[N],weight[N];
int n,car_max,ans;
int cmp(int a,int b)
{
    return a>b;
}
void dfs(int now,int sum)
{
    if(sum>=ans) return ;
    if(now==n+1)
    {
        ans=min(ans,sum);
        return ;
    }
    for(int i=1;i<=sum;i++)
    {
        if(car[i]+weight[now]<=car_max)
        {
            car[i]+=weight[now];
            dfs(now+1,sum);
            car[i]-=weight[now];
        }
    }
    car[sum+1]=weight[now];
    dfs(now+1,sum+1);
    car[sum+1]=0;
}
int main()
{
    cin>>n>>car_max;
    for(int i=1;i<=n;i++)
        cin>>weight[i];
    sort(weight+1,weight+n+1,cmp);
    ans=n;
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 238. 银河英雄传说

吴鑫
4个月前
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=30010;
int p[N],sz[N],d[N];
int n;
void init()
{
    memset(d,0,sizeof d);
    for(int i=1;i<N;i++)
    {
        p[i]=i;
        sz[i]=1;
    }
}
int find(int x)
{
    if(p[x]!=x)
    {
        int t=p[x];
        p[x]=find(p[x]);
        d[x]+=d[t];
    }
    return p[x];
}
int main()
{
    cin>>n;
    init();
    while(n--)
    {
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);
        int x=find(a);
        int y=find(b);
        if(*op=='M')
        {
            if(x!=y)
            {
                d[x]=sz[y];
                sz[y]+=sz[x];
                p[x]=y;
            }
        }
        else
        {
            if(x==y) printf("%d\n",max(0,abs(d[a]-d[b])-1));
            else puts("-1");
        }
    }
    return 0;
}


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

吴鑫
4个月前
#include<iostream>

using namespace std;

const int N=100010;
int son[N*31][2],idx;
int p[N];
int n;
void insert(int x){
    int p=0;
    for(int i=30;i>=0;i--){
        int u=x>>i&1;
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
}
int query(int x){
    int ans=0;
    int p=0;
    for(int i=30;i>=0;i--){
        int u=x>>i&1;
        if(son[p][!u]) ans=ans*2+1,p=son[p][!u];
        else ans=ans*2,p=son[p][u];
    }
    return ans;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        scanf("%d",&p[i]);
        insert(p[i]);
    }
    int maxn=0;
    for(int i=0;i<n;i++) maxn=max(maxn,query(p[i]));
    cout<<maxn<<endl;
    return 0;
}


活动打卡代码 AcWing 142. 前缀统计

吴鑫
4个月前
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int son[N][26],cut[N],idx;
int n,m,ans;
void insert(string a){
    int p=0;
    for(int i=0;i<a.size();i++){
        int u=a[i]-'a';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
    cut[p]++;
}
void query(string a){
    int p=0;
    for(int i=0;i<a.size();i++){
        int u=a[i]-'a';
        if(!son[p][u]) return;
        p=son[p][u];
        ans+=cut[p];
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        string a;
        cin>>a;
        insert(a);
    }
    while(m--){
        ans=0;
        string a;
        cin>>a;
        query(a);
        cout<<ans<<endl;
    }
    return 0;
}



吴鑫
4个月前
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int son[N][26],cut[N],idx;
int n,m,ans;
void insert(string a){
    int p=0;
    for(int i=0;i<a.size();i++){
        int u=a[i]-'a';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
    cut[p]++;
}
void query(string a){
    int p=0;
    for(int i=0;i<a.size();i++){
        int u=a[i]-'a';
        if(!son[p][u]) return;
        p=son[p][u];
        ans+=cut[p];
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        string a;
        cin>>a;
        insert(a);
    }
    while(m--){
        ans=0;
        string a;
        cin>>a;
        query(a);
        cout<<ans<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 111. 畜栏预定

吴鑫
4个月前
#include <bits/stdc++.h>
using namespace std;
const int N=50100;
struct node
{
    int l;
    int r;
    int x;
    bool operator <(const node &a)const 
    {
        if(r==a.r)
            return l>a.l;
        return r>a.r;
    }
} a[N];
priority_queue<node> p;
int n,m,i,j,as[N];
int cmp(node a,node b)
{
    if (a.l==b.l)
        return a.r<b.r;
    return a.l<b.l;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for (i=1;i<=n;i++)
        cin>>a[i].l>>a[i].r,a[i].x=i;
    sort(a+1,a+1+n,cmp);
    int ans=0;
    for (i=1;i<=n;i++)
    {
        if (!p.empty() && p.top().r<a[i].l) 
        {
            as[a[i].x]=as[p.top().x];
            p.pop();
        }
        else
        {
            ans++;
            as[a[i].x]=ans;
        }
        p.push(a[i]);
    }    
    cout<<ans<<endl;
    for (i=1;i<=n;i++)
        cout<<as[i]<<endl;
    return 0;
}


活动打卡代码 AcWing 703. 数独检查

吴鑫
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 40;

int n, m;
int w[N][N];
bool st[N];

bool check_row()
{
    for (int i = 0; i < m; i ++ )
    {
        memset(st, 0, sizeof st);
        for (int j = 0; j < m; j ++ )
        {
            int t = w[i][j];
            if (t < 1 || t > m) return false;
            if (st[t]) return false;
            st[t] = true;
        }
    }
    return true;
}

bool check_col()
{
    for (int i = 0; i < m; i ++ )
    {
        memset(st, 0, sizeof st);
        for (int j = 0; j < m; j ++ )
        {
            int t = w[j][i];
            if (t < 1 || t > m) return false;
            if (st[t]) return false;
            st[t] = true;
        }
    }
    return true;
}

bool check_cell()
{
    for (int x = 0; x < m; x += n)
        for (int y = 0; y < m; y += n)
        {
            memset(st, 0, sizeof st);
            for (int dx = 0; dx < n; dx ++ )
                for (int dy = 0; dy < n; dy ++ )
                {
                    int t = w[x + dx][y + dy];
                    if (t < 1 || t > m) return false;
                    if (st[t]) return false;
                    st[t] = true;
                }
        }
    return true;
}

int main()
{
    int T;
    scanf("%d", &T);
    for (int C = 1; C <= T; C ++ )
    {
        scanf("%d", &n);
        m = n * n;
        for (int i = 0; i < m; i ++ )
            for (int j = 0; j < m; j ++ )
                scanf("%d", &w[i][j]);

        if (check_row() && check_col() && check_cell())
            printf("Case #%d: Yes\n", C);
        else
            printf("Case #%d: No\n", C);
    }
    return 0;
}