算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
吐槽:
    1. 真的是本年度变黄的最好机会,但是被我白白浪费了。。。。
    2. Orz mzry
A. Clear Symmetry

    定义一个01矩阵X,长和高相等且同时拥有两个性质:
        1. 含有1的格子不相邻
        2. 对于任意的格子 X[i][j] 有 X[i][j]==X[n-1-i][j] && X[i][j] == X[i][m-1-j]
    给你一个数n,求最小的恰好包含n个1的矩阵X的边长。

算法分析:

    猜结论,首先发现偶数的情况应该是不可能的。
    然后猜测解的分布是连续的。有个特例是n=3。
 1 #include<iostream>
 2 using namespace std;
 3 int num[100];
 4 int main(){
 5     int len = 1;
 6     num[0] = 1;
 7     do{
 8         num[len] = num[len-1] + len*4;
 9         len ++;
10     } while(num[len-1] <=100);
11     int n;
12     while(cin >> n){
13         int i=0;
14         if(n==3) {cout<<5<<endl;continue;}
15         for(;n > num[i];i++); 
16         cout<<2*i+1<<endl;
17     }
18 }
19 
B. Guess That Car!
     有一个矩阵C。位置(x,y)与(i,j)的权值是 C[i][j] * ( (|x-i|*4+2)^2 + (|y-j|*4+2)^2 )。
     要求求出最佳位置x,y使所有位置与x,y的权值和最小。

算法分析:

    正解是分别预处理x和y,然后依次检查。
    我的方法是直接用 d^2*c 和 d*c的关系去依次维护d^2*c。这个方法非常蠢,但是居然被我想到了卧槽 = =!
    易疵点是最大值的不容易选取,因为结果会很大。
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 typedef long long ll;
 6 const int N = 1005;
 7 int num[N][N];
 8 ll sumc, sumxc,sumx[N],sumy[N],now;
 9 ll dist(ll w,ll h){
10     return w*w + h*h;
11 }
12 int main(){
13     int n,m;
14     while(cin >> n >> m){
15         sumc = now = 0;
16         for(int i=0;i<n;i++)
17             for(int j=0;j<m;j++){
18                 scanf("%d",&num[i][j]);
19                 now += num[i][j] * dist(i*4+2, j*4+2);
20                 sumc += num[i][j];
21             }
22         for(int i=0;i<n;i++) sumx[i] = 0;
23         for(int i=0;i<m;i++) sumy[i] = 0;
24         for(int i=0;i<n;i++)
25             for(int j=0;j<m;j++)
26                 sumx[i] += num[i][j] ,
27                 sumy[j] += num[i][j] ;
28         ll nowx, nowy, sumyc = 0, ans = -1;
29         for(int i=0;i<n;i++)
30             sumyc += (i*4+2) * sumx[i];
31         ll myxc = 0;
32         int x,y;
33         for(int i=0;i<m;i++)
34             myxc += (i*4+2) * sumy[i];
35         for(int i=0;i<=n;i++){
36             if(i==0) nowx = now;
37             else {
38                 nowx += 16*sumc - 8*sumyc;
39                 sumyc -= 4*sumc;
40             }
41             sumxc = myxc;
42             for(int j=0;j<=m;j++){
43                 if(j==0) nowy = nowx;
44                 else {
45                     nowy += 16*sumc - 8*sumxc;
46                     sumxc -= 4*sumc;
47                 }
48                 if(ans == -1 || ans > nowy){
49                     ans = nowy;
50                     x = i; y = j;
51 //                    cout<<i<<" "<<j<<endl;
52                 }
53             }
54         }
55         cout<<ans<<endl;
56         cout<<x<<" "<<y<<endl;
57     }
58 }
59 
C. Fragile Bridges

    有n个点排成一行,每两个点有一个权值。 现在让你遍历这些点,每一次经过两点的时候,两点之间的权值就会 -1。 你的得分会+1。不允许经过权值为0的边。
    你可以自由选取出发点,使得分最多。求最多的得分。

算法分析:

    dpl[i][p],当p = 0时,dp[i]代表从i出发遍历 0 - i的点,能得到的最大得分。
    当p = 1时, dp[i]代表从i出发遍历0-i, 最后回到i的最大得分。
    dpr同理。 最后枚举每个出发点。O(n)复杂度。
    但是忘了当边长为1的时候是不能回头的,于是fail system test。 错过了变黄的最好机会啊!!!
 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 typedef long long ll;
 5 const int N = 100005;
 6 int num[N];
 7 ll dpl[N][2], dpr[N][2];
 8 int main(){
 9     int n;
10     cin >> n;
11     for(int i=0;i<n-1;i++)
12         scanf("%d",&num[i]);
13     dpl[0][0] = dpl[0][1] = 0;
14     for(int i=1;i<n;i++){
15         dpl[i][1] = (num[i-1] > 1 ? num[i-1]/2*2 + dpl[i-1][1] : 0);
16         if(num[i-1] & 1) dpl[i][0] = dpl[i-1][0] + num[i-1] ;
17         else dpl[i][0] = max( dpl[i][1] , dpl[i-1][0] + num[i-1] -1);
18     }
19     dpr[n-1][0] = dpr[n-1][1] = 0;
20     for(int i=n-2;i>=0;i--){
21         dpr[i][1] = (num[i] > 1 ? num[i]/2*2 + dpr[i+1][1] : 0);
22         if(num[i] & 1) dpr[i][0] = num[i] + dpr[i+1][0];
23         else dpr[i][0] = max(dpr[i][1], dpr[i+1][0] + num[i]-1);
24     }
25     ll ans = 0;
26     for(int i=0; i<n;i++){
27 //        cout<<"l: "<<dpl[i][0]<<" "<<dpl[i][1]<<" r: "<<dpr[i][0]<<" "<<dpr[i][1]<<endl;
28         ll v1 = max(dpl[i][0],dpr[i][0]);
29         ll v2 = max(dpl[i][1]+dpr[i][0],dpr[i][1]+dpl[i][0]);
30         ans = max(ans,max(v1,v2));
31     }
32     cout<<ans<<endl;
33 }
34 
posted on 2012-06-30 02:49 西月弦 阅读(535) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理