20230707
T1.信号传输（signal）
考场思路
先把这\(n+k+1\)个点都转化到平面直角坐标系上面
又是没有想清楚就开始打代码（但至少比昨天好，懂得放弃）
本来想的是按照x轴从左到右扫一遍
每一次处理这一列上的每个点
复杂度是\(O(n)\)
但是后面想到有可能信号是从后面的点传送过来的
所以我又再从右到左扫一遍
最后测试样例时发现这个想法是错误的
如果要全部遍历完需要不断地扫
因为这道题每条边的代价都是1
所以我果断放弃
在点之间建边，复杂度\(O(n^2)\)
用digstra打了30分的暴力
Solution
发现对于横坐标或者纵坐标相等的点
再那一条线上是可以随便传到任意一个点上的
所以或许可以把再这样一条平行于坐标轴的点看做一个整体
而每个点的作用就是转弯90度
也就是把它所在的两条直线（分别平行于x轴和y轴）
建立一条边连起来
而对于最后的\(k\)个点，就不用建边
这样在查询时讨论信号是从哪条直线来即可
这样就相当于在我的暴力上面进行优化
把点数和边数都减小了
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10,inf=0x3f3f3f3f,mx=2e6+1;
int n,k,m,head[maxn<<2],tot=0,dis[maxn<<2],x;
bool vis[maxn<<2];
struct edge{
int v,nxt,val;
}e[maxn<<3];
struct node{
int x,y;
}a[maxn];
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
void add(int u,int v){
dis[u]=dis[v]=inf;
e[++tot]=(edge){v,head[u],1};
head[u]=tot;
e[++tot]=(edge){u,head[v],1};
head[v]=tot;
}
priority_queue<pair<int,int> > q;
void dijstra(){
memset(vis,false,sizeof(vis));
dis[a[0].x]=0;dis[a[0].y+mx]=0;
q.push(make_pair(0,a[0].x));
q.push(make_pair(0,a[0].y+mx));
while(!q.empty()){
int u=q.top().second;q.pop();
if(vis[u]) continue;
vis[u]=true;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v,val=e[i].val;
if(dis[v]>dis[u]+val){
dis[v]=dis[u]+val;
q.push(make_pair(-dis[v],v));
}
}
}
}
int main(){
freopen("signal.in","r",stdin);
freopen("signal.out","w",stdout);
memset(dis,-1,sizeof(dis));
n=read();k=read();
for(int i=0;i<=n;i++){
a[i].x=read();a[i].y=read();
add(a[i].x,a[i].y+mx);
}
for(int i=1;i<=k;i++) a[i+n].x=read(),a[i+n].y=read();
dijstra();
m=read();
for(int i=1;i<=m;i++){
x=read();int ans=inf;
if(dis[a[x].x]==-1&&dis[a[x].y+mx]==-1) printf("-1\n");
else{
if(dis[a[x].x]!=-1) ans=min(ans,dis[a[x].x]);
if(dis[a[x].y+mx]!=-1) ans=min(ans,dis[a[x].y+mx]);
printf("%d\n",ans+2);
}
}
return 0;
}
注意dijstra复杂度：\(O(m log n)\)
T2.重排序列（permutation）
考场思路
把题意理解错的还得是我
可能还是因为没有想清楚
然后写了一个自认为的网络流的60分的暴力
打完了才发现题目要求是字典序最大
而不是让你序列总和最大
于是我就又打了个\(O(n^2)\)的暴力
结果答案错误就只有10分
Solution
原题CF313E
首先在读入的时候取模（这个不用说都知道）
然后，我们得到的\(c_i\)就有两种情况
\(a[i]+b[j] \lt m\)或者是\(a[i]+b[j]-m\)
很显然，第二种是不划算的
那么我们就考虑让第一种越多越好
我们将\(a,b\)数组从小到大排序
再从小到大去枚举\(a\)
我们去找与它加起来最大的\(b[j]\)使两者相加小于\(m\)
那这样找到的\(b[j]\)一定是一段后缀
因为\(b[j]\)要么不匹配，要么和比\(a[i]\)更小的匹配
这样肯定都不是最优
但是按照这样实现就在\(a[i]\)把\(a[i-1]\)淘汰之后
我们没有办法再去找\(a[i-1]\)的匹配
所以这样写正确性是不能保证的（大样例过不了）
所以我们想要从大到小枚举数组\(b\)
然后找到第一个与它相加\(\lt m\)的\(a[i]\)
所以我们贪心地去匹配就可以了
而对于最后剩下来的
就是他们相加大于\(m\)的了
那我们就让大的和大的匹配从而让字典序更大即可
说起来确实听简单，但是想不到啊……
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int n,mod,a[maxn],b[maxn],c[maxn],cnt=0,it;
bool vis[maxn];
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
multiset<int> st;
int main(){
freopen("permutation.in","r",stdin);
freopen("permutation.out","w",stdout);
n=read();mod=read();
for(int i=1;i<=n;i++) a[i]=read(),a[i]%=mod,st.insert(a[i]);
for(int i=1;i<=n;i++) b[i]=read(),b[i]%=mod;
sort(b+1,b+n+1);
for(int i=n;i>=1;i--){
multiset<int>::iterator it=st.lower_bound(mod-b[i]);
if(it==st.begin()) continue;
c[++cnt]=b[i]+(*--it);
st.erase(it);vis[i]=true;
}
for(int i=1;i<=n;i++){
if(vis[i]) continue;
c[++cnt]=b[i]+*st.begin()-mod;
st.erase(st.begin());
}
sort(c+1,c+cnt+1);
for(int i=cnt;i>=1;i--) printf("%d ",c[i]);
printf("\n");
return 0;
}
T3.价格调查（survey）
考场思路
写了一个\(n^3\)的dp
想要骗个10分但是写挂了
Solution
原题ARC159D
把题意转化就是一个难点
就如原题里面说的
每一次我们加入\(l \sim r\)的每一个元素
最后求最长上升子序列
我们考虑选择一个区间
就一定要选它的右端点，否则不优
所以说不同的右端点只有\(n\)个
所以令\(dp_i\)表示以\(i\)结尾的最长上升子序列
那么在加入区间\([l,r]\)时，我们只用更新\(dp_r\)
这样就可以分两种情况：
\(i \lt l,dp_r=dp_i+r-l+1\)
\(l \le i \lt r,dp_r=dp_i+r-i\)
这样的\(dp\)很显然是\(O(n^2)\)的
所以我们考虑当我们选\(dp_i\)时一定是选的小于\(l\)中最大的
我们可以用线段树来维护
同理，对于第二种情况的\(dp_i-i\)也可以用线段树来维护
这道题的关键就在于分析到必须要选右端点
否则肯定不是最优的
#include <bits/stdc++.h>
using namespace std;
#define mid L+((R-L)>>1)
#define lson L,mid,rt<<1
#define rson mid+1,R,rt<<1|1
#define lb(x) lower_bound(a+1,a+len+1,x)-a
const int maxn=2e5+10,inf=0x3f3f3f3f;
int a[maxn<<1],l[maxn],r[maxn],n,dp[maxn<<1],tr[2][maxn<<3],len,ans=0;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
void pushup(int u,int rt){tr[u][rt]=max(tr[u][rt<<1],tr[u][rt<<1|1]);}
void update(int u,int x,int val,int L=1,int R=len,int rt=1){
if(L==R){
tr[u][rt]=val;
return ;
}
if(x<=mid) update(u,x,val,lson);
else update(u,x,val,rson);
pushup(u,rt);
}
int query(int u,int x,int y,int L=1,int R=len,int rt=1){
if(x>y) return 0;
if(x<=L&&y>=R) return tr[u][rt];
int res=-inf;
if(x<=mid) res=max(res,query(u,x,y,lson));
if(y>mid) res=max(res,query(u,x,y,rson));
return res;
}
void build(int L=1,int R=len,int rt=1){
tr[0][rt]=0;
if(L==R){
tr[1][rt]=-a[L];
return;
}
build(lson);build(rson);
pushup(1,rt);
}
int main(){
freopen("survey.in","r",stdin);
freopen("survey.out","w",stdout);
n=read();
for(int i=1;i<=n;i++) l[i]=read(),r[i]=read(),a[i]=l[i],a[i+n]=r[i];
sort(a+1,a+n*2+1);
len=unique(a+1,a+n*2+1)-a-1;
build();
for(int i=1;i<=n;i++){
int p=lb(r[i]),p1=lb(l[i]);
dp[p]=max(query(0,1,p1-1)+r[i]-l[i]+1,query(1,p1,p)+r[i]);
update(0,p,dp[p]);update(1,p,dp[p]-r[i]);
}
for(int i=1;i<=len;i++) ans=max(ans,dp[i]);
printf("%d\n",ans);
return 0;
}
T4.哑剧（mime）
考场思路
用了一个数组，和一棵线段树
甚至不是可持久化
乱搞\(O(n^2 log n)\)
大样例都没过还有50分
Solution
还是没看懂
好像用了分块
总结
要学会对题目的特殊性质进行分析
不断优化解题过程，可以尝试合并之类的做法