2024牛客多校2部分题目

A：Floor Tiles

原题链接：Floor Tiles

首先我们需要明确，对与$ NM$的图，边缘的线头一定有$ 2(NM)$个，故曲线的最少为NM。

再考虑曲线最多的情况，显然，曲线最少时内部没有环，而曲线增多便是要在内部增加环的数量。

若要构造单位圆，显然最优为

$$\begin{matrix} A & B \\\\ B & A \\\\ \end{matrix}$$

但是由于已经确定了一个位置，故可能此排放的顺序有偏差（例如左上角的位置需为B）

故若左上角为A，最多有$N+M+ \lfloor ((N-1)(M-1)+1)/2 \rfloor$

若左上角为B，最多有 $ N+M+ \lfloor ((N-1)(M-1)+1)/2 \rfloor $

构造方法为先确定左上角为A或B，再枚举环的个数，如果足够那就全填A或B，这样保证以后不会出现环。

代码：

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
using namespace std;
const int INF=1e9;
int t;
int n,m,k;
int xx;
int yy;
char c;
int maxn(int m,int n,int flag){
    if(flag==0){
        return ((n-1)*(m-1)+1)/2;
    }
    else return (n-1)*(m-1)/2;
}
void solve(){
    cin>>n>>m>>k;
    cin>>xx>>yy>>c;
    int flag=0;
    if(c=='A'){
        flag=(xx+yy)%2;
    }
    else flag=(xx+yy+1)%2;//确定左上角的选择
    int maxn1=maxn(n,m,flag);//确定最多的数量
    if(k>maxn1+m+n||k<n+m){
        cout<<"No"<<endl;
        return;
    }
    cout<<"Yes"<<endl;
    int index=k-m-n;//确定环的数量
    if(c=='A'){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(index>0){
                    if((xx+yy)%2==(i+j)%2){
                        cout<<'A';
                        if(i!=1&&j!=1)index--;
                    }
                    else cout<<'B';
                }
                else cout<<'A';
            }
            cout<<endl;
        }
    }
    if(c=='B'){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(index>0){
                    if((xx+yy+1)%2==(i+j)%2){
                        cout<<'A';
                        if(i!=1&&j!=1)index--;
                    }
                    else cout<<'B';
                }
                else cout<<'B';
            }
            cout<<endl;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--){
        solve();
    }
}

B：Taking Candies

原题链接：Taking Candies

从最后开始枚举，假设A在倒数第 i 回合有m个硬币，那么B就有x+y-n个硬币。

显然，B应当使A拿到的更少，自己就能拿到更多，因此B的策略可以为尽量使A拿到的少。

$dp[i][j]$为倒数第 i 回合有 j 块钱，所拿到的最多的糖果数。

显然，当$dp[i][j]<dp[i+1][j-m]+val[i]$时A应花费m拿下，但是B此时应阻挠A拿下，即花费更多。

可使用二分查找到A出价的极限find，即当大于出价大于find时，A拿下不如不拿下，这样可以使B花费最多。

代码如下：

//#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
using namespace std;
int n,x,y;
int arr[100005];
ll dp[100005][205];//在倒数第i个回合，有j块钱，所拿到的最多糖果数
bool cmp(int x,int y){
    return x>y;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>x>>y;
    for(int i=1;i<=n;i++)cin>>arr[i];
    sort(arr+1,arr+1+n,cmp);
    //cout<<arr[1];
    int s=x+y;
    for(int i=n;i>=1;i--){
        for(int j=0;j<=s;j++){
            int l=0,r=min(j,s-j);//二分查找的右边界为min(j,s-j)保证find的最大值不会超过
            int find=-1;
            while(l<=r){//二分查找
                int mid=(r+l)>>1;
                if(arr[i]+dp[i+1][j-mid]>dp[i+1][min(s,j+mid)])find=mid,l=mid+1;
                else r=mid-1;
            }
            //cout<<find<<endl;
            if((arr[i]+dp[i+1][j-find]>dp[i+1][j+find+1])&&(j+find+1<=s))dp[i][j]=dp[i+1][j+find+1];
            else dp[i][j]=arr[i]+dp[i+1][j-find];
        }
    }
    cout<<dp[1][x];
}

I：Red Playing Cards

原题链接：Red Playing Cards

$dp[k]$为$[ l[i] , k]$的最大贡献，$f[i]$为$[l[i],r[i]]$的最大贡献。

在前后各设0，即求$f[0]$。

从大到小枚举，事实上我们需要考虑的仅有当小数包围大数的情况，这种情况我们直接将大数单独考虑即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 6005;
int dp[N],f[N],l[N],r[N],arr[N];
//dp[k]为[l[i],k]的最大贡献，f[i]为[l[i],r[i]]的答案
int n;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=2*n;i++){
        cin>>arr[i];
        if(l[arr[i]]==0)l[arr[i]]=i;
        else r[arr[i]]=i;
    }
    l[0]=0;
    r[0]=2*n+1;
    for(int i=n;i>=0;i--){
        int ll=l[i],rr=r[i];
        dp[ll]=i;
        for(int k=ll+1;k<=rr;k++){
            int j=arr[k];
            if(r[j]==k&&l[j]>ll)dp[k]=max(dp[k-1]+i,dp[l[j]-1]+f[j]);
            else dp[k]=dp[k-1]+i;
        }
        f[i]=dp[rr];
    }
    cout<<f[0];
    return 0;
}