模板

Java大数模板

二、Java之输入输出处理
由于ACM竞赛题目的输入数据和输出数据一般有多组(不定),并且格式多种多样,所以,如何处理题目的输入输出是对大家的一项最基本的要求。这也是困扰初学者的一大问题。

  1. 输入:

格式1:Scanner sc = new Scanner (new BufferedInputStream(System.in));

格式2:Scanner sc = new Scanner (System.in);

在读入数据量大的情况下,格式1的速度会快些。

读一个整数: int n = sc.nextInt(); 相当于 scanf(“%d”, &n); 或 cin >> n;

读一个字符串:String s = sc.next(); 相当于 scanf(“%s”, s); 或 cin >> s;

读一个浮点数:double t = sc.nextDouble(); 相当于 scanf(“%lf”, &t); 或 cin >> t;

读一整行: String s = sc.nextLine(); 相当于 gets(s); 或 cin.getline(…);

判断是否有下一个输入可以用sc.hasNext()或sc.hasNextInt()或sc.hasNextDouble()或sc.hasNextLine()

1
2
3
4
5
6
import java.util.Scanner;
import java.math.*;
Scanner cin = new Scanner (new BufferedInputStream(System.in));
while(cin.haxNextInt){
//操作
}

大数使用例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
int a = in.nextInt();
BigInteger b = in.nextBigInteger();
BigDecimal c = in.nextBigDecimal();
/*
BigDecimal:
构造方法:
BigDecimal(BigInteger val)
BigDecimal(BigInteger unscaledVal, int scale)
BigDecimal(BigInteger unscaledVal, int scale, MathContext mc)
BigDecimal(BigInteger val, MathContext mc)
BigDecimal(char[] in)
BigDecimal(char[] in, int offset, int len)
BigDecimal(char[] in, int offset, int len, MathContext mc)
BigDecimal(char[] in, MathContext mc)
BigDecimal(double val)
BigDecimal(double val, MathContext mc)
BigDecimal(int val)
BigDecimal(int val, MathContext mc)
BigDecimal(long val)
BigDecimal(long val, MathContext mc)
BigDecimal(String val)
BigDecimal(String val, MathContext mc)
成员方法:
BigDecimal abs()
BigDecimal abs(MathContext mc)
BigDecimal add(BigDecimal augend)
BigDecimal add(BigDecimal augend, MathContext mc)
byte byteValueExact()
int compareTo(BigDecimal val)
BigDecimal divide(BigDecimal divisor)
BigDecimal divide(BigDecimal divisor, int roundingMode)
BigDecimal divide(BigDecimal divisor, int scale, int roundingMode)
BigDecimal divide(BigDecimal divisor, int scale, RoundingMode roundingMode)
BigDecimal divide(BigDecimal divisor, MathContext mc)
BigDecimal divide(BigDecimal divisor, RoundingMode roundingMode)
BigDecimal[] divideAndRemainder(BigDecimal divisor)
BigDecimal[] divideAndRemainder(BigDecimal divisor, MathContext mc)
BigDecimal divideToIntegralValue(BigDecimal divisor)
BigDecimal divideToIntegralValue(BigDecimal divisor, MathContext mc)
double doubleValue()
boolean equals(Object x)
float floatValue()
int hashCode()
int intValue()
int intValueExact()
long longValue()
long longValueExact()
BigDecimal max(BigDecimal val)
BigDecimal min(BigDecimal val)
BigDecimal movePointLeft(int n)
BigDecimal movePointRight(int n)
BigDecimal multiply(BigDecimal multiplicand)
BigDecimal multiply(BigDecimal multiplicand, MathContext mc)
BigDecimal negate()
BigDecimal negate(MathContext mc)
BigDecimal plus()
BigDecimal plus(MathContext mc)
BigDecimal pow(int n)
BigDecimal pow(int n, MathContext mc)
int precision()
BigDecimal remainder(BigDecimal divisor)
BigDecimal remainder(BigDecimal divisor, MathContext mc)
BigDecimal round(MathContext mc)
int scale()
BigDecimal scaleByPowerOfTen(int n)
BigDecimal setScale(int newScale)
Returns a BigDecimal whose scale is the specified value, and whose value is numerically equal to this BigDecimal's.
BigDecimal setScale(int newScale, int roundingMode)
BigDecimal setScale(int newScale, RoundingMode roundingMode)
Returns a BigDecimal whose scale is the specified value, and whose unscaled value is determined by multiplying or dividing this BigDecimal's unscaled value by the appropriate power of ten to maintain its overall value.
short shortValueExact()
int signum()
Returns the signum function of this BigDecimal. (1,0,-1)
BigDecimal stripTrailingZeros()
Returns a BigDecimal which is numerically equal to this one but with any trailing zeros removed from the representation.
BigDecimal subtract(BigDecimal subtrahend)
BigDecimal subtract(BigDecimal subtrahend, MathContext mc)
BigInteger toBigInteger()
BigInteger toBigIntegerExact()
String toEngineeringString()
String toPlainString()
String toString()
BigDecimal ulp()
Returns the size of an ulp, a unit in the last place, of this BigDecimal.
BigInteger unscaledValue()
static BigDecimal valueOf(double val)
static BigDecimal valueOf(long val)
static BigDecimal valueOf(long unscaledVal, int scale)
*/
BigDecimal test = new BigDecimal("1.234567");
test = test.setScale(3, RoundingMode.HALF_UP);
System.out.println(test);
test = test.setScale(7, RoundingMode.HALF_EVEN);
System.out.println(test);
test = test.divide(new BigDecimal("3"), MathContext.UNLIMITED); // 默认也是UNLIMITED精度,无限小数会报错
System.out.println(test);

