C~G Java题解，代码已去除冗余，并保留简要注释~~~
所得数列必须是奇偶相间的形式，利用排列计算即可，时间复杂度O(n)
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 n=sc.nextInt();
System.out.println(n%2==0?fac(n/2)*fac(n/2)*2%mod:fac(n/2)*fac(n-n/2)%mod);
}
static long fac(int a){
return a==0?1:fac(a-1)*a%mod;
}
}
最后的答案显然为偶数长度，那么如果n的长度为奇数，只需要一次重复11和00即可；假如n本身就是偶数，需要先贪心放置数位为最小的“相邻数位一样”（找到n中第一对儿不同的数字对儿，之后的只需要交替填充00和11即可），最后就是验证是否保证相邻数对儿不同，只需要找到从左到右第一个相同的相邻数对儿，从这个位置依次向前尝试是否可以增加到9以内的数字并且跟前边不重复，若找到则后边交替填充00和11后返回，否则数位数需要增加2并交替填充11和00后返回，时间复杂度O(len(x))
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
for(int a:find(sc.next())){
System.out.print(a);
}
}
static int[] find(String s){
int n=s.length(),ans[]=new int[n];
if(n%2==1){
ans=new int[n+1];
for(int i=1;i<=n;i+=2){
ans[i]=ans[i-1]=i>>1&1^1;
}
}
else{
for(int i=1;i<n;i+=2){
int a=s.charAt(i-1)-'0',b=s.charAt(i)-'0';
if(a==b){
ans[i]=ans[i-1]=a;
}
else{
for(int j=0;j<10;j++){
if(j*11>=a*10+b){
ans[i]=ans[i-1]=j;
break;
}
}
for(int j=i+2,k=0;j<n;j+=2,k^=1){
ans[j]=ans[j-1]=k;
}
break;
}
}
for(int i=2;i<n;i+=2){
if(ans[i]==ans[i-1]){
boolean found=false;
for(int j=i+1;j>=0;j-=2){
ans[j]++;
ans[j-1]++;
if(j>2&&ans[j]==ans[j-2]){
ans[j]++;
ans[j-1]++;
}
if(ans[j]<10){
found=true;
for(int p=j+2,k=0;p<n;p+=2,k^=1){
ans[p]=ans[p-1]=k;
}
break;
}
}
if(!found){
ans=new int[n+2];
for(int j=1;j<n+2;j+=2){
ans[j]=ans[j-1]=j>>1&1^1;
}
}
}
}
}
return ans;
}
}
对于可分为一组的两个人a和b，要么只出a，要么只出b，要一起上，同一组分情况最多出现一种，因此本题可用分组背包解答，时间复杂度O(m+4nC)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt(),c=sc.nextInt(),m=sc.nextInt(),a[]=new int[n],b[]=new int[n];
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
b[i]=sc.nextInt();
}
List<long[][]> list=new ArrayList<>();
for(int i=0;i<m;i++){
int u=sc.nextInt()-1,v=sc.nextInt()-1,w=sc.nextInt();
list.add(new long[][]{{a[u],b[u],1},{a[v],b[v],1},{a[u]+a[v],(long)b[v]+b[u]+w,2}});
a[v]=a[u]=0;
}
for(int i=0;i<n;i++){
if(a[i]!=0){
list.add(new long[][]{{a[i],b[i],1}});
}
}
long max[][]=new long[c+1][5],ans=0;
for(long arr[][]:list){
for(int i=c;i>=0;i--){
for(int j=0;j<=4;j++){
for(long w[]:arr){
if(i>=w[0]&&j>=w[2]){
max[i][j]=Math.max(max[i][j],w[1]+max[i-(int)w[0]][j-(int)w[2]]);
}
}
ans=Math.max(ans,max[i][j]);
}
}
}
System.out.println(ans);
}
}
先判断树是否可以双生：对于树中的节点，想要成为配对儿中的较靠近根节点的那个节点，它的子树中必须有且仅有一个子树的节点数为奇数，依次递归判断；；而对于双生树的形态，一共有且仅有两种，预处理出从根节点到每个节点路径的两组前缀和：不修改任何节点的修改次数前缀和，以及路径全部改为红色后的修改次数的前缀和，具体实现需要借助求取最近公共祖先，时间复杂度O((n+q)C)，其中C==17
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));
StringTokenizer st=new StringTokenizer(bf.readLine());
int n=Integer.parseInt(st.nextToken()),q=Integer.parseInt(st.nextToken()),ans[]=new int[q],countSub[]=new int[n+5],par[][]=new int[n+5][17],level[]=new int[n+5],change[][]=new int[n+5][2],pre[][]=new int[n+5][2],tol[]=new int[2];
//change表示的是在各种模式下，所需要修改的次数的前缀；pre是在链全涂0色模式下所需要修改的次数前缀；tol表示两种模式下所需要修改的原始总次数
String s=bf.readLine();
List<Integer> path[]=new List[n+5];
for(int i=1;i<=n;i++){
path[i]=new ArrayList<>();
}
for(int i=0;i<n-1;i++){
st=new StringTokenizer(bf.readLine());
int u=Integer.parseInt(st.nextToken()),v=Integer.parseInt(st.nextToken());
path[u].add(v);
path[v].add(u);
}
find(1,0,countSub,par,level,path);
if(!check(1,0,0,countSub,change,pre,tol,path,s)){
Arrays.fill(ans,-1);
}
else{
for(int i=1;i<17;i++){
for(int j=1;j<=n;j++){
par[j][i]=par[par[j][i-1]][i-1];
}
}
for(int i=0;i<q;i++){
st=new StringTokenizer(bf.readLine());
int x=Integer.parseInt(st.nextToken()),y=Integer.parseInt(st.nextToken()),lca=lca(x,y,level,par);
ans[i]=n;
for(int j=0;j<2;j++){
ans[i]=Math.min(ans[i],tol[j]-(change[x][j]+change[y][j]-change[lca][j]-change[par[lca][0]][j])+(pre[x][j]+pre[y][j]-pre[lca][j]-pre[par[lca][0]][j]));
}
}
}
for(int a:ans){
bw.write(a+"\n");
}
bw.flush();
}
static boolean check(int k,int p,int cur,int countSub[],int change[][],int pre[][],int tol[],List<Integer> path[],String s){
//cur表示的是在“0模式”下的预设的点k应该有的颜色
//返回是否可以完成分组，并给节点预先分好组，做好前缀和，做好总和预处理
int countOdd=0,next=-1;
for(int a:path[k]){
if(a!=p&&countSub[a]==1){
countOdd++;
next=a;
}
}
if(countOdd!=1){
return false;
}
//下边处理k和next的事情：0模式下k和next都应该为cur，为了表述清楚，先处理k，再处理next
int color=s.charAt(k-1)=='R'?0:1,nextColor=s.charAt(next-1)=='R'?0:1;
change[k]=change[p].clone();
pre[k]=pre[p].clone();
change[k][color^cur^1]++;
pre[k][cur^1]++;
change[next]=change[k].clone();
pre[next]=pre[k].clone();
change[next][nextColor^cur^1]++;
pre[next][cur^1]++;
tol[color^cur^1]++;
tol[nextColor^cur^1]++;
//下面递归处理子树的事情：
for(int a:path[k]){
if(a!=p&&a!=next&&!check(a,k,cur^1,countSub,change,pre,tol,path,s)){
return false;
}
}
for(int a:path[next]){
if(a!=k&&!check(a,next,cur^1,countSub,change,pre,tol,path,s)){
return false;
}
}
return true;
}
static void find(int k,int p,int countSub[],int par[][],int level[],List<Integer> path[]){
countSub[k]=1;
for(int a:path[k]){
if(a!=p){
level[a]=1+level[k];
par[a][0]=k;
find(a,k,countSub,par,level,path);
countSub[k]^=countSub[a];
}
}
}
static int lca(int a,int b,int level[],int par[][]){
if(level[a]<level[b]){
return lca(b,a,level,par);
}
for(int i=16;i>=0;i--){
if(level[a]-level[b]>=1<<i){
a=par[a][i];
}
}
for(int i=16;i>=0;i--){
if(par[a][i]!=par[b][i]){
a=par[a][i];
b=par[b][i];
}
}
return a==b?a:par[a][0];
}
}
京公网安备 11010502036488号