2014年西南交通大学 新秀杯 ACM程序设计大赛 决赛解题报告

| Comments

比赛链接： 新秀杯 ACM程序设计大赛决赛

比赛还算成功，算上友情参赛，总共有7个题目有人通过，第一名最后成绩为5题，虽然离我想的差一点。不过还是不错~~

A 从头再来

只需要简单的统计单词A中每个字母出现的次数，与B中每个字母出现的次数做比较即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#define SQR(x) ((x)*(x))
#define rep(i, n) for (int i=0; i<(n); ++i)
#define repd(i,n)  for(int i=1;i<=(n);++i)
#define repf(i, a, b) for (int i=(a); i<=(b); ++i)
#define reps(i, a, b) for (int i=(a); i>=(b); --i)
#define MaxN  10010
#define ll long long
using namespace std;
void data(){
   freopen("data.in","r",stdin);
   freopen("data.out","w",stdout);
}
char a[MaxN],b[MaxN];
int s1[27],s2[27];
int gao(){
    memset(s1,0,sizeof(s1));
    memset(s2,0,sizeof(s2));
    int l1=strlen(a),l2=strlen(b);
    rep(i,l1) s1[a[i]-'a']++;
    rep(i,l2) s2[b[i]-'a']++;
    rep(i,26)if(s1[i]<s2[i]) return 0;
    return 1;   
}
int main(){
   //data();
   while(cin>>a>>b){
      printf("%s\n",gao()?"Yes":"No");
   }
   return 0;
}

B 挖掘机技术哪家强

~~连接DF，那么ADF的面积为正方形的一半，也是矩形的一半，正方形的面积就等于矩形的面积。 AE=a*a/b; DE=sqrt(a*a-AE*AE)

1
2
3
4
5
6
7
8
9

int main(){
   //  data();
   int a,b;
   while(~scanf("%d%d",&a,&b)){
       double res=sqrt(a*a-(a*a*1.0/b)*(a*a*1.0/b))*(a*a*1.0/b)/2.0;
       printf("%.2lf\n",res);             
   }
   return 0;
}

C YogyKwan的iPhone也弯了

假设半径为r,t为输入的数据那么可以写出如下等式： r*sin(pi-15/r/2)=t/2 我们可以知道，当r越大时候，t就会越小，于是我们可以二分判定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include<cstdio>
#include<cmath>
const double PI=acos(-1);
const double eps=1e-10;
int main(){
    //freopen("data.in","r",stdin);freopen("data2.out","w",stdout);
    double l,w,r,a,sj,xj,m,t;
    while(scanf("%lf",&w)!=EOF){
        l=15;
        sj=l/PI,xj=0.5*l/PI;
        w*=0.5,l*=0.5;
        while(sj-xj>eps){
            m=(sj+xj)*0.5;
            t=m*sin(l/m);
            if(t>w) sj=m;
            else xj=m;
        }
        r=m;
        a=l/r*2;
        printf("%f %f\n",r,a);
    }
    return 0;
}

D 强迫症改变世界

不妨用 f(k) 来表示摆放k个座位的方案数。我们可以把这些方案分成两类：最后一个座位是坐女生，或者最后一个座位是坐男生。如果是前一种情形，则我们只需要看前k–1座位有多少摆法就可以了；如果是后一种情形，那么倒数第二个座位必须是女生，因而这种情形下的方案数就取决于前 k–2个座位的安排方案数。因此我们得到， f(k) = f(k – 1) + f(k – 2) 其中f[1]=2,f[2]=3;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#define SQR(x) ((x)*(x))
#define rep(i, n) for (int i=0; i<(n); ++i)
#define repd(i,n)  for(int i=1;i<=(n);++i)
#define repf(i, a, b) for (int i=(a); i<=(b); ++i)
#define reps(i, a, b) for (int i=(a); i>=(b); --i)
int f[1002];
void gao(){
     f[0]=1;
     f[1]=2;
     repf(i,2,1001) f[i]=(f[i-1]+f[i-2])%mod;           
}
int main(){
    //data();
    int n;
    gao();
    while(~scanf("%d",&n)){
        printf("%ld\n",f[n]);
    }
    return 0;
}

E 强迫症改变世界2

