ExiaGN001 发表于 2023-2-1 07:55:34

USACO Cu T1 题解

本帖最后由 ExiaGN001 于 2023-2-3 07:43 编辑

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


#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    char a;
    int b;
    int cntg=0,cnth=0;
    int leadg=0,leadh=0;
    for(int i=0;i<n;i++)
    {
      cin>>a;
      if(a=='G')cntg++;
      else cnth++;
    }
    for(int i=0;i<n;i++)
    {
      cin>>b;
    }
    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;j++)
      {
            if(a==a)tmpcnt++;
            if((m2==1&&a=='G')|| (m1==1&&a=='H'))//是另一群首领
                flglead=1;
      }

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

最佳答案和题目无关！

ExiaGN001 发表于 2023-2-1 07:57:40

本帖最后由 ExiaGN001 于 2023-2-1 08:07 编辑

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

liuhongrun2022 发表于 2023-2-1 08:27:34

领鱼币

zhangjinxuan 发表于 2023-2-1 08:54:40

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

zhangjinxuan 发表于 2023-2-1 08:57:02

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

ExiaGN001 发表于 2023-2-1 09:04:38

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

我没去考试（悲

zhangjinxuan 发表于 2023-2-1 09:06:28

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

啊{:10_277:}
{:10_306:}
{:10_291:}
{:10_284:}
{:10_260:}
{:10_266:}

三五七言2 发表于 2023-2-1 15:48:46

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

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

三五七言2 发表于 2023-2-1 15:49:25

#include <bits/stdc++.h>
using namespace std;
const int N=1009;
int start,eend,temp,a,b,leess,money,s=1;
int n,m,ans=INT_MAX;
string number;
bool OK(string s){
        int cover,cool;
        memset(cool,0,sizeof(int)*10);
        memset(cover,0,sizeof(int)*10);
        for(int i=0;i<s.size();i++)
                if(s=='1')
                        for(int j=a;j<=b;j++)
                                cool+=leess;
        for(int i=0;i<n;i++)
                for(int m=start;m<=eend;m++)
                        if(cool<temp) return false;
        return true;
}
int price(string s){
        int total=0;
        for(int i=0;i<s.size();i++)
                if(s=='1') total+=money;
        return total;
}
int main(){
        cin>>n>>m;
        for(int i=0;i<n;i++) cin>>start>>eend>>temp;
        for(int i=0;i<m;i++) cin>>a>>b>>leess>>money;
        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 发表于 2023-2-1 18:08:08

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

其实更像后缀一些

zhangjinxuan 发表于 2023-2-2 12:26:13

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

ExiaGN001 发表于 2023-2-2 13:17:11

本帖最后由 ExiaGN001 于 2023-2-2 13:19 编辑

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

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

zhangjinxuan 发表于 2023-2-2 13:50:42

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

没事
页: [1]
查看完整版本: USACO Cu T1 题解