本以为会是三道小强与阿米巴，结果打开题目一看发现了这个：
T1:
恩先写着一道
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define rep(s,t) for(int i=s;i<=t;i++)
using namespace std;
inline int read() {
char ch=getchar();int x=,f=;
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-;
for(;isdigit(ch);ch=getchar()) x=x*+ch-'';
return x*f;
}
const int maxn=;
const int maxnode=;
int A[maxn],B[maxn],root[maxn];
int ls[maxnode],rs[maxnode],s[maxnode],ToT;
void build(int& y,int x,int l,int r,int pos) {
s[y=++ToT]=s[x]+;if(l==r) return;
int mid=l+r>>;ls[y]=ls[x];rs[y]=rs[x];
if(pos<=mid) build(ls[y],ls[x],l,mid,pos);
else build(rs[y],rs[x],mid+,r,pos);
}
int query(int y,int x,int l,int r,int k) {
if(l==r) return l;
int k2=s[ls[y]]-s[ls[x]],mid=l+r>>;
if(k<=k2) return query(ls[y],ls[x],l,mid,k);
return query(rs[y],rs[x],mid+,r,k-k2);
}
int main() {
freopen("kth.in","r",stdin);
freopen("kth.out","w",stdout);
int n=read(),q=read();
rep(,n) A[i]=B[i]=read();
sort(B+,B+n+);
rep(,n) build(root[i],root[i-],,n,lower_bound(B+,B+n+,A[i])-B);
rep(,q) {
int l=read(),r=read(),k=read();
printf("%d\n",B[query(root[r],root[l-],,n,r-l-k+)]);
}
return ;
}
T2:
无脑爆搜+调整顺序，只搞出来5个点。
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
using namespace std;
inline int read() {
char ch=getchar();int x=,f=;
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-;
for(;isdigit(ch);ch=getchar()) x=x*+ch-'';
return x*f;
}
int cnt;
char s[][];
int rr[],ry[];
int id(int x,int y) {return (((y-)/)*+(x-)/)+;}
int r[][],c[][],sq[][],num[][],use[];
struct Point {
int x,y,s;
bool operator < (const Point& ths) const {
return rr[x]+ry[num[x][y]]>rr[ths.x]+ry[num[x][y]];//s>ths.s;
}
}A[];
void dfs(int cur) {
if(cur==cnt+) {
rep(i,,) {
rep(j,,) putchar(s[i][j]);
puts("");
}
exit();
}
else {
int x=A[cur].x,y=A[cur].y,z=num[x][y];
for(int d=;d<=;d++) if(!r[x][d]&&!c[y][d]&&!sq[z][d]){
r[x][d]=c[y][d]=sq[z][d]=;use[d]++;
s[x][y]=(d<=?d-+'':d-+'A');dfs(cur+);
r[x][d]=c[y][d]=sq[z][d]=;use[d]--;
}
}
}
int sc[];
int main() {
srand(time());
rr[]=;rr[]=;rr[]=;rr[]=;ry[]=;ry[]=;
freopen("sixteen7.in","r",stdin);
freopen("sixteen7.out","w",stdout);
sc['']=;sc['']=;sc['']=;sc['']=;
sc['']=;sc['']=;sc['']=;sc['']=;
sc['']=;sc['']=;sc['A']=;sc['B']=;
sc['C']=;sc['D']=;sc['E']=;sc['F']=;
rep(i,,) scanf("%s",s[i]+);
rep(i,,) rep(j,,) {
num[i][j]=id(i,j);
if(s[i][j]=='.') {
A[++cnt]=(Point){i,j,};
rep(k,,) if(s[i][k]!='.') A[cnt].s++;
rep(k,,) if(s[k][j]!='.') A[cnt].s++;
rep(k,,) rep(k2,,) if(s[k][k2]!='.'&&id(k,k2)==id(i,j)) A[cnt].s++;
if(i==||i==||i==) A[cnt].s+=;
}
else {
r[i][sc[s[i][j]]]=;c[j][sc[s[i][j]]]=;
sq[num[i][j]][sc[s[i][j]]]=;
}
}
/*for(int i=1;i<cnt;i++)
for(int j=i+1;j<=cnt;j++)
if(A[j].x==6&&(A[i].x!=7)) swap(A[i],A[j]);
else if(A[j].x==7) swap(A[i],A[j]);
else if(A[j].x==10&&(A[i].x!=7)) swap(A[i],A[j]);*/
sort(A+,A+cnt+);
//rep(i,1,cnt) printf("%d %d\n",A[i].x,A[i].y);
dfs();
return ;
}
T3:
恩让我回忆回忆2333
-------------------
似乎记得要二分答案，那就先二分答案吧。
考虑如何判定x是否可行，将|E|/|V|>k变形成|E|-k*|V|>0，发现这是个裸的最大权闭合子图。因为选中一条边能贡献1的权，但同时要依赖于两个端点也必须选，而这两个端点的贡献每个都是-k。那么跑一边最大流，算一下是否为m即可。
等等，这道题要你输出分数啊！那么最后再计算一下最优解，在网络中找那些指向汇点且被割断的边，这些边的另一端就是选择的点。
注意特判m=0
#include<cstdio>
#include<cstring>
#include<cctype>
#include<queue>
#include<algorithm>
#define rep(s,t) for(int i=s;i<=t;i++)
#define ren for(int i=first[x];i!=-1;i=next[i])
using namespace std;
inline int read() {
char ch=getchar();int x=,f=;
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-;
for(;isdigit(ch);ch=getchar()) x=x*+ch-'';
return x*f;
}
const int maxn=;
const int maxm=;
const double eps=1e-;
int n,m,u[],v[],A[],is[],cnt,ans;
struct Dinic {
int n,m,s,t;
int vis[maxn],cur[maxn],d[maxn],first[maxn],next[maxm];
struct Edge {int from,to;double flow;}edges[maxm];
void init(int n) {
this->n=n;m=;
fill(first+,first+n+,-);
}
void AddEdge(int u,int v,double cap) {
edges[m]=(Edge){u,v,cap};next[m]=first[u];first[u]=m++;
edges[m]=(Edge){v,u,0.0};next[m]=first[v];first[v]=m++;
}
int BFS() {
fill(vis+,vis+n+,);
queue<int> q;q.push(s);d[s]=;vis[s]=;
while(!q.empty()) {
int x=q.front();q.pop();cur[x]=first[x];
ren {
Edge& e=edges[i];
if(!vis[e.to]&&e.flow>eps) {
vis[e.to]=;
d[e.to]=d[x]+;
q.push(e.to);
}
}
}
return vis[t];
}
double DFS(int x,double a) {
if(x==t||a<eps) return a;
double flow=0.0,f;
for(int& i=cur[x];i!=-;i=next[i]) {
Edge& e=edges[i];
if(d[e.to]==d[x]+&&(f=DFS(e.to,min(a,e.flow)))>eps) {
e.flow-=f;edges[i^].flow+=f;
flow+=f;a-=f;if(a<eps) break;
}
}
return flow;
}
double MaxFlow(int s,int t) {
double ans=0.0;this->s=s;this->t=t;
while(BFS()) ans+=DFS(s,1e50);
return ans;
}
void solve() {
rep(,m-) if(edges[i].to==t&&edges[i].flow<eps) A[++cnt]=edges[i].from;
}
}sol;
int check(double mid) {
sol.init(n+m+);
int s=n+m+,t=n+m+;
rep(,m) sol.AddEdge(s,i,1.0),sol.AddEdge(i,u[i]+m,1e50),sol.AddEdge(i,v[i]+m,1e50);
rep(,n) sol.AddEdge(i+m,t,mid);
return m-sol.MaxFlow(s,t)>eps;
}
int gcd(int a,int b) {return !b?a:gcd(b,a%b);}
int main() {
freopen("density.in","r",stdin);
freopen("density.out","w",stdout);
n=read(),m=read();
if(!m) {puts("0/1");return ;}
rep(,m) u[i]=read(),v[i]=read();
double l=0.0,r=m;
while(r-l>eps) {
double mid=(l+r)*0.5;
if(check(mid)) l=mid;
else r=mid;
}
check(l);sol.solve();
rep(,cnt) is[A[i]-m]=;
rep(,m) if(is[u[i]]&&is[v[i]]) ans++;
printf("%d/%d\n",ans/gcd(ans,cnt),cnt/gcd(ans,cnt));
return ;
}
交上去WA了一个点，FHQ带大家测了半天，最后发现最小割不唯一会WA。于是暴力枚举分子分母的过了23333