题解
印章
题意：用一个网格图形去覆盖另一个网格图图形并且不能旋转，重叠和溢出
考虑到方格纸最左上角的黑点和印章最左上角的墨水必然是重合的
将印章里的墨水点存在一个链表里，直接暴力依次覆盖方格纸上的黑点，并把覆盖过的黑点清空
复杂度是$O(nm)$
膜法师
题意：给出一个序列，有些节点是特殊的但是你不知道，每次你可以花费一定代价询问一段连续的区间中特殊点数量的奇偶性，问能够必然确定特殊点的最小花费。
考虑相邻两个数之间的缝隙。（包括第一个数之前和最后一个数之后）
每个询问都是在询问两个缝隙之间的奇偶性。
实际上题目要求的就是你最后必须能推导出每个数前后缝隙之间的奇偶性。
考虑将每个缝隙看作是一个点，询问就是在两个点之间建边，如果两个缝隙对应的点相邻，那么他们之间的奇偶性就可以得到。
所以问题转化成了最小生成树，边权就是对应的询问花费
看电影
题意：给出一个序列，每个节点有一种颜色，每种颜色有对应的权值，要求找出一个区间，使得区间内只出现过一次的颜色的权值之和最大。
先预处理出对于每个节点，下一个跟他相同颜色的点的位置，定义它为$nxt[i]$
然后枚举最后选的那个区间的左端点$L$，用一颗线段树记录对于每个$R$，这个区间的得分是多少
当左端点$L$向右移时，设当前左端点颜色为$i$，相当于把以$L$到$nxt[L]-1$为结尾的区间的得分减$w[i]$，再把以$nxt[L]$到$nxt[nxt[L]]-1$为结尾的区间的得分加$w[i]$
然后查询以$L$到$n$为结尾的区间的得分的最大值，得到$L$为开头的所有区间的得分的最大值
复杂度为$O(n\log n)$
标程
印章
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
vector<pair<int,int> >adj;
int n,m,a,b,T;
bool mp[1200][1200];
char str[1200];
inline bool solve(int x,int y)
{
if(adj.size()==0)return true;
int sx=x-adj[0].first,sy=y-adj[0].second;
for (int i=0;i<adj.size();i++)
{
int tx=sx+adj[i].first;
int ty=sy+adj[i].second;
if(tx<1||tx>n||ty<1||ty>m)return true;
if(!mp[tx][ty])return true;
mp[tx][ty]=false;
}
return false;
}
int main()
{
scanf("%d",&T);
while (T--)
{
memset(mp,0,sizeof(mp));
adj.clear();
scanf("%d %d %d %d",&n,&m,&a,&b);
for (int i=1;i<=n;i++)
{
scanf("%s",str+1);
for (int j=1;j<=m;j++)
{
if(str[j]=='x')mp[i][j]=true;
}
}
for (int i=1;i<=a;i++)
{
scanf("%s",str+1);
for (int j=1;j<=b;j++)
{
if(str[j]=='x')adj.push_back(make_pair(i,j));
}
}
int fl=0;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
if(mp[i][j])
{
if(solve(i,j))
{
printf("NIE\n");
fl=1;break;
}
}
}
if(fl==1)break;
}if(fl==0)printf("TAK\n");
}
return 0;
}膜法师
#include<cstdio>
#include<utility>
#include<algorithm>
using namespace std;
int cnt,x1,x2;
pair<int,pair<int,int> >edge[2200000];
int fat[2010];
inline int fnd(int x)
{
if(fat[x]==x)return x;
return fat[x]=fnd(fat[x]);
}
int n,cnt2;
long long ans;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
fat[i]=i;
for (int j=i;j<=n;j++)
{
scanf("%d",&x1);
cnt++;
edge[cnt]=make_pair(x1,make_pair(i,j+1));
}
}
fat[n+1]=n+1;
sort(edge+1,edge+cnt+1);
for (int i=1;i<=cnt;i++)
{
x1=edge[i].second.first;
x2=edge[i].second.second;
if(fnd(x1)!=fnd(x2))
{
fat[fnd(x1)]=fnd(x2);
cnt2++;
ans+=edge[i].first;
if(cnt2==n)break;
}
}
printf("%lld\n",ans);
return 0;
}看电影
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int f[1200000];
int w[1200000];
int next[1200000];
int las[1200000];
struct segment
{
int lef[5200000];
int rig[5200000];
long long val[5200000];
long long laz[5200000];
inline void update(int x)
{
val[x]=max(val[x*2],val[x*2+1]);
}
inline void upgrade(int x,long long va)
{
laz[x]+=va;
val[x]+=va;
}
inline void pushdown(int x)
{
upgrade(x*2,laz[x]);
upgrade(x*2+1,laz[x]);
laz[x]=0;
}
inline void build(int x,int le,int ri)
{
lef[x]=le;
rig[x]=ri;
val[x]=0;
laz[x]=0;
if(le==ri)return;
build(x*2,le,(le+ri)/2);
build(x*2+1,(le+ri)/2+1,ri);
}
inline void edit(int x,int le,int ri,long long va)
{
if(le>ri)return;
if(le<=lef[x]&&ri>=rig[x])
{
upgrade(x,va);
return;
}
pushdown(x);
if(le<=rig[x*2])edit(x*2,le,ri,va);
if(ri>rig[x*2])edit(x*2+1,le,ri,va);
update(x);
}
inline long long query(int x,int le,int ri)
{
if(le>ri)return 0;
if(le<=lef[x]&&ri>=rig[x])
{
return val[x];
}
long long summ=0;
if(le<=rig[x*2])summ=max(summ,query(x*2,le,ri));
if(ri>rig[x*2])summ=max(summ,query(x*2+1,le,ri));
return summ;
}
}sgt;
long long ans;
int main()
{
scanf("%d %d",&n,&m);
for (int i=1;i<=n;i++)
{
scanf("%d",&f[i]);
}
for (int i=1;i<=m;i++)
{
scanf("%d",&w[i]);
las[i]=n+1;
}
for (int i=n;i>=1;i--)
{
next[i]=las[f[i]];
las[f[i]]=i;
}
sgt.build(1,1,n);
for (int i=1;i<=m;i++)
{
if(las[i]!=n+1)
{
sgt.edit(1,las[i],next[las[i]]-1,w[i]);
}
}
for (int i=1;i<=n;i++)
{
ans=max(ans,sgt.query(1,i,n));
// printf("%d %lld\n",i,ans);
if(next[i]!=n+1)
{
sgt.edit(1,i,next[i]-1,-w[f[i]]);
sgt.edit(1,next[i],next[next[i]]-1,w[f[i]]);
}
else
{
sgt.edit(1,i,n,-w[f[i]]);
}
}
printf("%lld\n",ans);
return 0;
}
