Timus – 第 4 页 – Pancake's Personal Website

Timus #1155

题目说明：立方体相邻两点可以同时相加或相减，要把每个点变为0的过程

解题思路：
1. 要有解则A + C + F + H = B + D + E + G
2. 进入循环直至每个点为0
3. 找到最小的位置。如果这个最小的位置旁边3个点都为0，则找到另外一个有数的点，再找这两点分别相邻的相邻的点加1。如果这个最小的位置旁边3个领点有数字，则找一个有数字的点进行相减。（听上去会有点绕）

Firstly, if it possible it will satisfy the equation A + C + F + H = B + D + E + G.
Secondly, go into loop, if every position is 0 quit the loop.
Thirdly, find the maximum position to decrease/increase. If this maximum position doesn’t have adjacent position to decrease, than find another position with value (not 0), increase 1 to two adjacent position adjacent to the maximum position and another position. Else decrease 1 to maximum position and the position adjacent to it.

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


int judge_done(int arr[8]) {
    for (int i = 0; i < 8; i++) {
        if (arr[i] != 0) {
            return 1;
        }
    }
    return 0;
}

int judge_zero(int arr[3], int arr_all[8]) {
    for (int i = 0; i < 3; i++) {
        if (arr_all[arr[i]] != 0) {
            return 1;
        }
    }
    return 0;
}

int find_same(int arr1[3], int arr2[3]) {
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (arr1[i] == arr2[j]) {
                return arr1[i];
            }
        }
    }
    return 0;
}


