7-2 分香肠
有 N 根完全相同的香肠， 现在要平均分给 M 个客人。 问最少需要切几刀才能将其平均分给客人（不能多个香肠一起切）。
输入格式:两个整数 N(1≤N≤105) 和 M(1≤M≤105)
输出格式:一个整数，表示要切的刀数
输入样例:在这里给出一组输入。例如：
2 6
输出样例:在这里给出相应的输出。例如：
4
可以看出，以下切割策略是最佳的。
我们将香肠排列成一条直线，一条接着一条（从而获得由N个较短线段组成的线段）。将这条线切割成M个相等的线段可以得到所需的解。虽然我们在概念上做的是M-1切，但其中一些不是真正的切，而是落在香肠之间（较短的线段）。
例如，对于两条香肠和四个品尝者，第一次切是真实的，将第一条香肠分成两半，第二次切不是真实的，因为它实际上在两条香肠之间，第三次切是真的，将第二条香肠分成一半。
因此，我们可以简单地使用for循环来检查，对于对于每一次切割，它是真切割还是原本中间就是分开的。
另外，有一个明确的公式：解=M-gcd(N，M) （gcd即大公约数）
#includeusing namespace std;
int main()
{
int m, n;
cin >>n >>m;
cout<< (m - gcd(m,n));
return 0;
}
7-3 h0145. 会议安排
学校的礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学校礼堂的活动，每个时间最多安排一个活动。现在小刘有一些活动计划的时间表，他想尽可能的安排更多的活动，请问他该如何安排。
输入格式:第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是一个整数n(1随后的n行，每行有两个正整数Bi,Ei(0<=Bi,Ei<10000),分别表示第i个活动的起始与结束时间（Bi<=Ei)
输出格式:对于每一组输入，输出最多能够安排的活动数量。
每组的输出占一行
输入样例:在这里给出一组输入。例如：
2
2
1 10
10 11
3
1 10
9 11
11 20
输出样例:在这里给出相应的输出。例如：
2
2
利用贪心，将全部活动的起始时间从大到小排序，如果一个活动的开始时间大于当前正在进行的活动的开始时间并且结束时间小于当前正在进行的活动的结束时间，那么就让该活动替换当前正在进行的活动。如果一个活动的开始时间大于当前正在进行的活动的结束时间，那么将该活动安排上。
#includeusing namespace std;
pairp[10003];
bool cmp(paira, pairb)
{
return a.first< b.first;
}
int main()
{
int m;
cin >>m;
for (int i = 1; i<= m; i++)
{
int n,nowed,nowst,ans=1; cin >>n;
for (int j = 1; j<= n; j++)
{
int st, ed;
cin >>st >>ed;
p[j].first = st;
p[j].second = ed;
}
sort(p + 1, p + 1 + n, cmp);
nowed = p[1].second,nowst=p[1].first;
for (int j = 2; j<= n; j++)
{
if (p[j].second<=nowed && p[j].first>=nowst)
{
nowed = p[j].second;
nowst = p[j].first;
continue;
}
if (p[j].first >= nowed)
{
nowed = p[j].second;
nowst = p[j].first;
ans++;
}
}
cout<< ans<< endl;
}
return 0;
}
7-4 神秘密码
传说二战时X国收到了上帝的一串密码，只有解开密码，才能阻止战争的继续进行，世界才会恢复和平。解开密码的第一道工序就是解压缩密码，上帝对于连续的若干个相同的子串"X"会压缩为"[DX]"的形式(D是一个整数且1<=D<=99),比如说字符串"CBCBCBCB"就压缩为"[4CB]"或者"[2[2CB]]",类似于后面这种压缩之后再压缩的称为二重压缩。如果是"[2[2[2CB]]]"则是三重的。现在我们给你上帝发送的密码，请你对其进行解压缩。
输入格式:一个字符串。
输出格式:一个字符串。
输入样例:在这里给出一组输入。例如：
AC[3FUN]
输出样例:在这里给出相应的输出。例如：
ACFUNFUNFUN
【数据范围】
解压后的字符串长度在 20000 以内，最多只有十重压缩。保证只包含数字、大写字母、[和 ]。
这里就引用大佬的题解了，有图写的非常好。这道题刚看到我还以为是括号匹配问题......
P1928 外星密码 题解 - mutton 的博客 - 洛谷博客 (luogu.com.cn)
非递归题解
题解 P1928 【外星密码】 - Drifterming 的博客 - 洛谷博客 (luogu.com.cn)
#includeusing namespace std;
string unzip()
{
string str="",temp="";
int num;
char ch;
while(cin>>ch)
{
if(ch=='[')
{
cin>>num;
temp = unzip();
while(num--)
str+=temp;
}
else if(ch==']')
return str;
else str+=ch;
}
}
int main()
{
cout<
P1080 [NOIP2012 提高组] 国王游戏
题目描述恰逢 H 国国庆，国王邀请 nn 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 nn 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。
输入格式第一行包含一个整数 nn，表示大臣的人数。
第二行包含两个整数 aa 和 bb，之间用一个空格隔开，分别表示国王左手和右手上的整数。
接下来 nn 行，每行包含两个整数 aa 和 bb，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。
输出格式一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
输入输出样例输入 #1复制
3
1 1
2 3
7 4
4 6
输出 #1复制
2
说明/提示【输入输出样例说明】
按 11、22、33 这样排列队伍，获得奖赏最多的大臣所获得金币数为 22；
按 11、33、22 这样排列队伍，获得奖赏最多的大臣所获得金币数为 22；
按 22、11、33 这样排列队伍，获得奖赏最多的大臣所获得金币数为 22；
按22、33、11这样排列队伍，获得奖赏最多的大臣所获得金币数为 99；
按 33、11、22这样排列队伍，获得奖赏最多的大臣所获得金币数为 22；
按33、22、11 这样排列队伍，获得奖赏最多的大臣所获得金币数为 99。
因此，奖赏最多的大臣最少获得 22 个金币，答案输出 22。
【数据范围】
对于 20\%20% 的数据，有 1≤ n≤ 10,0< a,b< 81≤n≤10,0
对于 40\%40% 的数据，有1≤ n≤20,0< a,b< 81≤n≤20,0
对于 60\%60% 的数据，有 1≤ n≤1001≤n≤100；
对于 60\%60% 的数据，保证答案不超过 10^9109；
对于 100\%100% 的数据，有 1 ≤ n ≤1,000,0< a,b< 100001≤n≤1,000,0
NOIP 2012 提高组 第一天 第二题
国王游戏——又是一道证明题 - 凤翔先生的博客 - 洛谷博客 (luogu.com.cn)
【NOIP2012 提高组 day1】国王游戏 题解 - Boring__Zheng 的博客 - 洛谷博客 (luogu.com.cn)
#includeusing namespace std;
int len=1,answer[40000003];
void change(int x) {
for (int i = 1; i<= len; i++) answer[i] *= x;
for (int i = 1; i<= len + 15; i++) answer[i + 1] += answer[i] / 10, answer[i] %= 10;
for (int i = len + 15; i >= len; i--)if (answer[i] != 0) len = i;
return;
}
void dis(int x) {
int count = 0;
for (int i = len; i >= 1; i--) {
count = count * 10 + answer[i];
if (count< x) { answer[i] = 0; continue; }
answer[i] = count / x; count %= x;
}
for (int i = len; i >= 1; i--) if (answer[i] != 0) { len = i; break; }
return;
}
int main() {
int n,maxn,item,a,b;
cin >>n;
answer[1] = 1;
for (int i = 1; i<= n + 1; i++) {
int x, y; cin >>x >>y;
change(x); item = x * y;
if (item >maxn && i != 1) maxn = item, a = y, b = x;
}
dis(b * a);
if (answer[len] == 0) answer[len] = 1;//最少为1
for (int i = len; i >= 1; i--) cout<< answer[i];
return 0;
}
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享文章：预备队第三次双周赛-创新互联
网页URL：http://cdkjz.cn/article/djosds.html
