网站设计包括哪些步骤,微信公众号可以做几个微网站吗,升级系统,碧桂园房地产最新消息POJ3617 Best Cow Line 题意 给定长度为N的字符串S#xff0c;要构造一个长度为N的字符串T。起初#xff0c;T是一个空串#xff0c;随后反复进行下列任意操作#xff1a; 从S的头部#xff08;或尾部#xff09;删除一个字符#xff0c;加到T的尾部 目标是构造字典序… POJ3617 Best Cow Line 题意 给定长度为N的字符串S要构造一个长度为N的字符串T。起初T是一个空串随后反复进行下列任意操作 从S的头部或尾部删除一个字符加到T的尾部 目标是构造字典序尽可能小的字符串T。 思路 贪心算法不断取S的开头和末尾中较小的一个字符放到T的末尾。但对于S的开头和末尾字符相同的情况下需要比较下一个字符大小这可以用如下算法实现 按照字典序比较S和S翻转后的字符串S1如果S较小则从S的开头取否则从末尾取。 代码 Source CodeProblem: 3617 User: liangrx06
Memory: 728K Time: 47MS
Language: G Result: Accepted
Source Code
#include iostream
#include cstdio
#include algorithm
using namespace std;#define N 2000int main(void)
{int n, i, j, k, ii, jj;char s[N1], t[N1];while (cin n){for (i0; in; i) {getchar();scanf(%c, s[i]);}s[i] \0;i 0;j n-1;k 0;while (i j) {ii i, jj j;while (ii jj) {if (s[ii] ! s[jj])break;ii ;jj --;}if (ii jj s[ii] s[jj]) {t[k] s[j];j --;}else {t[k] s[i];i ;}}t[k] \0;for (i 0; i n; i){printf(%c, t[i]);if (i % 80 79) printf(\n);}if (n % 80) printf(\n);}return 0;
} POJ3069 Saruman’s Army 题意 这个题是说给你n个点然后让你标记其中尽可能少的点使得n个点都处于被标记点左右不超过R的区间内。 思路 贪心法求解从左到右选择。 代码 Source CodeProblem: 3069 User: liangrx06
Memory: 748K Time: 125MS
Language: G Result: Accepted
Source Code
#include iostream
#include cstdio
#include algorithm
using namespace std;#define N 1000int main(void)
{int r, n, i, j;int pos[N], res;while (cin r n) {if (r -1 n -1)break;for (i0; in; i)cin pos[i];sort(pos, posn);res 0;i 0;while (i n) {j i1;while (j n pos[j] - pos[i] r)j ;j --;i j1;while (i n pos[i] - pos[j] r)i ;res ;}cout res endl;}return 0;
} POJ3253 Fence Repair 题意 有一个农夫要把一个木板钜成几块给定长度的小木板每次锯都要收取一定费用这个费用就是当前锯的这个木版的长度。给定各个要求的小木板的长度及小木板的个数n求最小费用。 提示 以 3 5 8 5 为例 先从无限长的木板上锯下长度为 21 的木板花费 21 再从长度为21的木板上锯下长度为5的木板花费5 再从长度为16的木板上锯下长度为8的木板花费8 总花费 2158 34 思路 利用Huffman思想要使总费用最小那么每次只选取最小长度的两块木板相加再把这些“和”累加到总费用中即可 本题虽然利用了Huffman思想但是直接用HuffmanTree做会超时可以用优先队列做 代码 Source CodeProblem: 3253 User: liangrx06
Memory: 1184K Time: 219MS
Language: C Result: Accepted
Source Code
#include iostream
#include cstdio
#include algorithm
#include set
using namespace std;int main(void)
{int n, i;long long x, sum;multiset long long plank;while (cin n){for (i0; in; i) {cin x;plank.insert(x);}sum 0;while (plank.size() 1){x *(plank.begin()) *(plank.begin());sum x;plank.erase(plank.begin());plank.erase(plank.begin());plank.insert(x);}cout sum endl;plank.clear();}return 0;
} POJ2393 Yogurt factory 题意 有n周第i周需要向外供货yi生产1单位成本ci。若非本周生产的货物不在本周销售需要贮藏1单位贮藏一周需要花费s。问n周供货供需花费多少钱成本和贮藏费。 思路 贪心我们用minc记录当前的最小单价然后以最小单价买入这个最小单价要么是现在的单价要么是之前的最小单价贮藏费。minc中被替换掉的值是不可能是以后的最小单价的。因为现在被替换同时上若干个s之后它还是会比现在替换它的那个值大。 代码 Source CodeProblem: 2393 User: liangrx06
Memory: 132K Time: 16MS
Language: C Result: Accepted
Source Code
#includeiostream
using namespace std;int main()
{int n, s, minc 9999;scanf(%d %d, n, s);long long sum 0;while(n --){int c, y;scanf(%d %d, c, y);if(c minc s)c minc s;minc c;sum c * y;}printf(%lld\n, sum);return 0;
} POJ1017 Packets 题意 问题描述 一个工厂制造的产品形状都是长方体它们的高度都是h长和宽都相等一共有六个 型号他们的长宽分别为 1*1, 2*2, 3*3, 4*4, 5*5, 6*6. 这些产品通常使用一个 6*6*h 的长方体包裹包装然后邮寄给客户。因为邮费很贵所以工厂要想方设法的减小每个订单运送时的 包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由 你来设计。 输入数据 输入文件包括几行每一行代表一个订单。每个订单里的一行包括六个整数中间用空 格隔开分别为 1*1 至6*6 这六种产品的数量。输入文件将以 6 个0 组成的一行结尾。 输出要求 除了输入的最后一行6 个0 以外输入文件里每一行对应着输出文件的一行每一行输 出一个整数代表对应的订单所需的最小包裹数。 输入样例 0 0 4 0 0 1 7 5 1 0 0 0 0 0 0 0 0 0 输出样例 2 1 思路 这个问题描述得比较清楚我们在这里只解释一下输入输出样例共有两组有效输入 第一组表示有4 个3*3 的产品和一个6*6 的产品此时4 个 3*3 的产品占用一个箱子另外 一个 6*6 的产品占用 1 个箱子所以箱子数是 2第二组表示有7 个 1*1 的产品5 个 2*2 的产品和1 个 3*3 的产品我们可以把他们统统放在一个箱子中所以输出是1。 分析六个型号的产品占用箱子的具体情况如下6*6的产品每个会占用一个完整的箱 子并且没有空余空间5*5 的产品每个占用一个新的箱子并且留下 11 个可以盛放 1*1 的产品的空余空间4*4 的产品每个占用一个新的箱子并且留下5 个可以盛放2*2 的产品 的空余空间3*3 的产品情况比较复杂首先3*3 的产品不能放在原来盛有5*5 或者4*4 的箱子中那么必须为3*3 的产品另开新的箱子新开的箱子数目等于3*3 的产品的数目除以 4 向上取整同时我们需要讨论为3*3 的产品新开箱子时剩余的空间可以盛放多少2*2 和 1*1 的产品这里如果有空间可以盛放2*2 的产品我们就将它计入2*2 的空余空间等到 2*2 的产品全部装完如果还有2*2 的空间剩余再将它们转换成 1*1 的剩余空间。我们 可以分情况讨论为3*3 的产品打开的新箱子中剩余的空位共为四种情况第一种3*3 的 产品的数目正好是4 的倍数所以没有空余空间第二种3*3 的产品数目是4 的倍数加1 这时还剩 5 个2*2 的空位和7 个 1*1 的空位第三种3*3 的产品数目是4 的倍数加2这时还剩3 个2*2 的空位和6 个 1*1 的空位第四种3*3 的产品数目是4的倍数加3这时 还剩 1 个 2*2 的空位和5 个 1*1 的空位处理完3*3 的产品就可以比较一下剩余的2*2 的空位和2*2 产品的数目如果产品数目多就将2*2 的空位全部填满再为2*2 的产品打开新箱子同时计算新箱子中 1*1 的空位如果剩余空位多就将2*2 的产品全部填入2*2的空位再将剩余的 2*2 的空位转换成 1*1 的空位最后处理 1*1 的产品比较一下 1*1的空位与1*1 的产品数目如果空位多将1*1 的产品全部填入空位否则先将1*1 的空位填满然后再为 1*1 的产品打开新的箱子。 代码 Source CodeProblem: 1017 User: liangrx06
Memory: 132K Time: 16MS
Language: C Result: Accepted
Source Code
#include iostream
#include cstdio
#include algorithm
using namespace std;bool input(int a[])
{bool flag false;for (int i 1; i 6; i ) {scanf(%d, a[i]);if (a[i] ! 0) flag true;}return flag;
}int main(void)
{int a[7];int i, k, m, res;while (input(a)) {res 0;for (i 6; i 1; i --) {k (6/i)*(6/i);//每个包裹能放的第i个产品的数量m a[i]/k;//需要的包裹数量a[i] % k;int n1 6*6*m - i*i*m*k;//剩下多少个1*1if (a[i]) n1 6*6 - i*i*a[i];if (i 3 || i 4) {int n2 0;//剩下多少个2*2if (i 4)n2 5*m;else if (i 3 a[i])n2 (4-a[i])*2 - 1;if (n2 a[2])n2 a[2];a[2] - n2;//printf(n1%d, n2%d\n, n1, n2);n1 - 2*2*n2;//printf(n1%d, n2%d\n, n1, n2);}if ( i 2 i 5 ) {if (n1 a[1])n1 a[1];a[1] - n1;}//for (int x 1; x 6; x )// printf(%d , a[x]);//printf(\n);res m;if (a[i])res ;a[i] 0;}printf(%d\n, res);}return 0;
} POJ3040 Allowance 题意 有N种不同面额的纸币你雇佣的一个人每次支付至少C圆。每种纸币的面额大小为V每种纸币的大小成整倍数关系这是结题的关键张数为B问你最多能支付多少次 思路 将V从小到大进行一个排列 1.先把大于C元的纸币用了进行一个计数 2.再从大的纸币进行抓取抓得越多越好但要小于等于C如果等于C进行一个计数如果小于C再将纸币从小的抓取大于C进行一个计数。因为纸币是成倍数关系的你最大的纸币面额比前面所有纸币面额加起来都大。 3.最后进行一个支付情况的总加意思是你后面还能像这第2步这样支付方案的个数然后再从第2步开始直到不能支付。 代码 Source CodeProblem: 3040 User: liangrx06
Memory: 212K Time: 16MS
Language: C Result: Accepted
Source Code
#include iostream
#include cstdio
#include cstring
#include algorithm
using namespace std;const int N 20;struct Coin {int v, b;
};bool cmp(const Coin x, const Coin y)
{return x.v y.v;
}int n, c;
int m[N];
Coin coin[N];int sum;
bool choose(int i)
{m[i] sum / coin[i].v;if (m[i] coin[i].b)m[i] coin[i].b;sum - m[i]*coin[i].v;if (sum 0)return true;if (i 0 || choose(i-1) false) {if (coin[i].b m[i]) {sum - coin[i].v;m[i] ;return (sum 0);}return false;}return true;
}bool canPay()
{memset(m, 0, sizeof(m));sum c;return choose(n-1);
}int main(void)
{int i;cin n c;for (i 0; i n; i )cin coin[i].v coin[i].b;sort(coin, coinn, cmp);int res 0;while (canPay()) {int k (int)1e9;//for (i 0; i n; i )// printf(%d , m[i]);//printf(\n);for (i 0; i n; i ) {if (m[i] 0) {int t coin[i].b / m[i];k (t k) ? t : k;}}for (i 0; i n; i ) {if (m[i] 0) {coin[i].b - m[i] * k;}}res k;//break;}printf(%d\n, res);return 0;
} POJ1862 Stripies 题意 科学家发现一种奇怪的玩意他们有重量weight如果他们碰在一起总重变成2*sqrt(m1*m2)。要求出最终的重量的最小值。 思路 试一下就可以发现对重量较大的先碰可以对其多次sqrt使得最后的结果最小。 代码 Source CodeProblem: 1862 User: liangrx06
Memory: 220K Time: 16MS
Language: C Result: Accepted
Source Code
#include iostream
#include cstdio
#include cmath
#include algorithm
using namespace std;const int N 10000;int n;
double a[N];void input()
{cin n;for (int i 0; i n; i ) {cin a[i];}
}double coll(double x, double y)
{return 2*sqrt(x*y);
}double solve()
{sort(a, an);for (int i n-2; i 0; i --)a[i] coll(a[i], a[i1]);return a[0];
}int main(void)
{input();double res solve();printf(%.3lf\n, res);return 0;
} POJ3262 Protecting the Flowers 题意 有n个牛在FJ的花园乱吃。 所以FJ要赶他们回牛棚。 每个牛在被赶走之前每秒吃Di个花朵。赶它回去FJ来回要花的总时间是Ti×2。在被赶走的过程中被赶走的牛就不能乱吃。 思路 贪心策略对牛进行排序排序的标准是假设牛A与牛B要选一头赶走我们首先要选择破坏最大的一头牛赶走留破坏小的牛。他们的破坏着呢麽计算呢假设先赶走牛A那么牛B造成的损失是2×TA×DB先赶走牛B那么牛A造成的损失是2×TA×DB所以只要判断TA×DB与TA×DB谁大就知道该先赶走谁了所以数组排序的标准就是—Ti×DjTj×Di。 代码 Source CodeProblem: 3262 User: liangrx06
Memory: 1780K Time: 141MS
Language: C Result: Accepted
Source Code
#include iostream
#include cstdio
#include algorithm
using namespace std;const int N 100000;struct Cow {int t, d;double v;
};int n;
Cow cow[N];void input()
{cin n;for (int i 0; i n; i ) {scanf(%d%d, cow[i].t, cow[i].d);cow[i].v (double)(cow[i].d)/(double)(cow[i].t);}
}bool cmp(const Cow x, const Cow y)
{return x.v y.v;
}void solve()
{sort(cow, cown, cmp);long long res 0;int time 0;res time * cow[0].d;for (int i 1; i n; i ) {time 2*cow[i-1].t;res time * cow[i].d;}printf(%lld\n, res);
}int main(void)
{input();solve();return 0;
} 转载于:https://www.cnblogs.com/liangrx06/p/5083767.html
