2007 提高组题解
第一题 一开始还想是不是要用哈希表储存呢，但仔细想了一会儿，那个数据量20W 用个快排序，时间是能过的。所以这道题用个STL的快排，再一个循环统计个数就OK了。但最后交上去评测时0分，很尴尬。就是我在数据初始化时从一开始计数，我循环又从一开始，你懂的，多算了一次，爆掉了。改了就100了。200W的话数据就很强了，用哈希好一些。
第二题 额，写得很快，果然这种无脑模拟题最适合我了。但自信没检查，带了3组给的数据就走了。果然错了，过了4个点好像。主要是题没读完，没有判断处于字母和数字的情况，然后输出了一堆乱七八糟的字符，嗯，爆了。完了之后9分，哇，好气啊。再核对了一遍数据，额，我处理转大写时是这样写的：/* buffer – ‘a’+ ‘A’*/ 带数字进去可想而知是什么鬼了，我开始看数据时是‘3’变为了 ! 我还以为是十进制变成了十六进制呢。= =
第三题 处理了前60% 的数据，但答案没有高精，40分。听了orange Lee 的类的高精度处理讲解后，有了那么点感觉，但还是很不熟悉，这种果然还是要平时多写，其实主要是不怎么喜欢高精，感觉数组处理起来很烦，能用Long long 的题就是好题。总的来说是一道区间DP，主要难点还是高精的处理上。
第四题 做了半天也就不想做了，加上读了半天题没读懂很心累。其实是Floyd算法求直径，然后根据情况来选取偏心距。
/*
首先来考虑只有一条直径的时候，后面会说明有多条直径的时候可以当作一条来处理。首先可以通过经典的O(n)的算法求出树上的最远点，即一条直径（做法是从任意一点开始DFS一次求出一个最远的点，这是直径的一个端点；再从这个最远点开始再次DFS，再找到的最远点就是直径的另外一个端点）。然后顺序枚举这条最长路径上的每条长度小于s的最长子路径（说不太清楚看代码吧...），用一个队列维护。这样每一条可能的路径就是一个可能的核，再求出对应的偏心距就可以了。我是先用了一个Floyd预处理出所有顶点之间的最点路备用。 ok，来说有多条直径的问题： 题目中已经说了，如果有多条直径的话他们的中心也一定重合，换言之一定至少有一个节点或一条路径重合。假设有两条直径分别为AB和CD，它们重合的部分是EF。那么一定有AE的长度等于CE的长度，FB的长度等于FD的长度。其次核一定是在直径的中央部分。下面分两种情况讨论： 1. 如果给定的s能够覆盖重合的点或者路径，那么我们在任一条直径上选择一个核，那么对于另外的直径而言，就是只选择了重合的部分，对于这个核的偏心距“有贡献”的只可能是在非选中的直径上，而对于每条直径除去重合部分剩下的两部分的长度都是相等的，所以选择任意一条直径均可。 2. 如果不能覆盖，那么对于所有直径选择的部分都是相同的了，更是可以任选了。 两点还可以改进的地方，由于数据不是很强，我也就没改： 1. 核一定是在直径的中央部分，所以可以从直径的中心向两边扩展求核。 2. 距离核最远的点一定是度为1的点，Floyd预处理有点浪费了。
*/
#include<iostream> #include<algorithm> using namespace std; int data[200010]; int n,comp,tot; int main() { freopen("count.in","r",stdin); freopen("count.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&data[i]); sort(data+1,data+n+1); comp = data[1]; tot = 1; for(int i=2;i<=n;i++){ if(comp == data[i]) tot++; else { printf("%d %d ",comp,tot); comp = data[i]; tot = 1; } } printf("%d %d ",comp,tot); return 0; }
#include<iostream> #include<cstring> using namespace std; int p1,p2,p3; char str[110]; int main() { freopen("expand.in","r",stdin); freopen("expand.out","w",stdout); cin >> p1 >> p2 >> p3; cin >> str; int lenth = strlen(str); for(int i=0;i<=lenth-1;i++){ if(str[i] == '-' && str[i-1] < str[i+1]){ if(p3 == 1){ int comp = str[i-1]; while(++comp < str[i+1]){ for(int i=1;i<=p2;i++){ if(p1 == 1) cout << (char)comp; else if(p1 == 2) cout << (char)(comp - 'a' + 'A'); else cout << '*'; } } } else { int comp = str[i+1]; while(--comp > str[i-1]){ for(int i=1;i<=p2;i++){ if(p1 == 1) cout << (char)comp; else if(p1 == 2) cout << (char)(comp - 'a' + 'A'); else cout << '*'; } } } } else { cout << str[i]; } } return 0; }
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int power=4; const int base=10000; const int maxl=10; struct num { int a[maxl]; num() { memset(a,0,sizeof(a)); } num operator + (const num &b) { num c; c.a[0] = max(a[0],b.a[0]); for (int i=1; i<=c.a[0]; i++) { c.a[i] += a[i]+b.a[i]; c.a[i+1] += c.a[i]/base; c.a[i] = c.a[i]%base; } if (c.a[c.a[0]+1])++c.a[0]; return c; } num operator + (const int &b) { a[1]+=b; int i=1; while (a[i]>=base) { a[i+1] += a[i] / base; a[i] %= base; i++; } if (a[a[0] + 1]) a[0]++; return *this; } num operator = (int b) { a[0] = 0; while (b) { a[0]++; a[a[0]] = b % base; b /= base; } return *this; } bool operator < (const num &b) const { if (a[0] < b.a[0]) return true; if (a[0] > b.a[0]) return false; for (int i = a[0]; i > 0; --i) { if (a[i] != b.a[i]) return a[i] < b.a[i]; } return false; } void print() { printf("%d", a[ a[0] ]); for (int i = a[0]-1; i > 0; --i) printf("%0*d", power, a[i]); printf(" "); } } ans,f[maxn][maxn]; int main() { // freopen("game.in","r",stdin); // freopen("game.out","w",stdout); scanf("%d%d",&n,&m); for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) scanf("%d",&a[j]); for (int j=1; j<=m; j++) f[j][j] = a[j]; for (int j=1; j<=m-1; j++) { for (int k=1; k<=m-j; k++) { int l = k + j; f[k][l] = max(f[k+1][l] + f[k+1][l] + a[k], f[k][l-1] + f[k][l-1] + a[l]); } } ans = ans + f[1][m]; ans = ans + f[1][m]; } ans.print(); return 0; }
#include<cstring> #include<iostream> using namespace std; int map[350][350],deal[350]; int n,lev,x,y,value,ans = 2147483647; int main() { memset(map,127/3,sizeof(map)); cin >> n >> lev; for(int i=1; i<=n; i++) map[i][i] = 0; for(int i=1; i<=n-1; i++) { cin >> x >> y >> value; map[x][y] = map[y][x] = value; } for(int k=1; k<=n; k++) { for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { map[i][j] = min(map[i][k] + map[k][j],map[i][j]); } } } int record = 0; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { if(map[i][j] > record) { record = map[i][j]; x = i; y = j; } } } for(int i=1; i<=n; i++) if(map[x][i] + map[i][y] == map[x][y]) deal[++deal[0]] = i; for(int i=1; i<=deal[0]; i++) { for(int j=1; j<=deal[0]; j++) { if(map[deal[i]][deal[j]] <= lev) ans = min(ans,max(min(map[x][deal[i]],map[x][deal[j]]),min(map[deal[i]][y],map[deal[j]][y]))); } } cout << ans; return 0; }