C~F题解

C 异或故事

对于比特位多于一个的正数，可以分解为该数字去掉最低位以及最低位的异或，而对于比特位单独的数字，则分解为该数字加1和“它自己跟它加1异或后的数”，时间复杂度O(T)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++){
            int a=sc.nextInt();
            System.out.println(Integer.bitCount(a)==1?a+1+" "+(a^(a+1)):(a&-a)+" "+(a&(a-1)));
        }
    }
}

D 构造故事

先排序，那么从大到小，尝试让相邻的两个作为较大边，既可以保证两边之和尽可能大，又可以保证边之差尽可能小，从而直接验证较小的那个相邻的数是否可以即可，时间复杂度O(Tnlogn)

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=0;i<t;i++){
            int n=sc.nextInt(),a[]=new int[n];
            for(int j=0;j<n;j++){
                a[j]=sc.nextInt();
            }
            Arrays.sort(a);
            long ans=-1;
            for(int j=n-2;j>0;j--){
                if(a[j+1]-a[j]<a[j-1]){
                    ans=(long)a[j+1]+a[j]+a[j-1];
                    break;
                }
            }
            System.out.println(ans);
        }
    }
}

E 约会故事

用差分来维护快乐时段，需要注意快乐时间段的可能跨天，，哈希集合来维护奶茶，直接按题意模拟，时间复杂度O(n+m+q+C)，其中C==1440

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt(),count[]=new int[1500];
        Set<String> set=new HashSet<>();
        for(int i=0;i<n;i++){
            int start=find(sc.next()),end=find(sc.next());
            count[start]++;
            count[end+1]--;
            if(start>=end){
                count[0]++;
            }
        }
        for(int i=1;i<1440;i++){
            count[i]+=count[i-1];
        }
        for(int i=0;i<m;i++){
            set.add(sc.next());
        }
        int q=sc.nextInt();
        for(int i=0;i<q;i++){
            boolean invited=true,stayed=true;
            int inviteTime=find(sc.next());
            if(inviteTime>=120||count[inviteTime]==0){
                invited=false;
            }
            if(find(sc.next())>find(sc.next())){
                stayed=false;
            }
            if(!set.contains(sc.next())){
                stayed=false;
            }
            System.out.println(invited?(stayed?"Winner xqq":"Joker xqq"):"Loser xqq");
        }
    }
    static int find(String s){
        return Integer.parseInt(s.substring(0,2))*60+Integer.parseInt(s.substring(3));
    }
}

F 不是烤串故事

首先对于某个长度的翻转前缀，lcp的具有二段性，因此可以二分，，那么判断字符串相等的时候可以合理利用字符串哈希，需要分别几段s和t的正哈希以及s的反哈希，在判断的时候需要根据前缀个所判断lcp的大小关系稍微分类讨论，时间复杂度O(C+Tnlogn)，其中C==1e6

import java.util.*;
public class Main{
    static long mod=(int)1e9+9,base=307,pow[]=new long[(int)1e6+10];
    public static void main(String args[]){
        pow[0]=1;
        for(int i=1;i<=1e6;i++){
            pow[i]=pow[i-1]*base%mod;
        }
        Scanner sc=new Scanner(System.in);
        int T=sc.nextInt();
        for(int i=0;i<T;i++){
            int n=sc.nextInt();
            String s=sc.next(),t=sc.next();
            //分别代表的是s的正哈希，t的正哈希，s的反哈希
            long hash1[]=new long[n+5],hash2[]=new long[n+5],hash3[]=new long[n+5];
            for(int j=1;j<=n;j++){
                hash1[j]=(hash1[j-1]*base+s.charAt(j-1))%mod;
                hash2[j]=(hash2[j-1]*base+t.charAt(j-1))%mod;
                hash3[n-j+1]=(hash3[n-j+2]*base+s.charAt(n-j))%mod;
            }
            int max=0,idx=1;
            for(int j=1;j<=n;j++){
                int l=0,r=n;
                while(l<r){
                    int mid=(l+r)>>1;
                    if(check(j,mid,hash1,hash2,hash3)){
                        l=mid;
                    }
                    else{
                        r=mid-1;
                    }
                    if(l==r-1){
                        if(check(j,r,hash1,hash2,hash3)){
                            l=r;
                        }
                        break;
                    }
                }
                if(l>max){
                    max=l;
                    idx=j;
                }
            }
            System.out.println(max+" "+idx);
        }
    }
    static boolean check(int last,int len,long hash1[],long hash2[],long hash3[]){
        return hash2[len]==(len<=last?(hash3[last-len+1]+mod-hash3[last+1]*pow[len]%mod)%mod:((hash3[1]+mod-hash3[last+1]*pow[last]%mod)%mod*pow[len-last]%mod+hash1[len]+mod-hash1[last]*pow[len-last]%mod)%mod);
    }
}

听说还有线性方法。。。还不会Z函数，等等