臺州學院acm（臺州學院競賽_ACM省賽）

臺州學院競賽_ACM省賽-

臺州學院競賽_ACM省賽比賽地址戳這里1001:數學題：求極限：1002:maomeng的成就題解：對于某一個物品i，我們可以選擇他的第一個成就，或者選擇第二個成就，又或者不選，這樣我們就可以使用dfs,來遍歷所有情況。時間復雜度為O（3^10).#include<bits/stdc++.h>usingnamespacestd;constintN=10+5,mod=1e9+7;typedeflonglongLL;inttt[N],m[N],T[N],M[N];intn

比賽地址戳這里

1001 : 數學題：

求極限：

1002 : maomeng的成就

題解：
對于某一個物品i，我們可以選擇他的第一個成就，或者選擇第二個成就，又或者不選，這樣我們就可以使用dfs,來遍歷所有情況。時間復雜度為O（3^10).

#include<bits/stdc++.h>using namespace std;const int N=10+5,mod=1e9+7;typedef long long LL;int tt[N],m[N],T[N],M[N];int n,t,ans=0;void dfs(int i,int time,int sum){        //cout<<time<<endl;    if(time<=t)//如果時間小于t就比較。    {            ans=max(sum,ans);    }    if(i>n)return;//超過物品數量就返回。    dfs(i+1,time+tt[i],sum+m[i]);    dfs(i+1,time+T[i],sum+M[i]);    dfs(i+1,time,sum);}void solve(){        scanf("%d %d",&n,&t);    for(int i=1;i<=n;i++)    {            scanf("%d %d %d %d",&tt[i],&m[i],&T[i],&M[i]);    }    dfs(1,0,0);    printf("%d",ans);}int main(){        solve();}

是否還在為Ide開發工具頻繁失效而煩惱，來吧關注以下公眾號獲取最新激活方式。親測可用！

為防止網絡爬蟲，請關注公眾號回復”口令”

激活idea 激活CLion DataGrip DataSpell dotCover dotMemory dotTrace GoLand PhpStorm PyCharm ReSharper ReShaC++ Rider RubyMine WebStorm 全家桶 解鎖下載刷新

【正版授權，激活自己賬號】：Jetbrains全家桶Ide使用，1年售后保障，每天僅需1毛

【官方授權 正版激活】：官方授權 正版激活 自己使用，支持Jetbrains家族下所有IDE…

1003 : maomeng的boss戰

在一秒內我們收到的傷害為2n，那么我們就可以先將總血量除掉2n，那么剩下的血量如果大于等于n，那么就表示小z可以扛過這一秒，反之則不行。

#include<bits/stdc++.h>using namespace std;const int N=10+5,mod=1e9+7;typedef long long LL;int n,m;void solve(){        m-=1;//注意血量先減一    int s=2*n;    int cnt=m/2/n,re=m%(2*n);    if(re>=n)cnt++;    printf("%d\n",cnt);}int main(){        while(~scanf("%d %d",&n,&m))    {            solve();    }}

1004 : 競選總統：

題解：
記錄一下最高票數和平均票數,如果最高票數小于平均票數，則需要（平均票數-已有票數,否則，若最高票數無并列，則小于最高票數的需要（最高票數+1-已有票數），等于的要0票。若最高票數有并列，則需要（最高票數+1-已有票數。

#include <bits/stdc++.h>using namespace std;const int N = 2000;int n;int a[N];int main(){        cin >> n;    int m = -1,cnt = 0;    for(int i = 1; i <= n; i ++)    {            scanf("%d",&a[i]);        if(a[i] == m) cnt ++;        if(a[i] > m) m = a[i],cnt = 1;    }    for(int i = 1; i <= n; i ++)    {            if(a[i] < m) printf("%d",m - a[i] + 1);        else if(a[i] == m)        {                if(cnt > 1) printf("1");            else printf("0");        }        if(i != n) printf(" ");    }    return(0);}

1005 : maomeng的不知道什么東西

題解：
ps.數據可能弱了
首先對于一個數a[i],在他左邊有幾個比他小的數我們記作l[i]。
對于一個數a[i],在他右邊有幾個比他小的數我們記作r[i]。
對于每一個數a[i],他在答案里的貢獻就是了l[i]*r[i]*a[i]。
為什是這樣呢。因為相當于在他的左區域任意選一個點，右區域也任意選一個點，那么這個連續字串的值都為a[i]。
這樣我們就可以使用單調棧（不會的先了解一下）在O(n)的時間復雜度里求出l[i]和r[i]了。

#include<bits/stdc++.h>using namespace std;const int N=1e6+5,mod=1e9+7;typedef long long LL;LL a[N],l[N],r[N];struct node{ LL x,pos;};void solve(){ int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);a[0]=a[n+1]=1e9;stack<node>st;st.push({ a[0],0});for(int i=1;i<=n;i++){ if(!st.empty()){ while(st.top().x<=a[i])st.pop();}int x=st.top().x,pos=st.top().pos;l[i]=pos+1;st.push({ a[i],i});}while(!st.empty())st.pop();st.push({ a[n+1],n+1});for(int i=n;i>=1;i--){ if(!st.empty()){ while(st.top().x<a[i])st.pop();}int x=st.top().x,pos=st.top().pos;r[i]=pos-1;st.push({ a[i],i});}LL ans=0;for(int i=1;i<=n;i++){ LL L=(i-l[i]+1),R=(r[i]-i+1);ans=((L*R*a[i])%mod+ans)%mod;}printf("%lld",ans);}int main(){ solve();}

1006 : maomeng請了外援

題解：
經過觀察（真的。我們可以發現只要將前兩行的三個字母確定了，那么n階金字塔就確定了。
我們暴力模擬出六種情況的金字塔，和原金字塔進行比較，篩選出重合度最高的然后就可以了。

#include<bits/stdc++.h>using namespace std;const int N=1e3+5,mod=1e9+7;typedef long long LL;int a[N][N];int t[7][N][N];int n;void st(int x,int y,int id){ t[id][x][y]=6-(t[id][x-1][y]+t[id][x-1][y-1]);}void solve(){ scanf("%d",&n);for(int i=1;i<=n;i++){ getchar();for(int j=1;j<=i;j++){ char p;scanf("%c",&p);if(p=='G')a[i][j]=1;if(p=='R')a[i][j]=2;if(p=='B')a[i][j]=3;}}t[1][1][1]=1;t[1][2][1]=2;t[1][2][2]=3;t[2][1][1]=1;t[2][2][1]=3;t[2][2][2]=2;t[3][1][1]=2;t[3][2][1]=1;t[3][2][2]=3;t[4][1][1]=2;t[4][2][1]=3;t[4][2][2]=1;t[5][1][1]=3;t[5][2][1]=1;t[5][2][2]=2;t[6][1][1]=3;t[6][2][1]=2;t[6][2][2]=1;for(int i=1;i<=6;i++){ for(int j=3;j<=n;j++){ for(int k=2;k<n;k++)st(j,k,i);//注意特判每行的第一個和第最后一個t[i][j][1]=6-(t[i][j-1][1]+t[i][j][2]);t[i][j][j]=6-(t[i][j-1][j-1]+t[i][j][j-1]);}}int res=0;for(int i=1;i<=6;i++){ int ans=0;for(int j=1;j<=n;j++){ for(int k=1;k<=j;k++){ if (t[i][j][k] == a[j][k])ans++;}}res=max(ans,res);}printf("%d",n*(n+1)/2-res);}int main(){ solve();}