题解：P14477 图寻中国

· · 题解

P14477图寻中国 题解

本水题可以推公式

题意重述

给出一连串对局的总局数 n，再给出对局中最长连胜 a 和最长连败 b，求符合以上条件的最大胜利数。

思路分析

虽然题目要求胜利尽可能多，但为了不超过最大连胜局数，必须要在胜利 a 局后立刻输一局来分割连胜。就有两种情况：

  1. 如果最长连败为 0（也就是 b=0），则分隔直接使用 1 局失败即可，共重复 C\gets n\div (a+1) 个胜 a 局，败 1 局的周期。若 n\mod (a+1) \ne 0，即还有剩余局数没有比完，则使其全胜利即可，因为可以证明 n\mod (a+1) \le a。
  2. 如果最长连败非 0（也就是 b>0），则可以先将 a 局胜利和 b 局失败比掉，新增一个变量 C_2 \gets n-a-b（即剩余的局数），剩下的按照 b=0 的情况处理即可，最后别忘了加上一开始连胜的 a。

根据上面的分析，可以得出两种情况所对应的公式：

第一种情况：(C\times a)+(n\mod (a+1)) 即 C 组乘以每组连胜数加剩余的连胜局数。

第二种情况：(C_2\div(a+1))\times a+(C_2\mod(a+1))+a 即组数乘每组连胜数加上剩余胜利数加上一开始连胜的a。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n,a,b;
    cin>>n>>a>>b;
    if(b==0){//判断是否b=0，若是则按第一种情况处理
        int c=n/(a+1);
        int x=c*a;
        cout<<x+n%(a+1);//此处为了方便阅读将第一种情况的公式拆成三段，意义和结果不变
    }
    else{ //否则按第二种情况处理
        int c=n-a-b;
        int x=c/(a+1);
        cout<<x*a+a+c%(a+1);//此处为了方便阅读将第二种情况的公式拆成三段，意义和结果不变
    }
    return 0;//The End and AC!
}