《Codeforces Round #739 (Div. 3)》

2023-11-27 22:31:58

A：水题

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e4 + 5;
const int M = 5e5 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;

int b[N];
void init() {
    int tot = 0;
    for(int i = 1;tot <= 1005;++i) {
        if(i % 3 == 0 || i % 10 == 3) continue;
        b[++tot] = i;
    }
}
int main() {
    init();
    int ca;scanf("%d",&ca);
    while(ca--) {
        int k;scanf("%d",&k);
        printf("%d\n",b[k]);
    }

   // system("pause");
    return 0;
}

View Code

B：水题

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e4 + 5;
const int M = 5e5 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;

void solve() {
    int a,b,c;scanf("%d %d %d",&a,&b,&c);
    int d = max(a,b) - min(a,b);
    int mx = 2 * d;
    if(max(a,b) > mx || c > mx) printf("-1\n");
    else {
        if(c <= d) printf("%d\n",c + d);
        else printf("%d\n",c - d);
    }
}
int main() {
    int ca;scanf("%d",&ca);
    while(ca--) {
        solve();
    }

 //   system("pause");
    return 0;
}

View Code

C：模拟一下就行

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e4 + 5;
const int M = 5e5 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;

void solve() {
    int k;scanf("%d",&k);
    int st = 1,add = 2,cnt = 1,row,line;
    while(1) {
        if(k <= st) {
            if(k <= cnt) {
                line = cnt;
                row = k;
                break;
            }
            else {
                row = cnt;
                k -= cnt;
                line = cnt - k;
                break;
            }
        }
        k -= st;
        st += add;
        cnt++;
    }
    printf("%d %d\n",row,line);
}
int main() {
    int ca;scanf("%d",&ca);
    while(ca--) {
        solve();
    }
   // system("pause");
    return 0;
}

View Code

D：这里我觉得做法肯定有很多。

我的做法是把所有可能的答案存出来，dp求可以匹配的最长前缀，然后求最小值即可。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e4 + 5;
const int M = 5e5 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;

bool dp[20][20];//dp[i][j] - 前i个是否能以j结尾
string s[65];
void init() {
    for(int i = 0;i <= 60;++i) {
        LL ma = (1LL << i);
        s[i] = to_string(ma);
    }
}
void solve() {
    int n;scanf("%d",&n);
    string t = to_string(n);
    int m = t.size(),ans = INF;
    for(int i = 0;i <= 60;++i) {
        int len = s[i].size();
        memset(dp,0,sizeof(dp));
        dp[0][0] = 1;
        for(int k = 1;k <= m;++k) {
            dp[k][0] = 1;
            for(int j = 1;j <= len;++j) {
                if(t[k - 1] == s[i][j - 1]) {
                    dp[k][j] |= dp[k - 1][j - 1];
                }
                dp[k][j] |= dp[k - 1][j];
            }
        }
        for(int j = 0;j <= len;++j) {
            if(dp[m][j]) ans = min(ans,m - j + len - j);
        }
    }
    printf("%d\n",ans);
}
int main() {
    init();
    int ca;scanf("%d",&ca);
    while(ca--) {
        solve();
    }
   // system("pause");
    return 0;
}

View Code

E：其实我感觉这题还挺不错的。

首先很显然我们可以从后向前记录，按每个数一个次出现的顺序存取。

显然这个就是我们删除的操作序列。

然后我们可以知道每个数出现在几次变换的t中，然后就可以求得每次中每个数出现的次数。

这样我们就可以求得第一个串，然后暴力去删就可以了。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e4 + 5;
const int M = 5e5 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;

bool vis[30];
int sz[30],hav[30],add[30];
void solve() {
    memset(sz,0,sizeof(sz));
    memset(hav,0,sizeof(hav));
    memset(vis,0,sizeof(vis));
    memset(add,0,sizeof(add));
    string t;cin >> t;
    int n = t.size();
    vector<char> ans;
    for(int i = n - 1;i >= 0;--i) {
        if(vis[t[i] - ‘a‘] == 0) {
            vis[t[i] - ‘a‘] = 1;
            ans.push_back(t[i]);
        }
        sz[t[i] - ‘a‘]++;
    }
    reverse(ans.begin(),ans.end());
    int len = 1;
    string ma = "";
    for(auto v : ans) hav[v - ‘a‘] = len++,ma += v;
    for(int i = 0;i < 26;++i) {
        if(sz[i] == 0) continue;
        if(sz[i] % hav[i] != 0) {
            printf("-1\n");
            return ;
        }
    }
    string tmp = "";
    for(auto v : t) {
        int x = v - ‘a‘;
        if(add[x] == sz[x] / hav[x]) break;
        add[x]++;
        tmp += v;
    }
    string md = tmp,all = tmp;
    for(auto v : ans) {
        string ss = "";
        for(auto x : md) {
            if(x != v) ss += x;
        }
        md = ss;
        all += md;
    }
   // cout << all << endl;
    if(all == t) cout << tmp << " " << ma << endl;
    else printf("-1\n");
}
int main() {
    int ca;scanf("%d",&ca);
    while(ca--) {
        solve();
    }
   // system("pause");
    return 0;
}

