NOIP提高组模拟赛24
差点又因为文件暴0。。。
A. matrix
状压，\(f[i][j][k]\)表示第\(i-1\)行状态为\(j\)，第\(i\)行状态为\(k\)的最小花费。
貌似复杂度不对？但是舍弃非法状态后复杂度是可以接受的，具体怎么证明我不会
code
#include
#include
using namespace std;
int min(int x,int y){return x>1))&ms);
f[i][ns][mp[i+1]|op]=min(v[i][op]+f[i-1][j][k],f[i][ns][mp[i+1]|op]);
// printf("%d %d %d + %d -> %d %d %d == %d\n",i-1,j,k,v[i][op],i,ns,mp[i+1]|op,f[i][ns][mp[i+1]|op]);
}
}
}
}
int ans=inf;
for(int i=0;i<=ms;++i)ans=min(ans,f[n][ms][i]);
printf("%d\n",ans);
return 0;
}
B. block
第一问按照\(1->val 2->key\)排序，从大到小考虑每个数有多少位置可以放，统计一下即可。
可恶，第二关键字搞错了，然而.....
第二问直接拿链表暴力搞有\(90\)
正解平衡树二分或者奇妙线段树
平衡树二分我不理解，感觉那玩意两个关键字，没有二分所需要的单调性。。
线段树就是，你取一个数，所有比他小的数的\(key\)需要\(--\)，然后每次贪心选择字典序最小的，但是需要保证\(key>0\)，也就是说如果有\(key==1\)的需要优于字典序考虑
注意上面那个变化的\(key\)是一个类似备份的东西，它可以变，但是比较字典序需要用原数
然后，线段树有点细节啊。。。
code
#include
#include
#include
using namespace std;
const int mod=1e9+7;
const int maxn=500005;
struct node{
int key,val;
}d[maxn];
int n;
bool cmp(node x,node y){
if(x.val!=y.val)return x.val>y.val;
return x.keyR)return;
if(L<=l&&r<=R){
t[x].val+=v;
t[x].tag+=v;
return;
}
int mid=(l+r)>>1;
if(t[x].tag)push_down(x);
if(L<=mid)modify(x<<1,l,mid,L,R,v);
if(R>mid)modify(x<<1|1,mid+1,r,L,R,v);
push_up(x);
}
void modify(int x,int l,int r,int pos,int v){
if(l==r){
t[x].pos=t[x].vpos=l;
t[x].val=t[x].tu=v;
return;
}
int mid=(l+r)>>1;
if(t[x].tag)push_down(x);
if(pos<=mid)modify(x<<1,l,mid,pos,v);
else modify(x<<1|1,mid+1,r,pos,v);
push_up(x);
}
}T;
int main(){
freopen("block.in","r",stdin);
freopen("block.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d%d",&d[i].key,&d[i].val);
work();
sort(d+1,d+n+1,cmp2);
for(int i=1;i<=n;++i)T.modify(1,1,n,i,d[i].key);
for(int i=1;i<=n;++i){
int pos=T.t[1].val==1?T.t[1].vpos:T.t[1].pos;
printf("%d %d\n",d[pos].key,d[pos].val);
T.modify(1,1,n,1,pos-1,-1);
T.modify(1,1,n,pos,498244353);
}
return 0;
}
C. graph
\(emmm..\)
一个教训
ceil(x/y)是假的ceil((float)x/y)才对，为啥？类型转化。。。。。。
二维最短路，\(dis[i][j]\)表示\(1->i\)走了\(j\)条\(-1\)路径的最短路
枚举走几条\(-1\)为最短路，解不等式组
\(dis [n] [j] + val * j >= dis [n] [i] + val * i\)
解出来的范围随便取个数跑\(1-i\),\(n-i\)的最短路，枚举点看是否可以为最短路上的点，（\(d[0][j]+d[1][j]==val*i+dis[n][i]\)）
不过\(lyin\)说这个解法假了，正解应该是维护凸包.
code
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1005;
const int maxm=2005;
typedef long long ll;
int n,m,head[maxn],tot,cnt;
ll inf=0x3f3f3f3f3f3f3f3f;
bool ans[maxn];
struct edge{
int to,net,val;
}e[maxm<<1|1];
void add(int u,int v,int w){
e[++tot].net=head[u];
head[u]=tot;
e[tot].to=v;
e[tot].val=w;
}
struct node{
int x,cnt;
ll val;
node(){}
node(int _x,int _cnt,ll _val){
x=_x;cnt=_cnt;val=_val;
}
bool operator <(node x)const {
return val>x.val;
}
};
priority_queueq;
bool vis2[maxn][maxm];
ll dis[maxn][maxm];
void dijj(){
memset(vis2,0,sizeof(vis2));
memset(dis,0x3f,sizeof(dis));
dis[1][0]=0;q.push(node(1,0,0));
while(!q.empty()){
node x=q.top();q.pop();
if(vis2[x.x][x.cnt])continue;
vis2[x.x][x.cnt]=1;
for(int i=head[x.x];i;i=e[i].net){
int v=e[i].to;
if(e[i].val==-1){
if(dis[v][x.cnt+1]>dis[x.x][x.cnt]&&x.cnt<=cnt){
dis[v][x.cnt+1]=dis[x.x][x.cnt];
q.push(node(v,x.cnt+1,dis[v][x.cnt+1]));
}
}else{
if(dis[v][x.cnt]>dis[x.x][x.cnt]+e[i].val){
dis[v][x.cnt]=dis[x.x][x.cnt]+e[i].val;
q.push(node(v,x.cnt,dis[v][x.cnt]));
}
}
}
}
}
ll d[2][maxn];
bool vis [maxn];
void dij(int op,ll va){
memset(vis,0,sizeof(vis));
int s=op==0?1:n;
d[op][s]=0;
q.push(node(s,0,0));
while(!q.empty()){
node x=q.top();q.pop();
if(vis[x.x])continue;
vis[x.x]=1;
for(int i=head[x.x];i;i=e[i].net){
int v=e[i].to;
ll w=e[i].val==-1?va:e[i].val;
if(d[op][v]>d[op][x.x]+w){
d[op][v]=d[op][x.x]+w;
q.push(node(v,0,d[op][v]));
}
}
}
}
int main(){
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
int u,v,w;scanf("%d%d%d",&u,&v,&w);
add(u,v,w);add(v,u,w);if(w==-1)++cnt;
}
dijj();
for(int i=0;i<=cnt;++i){
if(dis[n][i]==inf)continue;
ll l=0,r=inf;bool flag=0;
for(int j=0;j<=cnt;++j){
if(i==j)continue;
ll x=dis[n][j]-dis[n][i];
ll y=i-j;
// dis [n] [j] + val * j >= dis [n] [i] + val * i
// dis [n] [j] - dis [n] [i] >= (i-j) * val
// x >= y * val
if(x<=0&&y>0){flag=1;break;}
if(x>0&&y<0)continue;
if(y<0)l=max(l,ll(ceil((float)x/y)));
else r=min(r,ll(x/y));
}
if(flag||l>r)continue;
memset(d,0x3f,sizeof(d));
dij(1,l);dij(0,l);
ll mxl=l*i+dis[n][i];
for(int j=2;j