头像

AC小菜




离线:6小时前


最近来访(11)
用户头像
996
用户头像
l_y_f
用户头像
-摆烂王-
用户头像
slight
用户头像
听雨.无尘明月夜
用户头像
丑橘不丑
用户头像
IINE
用户头像
封禁用户
用户头像
NFYD


暴力最后一个点过不了

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include<bits/stdc++.h>

using namespace std;
const int N = 1e6 + 5;

int prime[N];
void getprime(int n)
{
    for (int i = 2; i <= n/i; i++)
    {
        if (n % i == 0)
        {
            int s = 0;
            while (n % i == 0)
            {
                s++;
                n /= i;
            }
            prime[i] += s;
        }
    }
    if (n > 1)
        prime[n] += 1;
}
int main()
{
    int n;
    cin >> n;

    for (int i = 2; i <= n; i++)
    {
        getprime(i);
    }

   for(int i=2;i<=n;i++)
   {
       if(prime[i]!=0)
       printf("%d %d\n",i,prime[i]);
   }
    return 0;

}

线性筛+阶乘计算 阶乘计算公式!!!!

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

using namespace std;

int n,prime[1000005],cnt,st[1000005];

void get_prime(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(st[i]==0)
        {
            prime[cnt++]=i;

        }
        for(int j=0;prime[j]<=n/i;j++)
        {
           st[prime[j]*i]=1;
            if(i%prime[j]==0)
            break;
        }
    }

}

int main()
{
    cin>>n;
    get_prime(n);
    for(int i=0;i<cnt;i++)
    { 
        int ans=0,t=n;
        while(t)
        {
            ans+=t/prime[i];
            t/=prime[i];
        }
        if(ans)
        cout<<prime[i]<<" "<<ans<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 691. 立方体IV

dp+记忆化搜索

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

using namespace std;

int T, n, mp[1005][1005], f[1005][1005];
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };

int dp(int a, int b)
{
    int &t = f[a][b];
    if (t != -1) return t;

    t = 1;
    for (int i = 0; i < 4; i++)
    {
        int x = a + dx[i], y = b + dy[i];
        if (x >= 0 && x < n && y >= 0 && y < n && mp[a][b]+1 == mp[x][y])
            t = max(t, dp(x, y) + 1);
    }

    return t;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        cin >> n;
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                cin >> mp[j][k];

        memset(f, -1, sizeof f);
        int id, dis = 0;

        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
            {
                int t = dp(j, k);
                if (t > dis || (t == dis && id > mp[j][k]))
                {
                    id = mp[j][k];
                    dis = t;
                }
            }

        printf("Case #%d: %d %d\n", i, id, dis);
    }
    return 0;
}


活动打卡代码 AcWing 4279. 笛卡尔树

就是二叉搜索树

#include<bits/stdc++.h>
using namespace std;
int n,w[105];
vector<int> level[105];

int getmin(int l,int r)
{
    int root=l;
    for(int i=l;i<=r;i++)
    {
        if(w[root]>w[i])
        root=i;
    }

    return root;
}
void dfs(int l,int r,int d)
{
    if(l>r)
    return ;

    int t=getmin(l,r);
    level[d].push_back(w[t]);

    dfs(l,t-1,d+1);
    dfs(t+1,r,d+1);
}

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

    dfs(1,n,0);
    for (int i = 0; level[i].size(); i ++ )
    {
        for(auto x:level[i])
        cout<<x<<" ";
    }


    return 0;
}

用bfs


#include<bits/stdc++.h>
using namespace std;
int n, w[105], L[105], R[105];
vector<int> level[105];

int getmin(int l, int r)
{
    int root = l;
    for (int i = l; i <= r; i++)
    {
        if (w[root] > w[i])
            root = i;
    }

    return root;
}

int dfs(int l, int r)
{
    if (l > r)
        return 0;

    int t = getmin(l, r);
    L[t] = dfs(l, t - 1);
    R[t] = dfs(t + 1, r);

    return t;
}

