新田忌赛马
【问题描述】
(注：此题为d2t2-难度)
田忌又在跟大王van赛马的游戏
田忌与大王一共有2n匹马，每个马都有一个能力值x,1<=x<=2n且每匹马的x互不相同。每次田忌与大王放出一匹马，较大的获胜。但是田忌有一个能力，在任何比赛的开始前，他可以把马变成x较小的获胜，并一直持续到比赛结束
田忌可以一直不用这个能力，也可以在第一轮前使用
现在，田忌已经知道了大王的出马顺序，田忌要问聪明的你，他最多能获得几次胜利？
【输入格式】
第一行为一个整数：N(1<=N<=50000)接下来 一行n个数，为大王的顺序出场的n匹马的能力值（田忌的马可以通过此求出）
【输出格式】
一个整数，表示最多的获胜次数
【样例输入】
4
1
8
4
3
【样例输出】
3

【样例说明】
田忌第一次出能力为7的马获胜
第二次开始前使用能力，出能力为6的马获胜
第三次出能力为5的马失败
第四次出能力为2的马获胜
总共3次
【出题人的关怀】
乱搞出奇迹（雾）
大胆猜想，不要证明
【数据规模】
对于20%的数据，n<=10
对于40%的数据 n<=20
对于35%的数据，不使用能力也可获得最多胜利(即20个点中有7个点不使用能力的程序能过（雾）)
前3个档的总分为60分（出题人的关怀）
对于80%的数据，n<=5000
对于100%的数据，n<=50000,

题解
首先暴力。。N!似乎就有20分了
然后2^n就有40分了。。
然后第3个档考虑能赢就选比他大的最小的即可60分。。
关于80分
我们考虑枚举分割线，就是使用技能的时间，对于田忌的马也相应分成比较大的或小的
正解
贪心，令f[i]表示前i个每次都出比对方稍微大一点的牌，最多能赢几次
g[i]表示从i-n中每次出比对方稍微小一点的牌，最多赢几次。
ans=max(f[i]+g[i+1]) 0<=i<=n

看到题目也是头昏眼花，把小于等于10的情况用全排列跑，结果这一块有两个点超时。
因为使用了能力之后，输赢直接逆转，所以倒过来从后往前跑，再枚举使用能力的位置，取胜利数最大的一次。

#include<bits/stdc++.h>
using namespace std;
set <int> x,y;
set <int>::iterator z;
int n,s,a[120000],b[120000],p[120000],q[120000];
int main(){
    freopen("horse.in","r",stdin);
    freopen("horse.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[a[i]]=1;
    }
    for(int i=1;i<=n*2;i++){
        if(b[i]==0){
            x.insert(i);
            y.insert(n*2-i);
        }
    }
    for(int i=1;i<=n;i++){
        z=x.upper_bound(a[i]);
        if(z!=x.end()){
            p[i]=p[i-1]+1;
            x.erase(z);
        }
        else p[i]=p[i-1];
    }
    for(int i=n;i>=1;i--){
        z=y.upper_bound(n*2-a[i]);
        if(z!=y.end()){
            q[i]=q[i+1]+1;
            y.erase(z);
        }
        else q[i]=q[i+1];
    }
    s=max(p[n],q[1]);
    for(int i=1;i<n;i++)
        s=max(s,p[i]+q[i+1]);
    cout<<s;
    return 0;
}

