第1题 标题统计 #include #include using namespace std; int main() { freopen("title.in", "r", stdin); freopen("title.out", "w", stdout); string title; getline(cin, title); int len = title.size(); for(int i = 0; i < (int)title.size(); i++) { if(' ' == title[i]) { len--; } } cout << len; return 0; } 评测结果 第2题 龙虎斗 #include #include #include using namespace std; #define LL long long int main() { freopen("fight.in","r",stdin); freopen("fight.out","w",stdout); int n, i, m, p1, p2; cin >> n; LL c[n + 1], s1, s2; for(i = 1; i <= n; i++) { cin >> c[i]; } cin >> m >> p1 >> s1 >> s2; c[p1] += s1; LL lPower = 0; // 龙势力 for(i = 1; i < m; i++) { lPower += c[i] * (m - i); } LL rPower = 0; for(i = m + 1; i <= n; i++) { rPower += c[i] * (i - m); } //cout << lPower << ' ' << rPower << endl; LL gap = abs(lPower - rPower); // 双方的气势差 p2 = m; //默认放在m位置 for(i = 1; i <= n; i++) { if(i < m) // 神兵加到左侧龙势力 { if(abs(lPower + s2 * (m - i) - rPower) < gap) { gap = abs(lPower + s2 * (m - i) - rPower); p2 = i; } } else if(i > m) // 神兵加到右侧虎势力 { if(abs(rPower + (i - m) * s2 - lPower) < gap) { gap = abs(rPower + (i - m) * s2 - lPower); p2 = i; } } } cout << p2 << endl; return 0; } 评测结果： 第3题 摆渡车 #include #include #include using namespace std; int n,m; int data[1024]; int sum[1024]; int dp[1024][128]; int main() { // freopen("bus.in", "r", stdin); // freopen("bus.out", "w", stdout); scanf("%d%d", &n, &m); for(int i=1; i<=n; ++i) { scanf("%d", data + i); } sort(data+1, data+n+1); for(int i=1; i<=n; ++i) { sum[i] = sum[i-1] + data[i]; } // i代表第i个人（可能不止一个） for(int i = 1; i <= n; ++i) { // j表示当前这个人可能的候车时间，取值[0,m-1) for(int j = 0; j < m; ++j) { int curBusTime=data[i] + j; if(j) { dp[i][j] = dp[i][j - 1]; } else { dp[i][j] = curBusTime*i - sum[i]; } // 最近的一趟车可能出发的时间 for(int lastBusTime = max(curBusTime - 2 * m + 1, 0); lastBusTime <= curBusTime - m; ++lastBusTime) { // lastCarry表示被上一辆车接走的学生人数 int lastCarry = lower_bound(data + 1, data + n + 1, lastBusTime + 1)- (data + 1); // lastWait表示上一个人的候车时间 int lastWait = min(lastBusTime - data[lastCarry], m - 1); // 动态转移方程 int tmp = dp[lastCarry][lastWait] + (i - lastCarry) * curBusTime - (sum[i] - sum[lastCarry]); if(tmp< p=""> { dp[i][j]=tmp; } } } } printf("%dn",dp[n][m-1]); return 0; } 评测结果 第4题 对称二叉树 #include inline int max(int x, int y) { return x > y ? x : y; } const int MAXN = 1000000; int cnt[MAXN + 5], lef[MAXN + 5], rig[MAXN + 5], ans; int v[MAXN + 5]; // 节点的权值 // 检查左右子树是否对称 bool checkSym(int leftId, int rightId) { if(leftId == -1 && rightId == -1) { // 若左右子节点都不存在，则认为是对称 return true; } if(v[leftId] != v[rightId]) { // 左子节点值 不等于 右子节点值，说明不对称 return false; } else { // 左子节点值等于右子节点值，则左左=右右且右左=左右，说明对称；否则不对称。注意要递归下去 return checkSym(lef[leftId], rig[rightId]) && checkSym(rig[leftId], lef[rightId]); } } // 求第nodeId个节点为根节点的二叉树，所包含的节点总数 int nodeCnt(int nodeId) { // 当前节点不存在 if(-1 == nodeId) { return 0; } else { // 左子树节点数 + 右子树节点树 + root本身的节点数1 return cnt[nodeId] = nodeCnt(lef[nodeId]) + nodeCnt(rig[nodeId]) + 1; } } void dfs(int nodeId) { // 空节点为递归终止的条件 if(-1 == nodeId) { return; } // 左子树节点总数 等于 右子树节点总数，这是对称的前提 if(cnt[lef[nodeId]] == cnt[rig[nodeId]]) { if(checkSym(lef[nodeId], rig[nodeId])) { // 若对称，获取总的节点数，并与原先的ans比较 ans = max(ans, cnt[nodeId]); } } // 左子树下是否包含对称二叉树 dfs(lef[nodeId]); // 右路子树是否包含对称二叉树 dfs(rig[nodeId]); } int main() { freopen("tree.in", "r", stdin); freopen("tree.out", "w", stdout); int n; scanf("%d", &n); for(int i=1; i<=n; i++) { scanf("%d", &v[i]); } for(int i=1; i<=n; i++) { scanf("%d%d", &lef[i], &rig[i]); } nodeCnt(1); dfs(1); printf("%dn", ans); return 0; }

--end--

声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com