第15届台州学院校赛题解

Red学编程

注意判断 ac个数 等于零的情况不要re

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int sum=0,cnt=0;
        for(int i=1;i<=n;i++)
        {
            int x;char op[4];
            scanf("%d %s",&x,op);
            if(op[0]=='A') sum+=x,cnt++;
        }
        if(cnt==0) puts("0 0");
        else printf("%d %d\n",sum,sum/cnt);
    }
}

##Red的长跑

只能在早上跑和晚上跑的，直接就减掉
统计以及早上和晚上都能跑的可不可以平均分摊到剩下要跑的天数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int main()
{
    int n,a,b,cnt=0;
    scanf("%d %d %d",&n,&a,&b);
    for(int i=1;i<=n;i++)
    {
        int f[3];
        scanf("%d %d",&f[1],&f[2]);
        if(f[1]==1&&f[2]==0) a=max(a-1,0);
        if(f[1]==0&&f[2]==1) b=max(b-1,0);
        if(f[1]==1&&f[2]==1) cnt++;
    }
    if(a+b<=cnt) puts("Yes");
    else puts("No");
}

Red去购物

贪心 剩下的钱直接先取最大的纸币
dp 背包模型

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int main()
{
    int a,b,c,d,e,f,x;
    while(~scanf("%d %d %d %d %d %d %d",&a,&b,&c,&d,&e,&f,&x))
    {
        int sum=a+b*5+c*10+d*20+e*50+f*100;
        if(sum<x) puts("oh no!");
        else
        {
            int v[6]={1,5,10,20,50,100};
            sum-=x;
            int ans=0;
            for(int i=5;i>=0;i--)
            {
                ans+=sum/v[i];
                sum-=(sum/v[i])*v[i];
            }
            printf("%d\n",ans);
        }
    }
}

Red的挖洞

bfs 直接将所有洞放入队列里，将地图上的每个点更新成与他最近的洞的编号，由于入队时满足小的编号在前面，所以题目要求 **（如果有多个出口的“曼哈顿距离”相同，选择出口编号最小的）**就可以满足
最后暴力更新x，y即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
struct node{
    int x,y;
};
queue<node>q;
int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};
int mp[1005][1005];
bool check(int x,int y)
{
    if(x<0||x>1000) return 0;
    if(y<0||y>1000) return 0;
    if(mp[x][y]) return 0;
    return 1;
}
void bfs()
{
    while(q.size())
    {
        int x=q.front().x,y=q.front().y;q.pop();
        for(int i=0;i<4;i++)
        {
            int tx=x+dx[i],ty=y+dy[i];
            if(check(tx,ty))
            {
                mp[tx][ty]=mp[x][y];
                q.push({tx,ty});
            }
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        q.push({x,y});
        mp[x][y]=i;
    }
    bfs();
    int sx,sy;
    scanf("%d %d",&sx,&sy);
    int ans[1005];
    memset(ans,0x3f,sizeof ans);
    for(int i=0;i<=1000;i++)
    {
        for(int j=0;j<=1000;j++)
        {
            ans[mp[i][j]]=min(ans[mp[i][j]],abs(i-sx)+abs(j-sy));
        }
    }
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
}

Red学语言

字符串模拟
统计三个冒号的位置即可
第一个数字位切片的开始索引；
第二个数字位切片的结束索引；
第三个数字位切片的步长；
观察可以发现：
第一个数字在第一个冒号前面
第二个数字在第二个冒号前面
第三个数字在第二个冒号后面

注意最后如果没有遍历到数字，将其改为默认

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int main()
{
    char s[1005];int m;
    scanf("%s %d",s,&m);
    while(m--)
    {
        char op[20];
        scanf("%s",op);
        int a[3]={-1,-1,-1},cnt=0;
        for(int i=0;op[i];i++)
        {
            if(op[i]==':') cnt++;
            if(op[i]>='0'&&op[i]<='9')
            {
                if(a[cnt]==-1) a[cnt]=op[i]-'0';
                else a[cnt]=a[cnt]*10+op[i]-'0';
            }
        }
        if(a[0]==-1) a[0]=0;
        if(a[1]==-1) a[1]=strlen(s);
        if(a[2]==-1) a[2]=1;
        for(int i=a[0];i<a[1];i+=a[2]) putchar(s[i]);
        putchar('\n');
    }
}

Red的序列

贪心处理每个数字即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll f(ll x)
{
    ll nums[15],cnt=0,ans=0;
    while(x)
    {
        nums[++cnt]=x%10;
        x/=10;
    }
    sort(nums+1,nums+1+cnt);
    for(int i=cnt;i;i--) ans=ans*10+nums[i];
    return ans;
}
int main()
{
    int n;
    scanf("%d",&n);
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        ll x;
        scanf("%lld",&x);
        sum+=f(x);
    }
    printf("%lld",sum);
}

