牛客多校第三場

• 2020 年 7 月 19 日
• 筆記

A.Clam and Fish

思路：貪心，沒啥好說

int n,m,k;
string s;
void solve(){
    cin>>n;
    cin>>s;
    int f=0,c=0;
    for (int i=0;i<n;i++){
        if (s[i]=='0'){
            if (c)c--,f++;
        }
        else if (s[i]=='1')c++;
        else f++;
    }
    f+=c/2;
    cout<<f<<endl;
}
int main(){
    int T=1;
    cin>>T;
    while (T--){
        solve();
    }
    return 0;
}

B.Classical String Problem

思路：記錄頭指針

int n,m,k,p;
string s;
void solve(){
    char c;
    int x;
    getchar();
    scanf("%c %d",&c,&x);
    if (c=='M'){
        p=(p+x+k)%k;
    }
    else{
        printf("%c\n",s[(p+x-1)%k]);
    }
}
int main(){
    int T=1;
    cin>>s;
    k=s.size();
    p=0;
    cin>>T;
    while (T--){
    	solve();
    }
    return 0;
}

C.Operation Love

題意：
將這隻任意翻轉旋轉過的手的20個坐標順時針或逆時針給你，問是左手還是右手
思路：先用叉積判斷出給出順逆時針，再通過邊長的關係得出左手還是右手

#define sqr(a) (a)*(a)
const double eps=0.1;
string s;
double x[21],y[21];
void solve(){
    for (int i=0;i<20;i++)scanf("%lf%lf",&x[i],&y[i]);
    double ans=0;
    for (int i=0;i<20;i++)ans+=x[i]*y[(i+1)%20]-x[(i+1)%20]*y[i];//鞋帶公式 
    ans/=2;//面積,<0順時針,>0逆時針
    int a,b;
    for (int i=0;i<20;i++){
        double t=sqrt(sqr(x[i]-x[(i+1)%20])+sqr(y[i]-y[(i+1)%20])); 
        if (t<=9+eps&&t>=9-eps)a=i;
        if (t<=8+eps&&t>=8-eps)b=i;
    }
    if ((a<b&&!(a==0&&b==19))||(a==19&&b==0)){
        if (ans>0) puts("right");
        else puts("left");
    }
    else{
        if (ans>0) puts("left");
        else puts("right");
    }
}
int main(){
    int T=1;
    cin>>T;
    while (T--){
    	solve();
    }
    return 0;
}

D.Points Construction Problem

題意：給定n,m,n代表n個黑點,m代表黑點和周圍空白區域構成的黑白點對個數，問滿足n和m圖形能否構成
思路：分析得,一個凸的黑點構成的圖形形成的點對為其外長方形的周長，也易知,m為奇數，該圖形無法構成。
不妨令所有點外圍為同一個長方形
最少點構成最大圖形

最多點構成圖形為長方形整體
中間部分的點可以如圖補充，左邊同右邊

可以枚舉1-m/2,長寬為a,b,當點在max(a,b)<=n<=a*b時滿足

int n,m,k;
void solve(){
    cin>>n>>m;
    if (m&1){cout<<"No"<<endl;return;}
    bool f=0;
    int a,b;
    for (int i=1;i<=m/2/2;i++){//枚舉長寬的寬 
        a=i,b=m/2-i;
        if (n>=b&&n<=a*b){f=1;break;}
    }
    if (f==0){cout<<"No"<<endl;return;}
    cout<<"Yes"<<endl;
    n-=b;
    for (int i=1;i<=a;i++)printf("%d %d\n",i,i);
    for (int i=a+1;i<=b;i++)printf("%d %d\n",a,i);
    for (int i=a-1;i>=1;i--){
        if (n==0)break;
        for (int j=i+1;j<=b;j++){
            printf("%d %d\n",i,j);
            n--;
            if (n==0)break;
        }
    }
    for (int i=2;i<=a;i++){
        if (n==0)break;
        for (int j=i-1;j>=1;j--){
            printf("%d %d\n",i,j);
            n--;
            if (n==0)break;
        }
    }
}
int main(){
    int T=1;
    cin>>T;
    while (T--){
        solve();
    }
    return 0;
}

E.Two Matchings

題意：原序列為a,長度為n,n為偶數,尋找兩個置換序列p,q,滿足a[p[i]]!=i,a[p[p[i]]]=i,問的最小值
思路：只要滿足4個點及以上一組就必定能形成2個置換序列,值為組中的(max-min)*2,先排序,再利用動態規劃即可求出最小值

int n,m,k;
int a[N],dp[N];
void solve(){
    cin>>n;
    for (int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    for (int i=1;i<=n;i++)dp[i]=inf;
    dp[0]=0;
    for (int i=4;i<=n;i++){
        dp[i]=min(dp[i],dp[i-4]+a[i]-a[i-3]);
        dp[i]=min(dp[i],dp[i-2]+a[i]-a[i-2]);
    }
    cout<<dp[n]*2<<endl;
}
int main(){
    int T=1;
    cin>>T;
    while (T--){
        solve();
    }
    return 0;
}

F.Fraction Construction Problem

G.Operating on a Graph

H.Sort the Strings Revision

I.Sorting the Array

J.Operating on the Tree

K.Eleven Game

L.Problem L is the Only Lovely Problem

超級簽到題