Skip to content

14009: 【原4009】步步为赢

题目

题目描述

author: yura 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4009

Description

丁姐起床以后才想起来今天要去参加步步为赢比赛第二轮,她打开比赛题目一看发现一大坨英文密码alsdifnpqwoienfskdanfpad......

丁姐和学科部的某个小盆友关系不错,所以问他要到了答案和加密的方法,加密方式如下:

第一步:对长度为l的明文,取它的某个约数a,将明文划分成l/a段

第二步:将每一段的第i个字连在一起,得到a段密文

第三步:按顺序将a段密文拼接在一起,得到完整密文

例子:

明文:THISISAWATERQUESTION

取a=4,分割为:THIS ISAW ATER QUES TION

每段第i个字母相连,得到4段密文:TIAQT HSTUI IAEEO SWRSN

连接密文:TIAQTHSTUIIAEEOSWRSN

话说虽然丁姐已经有了答案,但是她不能确定小盆友给她的答案是不是对的,你能帮帮她吗?

Input Format

第一行:一个字符串代表明文

第二行:一个字符串代表密文

字符串长度不超过100

Output Format

如果存在某个a(2<=a<=l)使得密文能够解密为明文,输出a。如果有多个a满足条件,输出最小的那个。

如果不存在这样的a,输出"No Solution"(不计引号)

Sample Input

THISISAWATERQUESTION
TIAQTHSTUIIAEEOSWRSN

Sample Output

4

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/23.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

using ll=long long;

int main() {
    char s[105], t[105];
    cin.getline(s, 103);
    cin.getline(t, 103);
    int l = strlen(s);
    int a;
    for (a = 2; a <= l; ++a) {
        if (l % a != 0) continue;
        char tmp[105];
        int count = 0;
        bool flag = true;
        for (int i = 0; i < a; ++i) {
            for (int j = i; j < l; j += a) {
                tmp[count++] = s[j];
                if (tmp[count - 1] != t[count - 1])
                    flag = false;
                if (!flag) break;
            }
            if (!flag) break;
        }
        if (flag) {
            cout << a << endl;
            return 0;
        }
    }
    if (a == l + 1) {
        cout << "No Solution" << endl;
    }
    return 0;
}

FineArtz's solution

/* 步步为赢 */
#include <iostream>
#include <string>
#include <cmath>
using namespace std;

bool devide(const string &s, const string &t, const int &x){
    string tmp = "";
    int len = s.size();
    for (int j = 0; j < x; ++j){
        for (int i = 0; i < len / x; ++i){
            tmp += s[i * x + j];
        }
    }
    if (tmp == t) return true;
    else return false;
}