yuyu的作业

简单的分解质因数 分解到两个相同的质因数即可输出sorry退出

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            int cnt=0;
            while(n%i==0)
            {
                n/=i;
                cnt++;
            }
            if(cnt>=2)
            {
                puts("Sorry");
                return 0;
            }
        }
    }
    puts("OK");
}

yuyu的扑克牌

两个for循环暴力更新即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int main()
{
    int n;
    int a[15];
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int ans=-1000;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i-1;j++)
        {
            ans=max(a[i]*a[j],ans);
        }
    }
    printf("%d",ans);
}

Red的字符

贪心考虑 如果后面有比当前大的字母那这个字母就不选

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
char s[100005];
// aaazzxbay
//    zzy
int main()
{
    int cnt[26]={0};
    scanf("%s",s);
    for(int i=0;s[i];i++) cnt[s[i]-'a']++;
    for(int i=0;s[i];i++)
    {
        int num=0;
        for(int j=s[i]-'a'+1;j<26;j++) num+=cnt[j];

        if(num==0) putchar(s[i]);

        cnt[s[i]-'a']--;
    }
}

Red去上课

字符串模拟

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
char s[100005];
// aaazzxbay
//    zzy
char ss[505][505][15];
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    int cnt=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            scanf("%s",ss[i][j]);
            if(strcmp(ss[i][j],"null")) cnt++;
        }
    }
    int ans=(int)ceil(cnt*1.0/m);
    printf("%d\n",ans);

    int idx=(n-1)*m+m-1,idx1=(ans-1)*m+m-1;
    while(1)
    {
        int x=idx/m,y=idx%m;
        int x1=idx1/m,y1=idx1%m;
        if(x==ans-1) break;
        if(strcmp(ss[x][y],"null")&&(!strcmp(ss[x1][y1],"null")))
        {
            swap(ss[x][y],ss[x1][y1]);
        }
        if(strcmp(ss[x][y],"null")&&(!strcmp(ss[x1][y1],"null"))) //后有人前有空位
        {
            idx--,idx1--;
        }
        if((!strcmp(ss[x][y],"null"))&&(!strcmp(ss[x1][y1],"null"))) //后没人前有空位
        {
            idx--;
        }
        if((!strcmp(ss[x][y],"null"))&&strcmp(ss[x1][y1],"null"))//后没人前没有空位
        {
            idx--;idx1--;
        }
        if(strcmp(ss[x][y],"null")&&strcmp(ss[x1][y1],"null"))// 后有人前没有空位
        {
            idx1--;
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(j) printf(" ");
            printf("%s",ss[i][j]);
        }
        printf("\n");
    }
}

Red的矿工

map分组
分类讨论详细见代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int gcd(int a,int b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}
map<pair<int,int>,int> mp;
int idx;
vector<int>G[1005];
bool cmp(int a,int b)
{
    return a>b;
}
struct node{
    int x,y,w;
}p[1005];
bool cmp2(node a,node b)
{
    return abs(a.x)<abs(b.x);
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].w);

    sort(p+1,p+1+n, cmp2);
    for(int i=1;i<=n;i++)
    {
        int x=p[i].x,y=p[i].y,w=p[i].w;
        int g=abs(gcd(x,y));
        x/=g;y/=g;
        if(!mp.count({x,y})) mp[{x,y}]=++idx;
        if((int) G[mp[{x,y}]].size()<3) G[mp[{x,y}]].push_back(w);
    }

    // 全部只抓第一个;

    int nums[1005]={0},ans=0;


    for(int i=1;i<=idx;i++) nums[i]=G[i][0];
    sort(nums+1,nums+idx+1,cmp);
    ans=nums[1]+nums[2]+nums[3];

    // 全部只抓三个

    for(int i=1;i<=idx;i++)
    {
        if(G[i].size()==3) ans=max(ans,G[i][0]+G[i][1]+G[i][2]);
    }

    // 只抓第一个 和 其他的 抓两个
    for(int i=1;i<=idx;i++)
    {
        if(G[i].size()>=2)
        {
            for(int j=1;j<=idx;j++)
            {
                if(j==i) continue;
                ans=max(ans,G[i][0]+G[i][1]+G[j][0]);
            }
        }
    }
    printf("%d",ans);
}

Red的大鱼

赛时被暴力卡过了
正解最小堆+离散化+树状数组

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7,N=1e5,INF=0x3f3f3f3f;
struct node{
    int pos;
    ll v;
    friend bool operator <(node a,node b)
    {
        return a.pos>b.pos;
    }
}p[N+5];

