Misc – hahaschool

思路

这个题刚到手其实都是会写的，但是一般交上去会发现爆内存，原因就是我们用来判定self number的数组开太大了，要想减少空间复杂度只能从这个数组入手，那么我们真的需要那么大的数组么？显然是不用的，通过本题的数据范围可以发现N最大为7位数，即使7位全是9，我们能够更新到的数组区域长度也仅为63个单位，所以我们把bool标记数组开个63长度就够了，开100那更是没问题，这个技巧就是所谓的“滚动数组”。
滚动数组的操作方法有几点：1.通过求余来确定位置 2.使用完当前位置后，要给它初始化为没有使用过的样子以便以后的元素正常使用。
仅仅使用滚动数组还不足以完成这个题，还要注意输出答案的方式，因为数组在滚动，所以你不可能在完成判定之后再输出结果，而是应该边滚动判定，边记录，最后把记录的输出去。
本题有几个坑点：首先你要把输出的目标索引排个序，否则如果数据是乱序的基本都会跪，其次要注意请求的索引中是有重复的，可能一个索引被请求了多次。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

bool isself[100];
vector<pair<int, int> > goal;
int container[5005];

bool cmp(pair<int, int> a,pair<int, int> b){
    return a.first < b.first;
}

int main(){
    int n = 0,k = 0;
    scanf(" %d %d",&n,&k);
    goal.clear();
    for (int i = 1; i <= k; i++) {
        int tmp = 0;
        scanf(" %d",&tmp);
        goal.push_back(make_pair(tmp, i));
    }
    sort(goal.begin(), goal.end(),cmp);
    memset(isself, true, sizeof(isself));
    memset(container, 0, sizeof(container));
    int cnt = 0;
    int cur = 0;
    for (int i = 1; i <= n; i++) {
        if (isself[i%64]) {
            cnt++;
            while (cnt == goal[cur].first) {
                container[goal[cur].second] = i;
                cur++;
            }
        }
        int tmp = i,sum = i;
        while (tmp != 0) {
            sum += tmp%10;
            tmp /= 10;
        }
        isself[sum%64] = false;
        isself[i%64] = true;
    }
    printf("%d\n",cnt);
    for (int i = 1;i < k; i++) {
        printf("%d ",container[i]);
    }
    printf("%d\n",container[k]);
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

bool isself[100];

vector<pair<int, int> > goal;

int container[5005];

bool cmp(pair<int, int> a,pair<int, int> b){

return a.first < b.first;

}

int main(){

int n = 0,k = 0;

scanf(" %d %d",&n,&k);

goal.clear();

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

int tmp = 0;

scanf(" %d",&tmp);

goal.push_back(make_pair(tmp, i));

}

sort(goal.begin(), goal.end(),cmp);

memset(isself, true, sizeof(isself));

memset(container, 0, sizeof(container));

int cnt = 0;

int cur = 0;

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

if (isself[i%64]) {

cnt++;

while (cnt == goal[cur].first) {

container[goal[cur].second] = i;

cur++;

}

int tmp = i,sum = i;

while (tmp != 0) {

sum += tmp%10;

tmp /= 10;

}

isself[sum%64] = false;

isself[i%64] = true;

}

printf("%d\n",cnt);

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

printf("%d ",container[i]);

}

printf("%d\n",container[k]);

return 0;

}

Proceed big numbers A and B,A and B have same digits(Both A and B have no prelude zeros),A contains uncertain digits marking ‘?’.Find a largest A to make A < B.

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

int main(){
    int caseCnt = 0;
    cin >> caseCnt;
    while (caseCnt--) {
        string a,b;
        cin >> a >> b;
        int bound = (int)a.size();
        bool flag = false;
        bool ok = true;
        for (int i = 0; i < a.size(); i++) {
            if (a[i] != '?') {
                if (a[i] > b[i]) {
                    ok = false;
                    bound = i;
                    break;
                }
                if (a[i] < b[i]) {
                    bound = i;
                    flag = true;
                    break;
                }
            }
        }
        if (!ok) {
            for (int i = bound-1; i >= 0; i--) {
                if (a[i] == '?') {
                    if (b[i] != '0') {
                        a[i] = b[i] - 1;
                        bound = i;
                        ok = true;
                        flag = true;
                        break;
                    }
                }
            }
        }
        if (ok) {
            for (int i = bound-1; i >= 0; i--) {
                if (a[i] == '?') {
                    if (flag) {
                        a[i] = b[i];
                    }else if (b[i] != '0') {
                        a[i] = b[i] - 1;
                        bound = i;
                        flag = true;
                    }
                }
            }
            for (int i = bound+1; i < a.size(); i++) {
                if (a[i] == '?') {
                    a[i] = '9';
                }
            }
            for (int i = 0; i < a.size(); i++) {
                if (!isdigit(a[i])) {
                    ok = false;
                    break;
                }
            }
            if (a[0] == '0' && a.size() > 1) {
                ok = false;
            }
            if (a == b) {
                ok = false;
            }
        }
        if (ok) {
            cout << a << endl;
        }else{
            cout << -1 << endl;
        }
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstdio>

#include <string>

#include <cstring>

#include <ctime>

#include <iomanip>

#include <cmath>

#include <set>

#include <stack>

#include <cmath>

using namespace std;

int main(){

int caseCnt = 0;

cin >> caseCnt;

while (caseCnt--) {

string a,b;

cin >> a >> b;

int bound = (int)a.size();

bool flag = false;

bool ok = true;

for (int i = 0; i < a.size(); i++) {

if (a[i] != '?') {

if (a[i] > b[i]) {

ok = false;

bound = i;

break;

}

if (a[i] < b[i]) {

bound = i;

flag = true;

break;

}

if (!ok) {

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

if (a[i] == '?') {

if (b[i] != '0') {

a[i] = b[i] - 1;

bound = i;

ok = true;

flag = true;

break;

}

if (ok) {

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

if (a[i] == '?') {

if (flag) {

a[i] = b[i];

}else if (b[i] != '0') {

a[i] = b[i] - 1;

bound = i;

flag = true;

}

for (int i = bound+1; i < a.size(); i++) {

if (a[i] == '?') {

a[i] = '9';

}

for (int i = 0; i < a.size(); i++) {

if (!isdigit(a[i])) {

ok = false;

break;

}

if (a[0] == '0' && a.size() > 1) {

ok = false;

}

if (a == b) {

ok = false;

}

if (ok) {

cout << a << endl;

}else{

cout << -1 << endl;

}

return 0;

}

策略是先从前往后扫描一遍已知的数位，如果相等的话，放过当前位，如果当前位a>b这时停止扫描，纪录扫到的位置i，记录状态为1，如果当前位a<b这时停止扫描记录扫描到位置i，状态为2.

对与状态1，如果我们不能在i之前找到一个‘？’使这一位正好比b少1，那么无解，找到了的话，就记录这个新位置为i，跳到状态2。

对于状态2，只要令i左边的数位和B一样，右边的数位都是9就可以了。

都完成之后，做一下最终检查，注意只有一位数时首位可以为0，A!=B就可以了。

Tag: Misc

SGU 108 Self-numbers 2

题意

思路

代码

FZU 2159 WuYou