补题（2016-2017区域赛）
写在前面：
有些事很艰难，但必须去做。
比如模拟以前经历过的困境，尝试再次置身其中。
假如连过去的问题都无法解决，又凭什么让自己相信，当全新的问题出现时，能做得更好呢？
2016 ICPC Dalian, by Avalon
Board: http://board.acmicpc.info/icpc2016/dlmu_onsite.php
Solved Now: 10/11
【补题（2016-2017区域赛）】Problem B
http://acm.hdu.edu.cn/showproblem.php?pid=5972
Code:
#include
using namespace std;
int n;
bitset<1003>b[10];
char s[5000003];
int main(){
while(~scanf("%d",&n)){
for(int i=0;
i<10;
i++)b[i].reset();
for(int i=0;
ians;
for(int i=0;
i Key: BITSET Shift-And FastIO
Problem K
http://acm.hdu.edu.cn/showproblem.php?pid=5981
Code:
#include
using namespace std;
const int mod=100000073;
typedef long long ll;
ll dp[5000003];
ll sum[5000003];
int main(){
dp[1]=1;
dp[2]=2;
sum[1]=1;
sum[2]=3;
int l=1,r=1;
for(int i=3;
i<=5000000;
i++){
while(dp[l+1]+l+1<=i-1)l++;
dp[i]=i-l;
while(dp[r+1]<=dp[i]-1)r++;
sum[i]=sum[r]-sum[l-1]+sum[i-1]+mod;
while(sum[i]>mod)sum[i]-=mod;
}
int x,y;
while(~scanf("%d%d",&x,&y)){
x=y-x+1;
printf("%lld %lld\n",dp[x],(sum[x]-sum[x-1]+mod)%mod);
}
} Key: DP 2-Pointer
2016 ICPC Qingdao, by Avalon
No Official Board
Replay Board: https://vjudge.net/contest/142308#rank
Solved Now: 6/13
Problem K
http://acm.hdu.edu.cn/showproblem.php?pid=5992
Code:
#include
using namespace std;
typedef long long ll;
const ll INF=1ll<<60;
struct node{
int d[3],ma[3],mi[3],l,r,id;
}T[200003];
int rt,n,m,cmp_d;
inline bool cmp(node a,node b){
return a.d[cmp_d]>1;
cmp_d=D;
nth_element(T+l,T+mid,T+r+1,cmp);
T[mid].ma[0]=T[mid].mi[0]=T[mid].d[0];
T[mid].ma[1]=T[mid].mi[1]=T[mid].d[1];
T[mid].ma[2]=T[mid].mi[2]=T[mid].d[2];
if(l!=mid){
T[mid].l=build(l,mid-1,(D+1)%3);
up(mid,T[mid].l);
}
if(r!=mid){
T[mid].r=build(mid+1,r,(D+1)%3);
up(mid,T[mid].r);
}
return mid;
}ll dis;
int ans;
int x,y,c;
//估计范围
inline ll getdis(int p){
ll ret=0;
if(T[p].mi[2]>c)return INF;
if(x>T[p].ma[0])ret+=1ll*(x-T[p].ma[0])*(x-T[p].ma[0]);
if(xT[p].ma[1])ret+=1ll*(y-T[p].ma[1])*(y-T[p].ma[1]);
if(yc)d0=INF;
if(d0 Key: KD-Tree
Referred to:
https://blog.csdn.net/jiangshibiao/article/details/34144829
2016 ICPC China-Final, by Avalon
Board: http://codeforces.com/gym/101194/standings
Solved Now: 8/13
Problem G
http://codeforces.com/gym/101194/attachments/download/5009/20162017-acmicpc-china-final-en.pdf
Code:
#include
using namespace std;
int n,m,q;
int a[200003];
int f[200003];
int siz[200003];
int fa[200003][20];
int fal[200003][20];
int ms[200003];
int tot;
int tim[200003];
int mx;
setst[100003];
int tmp;
int ans[200003];
bool vis[200003];
struct edge{
int u,v,w;
}rec[200003];
bool cmp(edge a,edge b){
return a.wmx){
mx=p;
tmp=a[u];
}
else if(p==mx){
tmp=min(tmp,a[u]);
}
}
void del(int u){
if(a[u]==-1)return ;
int p=--tim[a[u]];
if(p==0){
st[p+1].erase(a[u]);
}
else {
st[p+1].erase(a[u]);
st[p].insert(a[u]);
}
if(st[mx].empty()){
--mx;
if(mx==0)tmp=0;
else tmp=*(st[mx].begin());
}
}
void addtree(int u){
add(u);
for(int i=head[u];
~i;
i=e[i].next){
int v=e[i].to;
addtree(v);
}
}
void deltree(int u){
del(u);
for(int i=head[u];
~i;
i=e[i].next){
int v=e[i].to;
deltree(v);
}
}
void dfs2(int u){
vis[u]=true;
if(ms[u]==-1){
add(u);
ans[u]=tmp;
return;
}
for(int i=head[u];
~i;
i=e[i].next){
int v=e[i].to;
if(v==ms[u])continue;
dfs2(v);
deltree(v);
}
dfs2(ms[u]);
for(int i=head[u];
~i;
i=e[i].next){
int v=e[i].to;
if(v==ms[u])continue;
addtree(v);
}
add(u);
ans[u]=tmp;
}
void init(){
memset(a,-1,sizeof(a));
memset(f,0,sizeof(f));
tot=n;
cnt=0;
memset(head,-1,sizeof(head));
memset(fa,0,sizeof(fa));
mx=0;
for(int i=1;
i<=n;
i++)st[i].clear();
}
void printtree(){
for(int i=1;
i<=tot;
i++)printf("%d%c",a[i],i==tot?'\n':' ');
for(int u=1;
u<=tot;
u++){
for(int i=head[u];
~i;
i=e[i].next){
int v=e[i].to;
cout<=1;
i--){
if(!vis[i]){
dfs(i);
}
}
memset(vis,false,sizeof(vis));
for(int i=tot;
i>=1;
i--){
if(!vis[i]){
dfs2(i);
deltree(i);
}
}
memset(vis,false,sizeof(vis));
for(int j=1;
j<=18;
j++){
for(int i=1;
i<=tot;
i++){
fa[i][j]=fa[fa[i][j-1]][j-1];
fal[i][j]=fal[fa[i][j-1]][j-1];
}
}
int q;
scanf("%d",&q);
printf("Case #%d:\n",tt);
int last=0;
while(q--){
int x,y;
scanf("%d%d",&x,&y);
x^=last;
y^=last;
for(int j=18;
j>=0;
j--){
if(fa[x][j]==0)continue;
if(fal[x][j]<=y)x=fa[x][j];
}
last=ans[x];
printf("%d\n",last);
}
}
} Key: MST 启发式合并 树上倍增
Problem F
http://codeforces.com/gym/101194/attachments/download/5009/20162017-acmicpc-china-final-en.pdf
Code:
#include
#include
#include
using namespace std;
const int maxn=305000;
char str[maxn];
int s[maxn];
int sa[maxn], t[maxn], t2[maxn], c[maxn], n;
int Rank[maxn], height[maxn];
int u[maxn], d[maxn];
void build_sa(int m, int n){
int i, *x=t, *y=t2;
for(i=0;
i=0;
i--)sa[--c[x[i]]]=i;
for(int k=1;
k<=n;
k<<=1){
int p=0;
for(i=n-k;
i=k)y[p++]=sa[i]-k;
for(i=0;
i=0;
i--)sa[--c[x[y[i]]]]=y[i];
swap(x, y);
p=1;
x[sa[0]]=0;
for(i=1;
i=n)break;
m=p;
}
}
void geth(int n){
int i, j, k=0;
for(i=0;
i=f1)continue;
l=i, r=i;
while(sa[r]=l;
j--)d[j]=min(height[j+1], d[j+1]);
for(int j=l;
j Key: SA
推荐阅读
- ACSL|ACSL 美国计算机科学联赛 2016-2017 R4 摩天大楼-Skyscraper 题解
- 「原宿」01门店区域卫生标准|「原宿」01门店区域卫生标准 -
- Qt实战|Qt+OpenCV联合开发（十四）--图像感兴趣区域（ROI）的提取
- java内存区域与内存溢出异常
- 深入理解Java虚拟机之Java内存区域与内存溢出异常
- 把可滚动区域中-某个子元素平滑滚动到可视区域正中间位置
- 如何使用 Amazon S3 多区域访问点提高多区域应用程序的性能速度和可用性
- CodeForces CF #499 Div.2 赛后补题
- LeetCode 363. 矩形区域不超过 K 的最大数值和（DP+set二分查找）
- Android DrawerLayout 空白区域点击穿透问题最简单解决方案