A. 非常暴力枚举一下即可
#include<cstdio> #include<iostream> #include<string> #include<map> #include<algorithm> using namespace std; int main() { map<string,int>mp1,mp2; int n,i,j,k; cin>>n; string str; for(i=1;i<=n;i++){ cin>>str;mp1[str]++; } for(i=1;i<=n;i++){ cin>>str;mp2[str]++; } int ans=0; ans+=mp2["M"]+mp2["S"]+mp2["L"]-(min(mp1["M"],mp2["M"])+min(mp1["S"],mp2["S"])+min(mp1["L"],mp2["L"])); ans+=mp2["XS"]+mp2["XL"]-(min(mp1["XS"],mp2["XS"])+min(mp1["XL"],mp2["XL"])); ans+=mp2["XXS"]+mp2["XXL"]-(min(mp1["XXS"],mp2["XXS"])+min(mp1["XXL"],mp2["XXL"])); ans+=mp2["XXXS"]+mp2["XXXL"]-(min(mp1["XXXS"],mp2["XXXS"])+min(mp1["XXXL"],mp2["XXXL"])); cout<<ans<<endl; return 0; }B. 枚举在每个区间处加入新的标志改变亮灭即可，但是如何巧妙简洁地写出表达式还是挺需要想象力的…
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int N=1e5+5; int a[N],b[N]; int main() { int n,m,i,j,k; cin>>n>>m; for(i=1;i<=n;i++)scanf("%d",&a[i]); int sit=1; for(i=1;i<=n;i++){ b[i]=b[i-1]+sit*(a[i]-a[i-1]);//sit用于判断这个区间是亮还是灭 sit^=1; } b[n+1]=b[n]+sit*(m-a[n]);//不要漏了最后一个区间 int ans=b[n+1]; for(i=1;i<=n;i++)ans=max(ans,b[i]*2-b[n+1]+m-a[i]-1);//m-a[i]-(b[n+1]-b[i])-1求出在 // 当前区间改变状态后此区间后面的亮灯时长,加上前面不变的就是总的亮灯时长 cout<<ans<<endl; return 0; }C. 朴素的想法是建立一个cnt数组，统计每一个点被多少个区间覆盖了，然后我们发现其实并不用真的把所有点都模拟出来，只要在区间的l处+1，区间的r+1处-1即可，最后利用前缀和从前加到后就可以求出该区间的seg的覆盖数。区间的端点过大，因此要用map离散化一下。然后注意到端点之间的整个区间内的seg覆盖数肯定都是相同的即可。
#include<cstdio> #include<map> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; //#define ll long long map<ll,ll>M; ll A[200005],x,y,n,l; int main() { scanf("%lld", &n); for (l = n; l >= 1; --l) { scanf("%lld%lld", &x, &y); ++M[x];//在l处+1 --M[y + 1];//在r+1处-1 } x = 0;//注意x从0开始 for (auto it:M) { A[x] += it.first - l;//从前一个到这一个点中间所有点的区间覆盖数都是相同的 l = it.first;//更新 x += it.second;//注意it.second有正有负,依赖的是前缀和来求出当前区间的情况 } for (l = 1; l <= n; ++l) printf("%lld ", A[l]); return 0; }