会议
【问题背景】
yukuai26准备出一道水题，但是他不知道想出啥，于是召集了一堆人开会
【问题描述】
开会当然需要在一个特定的城市开会，我们规定他们为0城市，这n个人在不同的1-n的城市中，他们需要乌鸦坐飞机才能到达0号城市。
有一堆飞机航线，只有2种航线，一种从0到其他城市，一种从其他城市到0，飞机有d[i],f[i],t[i],c[i]表示时间，起点，终点，和花费。每个人需要从他们的城市出发，所有人在0号城市待上k天开会，最后返回。注意，开会的开始第一天和最后一天是不能坐飞机来到或离开0号城市的
那么，你能来帮他们算算他们最少共需要多少钱吗？
如果不能满足要求，请输出-1（你觉得会有多少分呢）
【输入格式】
第一行一个正整数 n,m,k表示有0-n这些城市，m条飞机线，k天的开会时间
第2-m+1行为 每行4个整数
【输出格式】
1个数，如果有解输出最小的花费，无解输出-1
【样例输入1】
1 2 10
20 0 1 36
10 1 0 28
【样例输出1】
-1
【样例输入2】
2 5 5
1 1 0 1
2 2 0 100
3 2 0 10
9 0 1 1000
10 0 2 10000
【样例输出2】
11011

【数据规模】
对于20%的数据，n,m<=10
对于40%的数据，n<=100 m<=3000
对于另20%的数据，c[i],d[i]<=1
对于另20%的数据，d[i]为i*2-1且k为1
对于100%的数据，n,m<=1e5,k<=1e6 f[i],t[i]<=n ,1<=c[i],d[i]<=1e6
【出题人的关怀】
难度为d2t1哦，暴力80还是很容易的

题解##

T2 meet
20分 暴力。
40分 大暴力
另外20分。。输出-1
再另外20分。。D[i]=i*2-1,K为1的话，就根本不用管开会的时间啊.
我们考虑维护2个数组f[i],g[i],f[i]表示在i时间前所有人到0号节点的最小花费，如果不能为inf,g[i]表示在i时间后所有人从0号节点回家的最小化费，如果不能为inf
对于每个f[i]，通过二分找到一个最小的g[j]
使得他们之间至少相差k
然后ans取min即可

这道题要双向枚举每个时间点所有人到达的最小花费

然后枚举开会的时间段，线性求出最小值。

//#include<bits/stdc++.h>
//using namespace std;
//int n,m,k,d[120000],f[120000],t[120000],c[120000],last=-0x3f3f3f3f,first=0x3f3f3f3f;
//int go[],back[],price;
//bool visgo[120000],visback[120000];
//int main() {
//  // freopen("meet.in","r",stdin);
//  // freopen("meet.out","w",stdout);
//  cin>>n>>m>>k;
//  for(int i=1; i<=m; i++) {
//      cin>>d[i]>>f[i]>>t[i]>>c[i];
//      if(f[i]==0) back[t[i]]++;
//      if(t[i]==0) go[f[i]]++;
//      if(f[i]==0&&d[i]<first) first=d[i];
//      if(t[i]==0&&d[i]>last) last=d[i];
//  }
////    cout<<first<<" "<<last<<endl;
//  if(first-last<=k) {
//      cout<<"-1";
//      return 0;
//  }
//  first=0x3f3f3f3f;
//  last=-0x3f3f3f3f;
//  for(int i=1; i<=n; i++) {
//      if(go[f[i]]==1) {
//          for(int j=1; j<=m; j++)
//              if(f[j]==i&&t[j]==0) {
//                  price+=c[j];
//                  visgo[f[i]]=true;
//                  if(d[i]>last) last=d[i];
//                  goto die;
//              }
//      }
//      if(back[f[i]]==1) {
//          for(int j=1; j<=m; j++)
//              if(t[j]==i&&f[j]==0) {
//                  price+=c[j];
//                  visback[f[i]]=true;
//                  if(d[i]<first) first=d[i];
//                  goto die;
//              }
//      }
//die:
//      ;
//  }
//  for(int i=1; i<=n; i++) {
//      if(visgo[i]==true&&visback[i]==false) {
//          int q=0x3f3f3f3f,ansj;
//          for(int j=1;j<=m;j++)
//              if(t[j]==i&&c[j]<q){
//                  q=c[j];
//                  ans=j;
//              }
//          price+=q;
//          visback[i]=true;
//
//      }
//      else if(visgo[i]==false&&visback[i]==true){
//
//
//      }
//      else if(visgo[i]==false&&visback[i]==false){
//
//
//
//
//      }
//
//
//  }
//
//
//
//  return 0;
//}











