分类 题解 下的文章

Java_Experiment

本仓库为Java课程实验代码库

  • 仓库下与本文件同层的首层文件夹为实验次数,内层文件夹为实验内题目标号,src文件夹下为工程的java源文件
  • 代码使用的 IDE 主要是 Intellij IDEA, 较少时候使用Eclipse,但保证经过了阿里巴巴Java开发手册的基本要求(部分代码由于题目要求可能并不遵守此规约),运行class文件时带有自定义参数 -ea
  • 代码使用的 JDK 主要是 Oracle JDK 11 和 Open JDK 8 (两个版本均包括但不限于AdoptOpenJDK ,AWS的CorrettoOpen JDK),不作于任何商业用途。
  • 仓库中的代码简记是自己学习的时候整理记录的,借鉴了API和网络的部分内容,以后有时间会考虑写完自己的总结
  • 目前PTA的所有题目都完成了AC代码,Java课程做过的PTA题目对应的代码链接如下

- 阅读剩余部分 -

Describe 一个规则的实心十二面体,它的 20 个顶点标出世界著名的 20 个城市,你从一个城市出发经过每个城市刚好一次后回到出发的城市。 Input 前 20 行的第 i 行有 3 个数,表示与第 i 个城市相邻的 3 个城市.第 20 行以后每行有 1 个数 m,m<=20,m>=1.m=0 退出. Output 输出从第 m 个城市出发经过每个城市 1 次又回到 m 的所有路线,如有多条路线,按字典序输出,每行 1 条路线.每行首先输出是第几条路线.然后个一个: 后列出经过的城市.参看 Sample output

- 阅读剩余部分 -

这么久没遇到过这样的题目了,忍不住写一下~
题目链接:PTA
7-1 jmu-ds-集合的并交差运算 (15 分)

/*
有两个整数集合A和B,现在要求实现集合的并、交、差运算。
例如A={2,7,9} ,B={3,7,12,2}, 则集合的并C=A∪B={2,7,9,3,12},
而集合的交 C=A∩B={2,7},集合的差C=A-B={9}。
集合A和B中元素个数在1~100之间。 

输入格式: 三行,
第一行分别为集合A,B的个数 
第二行为A集合的数据 
第三行为B集合的数据

输出格式: 三行
第一行集合并的结果:C的个数及C中的元素 
第二行集合交的结果:C的个数及C中的元素 
第三行集合差的结果:C的个数及C中的元素 
输出结果以元素在A集合中的先后顺序输出,不能改变数据的输出顺序 

输入样例: 3 4 2 7 9 3 7 12 2 

输出样例: 5 2 7 9 3 12 2 2 7 1 9 
*/