View Code

F1：暴力乱搞就行了。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e4 + 5;
const int M = 5e5 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;

pii same(int x) {
    int f = 0,t = x % 10,y = x % 10;
    x /= 10;
    while(x) {
        if(x % 10 != t) f = 1;
        y = x % 10;
        x /= 10;
    }
    return pii{y,f};
}
int LEN(int x) {
    int len = 0;
    while(x) len++,x /= 10;
    return len;
}
void solve() {
    int n,k;scanf("%d %d",&n,&k);
    if(k == 1) {
        pii ma = same(n);
        if(ma.second == 0) printf("%d\n",n);
        else {
            LL ans = 0;
            for(int i = 1;i <= LEN(n);++i) ans = ans * 10 + ma.first;
            if(ans < n) {
                ans = 0;
                for(int i = 1;i <= LEN(n);++i) ans = ans * 10 + (ma.first + 1);
            }
            printf("%lld\n",ans);
        }
    }
    else {
        pii ma = same(n);
        if(ma.second == 0) printf("%d\n",n);
        else {
            string s = to_string(n);
            string ans = "";
            int x = s[0] - ‘0‘;
            for(int i = 0;i <= 9;++i) {
                int f = 0,flag = 0,len = 0;
                string t = "";
                for(auto v : s) {
                    len++;
                    int y = v - ‘0‘;
                    if(max(x,i) > y) {
                        string ta = t;
                        ta += ‘0‘ + max(x,i);
                        for(int j = s.size() - len;j >= 1;--j) ta += ‘0‘ + min(x,i);
                        if(ta < ans || ans == "") ans = ta;
                    }
                    if(max(x,i) < y && f == 0) {flag = 1;break;}
                    if(f) t += ‘0‘ + min(x,i);
                    else {
                        if(min(x,i) > y) f = 1,t += ‘0‘ + min(x,i);
                        else if(min(x,i) == y) t += ‘0‘ + min(x,i);
                        else if(max(x,i) > y) f = 1,t += ‘0‘ + max(x,i);
                        else t += ‘0‘ + max(x,i);
                    }
                }
                if(flag) continue;
                if(ans == "" || t < ans) ans = t;
            }
            cout << ans << endl;
        }
    }
}
int main() {
    int ca;scanf("%d",&ca);
    while(ca--) {
        solve();
    }
   // system("pause");
    return 0;
}

View Code

F2：数位dfs。

二进制第i位的数表示i有没有被用过，然后状态中几个1就有几个不同的数，这里有个小优化，当我们第一次找到答案时肯定是最小的，因为我们是从小到大搜的。

复杂度分析一下，因为f状态只有2 ^ 10左右，所以复杂度不会很高。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e4 + 5;
const int M = 5e5 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;

int ans = 0,n,k,a[15],len = 0;
int cal(int x) {
    int sum = 0;
    while(x) {
        if(x % 2 == 1) sum++;
        x /= 2;
    }
    return sum;
}
void dfs(int x,bool lim,int sum,int f) {
    if(ans != 0) return ;
    if(x == len + 1) {
        ans = sum;
        return ;
    }
    int low = 0;
    if(lim == 1) low = a[len - x + 1];
    for(int i = low;i <= 9;++i) {
        if(cal(f | (1 << i)) <= k) dfs(x + 1,lim & (i == low),sum * 10 + i,f | (1 << i)); 
    }
}
void solve() {
    scanf("%d %d",&n,&k);
    ans = len = 0;
    int x = n;
    while(x) {
        a[++len] = x % 10;
        x /= 10;
    }
    dfs(1,1,0,0);
    printf("%d\n",ans);
}
int main() {
    int ca;scanf("%d",&ca);
    while(ca--) {
        solve();
    }
    //system("pause");
    return 0;
}

View Code

《Codeforces Round #739 (Div. 3)》

码农公寓

相关文章