// #pragma GCC optimize(2)
// #include<bits/stdc++.h>
// #include<cctype>
// #define int long long
// using namespace std;
// int d[120000],f[120000],t[120000],c[120000];
// int n,m,k,mxt,ans=0x3f3f3f3f;
// int go[120000],back[120000],first=0x3f3f3f3f,last=-0x3f3f3f3f;
// inline int read() {
//  int X=0,w=0;
//  char ch=0;
//  while(!isdigit(ch)) {
//      w|=ch=='-';
//      ch=getchar();
//  }
//  while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
//  return w?-X:X;
// }
// signed main() {
//  freopen("meet.in","r",stdin);
//  freopen("meet.out","w",stdout);
//  n=read();
//  m=read();
//  k=read();
//  for(int i=1; i<=m; i++) {
//      d[i]=read();
//      f[i]=read();
//      t[i]=read();
//      c[i]=read();
//      if(d[i]>mxt) mxt=d[i];
//      if(f[i]==0) back[t[i]]++;
//      if(t[i]==0) go[f[i]]++;
//      if(f[i]==0&&d[i]<first) first=d[i];
//      if(t[i]==0&&d[i]>last) last=d[i];
//  }
//  if(first-last<=k) {
//      cout<<"-1";
//      return 0;
//  }
//  if(k==1) {
//      for(int i=1; i<=mxt; i++) {
//          memset(go,0x3f3f3f3f,sizeof go);
//          memset(back,0x3f3f3f3f,sizeof back);
//          int pri=0;
//          for(int j=1; j<=m; j++) {
//              if(f[j]==0) {
//                  if(d[j]>i&&back[t[j]]>c[j]) {
//                      back[t[j]]=c[j];
//                  }
//              } else if(t[j]==0) {
//                  if(d[j]<i&&go[f[j]]>c[j]) {
//                      go[f[j]]=c[j];
//                  }
//              }
//          }
//          for(int ii=1; ii<=n; ii++) {
//              pri+=(back[ii]+go[ii]);
//          }
//          if(pri<ans&&pri) ans=pri;
//      }
//      cout<<ans;
//      return 0;
//  } else {
//      cout<<"-1";
//      return 0;


//  }


// }






#include<bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;
struct node{
    ll d,u,v,pay;
    bool operator <(const node &x)const{
        return d<x.d;
    }
}a[1000000];
const ll inf=1e12,t=1e6;
ll l[t+10], r[t+10], cost[t], n, m, k, now, ans;
inline ll read(){
    ll x=0,f=1;char dd;
    for(;!isdigit(c);dd){if(c=='-')f=-1;if(c==EOF)return EOF;}
    for(;isdigit(c);dd)x=(x<<1)+(x<<3)+(c^48);return x*f;
}
signed main() {
    freopen("meet.in", "r", stdin);
    freopen("meet.out", "w", stdout);
    cin >> n >> m >> k;
    for (ll i = 1; i <= m; i++) {
        a[i].d=read();
        a[i].u=read();
        a[i].v=read();
        a[i].pay=read();
    }
    sort(a + 1, a + m + 1);
    for (ll i = 1; i <= n; i++) cost[i] = inf;
    l[0] = inf*n;
    now = 1;
    for (ll i=1;i<=t;++i){
        l[i]=l[i-1];
        while (a[now].d==i){
            ll x=now++;
            if (!a[x].u) continue;
            if (a[x].pay<cost[a[x].u]){
                l[i]=l[i]-cost[a[x].u]+a[x].pay;
                cost[a[x].u]=a[x].pay;
            }
        }
    }
    for (ll i = 1; i <= n; i++) cost[i] =inf;
    r[t+1] = inf*n;
    now = m;
    for (ll i=t;i;--i){
        r[i]=r[i+1];
        while (a[now].d==i){
            ll x=now--;
            if (!a[x].v) continue;
            if (a[x].pay<cost[a[x].v]){
                r[i]=r[i]-cost[a[x].v]+a[x].pay;
                cost[a[x].v]=a[x].pay;
            }
        }
    }
    ans = inf;
    for (ll i=1;i+k+1<=t;++i){
        ans=min(ans,l[i]+r[i+k+1]);
    }
    if (ans == inf) cout << "-1";
    else cout << ans;
    return 0;
}

