Java题解，代码已去除冗余~~~
按照题意利用哈希表模拟即可，时间复杂度O(q)
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int q=sc.nextInt();
Map<String,Set<String>> map1=new HashMap<>(),map2=new HashMap<>();
for(int i=0;i<q;i++){
int op=sc.nextInt();
if(op==1){
String x=sc.next(),y=sc.next();
map1.putIfAbsent(x,new HashSet<>());
map1.get(x).add(y);
map2.putIfAbsent(y,new HashSet<>());
map2.get(y).add(x);
}
else if(op==2){
System.out.println(map1.getOrDefault(sc.next(),new HashSet<>()).size());
}
else if(op==3){
String x=sc.next(),y=sc.next();
System.out.println(map2.getOrDefault(y,new HashSet<>()).contains(x)?1:0);
}
else{
System.out.println(map1.size());
}
}
}
}
类似于BST的序列化，任意一种排列对应的是唯一的二叉树，因此直接求得n的阶乘即可，而对于大于p的数字结果都是0，时间复杂度O(p+len(n))
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
String n=sc.next();
int p=sc.nextInt();
System.out.println(n.length()<7?fac(Integer.parseInt(n),p):0);
}
static long fac(int a,int p){
return a==0?1%p:fac(a-1,p)*a%p;
}
}
操作的实质就是先作一个位移，再进行一个异或后取后k位，而异或具有对称性，因此可以反推，时间复杂度O(nmk)
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(),k=sc.nextInt(),a[]=new int[n];
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
}
for(int i=0;i<m;i++){
String y=sc.next();
int ans[]=new int[k],idx=k-1;
for(int j=y.length()-1;j>=0;j--){
ans[y.length()-1-j]=y.charAt(j)-'0';
}
for(int p=a.length-1;p>=0;p--){
if(a[p]>0){
for(int j=0;j<k;j++){
ans[j]^=j>=a[p]?ans[j-a[p]]:0;
}
}
else{
for(int j=k-1;j>=0;j--){
ans[j]^=j-a[p]<k?ans[j-a[p]]:0;
}
}
}
while(idx>0&&ans[idx]==0){
idx--;
}
StringBuilder sb=new StringBuilder();
for(int j=idx;j>=0;j--){
sb.append(ans[j]);
}
System.out.println(sb);
}
}
}
图只能是一个树或者基环树，那么移动的情况要么是，图上的点两两配对儿，要么是环上的点内部配对儿，，环上的支链两两配对儿；对于非环节点，度数为1的节点来说，它只能跟唯一的相邻的点集合配对儿，因此只需由叶节点向里地把度数为1的点拆下来，同时统计没法继续配对儿的点数目，时间复杂度O(Tn)
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(),m=sc.nextInt(),degree[]=new int[n+5],ans=0;
List<Integer> path[]=new List[n+5];
for(int j=1;j<=n;j++){
path[j]=new ArrayList<>();
}
for(int j=0;j<m;j++){
int u=sc.nextInt(),v=sc.nextInt();
path[u].add(v);
path[v].add(u);
degree[u]++;
degree[v]++;
}
Queue<Integer> q=new LinkedList<>();
for(int j=1;j<=n;j++){
if(degree[j]==1){
q.add(j);
}
}
while(!q.isEmpty()){
int a=q.poll();
if(degree[a]==-1){
continue;
}
for(int b:path[a]){
if(degree[b]>0){
degree[b]=degree[a]=-1;
for(int c:path[b]){
if(c!=a&°ree[c]!=-1){
degree[c]--;
if(degree[c]==0){
degree[c]=-1;
ans++;
}
else if(degree[c]==1){
q.add(c);
}
}
}
break;
}
}
}
System.out.println(n==1?1:ans==0?"Yes":ans);
}
}
}
延迟标记的动态开点线段树，每个节点记录数据总和，最大的斐波那契数列的下标，以及延迟标记（其实点），时间复杂度O(C1+nlogC2)，其中C1==2e5，C2==1e11为保证开点的最大区间
import java.util.*;
public class Main{
static long mod=998244353,fab[]=new long[200005];
static{
fab[1]=1;
for(int i=2;i<=200000;i++){
fab[i]=(fab[i-1]+fab[i-2])%mod;
}
for(int i=1;i<=200000;i++){
fab[i]=(fab[i]+fab[i-1])%mod;
}
}
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
long l=(long)5e10,r=l-1;
SegTree st=new SegTree(0,(long)1e11);
for(int i=0;i<n;i++){
int op=sc.nextInt();
if(op==1){
int x=sc.nextInt();
r+=x;
insert(st,r-x+1,r,r-x+1);
}
else if(op==2){
int x=sc.nextInt();
l-=x;
insert(st,l,l+x-1,l);
}
else if(op==3){
long x=sc.nextLong();
r-=x;
erase(st,r+1,r+x);
}
else if(op==4){
long x=sc.nextLong(),y=sc.nextLong();
int idx=findMax(st,l+x-1,l+y-1);
System.out.println(idx==0?0:(fab[idx]-fab[idx-1]+mod)%mod);
}
else{
long x=sc.nextLong(),y=sc.nextLong();
System.out.println(findSum(st,l+x-1,l+y-1));
}
}
}
static long findSum(SegTree st,long a,long b){
long l=st.l,r=st.r;
if(l==a&&r==b){
return st.sum;
}
clear(st);
long mid=(l+r)>>1;
return b<=mid?findSum(st.left,a,b):a>mid?findSum(st.right,a,b):(findSum(st.left,a,mid)+findSum(st.right,mid+1,b))%mod;
}
static int findMax(SegTree st,long a,long b){
long l=st.l,r=st.r;
if(l==a&&r==b){
return st.max;
}
clear(st);
long mid=(l+r)>>1;
return b<=mid?findMax(st.left,a,b):a>mid?findMax(st.right,a,b):Math.max(findMax(st.left,a,mid),findMax(st.right,mid+1,b));
}
static void erase(SegTree st,long a,long b){
long l=st.l,r=st.r;
if(l==a&&r==b){
st.start=-1;
st.sum=st.max=0;
}
else{
clear(st);
long mid=(l+r)>>1;
if(b<=mid){
erase(st.left,a,b);
}
else if(a>mid){
erase(st.right,a,b);
}
else{
erase(st.left,a,mid);
erase(st.right,mid+1,b);
}
pushup(st);
}
}
static void insert(SegTree st,long a,long b,long s){
//在[a,b]区间内更新为左端点在s的数列
long l=st.l,r=st.r;
if(l==a&&b==r){
update(st,s);
}
else{
create(st);
clear(st);
long mid=(l+r)>>1;
if(b<=mid){
insert(st.left,a,b,s);
}
else if(a>mid){
insert(st.right,a,b,s);
}
else{
insert(st.left,a,mid,s);
insert(st.right,mid+1,b,s);
}
pushup(st);
}
}
static void clear(SegTree st){
long l=st.l,r=st.r;
if(l<r&&st.start!=-1){
create(st);
update(st.left,st.start);
update(st.right,st.start);
}
st.start=-1;
}
static void update(SegTree st,long s){
long l=st.l,r=st.r;
st.start=s;
st.max=(int)(r-s+1);
st.sum=(fab[(int)(r-s+1)]-fab[(int)(l-s)]+mod)%mod;
}
static void create(SegTree st){
long l=st.l,r=st.r,mid=(l+r)>>1;
if(st.left==null){
st.left=new SegTree(l,mid);
}
if(st.right==null){
st.right=new SegTree(mid+1,r);
}
}
static void pushup(SegTree st){
st.sum=(st.left.sum+st.right.sum)%mod;
st.max=Math.max(st.left.max,st.right.max);
}
}
class SegTree{
long l,r,sum=0,start=-1;
int max=0;
SegTree left,right;
SegTree(long l,long r){
this.l=l;
this.r=r;
}
}
思路看官解吧，我是照猫画虎的，时间复杂度O(能过)
import java.util.*;
import java.math.*;
public class Main{
static BigInteger zero=new BigInteger("0"),one=BigInteger.ONE,mod=new BigInteger("998244353"),two=new BigInteger("2");
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++){
BigInteger n=new BigInteger(sc.next()),a=new BigInteger(sc.next()),b=new BigInteger(sc.next());
if(a.equals(one)&&b.equals(one)){
System.out.println(1);
}
else if(a.equals(one)||b.equals(one)||a.equals(n)&&b.equals(n)){
System.out.println(2);
}
else if(a.add(b).compareTo(n)<=0){
System.out.println(4);
}
else{
BigInteger ans=BigInteger.ONE;
for(BigInteger bi:new BigInteger[]{BigInteger.ONE,a.add(b).subtract(n),a.add(b).subtract(n).add(one),a,a.add(one),n}){
ans=lcm(ans,find(n,a,b,bi));
}
System.out.println(ans.multiply(two).mod(mod));
}
}
}
static BigInteger find(BigInteger n,BigInteger a,BigInteger b,BigInteger start){
if(start.compareTo(one)<0||start.compareTo(n)>0){
return zero;
}
BigInteger inc=n.multiply(two).subtract(a).subtract(b),cur=new BigInteger(start.toString()),ans=BigInteger.ZERO,s=a.add(b).subtract(n);
boolean inInterVal=start.compareTo(s)<=0;
do{
if(cur.compareTo(s)<=0){
BigInteger step=s.subtract(cur).divide(inc).add(one);
if(inInterVal&&start.compareTo(cur)>=0&&cur.subtract(start).mod(inc).equals(zero)){
step=start.subtract(cur).divide(inc);
}
ans=ans.add(step);
cur=cur.add(step.multiply(inc));
}
else if(cur.compareTo(a)<=0){
ans=ans.add(one);
cur=a.add(one).subtract(cur);
}
else{
ans=ans.add(one);
cur=n.multiply(two).subtract(b).add(one).subtract(cur);
}
}
while(!cur.equals(start));
return ans;
}
static BigInteger lcm(BigInteger a,BigInteger b){
return a.equals(zero)?b:b.equals(zero)?a:a.multiply(b).divide(a.gcd(b));
}
}
京公网安备 11010502036488号