CZYZ 暑期集训 NOIP 训练赛

A.巧克力(chocolate)

• 小学弱智游戏题
• n=m=1 时 ;显然 Jane 赢。
  若 n!=1 || m!=1 时 ; 可证 January 赢。
  –附证明：
  Chomp游戏
  –附代码：

#include
using namespace std;
int t,n,m;
int main() {
    freopen("chocolate.in","r",stdin);
    freopen("chocolate.out","w",stdout);
    cin>>t;
    while(t--) {
        cin>>n>>m;
        if(n==1 && m==1)
            cout<<"Jane"<<endl;
        else
            cout<<"January"<<endl;
    }
    return 0;
}

B.喝水(water)

• 裴蜀定理 ，不会 。

C.魔法(magic)

概率 DP

• 下文中q为Q%,p为P%。
• 设 e(x) 是使用 x 点魔力后可以释放的魔法数量 ，则转移方程有：
  e(x)=max(1+p+e(x-B),1+q\times e(x-B+1) + (1-q) \times e(x – B)) ;
• 取最大即可 ，注意 ：B=1 时要进行特判 ，最后得到的式子为：
  e(x) = max(1+p+e(x-B), 1 \div (1 – q) + e(x)) ;
• 附代码 :

#include
using namespace std;
int t;
int a,b,p,q;
double p1;
double q1;
double e[200001];
int main() {
    freopen("magic.in","r",stdin);
    freopen("magic.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--) {
        cin>>a>>b>>p>>q;
        p1=p/100.0;
        q1=q/100.0;
        for(int i=0; i<=a; i++)
            e[i]=0;
        for(int i=b; i<=a; i++) {
            e[i]=1+p1+e[i-b];
            if(b==1)
                e[i]=max(e[i],1/(1-q1)+e[i-1]);
            else
                e[i]=max(e[i],1+q1*e[i-b+1]+(1-q1)*e[i-b]);
        }
        printf("%.10f\n",e[a]);
    }
    return 0;
}

D.分裂(split)

• 字符串哈希 ，不会 。

• 困了……