浙大校赛(现场团体出6题) 2019/4/14

            <!-- wp:paragraph -->

http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5969

A题,给出男生女生的身高,以及他们的配对原则,1只能跟0配对,0只能跟1配对,同时,男生是1的时候要比女生的身高矮,如果男生是0的时候,要比女生身高要高。求这个舞会,最大的匹配数量。

贪心:分组从小到大排序,然后如果标号为1的男子,就选是否存在比他高一点点的女生。。之类的。(现场wa了,绪杰重构之后过了,待补)(已补,问题出在输入的时候,用n来读入女生)

//绪杰的代码
#include<bits/stdc++.h>
using namespace std;
int a0[100005],a1[100005],b0[100005],b1[100005],a[100005],b[100005];
int main()
{
    int T;
    cin>>T;
    int n,m;
    int na0,na1,nb0,nb1;
    int tmp;
    int p,ans;
    while(T--)
    {
        cin>>n>>m;
        for(int i=0;i<n;i++)
            cin>>a[i];
        for(int i=0;i<m;i++)
            cin>>b[i];
        na0=0;na1=0;nb0=0;nb1=0;
        for(int i=0;i<n;i++)
        {
            cin>>tmp;
            if(tmp==0) a0[na0++]=a[i]; else a1[na1++]=a[i];
        }
        for(int i=0;i<m;i++)
        {
            cin>>tmp;
            if(tmp==0) b0[nb0++]=b[i]; else b1[nb1++]=b[i];
        }
        //cout<<na0<<" "<<na1<<" "<<nb0<<' '<<nb1<<endl;
        sort(a0,a0+na0);
        sort(a1,a1+na1);
        sort(b0,b0+nb0);
        sort(b1,b1+nb1);
        p=0;
        ans=0;
        for(int i=0;i<na0;i++)
        {
            //cout<<a0[i]<<' '<<b1[p]<<endl;
            if (a0[i]>b1[p])
            {
                ans++;
                p++;
                if(p>=nb1) break;
            }
        }
        p=0;
        for(int i=0;i<nb0;i++)
        {
            if (b0[i]>a1[p])
            {
                ans++;
                p++;
                if(p>=na1) break;
            }
        }
        cout<<ans<<endl;
    }
}
//My WA submit
#include<bits/stdc++.h>
using namespace std;
vector<int> man0,man1,women0,women1;
vector<int> a,b;
void print(vector<int> &a)
{
    for(int i=0;i<a.size();i++)
        cout<<a[i]<<" ";
    cout<<endl;
}
bool cmp(int x,int y)
{
    return x>y;
}
int main(){
    int T;
    //freopen("in.txt","r",stdin);
    scanf("%d",&T);
    while(T--)
    {
        man0.clear();
        man1.clear();
        women0.clear();
        women1.clear();
        a.clear();
        b.clear();
        int n,m;
        cin>>n>>m;
        for(int i=0;i<n;i++)
        {
            int x;
            scanf("%d",&x);
            a.push_back(x);
        }
        for(int i=0;i<n;i++)//这里就是错误点,应该改成m
        {
            int x;
            scanf("%d",&x);
            b.push_back(x);
        }
        for(int i=0;i<n;i++)
        {
            int x;
            scanf("%d",&x);
            if(x==0)
            {
                man0.push_back(a[i]);
            }else
            {
                man1.push_back(a[i]);
            }
        }
        for(int i=0;i<n;i++)
        {
            int x;
            scanf("%d",&x);
            if(x==0)
            {
                women0.push_back(b[i]);
            }else
            {
                women1.push_back(b[i]);
            }
        }

    //  cout<<"men0:"<<endl;
    //  print(women0);

        //men==0,women==1 then height(men)>height(women)
        int ans=0;  

        int left=0;
        int right=0;
        sort(man0.begin(),man0.end(),cmp);
        sort(women1.begin(),women1.end(),cmp);
        while((left<man0.size()&&right<women1.size()))
        {
            if(man0[left]>women1[right])
            {
                ans++;
                left++;
                right++;
                if(!(left<man0.size()&&right<women1.size()))
                {
                    break;
                }
            }else
            {
                right++;
                if(!(left<man0.size()&&right<women1.size()))
                {
                    break;
                }               
            }
        }

        //men==1,women==0 then height(men)<height(women)
        left=0;
        right=0;
        sort(man1.begin(),man1.end());
        sort(women0.begin(),women0.end());
        while((left<man1.size()&&right<women0.size()))
        {
            if(man1[left]<women0[right])
            {
                ans++;
                left++;
                right++;
                if(!(left<man1.size()&&right<women0.size()))
                {
                    break;
                }
            }else
            {
                right++;
                if(!(left<man1.size()&&right<women0.size()))
                {
                    break;
                }
            }
        }
        cout<<ans<<endl;
    }
}

