@kaike
第一题太简单我不想说什么
来说第二题。
1．小x的旅行
(travel.pas/c/cpp)
【问题描述】
小x大学毕业后，进入了某个公司做了高层管理，他每年的任务就是检查这个公司在全国各地N个分公司的各种状况，每个公司都要检查一遍，且只能检查一遍，也就是说这N个地方只能也必须去一次。
当然，小x每年可以选择从任意一个城市开始，任意一个城市结束。
现在给出这N个公司所在地任意两个地点飞机票的价格，现在小x为了给公司省下交通费，需要设计一个程序，来计算一下如何花费最低能够完成任务。
作为一名有过信息学竞赛经历的有志青年，小x给自己的路线又规定了一个约束条件：如果要访问编号为K的城市，那么编号比K小的所有城市或者在访问K之前访问，或者在访问K之后访问。这个条件也必须遵守。
比如：如果有3个城市：2 1 3和 3 1 2 的顺序都是合法的，但是 1 3 2的顺序就是非法的，因为比3小的1在3之前，2在3之后，和小x的要求冲突。
【输入】
第一行：一个整数N。
接下来N行，每行N个整数。第i行第j列的值a[i][j]表示第i个城市到第j个城市飞机票的价格。保证这N个整数在[0..1000]之间。
【输出】
一个整数，表示满足要求的最小花费。
【输入输出样例1】
|
travel.in |
travel.out |
|
3 0 5 2 5 0 4 2 4 0 |
7 |
【输入输出样例2】
|
travel.in |
travel.out |
|
4 0 15 7 8 15 0 16 9 7 16 0 12 8 9 12 0 |
31 |
【样例解释】顺序为3, 1, 2, 4 或者 4, 2, 1, 3.
【数据范围】
30% 数据保证N<=10
50% 数据保证 N<=20
100% 数据保证 N<=1500
第一眼看上去：咦这不是个最小生成树？
后来觉得不对，应该算出顶点和图的关系...后来我就不会写了
生成顶点了太多..不会写
后来看他们都写得dfs，dfs现在刚复习完....
看题解，原来如此简单。
反着推，从1开始，这个我考试的时候也想到了。不同的是枚举左端点和右端点
根据两个城市之间的关系+记忆化搜索，可以A。
不加的话大概能到70分。
然而苦于思维打不开想不到QAQ
1 /* 2 by kaike 3 11/14/2016 4 */ 5 #include<iostream> 6 #include<algorithm> 7 #include<cstdio> 8 using namespace std; 9 #define FILE "travel" 10 const int MAXN=1510; 11 int mo[MAXN][MAXN],a[MAXN][MAXN],n; 12 int dp(int l,int r) 13 { 14 if(mo[l][r]) return mo[l][r]; 15 int next=max(l,r)+1; 16 if(next==n) return 0; 17 return mo[l][r]=min(a[next][l]+dp(next,r), 18 a[r][next]+dp(l,next)); 19 } 20 int main() 21 { 22 //freopen(FILE".in","r",stdin); 23 //freopen(FILE".out","w",stdout); 24 cin>>n; 25 for(int i=0;i<n;i++) 26 for(int j=0;j<n;j++) 27 cin>>a[i][j]; 28 cout<<dp(0,0)<<endl; 29 return 0; 30 }
第三题是树状数组求和。
它每循环一次，就是找二进制的1，同时ans++;
x被计算的次数=右端点x的个数+左端点为x+1的个数 = x+n-x = n
这样就可以从1枚举到n并对bitcount(i)求和。
70分到手。
要A的算法是要用数位DP？并不会。
1 /* 2 by kaike 3 11/14/2016 4 */ 5 #include<iostream> 6 #include<algorithm> 7 using namespace std; 8 #define FILE "bit" 9 int map[51000],t,x; 10 const int ss=1000000007; 11 int lowbit(int x) 12 { 13 return x&(-x); 14 } 15 int sum(int x) 16 { 17 int ans=0; 18 while(x>0) 19 { 20 ans++; 21 x-=lowbit(x); 22 } 23 return ans; 24 } 25 int main() 26 { 27 freopen(FILE".in","r",stdin); 28 freopen(FILE".out","w",stdout); 29 cin>>t; 30 for(int i=1;i<=t;i++) 31 { 32 cin>>x; 33 long long s=0; 34 for(int j=1;j<=x;j++) 35 s+=(sum(j)*x)%ss; 36 cout<<s<<endl; 37 } 38 return 0; 39 }