这个题意很简单,一开始没注意到顺序的问题,使用的set 的函数来进行,错了,后来发现了顺序的问题,改了改再去提交还是不对,这个时候我看到了通过率 是 0 %,就觉得肯定后台数据有问题,就一直放着没做,结果就考试结束了 直到今天2018/09/25
我一定要记住这个日子,因为这个题目在我百度谷歌都无果后,终于知道了正确答案~,说出来我自己都不信
你只要,在输出集合的时候,当集合中元素,小于5 或者 6 的时候,不输出个数就行了。。
此处感谢软件的机智勇敢大无畏的同学们,是你们让我知道了,这道题的正确解答是什么,死的明明白白

    #include <bits/stdc++.h>
    using namespace std;
    typedef int ElemType;
    typedef struct
    {
        ElemType *elem;
        int length;
        int listsize;
    } SqList;
    void Sqlistiniti(SqList &s)
    {
        s.elem = new ElemType[1009];
        s.length = 0;
        s.listsize = 1009;
    }
    void Sqlistcreate(SqList &s, int n)
    {
        Sqlistiniti(s);
        s.length = n;
        for (int i = 0; i < n; i++)
        {
            cin >> s.elem[i];
        }
    }

    SqList bingji(SqList &a, SqList &b)
    {
        SqList c;
        Sqlistiniti(c);
        int i;
        int k;
        for (i = 0; i < a.length; i++)
        {
            c.elem[i] = a.elem[i];
            c.length++;
        }
        int n = i;
        for (int j = 0; j < b.length; j++)
        {
            int flag = 1;
            for (k = 0; k < c.length; k++)
            {
                if (b.elem[j] == c.elem[k])
                {
                    flag = 0;
                    break;
                }
            }
            if (flag)
            {
                c.elem[i++] = b.elem[j];
                c.length++;
            }
        }
        return c;
    }
    SqList jiaoji(SqList &a, SqList &b)
    {
        SqList c;
        Sqlistiniti(c);
        int k = 0;
        for (int i = 0; i < a.length; i++)
        {
            for (int j = 0; j < b.length; j++)
            {
                if (a.elem[i] == b.elem[j])
                {
                    c.elem[k++] = a.elem[i];
                    c.length++;
                }
            }
        }
        return c;
    }

    SqList chaji(SqList &a, SqList &b)
    {
        SqList c;
        Sqlistiniti(c);
        int j, k = 0;
        for (int i = 0; i < a.length; i++)
        {
            int flag = 1;
            for (j = 0; j < b.length; j++)
            {
                if (a.elem[i] == b.elem[j])
                {
                    flag = 0;
                    break;
                }
            }
            if (flag)
            {
                c.elem[k++] = a.elem[i];
                c.length++;
            }
        }
        return c;
    }
    void Sqlistprint(SqList &s, SqList &a)
    {
        int f = 0;
        if (a.length <= 6)
        {
            cout << s.length;
            for (int i = 0; i < s.length; i++)
            {
                cout << " " << s.elem[i];
            }
        }
        else
            for (int i = 0; i < s.length; i++)
            {
                if (i)
                    cout << " ";
                cout << s.elem[i];
            }
        cout << endl;
    }

    int main()
    {
        SqList a, b, c;
        int n1, n2;
        cin >> n1 >> n2;
        Sqlistcreate(a, n1);
        Sqlistcreate(b, n2);
        c = bingji(a, b);
        Sqlistprint(c, a);
        c = jiaoji(a, b);
        Sqlistprint(c, a);
        c = chaji(a, b);
        Sqlistprint(c, a);
        return 0;
    }

题目来自 网络与信息安全-数据结构作业1-数据结构基本概念 6-1

原题描述


6-1 顺序表基本操作(10 分)
本题要求实现顺序表元素的增、删、查找以及顺序表输出共4个基本操作函数。L是一个顺序表,函数Status ListInsert_Sq(SqList &L, int pos, ElemType e)是在顺序表的pos位置插入一个元素e(pos应该从1开始),函数Status ListDelete_Sq(SqList &L, int pos, ElemType &e)是删除顺序表的pos位置的元素并用引用型参数e带回(pos应该从1开始),函数int ListLocate_Sq(SqList L, ElemType e)是查询元素e在顺序表的位次并返回(如有多个取第一个位置,返回的是位次,从1开始,不存在则返回0),函数void ListPrint_Sq(SqList L)是输出顺序表元素。实现时需考虑表满扩容的问题。
函数接口定义
Status ListInsert_Sq(SqList &L, int pos, ElemType e);
Status ListDelete_Sq(SqList &L, int pos, ElemType &e);
int ListLocate_Sq(SqList L, ElemType e);
void ListPrint_Sq(SqList L);
其中 L 是顺序表。 pos 是位置; e 代表元素。当插入与删除操作中的pos参数非法时,函数返回ERROR,否则返回OK。

裁判测试程序样例:

//库函数头文件包含
#include
#include
#include


//函数状态码定义
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE -1
#define OVERFLOW   -2

typedef int  Status;