B题是一道,大整数运算的题目,大整数除法,写得比较得心应手,但是大整数加法写崩了。需要补一下大加的板子。最后还是套的板子过的,有点难受。

C题是一道模拟题,给出一个机器人的指令集,然后给出在某个坐标,然后计算出这个坐标对应的指令是啥。然后要你求出通过这个指令运算,最多捡起多少个垃圾。这题是一个大模拟。但是我的哈希函数写的有点问题,n是行数,m是列数,我的哈希映射为n*x+y,这显然是有问题的…应该是m*x+y;

然后这个代码有必要贴一下,因为我觉得这是我写的最工整的一个模拟题了。

#include<bits/stdc++.h>
using namespace std;
int f[2005][2005];
int run(int x,int y)
{
    int sum=3*3*3*3*f[x][y]+
            3*3*3*f[x-1][y]+
            3*3*f[x+1][y]+
            3*f[x][y-1]+
            f[x][y+1];
    return sum;
}
int n,m;
set<int> st;

int hash(int x,int y)
{
    return x*m*n+y;
}

bool is_move(int x,int y,char move)
{
    if(move=='I') return false;
    if(move=='P')
    {
        if(f[x][y]==2) return true;
        return false;
    }
    if(move=='U')
    {
        int h=hash(x-1,y);
        //if zhao dao le 
        if(st.find(h)!=st.end()) return false;
        if(f[x-1][y]!=1) return true;
        return false;
    }
    if(move=='D')
    {
        int h=hash(x+1,y);
        if(st.find(h)!=st.end()) return false;
        if(f[x+1][y]!=1) return true;
        return false;
    }
    if(move=='L')
    {
        int h=hash(x,y-1);
        if(st.find(h)!=st.end()) return false;
        if(f[x][y-1]!=1) return true;
        return false;
    }
    if(move=='R')
    {
        int h=hash(x,y+1);
        if(st.find(h)!=st.end()) return false;
        if(f[x][y+1]!=1) return true;
        return false;
    }
}

int main()
{
    //freopen("in.txt","r",stdin);
    int t;
    cin>>t;
    while(t--)
    {
        //while(!st.empty()) st.pop();
        st.clear();
        int x,y;
        long long k;
        cin>>n>>m;
        cin>>x>>y>>k;
        string s;
        cin>>s;
        for(int i=0;i<n;i++)
        {
            string t;
            cin>>t;
            for(int j=0;j<m;j++)
            {
                int temp=t[j]-'0';
                f[i][j]=temp;
            }
        }
        int now_x=x-1,now_y=y-1;
        int ans=0;
        st.insert(hash(now_x,now_y));
        while(k--)
        {
            int sum=run(now_x,now_y);
            if(is_move(now_x,now_y,s[sum]))
            {
                if(s[sum]=='P')
                {
                    f[now_x][now_y]=0;
                    ans++;
                    st.clear();
                    st.insert(hash(now_x,now_y));
                }else
                {
                    if(s[sum]=='R') now_y=now_y+1;
                    if(s[sum]=='L') now_y=now_y-1;
                    if(s[sum]=='U') now_x=now_x-1;
                    if(s[sum]=='D') now_x=now_x+1;
                    st.insert(hash(now_x,now_y));
                }
            }else
            {
                break;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

J是水题,不说了

E是绪杰第一个出的题目,我没看题,也不说了

G题待补

您可能还喜欢...

发表评论

电子邮件地址不会被公开。 必填项已用*标注