edu cf#136 Div.2(A~C)

edu Cf #136 Div.2

A. Immobile Knight

• 题意

  • n*m的棋盘，马走日，输出马不能走的坐标，没有这样的坐标则输出任意坐标

• 题解

  • 方法一：暴力；数据范围很小，直接每一个坐标判断是不是符合要求的坐标
  • 方法二：贪心；
    • 贪心1:只有棋盘为1条状态的，一定全是孤立点，其他的输出2 2即可，因为n=m<=3时孤立点为(2,2)，而其他棋盘(2,2)一定为非孤立点
    • 贪心2:棋盘中心最有可能为孤立点，所以直接输出棋盘中心，如果有孤立点，棋盘中心一定符合，如果没有孤立点，棋盘中心也符合输出要求

• 代码

方法一：暴力

#include 

using namespace std;
int n,m;

bool check(int x,int y) {//islocate
    if((x-2<1 || y-1<1) && (x-2<1 || y+1>m) && (x-1<1 || y-2<1) && (x-1<1 || y+2>m)
    && (x+1>n || y-2<1) && (x+1>n || y+2>m) && (x+2>n || y-1<1) && (x+2>n || y+1>m)) 
    return 1;
    else return 0;
}

void solve() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if(check(i,j)) {
                cout<<i<<' '<<j<<'\n';
                return ;
            }
        }
    }
    cout<<n<<' '<<m<<'\n';
}

int main() {
    int t;
    cin>>t;
    while(t--) solve();
    
    return 0;
}

方法二：贪心

//中心
void solve()
{
    int n,m;
    cin >> n >> m;
    cout << (n+1)/2 << " " << (m+1)/2 << endl;
}


//特判2 2
void solve()
{
    int n,m;
    cin >> n >> m;
    if (n==1 || m==1){
        cout << "1 1" << endl;
        return;
    }
    cout << 2 << " " << 2 << endl;
}

B. Meeting on the Line

• 题意

  • 给定一个长度为n的绝对值差分序列d，输出唯一的前缀和序列a(a[i]>=0)，不唯一输出-1
  • d[i]=|a[i]-a[i-1]|

• 题解

  • 只需要从前往后一次计算两种可能的前缀和a[i-1]-d[i],a[i-1]+d[i]，看其值是否非负且唯一，不符合直接-1，符合则确定了a[i]

• 代码

#include 

using namespace std;
const int N=110;
int n,a[N],d[N];

void solve() {
    cin>>n;
    for(int i=1;i<=n;i++) cin>>d[i];
    
    for(int i=1;i<=n;i++) {
        int t1=a[i-1]+d[i];//a[i]可能值
        int t2=a[i-1]-d[i];//a[i]可能值
        if(t1>=0 && t2>=0 && t1!=t2) {//判断是否有唯一合法的a[i]
            cout<<-1<<'\n';
            return ;
        }
        a[i]=t1;
    }
    for(int i=1;i<=n;i++) cout<<a[i]<<' ';
    cout<<'\n';
}

int main() {
    int t;
    cin>>t;
    while(t--) solve();
    
    return 0;
}

C. Minimum Notation

• 题意

  • n张牌(n为偶数)，牌的数字为1～n的排列，A和B玩家各有n/2张牌
  • 游戏规则，A先手，每轮先手次序交换；先手如果出了一张牌比对手的所有牌都大，那么直接赢得比赛；如果出的不是最大的，对手需要出一张比先手大的牌，此轮平局；下一轮先手顺序交换继续直到所有牌打完或者有玩家赢了
  • 输出A一定赢，B一定赢，一定平局的牌的分配情况

• 题解

  • 易得，无论如何玩家一定会先出手中最大的牌。因为如果先手有全场最大的牌直接出就赢了，后手有最大的牌，那么先手一定用次大的牌逼出后手用掉最大牌，而后手也必须这么做，否则输掉比赛

  • 平局的情况一定是(只有一种)

    A: n-1 n-2 n-5 n-6 ...
    B: n   n-3 n-4 n-7 ...
    

  • C(n,n/2)为总的情况数，1中平局，那么只要算出A必胜的情况数，直接相减即可得到B必胜的情况数。

  • 如何计算A必胜呢？假设f[n]为总牌数为n的情况下A必胜的数量，相对于平局来看，如果A直接拥有牌n，那么直接胜利，胜利情况数为C(n-1,n/2)；如果n在B手上，那么要赢，只能让这一轮先平局，所以A手上有n-1，对于第二轮先手交换，即B先手，那么A赢即为牌数只有n-2时，B赢得数量(因为先后手交换了)，所以A胜利情况为B赢得情况=C(n-2,(n-2)/2)-C(n-2-1,(n-2)/2)-1

  • 往后轮次依次递推即可

• 代码

#include 

using namespace std;
const int N=65,mod=998244353;
int c[N][N];
int n;

void init() {//预处理组合数
    for(int i=0;i<N;i++)
        for(int j=0;j<=i;j++)
            if(!j)c[i][j]=1;
            else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}

void solve() {
    cin>>n;
    long long a=1,b=0;//初始化i=2时，即牌数最小时
    for(int i=4;i<=n;i+=2) {
        a=(c[i-1][i/2-1]+b)%mod;//第一轮必胜+第一轮平局第二轮上一种牌数必输
        b=(c[i][i/2]-a-1+mod)%mod;//必输情况更新
    }
    cout<<a<<' '<<(c[n][n/2]-a+mod-1)%mod<<' '<<1<<'\n';//注意负数取摸
}

int main() {
    init();
    int t;
    cin>>t;
    while(t--) solve();
    
    return 0;
}