概要

不算难，但是简单模拟没写对

题目

T1

随便模拟一下就行，怎么也不会 T。

#include<bits/stdc++.h>
using namespace std;
int n,t,x=1,y=1;
int main()
{
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
    cin>>n>>t;
    for(int i=1;i<=t;i++)
    {
        y++;
        if(y>n)
        {
            x++;
            y=1;
        }
        if(x>n)
        {
            x=1;
            y=1;
        }
    }
    cout<<x<<" "<<y<<"\n";
    return 0;
}

T2

贪心

• 如果赔本就不选
• 否则按代价升序，如果当前选不了就可以直接 break

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n;
LL ans;
struct node
{
    LL val,uval,jval;
}a[100010];
bool cmp(node s1,node s2)
{
    if(s1.jval>0 && s2.jval>0)
    {
        return s1.uval<s2.uval;
    }
    return s1.jval>s2.jval;
}
int main()
{
    freopen("collect.in","r",stdin);
    freopen("collect.out","w",stdout);
    scanf("%d%lld",&n,&ans);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&a[i].val,&a[i].uval);
        a[i].jval=a[i].val-a[i].uval;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        if(ans<a[i].uval)
        {
            break;
        }
        if(a[i].jval<=0)
        {
            break;
        }
        ans+=a[i].jval;
    }
    printf("%lld\n",ans);
    return 0;
}

T3

根据题意模拟即可

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int id,gz,y;
    char work;
    string name;
}a[30];
struct cnode
{
    string name;
    int id,gz,y,iid;
    char work;
}b[30];
string tnc,q,master;
int p[10],cnt=2,team_boss_id;
bool cmp1(node s1,node s2)
{
    if(s1.gz==s2.gz)
    {
        return s1.id<s2.id;
    }
    return s1.gz<s2.gz;
}
bool cmp2(cnode s1,cnode s2)
{
    if(s1.iid==team_boss_id)
    {
        return 1;
    }
    if(s2.iid==team_boss_id)
    {
        return 0;
    }
    if(s1.gz==s2.gz)
    {
        return s1.id<s2.id;
    }
    return s1.gz<s2.gz;
}
int main()
{
    freopen("footballteam.in","r",stdin);
    freopen("footballteam.out","w",stdout);
    for(int i=1;i<=22;i++)
    {
        cin>>a[i].id>>a[i].name>>a[i].work;
        getline(cin,tnc);
        //cerr<<"READ IS OK\n";
        int st=0,ed=0;
        for(int j=0;j<tnc.size();)
        {
            if(tnc[j]==' ')
            {
                a[i].y+=(ed-st+1);
                ed=0,st=0;
                j++;
            }
            else if(tnc[j]>='0' && tnc[j]<='9')
            {
                st=(tnc[j]-48)*1000+(tnc[++j]-48)*100+(tnc[++j]-48)*10+(tnc[++j]-48);
                j++;
            }
            else if(tnc[j]=='-')
            {
                ed=(tnc[++j]-48)*1000+(tnc[++j]-48)*100+(tnc[++j]-48)*10+(tnc[++j]-48);
                j++;
            }
        }
        a[i].y+=(ed-st+1);
        cerr<<ed<<" "<<st<<" ";
        cerr<<a[i].y<<"\n";
        if(a[i].work=='S')
        {
            a[i].gz=4;
        }
        else if(a[i].work=='M')
        {
            a[i].gz=3;
        }
        else if(a[i].work=='D')
        {
            a[i].gz=2;
        }
        else if(a[i].work=='G')
        {
            a[i].gz=1;
        }
    }
    sort(a+1,a+1+22,cmp1);
    cin>>q;
    for(int i=0;i<q.size();i++)
    {
        if(q[i]=='-')
        {
            cnt++;
        }
        else
        {
            p[cnt]=p[cnt]*10+(q[i]-48);
        }
    }
    cnt=0;
    p[1]=1;
    b[0].id=0;
    b[0].y=0; 
    for(int i=1;i<=22;i++)
    {
        if(p[a[i].gz]>0)
        {
            b[++cnt].id=a[i].id;
            b[cnt].iid=cnt;
            b[cnt].name=a[i].name;
            b[cnt].work=a[i].work;
            b[cnt].gz=a[i].gz;
            b[cnt].y=a[i].y;
            if(b[team_boss_id].y<b[cnt].y || (b[team_boss_id].y<=b[cnt].y && b[cnt].id>b[team_boss_id].id))
            {
                team_boss_id=cnt;
            }
            p[a[i].gz]--;
        }
    }
    if(cnt!=11)
    {
        //cerr<<"CNT="<<cnt<<"\n";
        puts("IMPOSSIBLE TO ARRANGE");
        return 0;
    }
    sort(b+1,b+1+cnt,cmp2);
    for(int i=1;i<=cnt;i++)
    {
        cout<<b[i].id<<" "<<b[i].name<<" "<<b[i].work<<"\n";
    }
    return 0;
}

T4

此为 $\texttt{DP}$ 也，可是我不会。

用贪心也能过。

观察发现无非就是 小-大-小-大……

或 大-小-大-小（相比于相邻的）

如果不符合就累加并修改为极值

#include<bits/stdc++.h>
#define TBH 2147483646
#define small 1
#define big 2
using namespace std;
int ans,a[100010],n,b[100010];
int c1()
{
    int cnt=0;
    a[n+1]=-1919810;
    for(int i=2;i<=n;i+=2)
    {
        if(a[i]<=a[i+1] && a[i]<=a[i-1])
        {
            cnt++;
            a[i]=TBH;
        }
        else if(a[i]<=a[i+1])
        {
            cnt++;
            a[i+1]=-114514;
        }
        else if(a[i]<=a[i-1])
        {
            cnt++;
            a[i-1]=-114514;
        }
    }
    return cnt;
}
int c2()
{
    int cnt=0;
    a[n+1]=2147483647;
    for(int i=2;i<=n;i+=2)
    {
        if(a[i]>=a[i+1] && a[i]>=a[i-1])
        {
            cnt++;
            a[i]=-114514;
        }
        else if(a[i]>=a[i+1])
        {
            cnt++;
            a[i+1]=TBH;
        }
        else if(a[i]>=a[i-1])
        {
            cnt++;
            a[i-1]=TBH;
        }
    }
    return cnt;
}
int main()
{
    freopen("wave.in","r",stdin);
    freopen("wave.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    if(n<=2)
    {
        puts("0");
        return 0;
    }
    if(n==3)
    {
        if((a[2]>a[3] && a[2]>a[1]) || (a[2]<a[3] && a[2]<a[1]))
        {
            puts("0");
        }
        puts("1");
        return 0;
    }
    int a1=c1();
    for(int i=1;i<=n;i++)
    {
        a[i]=b[i];
    }
    int a2=c2();
    ans=min(a1,a2);
    cout<<ans<<"\n";
    return 0;
}