将军
【问题描述】
手持倚天剑的将军wzp，有着很多士兵
Wzp有n个士兵，每个士兵有一个能力值，他正在与cqz与szb搏杀着，wzp准备把n个士兵排成一个列，要求第i个士兵的能力值不小于第i/k（下取整）个士兵的能力值。同时，wzp希望第一个士兵能力值尽可能大，如果相同，希望第二个士兵能力值尽可能大，如果相同。。以此类推。
简单题意：给定n,k,d数组,找出一个字典序最大的排列，使得d[i]>=dtrunc(i/k)，trunc为下取整
【输入格式】
输入文件general.in共有两行，第一行为n和k（其中k为一个实数！！）
第二行n个数，为士兵的能力值
【输出格式】
输出一行n个数，为字典序最大的符合要求的排列

【样例输入】
4 2.0
114 514 1919 810 。

【输出样例】
114 810 514 1919

【出题人的关怀】
此题欢迎乱搞同学（吗？）

题解

image.png
image.png
image.png
image.png
image.png
image.png
image.png

这题的条件是一个树状结构，用线段树来维护子树中已经被确定的数。打表也有25分诶。

//#pragma GCC optimize(2)
//#include<bits/stdc++.h>
//using namespace std;
//int n,a[120000];
//double k;
//int main() {
//  freopen("general.in","r",stdin);
//  freopen("general.out","w",stdout);
//  cin>>n>>k;
//  for(int i=1; i<=n; i++) cin>>a[i];
//  sort(a+1,a+n+1);
//  if(int(k)==2) {
//      if(n==1) {
//          cout<<a[1];
//      } else if(n==2) {
//          cout<<a[1]<<" "<<a[2];
//      } else if(n==3) {
//          cout<<a[1]<<" "<<a[3]<<" "<<a[2];
//      } else if(n==4) {
//          cout<<a[1]<<" "<<a[3]<<" "<<a[2]<<" "<<a[4];
//      } else if(n==5) {
//          cout<<a[1]<<" "<<a[3]<<" "<<a[2]<<" "<<a[5]<<" "<<a[4];
//      } else if(n==6) {
//          cout<<a[1]<<" "<<a[4]<<" "<<a[2]<<" "<<a[6]<<" "<<a[5]<<" "<<a[3];
//      } else if(n==7) {
//          cout<<a[1]<<" "<<a[5]<<" "<<a[2]<<" "<<a[7]<<" "<<a[6]<<" "<<a[4]<<" "<<a[3];
//      } else if(n==8) {
//          cout<<a[1]<<" "<<a[6]<<" "<<a[2]<<" "<<a[8]<<" "<<a[7]<<" "<<a[5]<<" "<<a[4]<<" "<<a[3];
//      } else if(n==9) {
//          cout<<a[1]<<" "<<a[6]<<" "<<a[2]<<" "<<a[8]<<" "<<a[7]<<" "<<a[5]<<" "<<a[4]<<" "<<a[3]<<" "<<a[9];
//      } else if(n==10) {
//          cout<<a[1]<<" "<<a[6]<<" "<<a[2]<<" "<<a[9]<<" "<<a[7]<<" "<<a[5]<<" "<<a[4]<<" "<<a[3]<<" "<<a[10]<<" "<<a[8];
//      }
//  } else if(k==n) {
//      cout<<a[n-1];
//      for(int i=n-2; i>=1; i--) cout<<" "<<a[i];
//      cout<<" "<<a[n];
//  } else if(int(k)==3) {
//      if(n==1) {
//          cout<<a[1];
//      } else if(n==2) {
//          cout<<a[2]<<" "<<a[1];
//      } else if(n==3) {
//          cout<<a[2]<<" "<<a[1]<<" "<<a[3];
//      } else if(n==4) {
//          cout<<a[2]<<" "<<a[1]<<" "<<a[4]<<" "<<a[3];
//      } else if(n==5) {
//          cout<<a[2]<<" "<<a[1]<<" "<<a[5]<<" "<<a[4]<<" "<<a[3];
//      } else if(n==6) {
//          cout<<a[3]<<" "<<a[1]<<" "<<a[6]<<" "<<a[5]<<" "<<a[4]<<" "<<a[2];
//      } else if(n==7) {
//          cout<<a[4]<<" "<<a[1]<<" "<<a[7]<<" "<<a[6]<<" "<<a[5]<<" "<<a[3]<<" "<<a[2];
//      } else if(n==8) {
//          cout<<a[5]<<" "<<a[1]<<" "<<a[8]<<" "<<a[7]<<" "<<a[6]<<" "<<a[4]<<" "<<a[3]<<" "<<a[2];
//      } else if(n==9) {
//          cout<<a[5]<<" "<<a[1]<<" "<<a[8]<<" "<<a[7]<<" "<<a[6]<<" "<<a[5]<<" "<<a[4]<<" "<<a[3]<<" "<<a[9];
//      } else if(n==10) {
//          cout<<a[5]<<" "<<a[1]<<" "<<a[8]<<" "<<a[7]<<" "<<a[6]<<" "<<a[5]<<" "<<a[4]<<" "<<a[3]<<" "<<a[10]<<" "<<a[9];
//      }
//  } else {
//      for(int i=1; i<=n; i++) cout<<a[i]<<" ";
//  }
//  return 0;
//}




