Algorithm Programming Problem

P1125 [NOIP 2008 提高组] 笨小猴 我理解的题目意思 一个字符串中出现次数最多的字母的出现次数是 maxn ，minn 是出现次数最少的字母的出现次数，如果 maxn−minn 是一个质数,那么输出 Lucky Word，再换行输出 maxn−minn 的值；否则输出 No Answer,，换行输出 0。 $$字符串长度小于 100$$解题思路 依题意模拟即可，用数组b记录字母出现次数，遍历出maxn、minn，再判断maxn−minn是否为质数。 代码： #include <iostream> #include <algorithm> using namespace std; char a[105]; int main() { cin >> a; int b[26] = {0}; for (int i = 0; a[i] != '\0'; i++) { b[a[i] - 'a']++; } int maxn = -1, minn = 105; for (int i = 0; i < 26; i++) { if (b[i] > 0) { maxn = max(maxn, b[i]); minn = min(minn, b[i]); } } int ans = maxn - minn; for (int i = 2; i <= ans / 2; i++) { if (ans % i == 0 && ans != 2) { cout << "No Answer" << endl << 0; return 0; } } if (ans < 2) cout << "No Answer" << endl << 0; else cout << "Lucky Word" << endl << ans; return 0; }

P1124 [ZJOI2001] 文件压缩 我理解的题目意思 对一个长度为 n 的字符串 S，首先根据它构造 n 个字符串，其中第 i 个字符串由将 S 的前 i−1 个字符置于末尾得到。然后把这 n 个字符串按照首字符从小到大排序，如果两个字符串的首字符相等，则按照它们在 S 中的位置从小到大排序。排序后的字符串的尾字符可以组成一个新的字符串 S′ ，它的长度也是 n，并且包含了 S 中的每一个字符。最后输出 S′ 以及 S 的首字符在 S′ 中的位置 p。 读入 S′ 和 p，输出字符串 S. $$1≤n≤10000，S 仅含小写字母$$解题思路 输入输出样例 #1 输入 #1 7 xelpame 7 输出 #1 example 注意到，S' 只是把原字符串 S 中的所有字符重新排列了一下，所以 S' 和 S 包含的字符完全相同。 我们把 S' 从小到大排序，得到： F = sort(S') 现在观察排序后的每一行。 原来的第 j 个字符串是： S[j] S[j+1] ... S[n] S[1] ... S[j-1] 所以： ...

P1123 取数游戏 我理解的题目意思 一个 N×M 的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻 8 个格子中的一个即认为这两个数字相邻），求取出数字和最大是多少。 $$1≤N,M≤6，1≤T≤20，ai,j​≤10^5$$解题思路 注意到数据量很小，可以dfs最大的数字和，维护一个chosen数组做一个待选择数字是否有相邻数字被选择的判断。 代码： #include <iostream> #include <algorithm> using namespace std; int t, n, m, ans; int a[10][10]; // 检查 (x,y) 是否与已选的格子相邻 bool ok(int x, int y, bool chosen[10][10]) { for (int dx = -1; dx <= 1; dx++) { for (int dy = -1; dy <= 1; dy++) { if (dx == 0 && dy == 0) continue; int nx = x + dx; int ny = y + dy; if (nx >= 1 && ny >= 1 && nx <= n && ny <= m && chosen[nx][ny]) return false; } } return true; } void dfs(int x, int y, int sum, bool chosen[10][10]) { if (x > n) { ans = max(ans, sum); return; } int nx = (y == m) ? x + 1 : x; int ny = (y == m) ? 1 : y + 1; dfs(nx, ny, sum, chosen); if (ok(x, y, chosen)) { chosen[x][y] = true; dfs(nx, ny, sum + a[x][y], chosen); chosen[x][y] = false; } } int main() { cin >> t; while (t--) { cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j]; ans = 0; bool chosen[10][10] = {}; dfs(1, 1, 0, chosen); cout << ans << endl; } return 0; }

