2014省赛回顾

题目链接：1058--1067

http://xcacm.hfut.edu.cn/problemset.php#

省赛题其实并不难。。。练手速用。。。

1062：

感觉是先离散化，然后从点向上下左右四个方向发射线，看和边相交的次数

1063: 4min

 1 //4min
 2 
 3 #include <iostream>
 4 #include <algorithm>
 5 #include<cstdio>
 6 using namespace std;
 7 int N,t;
 8 double ans;
 9 double a[10010];
10 
11 int main()
12 {
13     while(cin>>N)
14     {
15         for (int i=0;i<N;i++)
16             cin>>a[i];
17 
18         sort(a,a+N);
19         //for (int i=0;i<N;i++)   cout<<a[i]<<" ";
20         t=N/2-1;
21         if (N%2!=0)
22             ans=a[t+1];
23         else
24             ans=(a[t]+a[t+1])/2;
25 
26         printf("%.2lf
",ans);
27     }
28 }

View Code

1064： 9min

 1 //9min
 2 
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 int n,m,k;
 7 int R[10000],C[10000];
 8 int main()
 9 {
10     while(cin>>n>>m>>k)
11     {
12         bool ok=false;
13         for (int i=1;i<=k;i++)
14             cin>>R[i]>>C[i];
15         for (int i=1;i<=k-1;i++)
16             for (int j=i+1;j<=k;j++)
17             {
18                 int ri=R[i],ci=C[i],rj=R[j],cj=C[j];
19                 int rr=abs(ri-rj),cc=abs(ci-cj);
20                 if((rr==1)||(cc==1))
21                     ok=true;
22             }
23         if (ok) cout<<"YES"<<endl;  else  cout<<"NO"<<endl;
24     }
25     return 0;
26 }

View Code

1065: 24min

 1 //24min
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <vector>
 5 #include <cstring>
 6 using namespace std;
 7 
 8 string str;
 9 int n,q,mn;
10 int file[10100];
11 
12 int cmps(string a,string b)
13 {
14     int ans=0;
15     for (int i=0;i<36;i++)
16     {
17         char aa=a[i],bb=b[i];
18         if (aa!=bb)  ans++;
19         if (ans>mn)    return(1000010);
20     }
21     return ans;
22 }
23 
24 int main()
25 {
26     while(cin>>n)
27     {
28         vector<string>  NM;
29         vector<string>  HS;
30         for (int i=1;i<=n;i++)
31         {
32             cin>>str;
33             NM.push_back(str);
34             cin>>str;
35             HS.push_back(str);
36         }
37         cin>>q;
38         for (int ii=1;ii<=q;ii++)
39         {
40             cin>>str;
41             cin>>str;
42             int num=0;
43             mn=1000000;
44             for (int i=0;i<n;i++)
45             {
46                 string st=HS[i];
47                 int ans=cmps(str,st);
48                 //cout<<"comp:  "<<str<<" "<<st<<" , "<<ans<<endl;
49                 if (ans<mn)
50                 {
51                     num=1;
52                     mn=ans;
53                     file[num]=i;
54                 }
55                 else if (ans==mn)
56                 {
57                     num++;
58                     file[num]=i;
59                 }
60             }
61             cout<<num<<endl;
62             cout<<36-mn<<endl;
63             for (int i=1;i<=num;i++)
64                 cout<<NM[file[i]]<<endl;
65         }
66     }
67 
68 
69     return 0;
70 }

View Code

1066：40min

记得用那个优化：找[1,n]中满足i%p==0的i --> 枚举p的每个<=n的倍数

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cmath>
 5 using namespace std;
 6 #define MAXN 100010
 7 int np=0,n;
 8 int prime[MAXN],phi[MAXN];
 9 bool pr[MAXN];
10 long long ans;
11 
12 void isprime(int n)     //求1--n的质数。pr[i]=1 : i is a prime
13 {
14     memset(pr,true,sizeof(pr));
15     int m=sqrt(n+0.5);
16     pr[1]=false;
17     for (int i=2; i<=m; i++)
18         if (pr[i])
19         {
20             for (int j=i*i; j<=n; j+=i)
21                 pr[j]=false;
22         }
23     np=0;
24     for (int i=1; i<=n; i++)
25         if (pr[i])
26         {
27             np++;
28             prime[np]=i;
29         }
30 }
31 
32 void calc_phi(int n)        //求1--n的欧拉函数，phi[i]=φ(i)
33 {
34     for (int i=2; i<=n; i++)
35         phi[i]=0;
36     phi[1]=1;
37     for (int i=2; i<=n; i++)
38         if (!phi[i])
39             for (int j=i; j<=n; j+=i)
40             {
41                 if (!phi[j])    phi[j]=j;
42                 phi[j]=phi[j]/i*(i-1);
43             }
44 }
45 
46 int main()
47 {
48     isprime(100000);
49     calc_phi(100000);
50 
51     //cout<<np<<endl;
52 
53     while(cin>>n)
54     {
55         ans=0;
56 
57         for (int i=1;i<=np;i++)
58         {
59             int prm=prime[i];
60             if (prm<=n) ans++;
61             int j=2;
62             while(prm*j<=n)
63             {
64                 ans+=phi[j]*2;
65                 j++;
66             }
67         }
68 
69         cout<<ans<<endl;
70     }
71 
72     return 0;
73 }

View Code

1067: 22min

 1 //22min
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstdio>
 5 using namespace std;
 6 
 7 int X[10010],Y[10010];
 8 int n,m,opt,P,Q,L;
 9 int xadd,xmul,yadd,ymul;
10 
11 int main()
12 {
13     while(cin>>n)
14     {
15         for (int i=1;i<=n;i++)
16             scanf("%d%d",&X[i],&Y[i]);
17             //cin>>X[i]>>Y[i];
18         cin>>m;
19         xadd=0,xmul=1,yadd=0,ymul=1;
20         for (int i=1;i<=m;i++)
21         {
22             scanf("%d",&opt);
23             if (opt==1)
24             {
25                 cin>>P>>Q;
26                 xadd+=P;
27                 yadd+=Q;
28             }
29             else if (opt==2)
30             {
31                 cin>>L;
32                 xadd=xadd*L;
33                 yadd=yadd*L;
34                 xmul=xmul*L;
35                 ymul=ymul*L;
36             }
37             else if (opt==3)
38             {
39                 ymul=ymul*-1;
40                 yadd=yadd*-1;
41             }
42             else if (opt==4)
43             {
44                 xadd=xadd*-1;
45                 xmul=xmul*-1;
46             }
47         }
48         //cout<<xadd<<" "<<xmul<<"  "<<yadd<<" "<<ymul<<endl;
49         for (int i=1;i<=n;i++)
50             {
51                 X[i]=X[i]*xmul+xadd;
52                 Y[i]=Y[i]*ymul+yadd;
53             }
54         for (int i=1;i<=n;i++)
55             printf("%d %d
",X[i],Y[i]);
56             //cout<<X[i]<<" "<<Y[i]<<endl;
57     }
58     return 0;
59 }

View Code