台州学院竞赛_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();}