A. Subsequence Permutation

 题意：水

 

B. Running for Gold

 题意：有n个运动员都参加了五场比赛，定义一个运动员比另一个运动员强当他有大于等于3次比赛的名次在另一位之前；定义比除自己以外所有在场运动员都强的运动员为冠军，询问当前的n个运动员中是否存在冠军，如存在，则输出其中任意一个的下标。

思路：先假设冠军存在且为第一位运动员，扫一遍观察后一位运动员是否强于当前的“冠军”，如果后一位更强，则更新“冠军”为后一位。这样在扫完一遍后保证得到的“冠军”一定是能战胜人数最多的，重新扫一遍统计有没有人能战胜他，如有，则不存在冠军，如无，则他就是冠军（做的时候犯病了，写了个假贪心还加了离散化）

代码：

ll a[N][6],b[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    //IO
    cin>>t;
    while(t--)
    {
        cin>>n;
        ll ans=1;
        rep(i,1,n)rep(j,1,5)cin>>a[i][j];
        rep(i,2,n)
        {
            ll sum=0;
            rep(j,1,5)
            {
                if(a[i][j]<a[ans][j])sum++;
            }
            if(sum>=3)ans=i;
        }
        rep(i,1,n)
        {
            if(i==ans)continue;
            ll sum=0;
            rep(j,1,5)
            {
                if(a[i][j]<a[ans][j])sum++;
            }
            if(sum>=3)
            {
                ans=-1;
                break;
            }
        }
        cout<<ans<<endl;
    }
}

View Code C. Maximize the Intersections

 题意：给定一个有2*n个点的圆，点均匀分布在圆的边上且按顺时针排列，给定k条确定的弦，连接剩下的2*(n-k)个点，统计可能园内可能得到的交点的最大值。

思路：观察易得在所有可选点中，连接距离最大点的交点最多。

代码：

ll a[N],b[N],vis[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    //IO
    cin>>t;
    while(t--)
    {
        vector<pll>A;
        cin>>n>>k;
        tt=0;
        rep(i,1,2*n)vis[i]=0;
        rep(i,1,k)
        {
            ll x,y;
            cin>>x>>y;
            if(x>y)swap(x,y);
            vis[x]=vis[y]=1;
            A.pb({x,y});
        }
        if(n!=k)
        {
            vector<ll>xx;
            rep(i,1,2*n)
            {
                if(!vis[i])
                {
                    xx.pb(i);
                }
            }
            sort(xx.begin(),xx.end());
            rep(i,0,xx.size()/2-1)
            {
                A.pb({xx[i],xx[xx.size()/2+i]});
            }
        }
        ans=0;
        sort(A.begin(),A.end());
        for(ll i=0;i<A.size();i++)
        {
            ll x=A[i].ft,y=A[i].sd;
            for(ll j=i+1;j<A.size();j++)
            {
                ll xx=A[j].ft,yy=A[j].sd;
                if(xx>y)break;
                if(yy>y)ans++;
            }
        }
        cout<<ans<<endl;
    }
}

View Code D. Array Differentiation

 题意：给定长为n的数组a，问能否构造一个等长的数组b使得对于ai有bj-bk=ai(1<=i<=n,1<=j,k<=n)

思路：见代码

代码：

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    //IO
    cin>>t;
    while(t--)
    {
        cin>>n;
        rep(i,1,n)cin>>a[i];
        ll temp=1,flag=0;
        rep(i,1,n)temp*=3;
        rep(i,1,temp-1)
        {
            ll cnt=i,sum=0;
            rep(j,1,n)
            {
                ll kk=cnt%3;
                cnt/=3;
                if(kk==2)kk-=3;
                sum+=kk*a[j];
            }
            if(sum==0)
            {
                flag=1;
                break;
            }
        }
        if(flag)yes;
        else no;
    }
}

View Code