/*
BigInteger:
构造方法:
BigInteger(byte[] val)
BigInteger(int signum, byte[] magnitude)
BigInteger(int bitLength, int certainty, Random rnd)
Constructs a randomly generated positive BigInteger that is probably prime, with the specified bitLength.
BigInteger(int numBits, Random rnd)
Constructs a randomly generated BigInteger, uniformly distributed over the range 0 to (2numBits - 1), inclusive.
BigInteger(String val)
BigInteger(String val, int radix)
成员方法:
BigInteger abs()
BigInteger add(BigInteger val)
BigInteger and(BigInteger val)
BigInteger andNot(BigInteger val)
Returns a BigInteger whose value is (this & ~val).
int bitCount()
Returns the number of bits in the two's complement representation of this BigInteger that differ from its sign bit.
int bitLength()
Returns the number of bits in the minimal two's-complement representation of this BigInteger, excluding a sign bit.
BigInteger clearBit(int n)
Returns a BigInteger whose value is equivalent to this BigInteger with the designated bit cleared.
int compareTo(BigInteger val)
BigInteger divide(BigInteger val)
BigInteger[] divideAndRemainder(BigInteger val)
double doubleValue()
boolean equals(Object x)
BigInteger flipBit(int n)
Returns a BigInteger whose value is equivalent to this BigInteger with the designated bit flipped.
float floatValue()
BigInteger gcd(BigInteger val)
Returns a BigInteger whose value is the greatest common divisor of abs(this) and abs(val).
int getLowestSetBit()
Returns the index of the rightmost (lowest-order) one bit in this BigInteger (the number of zero bits to the right of the rightmost one bit).
int hashCode()
int intValue()
boolean isProbablePrime(int certainty)
Returns true if this BigInteger is probably prime, false if it's definitely composite.
long longValue()
BigInteger max(BigInteger val)
BigInteger min(BigInteger val)
BigInteger mod(BigInteger m)
BigInteger modInverse(BigInteger m)
Returns a BigInteger whose value is (this^-1 mod m).
BigInteger modPow(BigInteger exponent, BigInteger m)
BigInteger multiply(BigInteger val)
BigInteger negate()
BigInteger nextProbablePrime()
Returns the first integer greater than this BigInteger that is probably prime.
BigInteger not()
BigInteger or(BigInteger val)
BigInteger pow(int exponent)
static BigInteger probablePrime(int bitLength, Random rnd)
Returns a positive BigInteger that is probably prime, with the specified bitLength.
BigInteger remainder(BigInteger val)
Returns a BigInteger whose value is (this % val).
BigInteger setBit(int n)
Returns a BigInteger whose value is equivalent to this BigInteger with the designated bit set.
BigInteger shiftLeft(int n)
Returns a BigInteger whose value is (this << n).
BigInteger shiftRight(int n)
Returns a BigInteger whose value is (this >> n).
int signum()
BigInteger subtract(BigInteger val)
boolean testBit(int n)
Returns true if and only if the designated bit is set.
byte[] toByteArray()
String toString()
String toString(int radix)
static BigInteger valueOf(long val)
BigInteger xor(BigInteger val)
*/

