吐槽： 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
西月弦 阅读(527)
评论(0) 编辑 收藏 引用 所属分类:
解题报告