YL 模拟赛总结 10

Problem

T1

二分板子。

对于 \(c_i\) 降序排序，然后二分 \(h\) 指数，在 check 中贪心地使用综述增加引用次数即可。

T2

通过观察可以发现，在一篇论文的贡献列表中，若某一位置出现了比它前面的名字的字典序更小的情况，则说明从这个位置开始，后面的人的资历一定 \(\ge\) 前面的人。

根据这一性质，我们对于每一条贡献列表，都去寻找这样的位置，然后更新答案数组即可。

#include<bits/stdc++.h>
using namespace std;

int k,n;
string a[131];
unordered_map<string,int> m;
char ans[131][131];

int main(){
    cin>>k>>n;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s,m[s]=i;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) ans[i][j]='B';
            else ans[i][j]='?';
        }
    }
    while(k--){
        for(int i=1,p=1;i<=n;i++){
            cin>>a[i];
            if(a[i]<a[i-1]) p=i;
            for(int j=1;j<p;j++)
                ans[m[a[j]]][m[a[i]]]='0',ans[m[a[i]]][m[a[j]]]='1';
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) cout<<ans[i][j];
        cout<<'\n';
    }
    return 0;
}

T3

我们反向思考，考虑每块草地可以让几对牛交友。

显然，一块草地相邻的位置若拥有 \(\ge 2\) 头牛，则可以让一对牛交友。

但是，有可能这块草地与其他草地重复让某一对牛交友。

这种情况只会出现于两块草地呈斜对角的状态时，特判一下即可。

#include<bits/stdc++.h>
using namespace std;

int n,m,ans;
char mp[1031][1031];
int cnt[1031][1031];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

int calc(int x,int y){
    cnt[x][y]=0;
    for(int i=0;i<4;i++)
        cnt[x][y]+=(mp[x+dx[i]][y+dy[i]]=='C');
    return cnt[x][y]>=2;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>mp[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(mp[i][j]=='G'){
                ans+=calc(i,j);
                if(cnt[i][j]==2&&mp[i-1][j]=='C'){
                    ans-=(mp[i][j-1]=='C'&&cnt[i-1][j-1]==2);
                    ans-=(mp[i][j+1]=='C'&&cnt[i-1][j+1]==2);
                }
            }
        }
    cout<<ans;
    return 0;
}

T4

又是二分板子（

首先，朴素的想法是二分 \(X\) 的值，然后模拟 \(K\) 天还奶的过程进行校验。

但这样做时间复杂度是 \(O(n)\)，无法通过。

我们发现，题目中的 \(\frac{N-G}{X}\) 会随着时间的推移慢慢变小。

那么当它某一时刻 \(\le m\) 时，那么它接下来将一直会变小，所以 \(\frac{N-G}{X}\) 的值会恒定为 \(m\)，此时就没必要继续模拟下去了，直接使用数学公式校验即可。

并且，我们也无需一天一天地模拟。具体见 here。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,k,m;

bool check(int x){
    int s=0;
    for(int d=0;d<k;){
        int y=(n-s)/x;
        if(y<=m) return s+(k-d)*m>=n;
        int tme=min(k-d,(n-s)%x/y+1);
        s+=tme*y,d+=tme;
    }
    return s>=n;
}

signed main(){
    //freopen("loan.in","r",stdin);
    //freopen("loan.out","w",stdout);
    cin>>n>>k>>m;
    int l=0,r=n+1;
    while(l+1<r){
        int mid=(l+r)>>1;
        if(check(mid)) l=mid;
        else r=mid;
    }
    cout<<l;
    return 0;
}