P1122 最大子树和 我理解的题目意思 给出n个点，点具有点权a[i]，n-1条双向边将点连接为一个树，通过剪枝使得剩下的点权和最大，输出最大值。 $$1≤n≤16000，a_i范围在 [−10^9,10^9] 内$$解题思路 使用vector数组记录点的邻接点，使用f[i]记录保留a[i]的最大点权和。初始化f[i]为a[i],dfs点i的邻接点k的最大点权和，若f[k]>0，则f[i]=f[i]+f[k]，同时设置一个fa用于避免反向搜索到起点。 代码： #include <iostream> #include <vector> using namespace std; vector<int> ad[20000]; int n; int ans = 1 << 31; int a[20000]; int f[20000]; void dfs(int u, int fa) { f[u] = a[u]; for (int i = 0; i < ad[u].size(); i++) { int t = ad[u][i]; if (t != fa) { dfs(t, u); if (f[t] > 0) { f[u] += f[t]; } } } } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= n - 1; i++) { int x, y; cin >> x >> y; ad[x].push_back(y); ad[y].push_back(x); } dfs(1, 0); for (int i = 1; i <= n; i++) ans = max(ans, f[i]); cout << ans; return 0; } 参考 Mutsumi_0114

P1121 环状最大两段子段和 我理解的题目意思 给出一段长度为 n 的环状序列 a，即认为 a1​ 和 an​ 是相邻的，选出其中连续不重叠且非空的两段使得这两段和最大。 $$2≤n≤2×10^5，−10^4≤a_i​≤10^4$$解题思路 从前到后计算出到a[i]之前的最大字段和af[i]，从后到前计算出到a[i+1]之前的最大字段和ab[i],遍历枚举出最大的af[i]+ab[i+1]作为初始的环状最大两段子段和ans。 再计算将max方法改为min，从前到后计算出到a[i]之前的最小字段和mf[i]，从后到前计算出到a[i+1]之前的最小字段和mb[i],遍历枚举出最小的af[i-1]+ab[i+1]作为最小两段子段和t，因为最大两段子段可以相邻。 比较ans和sum-t，ans=max(ans,sum-t). 代码： #include <iostream> #include <algorithm> #include <cstring> #define size 300000 using namespace std; int n; int a[size], af[size], ab[size], mf[size], mb[size]; int sum; int getmin(int *arr, int l) { mf[1] = a[1]; for (int i = 2; i <= l; i++) mf[i] = min(mf[i - 1], 0) + a[i]; for (int i = 2; i <= l; i++) mf[i] = min(mf[i - 1], mf[i]); int ans = 1ll << 31ll - 1ll; mb[l] = a[l]; for (int i = l - 1; i > 1; i--) mb[i] = min(mb[i + 1], 0) + a[i]; for (int i = l - 1; i > 1; i--) mb[i] = min(mb[i + 1], mb[i]); for (int i = 2; i <= l- 1; i++) ans = min(ans, mf[i - 1] + mb[i + 1]); return ans; } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; sum += a[i]; } af[1] = a[1]; for (int i = 2; i <= n; i++) af[i] = max(af[i - 1], 0) + a[i]; for (int i = 2; i <= n; i++) af[i] = max(af[i - 1], af[i]); int ans = 1ll << 31ll; ab[n] = a[n]; for (int i = n - 1; i > 1; i--) ab[i] = max(ab[i + 1], 0) + a[i]; for (int i = n - 1; i > 1; i--) ab[i] = max(ab[i + 1], ab[i]); for (int i = 1; i <= n - 1; i++) ans = max(ans, af[i] + ab[i + 1]); // ans = max(ans, sum - getmin(a, n - 1)); ans = max(ans, sum - getmin(a + 1, n - 1)); cout << ans; return 0; } 参考 zhy137036

