B.魔法之森的蘑菇(二)
这题我当时想用的是二维前缀和，用暴力也可以。
这题的核心就是找到判断他是矩形的条件，不管是用前缀和还是用暴力，他为矩形的判断条件都是当一个矩形内' . '的个数和矩形的面积相等。
即有暴力解法：
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
using namespace std;
const int N = 41;int t,n,m,mi=-1000000;
char a[N][N],x;
int sum[N][N],p,q,w,o;//判断矩形内.的个数
int find(int i,int j,int k,int l){int ans=0;for(int x=i;x<=k;x++){for(int y=j;y<=l;y++){if(a[x][y]=='*'){break;}else{ans++;}}}return ans;
}int main(void){cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];} }for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int k=i;k<=n;k++){for(int l=j;l<=m;l++){if(find(i,j,k,l)==(k-i+1)*(l-j+1)){if(mi<find(i,j,k,l)){mi=find(i,j,k,l);p=i;q=j;w=k;o=l;}}}}}}cout<<p<<" "<<q<<" "<<w<<" "<<o<<endl;return 0;
}也有前缀和写法：
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
using namespace std;
const int N = 41;int t,n,m,mi=-1000000;
char a[N][N],x;
int s[N][N],p,q,w,o;int Sum(int x,int y,int x2,int y2){return s[x2][y2]-s[x-1][y2]-s[x2][y-1]+s[x-1][y-1];
}int main(void){cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}//构造差分数组for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]=='.'){s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+1;}else{s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];}}} //进行判断存在多大的矩形 int res=0,xx1,xx2,yy1,yy2;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int k=1;k<=n;k++){for(int l=1;l<=m;l++){if(Sum(i,j,k,l)==(k-i+1)*(l-j+1)){if(Sum(i,j,k,l)>res){res=Sum(i,j,k,l);xx1=i;yy1=j;xx2=k;yy2=l;}}}}}} cout<<xx1<<" "<<yy1<<" "<<xx2<<" "<<yy2<<endl;return 0;
} C.迷途之家的大贤者(二)
我当时写的时候一直被最后一个样例卡住，我属于绕弯子了，分了好多种情况，同时也是漏情况了，我的代码如下：
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <set>
#include <map>
using namespace std;
const int N = 1e5+10;int t,n,m,sum=0,s1,s2,x,s;
set<int> a,b;
map<int,int> mp;int main(void){cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>x;a.insert(x);mp[x]=1;}for(int i=1;i<=n;i++){cin>>x;b.insert(x);if(mp[x]==1){s++;mp[x]=2;}}s1=n-a.size();s2=n-b.size();if(s1>s2){if(s>s1-s2){s1=s1+(s-(s1-s2));cout<<s1<<endl;}else{cout<<s1<<endl;}}else if(s2>s1){if(s>s2-s1){s2=s2+(s-(s2-s1));cout<<s2<<endl;}else{cout<<s2<<endl;}}else{s1=s2+(s+1)/2;cout<<s1<<endl;}return 0;
} 有点想复杂了，但实际上我看的其他大佬写的，真的很巧妙qwq，请看vcr
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <set>
using namespace std;
const int N = 41;int t,n,m,mi=-1000000;
set<int> a,b;
int x;int main(void){cin.tie(0);cout.tie(0); cin>>n;for(int i=1;i<=n;i++){cin>>x;a.insert(x);}for(int i=1;i<=n;i++){cin>>x;b.insert(x);}int yy1=a.size();int yy2=b.size();int cnt=0;
//判断a，b他们相同的有几个，用cnt记录，同时把这两个都在对应容器中删去for(auto i:a){if(b.count(i)){yy1--;yy2--;cnt++;}}
//判断把相同元素加在哪边的容器，然后尽量让两边容器大小一样，这样能够确保删除的元素个数最少while(cnt--){if(yy1>=yy2){yy2++;}else{yy1++;}}
//yy1和yy2表示的是最终得到的a,b俩容器的元素的分布情况cout<<n-min(yy1,yy2);return 0;
}
D. 红魔馆的馆主(二)
我一开始有点无从下手，结果还真的不会写哈哈哈哈哈哈，我还得再练......
我看的题解的思路就是，先统计没有改变任何数之前，数组中有多少个元素能够和别的元素配对组成495的倍数，配对的方法：用两个指针，第一个指针i指向1-495，第二个指针j指向i-495，如果i和j存在，且乘积是495的倍数，分两种情况，当i和j相等时，个数其实是个，当i和j不相等时，个数是f[i]*f[j]。
然后再进行一个for循环，一个一个进行判断，元素+1之后会有几个数组中的元素的个数符合条件，如果比最开始的大，更新，恢复现场，再进行判断下一个........
直接上代码：
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <set>
using namespace std;
const int mod = 495;long long t,n,ans,f[510],x;long long count(){long long res=0;for(int i=0;i<mod;i++){for(int j=i;j<mod;j++){if(i*j%mod==0){if(i==j){res+=f[i]*(f[i]-1)/2;}else{res+=f[i]*f[j];}} }}return res;
}int main(void){cin.tie(0);cout.tie(0); cin>>n;for(int i=1;i<=n;i++){cin>>x;f[x%mod]++;}ans=count();for(int i=1;i<mod;i++){if(!f[i])continue;f[i]--;f[(i+1)%mod]++;ans=max(ans,count());f[i]++,f[(i+1)%mod]--;}cout<<ans<<endl;return 0;
}
