2017-2018 ACM-ICPC,Asia Daejeon Regional Contest問題解(GYM 101667)

12問の問題は、やはり通過人数の高さから低さまでやります.
ハングルhttp://blog.myungwoo.kr/121(コードあり)この试合のランキング、170分でチームakがあります....
D Happy Number
水問題は,まず1回操作すればよい.
C Game Map
無方向連通図上の点シーケンスを探す、シーケンス中の点が順次エッジ接続され、度数が増加することが要求される.
小数点から大数点までのエッジを残すだけで、この図はDAGとなり、テーマはDAG上の最長ルートに変わり、dpは解くことができる.直接度数でトポロジーシーケンスを排出し、度数の小さい隣接点の答えに順次アクセスし、最後に最大の答えを取ればよい.
WA点:隣接点にアクセスするときの判定度数が小さい.WA点:各点の答えは1に初期化されていない.

const int M = 100016;
vector<int> save[M];
vector<int> id;
int ans[M];
    int n=read(),m=read();
    for(int i=0;iint a=read(),b=read();
        save[a].push_back(b),save[b].push_back(a);
    }
    for(int i=0;iconst int & a,const int &b){
        return save[a].size()int ret=0;
    for(int i:id)
    {
        ans[i]=1;
        for(int j:save[i])
            if(save[j].size()1);
        ret=max(ret,ans[i]);
    }
    printf("%d
",ret );

F Philosopher’s Walk分治
哲♂学の道はn(2->32768,2のべき乗)を与えて、m(n^2以下)は、1つの長幅がnの哲学図の中でm番目の位置の座標を聞く.長幅が2の哲学図F 2:左下、左上、右上、右下の長幅が4の哲学図F 4:左下F 2右旋、左上F 2、右上F 2左下F 2左旋長項が8の哲学図:順次類推する.
F(x,y)を長幅xとする哲学図におけるy番目の位置の座標境界F(1,1)=(1,1)F(x,y):y<=x^2/4のとき、F(x,y)=左旋(F(x/2,y)=y<=x^2/2のとき、F(x,y)=F(x/2,y)=F(x/2,y-x^2/4)+(0,x/2)y<=3*x^2/4のとき、F(x,y)=F(x/2,y-x^2/2/2)+(x/2,x/2,x/2)そうでなければ、F(x,y)=右回り(F(x/2,y-3*x^2/4)+(x/2,0)
1つの明らかな问题は、どのように座標を表します.32769を底にして演算することができます(座標の范囲は1から32768です).符号化と復号は多くなくて、プラスは直接プラスします.左右の回転:x=n+1-y,y=n+1-x右の回転:x=y,y=x
ローカルエラーポイント1:境界帰還(1,1)時に符号化することなく直接帰還1ローカルエラーポイント2:左右の回転の概念を誤って理解し、直接回転ではなく経路座標で対応すべきである.

const int B = 32769;
int B1(int x,int y)
{
    return x*B+y;
}
pair<int,int> B2(int p)
{
    return make_pair(p/B,p%B);
}
int zig(int p,int n)
{
    pair<int,int> pii=B2(p);
    int x=pii.second,y=pii.first;
    return B1(x,y);
}
int zag(int p,int n)
{
    pair<int,int> pii=B2(p);
    int x=n+1-pii.second,y=n+1-pii.first;
    return B1(x,y);
}
int cal(int n,int m)
{
    if(n==1) return B1(1,1);
    int x=n*n/4;
    if(m<=x) return zig(cal(n/2,m),n/2);
    if(m<=x*2) return cal(n/2,m-x)+B1(0,n/2);
    if(m<=x*3) return cal(n/2,m-x*2)+B1(n/2,n/2);
    return zag(cal(n/2,m-x*3),n/2)+B1(n/2,0);
}
int main(void)
{
    int n=read(),m=read();
    pair<int,int> pii = B2(cal(n,m));
    printf("%d %d
",pii.first,pii.second );
    return 0;
}

H-Rock Paper Scissorsボリューム
石ハサミ布の3つの状況は完全に独立しており、各位置の各状況の答えを求めることができ、それから最大値を求めることができる.
答えの表示方法をリストし、短いシーケンスに逆を取り、fftでボリュームを求める.
詳しくは学習ノートの[ボリューム]と[FFT]を参照し、この問題の詳細な解釈とコードがある.