[原创]Codeforces #353 div.2 Infinite Sequence&Restoring Painting&Money Transfers前三题题解

2016-05-18 21:59:54 Tabris_ 阅读数：531

博客爬取于2020-06-14 22:44:27
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/51447994

题目链接：
A :http://codeforces.com/problemset/problem/675/A
B :http://codeforces.com/problemset/problem/675/B
C :http://codeforces.com/problemset/problem/675/C

A

A. Infinite Sequence
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Vasya likes everything infinite. Now he is studying the properties of a sequence s, such that its first element is equal to a (s1 = a), and the difference between any two neighbouring elements is equal to c (si - si - 1 = c). In particular, Vasya wonders if his favourite integer b appears in this sequence, that is, there exists a positive integer i, such that si = b. Of course, you are the person he asks for a help.

Input
The first line of the input contain three integers a, b and c ( - 109 ≤ a, b, c ≤ 109) — the first element of the sequence, Vasya’s favorite number and the difference between any two neighbouring elements of the sequence, respectively.

Output
If b appears in the sequence s print “YES” (without quotes), otherwise print “NO” (without quotes).

Examples

input
1 7 3
output
YES

input
10 10 0
output
YES

input
1 -4 5
output
NO

input
0 60 50
output
NO

Note
In the first sample, the sequence starts from integers 1, 4, 7, so 7 is its element.

In the second sample, the favorite integer of Vasya is equal to the first element of the sequence.

In the third sample all elements of the sequence are greater than Vasya’s favorite integer.

In the fourth sample, the sequence starts from 0, 50, 100, and all the following elements are greater than Vasya’s favorite integer.

题目大意：就是有一个等差数列给你首元素与公差再给你一个数判断其在不在等差数列上

题目很简单

判断（b-a）mod C == 0 ？

注意的是C<0 与C = 0 的情况稍加判断即可

直接上代码

# include <stdio.h>
# define _LL __int64
int main()
{

    _LL a,b,c;
    scanf("%I64d%I64d%I64d",&a,&b,&c);
    int flag=0;

    if(c<0)
    {
        a=-a,b=-b,c=-c;
    }

    if(a==b)  flag=1;
    if(c!=0&&a<b&&(b-a)%c==0)
        flag=1;

    if(flag)    printf("YES\n");
    else        printf("NO\n");

    return 0;
}

B

B. Restoring Painting
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Vasya works as a watchman in the gallery. Unfortunately, one of the most expensive paintings was stolen while he was on duty. He doesn’t want to be fired, so he has to quickly restore the painting. He remembers some facts about it.

The painting is a square 3 × 3, each cell contains a single integer from 1 to n, and different cells may contain either different or equal integers.
The sum of integers in each of four squares 2 × 2 is equal to the sum of integers in the top left square 2 × 2.
Four elements a, b, c and d are known and are located as shown on the picture below.

Help Vasya find out the number of distinct squares the satisfy all the conditions above. Note, that this number may be equal to 0, meaning Vasya remembers something wrong.

Two squares are considered to be different, if there exists a cell that contains two different integers in different squares.

Input
The first line of the input contains five integers n, a, b, c and d (1 ≤ n ≤ 100 000, 1 ≤ a, b, c, d ≤ n) — maximum possible value of an integer in the cell and four integers that Vasya remembers.

Output
Print one integer — the number of distinct valid squares.

Examples
input
2 1 1 1 2
output
2
input
3 3 1 2 3
output
6
Note
Below are all the possible paintings for the first sample.

In the second sample, only paintings displayed below satisfy all the rules.

题目大意 : 给你一个九宫格其中四个角和中间的数是未知的
给定你一个数 n 和其他四个数a,b,c,d
问在四个角和中间的格子上填上1~n中的数 (可以重复填入)
使得四个2x2的格子数的和相等的填法有多少种

解题思路：

Tables	Are	Cool
x1	a	x2
b	??	c
x3	d	x4

2x2的情况为
1: x1+a+b+??
2: x2+a+c+??
3: x3+d+b+??
4: x4+c+d+??
显然中间的？？填什么多可以即有n中填法

同时也能得到
当任意x值确定的时候其他值也就确定了

假定当 x1,x2,x3,x4满足题意的时候
x1+1,x2+1,x3+1,x4+1 也满足题意（当中最大值<=n）

这个时候我们只要枚举一下
a+b, b+d,d+c,a+c的最大值这时候其对应的x值为1

结果即为
count（maxX~n) * n;

附本题代码

