AtCoder Beginner Contest 136

A - +-x

直接取\(max\)即可。

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 5;

int main() {

    ios::sync_with_stdio(false); cin.tie(0);

    int a, b;

    cin >> a >> b;

    cout << max(a + b, max(a - b, a * b));

    return 0;

}

B - One Clue

直接输出，注意判断左右边界。

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 5;

int main() {

    ios::sync_with_stdio(false); cin.tie(0);

    int k, x;

    cin >> k >> x;

    for(int i = max(-1000000, x - k + 1); i <= min(1000000, x + k - 1); i++) cout << i << ' ';

    return 0;

}

C - Green Bin

\(map\)统计\(string\)出现次数即可。

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 5;

map <string, int> mp;

string s;

int n;

int main() {

    ios::sync_with_stdio(false); cin.tie(0);

    cin >> n;

    ll ans = 0;

    for(int i = 1; i <= n; i++) {

        cin >> s;

        sort(s.begin(), s.end());

        if(mp.find(s) != mp.end()) ans += mp[s];

        mp[s]++;

    }

    cout << ans;

    return 0;

}

D - Summer Vacation

时间倒流。

每一个工作只能在某一个时刻之前开始进行才能获得收益。考虑倒序枚举时间，在每一个位置将所有工作加入，取最大收益即可。

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 5;

int n, m;

vector <int> c[N];

struct node{

    int A, B;

}a[N];

int main() {

    ios::sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;

    for(int i = 1; i <= n; i++) cin >> a[i].B >> a[i].A;

    for(int i = 1; i <= n; i++) {

        if(a[i].B <= m) c[m - a[i].B].push_back(a[i].A);

    }

    priority_queue <int> q;

    int ans = 0;

    for(int i = m - 1; i >= 0; i--) {

        for(auto it : c[i]) q.push(it);

        if(!q.empty()) {

            ans += q.top(); q.pop();

        }

    }

    cout << ans;

    return 0;

}

E - Coins Respawn

首先\(dfs\)一次找到所有能够到达\(n\)的点，然后在这些点上面跑\(spfa\)+判正环就行。

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2505, M = 5005;

int n, m, p;

struct Edge{

    int u,v,w,next;

}e[M<<1];

int tot, head[N];

void adde(int u,int v,int w){

    e[tot].u=u;e[tot].v=v;e[tot].w=w;e[tot].next=head[u];head[u]=tot++;

}

bool ok[N], vis[N];

bool g[N][N];

int c[N], d[N], dis[N];

void dfs(int u) {

    ok[u] = 1;

    for(int i = 1; i <= n; i++) {

        if(g[u][i] && !ok[i]) dfs(i);

    }

}

int spfa(int s){

    queue <int> q;

    memset(d,0xcf,sizeof(d));

    memset(vis,0,sizeof(vis));memset(c,0,sizeof(c));

    q.push(s);vis[s]=1;d[s]=0;c[s]=1;dis[s]=0;

    while(!q.empty()){

        int u=q.front();q.pop();vis[u]=0;

        if(c[u]>n){

            return d[0];

        }

        for(int i=head[u];i!=-1;i=e[i].next){

            int v=e[i].v;

            if(!ok[v]) continue;

            if(d[v]<d[u]+e[i].w){

                d[v]=d[u]+e[i].w;

                dis[v]=dis[u]+1;

                if(!vis[v]){

                    vis[v]=1;

                    q.push(v);

                    c[v]++;

                }

            }

        }

    }

    return d[n];

}

int main() {

    ios::sync_with_stdio(false); cin.tie(0);

    cin >> n >> m >> p;

    memset(head, -1, sizeof(head));

    for(int i = 1; i <= m; i++) {

        int u, v, w; cin >> u >> v >> w;

        adde(u, v, w - p);

        g[v][u] = 1;

    }

    dfs(n);

    int t = spfa(1);

    if(t == d[0]) cout << -1;

    else cout << max(0, t);

    return 0;

}

F - Polynomial Construction

考虑拉格朗日插值，那么答案就是：

\[y=\sum_{i=0}^{p-1}a_i\prod_{j\neq i}\frac{x-j}{i-j}=\sum_{i=0}^{p-1}a_i\prod_{j\neq i}x-j\prod_{j\neq i}\frac{1}{i-j}
\]

现在就考虑如何快速求\(\prod_{j\neq i}x-j\)。

这部分可以直接递推计算，设\(dp[i][j]\)表示考虑\(\prod_{k=0}^{i}x-k\)的结果中\(x^j\)的系数是多少，那么就有：

\(dp[i][0]=dp[i-1][0]*(-i)\)
\(dp[i][j]=dp[i-1][j-1]-dp[i-1][j]*i\)

因为式子中有限制条件:\(j\neq i\)，那么就考虑如何去掉一个\(x-i\):

\(dp[n-1][j]=dp[n-1][j+1](if:i=0)\)
\(dp[n-1][j]=\frac{dp[n-1][j]-tmp}{i}(else)\)，\(tmp\)表示前面的对后面的贡献。

详见代码：

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 3000;

int n, mod;

int a[N], res[N];

ll qp(ll a, ll b) {

    ll ans = 1;

    while(b) {

        if(b & 1) ans = ans * a % mod;

        a = a * a % mod;

        b >>= 1;

    }

    return ans;

}

int inv[N], inv2[N];

int dp[N][N];

int add(int x, int y) {

    x += y;

    if(x >= mod) x -= mod;

    return x;

}

int sub(int x, int y) {

    x -= y;

    if(x < 0) x += mod;

    return x;

}

int mul(ll x, ll y) {

    x = x * y % mod;

    if(x < 0) x += mod;

    return x;

}

void pre() {

    for(int i = 1; i <= n; i++) inv[i] = qp(i, mod - 2);

    for(int i = 1; i <= n; i++) inv2[i] = qp(mod - i, mod - 2);

    dp[0][1] = 1;

    for(int i = 1; i < n; i++) {

        for(int j = 0; j <= i + 1; j++) {

            dp[i][j] = mul(dp[i - 1][j], mod - i);

            if(j) dp[i][j] = add(dp[i][j], dp[i - 1][j - 1]);

//            cout << i << ' ' << j << ' ' << dp[i][j] << '\n';

        }

    }

}

int main() {

    ios::sync_with_stdio(false); cin.tie(0);

    cin >> n; mod = n;

    for(int i = 0; i < n; i++) cin >> a[i];

    pre();

    for(int i = 0; i < n; i++) if(a[i]) {

        int ans = 1;

        for(int j = 0; j < n; j++) {

            if(i > j) ans = mul(ans, inv[i - j]);

            if(i < j) ans = mul(ans, inv2[j - i]);

        }

        int tmp = 0;

        if(i == 0) tmp = dp[n - 1][1];

        res[0] = add(res[0], mul(ans, tmp));

        for(int j = 1; j < n; j++) {

            tmp = mul(sub(dp[n - 1][j], tmp), inv2[i]);

            if(i == 0) tmp = dp[n - 1][j + 1];

            res[j] = add(res[j], mul(ans, tmp));

        }

    }

    for(int i = 0; i < n; i++) cout << res[i] << " \n"[i == n - 1];

    return 0;

}

巴特西

AtCoder Beginner Contest 136

AtCoder Beginner Contest 136

A - +-x

B - One Clue

C - Green Bin

D - Summer Vacation

E - Coins Respawn

F - Polynomial Construction

最新文章

热门文章