2013 Multi-University Training Contest 6 部分解题报告

problem 1001（hdu 4655）

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4655

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 #define mm 1000000007
 6 int a[1000001];
 7 int b[1000001];
 8 __int64 x[1000001];
 9 __int64 mmax(__int64 x,__int64 y)
10 {
11     if(x>y)
12     return x;
13     else
14     return y;
15 }
16 __int64 mmin(__int64 x,__int64 y)
17 {
18     if(x<y)
19     return x;
20     else
21     return y;
22 }
23 __int64 jisuan(int n)
24 {
25     int i;
26     __int64 sum;
27     x[0]=1;
28     x[1]=a[0];
29     for(i=2;i<n;i++)x[i]=x[i-1]*a[i-1],x[i]%=mm;
30     sum=a[0];
31     for(i=1;i<n;i++)
32     {
33         sum=(sum%mm)*(a[i]%mm)+((((mmax(a[i],a[i-1])-1)*mmin(a[i],a[i-1]))%mm)*x[i-1])%mm;
34         sum%=mm;
35     }
36     return sum;
37 }
38 int main()
39 {
40     int T,i,n;
41     scanf("%d",&T);
42     while(T--)
43     {
44         scanf("%d",&n);
45         for(i=0;i<n;i++)
46         {
47             scanf("%d",&a[i]);
48             b[i]=a[i];
49         }
50         sort(b,b+n);
51         if(n%2==1)
52         {
53             for(i=0;i<n;i++)
54             {
55                 if(i%2==0)a[i]=b[i/2];
56                 else a[i]=b[n/2+i/2+1];
57             }
58         }
59         else
60         {
61             a[0]=b[0];
62             a[1]=b[n/2];
63             a[2]=b[n/2+1];
64             for(i=3;i<n;i++)
65             {
66                 if(i%2==1)
67                 a[i]=b[i/2];
68                 else a[i]=b[n/2+i/2];
69             }
70         }
71         printf("%I64d
",jisuan(n));
72     }
73     return 0;
74 }

View Code

problem 1008（hdu 4662）

题目：http://acm.hdu.edu.cn/showproblem.php?pid=4662

MU Puzzle

思路：统计I的个数，一个U代表3个I，最后的总数若是二的倍数而不是3的倍数，那么就是yes

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn=100010;
 6 char str[maxn];
 7 int main()
 8 {
 9 
10     int n;
11     scanf("%d",&n);
12     int i;
13     for(i=0; i<n; i++)
14     {
15         getchar();
16         scanf("%s",str);
17         int len=strlen(str);
18         int j;
19         int flag=1;
20         int num=0;
21         if(str[0]=='M')
22         {
23             for(j=1; j<len; j++)
24             {
25                 if(str[j]=='M')
26                 {
27                     flag=0;
28                     break;
29                 }
30                 else if(str[j]=='I')
31                 {
32                     num+=1;
33                 }
34                 else
35                 num+=3;
36             }
37             if(flag==0)
38             printf("No
");
39             else if(num==1||num==2)
40             printf("Yes
");
41             else if(num%2==0&&num%3!=0)
42             printf("Yes
");
43             else
44             printf("No
");
45         }
46         else
47         printf("No
");
48 
49     }
50     return 0;
51 }

View Code