//顺序表的存储结构定义
#define LIST_INIT_SIZE  100
#define LISTINCREMENT   10
typedef int ElemType;  //假设线性表中的元素均为整型
typedef struct{
    ElemType* elem;   //存储空间基地址
    int length;       //表中元素的个数
    int listsize;     //表容量大小
}SqList;    //顺序表类型定义
Status ListInsert_Sq(SqList &L, int pos, ElemType e);
Status ListDelete_Sq(SqList &L, int pos, ElemType &e);
int ListLocate_Sq(SqList L, ElemType e);
void ListPrint_Sq(SqList L);

//结构初始化与销毁操作
Status InitList_Sq(SqList &L){
  //初始化L为一个空的有序顺序表
    L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!L.elem)exit(OVERFLOW);
    L.listsize=LIST_INIT_SIZE;
    L.length=0;
    return OK;
}


int main() {
    SqList L;

    if(InitList_Sq(L)!= OK) {
        printf("InitList_Sq: 初始化失败!!!n");
        return -1;
    }

    for(int i = 1; i <= 10; ++ i)
        ListInsert_Sq(L, i, i);

    int operationNumber;  //操作次数
    scanf("{2186e5f7970dac0e9cf7cfc7913f086a2d003118a30b627bce447294ada8be4e}d", &operationNumber);

    while(operationNumber != 0) {
        int operationType;  //操作种类
        scanf("{2186e5f7970dac0e9cf7cfc7913f086a2d003118a30b627bce447294ada8be4e}d", & operationType);

        if(operationType == 1) {  //增加操作
            int pos, elem;
            scanf("{2186e5f7970dac0e9cf7cfc7913f086a2d003118a30b627bce447294ada8be4e}d{2186e5f7970dac0e9cf7cfc7913f086a2d003118a30b627bce447294ada8be4e}d", &pos, &elem);
            ListInsert_Sq(L, pos, elem);
        } else if(operationType == 2) {  //删除操作
             int pos; ElemType elem;
             scanf("{2186e5f7970dac0e9cf7cfc7913f086a2d003118a30b627bce447294ada8be4e}d", &pos);
             ListDelete_Sq(L, pos, elem);
             printf("{2186e5f7970dac0e9cf7cfc7913f086a2d003118a30b627bce447294ada8be4e}dn", elem);
        } else if(operationType == 3) {  //查找定位操作
            ElemType elem;
            scanf("{2186e5f7970dac0e9cf7cfc7913f086a2d003118a30b627bce447294ada8be4e}d", &elem);
            int pos = ListLocate_Sq(L, elem);
            if(pos >= 1 && pos <= L.length)
                printf("{2186e5f7970dac0e9cf7cfc7913f086a2d003118a30b627bce447294ada8be4e}dn", pos);
            else
                printf("NOT FIND!n");
        } else if(operationType == 4) {  //输出操作
            ListPrint_Sq(L);
        }
       operationNumber--;
    }
    return 0;
}

/* 请在这里填写答案 */

输入格式: 第一行输入一个整数operationNumber,表示操作数,接下来operationNumber行,每行表示一个操作信息(含“操作种类编号 操作内容”)。 编号为1表示插入操作,后面两个参数表示插入的位置和插入的元素值 编号为2表示删除操作,后面一个参数表示删除的位置 编号为3表示查找操作,后面一个参数表示查找的值 编号为4表示顺序表输出操作 输出格式: 对于操作2,输出删除的元素的值 对于操作3,输出该元素的位置,如果不存在该元素,输出“NOT FOUND”; 对于操作4,顺序输出整个顺序表的元素,两个元素之间用空格隔开,最后一个元素后面没有空格。

输入样例:

4
1 1 11
2 2
3 3
4

输出样例:

1
3
11 2 3 4 5 6 7 8 9 10

笔记部分

一、 realoc 函数

  • realloc 函数的使用要求引入头文件 stdlib.h

  • 该函数的原型为realloc(void *__ptr, size_t __size)

