C~F Java题解，代码已去除冗余~~~
对所有蛋挞的连通块建图并深搜，符合要求的点，要么是单点块，要么是根据tarjan算法求出的割点，时间复杂度O(n)
import java.util.*;
public class Main{
static int move[][]={{0,1},{0,-1},{1,0},{-1,0}},timeStamp=1;
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),time[]=new int[n*2],low[]=new int[n*2],ans=0;
String s[]={sc.next(),sc.next()};
List<Integer> path[]=new List[n*2];
for(int i=0;i<n*2;i++){
if(s[i/n].charAt(i%n)=='.'){
path[i]=new ArrayList<>();
for(int mo[]:move){
int x=i/n+mo[0],y=i%n+mo[1];
if(x>=0&&x<2&&y>=0&&y<n&&s[x].charAt(y)=='.'){
path[i].add(x*n+y);
}
}
}
}
for(int i=0;i<n*2;i++){
if(path[i]!=null&&time[i]==0){
ans+=tarjan(i,-1,path,time,low);
}
}
System.out.println(ans);
}
static int tarjan(int k,int pre,List<Integer> path[],int time[],int low[]){
time[k]=low[k]=timeStamp++;
int ans=0,child=0,inc=0;
for(int a:path[k]){
if(low[a]==0){
child++;
ans+=tarjan(a,k,path,time,low);
if(pre!=-1&&low[a]>=time[k]||pre!=-1&&low[a]>time[k]){
inc=1;
}
low[k]=Math.min(low[k],low[a]);
}
else if(a!=pre){
low[k]=Math.min(low[k],low[a]);
}
}
if(pre==-1&&(child>=2||child==0)){
inc=1;
}
return ans+inc;
}
}
连边的点的连通块之间颜色必须一样，因此需要找出连通块并找出其中颜色最多的数量，其他的点就需要重新染色
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(),c[]=new int[n+5],ans=0;
List<Integer> path[]=new List[n+5];
for(int i=1;i<=n;i++){
c[i]=sc.nextInt();
path[i]=new ArrayList<>();
}
for(int k=0;k<m;k++){
int i=sc.nextInt(),j=sc.nextInt();
path[i].add(j);
path[j].add(i);
}
for(int i=1;i<=n;i++){
if(c[i]>0){
int count=0,max=1;
Map<Integer,Integer> map=new HashMap<>();
map.put(c[i],map.getOrDefault(c[i],0)+1);
Queue<Integer> q=new LinkedList<>();
q.add(i);
c[i]=0;
while(!q.isEmpty()){
count++;
int a=q.poll();
for(int b:path[a]){
if(c[b]>0){
map.put(c[b],map.getOrDefault(c[b],0)+1);
q.add(b);
max=Math.max(max,map.get(c[b]));
c[b]=0;
}
}
}
ans+=count-max;
}
}
System.out.println(ans);
}
}
一组括号之前可以移除的就是除了自己以及包裹自己的那些括号了，记录每个括号的层数即可，时间复杂度O(n)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),count=0,dep=0,ans[]=new int[n];
String s=sc.next();
for(char c:s.toCharArray()){
if(c=='('){
dep++;
ans[count]=n-dep;
count++;
}
else{
dep--;
}
if(dep<0||dep>n){
System.out.println("-1");
return;
}
}
for(int a:ans){
System.out.print(a+" ");
}
}
}
线段树记录每个区间的乘积，以及魅力值，用延迟标记，时间复杂度O((n+q)*(logn)*2)
import java.io.*;
public class Main{
static int mod=(int)1e9+7;
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]),a[]=new int[n];
arr=bf.readLine().split(" ");
for(int i=0;i<n;i++){
a[i]=Integer.parseInt(arr[i]);
}
SegTree st=new SegTree(0,n-1);
build(st,a);
for(int i=0;i<q;i++){
arr=bf.readLine().split(" ");
if(arr[0].equals("1")){
modify(st,Integer.parseInt(arr[1])-1,Integer.parseInt(arr[2])-1,Integer.parseInt(arr[3]));
}
else{
bw.write(find(st,Integer.parseInt(arr[1])-1,Integer.parseInt(arr[2])-1)[1]+"\n");
}
}
bw.flush();
}
static long[] find(SegTree st,int a,int b){
int l=st.l,r=st.r;
if(l==a&&r==b){
return new long[]{st.pro,st.sum};
}
else{
clear(st);
int mid=(l+r)>>1;
if(b<=mid){
return find(st.left,a,b);
}
if(a>mid){
return find(st.right,a,b);
}
long arr1[]=find(st.left,a,mid),arr2[]=find(st.right,mid+1,b);
return new long[]{arr1[0]*arr2[0]%mod,(arr1[1]+arr2[1]*arr1[0])%mod};
}
}
static void modify(SegTree st,int a,int b,int x){
int l=st.l,r=st.r;
if(l==a&&r==b){
fill(st,x);
}
else{
clear(st);
int mid=(l+r)>>1;
if(b<=mid){
modify(st.left,a,b,x);
}
else if(a>mid){
modify(st.right,a,b,x);
}
else{
modify(st.left,a,mid,x);
modify(st.right,mid+1,b,x);
}
pushup(st);
}
}
static void build(SegTree st,int a[]){
int l=st.l,r=st.r;
if(l==r){
st.pro=st.sum=a[l];
}
else{
int mid=(l+r)>>1;
st.left=new SegTree(l,mid);
st.right=new SegTree(mid+1,r);
build(st.left,a);
build(st.right,a);
pushup(st);
}
}
static void clear(SegTree st){
if(st.l<st.r&&st.val>0){
fill(st.left,st.val);
fill(st.right,st.val);
st.val=-1;
}
}
static void pushup(SegTree st){
if(st.l!=st.r){
st.pro=st.left.pro*st.right.pro%mod;
st.sum=(st.left.sum+st.right.sum*st.left.pro)%mod;
}
}
static void fill(SegTree st,long val){
st.val=val;
int l=st.l,r=st.r;
st.pro=pow(val,r-l+1);
st.sum=val==1?r-l+1:(pow(val,r-l+1)-1)*pow(val-1,mod-2)%mod*val%mod;
}
static long pow(long a,long b){
long ans=1;
for(;b!=0;b>>=1,a=a*a%mod){
if(b%2==1){
ans=ans*a%mod;
}
}
return ans;
}
}
class SegTree{
int l,r;
long sum,pro,val=-1;
SegTree left,right;
public SegTree(int l,int r){
this.l=l;
this.r=r;
}
}
京公网安备 11010502036488号