【算法竞赛】Namomo Winter 2023 Day 3 Div 2

题目来源：

Dashboard - 2017-2018 ACM-ICPC, NEERC, Northern Subregional Contest - Codeforces

Dashboard - 2017-2018 ACM-ICPC, NEERC, Moscow Subregional Contest - Codeforces

A. Auxiliary Project

代码语言：javascript复制

#pragma GCC optimize(2)

#include <bits/stdc  .h>

#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e6 10;

int n;
int f[N];
int cost[10] = {
    6, 2, 5, 5, 4, 5, 6, 3, 7, 6
};
/*
6 = 3 3 -> 7*2 = 14
7 = 3 4 -> 7 4 = 11
5 = 3 2 -> 7 1 = 8
4 = 4 -> 4
3 = 3 -> 7
2 = 2 -> 1
*/
void solve() {
    cin >> n;
    map<int, int> mp;
    mp[6] = 14, mp[7] = 11, mp[5] = 8, mp[4] = 4;
    mp[3] = 7, mp[2] = 1;
    memset(f, 0xcf, sizeof f);
    f[0] = 0;
    for(auto it : mp) {
        int v = it.fi, w = it.se;
        for(int j = v; j <= n; j   )
            f[j] = max(f[j], f[j-v] w);
    }
    cout << f[n] << 'n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;  // << setprecision(20); // double
    freopen("auxiliary.in", "r", stdin);
    freopen("auxiliary.out ", "w", stdout);
    // int Tcase;
    // cin >> Tcase; // scanf("%d", &Tcase);
    // while (Tcase--) 
    solve();
    return 0;
}
/*
贪心好像也可以做，直接模3，然后稍微分类下就行
*/

B. Consonant Fencity

代码语言：javascript复制

#pragma GCC optimize(2)

#include <bits/stdc  .h>

#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 26;

int cnt[N][N], refc[N];

void solve() {
    string s;
    cin >> s;
    string dic = "bcdfghjklmnpqrstvxz";
    memset(refc, -1, sizeof refc);
    for(int i = 0; i < dic.size(); i   ) {
        char x = dic[i];
        int p = x-'a';
        refc[p] = i;
    }
    for(int i = 1; i < s.size(); i   ) {
        int a = refc[s[i-1]-'a'], b = refc[s[i]-'a'];
        if(!~a || !~b) continue;
        cnt[a][b]   ;
        cnt[b][a]   ; // 两个互相相邻
    }
    int res = 0, rec = 0;
    int T;
    for(T = 0; T < (1<<19); T   ) {
        int tres = 0;
        for(int i = 0; i < 19; i   ) {
            if(T>>i & 1) // upper
                for(int j = 0; j < 19; j   )
                    if((T>>j & 1) == 0) { // lower
                        tres  = cnt[i][j];
                    }
        }
        if(tres > res) {
            res = tres;
            rec = T;
        }
    }
    for(auto &x : s) {
        int p = refc[x-'a'];
        if(~p && (rec>>p & 1)) x = toupper(x);
    }
    cout << s << 'n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;  // << setprecision(20); // double
    freopen("consonant.in", "r", stdin);
    freopen("consonant.out", "w", stdout);
    // int Tcase;
    // cin >> Tcase; // scanf("%d", &Tcase);
    // while (Tcase--) 
    solve();
    return 0;
}
/*
没估计好复杂度 3秒限制，实际就枚举2^19次状态，每个check下它的pair数即可

一开始像确定前后关系来计cnt和tres，然后可以减少一般的枚举量，结果wa了
后面想到如果'z'为大写，小写和他相互结对的就不能记录个数了。
*/

C. Intelligence in Perpendicularia

代码语言：javascript复制

#pragma GCC optimize(2)

#include <bits/stdc  .h>

#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