此题需要先会容斥定理， n以内a,b的倍数的个数有， sum=n/a+n/b-n/lcm(a,b); 然后我们枚举出所有的只含有4或者7的数字（大概1000个），然后去掉是前面出现过得数的倍数的数（如44是4的倍数） 大概还剩下不到600个，看起来很大，因为容斥定理的复杂度是2^n次方，但是，此题r的范围不是小，我们在做lcm的时候，很快就会超过范围，就不需要继续向下了，然后我们从大往小做，大概只需要递归10万次左右。

剩下的可以参考代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cctype>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <stack>
#define SQR(x) ((x)*(x))
#define rep(i, n) for (int i=0; i<(n); ++i)
#define repd(i,n)  for(int i=1;i<=(n);++i)
#define repf(i, a, b) for (int i=(a); i<=(b); ++i)
#define reps(i, a, b) for (int i=(a); i>=(b); --i)
#define PB push_back
#define MP(A, B) make_pair(A, B)
#define pow2(n) (1<<(n))
#define pi acos(-1)
#define eps 0.00000001
#define lg(n) log10((n)*1.0)
#define MaxN  1000000000
#define mod 1000000007
#define md(x) (((x)%mod+mod)%mod)
#define ll long long
using namespace std;
void data(){
   freopen("sample.in","r",stdin);
   freopen("sample.out","w",stdout);
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int t,n,m;
ll l,r,ans,a[3000],b[3000];
bool vis[3000];
void pre(int x,ll y)
{
  if(y>MaxN)return;
  if(x>0)a[++m]=y;
  pre(x+1,y*10+4);
  pre(x+1,y*10+7);
}
void gao(){
  sort(a+1,a+m+1);
  repd(i,m)
     if(!vis[i])
     {
         b[++n]=a[i];
         for(int j=i+1;j<=m;j++)
             if(!(a[j]%a[i]))
                 vis[j]=1;
     }
  repd(i,n) a[n-i+1]=b[i];
}
void dfs(int x,int y,ll z)
{
  if(x>n)
  {
    if(y&1)ans+=r/z-(l-1)/z;
    else if(y)ans-=r/z-(l-1)/z;
    return;
  }
  dfs(x+1,y,z);
  ll tmp=z/gcd(a[x],z);
  if((a[x]*tmp)<=r) dfs(x+1,y+1,a[x]*tmp);
}
int main()
{
    //data();
    pre(0,0);
    gao();
    while(~scanf("%lld%lld",&l,&r)){
      ans=0;
      dfs(1,0,1);
      printf("%lld\n",ans);
    }
    return 0;
}

F 不幸的程序员II

矩阵快速幂，如果你还不会这个，那么该先去学习矩阵快速幂。

简单公式推导如下: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

#include <cstdio>
#include<iostream>
#include<cstdlib>
#include<stdio.h>
#include<math.h>
using namespace std;
const int MAX = 3;
#define rep(i, n) for (int i=0; i<(n); ++i)
#define repd(i,n)  for(int i=1;i<=(n);++i)
#define repf(i, a, b) for (int i=(a); i<=(b); ++i)
#define reps(i, a, b) for (int i=(a); i>=(b); --i)
#define mod 1000000007
#define ll long long
typedef struct
{
   ll m[MAX][MAX];
} Matrix;
Matrix P;
Matrix I ={1,0,0,0,1,0,0,0,1};
Matrix matrixmul(Matrix a,Matrix b) 
{
   int i,j,k;
   Matrix c;
   rep(i,MAX)
   rep(j,MAX)
   {
     c.m[i][j] = 0;
     rep(k,MAX) c.m[i][j] += (a.m[i][k] * b.m[k][j])%(mod);
     c.m[i][j] %= (mod);
   }
   return c;
}
Matrix quickpow(ll n, Matrix P)
{
    Matrix m = P, b = I;
    while (n >= 1)
    {
        if (n & 1)
        b = matrixmul(b,m);
        n = n >> 1;
        m = matrixmul(m,m);
    }
    return b;
}
void data(){
   freopen("data.in","r",stdin);
   freopen("data.out","w",stdout);
}
int main()
{
    ll a,b,n,m;
    //data();
    while(~scanf("%lld%lld%lld%lld",&n,&m,&a,&b))
    {   
        Matrix T1,T2,T;
        Matrix P1 = {2,1,3,1,0,0,0,0,1};
        Matrix P2 = {5*8,4*8+7,6*8+9,5,4,6,0,0,1};
        T1=quickpow((m-2),P1);
        T2=quickpow(1LL*n-1,matrixmul(T1,P2));
        T=matrixmul(T2,T1);
        Matrix tmp={b%mod,0,0,a%mod,0,0,1,0,0};
        T=matrixmul(T,tmp);
        printf("%lld\n",T.m[0][0]%mod); 
    }
    return 0; 
}

G 你是一个好人

概率DP，我们假设dp[i][j]表示前i次表白收集了j张不同卡的概率，那么很明显: i==1,j==1时 dp[1][1] = 1;
i<j , dp[i][j] = 0;(一共都不到j张，怎么收集)
那么dp[i+1][j] = dp[i][j]*(j/n)+dp[i][j-1]*(n-(j-1))/n; 第一个表示第i+1收集的与之前的j张是一样的，第二个表示第i+1次收集的与前j-1个不同，那么就就多收集了一个，变成j个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cctype>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <stack>
#define SQR(x) ((x)*(x))
#define rep(i, n) for (int i=0; i<(n); ++i)
#define repd(i,n)  for(int i=1;i<=(n);++i)
#define repf(i, a, b) for (int i=(a); i<=(b); ++i)
#define reps(i, a, b) for (int i=(a); i>=(b); --i)
#define PB push_back
#define MP(A, B) make_pair(A, B)
#define pow2(n) (1<<(n))
#define pi acos(-1)
#define eps 0.00000001
#define lg(n) log10((n)*1.0)
#define MaxN  1000000
#define mod 1000000007
#define ll long long
#define typed int
using namespace std;
void data(){
   freopen("data.in","r",stdin);
   freopen("data.out","w",stdout);
}
//fast read
void RD(int &a) {
    int value = 0, s = 1;
    char c;
    while ((c = getchar()) == ' ' || c == '\n');
    if (c == '-') s = -s; else value = c-48;
    while ((c = getchar()) >= '0' && c <= '9')
        value = value * 10 + c - 48;
    a = s * value;
}
void RD(int &a,int &b){
    RD(a),RD(b);
}
void RD(int &a,int &b,int &c){
    RD(a),RD(b),RD(c);
}
double dp[101][2002];
double gao(int n,int m){
     memset(dp,0,sizeof(0));
     dp[0][0]=1.0;
     repd(i,n)repf(j,i,m) dp[i][j]=dp[i-1][j-1]*(n-i+1)/n+dp[i][j-1]*i/n; 
     return dp[n][m];
}
int main(){
   //data();
   int t,n,m;
   RD(t);
   rep(i,t){
      RD(n,m);
      if(m<n)printf("%.6lf\n",0);
      else printf("%.6lf\n",gao(n,m));
   }
   return 0;
}

H 最萌身高差

此题为树状数组的 YY 题。。。
首先我们考虑若 β 固定的情况，那么根据同模的性质。。如果 a%p == b%p 那么 |a-b| = k * p
这样预处理一下，只要找到模相同的个数，就能知道有多少组了。。此题 β很小，那么我们维护各个余数的前缀和就可以求个分别余数的区间和了。。。，因为此题要求支持修改，那么我们就使 用树状数组（如果你还不会，那么赶紧学起吧）就可以满足要求了。。、、
关键是怎么去修改更新；修改了一个数，我们需要一增一减，余数为 a% β 的减一， (a + p)% β 的加 1.. 这样就可以很好的查找和维护了。。

β不一样？ 但是β很小啊，我们再增加一维？这么做会MLE，那么我们离线处理每个β跑一次就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cctype>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <stack>
#define SQR(x) ((x)*(x))
#define rep(i, n) for (int i=0; i<(n); ++i)
#define repd(i,n)  for(int i=1;i<=(n);++i)
#define repf(i, a, b) for (int i=(a); i<=(b); ++i)
#define reps(i, a, b) for (int i=(a); i>=(b); --i)
#define PB push_back
#define MP(A, B) make_pair(A, B)
#define pow2(n) (1<<(n))
#define pi acos(-1)
#define eps 0.00000001
#define lg(n) log10((n)*1.0)
#define MaxN  200000
#define mod 13041290
#define mod2 1000000009
#define mod3 1000007
#define md(x) (((x)%mod+mod)%mod)
#define inf 2147483647
#define inf2 0x7fffffffffffffff
#define ll long long
#define typed int
using namespace std;
void data(){
   freopen("data.in","r",stdin);
   freopen("data2.out","w",stdout);
}
int C[10][MaxN]={0};
int n,m;
int read(int k,int i){
  int sum=0;
  for(;k;k-=(k&-k)) sum += C[i][k];
  return sum;
}
void update(int k,int p,int i){
    for(;k<=n;k+=(k&-k)) C[i][k] += p;
}
//fast read
void RD(int &a) { 
    int value = 0, s = 1; 
    char c;
    while ((c = getchar()) == ' ' || c == '\n');
    if (c == '-') s = -s; else value = c-48;
    while ((c = getchar()) >= '0' && c <= '9')
        value = value * 10 + c - 48;
    a = s * value;
}
int B[MaxN],A[MaxN];
int l[MaxN],r[MaxN],beta[MaxN];
int q[MaxN];
ll ans[MaxN];
int used[11];
int Q,a,p,m,l1,r1,beta1;
void gao(){
  memset(used,0,sizeof(used));
  rep(i,n) RD(A[i]);
  int len=0,t=0;
  rep(i,m){
      RD(Q);
    if(Q==1)RD(a),RD(p),l[len]=a,r[len]=p,q[len++]=-1;
    else{
         RD(l1),RD(r1),RD(beta1);
         l[len]=l1,r[len]=r1,beta[len]=beta1;
         used[beta1]=1,q[len++]=t++;
       if(beta1==1){ 
        ll ttt=r1-l1+1; 
        ans[q[len-1]]=ttt*(ttt-1)/2%mod;
       }
     }
  }
}
int main(){
  //data();
  while(~scanf("%d%d",&n,&m)){  
     gao();
     repf(k,2,10){
        if(!used[k])continue;
        memset(C,0,sizeof(C));
        rep(i,n) B[i]=A[i],update(i+1,1,A[i]%k);
        rep(i,m){
           if(q[i]==-1){
              update(l[i],-1,B[l[i]-1]%k);
              update(l[i],1,(B[l[i]-1]+r[i])%k);
              B[l[i]-1]+=r[i];
              continue;
           }
           if(beta[i]!=k)continue;
           ll sum=0;
           rep(j,beta[i]){
               ll tp = read(r[i],j) - read(l[i]-1,j);
               sum += tp*(tp-1)/2;
               sum %=mod;
           }
           ans[q[i]]=sum%mod;
        } 
     }
     rep(i,t) printf("%lld\n",ans[i]%mod);
  }
  return 0;
}

I Missing教大家画矩形

模拟题目，确定一个矩形只需要对角线确定， 所以找出最小，最大的x值和y值就行了 题目虽然简单，但是如果写法不好，也会被坑~ (此题来自于Missing)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

//Draw A Rectangle
//Author: _missing
// 模拟题，确定一个矩形只需要对角线确定，
// 所以找出最小，最大的x值和y值就行了
// 题目虽然简单，但是如果写法不好，也会被坑~
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
void draw(int x1, int y1, int x2, int y2) {
    for (int i = 0; i < x1; ++i) puts("");
    for (int i = x1; i <= x2; ++i) {
        for (int j = 0; j < y1; ++j) putchar(' ');
        for (int j = y1; j <= y2; ++j)
            if (i == x1 || i == x2) putchar('*');
            else if (j == y1 || j == y2) putchar('*');
            else putchar(' ');
        putchar('\n');
    }
}
int main() {
    //freopen("data2.in", "r", stdin);
    //freopen("data2.out", "w", stdout);
    int T, ncase = 0, N;
    while (~scanf("%d", &T)) {
        while (T--) {
            int x[4], y[4], minx = 100, maxx = -1, miny = 100, maxy = -1;
            int ok = 1;

            scanf("%d", &N);
            for (int i = 0; i < N; ++i) scanf("%d %d", x+i, y+i);
            for (int i = 0; i < N; ++i) {
                minx = min(minx, x[i]);
                maxx = max(maxx, x[i]);
                miny = min(miny, y[i]);
                maxy = max(maxy, y[i]);
            }
            if (minx == maxx || miny == maxy) ok = 0;
            for (int i = 0; ok && i < N; ++i) {
                if ((x[i] == minx || x[i] == maxx) &&
                    (y[i] == miny || y[i] == maxy)) continue;
                ok = 0;
            }

            printf("Case #%d:\n", ++ncase);
            if (!ok) { puts("None"); continue; }
            draw(minx, miny, maxx, maxy);
        }
    }
    return 0;
}

以上题目均为过测试数据的程序，不保证程序完全正确无误. Thanks for reading…

原文地址: http://www.UnkelTao.com/blog/2014/11/16/2014-swjtu-acm-onsite-programming-contest/

 由 UnkelTao 撰写并发表于 http://www.UnkelTao.com

Comments