NOIP 2016普及組第四題魔法陣magic題解

6368 ワード

タイトルの説明
六十年に一度の魔法戦争が始まり、大魔法使いは近くの魔法場から魔法のエネルギーを汲み取るつもりだ.
大魔法使いにはm個の魔法品があり、番号はそれぞれ1,2,...,mである.各アイテムには魔法値があり、私たちはXiでiと番号の付いたアイテムの魔法値を表します.各魔法値Xiはnを超えない正の整数であり、複数のアイテムの魔法値が同じである可能性がある.
大魔法使いは、4つの番号がa,b,c,dの魔法物品がxa今、大魔法使いは、魔法アイテムごとに、ある魔法陣のAアイテムとして現れる回数、Bアイテムとしての回数、Cアイテムとしての回数、Dアイテムとしての回数を知りたいと思っています.
にゅうしゅつりょくけいしき
入力フォーマット:入力ファイルの最初の行には、2つのスペースで区切られた正の整数nとmが含まれます.
次にm行、行ごとに正の整数を1つ、i+1行目の正の整数はXi、すなわちiと番号の付いた物品の魔法値を表す.
各Xiがそれぞれ正当範囲内で等確率でランダムに生成されることを保証する.
出力フォーマット:m行を出力し、行ごとに4つの整数を出力します.i行目の4つの整数は、iと番号付けされたものがA,B,C,Dとしてそれぞれ出現した回数を順次示す.
標準出力の各数が10^9を超えないことを保証します.
各行の隣接する2つの数の間には、ちょうど1つのスペースで区切られています.
入出力サンプル
入力サンプル#1:30 8 1 24 7 28 5 29 26出力サンプル#1:4 0 0 0 0 0 0 1 0 0 0 2 0 0 1 1 3 0 0 0 0 0 2 0 0 0 2 0 0 0 0 0 1 0入力サンプル#2:15 15 1 2 3 4 5 6 7 9 10 11 13 15出力サンプル#2:5 0 0 0 0 4 0 0 0 0 3 5 0 0 0 0 0 1 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 3 20 0 4 3 0 0 5 4 0 0 0 5
問題解
一つの普及グループのテーマにとって、この問題の難易度はやはり少し大きいので、まず問題を理解しなければなりません.テーマの中には大文字Xと小文字xがありますが、実は同じで、混同する人もいるかもしれません.
条件1をリストします.xaまず少し暴力的な方法を考えて、最初の条件に対して、直接すべてのものを1つのバケツに保存して、バケツの大きさはN(15000)を超えないで、毎回いくつかの魔法の値を列挙するのではなくて、列挙魔法の値の2番目の条件の意味は後の2つの数の差が後の2つの数の差の2倍に等しいことを意味して、条件の3に1つの小さい最適化を加えることができます.このように解答を集計する際にも条件3を満たしているか否かを判断することなく、設定後の2つの数の差をj xb−xa<(xc−xb)/3 2∗j<(xc−xb)/3 6∗jxb+6∗jとすると、xcを列挙する際に6∗j+xb+1から列挙すればよいので、列挙後の2つの数の差を考慮することができ、前の2つの数の差を算出し、xaを列挙してxbを算出することができるxcを列挙してxdを算出し、答えを統計するにはどうすればいいですか?詳細には、t[x]がxを表す値が何個あるか、ans[x][1 4]がxを表す数が1番目の道の4番目の数として何回出現したかを表すと、ans[xa][1]=t[xb]=t[xb]∗t[xc]∗t[xd]ans[xb][2]=t[xa]∗t[xc]∗t[xd]ans[xd]ans[xd]ans[xc][3]=t[xa]∗t[xb]ans[xd]ans[xd]ans[xd][xd]ans[xd][xd]ans[xd]ans[xd 4]=t[xb]∗t[xc]∗t[xd]出力時に入力毎の魔法値xに対してans[x][1]を出力し、ans[x][2]、ans[x][3]、ans[x][4]予想得点:60~85
同様に先列挙後の2つの数の差jを最適化することを考慮すると、xa=0の場合、他の3つの数の最小値は、xb=2後の2つの数に直接前の2つの数を加えたすべての可能な場合の和
どのように求めますか?
最小のxa(値1)から現在のxaまでをsum 1で記録することは、対応するxbのΣt[xa]∗t[xb]すなわちsum 1=Σt[xa]∗t[xb]と同様である.xdが現在のxaから可能な最小値(xd=xa+9*j+1)から最大xd(xd=n)までの最大xdと対応するxcのΣt[xc]t[xd]すなわちsum 2=Σt[xc]t[xd]ではans[xa][1]=t[xb]sum 2 ans[xb][2]=t[xa]=t[xa]sum 2 ans[xb][2]=t[xa]sum 2 ans[xc][3]=t[xd]sum 1 ans[xd][xd][4]=t[xc]∗sum 1が理解できなければ私のコードで見てもいいです
コード#コード#

#include
#include
#include
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 41000
using namespace std;
int n,m,e[N],t[N],ans[N][4];
void read(int &x)
{
    char c;c=getchar();int n=0;
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar()) n=n*10+c-48;
    x=n;
}
int main()
{
    freopen("magic.in","r",stdin);freopen("magic.out","w",stdout);
    read(n);read(m);
    fo(i,1,m) read(e[i]),t[e[i]]++;
    int b,c,d;
    fo(j,1,2000)
    {
        b=2*j;c=8*j+1;d=c+j;
        int sum=0,sum2=0;
        fo(i,d+1,n) sum+=t[i]*t[i-j];
        fo(a,1,n)
        {
            b++;c++;d++;
            sum2+=t[a]*t[b];
            if(d>n) break;
            if(t[a]*t[b]>0)
            {
                ans[a][0]+=t[b]*sum;
                ans[b][1]+=t[a]*sum;
            }
            if(t[c]*t[d]>0)
            {
                ans[c][2]+=t[d]*sum2;
                ans[d][3]+=t[c]*sum2;
            }
            sum-=t[d]*t[c];
        }
    }
    fo(i,1,m) printf("%d %d %d %d
",ans[e[i]][0],ans[e[i]][1],ans[e[i]][2],ans[e[i]][3]);
}

JSONをModelから一部だけ出力する方法

Go言語開発におけるtagの使用