void* __cdecl realloc(
    _Pre_maybenull_ _Post_invalid_ void*  _Block,
    _In_ _CRT_GUARDOVERFLOW        size_t _Size
    );
  • 也就是传入的第一个参数是指针类型,第二个参数是更改后的大小。

    • 如果操作使得内存分配减少,那么函数仅仅是改变了索引信息;
    • 如果操作使得内存分配增加,那么当当前内存之后有足够的内存来扩展的时候,函数直接扩展内存,返回指针;当当前内存段之后没有足够的空闲内存时,函数寻找堆 中的第一个能满足申请内存大小的内存段,将数据复制,并且释放旧的内存,返回指针。申请失败返回NULL
    • 返回的是指针,但无论何种情况,实际上都不保证返回原指针(可以通过输出地址尝试),原指针会被函数自动的释放,不可二次释放原指针

AC 代码

void ListPrint_Sq(SqList L){
    ElemType maxn = L.length;
    for (ElemType i = 0; i < maxn; ++i){
        if(i){
            printf(" ");
        }
        printf("{2186e5f7970dac0e9cf7cfc7913f086a2d003118a30b627bce447294ada8be4e}d", L.elem[i]);
    }
    puts("");
    return;
}

int ListLocate_Sq(SqList L, ElemType e){
    ElemType maxn = L.length;
    for (ElemType i = 0; i < maxn; ++i){
        if(L.elem[i] == e){
            return i + 1;
        }
    }
    return FALSE;
}

Status ListDelete_Sq(SqList &L, int pos, ElemType &e){
    ElemType maxn = L.length;
    if(pos < 1 || pos > maxn){
        return ERROR;
    }
    e = L.elem[pos - 1];
    for (ElemType i = pos - 1; i < maxn - 1; ++i){
        L.elem[i] = L.elem[i + 1];
    }
    L.length -= 1;
    // printf("DEL  {2186e5f7970dac0e9cf7cfc7913f086a2d003118a30b627bce447294ada8be4e}dn", L.length);
    // ListPrint_Sq(L);
    return OK;
}

Status ListInsert_Sq(SqList &L, int pos, ElemType e){
    ElemType maxn = L.length;
    if(pos < 1 || pos > maxn + 1){
        return ERROR;
    }
    if(L.length >= L.listsize){
        ElemType *newe;
        newe = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
        if(!newe){
            return OVERFLOW;
        }
        else {
            L.elem = newe;
            L.listsize += LISTINCREMENT;
        }
    }
    for (ElemType i = maxn; i >= pos; --i){
        L.elem[i] = L.elem[i - 1];
    }
    L.elem[pos - 1] = e;
    L.length += 1;
    // ListPrint_Sq(L);
    return OK;
}

/*
11 1 2 3 4 5 6 7 8 9 10
11 2 3 4 5 6 7 8 9 10

*/

[TOCM]

# 原题

Consider an n \times mn×m matrix of ones and zeros. For example, this 4 × 4:

1111
0111
0111
0110

We can compute even parity for each row, and each column. In this case, the row parities are [0, 1, 1, 0][0,1,1,0] and the column parities are [1, 0, 0, 1][1,0,0,1] (the parity is 11 if there is an odd number of 11s in the row or column, 00 if the number of 11s is even). Note that the top row is row 11, the bottom row is row nn, the leftmost column is column 11, and the rightmost column is column mm.
Suppose we lost the original matrix, and only have the row and column parities. Can we recover the original matrix? Unfortunately, we cannot uniquely recover the original matrix, but with some constraints, we can uniquely recover a matrix that fits the bill. Firstly, the recovered matrix must contain as many 11’s as possible. Secondly, of all possible recovered matrices with the most 11’s, use the one which has the smallest binary value when you start with row 11, concatenate row 22 to the end of row 11, then append row 33, row 44, and so on.

Input Format
Each input will consist of a single test case.

Note that your program may be run multiple times on different inputs.

Each test case will consist of exactly two lines.

The first line will contain a string R (1 \le |R| \le 50)R(1≤∣R∣≤50), consisting only of the characters 00 and 11. These are the row parities, in order.

The second line will contain a string C (1 \le |C| \le 50)C(1≤∣C∣≤50), consisting only of the characters 00 and 11. These are the column parities, in order.

