B. Two Cakes
传送门：http://codeforces.com/contest/911/problem/B
本题是一个数学问题。
有a个Ⅰ类球，b个Ⅱ类球；有n个盒子。将球放入盒子中，要求：
①所有的球均被放入盒子中；
②每一个盒子中至少有一个球；
③一个盒子里至多只能有一类球。
设将所有的球放入盒子后，每个盒子里至少有x个球。求x的最大值。
由上述规则可知，一个盒子或放入Ⅰ类球，或放入Ⅱ类球。设放入Ⅰ类球的盒子数为i，放入Ⅱ类球的盒子数为j，则：i+j=n。
于是，为使盒子中放入球的最小个数最大化，应尽量遵循平均性原则。于是，在放入Ⅰ类球的盒子中，每个盒子至少有[a/i]个球；在放入Ⅱ类球的盒子中，每个盒子至少有[b/j]个球。
于是，设cur(i)=min{[a/i],[b/j]}，则所求的x即为遍历i=1,2,...,n-1时，cur(i)取得的最大值。
参考程序如下：
#include <stdio.h> int min(int a, int b)
{
return a < b? a: b;
} int main(void)
{
int n, a, b;
scanf("%d%d%d", &n, &a, &b);
int x = ;
for (int i = ; i <= a && i < n; i++) {
int j = n - i;
int cur = min(a / i, b / j);
if (cur > x) x = cur;
}
printf("%d\n", x);
return ;
}
C. Three Garlands
传送门：http://codeforces.com/contest/911/problem/C
本题是一个数学问题。
给定三个正整数数k1,k2,k3，于是，对于给定的三个正整数x1,x2,x3，可以按照周期性规则，构成三个集合{x1+nk1|n=0,1,2,...},{x2+nk2|n=0,1,2,...},{x3+nk3|n=0,1,2,...}。现要求这三个集合的并集覆盖max{x1,x2,x3}及以后的所有自然数。试问对于给定的k1,k2,k3，是否存在一组x1,x2,x3，满足上述要求？
以下几种情形是满足要求的：
以下用“O”代表被数列中某一元素存在，“X”代表该元素不存在，则：
①若k1,k2,k3为{1,?,?}，则将出现“OOOO…”的情形，显然构成了连续的整数区间；
②若k1,k2,k3为{2,2,?}，则可以构造以下情形：
a.OXOXOXOX…
b.XOXOXOXO…
---------
OOOOOOOO…
如此，也可以构成了连续的整数区间；
③若k1,k2,k3为{3,3,3}，则可以构造以下情形：
a.OXXOXXOXX…
b.XOXXOXXOX…
c.XXOXXOXXO…
----------
OOOOOOOOO…
如此，也可以构成了连续的整数区间；
④除此之外，若k1,k2,k3为{4,4,2}，则可以构造以下情形：
a.OXXXOXXXO…
b.XXOXXXOXX…
c.XOXOXOXOX…
----------
OOOOOOOOO…
这里请关注情形④！！序列a、b恰好组成一个周期为2的序列“OXOXOXOXO…”。
除此之外，不存在满足条件的k1,k2,k3。
参考程序如下：
#include <stdio.h> int main(void)
{
int cnt[] = {};
for (int i = ; i < ; i++) {
int k;
scanf("%d", &k);
if (k <= ) cnt[k]++;
}
if (cnt[] >= || cnt[] >= || cnt[] == ||
cnt[] == && cnt[] == ) printf("YES\n");
else printf("NO\n");
return ;
}
D. Inversion Counting
传送门：http://codeforces.com/contest/911/problem/D
本题是一个序列上的问题——逆序对。
定义数列{ai|i=1,2,...,n}的逆序对如下：对于所有的1≤j<i≤n，若ai<aj，则<i,j>为一个逆序对。
于是，对于一个数列a[1..n]，给定m次操作。对于每一次操作，给定l,r(1≤l<r≤n)，将序列a[l..r]倒置。求倒置后的逆序对数——的奇偶性。
提到逆序对数，首先可以考虑——树状数组？归并排序？
然而，本题只需要求解逆序对数的奇偶性，于是设置一个0-1型变量flag，表示当前逆序对数的奇偶性。首先，计算初始序列的逆序对数。
之后，考虑某一次倒置操作：对于给定的l,r，记d=l-r+1，若倒置前序列a[l..r]的逆序对数为x，则倒置后序列的逆序对数为Cd2-x。于是，考虑Cd2的奇偶性即可。若这是一个奇数，则逆序对数的奇偶性变化；否则不变化。参考程序如下：
#include <stdio.h>
#include <stdbool.h>
#define MAX_N 2000 int a[MAX_N]; int main(void)
{
int n;
scanf("%d", &n);
for (int i = ; i < n; i++)
scanf("%d", &a[i]);
bool flag = ;
for (int i = ; i < n; i++) {
for (int j = ; j < i; j++) {
if (a[i] < a[j]) flag = !flag;
}
}
int m;
scanf("%d", &m);
while (m--) {
int l, r;
scanf("%d%d", &l, &r);
int d = r - l + ;
if (d & ) flag = !flag;
if (flag) printf("odd\n");
else printf("even\n");
}
return ;
}