吐槽： 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
西月弦 閱讀(540)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告