天天看點
傳回

2021牛客寒假算法基礎集訓營62021牛客寒假算法基礎集訓營6

2021牛客寒假算法基礎集訓營6

A 回文括号序列計數

我們定義一個字元串S是回文的，表示S的左右反轉和S相同。

我們定義一個字元串是括号序列：

  1. 空串是括号序列。
  2. 兩個括号序列P和Q的拼接是括号序列。
  3. 如果P是括号序列，’(’+P+’)'是括号序列。
求長度為 n (0<=n<=10^9) 的回文括号序列的方案數，對 998244353 取膜。 
#include <bits/stdc++.h>

//#pragma GCC optimize(2)
#define int long long
using namespace std;
const int mod = 998244353;
typedef long long LL;
typedef long long ll;
const int inf = 1e18;
//const int mod = 1e9 + 7;
const int maxn = 5e6 + 10;
const int N = 1e5 + 10000;



void solve() {
    int n;
    cin>>n;
    if (n) cout<<0<<"\n";
    else cout<<1<<"\n";
}

signed main() {
    //ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

J 天空之城

并查集

#include <bits/stdc++.h>

//#pragma GCC optimize(2)
#define int long long
using namespace std;
const int mod = 998244353;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int inf = 1e18;
//const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int N = 1e7 + 10000;

struct edge{
    int u,v,w;
}e[maxn];
int fa[10001];
string a,b;

int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

bool cmp(edge x,edge y){
    return x.w<y.w;
}

void solve() {
    int n,m,w;
    while (cin>>n>>m){
        cin>>a;
        for(int i=1;i<=n;i++)fa[i]=i;
        map<string,int > q;
        int cnt=0,ans=0,num=0;
        for (int i = 1; i <=m; ++i) {
            cin>>a>>b>>w;
            if (!q.count(a)) q[a]=++num;
            if (!q.count(b)) q[b]=++num;
            e[i]={q[a],q[b],w};
        }
        sort(e+1,e+m+1,cmp);
        for (int i = 1; i <=m; ++i) {
            int x=find(e[i].u);
            int y=find(e[i].v);
            if (y==x) continue;
            fa[x]=y;
            cnt++;
            ans+=e[i].w;
        }
        if (cnt!=n-1) cout<<"No!";
        else cout<<ans;
        cout<<"\n";
    } 
}

signed main() {
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
//    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

G 機器人

2021牛客寒假算法基礎集訓營62021牛客寒假算法基礎集訓營6
#include <bits/stdc++.h>

//#pragma GCC optimize(2)
#define int long long
using namespace std;
const int mod = 998244353;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int inf = 1e18;
//const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int N = 1e7 + 10000;

struct no {
    __int128 a, b;
} node[maxn];

bool cmp(no x, no y) {
    return x.a * y.b + x.b < x.b * y.a + y.b;
}

inline __int128 read() {
    __int128 x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch - '0');
        ch = getchar();
    }
    return x * f;
}

void print(__int128 x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}

void solve() {
    __int128 n, x;
    n = read();
    x = read();
    for (int i = 0; i < n; ++i) {
        node[i].a = read();
        node[i].b = read();
    }
    sort(node, node + n, cmp);
    for (int i = 0; i < n; ++i) {
        x = x * node[i].a + node[i].b;
    }
    print(x);
}

