[已解决]USACO Cu T1 题解

ExiaGN001

如题，代码在付费区。

思路：从后往前遍历，满足题目中任一条件即加入map，最后统计两者之积。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    char a[n];
    int b[n];
    int cntg=0,cnth=0;
    int leadg=0,leadh=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(a[i]=='G')cntg++;
        else cnth++;
    }
    for(int i=0;i<n;i++)
    {
        cin>>b[i];
    }
    map<int,int> m1,m2;//m1,m2分别记录G,H的首领

    bool flgsame=1,flglead=1;
    for(int i=n-1;i>=0;i--)
    {
        int tmpcnt=0;
        flglead=0;

        for(int j=i;j<b[i];j++)
        {
            if(a[i]==a[j])tmpcnt++;
            if((m2[j]==1&&a[i]=='G')|| (m1[j]==1&&a[i]=='H'))//是另一群首领
                flglead=1;
        }

        if((tmpcnt==cntg&&a[i]=='G')||(tmpcnt==cnth&&a[i]=='H')||flglead)
        {
            if(a[i]=='G'){m1[i]=1;leadg++;}
            else {m2[i]=1;leadh++;}
            //cout<<i<<" "<<a[i]<<"\n";
        }
    }
    cout<<leadg*leadh;
}

最佳答案和题目无关！

最佳答案

月排行榜 / 总排行榜

三五七言2

2023-2-1 15:49:25

#include <bits/stdc++.h>
using namespace std;
const int N=1009;
int start[N],eend[N],temp[N],a[N],b[N],leess[N],money[N],s=1;
int n,m,ans=INT_MAX;
string number;
bool OK(string s){
        int cover[N],cool[N];
        memset(cool,0,sizeof(int)*10);
        memset(cover,0,sizeof(int)*10);
        for(int i=0;i<s.size();i++)
                if(s[i]=='1')
                        for(int j=a[i];j<=b[i];j++)
                                cool[j]+=leess[i];
        for(int i=0;i<n;i++)
                for(int m=start[i];m<=eend[i];m++)
                        if(cool[m]<temp[i]) return false;
        return true;
}
int price(string s){
        int total=0;
        for(int i=0;i<s.size();i++)
                if(s[i]=='1') total+=money[i];
        return total;
}
int main(){
        cin>>n>>m;
        for(int i=0;i<n;i++) cin>>start[i]>>eend[i]>>temp[i];
        for(int i=0;i<m;i++) cin>>a[i]>>b[i]>>leess[i]>>money[i];
        for(int i=1;i<=m;i++) s*=2;
        for(int i=1;i<=s-1;i++){
                number="";
            for(int j=m-1;j>=0;j--){
                        int k=((i>>j)&1);
                stringstream ss;
                        ss<<k,number+=ss.str();       
            }
                if(OK(number)) ans=min(ans,price(number));
    }
    cout<<ans<<endl;
    return 0;
}

跳转到最佳答案楼层

ExiaGN001

@学习编程的采集 @EODVT @三五七言2 @Shioy
题解来喽~

liuhongrun2022

领鱼币

zhangjinxuan

我还以为是前缀和，写了将近150行，结果2个点错了

zhangjinxuan

我觉得全场最难的就是第一题，第二题一道01序列，第三题是个水题
既然楼主第一题都做出来了，那么楼主岂不满分也？岂不晋级也？

ExiaGN001

zhangjinxuan 发表于 2023-2-1 08:57
我觉得全场最难的就是第一题，第二题一道01序列，第三题是个水题
既然楼主第一题都做出来了，那 ...

我没去考试（悲

zhangjinxuan

ExiaGN001 发表于 2023-2-1 09:04
我没去考试（悲

啊

三五七言2

ExiaGN001 发表于 2023-2-1 07:57
@学习编程的采集 @EODVT @三五七言2 @Shioy
题解来喽~

大佬我问问第二题，我过了一个测试点，然后下面的测试点全红，你能帮我看看错哪了吗

三五七言2

#include <bits/stdc++.h>
using namespace std;
const int N=1009;
int start[N],eend[N],temp[N],a[N],b[N],leess[N],money[N],s=1;
int n,m,ans=INT_MAX;
string number;
bool OK(string s){
        int cover[N],cool[N];
        memset(cool,0,sizeof(int)*10);
        memset(cover,0,sizeof(int)*10);
        for(int i=0;i<s.size();i++)
                if(s[i]=='1')
                        for(int j=a[i];j<=b[i];j++)
                                cool[j]+=leess[i];
        for(int i=0;i<n;i++)
                for(int m=start[i];m<=eend[i];m++)
                        if(cool[m]<temp[i]) return false;
        return true;
}
int price(string s){
        int total=0;
        for(int i=0;i<s.size();i++)
                if(s[i]=='1') total+=money[i];
        return total;
}
int main(){
        cin>>n>>m;
        for(int i=0;i<n;i++) cin>>start[i]>>eend[i]>>temp[i];
        for(int i=0;i<m;i++) cin>>a[i]>>b[i]>>leess[i]>>money[i];
        for(int i=1;i<=m;i++) s*=2;
        for(int i=1;i<=s-1;i++){
                number="";
            for(int j=m-1;j>=0;j--){
                        int k=((i>>j)&1);
                stringstream ss;
                        ss<<k,number+=ss.str();       
            }
                if(OK(number)) ans=min(ans,price(number));
    }
    cout<<ans<<endl;
    return 0;
}

ExiaGN001

zhangjinxuan 发表于 2023-2-1 08:54
我还以为是前缀和，写了将近150行，结果2个点错了

其实更像后缀一些

zhangjinxuan

想参加 鱼C竞赛团队吗 https://fishc.com.cn/thread-223500-1-1.html

ExiaGN001

zhangjinxuan 发表于 2023-2-2 12:26
想参加 鱼C竞赛团队吗 https://fishc.com.cn/thread-223500-1-1.html

之前看过团规，我这种划水的肯定不满足条件
但是我还是要参加

zhangjinxuan

ExiaGN001 发表于 2023-2-2 13:17
之前看过团规，我这种划水的肯定不满足条件
但是我还是要参加

没事