HDU 4038 Stone
5698 ワード
ああ、試合中いろいろ考えたあげく、この問題をAさんにあげてしまった.
この問題の題意は1つのシーケンスの数に、2つの操作があって、1つはシーケンスの中のある数の値を1に加えるか、シーケンスの中で1つの数を加えて1にして、それから操作数を与えて、最後にこれらの数の積が最大であることを要求して、この積を求めます.
この問題をする上で考慮しなければならない細部は多く、まず負数の個数を求めなければならない.奇数であれば、最大の負数をできるだけ0に加えるのは、偶数に変換することに相当する.そして、負数は管理しなくてもいい.このとき、シーケンスに0があれば、彼らが乗算するのは0であることは明らかだ.だから、できるだけすべての0を1にし、その後、操作数がまだ残っている場合は、できるだけすべての1を2にしなければならない.1はシーケンスの中で何の役にも立たないからだ.2に増やすと2倍になる.1つの操作数でこの効果を達成するのが一番お得だ.その後、操作数が残っている場合は、すべての2を3にする.2つの操作はシーケンスの中に1つの2を追加することができ、2つの2を2つの3に変更することができるからだ.このように分析すると、明らかに2つの2を2つの3に変えるほうがお得で、1つの操作の時も明らかに2を3に変えるほうがお得で、その後、操作数がまだ残っていれば、操作数が1の時、明らかに最小の正数に加えたほうがお得ですが、操作数が1より大きい時、シーケンスの中に3がたくさんあると仮定することができます.3+1で得られる増幅は4/3であり、シーケンスに1つの数を追加することと、これらの3を1つ追加することによる増幅を比較することができ、2,3,4,5,6のときにシーケンスに1つの数を追加することによる増幅は3に1を追加することよりも大きく、すべての数は2と3で加算され、例えば6=3+3で構成されることが明らかになった.6を3と3に分解することによる増幅は自分よりも頼りになるので、できるだけ操作数を2または3に分割しますが、誰が優先しますか?私達は先に送ることができて、もし3*a=2*bならば、3^aはきっと2^bより大きくて、だから、最も優先するのは3であるべきで、だから、私達はできるだけシーケンスの中で3をプラスして、それから更に2をプラスして、3*a+2*b=操作数をさせます.コードは次のとおりです.
この問題の題意は1つのシーケンスの数に、2つの操作があって、1つはシーケンスの中のある数の値を1に加えるか、シーケンスの中で1つの数を加えて1にして、それから操作数を与えて、最後にこれらの数の積が最大であることを要求して、この積を求めます.
この問題をする上で考慮しなければならない細部は多く、まず負数の個数を求めなければならない.奇数であれば、最大の負数をできるだけ0に加えるのは、偶数に変換することに相当する.そして、負数は管理しなくてもいい.このとき、シーケンスに0があれば、彼らが乗算するのは0であることは明らかだ.だから、できるだけすべての0を1にし、その後、操作数がまだ残っている場合は、できるだけすべての1を2にしなければならない.1はシーケンスの中で何の役にも立たないからだ.2に増やすと2倍になる.1つの操作数でこの効果を達成するのが一番お得だ.その後、操作数が残っている場合は、すべての2を3にする.2つの操作はシーケンスの中に1つの2を追加することができ、2つの2を2つの3に変更することができるからだ.このように分析すると、明らかに2つの2を2つの3に変えるほうがお得で、1つの操作の時も明らかに2を3に変えるほうがお得で、その後、操作数がまだ残っていれば、操作数が1の時、明らかに最小の正数に加えたほうがお得ですが、操作数が1より大きい時、シーケンスの中に3がたくさんあると仮定することができます.3+1で得られる増幅は4/3であり、シーケンスに1つの数を追加することと、これらの3を1つ追加することによる増幅を比較することができ、2,3,4,5,6のときにシーケンスに1つの数を追加することによる増幅は3に1を追加することよりも大きく、すべての数は2と3で加算され、例えば6=3+3で構成されることが明らかになった.6を3と3に分解することによる増幅は自分よりも頼りになるので、できるだけ操作数を2または3に分割しますが、誰が優先しますか?私達は先に送ることができて、もし3*a=2*bならば、3^aはきっと2^bより大きくて、だから、最も優先するのは3であるべきで、だから、私達はできるだけシーケンスの中で3をプラスして、それから更に2をプラスして、3*a+2*b=操作数をさせます.コードは次のとおりです.
/*
ID: sdj22251
PROG: lamps
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAX 200000000
#define LOCAL
using namespace std;
__int64 a[100005];
__int64 f(__int64 a,__int64 n,__int64 m)
{
__int64 x;
if(n == 0)
return 1 % m;
else if(n % 2 == 0)
{
x=f(a, n / 2, m);
return x % m * x % m;
}
else
{
x=f(a, (n - 1) / 2, m);
return x % m * x % m * a % m;
}
}
int main()
{
int n, m, t, cas, i, Negative, loc, Negativemax, Positiveminus, loc2;
__int64 two ,three;
__int64 mod = (__int64)1000000007;
while(scanf("%d", &t) != EOF)
{
cas = 0;
while(t--)
{
loc = 0;
Negative = 0;
two = 0;
three = 0;
Positiveminus = MAX;
Negativemax = -MAX;
scanf("%d%d", &n, &m);
for(i = 0; i < n; i++)
{
scanf("%I64d", &a[i]);
if(a[i] < 0)
{
Negative++;
if(a[i] > Negativemax)
{
Negativemax = a[i];
loc = i;
}
}
}
if(Negative % 2)
{
if(a[loc] + m >= 0)
{
m -= (0 - a[loc]);
a[loc] = 0;
}
else
{
a[loc] += m;
m = 0;
}
}
if(m > 0)
{
for(i = 0; i < n; i++)
{
if(a[i] == 0)
{
if(m > 0)
{
a[i]++;
m--;
}
else break;
}
}
}
if(m > 0)
{
for(i = 0; i < n; i++)
{
if(a[i] == 1)
{
if(m > 0)
{
a[i]++;
m--;
}
else break;
}
}
}
if(m > 0)
{
for(i = 0; i < n; i++)
{
if(a[i] == 2)
{
if(m > 0)
{
a[i]++;
m--;
}
else break;
}
}
}
if(m > 0)
{
loc2 = 0;
for(i = 0; i < n; i++)
{
if(a[i] < Positiveminus)
{
Positiveminus = a[i];
loc2 = i;
}
}
if(m % 3 == 0)
{
three += m / 3;
}
else if(m % 3 == 1)
{
if(m == 1)
{
a[loc2]++;
m = 0;
}
else
{
three += m / 3 - 1;
two += 2;
}
}
else if(m % 3 == 2)
{
three += m / 3;
two++;
}
}
__int64 tmp = 1;
for(i = 0; i < n; i++)
{
tmp = tmp * a[i] % mod;
}
__int64 threenum = f((__int64)3, three, mod);
__int64 twonum = f((__int64)2, two, mod);
tmp = tmp * threenum % mod * twonum % mod;
printf("Case %d: %I64d
", ++cas, tmp % mod);
}
}
return 0;
}