本以为会是三道小强与阿米巴，结果打开题目一看发现了这个：

 

 

 

 

T1:

恩先写着一道

#include
      
       #include
       
        #include
        
         #include
         
          #define rep(s,t) for(int i=s;i<=t;i++)using namespace std;inline int read() {    char ch=getchar();int x=0,f=1;    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';    return x*f;}const int maxn=100010;const int maxnode=2000010;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]+1;if(l==r) return;     int mid=l+r>>1;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+1,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>>1;    if(k<=k2) return query(ls[y],ls[x],l,mid,k);    return query(rs[y],rs[x],mid+1,r,k-k2);    }int main() {    freopen("kth.in","r",stdin);    freopen("kth.out","w",stdout);    int n=read(),q=read();    rep(1,n) A[i]=B[i]=read();    sort(B+1,B+n+1);    rep(1,n) build(root[i],root[i-1],1,n,lower_bound(B+1,B+n+1,A[i])-B);    rep(1,q) {        int l=read(),r=read(),k=read();        printf("%d\n",B[query(root[r],root[l-1],1,n,r-l-k+2)]);             }    return 0;}
         
        
       
      

 

T2:

无脑爆搜+调整顺序，只搞出来5个点。

#include
      
       #include
       
        #include
        
         #include
         
          #define rep(i,s,t) for(int i=s;i<=t;i++)using namespace std;inline int read() {    char ch=getchar();int x=0,f=1;    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';    return x*f;}int cnt;char s[20][20];int rr[423],ry[324];int id(int x,int y) {
    return (((y-1)/4)*4+(x-1)/4)+1;}int r[20][20],c[20][20],sq[20][20],num[20][20],use[17];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[410];void dfs(int cur) {     if(cur==cnt+1) {          rep(i,1,16) {              rep(j,1,16) putchar(s[i][j]);              puts("");          }          exit(0);     }          else {          int x=A[cur].x,y=A[cur].y,z=num[x][y];          for(int d=1;d<=16;d++) if(!r[x][d]&&!c[y][d]&&!sq[z][d]){              r[x][d]=c[y][d]=sq[z][d]=1;use[d]++;              s[x][y]=(d<=10?d-1+'0':d-11+'A');dfs(cur+1);              r[x][d]=c[y][d]=sq[z][d]=0;use[d]--;          }     }}int sc[1010];int main() {    srand(time(0));    rr[6]=17;rr[7]=876;rr[10]=16;rr[12]=12;ry[10]=38;ry[6]=34;    freopen("sixteen7.in","r",stdin);    freopen("sixteen7.out","w",stdout);    sc['0']=1;sc['1']=2;sc['2']=3;sc['3']=4;    sc['4']=5;sc['5']=6;sc['6']=7;sc['7']=8;    sc['8']=9;sc['9']=10;sc['A']=11;sc['B']=12;    sc['C']=13;sc['D']=14;sc['E']=15;sc['F']=16;    rep(i,1,16) scanf("%s",s[i]+1);    rep(i,1,16) rep(j,1,16) {        num[i][j]=id(i,j);        if(s[i][j]=='.') {            A[++cnt]=(Point){i,j,0};            rep(k,1,16) if(s[i][k]!='.') A[cnt].s++;            rep(k,1,16) if(s[k][j]!='.') A[cnt].s++;            rep(k,1,16) rep(k2,1,16) if(s[k][k2]!='.'&&id(k,k2)==id(i,j)) A[cnt].s++;            if(i==6||i==7||i==10) A[cnt].s+=200;        }        else {            r[i][sc[s[i][j]]]=1;c[j][sc[s[i][j]]]=1;            sq[num[i][j]][sc[s[i][j]]]=1;        }    }    /*for(int i=1;i
         
        
       
      

T3:

 

恩让我回忆回忆2333

-------------------

似乎记得要二分答案，那就先二分答案吧。

考虑如何判定x是否可行，将|E|/|V|>k变形成|E|-k*|V|>0，发现这是个裸的最大权闭合子图。因为选中一条边能贡献1的权，但同时要依赖于两个端点也必须选，而这两个端点的贡献每个都是-k。那么跑一边最大流，算一下是否为m即可。

等等，这道题要你输出分数啊！那么最后再计算一下最优解，在网络中找那些指向汇点且被割断的边，这些边的另一端就是选择的点。

注意特判m=0

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #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=0,f=1;    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';    return x*f;}const int maxn=2010;const int maxm=50100;const double eps=1e-5;int n,m,u[5010],v[5010],A[60],is[60],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=0;         fill(first+1,first+n+1,-1);    }     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+1,vis+n+1,0);        queue
           
             q;q.push(s);d[s]=0;vis[s]=1; 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]=1; d[e.to]=d[x]+1; q.push(e.to); } } } return vis[t]; } double DFS(int x,double a) { if(x==t||a
            
             eps) { e.flow-=f;edges[i^1].flow+=f; flow+=f;a-=f;if(a
             
              s=s;this->t=t; while(BFS()) ans+=DFS(s,1e50); return ans; } void solve() { rep(0,m-1) if(edges[i].to==t&&edges[i].flow
              
               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 0;} rep(1,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(1,cnt) is[A[i]-m]=1; rep(1,m) if(is[u[i]]&&is[v[i]]) ans++; printf("%d/%d\n",ans/gcd(ans,cnt),cnt/gcd(ans,cnt)); return 0;}
              
             
            
           
          
         
        
       
      

 交上去WA了一个点，FHQ带大家测了半天，最后发现最小割不唯一会WA。于是暴力枚举分子分母的过了23333