P1120 [CERC 1995] 小木棍 我理解的题目意思 有一些同样长的木棍，把这些木棍随意砍成几段，直到每段的长都不超过 50。给出n段小木棍的长度,找出原始木棍的最小可能长度。 $$1≤n≤65，1≤a_i​≤50$$解题思路 首先确定原始木棍的长度范围，也就是搜索范围： 原始木棍数量大于等于2，长度len上限是$\frac{1}{2} \sum_{i=1}^{n}a_i$，下限为$max(a_i)$。 原始木棍数量等于1,长度len$=\sum_{i=1}^{n}a_i$，直接输出就行。 对于原始木棍数量大于等于2的情况，使用dfs进行搜索，要进行几个剪枝，下面是构造过程： 先对a[i]进行从大到小排序，因为更小的小木棍可以更灵活地组成木棍，要后使用。 设置一个used数组记录哪些小木棍已使用。 使用参数last,rest,k分别表示上一个使用的小木棍、木棍剩余需要长度、填充的第几个木棍。 当rest=0时，判断凑成木棍个数是否满足，若不满足则从1到n进行dfs搜索未访问的小木棍； 当rest!=0时，从last到n进行进行dfs搜索未访问的小木棍，这里可以进行几个剪枝：a[i] > rest就跳过，搜索下一个；搜索完之后，如果a[i] = rest，直接返回false；跳过相同长度的木棍。 代码： #include <iostream> #include <algorithm> #include <cstring> using namespace std; int n; int a[70]; bool used[70]; int sum; int len; int m; bool cmp(int a, int b) { return a > b; } bool dfs(int last, int rest, int k) { if (rest == 0) { if (k == m) return true; int i = 1; while (i <= n && used[i]) i++; if (i > n) return false; used[i] = true; if (dfs(i, len - a[i], k + 1)) return true; used[i] = false; return false; } for (int i = last; i <= n; i++) { if (used[i] || a[i] > rest) continue; used[i] = true; if (dfs(i, rest - a[i], k)) return true; used[i] = false; if (a[i] == rest) return false; // 跳过相同长度的木棍 while (i + 1 <= n && a[i + 1] == a[i]) i++; } return false; } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; sum += a[i]; } sort(a + 1, a + 1 + n, cmp); for (len = a[1]; len <= sum / 2; len++) { if (sum % len != 0) continue; fill(used, used + n + 1, false); m = sum / len; used[1] = true; if (dfs(1, len - a[1], 1)) { cout << len; return 0; } // used[1] = false; //搜索程序本身已经处于时间复杂度临界状态，而这条语句本身不改变搜索逻辑。虽然只是一次赋值，但整个程序可能运行了大量 DFS。 } cout << sum; return 0; } 参考 Kaori

P1119 灾后重建 我理解的题目意思 给出N个点、M条双向边、点存在的最早时间ti。做Q次查询t时刻点x和y之间的最短距离，若此时无法连通，则输出-1。 $$t_0​≤t_1​≤⋯≤t_{N−1}​$$ $$查询的 t 是不下降的$$ $$1≤N≤200，0≤M≤N×(N−1)/2​，1≤Q≤50000,所有输入数据涉及整数均不超过 10^5$$解题思路 每次查询时遍历小于等于t的tk,使用floyd算法计算加入点k之和的最短路径长度数组，初始化最短路径长度数组为一个较大的数inf，若f[x][y]=inf则输出-1，否则输出f[x][y]。 代码： #include <iostream> #include <algorithm> #define len 205 using namespace std; int a[len]; int f[len][len]; int n, m; void update(int k) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (f[i][j] > f[i][k] + f[k][j]) f[i][j] = f[i][k] + f[k][j]; } } return; } int main() { cin >> n >> m; for (int i = 0; i < n; i++) { cin >> a[i]; f[i][i] = 0; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i != j) f[i][j] = 1e9; } } for (int s = 1; s <= m; s++) { int x, y, w; cin >> x >> y >> w; f[x][y] = f[y][x] = w; } int q; int k = 0; cin >> q; for (int s = 1; s <= q; s++) { int x, y, t; cin >> x >> y >> t; while (a[k] <= t && k < n) { update(k); k++; } if (t < a[x] || t < a[y]) cout << -1 << endl; else { if (f[x][y] == 1e9) cout << -1 << endl; else cout << f[x][y] << endl; } } return 0; } 参考 Time_Rune