MyPair[] pairs = new MyPair[1000];
Arrays.sort(pairs);
Arrays.binarySearch(pairs, 1, 4, new MyPair());
/*
二分查找
如果元素在数组中,则值为0~n-1,否则值为-1~-(n+1),表示第一个比它大的值的位置,下标从1开始
*/
List<MyPair> pairList = new ArrayList<>();
pairList.add(new MyPair());
//pairList.sort();
pairList.sort(new Cmp());
Collections.shuffle(pairList);
Collections.swap(pairList, 1, 3);
Collections.sort(pairList);
}
}

class MyPair implements Comparable {
int x, y;

@Override
public int compareTo(Object o) {
MyPair b = (MyPair)o;
if(x!=b.x) return x<b.x?-1:1;
else if(y!=b.y) return y<b.y?-1:1;
return 0;
}
}

class Cmp implements Comparator<MyPair> {
@Override
public int compare(MyPair o1, MyPair o2) {
if(o1.x!=o2.x) return o1.x<o2.x?-1:1;
else if(o1.y!=o2.y) return o1.y<o2.y?-1:1;
return 0;
}
}

关于树的

树链剖分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
void swap(int &a,int &b){
int temp = a;
a = b;
b = temp;
}
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e4+10;
int size[maxn],dep[maxn],top[maxn],fa[maxn],id[maxn],son[maxn];
int head[maxn],w[maxn];
int n,cnt,totw,m;
struct edge{
int next,to;
}G[maxn<<1];
int find(int x){ return x==fa[x]?x:find(fa[x]);}
void addedge(int u,int v){
G[cnt].next = head[u];
G[cnt].to = v;
head[u] = cnt++;
}
void dfs1(int u,int f){
size[u] = 1;
for(int i=head[u];~i;i=G[i].next){
int v = G[i].to;
if(v==f) continue;
dep[v] = dep[u]+1;
fa[v] = u;
dfs1(v,u);
if(size[v] > size[son[u]]) son[u] = v;
size[u]+=size[v];
}
}
void dfs2(int u,int topu){
top[u] = topu;
id[u] = ++totw;
if(son[u]) dfs2(son[u],top[u]);
for(int i=head[u];~i;i=G[i].next){
int v = G[i].to;
if(v==fa[u] || v==son[u]) continue;
dfs2(v,v);
}
}
int data[maxn<<2],lazy[maxn<<2];
void pushdown(int rt){
if(lazy[rt]!=0){
data[rt<<1] += lazy[rt];
data[rt<<1|1] += lazy[rt];
lazy[rt<<1] += lazy[rt];
lazy[rt<<1|1] += lazy[rt];
lazy[rt] = 0;
}
}
void build(int l,int r,int rt){
lazy[rt] = 0;
if(l==r){
data[rt] = w[l];
return;
}
int mid = l+r>>1;
build(lson); build(rson);
}
int query(int pos,int l,int r,int rt){
if(l==r && l==pos) return data[rt];
int mid = l+r>>1;
pushdown(rt);
if(pos<=mid) return query(pos,lson);
else return query(pos,rson);
}
void update(int val,int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
lazy[rt] += val;
data[rt] += val;
return;
}
pushdown(rt);
int mid = l+r>>1;
if(L<=mid) update(val,L,R,lson);
if(mid<R) update(val,L,R,rson);
}
void change(int u,int v,int val){
int t1=top[u],t2=top[v];
while(t1!=t2){
if(dep[t1]<dep[t2]){
swap(t1,t2);
swap(u,v);
}
update(val,id[t1],id[u],1,totw,1);
u = fa[t1];
t1 = top[u];
}
if(dep[u]>dep[v]) swap(u,v);
update(val,id[u],id[v],1,totw,1);
}
int val[maxn];
int p;
char op[20];
void init(){
cnt = totw = 0;
memset(head,-1,sizeof(head));
dep[1] = fa[1] = size[0] = 0;
memset(son,0,sizeof(son));
}
int main(){
#ifdef LOCAL
freopen("4.in","r",stdin);
#endif
while(~scanf("%d%d%d",&n,&m,&p)){
init();
rep(i,1,n+1) scanf("%d",val+i);
rep(i,0,m){
int u,v;scanf("%d%d",&u,&v);
addedge(u,v); addedge(v,u);
}
dfs1(1,0);
dfs2(1,1);
rep(i,1,n+1) w[id[i]] = val[i];
build(1,totw,1);
while(p--){
scanf("%s",op);
if(op[0]=='Q'){
int x;scanf("%d",&x);
printf("%d\n",query(id[x],1,totw,1));
}else{
int u,v,val;scanf("%d%d%d",&u,&v,&val);
if(op[0]=='D') val = -val;
change(u,v,val);
}
}
}

return 0;
}

