打卡～
Easy（250pts）：
题目大意：rating2200及以上和2200以下的颜色是不一样的（我就是属于那个颜色比较菜的），有个人初始rating为X，然后每一场比赛他的rating如果增加就会加D[i]，如果减就会减D[i]，但是如果rating小于0了就变成0，这个人不太喜欢比较厉害的颜色，所以他不能连续两次rating大于等于2200，求颜色变化的最多个数，保证比赛最多50场，D[i]<=10^9。
这套题还是很难的，所以我们来好好分析。
首先，样例0告诉我们贪心什么都是假的，不存在的，所以只能DP咯。
我们考虑f[i][j]表示第i场比赛打完rating是j的颜色变化最大值，
如果掉rating，那么最优值就是f[i+1][max(j-D[i],0)]，
如果涨rating，又没涨到2200，那么最优值就是f[i+1][j+D[i]]，
如果涨rating而且涨到2200，那么如果这是最后一场比赛直接返回1，不然就一定要求j+D[i]-D[i+1]<2200，于是最优值就是f[i+2][j+D[i]-D[i+1]]+2，
这样就能DP了，然而D[i]的范围太大了，显然会爆炸。
我们考虑如何减少状态数，于是我们发现当rating高于2200的时候，下一场必须跌而且必须跌到2200以下，
所以其实如果rating大于2200，那么我们根本不用关心他的rating是多少，
这样就可以省好多好多状态啦，然后直接dp就好了。
时间复杂度O(n*w)，代码如下：
1 #include <bits/stdc++.h> 2 using namespace std; 3 int n; 4 int f[57][2207]; 5 class TypoCoderDiv1 6 { 7 public: 8 int getmax(vector <int> D, int X) 9 { 10 n=D.size(); 11 memset(f,0,sizeof(f)); 12 for (int i=n-1;i>=0;i--) 13 for (int j=0;j<2200;j++) 14 { 15 if (j+D[i]<2200) f[i][j]=f[i+1][j+D[i]]; else 16 if (i+1==n) f[i][j]=1; else 17 if (j+D[i]-D[i+1]<2200) f[i][j]=f[i+2][max(0,j+D[i]-D[i+1])]+2; 18 f[i][j]=max(f[i][j],f[i+1][max(0,j-D[i])]); 19 } 20 return f[0][X]; 21 } 22 };
Medium（550pts）：
题目大意：有2N个长方形，每个长方形的长和宽都给定，现在要使得这些长方形恰好分成两组，每组N个长方形，把一组堆在桌上，最大重合面积分别为S1，S2，要求输出S1+S2的最大值，数据满足N<=100000，长宽都在10^9范围内。
种子要先预处理出来，这个没有异议的吧。。。
我们先考虑一个比较简化的问题，我们不考虑长方形的分组，只考虑N个长方形怎么叠在一起S最大。
显然我们需要把这N个长方形按照一个边角对齐，然而只看出这一个性质的话只能过div2的medium，
我们还需要看出，对于每个长方形一定是每个长方形较短的边堆放在一个方向，较长的边堆放在另一个方向，我们来证明一下。
假设两个长方形，第一个为x*y(x<=y)，第二个为z*w(z<=w)，并且有x<=z，
如果较短的边都在一个方向，那么S=min(x,z)*min(y,w)=x*min(y,w)，
如果较短的边不在一个方向，那么S=min(x,w)*min(y,z)=x*min(y,z)，
显然有min(y,w)>=min(y,z)，
所以这个结论是正确的～～～
接下来，我们来考虑如何分组，
通过上面两个式子会发现，不管怎么分组，最短的那条x边一定会成为某个S的一条边，
于是我们先令所有长方形的x<=y，然后将所有长方形按照x从小到大排序，
那么x[1]一定会被选中，我们假设另一个会被选中的x边为x[i]，
我们先枚举i，那么显然1～i-1都被分在了一组，还剩下i+1~2*N没有被分组，一共2*N-i个长方形。
这2*N-i个长方形中y最小的那个长方形的y值设为y0，于是y0要么和x[1]一组，要么和x[i]一组，
由于我们要求S的和最大，那么剩下的一个y显然要取那2*N-i个长方形中y值最大的那个y值。
于是经过n次的枚举，我们得到了最后的答案。
由于n<=100000，直接O(n^2)暴力显然不行（听官方题解说暴力是O(n^2logn)），所以我们需要一个随便什么数据结构来维护一下就可以了。
当然最简单的方法就是直接上两个multiset就完事啦～
时间复杂度O(nlogn)，代码如下：
1 #include <bits/stdc++.h> 2 #define Maxn 200007 3 #define inf 10000000007 4 using namespace std; 5 int n; 6 long long x[Maxn],y[Maxn]; 7 pair<long long,long long> a[Maxn]; 8 multiset<long long> st1,st2; 9 multiset<long long>::iterator it; 10 class PilingRectsDiv1 11 { 12 public: 13 long long getmax(int N, vector <int> XS, vector <int> YS, int XA, int XB, int XC, int YA, int YB, int YC) 14 { 15 n=N; 16 for (int i=0;i<XS.size();i++) x[i]=XS[i],y[i]=YS[i]; 17 for (int i=XS.size();i<2*n;i++) x[i]=(1LL*x[i-1]*XA+XB)%XC+1,y[i]=(1LL*y[i-1]*YA+YB)%YC+1; 18 for (int i=1;i<=2*n;i++) a[i]=make_pair(min(x[i-1],y[i-1]),max(x[i-1],y[i-1])); 19 sort(a+1,a+2*n+1); 20 //a[1].x must be chosen 21 st1.clear(),st2.clear(); 22 for (int i=1;i<=n;i++) st1.insert(a[i].second),st2.insert(a[i+n].second); 23 long long ans=0; 24 for (int i=n;i;i--) 25 { 26 //there will be only n kind of plans 27 //i means that the ith block has the smallest x 28 ans=max(ans,1LL*a[1].first*(*st1.begin())+1LL*a[i+1].first*(*st2.begin())); 29 st1.erase(st1.find(a[i].second)),st2.insert(a[i].second); 30 st1.insert(*st2.begin()),st2.erase(st2.begin()); 31 } 32 st1.clear(),st2.clear(); 33 for (int i=1;i<=n;i++) st1.insert(a[i].second),st2.insert(a[i+n].second); 34 for (int i=n;i;i--) 35 { 36 ans=max(ans,1LL*a[1].first*(*st1.begin())+1LL*a[i+1].first*(*st2.begin())); 37 st1.erase(st1.find(a[i].second)),st2.insert(a[i].second); 38 it=st2.end();--it; 39 st1.insert(*it),st2.erase(it); 40 } 41 return ans; 42 } 43 };
Hard（1000pts）：
这应该是我做到的SRM里面第一个分值1000分的hard题，好神哪>_<
这个题是一个超级帅无敌的公式题，但是似乎官方题解中并没有把推导过程写清楚。
题目大意：有一个N*M的方格组成的小黑盒，每个黑盒中的格子都是一块倾斜45度的玻璃板（有两个方向），现在从外围2(N+M)个格子打入激光，激光一定会退出小黑盒，这样我们得到了2(N+M)个格子和它们对应的出口。现在从小黑盒中任意去掉一块玻璃板，从外围2(N+M)个格子打入激光，发现它们对应的出口完全没有变化。求满足题意的玻璃板构成的方案数。数据满足1<=N,M<=200。
考虑对于每一块玻璃的每一个面，如果它被同一道激光照射了两次，那么说明激光形成了一个圈，由光路可逆，这光线就出不来了。。。
所以每一面最多被照射过一次，所以每一块玻璃被照射过了0次或者1次或者2次。
我们定义如果有一部分玻璃形成了一块封闭区域，而且光线如果在里面会形成循环，那么定义这一组玻璃为一个圈，
如果某一块玻璃板旋转90度后能组成一个圈，那么定义这组玻璃是一个半圈。
如果一块玻璃板被照射过了0次，直接拿走它显然不会造成任何问题，所以我们把它拿(chi)走(diao)。
如果一块玻璃板被照射了1次，我们假设光线从上射入，从左反射出。
那么我们将这块玻璃拿走，光线穿过方格到下方，通过一系列变化来到右方，从右往左穿方格。
也就是说，这块玻璃在一个圈中。
如果一块玻璃被照射了2次，我们假设光线从上射入，从左反射出，再到下方，从下进入，从右反射出。
我们将这块玻璃拿走，光线从上射入，从下穿过，再来到左方，从右侧穿过。
也就是说，如果把这块玻璃旋转90度，那么它在一个圈中，换句话说这块玻璃在一个半圈中。
问题转化为了，有多少方案使得图中存在圈或者半圈。
随手画几个圈和半圈就能够发现，一个图中如果有圈，就一定存在样例0中的5个基本图形。
问题转化为了，有多少方案使得图中至少存在5个基本图形之一。
到这里官方题解写了这么一句话：“The approach here is to do further analysis and find the following formula”，然后给出了一个公式。。。
这个公式反正我是不会证明的，也许找规律能找出来吧。。。
matthew99a对这个化简的问题使用了dp，但是我也没看懂，所以这里直接给出公式。（详见代码）
时间复杂度写什么啊。。。O(log(N*M))／O(N*M)，代码如下：
1 #include <bits/stdc++.h> 2 #define modp 1000000007 3 #define Maxn 4 using namespace std; 5 int power[40007]; 6 class BlackBoxDiv1 7 { 8 public: 9 int count(int N, int M) 10 { 11 power[0]=1; 12 for (int i=1;i<=M*N;i++) power[i]=(2LL*power[i-1])%modp; 13 long long ans=power[N*M]-1LL*power[N]*M*M%modp-1LL*power[M]*N*N%modp+modp+modp; 14 ans=(ans+1LL*(N-1)*(N-2)*(M-1)*(M-2)/2%modp+2LL*N*M*(N+M)%modp-5LL*N*M%modp+3*N+3*M-3+modp+modp+modp)%modp; 15 return ans; 16 } 17 };