感谢 @Toshi 提供 C 题 O(n^2) 题解以及 DEF 题解

A、ACMer不得不知道的事儿(五)

签到题,暴力计算即可。

#include <iostream>

using namespace std;

int main()
{
    int T;
    cin >> T;
    while(T--){
        int n, rnk, m;
        cin >> n >> rnk >> m;
        if(m == 0 || n / 10 * 6 < rnk) {
            cout << -1 << endl;
        }
        else{
            for(int i = rnk; i <= n; ++i){
                if(i / 10 * 6 >= rnk){
                    cout << i << endl;
                    break;
                }
            }
        }
    }
    return 0;
}

B、HHHHooolllooww Knniiggghhtt

先计算构成一个Hollow Knight需要的各种字母的数量,以及统计总的输入的各种字母的数量,然后枚举组成几个Hollow Knight,判断拥有的字母是否能构成即可。

#include <iostream>
#include <cstring>
#include <cstdlib>

using namespace std;

char hk[] = "hollowknight";

int need[26];

void init(){
    int len = strlen(hk);
    for(int i = 0; i < len; ++i){
        ++need[hk[i]-'a'];
    }
}

const int N = 105;
int cnt[26];
int tempcnt[26];
int others;
int tempothers;
char s[N];

void solve(){
    memset(cnt, 0, sizeof cnt);
    others = 0;
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> s;
        int len = strlen(s);
        for(int j = 0; j < len; ++j){
            if(s[j] >= 'A' && s[j] <= 'Z'){
                ++cnt[s[j]-'A'];
            }
            else if(s[j] >= 'a' && s[j] <= 'z'){
                ++cnt[s[j]-'a'];
            }
            else{
                ++others;
            }
        }
    }
    int ans = 0;
    for(int i = 1;;++i){
        memcpy(tempcnt, cnt, sizeof cnt);
        tempothers = others;
        bool flag = true;
        for(int j = 0; j < 26; ++j){
            if(need[j] * i > tempcnt[j]){
                flag = false;
                break;
            }
            tempothers += tempcnt[j] - need[j] * i;
        }
        if(tempothers < i) flag = false;
        if(flag)
            ans = i;
        else break;
    }
    cout << ans << endl;
}


int main()
{
    init();
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

C、身体越来越好的lrc

这题可以 O(N^3) 直接暴力,首先枚举前两个数(非0),然后从第三个数开始是显然升序的,并且在知道前两个数的情况下可以直接计算出第三个数,所以只要 for 一遍判断是否合法即可。

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

using namespace std;

using ll = long long;
const int N = 205;
ll a[N];

void solve(){
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    sort(a, a+n);
    int ans = 0;
    for(int i = 0; i < n; ++i){
        if(a[i] == 0) continue;
        ans = max(ans, 1);
        for(int j = 0; j < n; ++j){
            if(i == j || a[j] == 0) continue;
            int cnt = 2;
            ll pre = a[j], nxt = a[i] + a[j];
            for(int k = max(i,j) + 1; k < n; ++k){
                if(a[k] == nxt){
                    ++cnt;
                    nxt = pre + a[k];
                    pre = a[k];
                }
                else if(a[k] > nxt){
                    break;
                }
            }
            ans = max(ans, cnt);
        }
    }
    cout << ans << endl;
}


int main()
{
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

C 补充一种 O(n^2) 做法
dp[i][j] 表示以 a[i]a[j]f[1]f[2]fib 序列长度,接着转移
dp[i][j] = dp[j][k] + 1 ,其中 a[k] = a[i] + a[j]
这时候有个问题,如何快速得到 k ,一种方法是用 map ,值映射到下标,这样复杂度是O(log) ,或者用 unordermap 或手写 hash ,这样是 O(1) 的。
当然也可以预处理得到 k,设 idx[i][j] = min ( k | a[k] >= a[i] + a[j] ) ,接着,因为 idx[i][j] >= idx[i][j-1] ,是递增的,类似于胖哥上述的 O(n^3) 里面的做法,在i为确定值的时候,用双指针 jk ,从 0 一直跑到 n-1 ,这样预处理复杂度 O(n^2)
递归写法的代码:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N = 1e3+10;
const int inf = 0x3f3f3f3f;

int dp[N][N], nxt[N][N];
int a[N];
int d(int i, int j){
    if(dp[i][j] != -1) return dp[i][j];
    if(nxt[i][j] != -1){
        return dp[i][j] = d(j, nxt[i][j]) + 1;
    }
    return dp[i][j] = 2;
}
void work(){
    int n;scanf("%d", &n);
    for(int i = 0;i<n;i++) scanf("%d", &a[i]);
    sort(a,a+n);
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            dp[i][j] = nxt[i][j] = -1;
        }
    }
    for(int i = 0;i<n;i++){
        int k = 0;
        for(int j = 0;j<n;j++){
            while(k<n && a[k]<a[i]+a[j]){
                k++;
            }
            if(a[k]==a[i]+a[j]) nxt[i][j] = k;
        }
    }
    int ans = 0;
    for(int i = 0;i<n;i++){
        if(a[i]) ans = max(ans, 1);
        for(int j = 0;j<n;j++){
            if(i!=j && a[i] && a[j]){
                ans = max(ans, d(i,j));
            }
        }
    }
    printf("%d\n", ans);
}
int main() {
    #ifdef local
    freopen("in.txt","r",stdin);
    #endif // local
    int t;scanf("%d", &t);
    while(t--)
        work();
}

