我是咸鱼啊啊啊啊
我再也不交卷前1S改代码了，会-1s
题面见文件。
T1
考场代码，毫无美感。
在逆推的时候应该除19，而非20(ryc:啊我也不知道为什么).
因为是逆推，所以前一个点是这个点的 20/19
#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
using namespace std;
const int N=50005;
int n,p,S,T,dis[300],head[505],ecnt;
struct Edge {
int to,nxt,val;
} e[52*52*3+5];
void add(int bg,int ed) {
e[++ecnt].nxt=head[bg];
e[ecnt].to=ed;
head[bg]=ecnt;
}
bool ck[200],vis[N];
queue<int>q;
int CNT;
void spfa() {
memset(dis,0x3f,sizeof dis);
q.push(T);
dis[T]=p;
vis[T]=1;
while(!q.empty()) {
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u]; i; i=e[i].nxt) {
int v=e[i].to;
if(ck[u]) {
int tp=dis[u]+ceil((double)dis[u]/19.0);
if(dis[v]>tp) {
dis[v]=tp;
if(!vis[v])vis[v]=1,q.push(v);
}
} else {
if(dis[v]>dis[u]+1) {
dis[v]=dis[u]+1;
if(!vis[v]) {
vis[v]=1,q.push(v);
}
}
}
}
}
}
int main() {
freopen("toll.in","r",stdin);
freopen("toll.out","w",stdout);
for(int i='A'; i<='Z'; i++) ck[i]=1;
while(1) {
char a,b;
CNT++;
memset(head,0,sizeof head);
ecnt=0;
scanf("%d",&n);
if(n==-1)return 0;
for(int i=1; i<=n; i++) {
scanf(" %c %c",&a,&b);
add(b,a);
add(a,b);
}
cin>>p>>a>>b;
S=a,T=b;
spfa();
printf("Case %d: %d
",CNT,dis[S]);
}
}
T2
一道貌似网络流的题，考场最后一秒改了边权，80->20 &^%$#@!
实际上是最长上升子序列。
因为给每个逆序对之间连一条边，那么反证，如果选的不是LIS，那么一定会导致另一个或多个数被连边，会导致ans更差。
#include <bits/stdc++.h>
using namespace std;
int n;
const int N=2005,inf=0x3f3f3f3f,S=2003,T=2001;
int a[100005],h[100005],ecnt=1,head[100005];
struct Edge {
int to,nxt,val;
} e[N*N<<1];
void add(int bg,int ed,int val) {
e[++ecnt].nxt=head[bg];
e[ecnt].to=ed;
e[ecnt].val=val;
head[bg]=ecnt;
}
queue<int>q;
bool bfs() {
memset(h,-1,sizeof h);
q.push(S);
h[S]=0;
while(!q.empty()) {
int u=q.front();
q.pop();
for(int i=head[u]; i; i=e[i].nxt) {
int v=e[i].to;
if(h[v]==-1&&e[i].val) {
h[v]=h[u]+1;
q.push(v);
}
}
}
return h[T]!=-1;
}
int dfs(int x,int f) {
if (x==T)return f;
int tp,used=0;
for(int i=head[x]; i; i=e[i].nxt) {
int v=e[i].to;
if(e[i].val&&h[v]==h[x]+1) {
tp=dfs(v,min(f-used,e[i].val));
used+=tp;
e[i].val-=tp;
e[i^1].val+=tp;
if(used==f) return f;
}
}
if(!used) h[x]=-1;
return used;
}
int maxflow;
int t[100005<<2];
void add(int x,int Max) {
for(; x<=100005*3; x+=x&-x) {
t[x]=max(t[x],Max);
}
}
int ask(int x) {
int Max=-1;
for(; x; x-=x&-x)
Max=max(Max,t[x]);
return Max;
}
int f[100005<<2];
void dinic() {
while(bfs())maxflow+=dfs(S,inf);
}
void insert(int a,int b,int c) {
add(a,b,c);
add(b,a,0);
}
int main() {
freopen("sort.in","r",stdin);
freopen("sort.out","w",stdout);
scanf("%d",&n);
if(n<=1000) {
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
for(int i=1; i<=n; i++) {
for(int j=i+1; j<=n; j++) {
if(a[i]>a[j]) add(i,j+n,inf),add(j+n,i,0);
}
}
for(int i=1; i<=n; i++) insert(S,i,1),insert(i+n,T,1);
dinic();
cout<<n-maxflow;
return 0;
} else {
int ans=1;
for(int i=1; i<=n; i++) {
int x;scanf("%d",&x);
f[i]=ask(x)+1;
ans=max(ans,f[i]);
add(x,f[i]);
}
printf("%d",ans);
}
}
失败的数据分治。
T3
唯一的水题，就是细节有点多。
状压dp，判一下能不能执行，因为每次执行相同密室后的结果一定相同，所以ans一定不变。
tip:发现不可行的时候，我这个写法是不能清零的，因为如果清零那么可能之前执行成功过。（GhostCai实测WA2个点）
我就是要压行
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,a[25],b[25],c[25],d[25],e[25],k1,k2,k3;
struct F {
int a1,a2,a3;
} f[1<<15];
int main() {
freopen("room.in","r",stdin);
freopen("room.out","w",stdout);
scanf("%d",&n);
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
for(int i=1; i<=n; i++) scanf("%d",&b[i]);
for(int i=1; i<=n; i++) scanf("%d",&c[i]);
for(int i=1; i<=n; i++) scanf("%d",&d[i]);
for(int i=1; i<=n; i++) scanf("%d",&e[i]);
scanf("%d%d%d",&k1,&k2,&k3);
f[0].a2=k2,f[0].a1=k1,f[0].a3=k3;
for(int i=0; i<(1<<n); i++) {
for(int j=1; j<=n; j++) {
if(!((1<<j-1)&i)) {
if(a[j]>f[i].a1) {
if(a[j]>f[i].a1+f[i].a3) continue;
else {
if(f[i].a2<b[j]) {
if(f[i].a3-(a[j]-f[i].a1)+f[i].a2<b[j]) continue;
else f[i|(1<<j-1)].a1=0,f[i|(1<<j-1)].a2=0,f[i|(1<<j-1)].a3=(f[i].a3-(a[j]-f[i].a1)-(b[j]-f[i].a2));
} else f[i|(1<<j-1)].a1=0,f[i|(1<<j-1)].a2=f[i].a2-b[j],f[i|(1<<j-1)].a3=f[i].a3-(a[j]-f[i].a1);
}
} else {
if(b[j]>f[i].a2) {
if(b[j]>f[i].a2+f[i].a3) continue;
f[i|(1<<j-1)].a1=f[i].a1-a[j],f[i|(1<<j-1)].a2=0,f[i|(1<<j-1)].a3=f[i].a3-(b[j]-f[i].a2);
} else {
f[i|(1<<j-1)].a1=f[i].a1-a[j],f[i|(1<<j-1)].a2=f[i].a2-b[j];
f[i|(1<<j-1)].a3=f[i].a3;
}
}
f[i|(1<<j-1)].a1+=c[j];
f[i|(1<<j-1)].a2+=d[j];
f[i|(1<<j-1)].a3+=e[j];
}
}
}
int ans=-1;
for(int i=0; i<(1<<n); i++) ans=max(ans,f[i].a1+f[i].a2+f[i].a3);
cout<<ans;
}