void bfs(int t)
{
    queue<int> q;
    q.push(t);
    while (q.size())
    {
        int x = q.front();
        q.pop();
        cout << w[x] << " ";
        if (L[x] != 0)
            q.push(L[x]);
        if (R[x] != 0)
            q.push(R[x]);
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> w[i];

    int rt = dfs(1, n);

    bfs(rt);

    return 0;
}



SG函数+记忆化搜索

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;
const int N=2005;
const int M=6005;
int n,m,k,e[M],h[N],ne[M],sg[N],idx;
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

int SG(int x)
{
    if(sg[x]!=-1) return sg[x];

    unordered_set<int> S;
    for(int i=h[x];i!=-1;i=ne[i])
    {
        S.insert(SG(e[i]));
    }

    for(int i=0;;i++)
    {
        if(S.count(i)==0)
        return sg[x]=i;
    }
}
int main()
{
    memset(h, -1, sizeof h);
    memset(sg,-1,sizeof sg);
    cin>>n>>m>>k;
    for(int i=0;i<m;i++)
    {
        int u,v;
        cin>>u>>v;
        add(u,v);
    }
    int res=0;

    for(int i=0;i<k;i++)
    {
        int x;
        cin>>x;
        res^=SG(x);
    }

    if(res)
    cout<<"win";
    else
    cout<<"lose";
    return 0;
}



活动打卡代码 AcWing 4278. 峰会

md ! l的最大值是N!!!! pat真是服了

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

using namespace std;

int n, m, k, g[1005][1005];

int main()
{
    cin >> n >> m;
    int x, y;
    while (m--) {
        cin >> x >> y;
        g[x][y] = 1;
        g[y][x] = 1;
    }
    cin >> k;
    int l, a[205] = { 0 }, f;
    for (int t = 1; t <= k; t++)
    {
        f = 1;
        cin >> l;
        for (int i = 0; i < l; i++) cin >> a[i];

        for (int i = 0; i < l-1; i++)
            for (int j = i+1; j < l; j++)
                if (g[a[i]][a[j]] == 0)
                    f = 0;

        int mor = 205;
        if (f)
        {
            int flag = 0;
            for (int i = 1; i <= n; i++)
            {
                int fl = 1;
                for (int j = 0; j < l; j++)
                {
                    if (g[i][a[j]] == 0)
                    {
                        fl = 0;
                        break;
                    }
                }

                if (fl)
                {
                    flag = 1;
                    mor=i;
                    break;
                }
            }
            if (flag)
                printf("Area %d may invite more people, such as %d.\n", t, mor);

            else
                printf("Area %d is OK.\n", t);
        }


        else
            printf("Area %d needs help.\n", t);
    }
    return 0;
}


活动打卡代码 AcWing 4277. 区块反转

最后一个数据!!!!!!!!!!,n=k=100000!!

#include<bits/stdc++.h>
using namespace std;


int n, k, e[100005], ne[100005], h;
int main()
{
    cin >> h >> n >> k;

    int adr, num, next;
    while (n--)
    {
        cin >> adr >> num >> next;
        e[adr] = num;
        ne[adr] = next;
    }
    vector<int> c;
    int t = 0;
    for (int i = h; i != -1; i = ne[i])
    c.push_back(i),t++;

    for (int i = t - (t % k); i >= 0; i -= k)
    {
        for (int j = 0; j < k && i + j < t; j++)
        {
            if (j != k-1 && i + j != t - 1)
                printf("%05d %d %05d\n", c[i + j], e[c[i + j]], c[i + j + 1]);
            else
            {
                if (i + j == k-1||(i+j==t-1&&t<k))//!!!!!!!!!!!
                    printf("%05d %d -1", c[i + j], e[c[i + j]]);
                else
                    printf("%05d %d %05d\n", c[i + j], e[c[i + j]], c[i- k]);
            }

        }
    }
    return 0;
}


活动打卡代码 AcWing 4276. 擅长C

处理字符串的时候要注意,如果为空就不要

#include<bits/stdc++.h>
using namespace std;
string alp[26][7],wd[1005];


int main()
{
    for (int i = 0; i < 26; i ++ )
    for (int j = 0; j < 7; j ++ )
    cin>>alp[i][j];

    string s;
    getchar();
    getline(cin,s);

    vector<string> res;
    string str;
    for(int i=0;i<s.size();i++)
    {
        str="";
        while(s[i]>='A'&&s[i]<='Z')
       {
           str+=s[i];
           i++;
       }
       if(str!="")//!!!!!!!!
       res.push_back(str);


    }

    for(int i=0;i<res.size();i++)
    {
        if(i)
        cout<<endl;
        for(int k=0;k<7;k++)
        {
         for(int j=0;j<res[i].size();j++)
        {
            if(j)
            cout<<" ";
            cout<<alp[res[i][j]-'A'][k];
        }
       cout<<endl;
        }

    }
    return 0;
}




AC小菜
11天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;
int a[105],m[105],n;

void exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0)
    x=1,y=0;
    else
    {
    exgcd(b,a%b,y,x);
    y-=a/b*x;
    }

}
int main()
{
    cin>>n;
    ll M=1;
    for(int i=0;i<n;i++)
    {
        cin>>m[i]>>a[i];
        M*=m[i];
    }
    ll res=0;
    for (int i = 0; i < n; i ++ )
    {
        ll t=M/m[i],x,y;
        exgcd(t,m[i],x,y);
        res+=a[i]*t*x;
    }

    cout<<(res%M+M)%M;
    return 0;
}


