欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #666 (Div. 2) ------ Multiples of Length

程序员文章站 2022-04-30 22:49:44
...

题目

You are given an array a of n integers.

You want to make all elements of a equal to zero by doing the following operation exactly three times:

Select a segment, for each number in this segment we can add a multiple of len to it, where len is the length of this segment (added integers can be different).

It can be proven that it is always possible to make all elements of a equal to zero.

Codeforces Round #666 (Div. 2) ------ Multiples of Length

题解:

这题的大致题意即给定你一个长度为n的数组,然后进行3次操作(不可以多于3次,也不可以少于三次)。操作要求如下:选定一个区间,区间长度为r - l + 1,这个区间内每个数都可以加上m * (r - l + 1),m为任意整数,且对于每个数m的值都可以不同。
求解方法:这里采用一种特殊的通解
第一次操作:选定区间1-(n - 1),是其里面的数a[i]都变成n * a[i],即加上(n - 1)* a[i],符合操作要求
第二次操作:对最后一个数a[n]进行操作,使其变为0
第三次操作:选定区间1 - n,减去n * a[i], 使其整个数组变为0;

AC代码

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<map>
#include<string>
using namespace std;
#define ll long long
const int N = 1e5 + 15;
ll a[N];
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int n; cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	if (n == 1) {
		cout << 1 << " " << 1 << endl;
		cout << -a[0] << endl;
		cout << 1 << " " << 1 << endl;
		cout << 0 << endl;
		cout << 1 << " " << 1 << endl;
		cout << 0 << endl;
	}
	else {
		cout << "1 " << n - 1 << endl;
		for (int i = 0; i < n - 1; i++) {
			cout << a[i] * (n - 1) << " ";
			a[i] = n * a[i];
		}
		cout << endl;
		cout << n << " " << n << endl;
		cout << -a[n - 1] << endl;
		a[n - 1] = 0;
		cout << 1 << " " << n << endl;
		for (int i = 0; i < n; i++)
			cout << -a[i] << " ";
	}
	return 0;
}

Python代码

n = int(input())
a = []
a = list(map(int, input().split()))
if n == 1:
    print("1 1")
    print(-a[0])
    print("1 1")
    print(0)
    print("1 1")
    print(0)
else:
    print("1 {}".format(n - 1))
    for i in range(n - 1):
        print("{}".format((n - 1) * a[i]), end = " ")
        a[i] = n * a[i]
    print()
    print("{} {}".format(n, n))
    print(-a[n - 1])
    a[n - 1] = 0
    print("{} {}".format(1, n))
    for i in range(n):
        print("{}".format(-a[i]), end = " ")
    print()