目录
1371A. Magical Sticks
1371B. Magical Calendar
1371C. A Cookie for You
1371DD. Grid-00100
1371E1. Asterism (Easy Version)
题意：给N个长度为1~N的木棒，木棒可以拼接在一起。问最多可以拼接出多少根长度相等的木棒。
思路：全拼成长度N，1和N-1拼，2和N-2拼。
代码：
int main(){ int t; scanf("%d", &t); while(t--){ int n; scanf("%d", &n); int ans = 1; n --; ans += n / 2; cout << ans << endl; } return 0; }题意：可以规定每周的天数为1~R中的任意一个数。现在要选择连续的N天，在日历上将这N天涂上颜色。问对于1~R不同的天数，总共有多少种不一样的形状（被涂上颜色的格子组成的多边形）。
思路：假设选择本周天数为X天，若X>=N，则N天必定只能涂在日历上的同一行，所有的形状都相同。假设X<N，则N天必定涂在两周以上，那么第一周的选择可以是只涂最后一格、只涂最后两格.....涂满整周，每种涂法形状都不同，因此答案为X。所以总的不一样形状为：1+2+3+4+...+X。判断R与N的大小关系，计算两种关系下的方案数。
代码：
#define LL long long int main(){ int t; scanf("%d", &t); while(t--){ LL n, r; cin >> n >> r; if(n <= r){ printf("%lld\n", n * (n - 1) / 2 + 1); } else{ printf("%lld\n", r * (r + 1) / 2); } } return 0; }题意：有V个vanilla cookies和C个chocolate cookies，现在要邀请N个性格属性为1的客人和M个性格属性为2的客人。性格属性为1的客人吃cookie的习惯是：如果 V > C 则吃一个vanilla cookie，否则吃一个chocolate cookie。性格属性为2的客人的习惯与属性1的相反。现在给定V、C、N、M，问能否安排客人前来聚会的顺序，使得每一个人都有cookie吃。
思路：属性1的客人只吃多的，属性2的客人只吃少的。因此将少的cookie直接全部给属性2的客人吃明显是最优的。因为如果先安排了属性1的客人进场，有可能属性1的客人会影响到min(V, C)。因此邀请客人的顺序必定是先邀请M个属性2客人，再邀请N个属性1客人。为了使得所有客人都有cookie吃，所以 min(V, C) >= M 满足属性2客人，其余饼干给属性1客人，至少要剩下N块。所以总的要求为 : min(V, C) >= M && V + C >= N + M。
代码：
int main(){ int t; scanf("%d", &t); while(t--){ LL a, b, n, m; cin >> a >> b >> n >> m; if(min(a, b) >= m && n + m <= a + b) printf("Yes\n"); else printf("No\n"); } return 0; }题意：默认给定一个N*N的 0 矩阵，现在要将 K 个0替换为1。定义矩阵A的一个属性F(A)，Ri，Ci，Ri 为01矩阵第 i 行中 1 的数量。Ci 为01矩阵第 i 列中 1 的数量 。，要求构造一个F最小的01矩阵。输出F与01矩阵的样子。
思路：很明显每次换0为1的时候增加的都是不同行不同列是最优的。如果当N==K时，很容易想到对角线的0全换成1是最优的，当K更大的时候，同样是依照对角线的规则去换0为1，就始终能够保持最优的F。因为此时每一行的最大最小差值小于等于1，列也类似。以N=4的矩阵为例，依照下图标号顺序进行01替换。
代码：
int main(){ int t; scanf("%d", &t); while(t--){ int n, k; scanf("%d %d", &n, &k); vector<int> a[n]; for(int i = 0; i < n; ++i) a[i].resize(n); int x, y; x = y = 0; int cnt = 0; int minr, minc, maxr, maxc; minr = minc = inf; maxr = maxc = 0; vector<int> R(n), C(n); while(k--){ a[x][y] = 1; R[x]++; C[y]++; x++; y++; cnt++; x %= n; y %= n; if(cnt == n) y++, y %= n, cnt = 0; } for(int i = 0; i < n; ++i){ minr = min(minr, R[i]); maxr = max(maxr, R[i]); minc = min(minc, C[i]); maxc = max(maxc, C[i]); } int r, c; r = (maxr - minr) * (maxr - minr); c = (maxc - minc) * (maxc - minc); printf("%d\n", r + c); for(int i = 0; i < n; ++i){ for(int j = 0; j < n; ++j){ printf("%d", a[i][j]); } printf("\n"); } } return 0; }题意：yuzu有X个糖果，有N个敌人，每个敌人有Ai个糖果。现在yuzu决定了一个排列P。决定完之后她会和N个敌人战斗，如果第P[i]个敌人的糖果数量A[P[i]] <= X，则战斗胜利，yuzu获得1个糖果，否则的话yuzu什么也没有获得。yuzu想要赢得所有战斗，那么有多少个满足要求的排列。 以上的问题十分简单，所以yuzu的朋友Aoi在基础上提出了新问题。定义一个函数F。F(X)是对于X满足的排列的数量。输入中会给定一个N，数组A，以及一个质数prim。定义X是good的如果F(X)不被prim整除。输出所有是good的X。
思路：如果初始糖果数量 X < Max(A[i]) - N + 1 就不可能打败所有敌人，F(X) = 0，0 % p == 0，X非good。如果初始糖果数量X >= Max(A[i])，则所有敌人不管是什么顺序都必定可以全部打败，F(X) = N!，由于 ，因此N！% p 0。所以只需要判断中间的所有数是否满足要求即可。具体过程见代码注释。
代码：
#define LL long long vector<int> a; int n, p; inline bool check(int x){ int l = 0; LL ans = 1; int cnt = 0; while(l < n){ int r = l; while(r < n && a[r] <= x) cnt++, r++; //当前可以击败cnt个 if(l == r){ if(cnt == 0) return 0;//一个也无法击败 ans *= cnt;//cnt个可以击败，当前的选择就有cnt种 x++;//击败一个敌人X++ cnt--; ans %= p;//如果%p == 0，ans从此始终为0. } else{ ans *= cnt; x++; cnt--; ans %= p; } l = r; } while(cnt){//还剩下cnt个敌人没有打败且所有敌人都必定可以打败，排列种类为cnt! ans *= cnt; ans %= p; cnt--; } return ans != 0;//ans不等于0则说明ans不为p的倍数，如果为p的倍数则在过程中必定%p = 0 } int main(){ scanf("%d %d", &n, &p); a.resize(n); int Max = 0; for(int i = 0; i < n; ++i){ scanf("%d", &a[i]); Max = max(Max, a[i]); } sort(a.begin(), a.end()); vector<int> ans; for(int i = Max - N + 1; i < Max; ++i) if(check(i)) ans.pb(i); printf("%d\n", ans.size()); for(int i = 0; i < ans.size(); ++i) printf("%d%c", ans[i], i == ans.size() - 1 ? '\n' : ' '); return 0; }
