2021-team4-C014

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

A k==2 没有判 卡了好久

H 读入反了 最后才发现

F 还不知道哪里错了

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define N 120050
#define MO 998244353
long double O,_O;
int a,b,t,O2[N],O3[N],p2[N],p3[N],n,T,Ans,_Ans,t2,t3;

#define D 25

struct node {
    int a, b;
    bool operator < (const node&g)const{
        if(b!=g.b)return b>g.b;
        return a>g.a;
    }
}A2[N],A3[N];

inline void upd(int &a, int b)
{
    a+=b;
    a%=MO;
}


void cal()
{
    int u2,u3;u2=u3=1;
    for(int i=1;i<n;++i){
        while(O2[u2]) ++u2;
        while(O3[u3]) ++u3;

        int op=n-i;
        int fl=0;
        if(n-i+1 <= D+3){
            fl=1;
        }

        if(u3>t3){
            upd(Ans,(long long)A2[u2].b*p2[op]%MO);
            if(fl)O+=(long double)A2[u2].b*pow(2,op);
            ++u2;
            continue;
        }
        if(u2>t2){
            upd(Ans,(long long)A3[u3].b*p3[op]%MO);
            if(fl)O+=(long double)A3[u3].b*pow(3,op);
            ++u3;
            continue;
        }
        if(n-i+1 >= D) {
            upd(Ans,(long long)A3[u3].b*p3[op]%MO);
            if(fl)O+=(long double)A3[u3].b*pow(3,op);
            ++u3;
            continue;
        }
        if(pow(2,n-i)*A2[u2].b > pow(3,n-i)*A3[u3].b){
            upd(Ans,(long long)A2[u2].b*p2[op]%MO);
            if(fl)O+=(long double)A2[u2].b*pow(2,op);
            ++u2;
        } else {
            upd(Ans,(long long)A3[u3].b*p3[op]%MO);
            if(fl)O+=(long double)A3[u3].b*pow(3,op);
            ++u3;
        }
    }
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);

    p2[0]=1;p3[0]=1;
    for(int i=1;i<=100500;++i){
        p2[i]=(long long)p2[i-1]*2%MO;
        p3[i]=(long long)p3[i-1]*3%MO;
    }

    cin >> T;
    while(T--){
        cin >> n; t2=t3=0;
        for(int i=1;i<=n;++i){
            cin >> a >> b >> t;
            if(t ==2 )A2[++t2].a=a,A2[t2].b=b;
                else A3[++t3].a=a,A3[t3].b=b;
        }
        sort(A2+1,A2+t2+1); // ->xiao
        sort(A3+1,A3+t3+1);

        _O=0; _Ans=0;

        //u2
        for(int i=max(t2-D,1ll);i<=t2;++i){
            O2[i]=1;

            O = A2[i].a;

            Ans=A2[i].a;
            cal();

            if(O > _O){
                _O=O;
                _Ans=Ans;
            }

            O2[i]=0;

        }
        //u3
        for(int i=max(t3-(D-t2)+1,1ll);i<=t3;++i){
            O3[i]=1;

            O = A3[i].a;
            Ans=A3[i].a;
            cal();
            if(O > _O){
                _O=O;
                _Ans=Ans;
            }
            O3[i]=0;
        }

        if(T)cout<<_Ans<<'\n';
        else cout<<_Ans;
    }

}
/*
1
3
1 1 2
2 2 2
1 1 3
*/

A k==2 没有判 卡了好久

H 读入反了 最后才发现

F 还不知道哪里错了

#include

using namespace std;

#define int long long

#define N 120050

#define MO 998244353

long double O,_O;

int a,b,t,O2[N],O3[N],p2[N],p3[N],n,T,Ans,_Ans,t2,t3;

#define D 25

struct node {

int a, b;

bool operator < (const node&g)const{

if(b!=g.b)return b>g.b;

return a>g.a;

}

}A2[N],A3[N];

inline void upd(int &a, int b)

{

a+=b;

a%=MO;

}

void cal()

{

int u2,u3;u2=u3=1;

for(int i=1;i

while(O2[u2]) ++u2;

while(O3[u3]) ++u3;

int op=n-i;

int fl=0;

if(n-i+1 <= D+3){

fl=1;

}

if(u3>t3){

upd(Ans,(long long)A2[u2].b*p2[op]%MO);

if(fl)O+=(long double)A2[u2].b*pow(2,op);

++u2;

continue;

}

if(u2>t2){

upd(Ans,(long long)A3[u3].b*p3[op]%MO);

if(fl)O+=(long double)A3[u3].b*pow(3,op);

++u3;

continue;

}

if(n-i+1 >= D) {

upd(Ans,(long long)A3[u3].b*p3[op]%MO);

if(fl)O+=(long double)A3[u3].b*pow(3,op);

++u3;

continue;

}

if(pow(2,n-i)*A2[u2].b > pow(3,n-i)*A3[u3].b){

upd(Ans,(long long)A2[u2].b*p2[op]%MO);

if(fl)O+=(long double)A2[u2].b*pow(2,op);

++u2;

} else {

upd(Ans,(long long)A3[u3].b*p3[op]%MO);

if(fl)O+=(long double)A3[u3].b*pow(3,op);

++u3;

}

}

}

signed main()

{

cin.tie(0)->sync_with_stdio(0);

p2[0]=1;p3[0]=1;

for(int i=1;i<=100500;++i){

p2[i]=(long long)p2[i-1]*2%MO;

p3[i]=(long long)p3[i-1]*3%MO;

}

cin >> T;

while(T--){

cin >> n; t2=t3=0;

for(int i=1;i<=n;++i){

cin >> a >> b >> t;

if(t ==2 )A2[++t2].a=a,A2[t2].b=b;

else A3[++t3].a=a,A3[t3].b=b;

}

sort(A2+1,A2+t2+1); // ->xiao

sort(A3+1,A3+t3+1);

_O=0; _Ans=0;

//u2

for(int i=max(t2-D,1ll);i<=t2;++i){

O2[i]=1;

O = A2[i].a;

Ans=A2[i].a;

cal();

if(O > _O){

_O=O;

_Ans=Ans;

}

O2[i]=0;

}

//u3

for(int i=max(t3-(D-t2)+1,1ll);i<=t3;++i){

O3[i]=1;

O = A3[i].a;

Ans=A3[i].a;

cal();

if(O > _O){

_O=O;

_Ans=Ans;

}

O3[i]=0;

}

if(T)cout<<_Ans<<'\n';

else cout<<_Ans;

}

}

/*

1

3

1 1 2

2 2 2

1 1 3

*/