昨天晚上做梦 梦见自己被关进戒网瘾学校 里面的老师全和疯子一样 然后我和这帮疯子老师比疯 疯子老师发现他们没我疯 所以就把我放了 lhx 罗曼蒂克的辟谷
今天的乐子
今天的乐子2
今天的乐子3
A.五彩斑斓
赛时的想法
\(n^4\) 的做法，设 \(f_{i,j,k,l}\) 表示以 \((i,j)\) 为左上角，右下角不超过 \((k,l)\) 的矩阵的个数和
\[f_{i,j,k,l}=f_{i,j,k-1,l}+f_{i,j,k,l-1}-f_{i,j,k-1,l-1}+judge_{i,j,k,l} \]观察到可以直接开桶，把第四维压掉
然后就变成 \(n^3\) 的了
但是我正确性出问题了，不知道哪有问题，有大佬可以指一下思路上的问题
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int n,m;
int a[401][401];
long long f[401][401];
long long samecnt[401][401];
map<int,int>mp;
int cnt=0;
bool check(int xa,int ya,int xb,int yb){
int tmp1=a[xa][ya],tmp2=a[xa][yb],
tmp3=a[xb][ya],tmp4=a[xb][yb];
return !(tmp1==tmp2 and tmp2==tmp3 and tmp3==tmp4);
}
signed main(){
freopen("colorful.in","r",stdin);
freopen("colorful.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
scanf("%d",&a[i][j]);
if(!mp.count(a[i][j])){
mp[a[i][j]]=++cnt;
}
a[i][j]=mp[a[i][j]];
}
}
int ans=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
for(int k=1;k<=cnt;++k){
samecnt[j][k]&=0;
}
}
for(int j=1;j<=m;++j){
f[i][j]=f[i][j-1]+f[i-1][j]-f[i-1][j-1];
for(int sti=1;sti<=i;++sti){
if(a[sti][j]==a[i][j]){
samecnt[sti][a[i][j]]++;
f[i][j]+=j-samecnt[sti][a[i][j]];
}
else f[i][j]+=j;
}
}
}
cout<<f[n][m]<<endl;
}
题解的思路是类似的，正难则反，考虑求顶点全相同的矩形个数，\(n^4\) 的做法就更简单了，直接枚举顶点就行了
所以有人直接用 bitset 草过去了
实际上可以对值域开桶
假设我们已经知道了矩形的右边两个点（可以通过分别枚举上边界，右边界和下边界来 \(n^3\) 得到），那么我们有如下两个结论
- 已知的两个点不一致时不存在解
- 考虑下边界这一行，设 \(cnt_{a_{rd}}\) 表示在该行下标小于等于矩形右下角的节点中，值和右下角顶点相同，且与对应上边界节点值相同的节点数量，则该点答案即为 \(cnt_{a_{rd}}\)
如果难理解可以画图理解
图
瓶颈在清空，出题人你没有心
#include<bits/stdc++.h>
using namespace std;
int n,m;
int cnt[1000001],a[401][401];
long long ans;
int main(){
freopen("colorful.in","r",stdin);
freopen("colorful.out","w",stdout);
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=i;j<=n;++j){
for(int k=1;k<=m;++k){
if(a[i][k]==a[j][k]){
cnt[a[i][k]]++;
ans+=cnt[a[i][k]];
}
}
for(int k=1;k<=m;++k){
if(a[i][k]==a[j][k]){
cnt[a[i][k]]=0;
}
}
}
}
cout<<n*(n+1ll)*m*(m+1)/4-ans;
}
B.错峰旅行
结论题
结论
- 如果有一段连续的长度为 \(l\) 的时间段，满足该时间段内不存在状态改变的城市，且状态为不拥挤的城市有 \(x\) 个，则对方案数的贡献（乘）为 \(x^l\)
所以这是一个离散化板子题
- 把所有坐标离线下来做离散化（注意开始结尾也要插进去离散化），然后因为对于区间 \([l,r]\)，是 \(r+1\) 才更新状态，所以应该插入 \(l,r+1\)
- 开双指针对坐标扫一遍，另一个扫操作，记一下这个是状态加还是状态减，直接统计答案就行了
不明白 STD 开牛魔的差分，题目里不是保证了区间不重叠了吗
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=1e9+7;
int power(int a,int t){
int base=a,ans=1;
while(t){
if(t&1){
ans=ans*base%p;
}
base=base*base%p;
t>>=1;
}
return ans;
}
int n,m,s,t;
struct ope{
int id,pos;
bool isadd;
bool operator <(const ope &A)const{
if(A.pos==pos) return isadd<A.isadd;
return pos<A.pos;
}
};
int sum[1000001];
vector<ope>op={{}};
map<int,int>mp;
int pos[4000001];
int cnt=0,cnt2=0;
signed main(){
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
scanf("%lld %lld %lld %lld",&n,&m,&s,&t);
for(int i=1;i<=m;++i){
int x,l,r;
scanf("%lld %lld %lld",&x,&l,&r);
op.push_back({x,l,true});
op.push_back({x,r+1,false});
pos[++cnt2]=l;
pos[++cnt2]=r+1;
}
pos[++cnt2]=s;
pos[++cnt2]=t+1;
sort(op.begin(),op.end());
sort(pos+1,pos+cnt2+1);
cnt2=unique(pos+1,pos+cnt2+1)-pos-1;
long long lsum=1,nsum=0;
long long lnum=n,nnum=0;
for(int i=1,j=0;i<cnt2;++i){
nsum=0;
nnum=lnum;
while(j<2*m and op[j+1].pos<=pos[i]){
j++;
int x=op[j].id;
int d=(op[j].isadd?1:-1);
if(sum[x]>0 and sum[x]+d<=0) ++nnum;
else if(sum[x]<=0 and sum[x]+d>0) --nnum;
sum[x]+=d;
}
assert(pos[i+1]-pos[i]>=0);
nsum=lsum*power(nnum,pos[i+1]-pos[i])%p;
lsum=nsum;
lnum=nnum;
}
cout<<nsum;
}
C.线段树
考虑一个询问区间 \([l,r]\) 的贡献，发现至少有 \(1\) 的贡献
抛开这个 \(1\) 不谈，剩下的贡献都是通过如下方式增加的
- 线段树存在一个子区间，使得两个区间有交集且不包含
因此区间 DP，设 \(f_{i,j}\) 表示区间 \([i,j]\) 划分后的最小新增贡献
\[f_{i,j}=\min_{k}f_{i,k}+f_{k+1,j}+cost \]所以计算本层贡献即可
关于本层贡献的计算，可以分别统计有多少区间与当前区间有交，有多少区间被当前区间包含，直接减掉就行了
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define r l+len-1
int n,qq;
int w[501];
int num[501][501];
int f[501][501];
signed main(){
freopen("segment.in","r",stdin);
freopen("segment.out","w",stdout);
cin>>n>>qq;
for(int i=1;i<=qq;i++){
int _l,_r;
scanf("%lld %lld",&_l,&_r);
num[_l][_r]++;
w[_l]++;w[_r]--;
}
for(int i=1;i<=n;i++){
w[i]+=w[i-1];
}
for(int len=n-1;len>=1;len--){
for(int l=1;r<=n;l++){
num[l][r]=num[l][r]+num[l-1][r]+num[l][r+1]-num[l-1][r+1];
}
}
for(int len=2;len<=n;len++){
for(int l=1;r<=n;l++){
f[l][r]=LLONG_MAX;
for(int k=l;k<r;k++){
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+(w[k]-num[l][r]));
}
}
}
cout<<f[1][n]+qq<<'\n';
}