前言

今天题目比较水and我进了C组，不过太太太太太太太太太太太太太太太太绝望了QAQ。所以我也没有做C组的题。写完博客我就做O(∩_∩)O。

正题

---

题1：奇数统计（jzoj1547）

就是输入n个数，输出出现次数为奇数的一个数（只有一个）。

---

输入

第一行是N，下一行有N个正整数。

输出

出现了奇数次的数。

样例输入

9

3 1 2 2 17 1 3 17 3

样例输出

3

---

桶不解释

---

代码

#include
    
     #include
     
      using namespace std;int n,a[10001],x,ans;int main(){    //freopen("count.in","r",stdin);    //freopen("count.out","w",stdout);    scanf("%d",&n);    for (int i=1;i<=n;i++)    {        scanf("%d",&x);        a[x]++;    }       for (int i=1;i<=10000;i++) if (a[i]%2==1) {
   printf("%d",i);return 0;}}
     
    

相信我不加批注你们也懂不O(∩_∩)O

---

题2：有理逼近（jzoj1548）

---

输入

输入文件的第一行为P、N，其中 P、N<30000。

输出

输出文件只有一行，格式为“X/Y U/V”。注意，答案必须是既约的，也就是说分子、分母的最大公约数必须等于1。

样例输入

2 5

样例输出

4/3 3/2

---

暴枚好像会超时，所以我们先枚举分子，然后从中间开始向两边扩展的搜分母。

在这里感谢朋友提供思路，这里是他的博客：

---

代码

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;double p,s1,s2,ss1,ss2,j,k;int w,n,u;int main(){    //freopen("rational.in","r",stdin);    //freopen("rational.out","w",stdout);    scanf("%d%d",&w,&n);    p=sqrt(w);//开方    u=n/p;//确定中间值    s1=-214748364;s2=1;ss1=214748364;ss2=1;//初始化    for (double i=1;i<=n;i++)    {        j=u;k=0;        while (j+k<=n && j-k>=1){            if (p-i/(j+k)>0 && p-i/(j+k)
        
         0 && p-i/(j-k)
         
          0 && i/(j+k)-p
          
           0 && i/(j-k)-p
          
         
        
       
      
     
    

---

题目3：活动安排（jzoj1549）

有n （n<=100） 个活动，每个活动开始时间si，结束时间fi。每个活动需要一个会场，求需要的最小会场数。水题。

---

输入

第一行是活动数n（1≤n≤100）。

以后的n行，每行两个整数，分别表示n个活动的开始时间si和结束时间fi(1≤i≤n)，si

输出

一个整数，表示需要的最少会场数。

样例输入

4

1 8

2 5

7 15

5 9

样例输出

3

---

判断当前有没有空的会场，如果有就把活动安排进去，不然就开一个新的。

---

代码

#include
    
     using namespace std;int s[101],f[101],n,t,w,wf[101];int main(){    //freopen("meet.in","r",stdin);    //freopen("meet.out","w",stdout);    scanf("%d",&n);    for (int i=1;i<=n;i++) scanf("%d%d",&s[i],&f[i]);    for (int i=1;i
     
      s[j])        {            t=s[i];            s[i]=s[j];            s[j]=t;            t=f[i];            f[i]=f[j];            f[j]=t;        }//看我连快排都懒得用了    for (int i=1;i<=n;i++)    {        for (int j=1;j<=w;j++)          if (s[i]>=wf[j])//有空会场          {            wf[j]=f[i];            f[i]=-1;            break;          }        if (f[i]!=-1)//安排新会场        {            w++;            wf[w]=f[i];//活动结束时间        }    }    printf("%d",w);//输出}
     
    

---

题目4：最小步数（jzoj1550）

一条路长n，每走到一个格会获得Ai元（-10000<=Ai<=10000），你也可以选择花100元跳过该格，金币不可以为负数。求到终点最小的步数

---

输入

共有两行。

第一行为整数N（0<=N<=100）。

第二行有N个整数，第K个数为A[K]，-10000<=A[K]<=10000，。

输出

一个整数，表示需要走的最少步数。若无法走到终点，输出-1。

样例输入

6

30 30 30 30 30 30

样例输出

5

---

这里dp，其实记搜也可以过（不过不重要）。然后用f[i][j]来表示到达第i格用j步并且最后一步是跳过的最大金币，然后用f[i][j]来表示到达第i格用j步并且最后一步是走过的最大金币。

动态转移方程：f[i][j]=max(f[i-1][j],f2[i-1][j])-100 （跳过该步）

f2[i][j]=max(f[i-1][j-1],f2[i-1][j-1])+a[i] （走过该步）

---

代码

#include
    
     #include
     
      using namespace std;int a[101],f[101][101],n,ans,f2[101][101];int main(){    //freopen("steps.in","r",stdin);    //freopen("steps.out","w",stdout);    scanf("%d",&n);    for (int i=1;i<=n;i++)    {        scanf("%d",&a[i]);    }       for (int i=1;i<=n;i++)      for (int j=0;j<=i;j++) {f2[i][j]=-214748364;f[i][j]=-214748364;}//初始化     for (int i=1;i<=n;i++)    {        for (int j=1;j<=i;j++)        {            if (max(f[i-1][j],f2[i-1][j])-100>=0 && i!=n) f[i][j]=max(f[i-1][j],f2[i-1][j])-100;//跳            if (max(f[i-1][j-1],f2[i-1][j-1])+a[i]>=0) f2[i][j]=max(f[i-1][j-1],f2[i-1][j-1])+a[i];//走        }    }    for (int i=0;i<=n;i++) if (f2[n][i]>=0) {
   printf("%d",i);return 0;}//查找    printf("-1");//不能到达}