非递归只要从后面往前做即可,代码略

D、去月球

对于每一行、每一列以及副对角线的操作,都有做和不做两种,由于最多 n(n\leq10) ,最多 m(m\leq10) ,情况数为 2^{(n+m+1)} ,大概 1e6 左右,那么可以枚举所有情况,枚举到某一种情况后需要验证是否合法以及计算该情况下的操作数,验证合法复杂度为 O(nm) ,计算操作数的复杂度为 O(n+m) ,总体复杂度 O(2^{(n+m)} * n * m)
有两种枚举法,一种是二进制位枚举,选和不选用 10 表示,则某一种情况可以用 n+m+1 个二进制位的整数来表示,如 n=2, m=2 ,那么 00101 可以表示第 1 列翻转,副对角线翻转,其它不动;当然你也可以认为最右边 n 个位表示行是否翻转,最左边的位表示副对角线,但前者可以直接用数值大小比较字典序

#include<cstdio>
#include<iostream>

using namespace std;

typedef long long ll;
const int N = 1e3+10;
const int inf = 0x3f3f3f3f;
char s[N][N];
int n,m;
bool ok(int x){
    char t[N][N];
    //做个备份
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            t[i][j] = s[i][j] - '0';
        }
    }
    //从左到右检查所有操作,是做还是不做
    for(int k = (1<<(n+m)),i = 1;k>=1;k>>=1, i++){
        if(k & x){
            if(i<=n){
                for(int j = 0;j<m;j++){
                    t[i-1][j]^=1;
                }
            }else if (i<=n+m){
                for(int j = 0;j<n;j++){
                    t[j][i-n-1]^=1;
                }
            }else{
                for(int i = n-1, j = 0;i>=0;i--, j++){
                    t[i][j]^=1;
                }
            }
        }
    }
    //验证是否合法
    bool ans = true;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(!t[i][j]) ans=0;
        }
    }
    return ans;
}
int count(int x){
    //利用lowbit计算二进制中1的数量
    int cnt = 0;
    for(;x;x-=x&-x, cnt++);
    return cnt;
}
void work(){
    scanf("%d%d", &n, &m);
    for(int i = 0;i<n;i++){
        scanf("%s",s[i]);
    }
    int ans = inf;
    int ansk;
    //枚举所有情况。数值大则字典序小
    for(int k = 0;k<(1<<(n+m+1));k++){
        int c = count(k);
        if(c > ans || !ok(k)) continue;
        if(c < ans){
            ans = c;
            ansk = k;
        }else if (c == ans){
            ansk = max(ansk, k);
        }
    }
    if(ans == inf){
        puts("JustGoToPlayToTheMoon");
        return;
    }
    printf("%d\n", ans);
    char space[5] = "";
    for(int k = (1<<(n+m)),i = 1;k>=1;k>>=1, i++){
        if(ansk & k){
            printf("%s%d",space, i);
            space[0] = ' ';
        }
    }
    if(ans)puts("");
}
int main() {
    #ifdef local
    freopen("in.txt","r",stdin);
    #endif // local
    int t;scanf("%d", &t);
    while(t--)
        work();
}

递归写法,本质一样,也是枚举所有情况

#include<cstdio>
#include<iostream>

using namespace std;

typedef long long ll;
const int N = 1e3+10;
const int inf = 0x3f3f3f3f;
char s[N][N];
int n,m;
int ans;
int ansk;
int count(int x){
    //利用lowbit计算二进制中1的数量
    int cnt = 0;
    for(;x;x-=x&-x, cnt++);
    return cnt;
}
void dfs(int x,int k){
    if(x>n+m+1){
        bool ok = true;
        for(int i = 0;i<n&&ok;i++){
            for(int j = 0;j<m&&ok;j++){
                if(!s[i][j]){
                    ok = 0;
                }
            }
        }
        if(ok){
            int c = count(k);
            if(c<ans){
                ans = c;
                ansk = k;
            }else if (c==ans){
                ansk = max(ansk, k);
            }
        }
        return;
    }
    dfs(x+1, k);
    if(x<=n){
        for(int j = 0;j<m;j++){
            s[x-1][j]^=1;
        }
    }else if (x<=n+m){
        for(int j = 0;j<n;j++){
            s[j][x-n-1]^=1;
        }
    }else{
        for(int i = n-1, j = 0;i>=0;i--, j++){
            s[i][j]^=1;
        }
    }
    dfs(x+1, k|(1<<(n+m+1-x)));

    //还原
    if(x<=n){
        for(int j = 0;j<m;j++){
            s[x-1][j]^=1;
        }
    }else if (x<=n+m){
        for(int j = 0;j<n;j++){
            s[j][x-n-1]^=1;
        }
    }else{
        for(int i = n-1, j = 0;i>=0;i--, j++){
            s[i][j]^=1;
        }
    }
}