#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,x<<1
#define rson mid+1,r,x<<1|1
int a[500050], ans[500050], head[500050], to[500050], nxt[500050], cnt, si[500050], sum[2000020];

void add(int x, int y) {
    to[++cnt] = y;
    nxt[cnt] = head[x];
    head[x] = cnt;
    si[x] += si[y];
}

void update(int p, int a, int l, int r, int x) {
    sum[x] += a;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (p <= mid) update(p, a, lson);
    else update(p, a, rson);
}

int find(int k, int l, int r, int x) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    if (sum[x << 1 | 1] < k) return find(k - sum[x << 1 | 1], lson);
    else return find(k, rson);
}
inline int read() {
    char c = getchar();
    int tot = 1;
    while ((c < '0' || c > '9') && c != '-') c = getchar();
    if (c == '-') {
        tot = -1;
        c = getchar();
    }
    int sum = 0;
    while (c >= '0' && c <= '9') {
        sum = sum *10 + c - '0';
        c = getchar();
    }
    return sum * tot;
}
inline void write(int x) {
    if (x < 0)putchar('-'), x = -x;
    if (x > 9)write(x / 10); putchar(x % 10 | 48);
}
int main() {
    freopen("general.in", "r", stdin);
    freopen("general.out", "w", stdout);
    int n, t, l, last = 1;
    double k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) a[i] = read(), si[i] = 1;
    sort(a + 1, a + n + 1);
    for (int i = n; i; i--) add((int)floor(i / k), i);
    for (int i = head[0]; i; i = nxt[i]) update(to[i], si[to[i]], 1, n, 1);
    for (int i = 1; i <= n; i = last) {
        while (last <= n && a[i] == a[last]) last++;
        for (int j = last - i; j; j--) {
            t = find(j, 1, n, 1);
            ans[t] = a[i];
            update(t, -si[t], 1, n, 1);
            for (l = head[t]; l; l = nxt[l])
                update(to[l], si[to[l]], 1, n, 1);
        }
    }
    for (int i = 1; i <= n; i++) {write(ans[i]); putchar(' ');}
    return 0;
}