A. Bad Triangle

제목:

승차순 하나 드릴게요.물음: 삼각형이 될 수 없는 트리플 (삼원조) 이 존재하는지 여부입니다.

아이디어:

가장 작은 두 변과 가장 큰 변을 취하다.a【1】+a【2】<=a【n】시 조건을 만족시킨다.

AC

#include 
using namespace std;
const int maxn=5e4+10;
int a[maxn];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        int ans=-1;
        int n;cin>>n;
        for(int i=1; i<=n; i++)cin>>a[i];
        if(a[1]+a[2]<=a[n])ans=1;
        if(ans==1)cout<<1<<' '<<2<<' '<<n<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}

B. Substring Removal Game

제목:

01열에는 다음과 같은 작업이 있습니다.

문자를 지웁니다.

또는 연속적인 1(또는 0)

을 없애다
한 사람당 한 번씩 조작하고 번갈아 오다.(최종 점수는 1을 뺀 개수).
질문:앨리스의 점수를 구하다

아이디어:

한 명당 더 가고 싶을 거야.(만약 0101이 이렇게 된다면 틀림없이 가지 않을 것이다0. 왜냐하면 갔기 때문이다0. 그러면 상대는 11가 없어질 수 있기 때문이다.)

그럼 연속 1을 집계하면 됩니다.

AC

#include 
#include 
#include 
#include 
using namespace std;
char s[200];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        vector<int>v;
        cin>>(s+1);
        int len=strlen(s+1);
        int cnt=0,flag=0;
        for(int i=1; i<=len; i++){
            if(s[i]=='1')cnt++,flag=1;
            else {
                if(cnt)v.push_back(cnt);
                cnt=flag=0;
            }
        }
        if(cnt)v.push_back(cnt);
        sort(v.begin(),v.end());
        int ed=v.size()-1;
        int ans=0;
        for(int i=ed; i>=0; i-=2)ans+=v[i];
        cout<<ans<<endl;
    }
    return 0;
}

C. Good Subarrays

제목:

good subarray 。구:good subarray가 몇 개 있어요?

아이디어:

특히 1111을 고려할 수 있다.그러면 5(구간 길이) = 5(구간 화)에 해당한다.

이렇게 직접 찾으면 n2n^2n2.그럼 방법을 강구해서 최적화시켜야지.

시간 복잡도는 good subarray의 이 조건에서 나타난다는 것을 위에서 알 수 있다.그럼 방법을 생각해 조건을 간소화하자.

개수를 1로 줄일 수 있다.그러면 。(이 조건은 간소화할 수 있고 구간 안의 모든 수는 1을 줄일 수 있다. 만약에 조건이 충족된다면 이 구간의 합은 0이어야 한다)는 것을 간소화할 수 있다.ii i를 종점으로 하는 하위 서열에는 몇 개의 good subarray가 있다.

eg1 :11111 pre[1]=0, pre[2]=0, pre[3]=0, pre[4]=0, pre[5]=0 ans=1(i=1)+2(i=2)+3(i=3)+4(i=4)+5(i=5).
eg2: 110202 pre[1]=0, pre[2]=0, pre[3]=-1, pre[4]=0, pre[5]=-1, pre[2]=0, ans= 1+2+0+3+1+4

AC

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn=9e5+10;
ll pre[maxn];//,sum[maxn];
char s[maxn];
map<int,int>ma;
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        cin>>(s+1);
        ma.clear();
        pre[0]=0;//sum[0]=0;
        for(int i=1; i<=n; i++)pre[i]=pre[i-1]+s[i]-'0'-1;
        ll ans=0;
        ma[0]=1;
        for(int i=1; i<=n; i++)ans+=ma[pre[i]]++;
        cout<<ans<<endl;
    }
    return 0;
}

D. Colored Rectangles

제목:

r변, g변, b변이 있습니다.두 개의 조합 직사각형.구: a n s = ∑p a r e a ans=\sumparea ans=∑p​area.

아이디어:

단순 상태

먼저 순서를 정한다.

모든 상태를 계산하고 max를 취한다.

AC

#include 
#include 
#include 
using namespace std;
typedef long long ll;
ll a[4][300];
ll dp[300][300][300];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll col[4];
    cin>>col[1]>>col[2]>>col[3];
    for(int i=1; i<=3; i++){
        for(int j=1; j<=col[i]; j++)cin>>a[i][j];
    }
    ll ans=0;
    for(int i=1; i<=3; i++)sort(a[i]+1,a[i]+1+col[i]);
    for(int i=col[1]; ~i; i--){
        for(int j=col[2]; ~j; j--){
            for(int k=col[3]; ~k; k--){
                dp[i][j][k]=max(dp[i][j][k],dp[i+1][j+1][k]+(ll)a[1][i+1]*a[2][j+1]);//1,2
                dp[i][j][k]=max(dp[i][j][k],dp[i+1][j][k+1]+(ll)a[1][i+1]*a[3][k+1]);//1,3
                dp[i][j][k]=max(dp[i][j][k],dp[i][j+1][k+1]+(ll)a[3][k+1]*a[2][j+1]);//2,3
            }
        }
    }
    for(int i=col[1]; ~i; i--){
        for(int j=col[2]; ~j; j--){
            for(int k=col[3]; ~k; k--){
                ans=max(dp[i][j][k],ans);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}