void solve() {
    int n;
    cin >> n;
    vector<PII> a(n);
    for(auto &x : a) cin >> x.fi >> x.se;
    int xMx = a[0].fi, xMn = a[0].fi, yMx = a[0].se, yMn = a[0].se;
    LL sum = 0;
    for(int i = 1; i < n; i   ) {
        sum  = abs(a[i].fi a[i].se-a[i-1].fi-a[i-1].se);
        xMx = max(xMx, a[i].fi), xMn = min(xMn, a[i].fi);
        yMx = max(yMx, a[i].se), yMn = min(yMn, a[i].se);
    }
    sum  = abs(a[0].fi a[0].se-a[n-1].fi-a[n-1].se);
    cout << sum-2*(xMx-xMn yMx-yMn) << 'n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;  // << setprecision(20); // double
    freopen("intel.in", "r", stdin);
    freopen("intel.out ", "w", stdout);
    // int Tcase;
    // cin >> Tcase; // scanf("%d", &Tcase);
    // while (Tcase--) 
    solve();
    return 0;
}
/*
不要被计算几何的外表骗了，实际只是脑经急转弯 —— dls

外面能看到的部分就是上下左右四个方向
就是x最大最小值、y最大最小值处理一下的值
*/

D. Kotlin Island

代码语言：javascript复制

#pragma GCC optimize(2)

#include <bits/stdc  .h>

#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 110;

char g[N][N];

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    int mx = (n 1)/2, my = (m 1)/2;
    int x = -1, y = -1;
    bool ok = false;
    for(int i = 1; i <= mx; i   ) {
        for(int j = 1; j <= my; j   )
            if(i*j == k) {
                x = i-1, y = j-1;
                ok = true;
                break;
            }
        if(ok) break;
    }
    if(!ok) {
        cout << "Impossiblen";
        return;
    }
    // cout << x << ' ' << y << 'n';
    for(int i = 0; i < n; i   )
        for(int j = 0; j < m; j   )
            g[i][j] = '.';
    for(int i = 1, j = 0; i < n && j < x; i  = 2, j   )
        for(int u = 0; u < m; u   )
            g[i][u] = '#';
    for(int i = 1, j = 0; i < m && j < y; i  = 2, j   )
        for(int u = 0; u < n; u   )
            g[u][i] = '#';
    for(int i = 0; i < n; i   )
        cout << g[i] << 'n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;  // << setprecision(20); // double
    freopen("kotlin.in", "r", stdin);
    freopen("kotlin.out", "w", stdout);
    // int Tcase;
    // cin >> Tcase; // scanf("%d", &Tcase);
    // while (Tcase--) 
    solve();
    return 0;
}

E. Little Difference

代码语言：javascript复制

#pragma GCC optimize(2)

#include <bits/stdc  .h>

#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