int main() {
    int arr[8];
    string arr_name = "ABCDEFGH";
    for (int i = 0; i < 8; i++)  cin >> arr[i];
    if (arr[0] + arr[2] + arr[5] + arr[7] != arr[1] + arr[3] + arr[4] + arr[6]) {
        cout << "IMPOSSIBLE" << endl;
    }
    else {
        int neighbor[8][3] = { { 1, 3, 4 } ,{ 0, 2, 5 },{ 1, 3, 6 },{ 0, 2, 7 },{ 0, 5, 7 },{ 1, 4, 6 },{ 2, 5, 7 },{ 3, 4, 6 } };
        int max, position, temp_position;
        while (judge_done(arr)) {
            max = arr[0]; position = 0;
            for (int i = 0; i < 8; i++) {
                max = max >= arr[i] ? max : arr[i];
                position = max > arr[i] ? position : i;
            }
            if (max > 0) {
                if (judge_zero(neighbor[position], arr)) {
                    for (int i = 0; i < 3; i++) {
                        if (arr[neighbor[position][i]] != 0) {
                            arr[position]--;
                            arr[neighbor[position][i]]--;
                            cout << arr_name[position] << arr_name[neighbor[position][i]] << "-" << endl;
                            break;
                        }
                    }
                }
                else {
                    for (int i = 0; i < 8; i++) {
                        if (i == position) continue;
                        else if (arr[i] != 0) {
                            temp_position = i;
                            break;
                        }
                    }
                    int position1 = neighbor[position][0];
                    int position2 = find_same(neighbor[position1], neighbor[temp_position]);
                    arr[position1]++; arr[position2]++;
                    cout << arr_name[position1] << arr_name[position2] << "+" << endl;
                }
            }
        }
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int judge_done(int arr[8]) {

for (int i = 0; i < 8; i++) {

if (arr[i] != 0) {

return 1;

}

return 0;

}

int judge_zero(int arr[3], int arr_all[8]) {

for (int i = 0; i < 3; i++) {

if (arr_all[arr[i]] != 0) {

return 1;

}

return 0;

}

int find_same(int arr1[3], int arr2[3]) {

for (int i = 0; i < 3; i++) {

for (int j = 0; j < 3; j++) {

if (arr1[i] == arr2[j]) {

return arr1[i];

}

return 0;

}

int main() {

int arr[8];

string arr_name = "ABCDEFGH";

for (int i = 0; i < 8; i++) cin >> arr[i];

if (arr[0] + arr[2] + arr[5] + arr[7] != arr[1] + arr[3] + arr[4] + arr[6]) {

cout << "IMPOSSIBLE" << endl;

}

else {

int neighbor[8][3] = { { 1, 3, 4 } ,{ 0, 2, 5 },{ 1, 3, 6 },{ 0, 2, 7 },{ 0, 5, 7 },{ 1, 4, 6 },{ 2, 5, 7 },{ 3, 4, 6 } };

int max, position, temp_position;

while (judge_done(arr)) {

max = arr[0]; position = 0;

for (int i = 0; i < 8; i++) {

max = max >= arr[i] ? max : arr[i];

position = max > arr[i] ? position : i;

}

if (max > 0) {

if (judge_zero(neighbor[position], arr)) {

for (int i = 0; i < 3; i++) {

if (arr[neighbor[position][i]] != 0) {

arr[position]--;

arr[neighbor[position][i]]--;

cout << arr_name[position] << arr_name[neighbor[position][i]] << "-" << endl;

break;

}

else {

for (int i = 0; i < 8; i++) {

if (i == position) continue;

else if (arr[i] != 0) {

temp_position = i;

break;

}

int position1 = neighbor[position][0];

int position2 = find_same(neighbor[position1], neighbor[temp_position]);

arr[position1]++; arr[position2]++;

cout << arr_name[position1] << arr_name[position2] << "+" << endl;

}

return 0;

}

Timus #2025

题目说明：有n个人分成了k组，不同组的人两两对打，要求对打局数最大。

题目解析：每组约平均得出结果越大，sum过程纯属数学计算过程。

Problem Analysis English version: We can easily notice from math calculations that the more average of each group, the bigger number we will get.

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

int main() {
	int ii;
	cin >> ii;
	int n, k, sum;
	for (int i = 0; i < ii; i++) {
		cin >> n; cin >> k;
		int group = n / k;
		int rest = n % k;
		sum = group * group * (k - 1) * k / 2 + rest * (rest - 1) / 2 + rest * (k - 1) * group;
		cout << sum << endl;
	}
	return 0;
}

#include<iostream>

#include<cmath>

using namespace std;

int main() {

int ii;

cin >> ii;

int n, k, sum;

for (int i = 0; i < ii; i++) {

cin >> n; cin >> k;

int group = n / k;

int rest = n % k;

sum = group * group * (k - 1) * k / 2 + rest * (rest - 1) / 2 + rest * (k - 1) * group;

cout << sum << endl;

}

return 0;

}

Timus #1401

题目说明：给定一个起点，剩下的用L形的三个方块进行填充。

题目解析：迭代。最大的正方形切成四个小正方形，一步步切下去直到最后剩余2*2的小正方形。在大正方形正中间四个方块，除起点所在象限的方块，即另外三个方块标记上相同数字。

Title Analysis English version: We can using iteration to solve problems. From the start position, starting to binary cut the matrix into four pieces until every sub-matrix is 2*2. I will mark the start position and the other three positions in the middle which has different quadrants besides the quadrant the start position in.

#include<iostream>
#include<cmath>
#include <memory.h>
using namespace std;


int matrix[512][512];
int mark = 0;


void generator(int beginx, int beginy, int endx, int endy, int x2, int y2) {
    int order = endx - beginx + 1;
    int positions[4][2] = { {order / 2 - 1 + beginx, order / 2 - 1 + beginy}, {order / 2 - 1 + beginx, order / 2 + beginy}, {order / 2 + beginx, order / 2 + beginy}, {order / 2 + beginx, order / 2 - 1 + beginy} };
    int min = abs(positions[0][0] - x2) + abs(positions[0][1] - y2), positionMin = 0;
    for (int i = 1; i < 4; i++) {
        int length = abs(positions[i][0] - x2) + abs(positions[i][1] - y2);
        positionMin = min < length ? positionMin : i;
        min = min < length ? min : length;
    }
    mark++;
    for (int i = 0; i < 4; i++) {
        if (i == positionMin) continue;
        else matrix[positions[i][0]][positions[i][1]] = mark;
    }
    if (order == 2) return;

    if (positionMin == 0)generator(beginx, beginy, positions[0][0], positions[0][1], x2 , y2);
    else generator(beginx, beginy, positions[0][0], positions[0][1], positions[0][0], positions[0][1]);

    if (positionMin == 1)generator(beginx, positions[1][1], positions[1][0], endy, x2, y2);
    else generator(beginx, positions[1][1], positions[1][0], endy, positions[1][0], positions[1][1]);

    if (positionMin == 2)generator(positions[2][0], positions[2][1], endx, endy, x2, y2);
    else generator(positions[2][0], positions[2][1], endx, endy, positions[2][0], positions[2][1]);

    if (positionMin == 3)generator(positions[3][0], beginy, endx, positions[3][1], x2, y2);
    else generator(positions[3][0], beginy, endx, positions[3][1], positions[3][0], positions[3][1]);


}

int main()
{
    int n, x, y, n2;
    cin >> n;
    cin >> x;
    cin >> y;
    n2 = pow(2, n);
    matrix[x - 1][y - 1] = 0;

    generator(0, 0, n2 - 1, n2 - 1, x - 1, y - 1);

    for (int i = 0; i < n2; i++)
    {
        for (int j = 0; j < n2 - 1; j++) cout << matrix[i][j] << " "; 
        cout << matrix[i][n2 - 1] << endl;
    }
}

#include<iostream>

#include<cmath>

#include <memory.h>

using namespace std;

int matrix[512][512];

int mark = 0;

void generator(int beginx, int beginy, int endx, int endy, int x2, int y2) {

int order = endx - beginx + 1;

int positions[4][2] = { {order / 2 - 1 + beginx, order / 2 - 1 + beginy}, {order / 2 - 1 + beginx, order / 2 + beginy}, {order / 2 + beginx, order / 2 + beginy}, {order / 2 + beginx, order / 2 - 1 + beginy} };

int min = abs(positions[0][0] - x2) + abs(positions[0][1] - y2), positionMin = 0;

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

int length = abs(positions[i][0] - x2) + abs(positions[i][1] - y2);

positionMin = min < length ? positionMin : i;

min = min < length ? min : length;

}

mark++;

for (int i = 0; i < 4; i++) {

if (i == positionMin) continue;

else matrix[positions[i][0]][positions[i][1]] = mark;

}

if (order == 2) return;

if (positionMin == 0)generator(beginx, beginy, positions[0][0], positions[0][1], x2 , y2);

else generator(beginx, beginy, positions[0][0], positions[0][1], positions[0][0], positions[0][1]);

if (positionMin == 1)generator(beginx, positions[1][1], positions[1][0], endy, x2, y2);

else generator(beginx, positions[1][1], positions[1][0], endy, positions[1][0], positions[1][1]);

if (positionMin == 2)generator(positions[2][0], positions[2][1], endx, endy, x2, y2);

else generator(positions[2][0], positions[2][1], endx, endy, positions[2][0], positions[2][1]);

if (positionMin == 3)generator(positions[3][0], beginy, endx, positions[3][1], x2, y2);

else generator(positions[3][0], beginy, endx, positions[3][1], positions[3][0], positions[3][1]);

}

int main()

{

int n, x, y, n2;

cin >> n;

cin >> x;

cin >> y;

n2 = pow(2, n);

matrix[x - 1][y - 1] = 0;

generator(0, 0, n2 - 1, n2 - 1, x - 1, y - 1);

for (int i = 0; i < n2; i++)

{

for (int j = 0; j < n2 - 1; j++) cout << matrix[i][j] << " ";

cout << matrix[i][n2 - 1] << endl;

}

Timus #1005

题目说明：把全部石头分成两部分，使得两堆石头质量相差最小

题目解析：dp动态规划

因为本人不会/没写过动态规划，该代码实为CSDN上的代码，本人做法为全排列，算法复杂度太高，runtime error。

#include <iostream>
#include <cstdio>
#include <cstring>                  //for memset 
#include <algorithm>                //for max
using namespace std;
const int M = 100;
int w[M];
int dp[M * 100000];
int main()
{
    int n;
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> w[i];
        sum += w[i];
    }
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; ++i)
        for (int j = sum / 2; j >= w[i]; --j)
            dp[j] = max(dp[j], dp[j - w[i]] + w[i]);
    cout << sum - dp[sum / 2] * 2 << endl;
    return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring> //for memset

#include <algorithm> //for max

using namespace std;

const int M = 100;

int w[M];

int dp[M * 100000];

int main()

{

int n;

cin >> n;

int sum = 0;

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

cin >> w[i];

sum += w[i];

}

memset(dp, 0, sizeof(dp));

for (int i = 0; i < n; ++i)

for (int j = sum / 2; j >= w[i]; --j)

dp[j] = max(dp[j], dp[j - w[i]] + w[i]);

cout << sum - dp[sum / 2] * 2 << endl;

return 0;

}

Timus #1296

题目解释：最大子序列的和

#include <iostream>
using namespace std;

int main() {
    int n, sum = 0, ans = 0, temp;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> temp;
        sum += temp;
        sum = sum > 0 ? sum : 0;
        ans = sum > ans ? sum : ans;
    }
    cout << ans << endl;
}

#include <iostream>

using namespace std;

int main() {

int n, sum = 0, ans = 0, temp;

cin >> n;

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

cin >> temp;

sum += temp;

sum = sum > 0 ? sum : 0;

ans = sum > ans ? sum : ans;

}

cout << ans << endl;

}