CFEDU-142-1792

· · 个人记录

感觉很好的一套题目，水题也有意思。

A GamingForces，考察排序与贪心。

B Stand-up Comedian 数学，推式子。

有点意思的递推

#include<bits/stdc++.h>
using namespace std;
const int N=20;
int a[N],n; 
int work(){

    int ans=0,f=0;//ans为进行轮数，f为当前ab最小的分数。
    for(int i=1;i<=4;i++)cin>>a[i];
    if(a[2]>a[3])swap(a[2],a[3]);
    ans=a[1],f=a[1];
    if(f==0){
        ans=min(1,a[2]+a[3]+a[4]);
        return ans;
    }
    int tmp=min(a[3]-a[2],a[1]);//a[3]>=a[2] 
    f-=tmp;
    if(a[3]-a[2]>a[1])ans=a[1]+2*a[2]+a[1]+1;//a,b有a1分，
    else ans=a[1]+2*a[2]+tmp+min(f+1,a[4]);
    return ans;
}
int main(){

    int t;
    cin>>t;
    while(t--){
        cout<<work()<<endl;
    }
}

C

排序、贪心，分析出成对出现是本题的关键，由内到外连续的升序为可以不动的数对。

/*
最多操作n/2次。
最后一次一定操作(1,n),逆序为(2,n-1)...(n/2,n+1-n/2)
                 n/2         n/2-1..k. 1 
最容易想到的方法是二分答案，模拟从第k次操作开始执行，看能否完成有序排列。
时间复杂度o(nlogn)

在操作的过程中，手工操作发现，
    如果只需要1次操作，那么拿出(1,n)后，数据已经有序。
    同理，如果需要k次操作，那么拿出(1..k) ... (n-k+1,n)后 
                     剩下的k+1,k+2,...n-k-1,n-k已经有序了。 
            3 8 1 4 5 2 6 9 7
    删掉19  3 8   4 5 2 6   7
    删掉28  3     4 5   6   7 
    用链表删除吗？删除链表o(1),判断有序o(n)，复杂度太高。
    我们只需要知道剩下的3 4 5 6 7在原始数据中是连续上升子序列即可。
    找数列中最大连续上升子序列的长度。
    我们记录一x的位置，看他是否在x-1的前面。 
*/ 
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+9;
int a[N],n; 
int work(){
    int x,ans;
    scanf("%d",&n);
    for(int i=0;i<=n+1;i++)a[i]=0; 
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        a[x]=i; 
    }
    ans=n/2;
    //1 2  8 9满座这样的条件不用动。
    //从内层结构开始，看是否需要移动 4 5 6  a[4]<a[5]  a[5]<a[6]

    for(int i=n/2;i>=1;i--){
        if(a[i]<a[i+1]&&a[n-i]<a[n-i+1]){
            ans--;
        }
        else break;
    } 
    return ans; 

}
int main(){
        int t;
    cin>>t;
    while(t--){
        cout<<work()<<endl;
    }
}

D Fixed Prefix Permutations

逆向思维，找到一个数列的逆序列，转化为字符串的前缀匹配。利用tire树或者哈希完成。

/*
 8 10
3 4 9 6 10 2 7 8 1 5
3 9 1 8 5 7 4 10 2 6
3 10 1 7 5 9 6 4 2 8
1 2 3 4 8 6 10 7 9 5
1 2 3 4 10 6 8 5 7 9
9 6 1 2 10 4 7 8 3 5
7 9 3 2 5 6 4 8 1 10
9 4 3 7 5 6 1 10 8 2
p*q=r: r[j]=q[p[j]]
期望得到：q[p[j]]=j
比如：a'*a3=10
j==1: q[3]=1, p1=3;  j=2,q[p[2]]=2,p[2]=9
    p[q[j]]=j
i    :1  2  3  4  5  6  7  8  9  10
a3  q:3  10 1  7  5  9  6  4  2  8
a3' p:3  9  1  8  5  7  4  10 6  2
那么找出a3的逆排列a'
    ai*a3即为ai与a3'的最大前缀,记为：f(ai,a3')。
    ans（ai）=max(f(ai*aj'))

算法步骤：贪心求出每一个aj',存入字典序
          对每个ai，查找其在字典序上的最大前缀。 

*/ 

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10,M=12;
int t,n,m,trie[800005][11],cnt=1;
int a[N][M];
void insert(int b[]){
    int p=0;
    int temp[M]={0};//p[q[j]]=j
    for(int i=1;i<=m;i++)temp[b[i]]=i;
    for(int i=1;i<=m;i++){
        int v=temp[i];
        if(!trie[p][v])trie[p][v]=cnt++;
        p=trie[p][v];
    }
}
int ask(int b[]){
    int p=0,ans=0;
    for(int i=1;i<=m;i++){
        int v=b[i];
        if(trie[p][v]){
            ans++;
            p=trie[p][v];
        }else break;
    }
    return ans;
}
int main(){
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=0;i<cnt;i++)
            for(int j=0;j<=10;j++)
                trie[i][j]=0;
        cnt=1;

        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
            insert(a[i]);
        }
        for(int i=1;i<=n;i++){
            cout<<ask(a[i])<<" ";
        }
        printf("\n");
    }
}