线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head ----------------------------------------
const int maxn = 1e6+20;
int T,n,m;
struct sgt{
int maxlen[maxn<<2];
int ll[maxn<<2],rr[maxn<<2],mm[maxn<<2];
int lazy[maxn<<2];
void build(int l,int r,int rt){
lazy[rt] = -1;
if(l==r){
ll[rt] = rr[rt] = 0;
mm[rt] = 1;
return;
}
int mid = l+r>>1;
build(lson); build(rson);
}
void init(){
lazy[1] = 1;
}
void pushup(int l,int r,int rt){
if(lazy[rt]>=0){
maxlen[rt] = ll[rt] = rr[rt] = mm[rt] = (lazy[rt]?(r-l+1):0);
}else{
int lc = rt<<1,rc = rt<<1|1,mid = l+r>>1;
ll[rt] = ll[lc];
if(ll[lc]==(mid-l+1)) ll[rt] += ll[rc];
mm[rt] = rr[lc] + ll[rc];
rr[rt] = rr[rc];
if(rr[rc] == r-mid) rr[rt] += rr[lc];
maxlen[rt] = max(maxlen[lc],max(maxlen[rc],mm[rt]));
}
}
void pushdown(int rt){
if(lazy[rt]>=0){
int lc=rt<<1,rc=rt<<1|1;
lazy[lc] = lazy[rc] = lazy[rt];
lazy[rt] = -1;
}
}
int query(int val,int l,int r,int rt){
pushup(l,r,rt);
//cout<<l<<' '<<r<<' '<<" ";
int lc = rt<<1,rc = rt<<1|1,mid = l+r>>1;
if(val>maxlen[rt]) return 0;
if(ll[rt] >= val) return l;
pushdown(rt);
pushup(rson);
int temp = query(val,lson);
if(temp) return temp;
if(mm[rt] >= val) return mid-rr[lc]+1;
return query(val,rson);
}
void update(int val,int L,int R,int l,int r,int rt){
if(L<=l && r<=R){
lazy[rt] = val;
pushup(l,r,rt);
return;
}
pushdown(rt);
int mid = l+r>>1;
if(L<=mid) update(val,L,R,lson);
else pushup(lson);
if(mid<R) update(val,L,R,rson);
else pushup(rson);
pushup(l,r,rt);
}
}all,ns;
char op[20];
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
scanf("%d",&T);
rep(test_case,1,T+1){
printf("Case %d:\n",test_case);
scanf("%d%d",&n,&m);
//all.build(1,n,1); ns.build(1,n,1);
all.init(); ns.init();
while(m--){
scanf("%s",op);
if(op[0]=='D'){
int x;scanf("%d",&x);
int ans = all.query(x,1,n,1);
if(ans){
all.update(0,ans,ans+x-1,1,n,1);
printf("%d,let's fly\n",ans);
}else{
puts("fly with yourself");
}
}else if(op[0]=='N'){
int x;scanf("%d",&x);
int ans = all.query(x,1,n,1);
if(!ans) ans = ns.query(x,1,n,1);
if(ans){
all.update(0,ans,ans+x-1,1,n,1);
ns.update(0,ans,ans+x-1,1,n,1);
printf("%d,don't put my gezi\n",ans);
}else{
puts("wait for me");
}
}else{
int x,y;scanf("%d%d",&x,&y);
all.update(1,x,y,1,n,1);
ns.update(1,x,y,1,n,1);
puts("I am the hope of chinese chengxuyuan!!");
}
}
}