int main(){
    string s, t;
    cin >> s >> t;
    int len = s.size();
    for (int i = 2; i <= len; ++i){
        if (len % i == 0){
            bool flag = devide(s, t, i);
            if (flag){
                cout << i << endl;
                return 0;
            }
        }
    }
    cout << "No Solution" << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstring"
using namespace std;

int main() {
    char input[200], output[200];
    cin >> output >> input;

    int length = strlen(input);
    bool flag = false;

    //寻找最小a
    for (int a = 1; a <= length; a++) {
        //判断是否整除
        if (length%a)
            continue;
        int gap = length / a;
        char temp[200] = { 0 };
        //拼接
        for (int i = 0,n=0; i<gap; i++) {
            for (int j = 0; j*gap<length; j++,n++) {
                temp[n] = input[j*gap + i];
            }
        }
        //判断结果
        if (strcmp(temp, output) == 0) {
            flag = true;
            cout << a;
            break;
        }
    }

    if (!flag)
        cout << "No Solution";

    return 0;
}

Neight99's solution

#include <cstring>
#include <iostream>

using namespace std;

template <class T>
class seqList {
   private:
    T *data;
    int Length;
    int maxSize;
    void doubleSpace();

   public:
    seqList(int initSize = 10);
    seqList(const seqList<T> &);
    ~seqList();
    int length() const;
    void add(const T &x);
    void traverse() const;
    void clear();
    seqList<T> operator+(seqList<T> &);
    seqList<T> &operator=(const seqList<T> &);
    T &operator[](int);
};

template <class T>
void seqList<T>::doubleSpace() {
    T *tmp = data;

    maxSize *= 2;

    data = new T[maxSize];
    for (int i = 0; i < Length; ++i) {
        data[i] = tmp[i];
    }

    delete[] tmp;
}

template <class T>
seqList<T>::seqList(int initSize) {
    data = new T[initSize];
    Length = 0;
    maxSize = initSize;
}

template <class T>
seqList<T>::~seqList() {
    delete[] data;
}

template <class T>
int seqList<T>::length() const {
    return Length;
}

template <class T>
void seqList<T>::add(const T &x) {
    if (Length == maxSize) {
        doubleSpace();
    }

    data[Length] = x;
    Length++;
}

template <class T>
void seqList<T>::traverse() const {
    for (int i = 0; i < Length - 1; i++) {
        cout << data[i] << ' ';
    }
    cout << data[Length - 1];
}

template <class T>
T &seqList<T>::operator[](int x) {
    return data[x];
}

template <class T>
void seqList<T>::clear() {
    Length = 0;
}

template <class T>
seqList<T>::seqList(const seqList<T> &right) {
    Length = right.Length;
    maxSize = right.maxSize;
    data = new T[maxSize];
    for (int i = 0; i < maxSize; i++) {
        data[i] = right.data[i];
    }
}

template <class T>
seqList<T> &seqList<T>::operator=(const seqList<T> &right) {
    if (&right != this) {
        delete[] data;

        Length = right.Length;
        maxSize = right.maxSize;
        data = new T[maxSize];
        for (int i = 0; i < Length; i++) {
            data[i] = right.data[i];
        }
    }

    return *this;
}

int main() {
    char ming[110], mi[110];
    int len;
    seqList<int> vec;

    cin >> ming >> mi;

    len = strlen(ming);

    for (int i = 1; (i * i) <= len; i++) {
        if (len % i == 0) {
            vec.add(i);
            if (len != i * i) {
                vec.add(len / i);
            }
        }
    }

    for (int i = 0; i < vec.length() - 1; i++) {
        for (int j = 0; j < vec.length() - i - 1; j++) {
            if (vec[j] > vec[j + 1]) {
                int tmp;
                tmp = vec[j + 1];
                vec[j + 1] = vec[j];
                vec[j] = tmp;
            }
        }
    }

    for (int i = 0; i < vec.length(); i++) {
        int tmp = vec[i], k = 0;
        char testmi[110] = {0};

        for (int j = 0; j < tmp; j++) {
            for (int l = 0; l < len / tmp; l++) {
                testmi[k] = ming[l * tmp + j];
                k++;
            }
        }

        if (strcmp(testmi, mi) == 0) {
            cout << tmp;
            return 0;
        }
    }

    cout << "No Solution";

    return 0;
}

q4x3's solution

/**
 * 模拟
 * 别忘了No Solution
 **/
#include <iostream>
#include <cstring>
using namespace std;

char s[105], ans[105], tmp[105];
int a;
bool flag = 0;

int main() {
    cin >> s;
    cin >> ans;
    for(int i = 2;i < strlen(s);++ i) {
        if(strlen(s) % i != 0) continue;
        a = i;
        for(int j = 0;j < strlen(s) / a;++ j) {
            for(int k = 0;k < a;++ k) {
                tmp[j + k * strlen(s) / a] = s[j * a + k];
            }
        }
        if(strcmp(tmp, ans) == 0) {
            flag = 1;
            break;
        }
    }
    if(flag) cout << a << endl;
    else cout << "No Solution" << endl;
    return 0;
}

skyzh's solution

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

int main() {
    char str[200], enc[200];
    cin.getline(str, 200);
    cin.getline(enc, 200);
    int L = strlen(str);
    if (strlen(str) == strlen(enc))
    for (int j = 2; j <= L; j++) {
        if (L % j == 0) {
            bool found = true;
            for (int i = 0, b = 0; i < L;) {
                if (str[b] != enc[i]) {
                    found = false;
                    break;
                }
                i++;
                b += j;
                if (b >= L) b = b - L + 1;
            }
            if (found) {
                cout << j << endl;
                return 0;
            }
        }
    }
    cout << "No Solution" << endl;
    return 0;
}

victrid's solution

#include <iostream>
#include <cstring>
using namespace std;
inline int div(int length, int index, int division) {
    return (index * (length / division) % (length - 1) + (length - 1)*(index == length - 1));
}
int main() {
    char cp[100];
    char ck[100];
    cin.getline(ck, 100);
    cin.getline(cp, 100);
    short int size = strlen(cp);
    if (cp[0] != ck[0] || size != strlen(ck)) {
        cout << "No Solution";
        return 0;
    }
    for (int i = size / 2; i >= 1; i--) {
        if (cp[i] == ck[1] && !(size % i)) {
            for (int j = 2; j < size; j++) {
                if (cp[div(size, j, size / i)] != ck[j])
                    goto z;
            }
            cout << size / i;
            return 0;
        }
    z:;
    }
    cout << "No Solution";
    return 0;
}