void work(){
    scanf("%d%d", &n, &m);
    for(int i = 0;i<n;i++){
        scanf("%s",s[i]);
        for(int j = 0;j<m;j++){
            s[i][j]-='0';
        }
    }
    ans = inf;
    dfs(1, 0);

    if(ans == inf){
        puts("JustGoToPlayToTheMoon");
        return;
    }
    printf("%d\n", ans);
    char space[5] = "";
    for(int k = (1<<(n+m)),i = 1;k>=1;k>>=1, i++){
        if(ansk & k){
            printf("%s%d",space, i);
            space[0] = ' ';
        }
    }
    if(ans)puts("");
}
int main() {
    #ifdef local
    freopen("in.txt","r",stdin);
    #endif // local
    int t;scanf("%d", &t);
    while(t--)
        work();
}

其实这题还可以 O(nm) ,考虑第一行和副对角线选和不选,有 4 种情况,枚举后,假如第一行还是有 1 ,要消除它们只能通过列,则这时候所有列的是否操作被唯一确定,列翻转后,如果还是有 1 ,则只能通过其它行来消除,这时其他行是否操作也被唯一确定,翻转操作 O(nm) ,判断合法和计算操作数 O(nm) , 总体 O(nm)
代码好像有点麻烦,没写

E、调制饮料,改变人生

模拟一下

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

typedef long long ll;
char matrl[105][35];
char drinkname[105][35];

struct Drink{
    int index[105];
    int num[105];
    int len;
    bool isbig;
    int cnt;
}drink[105];

int findstr(char s[][35], int len, char key[35]){
    for(int i = 0;i<len;i++){
        if(strcmp(s[i], key) == 0){
            return i;
        }
    }
    return len;
}
int ans[35];
void work(){
    int n,matn,drinkn;scanf("%d%d%d", &n, &matn, &drinkn);
    for(int i = 0;i<matn;i++){
        scanf("%s", matrl[i]);
    }
    for(int i = 0;i<drinkn;i++){
        scanf("%s", drinkname[i]);
        int x;scanf("%d", &x);
        drink[i].len = 0;
        drink[i].cnt = 0;
        int sum = 0;
        for(int j = 0;j<x;j++){
            char mname[35];
            int num;
            scanf("%s%d", mname, &num);
            int idx = findstr(matrl, matn, mname);
            sum += num;
            if(idx != matn){
                int len = drink[i].len;
                drink[i].index[len] = idx;
                drink[i].num[len] = num;
                drink[i].len++;
            }
        }
        drink[i].isbig = sum > 10;
    }
    memset(ans, 0, sizeof(ans));
    for(int kk = 0;kk<n;kk++){
        char dname[35];
        int big;
        scanf("%s%d", dname, &big);
        int i = findstr(drinkname, drinkn, dname);
        int d = 1;
        if(big && !drink[i].isbig) {
            d = 2;
        }
        drink[i].cnt+=d;
    }
    for(int i = 0;i<drinkn;i++){
        for(int j = 0;j<drink[i].len;j++){
            ans[drink[i].index[j]] += drink[i].cnt * drink[i].num[j];
        }
    }
    for(int i = 0;i<matn;i++){
        printf("%d%c", ans[i], " \n"[i==matn-1]);
    }
}
int main() {
    #ifdef local
    freopen("in.txt","r",stdin);
    #endif // local
    int t;scanf("%d", &t);
    while(t--)
        work();
}

F、Robin和紫紫的做题比赛

枚举 s 的所有分配,共 s+1 种,再计算按按钮次数,这个可以预处理从 0i 的按按钮次数 (0\leq i \leq999) ,接着用前缀和性质 O(1) 得到

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;

typedef long long ll;
const int N = 1e3+10;
const int inf = 0x3f3f3f3f;
int d[N];
int dist(int x,int y){
    //利用前缀和的性质
    return d[y] - d[x];
}
int count(int x,int y){
    return abs(x%10 - y%10) + abs(x/10%10 - y/10%10) + abs(x/100 - y/100);
}
void init(){
    d[0] = 0;
    for(int i = 1;i<1000;i++){
        //当然,通过打表或者手算你会发现d[i] = i + i/10*9 + i/100*9;
        d[i] = d[i-1] + count(i-1, i);
    }
}
int T;
void work(){
    int a,b,s;scanf("%03d%03d%d", &a, &b, &s);
    int ans[2] = {inf};
    for(int i = 0;i<=s;i++){
        int j = s-i;
        int dst = dist(a, a+i) + dist(b, b+j);
        ans[0] = min(ans[0], dst);
        ans[1] = max(ans[1], dst);
    }
    printf("Case %d: %d %d\n", ++T, ans[1], ans[0]);
}
int main() {
    #ifdef local
    freopen("in.txt","r",stdin);
    #endif // local
    init();
    int t;scanf("%d", &t);
    while(t--)
        work();
}
分类: 未分类

发表评论

电子邮件地址不会被公开。 必填项已用*标注

隐藏
变装