2016 Multi-University Training Contest 2

直接队友代码

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <sstream>
 5 #include <string>
 6 #include <algorithm>
 7 #include <list>
 8 #include <map>
 9 #include <vector>
10 #include <queue>
11 #include <stack>
12 #include <cmath>
13 #include <cstdlib>
14 using namespace std;
15 long long a[100006];
16 int main()
17 {
18     //freopen("in.txt","r",stdin);
19     int T;
20     scanf("%d",&T);
21     while(T--)
22     {
23         long long p = 0,q;
24         memset(a,0,sizeof(a));
25         int n;
26         long long sum = 0;
27         long long sum2 = 0;
28         scanf("%d",&n);
29         for(int i = 0; i < n; i ++)
30         {
31             scanf("%I64d",&a[i]);
32             if(a[i] < 0)
33                 a[i] = -a[i];
34             sum += a[i];
35             sum2 += a[i] * a[i];
36         }
37     sum = sum * sum;
38         p = sum2* n- sum;
39 
40         q = n;
41         int temp = __gcd(p,q);
42         p = p / temp;
43         q  = q/ temp;
44         printf("%I64d/%I64d
",p,q);
45 
46     }
47     return 0;
48 }

View Code

5724 It's All In The Mind

水

 1 // #pragma comment(linker, "/STACK:102c000000,102c000000")
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <sstream>
 6 #include <string>
 7 #include <algorithm>
 8 #include <list>
 9 #include <map>
10 #include <vector>
11 #include <queue>
12 #include <stack>
13 #include <cmath>
14 #include <cstdlib>
15 // #include <conio.h>
16 using namespace std;
17 #define clc(a,b) memset(a,b,sizeof(a))
18 #define inf 0x3f3f3f3f
19 #define lson l,mid,rt<<1
20 #define rson mid+1,r,rt<<1|1
21 const int N = 1e5+10;
22 const int M = 1e6+10;
23 const int MOD = 1e9+7;
24 #define LL long long
25 #define mi() (l+r)>>1
26 double const pi = acos(-1);
27 
28 void fre() {
29     freopen("in.txt","r",stdin);
30 }
31 
32 // inline int r() {
33 //     int x=0,f=1;char ch=getchar();
34 //     while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
35 //     while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;
36 // }
37 
38 int a[110];
39 int main(){
40     int T;
41     scanf("%d",&T);
42     while(T--){
43         clc(a,0);
44         int n,m;
45         scanf("%d%d",&n,&m);
46         int sum=0;
47         int last=2;
48         for(int i=0;i<m;i++){
49             int pos;
50             scanf("%d",&pos);
51             scanf("%d",&a[pos]);
52             if(pos==1||pos==2){
53                 sum+=a[pos];
54                 continue;
55             }
56             int len=pos-last;
57             sum+=len*a[pos];
58             last=pos;
59         }
60         // cout<<sum<<endl;
61         if(!a[1]) a[1]=100,sum+=100;
62         if(!a[2]) a[2]=a[1],sum+=a[2];
63         // cout<<sum<<endl;
64         int g=__gcd(sum,a[1]+a[2]);
65         printf("%d/%d
",(a[1]+a[2])/g,sum/g);
66     }
67     return 0;
68 }

View Code

5745 La Vie en rose

题意有好难理解，其实就是只能交换相邻字符且一次

队友代码

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <queue>
 7 #include <set>
 8 #include <map>
 9 #include <string>
10 #include <cmath>
11 #include <stdlib.h>
12 using namespace std;
13 typedef long long LL;
14 const int inf=0x3f3f3f3f;
15 const int N=1e5+10;
16 char s1[N],s2[5010];
17 bool ans[N];
18 int main()
19 {
20     //freopen("in.txt","r",stdin);
21     int t,n,m;
22     scanf("%d",&t);
23     while(t--)
24     {
25         scanf("%d%d",&n,&m);
26         scanf("%s%s",s1,s2);
27         memset(ans,0,sizeof(ans));
28         for(int i=0;i<n;i++)
29         {
30             int p=i,j;
31             for(j=0;j<m;j++)
32             {
33                 if(s1[p+j]==s2[j]) continue;
34                 if(s1[p+j]==s2[j+1]&&s1[p+j+1]==s2[j]) j++;
35                 else break;
36             }
37             if(j>=m) ans[i]=1;
38         }
39         for(int i=0;i<n;i++)
40             printf("%d",ans[i]);
41         printf("
");
42     }
43     return 0;
44 }

View Code

5744 Keep On Movin

把一堆字母分成多组回文串，求每组里面最短的最长

水

 1 // #pragma comment(linker, "/STACK:102c000000,102c000000")
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <sstream>
 6 #include <string>
 7 #include <algorithm>
 8 #include <list>
 9 #include <map>
10 #include <vector>
11 #include <queue>
12 #include <stack>
13 #include <cmath>
14 #include <cstdlib>
15 // #include <conio.h>
16 using namespace std;
17 #define clc(a,b) memset(a,b,sizeof(a))
18 #define inf 0x3f3f3f3f
19 #define lson l,mid,rt<<1
20 #define rson mid+1,r,rt<<1|1
21 const int N = 1e5+10;
22 const int M = 1e6+10;
23 const int MOD = 1e9+7;
24 #define LL long long
25 #define mi() (l+r)>>1
26 double const pi = acos(-1);
27 
28 void fre() {
29     freopen("in.txt","r",stdin);
30 }
31 
32 // inline int r() {
33 //     int x=0,f=1;char ch=getchar();
34 //     while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
35 //     while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;
36 // }
37 
38 int main(){
39     // fre();
40     int T;
41     int n;
42     scanf("%d",&T);
43     while(T--){
44         scanf("%d",&n);
45         int num=0,cnt=0;
46         LL sum=0;
47         for(int i=0;i<n;i++){
48             int x;
49             scanf("%d",&x);
50             sum+=x;
51             if(x&1){
52                num++;
53                cnt+=x/2;
54             }
55             else
56                cnt+=x/2;
57         }
58         if(num==0){
59             printf("%I64d
",sum);
60             continue;
61         }
62         int ans;
63         ans=1+cnt/num*2;
64         printf("%d
",ans);
65     }
66     return 0;
67 }

View Code

5738 Eureka

题意：求多少个子集共线

思路：先按x，y排序个。从左边开始枚举每个点当作起点，统计右边有多少个共线的子集。用极坐标排序，但是判断点共线的时候把斜率转换成相乘的形式。

有n个点和i共线的话，那么子集为2^n-1,注意重点的情况会多算d-1次

 1 // #pragma comment(linker, "/STACK:102c000000,102c000000")
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <sstream>
 6 #include <string>
 7 #include <algorithm>
 8 #include <list>
 9 #include <map>
10 #include <vector>
11 #include <queue>
12 #include <stack>
13 #include <cmath>
14 #include <cstdlib>
15 // #include <conio.h>
16 using namespace std;
17 #define clc(a,b) memset(a,b,sizeof(a))
18 #define inf 0x3f3f3f3f
19 #define lson l,mid,rt<<1
20 #define rson mid+1,r,rt<<1|1
21 const int N = 1e5+10;
22 const int M = 1e6+10;
23 const int MOD = 1e9+7;
24 #define LL long long
25 #define mi() (l+r)>>1
26 double const pi = acos(-1);
27 const double eps = 1e-8;
28 void fre() {
29     freopen("in.txt","r",stdin);
30 }
31 
32 // inline int r() {
33 //     int x=0,f=1;char ch=getchar();
34 //     while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
35 //     while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;
36 // }
37 
38 struct Point{
39     int x,y;
40     double ang;
41 }p[1010],p2[1010];
42 
43 bool cmp(Point a,Point b){
44     if(a.y==b.y) return a.x<b.x;
45     return a.y<b.y;
46 }
47 
48 bool cmp2(Point a,Point b){
49     return a.ang<b.ang;
50 }
51 int f[1010];
52 int main(){
53     // fre();
54     f[0]=1;
55     for(int i=1;i<1005;i++){
56         f[i]=(f[i-1]*2)%MOD;
57     }
58     int T;
59     scanf("%d",&T);
60     while(T--){
61         int n;
62         scanf("%d",&n);
63         for(int i=1;i<=n;i++){
64             scanf("%d%d",&p[i].x,&p[i].y);
65         }
66         LL ans=0;
67         sort(p+1,p+1+n,cmp);
68         for(int i=1;i<n;i++){
69             int s=0,cnt=0;
70             for(int j=i+1;j<=n;j++){
71                 if(p[j].x==p[i].x&&p[j].y==p[i].y) {s++;continue;}
72                 p2[++cnt].ang=atan2(p[j].y-p[i].y,p[j].x-p[i].x);
73                 p2[cnt].x=p[j].x;
74                 p2[cnt].y=p[j].y; 
75             }
76             sort(p2+1,p2+1+cnt,cmp2);
77             int k,d=0; 
78             for(int j=1;j<=cnt;){
79                 int num=s+1;
80                 for(k=j+1;k<=cnt;k++){
81                     if((p2[k].y-p2[j].y)*(p2[j].x-p[i].x)!=(p2[j].y-p[i].y)*(p2[k].x-p2[j].x)) break;
82                         num++;
83                 }
84                 j=k;
85                 d++;
86                 ans=(ans+f[num]-1)%MOD;
87             }
88             ans=(ans-(LL)(d-1)*(f[s]-1)%MOD+MOD)%MOD;
89         }
90         printf("%I64d
",ans);
91     }
92     return 0;
93 }

View Code