# include <stdio.h>
# define _LL __int64
int main()
{
    int n,a,c,b,d;
    scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
    _LL sum=1;
    int maxi=-11,m;

    int x1=-1,x2=-1,x3=-1,x4=-1;

    if(a+b>=max(max(a+c,c+d),d+b))
    {
        x1=1;
        m=a+b+1;
        x2=m-a-c;
        x3=m-b-d;
        x4=m-c-d;
    }
    if(a+c>=max(max(a+b,c+d),d+b))
    {
        x2=1;
        m=a+c+1;
        x1=m-a-b;
        x3=m-b-d;
        x4=m-c-d;
    }
    if(d+b>=max(max(a+c,c+d),a+b))
    {
        x3=1;
        m=d+b+1;
        x1=m-a-b;
        x2=m-a-c;
        x4=m-c-d;
    }
    if(c+d>=max(max(a+c,a+b),d+b))
    {
        x4=1;
        m=c+d+1;
        x1=m-a-b;
        x2=m-a-c;
        x3=m-b-d;
    }
  //  printf("%d %d %d %d\n",x1,x2,x3,x4);
    if(a+b+x1==a+c+x2&&a+b+x1==b+d+x3&&a+b+x1==d+c+x4)
    {
        maxi=max(max(x1,x2),max(x3,x4));
        if(maxi<=n)
            printf("%I64d\n",sum*(n-maxi+1)*n);
        else
            printf("0\n");
    }
    else
        printf("0\n");

    return 0;
}

C

C. Money Transfers
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
There are n banks in the city where Vasya lives, they are located in a circle, such that any two banks are neighbouring if their indices differ by no more than 1. Also, bank 1 and bank n are neighbours if n > 1. No bank is a neighbour of itself.

Vasya has an account in each bank. Its balance may be negative, meaning Vasya owes some money to this bank.

There is only one type of operations available: transfer some amount of money from any bank to account in any neighbouring bank. There are no restrictions on the size of the sum being transferred or balance requirements to perform this operation.

Vasya doesn’t like to deal with large numbers, so he asks you to determine the minimum number of operations required to change the balance of each bank account to zero. It’s guaranteed, that this is possible to achieve, that is, the total balance of Vasya in all banks is equal to zero.

Input
The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of banks.

The second line contains n integers ai ( - 109 ≤ ai ≤ 109), the i-th of them is equal to the initial balance of the account in the i-th bank. It’s guaranteed that the sum of all ai is equal to 0.

Output
Print the minimum number of operations required to change balance in each bank to zero.

Examples

input
3
5 0 -5
output
1

input
4
-1 0 1 0
output
2

input
4
1 2 3 -6
output
3

Note
In the first sample, Vasya may transfer 5 from the first bank to the third.

In the second sample, Vasya may first transfer 1 from the third bank to the second, and then 1 from the second to the first.

In the third sample, the following sequence provides the optimal answer:

transfer 1 from the first bank to the second bank;
transfer 3 from the second bank to the third;
transfer 6 from the third bank to the fourth.

题目大意 : 就是一圈银行有的银行缺钱有的银行的钱有富余你要把富余出来的前取走存到缺钱的银行里银行是围城一个圈的
问你身上揣钱的走过的路有多少
两个邻近的银行中有一条道
（略带意淫的翻译）

解题思路：
借鉴:http://blog.csdn.net/yukizzz/article/details/51437984
把这些分成尽可能多的和为0的区间
每个区间走过的路即为区间元素个数-1;
这里用了map 否则数组开不了那么大
（区间和为0的充要条件是区间两端点的前缀和相等即mp[si] == mp[sj]）那么这道题就做出来了
附本题代码

# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
# include <vector>
# include <queue>
# include <set>
# include <map>
# include <string>
# include <math.h>
# include <stdlib.h>
# include <time.h>
using namespace std;

/*********************INPUT*************************/
# define s2l(a,b)   scanf("%d%d",&a,&b)
# define s2_l(a,b)  scanf("%I64d%I64d",&a,&b)
# define s1l(a)     scanf("%d",&a)
/*********************OUTPUT*************************/
# define pr1l(a)    printf("%d",a);
# define pr1_l(a)   printf("%I64d",a);
# define pr1ll(a)   printf("%lld",a);
# define space      printf(" ");
# define line       printf("\n");

/*****************type-num***********************/
# define LL long long int
# define _LL __int64
/****************************************/
# define fr(a,b,c)  for(int a=b;a<c;a++)
# define del(a,b)   memset(b,a,sizeof(b));
# define Rep(a,n)   for(int a=1;a<n;a++)
# define Rop(a,n)   for(int a=1;a<n;a++)

const int mod = 7;
const _LL MOD = 1e9 + mod;
const int MAX = 1e5+50;
const int MIN = 1e2+50;

map<LL, int>m;
int main(void)
{
    int n;
    s1l(n);
    int ans = 0;
    LL tot = 0;
    int qwer;
    for(int i = 0; i < n; i++)
    {
        s1l(qwer);
        tot += qwer;
        m[tot]++;
        ans = max(ans, m[tot]);
    }
    printf("%d", n - ans);
   return 0;
}