逐渐智障
B.so easy
并查集，可能会卡掉map,建议使用unordered_map。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
using namespace std;
const int N = 1e6+100;
const int mod = 1e9+7;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
inline bool read(ll &num) {
char in;bool IsN=false;
in=getchar();
if(in==EOF) return false;
while(in!='-'&&(in<'0'||in>'9')) in=getchar();
if(in=='-'){ IsN=true;num=0;}
else num=in-'0';
while(in=getchar(),in>='0'&&in<='9'){
num*=10,num+=in-'0';
}
if(IsN) num=-num;
return true;
}
unordered_map<int,int> par;
int find(int x){
if(par[x]==0){
par[x]=x;
return x;
}
return x==par[x]?x:par[x]=find(par[x]);
}
int main(){
int n,q;
scanf("%d %d",&n,&q);
int op,x;
while(q--){
scanf("%d %d",&op,&x);
if(op==1){
par[find(x)]=x+1;
}else{
if(find(x)>n) puts("-1");
else printf("%d\n",find(x));
}
}
return 0;
}
C.Buy Watermelon
签到，大于2的偶数都可以被拆分成两个偶数和。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#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+100;
const int mod = 1e9+7;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fep(i,a,b) for(int i=(a);i>=(b);i--)
inline bool read(ll &num) {
char in;bool IsN=false;
in=getchar();
if(in==EOF) return false;
while(in!='-'&&(in<'0'||in>'9')) in=getchar();
if(in=='-'){ IsN=true;num=0;}
else num=in-'0';
while(in=getchar(),in>='0'&&in<='9'){
num*=10,num+=in-'0';
}
if(IsN) num=-num;
return true;
}
int main(){
// freopen("1.in", "r", stdin);
ll t,n;
read(n);
if(n>2&&(n%2==0)){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
return 0;
}
D. Carneginon
KMP,懒得写了（狗头）。。
E. XKC’s basketball team
对于每个$i$查找最右的大于等于$a_i+m$的位置。线段树维护区间最大值优先查右子树即可。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
using namespace std;
const int N = 2e6+100;
const int mod = 1e9+7;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll llINF = 0x3f3f3f3f3f3f3f3f;
inline bool read(ll &num) {
char in;bool IsN=false;
in=getchar();
if(in==EOF) return false;
while(in!='-'&&(in<'0'||in>'9')) in=getchar();
if(in=='-'){ IsN=true;num=0;}
else num=in-'0';
while(in=getchar(),in>='0'&&in<='9'){
num*=10,num+=in-'0';
}
if(IsN) num=-num;
return true;
}
int mxx[N],a[N];
int n,m;
void pushup(int rt){
mxx[rt]=max(mxx[rt<<1],mxx[rt<<1|1]);
}
void buildtree(int rt,int l,int r){
mxx[rt]=0;
if(l==r){
mxx[rt]=a[l];return ;
}
int mid=(l+r)>>1;
buildtree(rt<<1,l,mid);
buildtree(rt<<1|1,mid+1,r);
pushup(rt);
}
int query(int rt,int l,int r,int x){
// cout<<rt<<' '<<l<<' '<<r<<' '<<mxx[rt]<<endl;
if(l==r){
if(mxx[rt]>=x){
return l;
}
else return -1;
}
int mid=(l+r)>>1;
if(mxx[rt<<1|1]>=x){
return query(rt<<1|1,mid+1,r,x);//先查右面
}else{
return query(rt<<1,l,mid,x);
}
}
int main(){
//freopen("1.in", "r", stdin);
scanf("%d %d",&n,&m);
rep(i,1,n) scanf("%d",&a[i]);
buildtree(1,1,n);
vector<int> ans;
rep(i,1,n){
int id=query(1,1,n,a[i]+m);
if(id<=i) ans.push_back(-1);
else{
ans.push_back(id-i-1);
}
}
printf("%d",ans[0]);
rep(i,1,(int)ans.size()-1) printf(" %d",ans[i]);
puts("");
return 0;
}
I. query
对于$[1,n]$，枚举它们所有的倍数，总对数也就大概只有$O(n \cdot log(n))$，因此转化为一个正方形，每次查询$[l,l]$到$[r,r]$之间点的个数即可。接下来直接离线然后用树状数组维护前缀和即可。
1 |
|
J. Random Access Iterator
首先预处理出每个点所能到达的最大深度和子节点的数量，令$dp[x]$表示能到达叶子节点的概率，当从$u$向$v$转移时，只有$v$能到达的的最大深度等于树的深度时才能转移。对于叶子节点：$dp[x]=1$,向上转移即可。
1 |
|
M. Longest subsequence
在$S$中找到最长的子序列使其字典序大于$T$,输出长度即可。
假设子序列为$T’$，如果$T’>T$,则$T’$一定存在某个位置$p$使得$T’[1…p-1]=T[1…p]$，而$T’[p]>T[p]$,枚举$p$，利用序列自动机计枚举$T’[p]$并快速求的位置，计算答案即可。
1 |
|