Output Format
If it is possible to recover the original matrix with the given constraints, then output the matrix as |R|∣R∣ lines of exactly |C|∣C∣ characters, consisting only of 00’s and 11’s. If it is not possible to recover the original matrix, output -1−1.

样例输入1
0110
1001
样例输出1
1111
0111
1110
1111
样例输入2
0
1
样例输出2
-1
样例输入3
11
0110
样例输出3
1011
1101
题目来源

The North American Invitational Programming Contest 2018

# 简要概括 #

题目的意思是,一开始有一个矩阵,每一行的 1 的个数如果是偶数个,记为0,奇数个记为1,所以这样会根据矩阵行列中的 1 的个数 来形成两个10字符串。现在已知这个最终的字符串,要我们还原出原先的矩阵,两点额外的要求:
+ 使矩阵中 1 的数目尽可能的多
+ 最后的矩阵的每一行连接起来形成的二进制数最小

# 思路 #

这样一来我们可以分析得到,我们要在满足尽可能多的 1 的数目的前提下,把 1 往矩阵的右下角扔,这样可以保证,得到的二进制数最小。然后就是另一个问题,我们如何保证当前是尽可能多的 1
一开始想把 1 先往右下角放,然后遍历上去,最后检查,但是后来发现这个做法不可取,因为最后一行有可能并不一定都能通过改动变化成合法的,所以后期就把策略改成了

先把一个矩阵全部假设为1,然后从左上角开始,根据当前的行列中 1 的奇偶数,来判断需要置零的坐标

这个时候要注意 ,对于下面这一种情况的特判,当时找了好久的BUG
00
11
答案应该是
00
11

如果根据我们的算法,x 和 y 的坐标数不对等的话,还要根据二者的差值是否是偶数,来判断能否更改成合法矩阵,二者差值为奇数的情况始终不可能修改成合法的矩阵,应该输出 -1.

# Code Share #

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = (int)50 + 1;
int dic[maxn][maxn];

int main(int argc, char const *argv[])
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    string a, b;
    while(cin >> a >> b){
        memset(dic,0,sizeof(dic));
        vector<int> cmda,cmdb;
        bool have = false;
        int lena = a.size(), lenb = b.size();
        for(int i = 0;i < lena; i++){
            if(lenb & 1 && a[i] == '0'){
                cmda.push_back(i);
            }
            else if(a[i] == '1' && !(lenb&1)){
                cmda.push_back(i);
            }
        }
        for(int i = 0;i < lenb; i++){
            if(lena & 1 && b[i] == '0'){
                cmdb.push_back(i);
            }
            else if(b[i] == '1' && !(lena&1)){
                cmdb.push_back(i);
            }
        }
        if((cmda.size()-cmdb.size()) & 1){
            cout << -1 << endl;
            have = true;
        }
        else if(cmda.size() == cmdb.size()){
            int sl = cmda.size();
            for(int i = 0;i < sl; i++){
                dic[cmda[i]][cmdb[i]]++;
            }
        }
        else{
            if(cmda.size() < cmdb.size()){
                int i = 0,j = 0;
                for(i = 0;i < (int)cmdb.size() - (int)cmda.size(); i++){
                    dic[0][cmdb[i]]++;
                }
                for(;j < (int)cmda.size();){
                    dic[cmda[j++]][cmdb[i++]]++;
                }
            }
            else{
                int i = 0,j = 0;
                for(i = 0;i < (int)cmda.size() - (int)cmdb.size(); i++){
                    dic[cmda[i]][0]++;
                }
                for(;j < (int)cmdb.size();){
                    dic[cmda[i++]][cmdb[j++]]++;
                }
            }
        }
        for(int i = 0;i < lena && !have; i++){
            for(int j = 0;j < lenb; j++){
                cout << 1 - dic[i][j];
            }
            // cout << "     " << i+1;
            cout << endl;
        }
    }
    return 0;
}

代码应该很容易懂,也没加上啥巧办法,就是生写的。

                                                            -- 2018.08.12