DEF Java题解~~~代码已去除冗余，并保留必要的注释
好烦啊，瞎做呗，令上边俩角的元素相同，下边俩角的元素相同，可以消掉一部分，剩下的代数式分解因式即可拼凑，时间复杂度O(1)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
System.out.println("99 100 99\n101 1 "+(sc.nextInt()+101)+"\n1 1 1");
}
}
寻找目标子序列的数目，可以找出任意分解在不同区间的贡献值，考虑全部情况相加，大串的数量跟串的数量（贡献）有关，减小复杂度可用分层前缀后缀和，时间复杂度O(n+q)
import java.util.*;
import java.io.*;
public class Main{
static String red="red";
static Map<String,Integer> map=new HashMap<>();
static{
for(int i=0;i<3;i++){
for(int j=i;j<3;j++){
map.put(red.substring(i,j+1),map.size());
}
}
}
public static void main(String args[]) throws IOException{
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
String arr[]=bf.readLine().split(" ");
int n=Integer.parseInt(arr[0]),q=Integer.parseInt(arr[1]);
String s=bf.readLine();
long pre1[][]=new long[n+5][7],pre2[][]=new long[n+5][7];
for(int i=1;i<=n;i++){
pre1[i]=pre1[i-1].clone();
char c=s.charAt(i-1);
int idx=red.indexOf(c);
if(idx>=0){
for(int j=idx-1;j>=0;j--){
pre1[i][map.get(red.substring(j,idx+1))]+=pre1[i-1][map.get(red.substring(j,idx))];
}
pre1[i][map.get(String.valueOf(c))]++;
}
}
for(int i=n;i>0;i--){
pre2[i]=pre2[i+1].clone();
char c=s.charAt(i-1);
int idx=red.indexOf(c);
if(idx>=0){
for(int j=idx-1;j>=0;j--){
pre2[i][map.get(red.substring(j,idx+1))]+=pre2[i+1][map.get(red.substring(j,idx))];
}
pre2[i][map.get(String.valueOf(c))]++;
}
}
for(int i=0;i<q;i++){
arr=bf.readLine().split(" ");
int l=Integer.parseInt(arr[0]),r=Integer.parseInt(arr[1]);
long ans=0;
for(int j=0;j<=3;j++){
for(int k=j;k<=3;k++){
ans+=find1(pre1,1,l-1,substring(red,0,j-1))*find2(pre2,l,r,substring(red,j,k-1))*find1(pre1,r+1,n,substring(red,k,2));
}
}
bw.write(ans+"\n");
}
bw.flush();
}
static long find1(long pre1[][],int l,int r,String s){
if(s.length()>r-l+1){
return 0;
}
if(s.length()==0){
return 1;
}
long ans=pre1[r][map.get(s)]-pre1[l-1][map.get(s)];
for(int i=1;i<s.length();i++){
ans-=find1(pre1,1,l-1,s.substring(0,i))*find1(pre1,l,r,s.substring(i));
}
return ans;
}
static long find2(long pre2[][],int l,int r,String s){
if(s.length()>r-l+1){
return 0;
}
if(s.length()==0){
return 1;
}
long ans=pre2[l][map.get(s)]-pre2[r+1][map.get(s)];
for(int i=1;i<s.length();i++){
ans-=find2(pre2,r+1,pre2.length-5,s.substring(0,i))*find2(pre2,l,r,s.substring(i));
}
return ans;
}
static String substring(String s,int l,int r){
return l>r?"":s.substring(l,r+1);
}
}
利用线性基，将每个灯所能够造成的影响用128位的二进制数表示，高斯消元至上三角矩阵，之后按位尝试变为1，由于Java不含int128，因此本代码中部分位运算采用手动处理，时间复杂度O(n^3)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),p[][]=new int[n][2],idx[]=new int[n];
long mask[][]=new long[n][2],start[]=new long[2],xor[][]=new long[n][2],ans[]=new long[2];//假设每一维的比特数最大为60位
String s=sc.next();
for(int i=0;i<n;i++){
idx[i]=i;
p[i]=new int[]{sc.nextInt(),sc.nextInt()};
start[i/60]|=(long)(s.charAt(i)-'0')<<(i%60);
xor[i][i/60]|=1L<<(i%60);
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(p[i][0]==p[j][0]||p[i][1]==p[j][1]){
mask[i][j/60]|=1L<<(j%60);
}
}
}
for(int i=0;i<n;i++){
int curIdx=i;
for(int j=i+1;j<n;j++){
if(findMaxBit(mask[idx[curIdx]])<findMaxBit(mask[idx[j]])){
curIdx=j;
}
}
if(curIdx!=i){
idx[i]^=idx[curIdx];
idx[curIdx]^=idx[i];
idx[i]^=idx[curIdx];
}
int cur=findMaxBit(mask[idx[i]]);
if(cur==-1){
break;
}
for(int j=i+1;j<n;j++){
if(findMaxBit(mask[idx[j]])==cur){
mask[idx[j]]=findXor(mask[idx[j]],mask[idx[i]]);
xor[idx[j]]=findXor(xor[idx[j]],xor[idx[i]]);
}
}
}
for(int i=n-1,j=0;i>=0;i--){
if((start[i/60]>>(i%60)&1)==0){
while(j<n&&findMaxBit(mask[idx[j]])>i){
j++;
}
if(j==n||findMaxBit(mask[idx[j]])<i){
System.out.println("-1");
return;
}
start=findXor(start,mask[idx[j]]);
ans=findXor(ans,xor[idx[j]]);
}
}
System.out.println(Long.bitCount(ans[0])+Long.bitCount(ans[1]));
for(int i=0;i<n;i++){
if((ans[i/60]>>(i%60)&1)==1){
System.out.print((i+1)+" ");
}
}
}
static long[] findXor(long a[],long b[]){
//128位的异或
return new long[]{a[0]^b[0],a[1]^b[1]};
}
static int findMaxBit(long a[]){
for(int i=100;i>=0;i--){
if((a[i/60]>>(i%60)&1)==1){
return i;
}
}
return -1;
}
}
京公网安备 11010502036488号