C~G Java题解，代码已去除冗余，并保留必要注释~~~
考虑数列前缀和（把0看做-1），翻转一个0可以使得该位置及其以后得前缀和的值增加2，翻转1则无变化，因此假如原序列本来就符合，那么随便翻转即可；假如前缀和最小值小于-2，那么无解；其他情况只需要翻转首个负数前缀和之前的一个0即可，时间复杂度O(n)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),pre=0,firstMinus=0,count=0;
String s=sc.next();
for(int i=0;i<n;i++){
int a=s.charAt(i)-'0';
pre+=a*2-1;
if(firstMinus==0&&a==0){
count++;
}
if(pre<-2){
System.out.println(0);
return;
}
else if(pre<0){
firstMinus=1;
}
}
System.out.println(firstMinus==1?count:n);
}
}
如C中的思路，假如前缀和全部非负，那么任意翻转，最小值小于-4，无解；最小值不小于-2，那么翻转的数字中至少一个为0，且第一个翻转的0必须在第一个负数前缀和处及其以前，因此枚举第一个翻转的0即可；否则翻转的两个数必须都是0，同样地，第一个0必须在第一个负数及其之前，而第二个0必须在第一个小于-2的位置及其之前，可利用前缀统计0的个数加速查询，时间复杂度O(n)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),pre[]=new int[n+1],min=0;
String s=sc.next();
for(int i=1;i<=n;i++){
pre[i]=pre[i-1]+(s.charAt(i-1)-'0')*2-1;
min=Math.min(min,pre[i]);
}
if(min==0){
//全部前缀和非负，可以任选
System.out.println((long)n*(n-1)/2);
}
else if(min<-4){
//翻转两次0都无法使得最小值非负
System.out.println(0);
}
else if(min>=-2){
//此时只需要在第一个负数的前边翻转一个0，枚举第一个翻转的0，后一个位置可任选，或者前边的1任选
long ans=0;
int idx=0,pre1[]=new int[n+1],idx1=0,idx2=0;
for(int i=1;i<=n;i++){
pre1[i]=pre1[i-1]+s.charAt(i-1)-'0';
}
while(pre[idx]>=0){
idx++;
}
for(int i=1;i<=idx;i++){
if(s.charAt(i-1)=='0'){
ans+=n-i+pre1[i];
}
}
System.out.println(ans);
}
else{
//必须翻转的是两个0，第一个0的位置必须是第一个负数以及之前，而第二个0的位置必须是第一个小于-3的位置之前
long ans=0;
int pre0[]=new int[n+1],idx1=0,idx2=0;
for(int i=1;i<=n;i++){
pre0[i]=pre0[i-1]+1-(s.charAt(i-1)-'0');
}
while(pre[idx1]>=0){
idx1++;
}
while(pre[idx2]>=-2){
idx2++;
}
for(int i=1;i<=idx1;i++){
if(s.charAt(i-1)=='0'){
ans+=pre0[idx2]-pre0[i];
}
}
System.out.println(ans);
}
}
}
对每个白色联通快进行边界检查，当且仅当连通块置于一个空位置邻点的时候，这个空位子才会对这个新的围合区域产生贡献，时间复杂度O(n^2)
import java.util.*;
public class Main{
static int move[][]={{0,1},{0,-1},{1,0},{-1,0}};
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),sum[][]=new int[n][n],ans=0;
String s[]=new String[n];
for(int i=0;i<n;i++){
s[i]=sc.next();
}
boolean has[][]=new boolean[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(s[i].charAt(j)=='*'&&!has[i][j]){
List<int[]> list=new ArrayList<>();
list.add(new int[]{i,j});
has[i][j]=true;
for(int p=0;p<list.size();p++){
int a[]=list.get(p);
for(int mo[]:move){
int x=a[0]+mo[0],y=a[1]+mo[1];
if(x>=0&&x<n&&y>=0&&y<n&&s[x].charAt(y)=='*'&&!has[x][y]){
has[x][y]=true;
list.add(new int[]{x,y});
}
}
}
Set<Integer> set=new HashSet<>();
for(int a[]:list){
for(int mo[]:move){
int x=a[0]+mo[0],y=a[1]+mo[1];
if(x>=0&&x<n&&y>=0&&y<n&&s[x].charAt(y)=='.'){
set.add(x*n+y);
}
}
}
if(set.size()==1){
for(int a:set){
sum[a/n][a%n]+=list.size();
ans=Math.max(ans,sum[a/n][a%n]);
}
}
}
}
}
System.out.println(ans);
}
}
其实没懂咋证明，看着视频题解照猫画虎，时间复杂度O(Tn)
import java.util.*;
import java.io.*;
public class Main{
public static void main(String args[]) throws IOException{
BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
for(int i=Integer.parseInt(bf.readLine());i!=0;i--){
StringTokenizer st=new StringTokenizer(bf.readLine());
int n=Integer.parseInt(st.nextToken());
long k=Long.parseLong(st.nextToken());
if(k<n||k>(long)n*n||k%2!=n%2){
bw.write("-1\n");
}
else{
int diff[]=new int[n],cur=n*2;
k=(long)n*n-k;
for(int j=0;j<n;j++){
diff[j]=j*2+1;
int d=(int)Math.min(diff[j]-1,k);
diff[j]-=d;
k-=d;
}
boolean has[]=new boolean[n*2+5];
for(int j=n-1;j>=0;j--){
while(has[cur]){
cur--;
}
bw.write(cur-diff[j]+" "+cur+"\n");
has[cur]=has[cur-diff[j]]=true;
}
}
}
bw.flush();
}
}
按照普通转移方程计算即可，初始状态概率为1，时间复杂度O(x^2+log(mod))
import java.util.*;
public class Main{
static int mod=(int)1e9+7;
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int x=sc.nextInt();
long p1=sc.nextInt()*pow(sc.nextInt(),mod-2)%mod,p2=sc.nextInt()*pow(sc.nextInt(),mod-2)%mod,p3=pow((p1+p2-p1*p2)%mod,mod-2),p[][]=new long[x+1][x+1],ans=0;
p[0][0]=1;
for(int i=0;i<=x;i++){
for(int j=0;j<=x;j++){
//p(i,j)=p1p2*p(i-1,j-1)+p1(1-p2)*p(i-1,j)+(1-p1)p2*p(i,j-1)+(1-p1)(1-p2)*p(i,j)
if(i+j==0){
continue;
}
if(i>0&&j!=x){
p[i][j]+=p1*(1-p2)%mod*p[i-1][j];
}
if(j>0&&i!=x){
p[i][j]+=p2*(1-p1)%mod*p[i][j-1];
}
if(i>0&&j>0){
p[i][j]+=p1*p2%mod*p[i-1][j-1];
}
p[i][j]=p[i][j]%mod*p3%mod;
}
}
for(int i=0;i<x;i++){
ans=(ans+p[i][x])%mod;
}
System.out.println((ans%mod+mod)%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;
}
}
京公网安备 11010502036488号