bool is2(LL n) {
    while(n % 2 == 0) n /= 2;
    return n == 1;
}
void solve() {
    LL n;
    cin >> n;
    vector<vector<LL>> ans;
    if(n == 1 || is2(n)) {
        cout << "-1n";
        return;
    }
    else {
        // cout << 1 << ' ' << n << 'n';
        vector<LL> t(1, n);
        ans.push_back(t);
    }
    LL t = (LL)(sqrt(n) 0.1);
    if(n == t*(t 1)) {
        // cout << 2 << ' ' << t << ' ' << t 1 << 'n';
        vector<LL> tt(1, t);
        tt.push_back(t 1);
        ans.push_back(tt);
    }
    else if(n == t*t) {
        // cout << 2 << ' ' << t << ' ' << t << 'n';
        vector<LL> tt(2, t);
        ans.push_back(tt);
    }
    for(LL i = 2; i*i*i <= n; i   ) {
        LL j = i 1, cnt0 = 0, cnt1 = 0;
        if(n % i == 0) {
            LL m = n;
            while(m % i == 0) m /= i, cnt0   ;
            if(m == 1) {
                vector<LL> tt(cnt0, i);
                ans.push_back(tt);
            }
            j = i 1, cnt0 = 0, cnt1 = 0;
            if(n % (i*j) == 0) {
                LL m = n;
                while(m % i == 0) m /= i, cnt0   ;
                while(m % j == 0) m /= j, cnt1   ;
                if(m == 1) {
                    vector<LL> tt(cnt0, i);
                    for(int z = 0; z < cnt1; z   )
                        tt.push_back(j);
                    ans.push_back(tt);
                }
            }
        }
    }
    cout << ans.size() << 'n';
    for(auto vec : ans) {
        cout << vec.size();
        for(auto x : vec) 
            cout << ' ' << x;
        cout << 'n';
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;  // << setprecision(20); // double
    freopen("little.in", "r", stdin);
    freopen("little.out", "w", stdout);
    // int Tcase;
    // cin >> Tcase; // scanf("%d", &Tcase);
    // while (Tcase--) 
    solve();
    return 0;
}
/*
对题目理解不完全，只要是任意数最多差1，且不存在元素和数目相同就是一个合法方案
2^k都是无限种方案。

解法的话，看到数据范围，三次开方的复杂度可以接受，就1次和2次的另外处理即可。
*/

F. Advertising Strategy

代码语言：javascript复制

#pragma GCC optimize(2)

#include <bits/stdc  .h>

#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

LL n, k;
LL Work(LL x) {
    LL cnt = 1;
    LL m = n-(k-x), last = -1;
    while(x < m) {
        // cout << x << 'n';
        if(x == last) {
            cnt = 1e18;
            break;
        }
        last = x;
        x  = min(x, (n-x)/2);
        cnt   ;
    }
    return cnt;
}
void solve() {
    cin >> n >> k;
    LL res = 1e18;
    for(int i = 1; i <= k; i   ) {
        res = min(res, Work(i));
    }
    cout << res << 'n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;  // << setprecision(20); // double
    // freopen("i.txt", "r", stdin);
    // freopen("o.txt", "w", stdout);
    // int Tcase;
    // cin >> Tcase; // scanf("%d", &Tcase);
    // while (Tcase--) 
    solve();
    return 0;
}
/*
增长的过程：
阶段一：
    乘二
阶段二：
     = (n-x)/2
所以是先快后慢，很容易得到中间时候放不如在开始或结尾放，所以枚举即可。
*/

G. Carpet

代码语言：javascript复制

#pragma GCC optimize(2)

#include <bits/stdc  .h>

#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e5 10, M = 2e5 10;

int idx, h[N], ne[M], ver[M];
int son[N], siz[N];
int n, cnt[25];
PII p[N];

void add(int a, int b) {
    ver[idx] = b, ne[idx] = h[a], h[a] = idx   ;
}
void dfs1(int u, int fa) {
    siz[u] = 1;
    for(int i = h[u]; ~i; i = ne[i]) {
        int v = ver[i];
        if(v == fa) continue;
        dfs1(v, u);
        siz[u]  = siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int fa, int line) {
    p[u] = {   cnt[line], line};
    for(int i = h[u]; ~i; i = ne[i]) {
        int v = ver[i];
        if(v != fa && v != son[u])
            dfs2(v, u, line 1);
    }
    if(son[u]) 
        dfs2(son[u], u, line);
}
void solve() {
    memset(h, -1, sizeof h);
    cin >> n;
    for(int i = 1; i < n; i   ) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    dfs1(1, -1);
    dfs2(1, -1, 1);
    for(int i = 1; i <= n; i   )
        cout << p[i].fi << ' ' << p[i].se << 'n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;  // << setprecision(20); // double
    // freopen("i.txt", "r", stdin);
    // freopen("o.txt", "w", stdout);
    // int Tcase;
    // cin >> Tcase; // scanf("%d", &Tcase);
    // while (Tcase--) 
    solve();
    return 0;
}
/*
轻重链剖分
    先把轻儿子放在下一行，再把重儿子放在父节点这一行的右边

    能够不挺分下去的儿子最多只有log n层，且列不会超出，符合
*/

H. Decoding of Varints

代码语言：javascript复制

#pragma GCC optimize(2)

#include <bits/stdc  .h>

#define fi first
#define se second
#define mkp(x, y) make_pair((x), (y))
#define all(x) (x).begin(), (x).end()

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

void solve() {
    ULL n;
    cin >> n;
    ULL sum = 0, len = 1;
    while(n --) {
        ULL a;
        cin >> a;
        if(a >= 128) {
            a -= 128;
            sum  = a*len;
            len *= 128;
        }
        else {
            sum  = a*len;
            if(sum & 1) {
                cout << -(LL)(sum/2 1) << 'n'; // -(sum 1)/2
            }
            else {
                cout << sum/2 << 'n';
            }
            sum = 0, len = 1;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;  // << setprecision(20); // double
    // freopen("i.txt", "r", stdin);
    // freopen("o.txt", "w", stdout);
    // int Tcase;
    // cin >> Tcase; // scanf("%d", &Tcase);
    // while (Tcase--) 
    solve();
    return 0;
}
/*
题意在绕，读懂后按题意模拟即可

题目只保证被加密的数在LL范围，并不保证加密出来的数在LL范围
ps. 一开始我用了int128，然后后面发现加密出来的数最多超LL一倍，且是正数
所以也可以用ULL
*/

kotlin dashboard decoding difference project

0 人点赞