P1118 [USACO06FEB] Backward Digit Sums G/S 我理解的题目意思 给两个正整数 n,sum 。将数字从 1 到 n 按某种顺序写下来，然后将相邻的数字相加，得到一个数字更少的新列表,重复这个过程，直到只剩下一个数字,若这个数字等于sum，则输出满足这个条件的字典序最小的序列1~n;否则不输出。 $$1≤N≤12，1≤sum≤12345$$解题思路 数组ai每次相邻相加的过程，最终结果的系数就是杨辉三角的对应行。所以先预处理出c记录杨辉三角系数，再进行深度优先搜索尝试所有顺序，设置一个pos，按字典序尝试数字填入a[pos]，结合剪枝优化时间，在字典序尝试之前先判断已经填入的 a[i]*c[i] 之和是否大于sum，大于则停止搜索。当pos等于n时，判断 a[i]*c[i] 之和是否等于sum。 代码： #include <iostream> #include <algorithm> using namespace std; int n, sum; int a[15],c[15]; bool vis[15]; void ini(){ for(int i=0;i<n;i++){ c[i]=1; for(int j=1;j<=i;j++){ c[i]=c[i]*(n-j)/j; } } } int calc(){ int res=0; for(int i=0;i<n;i++){ res+=a[i]*c[i]; } return res; } bool dfs(int pos){ if(pos==n)return calc()==sum; int csum=0; for(int i=0;i<pos;i++){ csum+=a[i]*c[i]; } if(csum>sum)return false; for(int i=1;i<=n;i++){ if(!vis[i]){ vis[i]=true; a[pos]=i; if(dfs(pos+1))return true; vis[i]=false; } } return false; } int main() { cin >> n >> sum; ini(); if(dfs(0)){ for(int i=0;i<n;i++){ cout<<a[i]<<" "; } } return 0; }

P1115 最大子段和 我理解的题目意思 给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大,输出最大值。 $$1≤n≤2×10^5，−10^4≤a_i​≤10^4$$解题思路 用贪心来做，初始化 ans 为 a1 。从前往后想，维护 bi 记录末尾是 ai 的最大连续子段和，从 a2 开始，设 c=ai+bi ,若 ai≤c ，则 bi=c ；若 ai>c ，则 bi=ai ，每次判断后，维护 ans 为 ans 和 bi 的较大者。 为什么可以这么做？ 第一个数为一个有效序列。 如果一个数加上上一个有效序列得到的结果比这个数大，那么该数也属于这个有效序列。 如果一个数加上上一个有效序列得到的结果比这个数小，那么这个数单独成为一个新的有效序列。 在执行上述处理的过程中实时更新当前有效序列的所有元素之和并取最大值。 代码： #include <iostream> using namespace std; int n,a,b,ans=-0x7fffffff; int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a; if(i==1)b=a; else { b=max(b+a,a); } ans=max(ans,b); } cout<<ans; return 0; } 参考 Arahc

P1114 “非常男女”计划 我理解的题目意思 给出一个数组由n个 0 或 1 组成，找出包含相同数目的0和1的最长子数组的长度。 $$1≤n≤10^5$$解题思路 一开始想的很简单，维护一个前缀和数组a记录到当前位置一共多少1，再用一个嵌套for循环遍历子数组，$a[j]-a[i-1]=(j-i+1)/2,j-i+1%2=0$ 满足的条件下输出最大的 j-i+1。注意到 $1≤n≤10^5$ ，O(n²)的复杂度下会超时，需要改换复杂度更低的方法。 O(n)解法：将女视为-1，将男视为1，问题转换为最长的和为0的子数组。用哈希表fs记录前缀和sum，先插入一个 fs[0]=0,再遍历查找是否有 fs[i]=sum ,若有则输出最大的 i-fs[sum] ,否则插入 fs[sum]=i 。 代码： #include <iostream> #include <unordered_map> using namespace std; int n; int main() { cin >> n; unordered_map<int,int>fp; fp[0]=0; int ans=0,sum=0; for (int i = 1; i <= n; i++) { int x; cin >> x; sum+=(x==1)?1:-1; if(fp.find(sum)!=fp.end()){ ans=max(ans,i-fp[sum]); } else{ fp[sum]=i; } } cout<<ans; return 0; }