signed main() {
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
//    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

dfs記憶化搜尋/狀壓dp

#include <bits/stdc++.h>

//#pragma GCC optimize(2)
using namespace std;
#define int long long
typedef long long LL;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int inf = 1e18;
const int mod = 998244353;
//const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int N = 1e7 + 10000;

int a[30];
int b[30];
__int128 f[(1 << 20) + 100];
int n, x;

__int128 dfs(int p) {
    if (f[p] != 0) return f[p];
    for (int i = 0; i < n; ++i) 
        if ((p & (1 << i)) != 0) 
            f[p] = max(dfs(p ^ (1 << i)) * a[i] + b[i], f[p]);
    return f[p];
}

inline void print(__int128 x) {
    if (x < 0) putchar('-'),x = -x;
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

void solve() {
    cin >> n >> x;
    for (int i = 0; i < n; ++i) 
        cin >> a[i] >> b[i];
    f[0] = x;
    print(dfs((1 << n) - 1));
}

signed main() {
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
//    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

E 網格

dp

#include <bits/stdc++.h>

//#pragma GCC optimize(2)
using namespace std;
#define int long long
typedef long long LL;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int inf = 1e18;
const int mod = 998244353;
//const int mod = 1e9 + 7;
const int maxn = 2e3 + 10;
const int N = 1e7 + 10000;

int a[maxn][maxn];
int dp[maxn][maxn][2];
int f[maxn][maxn][2];

int w(int x){
    int res=x;
    while (x){
        if (x&1) res++;
        x>>=1;
    }
    return res;
}

void solve() {
    int n,m;
    cin>>n>>m;
    for (int i = 1; i <=n; ++i)
        for (int j = 1; j <=n; ++j)
            cin>>a[i][j];
    int ans=0;
    for (int i = 1; i <=n; ++i) {
        for (int j = 2; j <=m; ++j) {
            dp[i][j][0]=max(dp[i][j-1][1]+w(a[i][j]^a[i][j-1]),dp[i][j-1][0]);
            dp[i][j][1]=max(dp[i][j-1][1],dp[i][j-1][0]);
        }
        ans+=max(dp[i][m][0],dp[i][m][1]);
    }
    for (int j = 1; j <=m; ++j) {
        for (int i = 2; i <=n; ++i) {
            f[i][j][0]=max(f[i-1][j][1]+w(a[i-1][j]^a[i][j]),f[i-1][j][0]);
            f[i][j][1]=max(f[i-1][j][1],f[i-1][j][0]);
        }
        ans += max(f[n][j][0], f[n][j][1]);
    }
    cout<<ans;
}

signed main() {
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
//    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

H 動态最小生成樹

并查集

#include <bits/stdc++.h>

//#pragma GCC optimize(2)
using namespace std;
#define int long long
typedef long long LL;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int inf = 1e18;
const int mod = 998244353;
//const int mod = 1e9 + 7;
const int maxn = 3e5 + 10;
const int N = 1e7 + 10000;

struct node{
    int u,v,w;
    bool operator <(const node & tmp){
        return w<tmp.w;
    }
}e[maxn],d[maxn];
int fa[maxn];

int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

void solve() {
    int n,m,q;
    cin>>n>>m>>q;
    for (int i = 1; i <=m; ++i) {
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    int l,r,x,y,z,t;
    while (q--){
        int opt;
        cin>>opt;
        if (opt==1){
            cin>>x>>y>>z>>t;
            e[x].u=y,e[x].v=z,e[x].w=t;
        } else{
            cin>>l>>r;
            int top=0;
            for (int i = l; i <=r ; ++i) d[++top]=e[i];
            sort(d+1,d+top+1);
            for (int i = 1; i <=n; ++i) fa[i]=i;
            int cnt=n-1,ans=0;
            for (int i = 1; i <=top&&cnt; ++i) {
                int fu=find(d[i].u);
                int fv=find(d[i].v);
                if (fu==fv) continue;
                cnt--;
                fa[fu]=fv;
                ans+=d[i].w;
            }
            if (cnt>0) cout<<"Impossible\n";
            else cout<<ans<<"\n";
        }
    }
}

signed main() {
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
//    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

B 系數

2021牛客寒假算法基礎集訓營62021牛客寒假算法基礎集訓營6
2021牛客寒假算法基礎集訓營62021牛客寒假算法基礎集訓營6
2021牛客寒假算法基礎集訓營62021牛客寒假算法基礎集訓營6
#include <bits/stdc++.h>

//#pragma GCC optimize(2)
using namespace std;
#define int long long
typedef long long LL;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int inf = 1e18;
const int mod = 998244353;
//const int mod = 1e9 + 7;
const int maxn = 3e5 + 10;
const int N = 1e7 + 10000;

int c[3][3]={1,0,0,1,1,0,1,2,1};

int getc(int m,int n){
    if (n<m) return 0;
    if (n>=3||m>=3)
        return getc(m/3,n/3)*getc(m%3,n%3)%3;
    return c[n][m];
}

void solve() {
    int n,k;
    cin>>n>>k;
    cout<<(k%2?(3-getc(k,n+n))%3:getc(k,n+n))<<"\n";
}

signed main() {
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}
組合數 dfs dp 并查集 狀壓DP 大數 Lucas
上一篇: ​LeetCode刷題實戰192：統計詞頻
下一篇: 資料中台體系結構、建設方法和落地實踐（3）資料中台的商業價值模型一、前言

繼續閱讀