1001 SDOI
简单模拟

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m;
typedef struct Node{
    char name[30];
    int sex;
    double s1,s2;
}Node;
Node node[110];
bool cmp(Node a,Node b)
{
    return a.s1>b.s1;
}
int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        char s[10];
        int s1,s2;
        bool flag=0;
        double max1=0,max2=0;
        for(i=1;i<=n;i++)
        {
            scanf("%s%s%lf%lf",node[i].name,s,&node[i].s1,&node[i].s2);
            if(node[i].s1>max1) max1=node[i].s1;
            if(node[i].s2>max2) max2=node[i].s2;
            if(!strcmp(s,"male")) node[i].sex=1;
            else {node[i].sex=0;flag=1;}
        }
        for(i=1;i<=n;i++)
        {
            node[i].s1=node[i].s1*(300*1.0/max1)*0.3+node[i].s2*(300*1.0/max2)*0.7;
        }
        sort(node+1,node+1+n,cmp);
        printf("The member list of Shandong team is as follows:\n");
        if(!flag)
        {
            for(i=1;i<=m;i++)
                printf("%s\n",node[i].name);
            continue;
        }
        int male=0,total=0;
        for(i=1;i<=n;i++)
        {
            int sex=node[i].sex;
            if(total<m)
            {
                if(sex)
                {
                    if(male<m-1)
                    {
                        printf("%s\n",node[i].name);
                        male++;
                        total++;
                    }
                }
                else
                {
                        printf("%s\n",node[i].name);
                        total++;
                }
            }
        }
    }
    return 0;
}

1002 Reorder the Books
题意：给出1-n的一个乱序排列，每次操作只能抽出一个放到开头，请问最少操作几次可以使序列有序。
这题想通了很简单。
我们可以得到以下两个简单结论：
1.抽出数字x放到开头不会改变数字a和数字b的相对顺序(a、b不同于x)
2.当抽出数字x放到开头时显然以后一定要把比x小的数字1，2,3，……,x-1抽出放到开头一次（基于第一点,他们的相对顺序是错误的，但是移动其他元素不能改变他们的相对顺序）。
那么显然我们希望这个x越小越好。
由于从最大数字n为结尾的相对顺序正确的几个数不需要移动，所以x其实就是从n开始往回看的第一个顺序错误的数。
考虑以下情况：3,1,4,2,5
由于3,4,5三个数字相对顺序是正确的，所以x就是2，我们第一次将2放到开头，第二次将1放到开头就行。（显然上面的第二点指出比2小的数字一定至少移动一次，然后，我们可以发现，它们事实上只需要移动一次就可以使未被移动的那些数字连续且有序）
我发现有些想法大脑里过一遍是是快速而跳跃的，但是要通俗易懂地写出来且在逻辑上很严格会很麻烦。。。

#include<stdio.h>
#include<string.h>
int a[30],pos[30];
int main()
{
    int i,j;
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            pos[a[i]]=i;
        }
        int ans=1;
        for(i=n;i>=2;i--)
        {
            if(pos[i]>pos[i-1]) ans++;
            else break;

        }
        printf("%d\n",n-ans);
    }

    return 0;
}

1003 The Highest Mark
这题比赛时没做出来，特么为什么我现在这么菜！（好吧，其实以前也很菜）
题意：n个题目原始分数ai,每分钟减少bi（从比赛开始算起），完成需要ci，问t分钟最多可以得到几分（从中选择一些题目做）
n<=1000,t<=3000
如果没有bi这个量，那么这题就是一个0/1背包。
假设现在顺序已经确定，那么

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef struct Node{
    int a,b,c;
}Node;
Node node[1010];
int n,m;
int t;
bool cmp(Node x,Node y)
{
    return (ll)x.b*(ll)y.c>(ll)y.b*(ll)x.c;
}
inline int max(int a,int b){return a>b?a:b;}
int dp[3010];
int main()
{
    int i,j,T;
    scanf("%d",&t);
    while(t–)
    {
        scanf("%d%d",&n,&T);
        for(i=1;i<=n;i++)
            scanf("%d%d%d",&node[i].a,&node[i].b,&node[i].c);
        sort(node+1,node+1+n,cmp);
        //for(i=1;i<=n;i++)
            //printf("%d  %d  %d\n",node[i].a,node[i].b,node[i].c);
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++)
            for(j=T;j>=0;j–)
            {
                if(node[i].c>j) continue;
                dp[j]=max(dp[j],dp[j-node[i].c]+node[i].a-node[i].b*j);
            }
        int ans=0;
        for(j=1;j<=T;j++) ans=max(ans,dp[j]);
        printf("%d\n",ans);

    }
    return 0;
}

1004 Candy Game