priority_queue<node> q;
ll t[N+5];
ll ans[N+5];
ll query(int x)
{
    ll ans=0;
    for(int i=x;i;i-=i&(-i)) ans+=t[i];
    return ans;
}
void add(int x,ll v)
{
    for(int i=x;i<=N;i+=i&(-i)) t[i]+=v;
}
vector<int>vec;
int findx(int x){return lower_bound(vec.begin(),vec.end(),x)-vec.begin()+1;}
int main()
{
    int n,w;
    scanf("%d %d",&n,&w);
    vec.push_back(0);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %lld",&p[i].pos,&p[i].v);
        vec.push_back(p[i].pos);
    }
    sort(vec.begin(), vec.end());
    add(findx(0),w);
    for(int i=1;i<=n;i++)
    {
        int pos=findx(p[i].pos);ll v=p[i].v;
        int last=pos;
        q.push({pos,v});
        while(q.size())
        {
            int a=q.top().pos,b=q.top().v;
            last=a;
            if(query(a)>b) add(a,b),q.pop();
            else break;
        }
        if(q.empty()) last=N;
        ans[i] = query(last);
    }
    for(int i=1;i<=n;i++)
    {
        if(ans[i]!=ans[i-1]) printf("%lld\n",ans[i]);
    }
}

Red的拼接

组合数公式

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
// a+k=b;
// (112)89 + 9 = (112)98
// (121)89 + 9 = (121)98
// A(c1+c2+...cn,c1+c2+...cn)/A(C1,C1)/A(C2,C2)
// C(n,c1)*C(n-c1,c2)*C(n-c1-c2,c2);
// 79 +9 =88
// C(n,m)=C(n-1,m-1)+C(n-1,m)
int c[10],k;
ll C[25][25];
ll f(int x,int y)
{
    unordered_map<int,int> cnt;
    for(int tx=1;tx<=x;tx++)
    {
        int dx=tx;
        for(int i=2;i*i<=dx;i++)
        {
            while(dx%i==0) cnt[i]++,dx/=i;
        }
        if(dx>1) cnt[dx]++;
    }
    for(int tx=1;tx<=y;tx++)
    {
        int dx=tx;
        for(int i=2;i*i<=dx;i++)
        {
            while(dx%i==0) cnt[i]--,dx/=i;
        }
        if(dx>1) cnt[dx]--;
    }
    for(int tx=1;tx<=x-y;tx++)
    {
        int dx=tx;
        for(int i=2;i*i<=dx;i++)
        {
            while(dx%i==0) cnt[i]--,dx/=i;
        }
        if(dx>1) cnt[dx]--;
    }
    ll ans=1;
    for(auto i:cnt)
    {
        for(int j=1;j<=i.second;j++) ans*=i.first;
    }
    return ans;
}
ll check(int a,int b)
{
    int ca[10]={0},cb[10]={0};
    int cr[10]={0};
    while(a)
    {
        if(a%10==0) return 0;
        ca[a%10]++;
        a/=10;
    }
    while(b)
    {
        if(b%10==0) return 0;
        cb[b%10]++;
        b/=10;
    }
    for(int i=1;i<=9;i++)
    {
        if(cb[i]!=ca[i]) return 0;
        if(ca[i]>c[i]) return 0;
    }
    int sum=0;
    for(int i=1;i<=9;i++)
    {
        cr[i]=c[i]-ca[i];
        sum+=cr[i];
    }
    ll ans=1;
    for(int i=1;i<=9;i++)
    {
        ans=ans*C[sum][cr[i]];
        sum-=cr[i];
    }
    return ans;
}
unordered_map<int,int>mp;
int main()
{
    for(int i=0;i<=24;i++)
        for(int j=i;j<=24;j++)
        {
            C[j][i]=f(j,i);
            //cout<<j<<" "<<i<<" "<<C[j][i]<<endl;
        }
    for(int i=1;i<=9;i++) scanf("%d",&c[i]);
    scanf("%d",&k);
    ll ans=0;
    int top=1;
    for(int i=k;i<100000;i++)
    {
        int vec[10],x=i,flag=0,cnt=0;

        while(x)
        {
            vec[++cnt]=x%10;
            x/=10;
        }
        for(int i=1,k=1,sum=0;i<=cnt;i++,k*=10)
        {
            sum=sum+k*vec[i];
            if(mp[sum])
            {
                flag=1;
                break;
            }
        }
        if(flag) continue;
        ll res=check(i,i-k);
        if(res) mp[i]=1;
        ans+=res;
    }
    printf("%lld",ans);
}