活动打卡代码 AcWing 4275. Dijkstra序列

AC小菜
13天前

dijkstra模板稍微变形

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

using namespace std;

int n, m, k, dist[1005], g[1005][1005], p[1005], st[1005];

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[p[0]] = 0;

    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (st[j] == 0 && (t == -1 || dist[t] > dist[j]||(dist[t]>=dist[j]&&p[i]==j)))//变形
                t = j;

        st[t] = 1;
        //cout << t << " ";
        if (t != p[i])
        {
            return 0;
        }

        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);

    }
    //cout << endl;
    return 1;
}
int main()
{
    cin >> n >> m;
    int a, b, c;
    memset(g, 0x3f, sizeof g);
    while (m--) {
        cin >> a >> b >> c;
        g[a][b] = c;
        g[b][a] = c;

    }
    cin >> k;
    while (k--)
    {
        memset(st, 0, sizeof st);
        memset(p, 0, sizeof p);
        for (int i = 0; i < n; i++)
            cin >> p[i];

        if (dijkstra())
            cout << "Yes" << endl;
        else

            cout << "No" << endl;
    }
    return 0;
}


活动打卡代码 AcWing 4274. 后缀表达式

AC小菜
13天前

这题居然做了半天,真废了!,仔细看题!!!!

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

using namespace std;

int n;
struct node
{
    string s;
    int l=-1,r=-1;
}tre[105];

string dfs(int t)
{
    if (tre[t].l == -1 && tre[t].r == -1)
        return "(" + tre[t].s + ")";
    if (tre[t].l == -1 && tre[t].r != -1)
        return "(" + tre[t].s + dfs(tre[t].r) + ")";

        return "(" + dfs(tre[t].l) + dfs(tre[t].r) +tre[t].s +")";
}
int main()
{
    cin >> n;
    string s;
    int l, r;
    for (int i = 1; i <= n; i++)
    {
        cin >> s >> l >> r;
        tre[i].s = s;
        tre[i].l = l, tre[i].r = r;
    }

    int root = 0;
    for (int i = 1; i <= n; i++)
    {
        int f = 1;
        for (int j = 1; j <= n; j++)
        {
            if (i == tre[j].l || i == tre[j].r)
            {
                f = 0;
                break;
            }
        }

        if(f)
            root = i;
    }

    cout<<dfs(root);

    return 0;
}