190504--2019湘潭大學(xué)程序設(shè)計(jì)大賽重現(xiàn)賽

發(fā)現(xiàn)自己真的太菜了，簽到題全部wa，所以現(xiàn)根據(jù)網(wǎng)上題解和自己的理解做一個(gè)題解自己看看
再此順便感謝網(wǎng)上貼出題解供我理解的大佬們：
阿茶家的庸醫(yī)(注釋和方法都非常清晰?。。?
yjun
守林鳥
ccsu_YangJ

目錄

A.Who's matter?(簽到題）
B.Number（簽到題）
C.Math Problem(簽到題)
D.stone(簽到題）
F.Black & White

鏈接：https://ac.nowcoder.com/acm/contest/893/A
來(lái)源：?？途W(wǎng)

A.Who's matter?(簽到題）

ICPC比賽中，誰(shuí)通過的題數(shù)多，誰(shuí)排名靠前；在通過題數(shù)相同的情況下，誰(shuí)的罰時(shí)少，誰(shuí)排名靠前；如果前兩者都相同，就看最后正確提交的時(shí)間，誰(shuí)早最排名靠前。 現(xiàn)在給你兩個(gè)隊(duì)伍的正確通過的題數(shù)、罰時(shí)和最后正確提交時(shí)間，請(qǐng)判斷一下，誰(shuí)的排名更靠前？

輸入描述:

只有一組測(cè)試樣例，兩行，每行三個(gè)整數(shù)n(0≤n≤13),p(1≤p≤1000),s(1≤s≤300)，依次表示兩個(gè)隊(duì)的正確通過的題數(shù)、罰時(shí)和最后正確提交時(shí)間。

輸出描述:

輸出一行（末尾要換行符）。
如果是第1個(gè)隊(duì)排名靠前，輸出1；如果是2隊(duì)，輸出2；如果無(wú)法分辨，輸出"God"。

1 10 10
1 22 2

輸出

<pre>1</pre>

示例2

輸入

<pre>1 10 10
2 42 20</pre>

輸出

<pre>2</pre>

示例3

輸入

1 10 10
1 10 10

輸出

God

//注意不要超時(shí)
#include<stdio.h>
#include<iostream>
using namespace std;
int main(){
    int a,b,suma=0,sumb=0,ta,tb,sa,sb;
    scanf("%d%d%d",&a,&ta,&sa);
    scanf("%d%d%d",&b,&tb,&sb);
    if(a>b)suma++;
    else if(b>a)sumb++;
    else {
        if(ta<tb)suma++;
        else if(ta>tb)sumb++;
        else {
           if(sa>sb)sumb++;
           else if(sa<sb)suma++;

        }
        
    }
    if(suma>sumb)cout<<"1"<<endl;
    else if(suma<sumb)cout<<"2"<<endl;
    else cout<<"God"<<endl;
    return 0;
}

鏈接：https://ac.nowcoder.com/acm/contest/893/B
來(lái)源：牛客網(wǎng)

B.Number（簽到題）

時(shí)間限制：C/C++ 1秒，其他語(yǔ)言2秒
空間限制：C/C++ 32768K，其他語(yǔ)言65536K
64bit IO Format: %lld

題目描述

Bonnie得到了一個(gè)數(shù)字n。
現(xiàn)在她想對(duì)這個(gè)數(shù)字不斷的做一種操作：

  • 如果n的最后一位數(shù)碼是0，那么她就把n除以10；
  • 否則她把這個(gè)數(shù)加上1；
  • 直到n變?yōu)橐粋€(gè)不大于1的數(shù)。

給定n，請(qǐng)問Bonnie需要做多少次操作？

輸入描述:

<pre>第一行一個(gè)數(shù)字T(1≤T≤300000)-樣例個(gè)數(shù)。

每個(gè)樣例僅一行一個(gè)數(shù)字n(1≤n≤109)

輸出描述:

每個(gè)樣例輸出一行一個(gè)數(shù)字—Bonnie需要做的操作次數(shù)。

示例1

輸入

6
9
99
2
11032
1000000000
62

輸出

2
3
9
44
9
13

說明

<pre>第一個(gè)樣例: 9→10→1
第二個(gè)樣例: 99→100→10→1

//做不出純粹是我個(gè)人理解題目的問題
//我以為判斷條件是轉(zhuǎn)化成二進(jìn)制碼的最后一位，沒想到n%10暴力AC，orz
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
int main(){
    int n,count,t;
    scanf("%d",&t);
    while(t--){
        count=0;
        scanf("%d",&n);
        while(n>1){
        if(n%10==0)n=n/10;
        else n++;
        count++;
        };
       cout<<count<<endl;   
    }
        return 0;
}

鏈接：https://ac.nowcoder.com/acm/contest/893/C
來(lái)源：?？途W(wǎng)

C.Math Problem(簽到題)

題目描述

已知整數(shù)a,a3，a,a^3除192的余數(shù)是1。求區(qū)間[L,R]之間滿足條件的a的累加和是多少？

輸入描述:

<pre>第一行是一個(gè)整數(shù)T(1≤T≤10000）表示樣例的個(gè)數(shù)。
每個(gè)樣例包含兩個(gè)整數(shù)L,R,1≤L≤R≤109

輸出描述:

每行輸出一個(gè)樣例的結(jié)果。

示例1

輸入

1
1 10

輸出

1
超時(shí)代碼：

#include<stdio.h>
#include<iostream>
#define ll long long 
using namespace std;
ll f(ll l,ll r){
    ll sum=0;
    for(int i=l;i<=r;i++){
       ll m=i*i*i;
        if(m%192==1)
         sum+=i;   
    }
    return sum;
}
int main(){
    ll t,l,r,a;
    cin>>t;
    while(t--){
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",f(l,r));
    }
}

AC代碼1：找規(guī)律，復(fù)雜度減少
（ak+1)3=a3k3+3a2k2+3ak+1=(a2k3+3a1k^2+3k)a+1=a*x+1;

即（a*k+1）的3次方也是a的倍數(shù)+1；

#include<bits/stdc++.h>
using namespace std;
int t,l,r;

int main(){
   
    
    scanf("%d",&t);
    while(t--){
        long long ans=0;
        scanf("%d%d",&l,&r);
        int p=l/192,q=r/192;
        if(l%192>1)p++;
        if(r%192<1)q--;
        for(int i=p;i<=q;i++){
            ans=ans+(long long )i*192+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

AC代碼2：

#include<stdio.h>
#include<iostream>
#define inf 0x3f3f3f3f
#define ll long long 
using namespace std;
int t;
ll l,r,a;
ll f(ll l,ll r){
    ll sum=0;
    while(l%192!=1)
        l++;
    while(r%192!=1)
        r--;
    a=r/192-l/192+1;
    sum=((l+r)/2)*a;
    return sum;
}
int main(){
    cin>>t;
    while(t--){
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",f(l,r));
    }
}

鏈接：https://ac.nowcoder.com/acm/contest/893/D
來(lái)源：?？途W(wǎng)

D.stone(簽到題）

時(shí)間限制：C/C++ 1秒，其他語(yǔ)言2秒
空間限制：C/C++ 32768K，其他語(yǔ)言65536K
64bit IO Format: %lld

題目描述[](javascript:void(0);)[]

有n堆石子排成一排，第i堆石子有a個(gè)石子。
每次，你可以選擇任意相鄰的兩堆石子進(jìn)行合并，合并后的石子數(shù)量為兩堆石子的和，消耗的體力等價(jià)于兩堆石子中石子數(shù)少的那個(gè)。
請(qǐng)問，將所有的石子合并成一堆，你所消耗的體力最小是多少？

輸入描述:

第一行是一個(gè)整數(shù)T表示樣例的個(gè)數(shù)。
每個(gè)樣例的第一行是一個(gè)整數(shù)表示石子堆的數(shù)量。
第二行是n個(gè)整數(shù)ai(1≤ai≤109)

輸出描述:

每行輸出一個(gè)樣例的結(jié)果。

示例1

輸入

2
2
1 2
1
1

輸出

1
0

說明

巨大的輸入，請(qǐng)使用C風(fēng)格的輸入。

//兩兩求最大值，然后用總數(shù)減最大值
//  WA理由：long long必須用在n,a上
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
#include<queue>
#include<stdlib.h>
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
int main(){
    ll t,n;
    ll a[100000];
    scanf("%d",&t);
    while(t--){
        ll sum=0;
        scanf("%d",&n);
        ll Max=0;
        for(int i=0;i<n;i++){
           scanf("%lld",&a[i]);
            sum+=a[i];
           Max=max(Max,a[i]);
           
        }
        printf("%lld\n",sum-Max);
    }
    return 0;
}

F.Black & White

題目描述

你有一個(gè)長(zhǎng)度為 n 的 01 串S，你可以執(zhí)行最多 m 次操作。
對(duì)于每次操作，你可以選擇一個(gè)位置 i 滿足
1≤i≤n，翻轉(zhuǎn)這一位的值，0變成1，1變成0。
定義一個(gè) 01 串的價(jià)值為其中最長(zhǎng)連續(xù)0的個(gè)數(shù)和最長(zhǎng)連續(xù)1的個(gè)數(shù)的較大值，求S在經(jīng)過最多m次操作后的最大價(jià)值。

輸入描述:

第一行一個(gè)整數(shù) T ，表示接下來(lái)有 T 個(gè)樣例。
首先輸入n,m，表示S串的長(zhǎng)度n和操作次數(shù)m，其中
1≤n≤100000，0≤m≤10000；
接下來(lái)輸入一個(gè)長(zhǎng)度為n的字符串S。

輸出描述:

一個(gè)整數(shù)，表示題面上描述的最大價(jià)值。
示例1

輸入

2
5 1
00101
2 1
01

輸出

4
2

說明

第一個(gè)串翻轉(zhuǎn)第三個(gè)位置，00001的價(jià)值為4；第二個(gè)串翻轉(zhuǎn)第一個(gè)位置，11的價(jià)值為2。

思路：

  • 尺取法（目前還搞不太清楚，故貼出大佬的尺取法的學(xué)習(xí)地址：尺取法 — 詳解 + 例題模板(全)）
  • 前綴+二分法：
    首先預(yù)處理兩個(gè)數(shù)組 pre1 和 pre0，分別代表1～i個(gè)位置上1和0的個(gè)數(shù)
    這樣就可以在 O(1) 的時(shí)間求出 區(qū)間內(nèi) 1或者0 的個(gè)數(shù)
    然后二分答案：最大長(zhǎng)度len。
    因?yàn)?len 是固定的，所以 l=1，r=len 開始 滑動(dòng)窗口（時(shí)間O(n)），每次移動(dòng)都判斷當(dāng)前方塊內(nèi) 1或者0的個(gè)數(shù)是否小于 可以改變的次數(shù)m，如果小于等于 則 len 可以成立，可以往更大值二分，否則只能往更小值二分。
    時(shí)間復(fù)雜度：每次二分判斷需要O(n)的時(shí)間，二分需要log2(n)的時(shí)間，所以總時(shí)間n*lg(n)時(shí)間復(fù)雜度ok

貼出前綴+二分AC代碼：

//大佬（阿茶的庸醫(yī)）的代碼
#include <iostream>
#include <algorithm>
#include <string>
#define N 100010
using namespace std;
string str;
int n, m;
int pre0[N], pre1[N];//0和1的個(gè)數(shù)數(shù)組
//判斷是否可以進(jìn)行轉(zhuǎn)換
//(每次移動(dòng)都判斷當(dāng)前方塊內(nèi) 1或者0的個(gè)數(shù)是否小于 可以改變的次數(shù)m)
bool judjed(int len){
    int l = 1, r = len;
    while(r <= n){
        if(pre0[r]-pre0[l-1] <= m || pre1[r]-pre1[l-1] <= m)
            return true;
        ++l, ++r;
    }
    return false;
}
//二分
int get_n(){
    int res;
    int l=0, r=n;
    while(l <= r){
        int mid = (l+r)/2;
        if(judjed(mid)){//可以往更大值二分
            l = mid+1;
            res = mid;
        }else{
            r = mid-1;
        }
    }
    return res;   
}

int main(){
    int T;
    cin >> T;
    while(T--){
        cin >> n >> m;//n長(zhǎng)度，m操作次數(shù)
        cin >> str;
        for(int i=1; i<=n; i++){
            if(str[i-1] == '0'){
                pre0[i] = pre0[i-1]+1;
                pre1[i] = pre1[i-1];
            }else{
                pre0[i] = pre0[i-1];
                pre1[i] = pre1[i-1]+1;
            }
        }
        cout << get_n() << endl;
        str.clear();
    }
    return 0;
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容