return 0;
}

LCA 最近公共父节点 用来求两点之间距离的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 10;
int cnt,n,m;
int head[maxn];
int fa[maxn];
struct node{
int next,to;
}G[maxn<<1];
void addedge(int u,int v){
G[cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt++;
}
struct ST{
int tot;
int first[maxn<<1],R[maxn<<1],order[maxn<<1],dp[maxn<<1][20],dis[maxn];
void init(int root){
tot = 0;
dfs(root,0,-1);
ST_init(tot);
}
void ST_init(int n){
rep(i,1,n+1) dp[i][0] = i;
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
int a = dp[i][j-1],b = dp[i+(1<<(j-1))][j-1];
dp[i][j] = R[a]<R[b]?a:b;
}
}
}
int LCA(int u,int v){
int x = first[u],y = first[v];
if(x>y) swap(x,y);
int res = RMQ(x,y);
return order[res];
}
int RMQ(int l,int r){
int k = 0;
while((1<<(k+1))<=r-l+1) k++;
int a = dp[l][k],b = dp[r-(1<<k)+1][k];
return R[a]<R[b]?a:b;
}
void dfs(int u,int deep,int f){
R[++tot] = deep;
dis[u] = deep;
order[tot] = u;
first[u] = tot;
for(int i=head[u];~i;i=G[i].next){
int v = G[i].to;
if(v==f) continue;
dfs(v,deep+1,u);
order[++tot] = u;
R[tot] = deep;
}
}
}st;
int find(int x){
return x==fa[x]?x:fa[x] = find(fa[x]);
}
int ind[maxn];
char s[60];
void init(){
cnt = 0;
memset(head,-1,sizeof(head));
memset(ind,0,sizeof(ind));
}
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
init();
map<string,int> mp;
int tot = 0;
rep(i,0,n-1){
int u,v;
scanf("%s",s);
if(mp[s]==0) mp[s] = ++tot,u = tot;
else u = mp[s];
scanf("%s",s);
if(mp[s]==0) mp[s] = ++tot,v = tot;
else v = mp[s];
addedge(v,u); ind[u]++;
}
int root = 0;
rep(i,1,n+1) if(ind[i]==0){
root = i;
break;
}
st.init(root);
rep(i,0,m){
int u,v,ans;
scanf("%s",s); u = mp[s];
scanf("%s",s); v = mp[s];
int rt = st.LCA(u,v);
int x = st.dis[u] - st.dis[rt];
int y = st.dis[v] - st.dis[rt];
if(rt==u) ans = 1;
else if(rt == v) ans = x;
else ans = x+1;
if(u==v) ans = 0;
printf("%d\n",ans);
}
}
return 0;
}