https://www.nowcoder.com/acm/contest/40#question
三道简答题，三道难题。
难题看着补吧qwq，虽然一般都不会补，面试肯定不会这么难吧qwq
吐槽：1 依旧没抽中。
2 剩下三道题看都没看。
A
珂朵莉的假动态仙人掌
题目描述
珂朵莉想每天都给威廉送礼物，于是她准备了n个自己的本子
她想送最多的天数，使得每天至少送一个本子，但是相邻两天送的本子个数不能相同
珂朵莉最多送几天礼物呢
输入描述:
第一行一个整数n
输出描述:
第一行输出一个整数，表示答案
示例1
输入
4
输出
3
说明
第一天送1个本子
第二天送2个本子
第三天送1个本子
备注:
对于100%的数据，有1 <= n <= 1000000000
规律 1 2 1 2 最少。于是就mod3呗
#include <bits/stdc++.h>
using namespace std;
int main()
{ int m;
scanf("%d",&m);
int ans=m/3;
ans*=2;
if(m%3) ans++;//当 为2时也加1，21 21 2这样
printf("%d\n",ans);
return 0;
}
D：珂朵莉的假toptree
题目描述
珂朵莉想求123456789101112131415…的第n项
输入描述:
第一行一个整数n
输出描述:
第一行输出一个整数，表示答案
示例1
输入
3
输出
3
示例2
输入
11
输出
0
说明
1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4…
第3个是3
第11个是0
备注:
对于100%的数据，有1 <= n <= 1000
思路：水题，暴力。
#include <bits/stdc++.h>
using namespace std;
int a[1004];
int main()
{ for(int i=1;i<=1000;i++)
a[i]=i;
string rel;
rel+='0';
for(int i=1;i<=1000;i++){
int as=i;
string sss;
while(as){
sss+=((as%10)+'0');
as/=10;
}
reverse(sss.begin(),sss.end());
//cout<<sss<<endl;
rel+=sss;
}
int m;
while(~scanf("%d",&m)){
cout<<rel[m]<<endl;
}
return 0;
}B 珂朵莉的值域连续段
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld
题目描述
珂朵莉给你一个有根树，求有多少个子树满足其内部节点编号在值域上连续
一些数在值域上连续的意思即其在值域上构成一个连续的区间
输入描述:
第一行有一个整数n，表示树的节点数。
接下来n–1行，每行两个整数x,y,表示存在一条从x到y的有向边。
输入保证是一棵有根树。
输出描述:
输出一个数表示答案
示例1
输入
5
2 3
2 1
2 4
4 5
输出
5
说明
节点1子树中编号为1，值域连续
节点3子树中编号为3，值域连续
节点5子树中编号为5，值域连续
节点4子树中编号为4,5，值域连续
节点2子树中编号为1,2,3,4,5，值域连续
备注:
对于100%的数据，有n <=100000
思路： 用dfs序维护子树，用线段树维护最大最小。
当子树满足条件时，肯定 max-min=size（子树的大小）
用dfs序处理子树是直觉啊qwq，不过貌似暴力就行。改的以前的板子。（其实应该手敲比较好）
空间开小了wa了一发，还有就是这是个有向树，根不一定是1。
#include <bits/stdc++.h>
using namespace std;
/* dfs裸题。
这个玩意 果然用树状数组不行。。好菜。
*/
const int maxn=8e5+200;
int cnt,sum[maxn*4],lazy[maxn*4],ide[maxn*4];
int maxx[maxn*4];
int minn[maxn*4];
int a[maxn];
struct Node{
int to,next;
}node[maxn*2];
int head[maxn];
int len;
int sta[maxn];
int end2[maxn];
int tim;
bool vis[maxn];
void add(int a,int b){
node[len].to=b;
node[len].next=head[a];
head[a]=len++;
}
void dfs(int u){
sta[u]=++tim;
ide[tim]=u;
vis[u]=true;
for(int i=head[u];i!=-1;i=node[i].next){
int to=node[i].to;
if(!vis[to])
dfs(to);
}
end2[u]=tim;
}
void init(){
memset(head,-1,sizeof(head));
len=0;
tim=0;
}
void pushdown(int id,int l,int r)
{
if(lazy[id])
{
int mid=(l+r)/2;
sum[id*2]=(mid-l+1)-sum[id*2];
lazy[id*2]^=1;
sum[id*2+1]=(r-mid-1+1)-sum[id*2+1];
lazy[id*2+1]^=1;
lazy[id]=0;
}
}
void build(int id,int l,int r)
{
if(l==r)
{
maxx[id]=ide[l];
minn[id]=ide[l];
sum[id]=1;
return;
}
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
maxx[id]=max(maxx[id*2],maxx[id*2+1]);
minn[id]=min(minn[id*2],minn[id*2+1]);
sum[id]=sum[id*2]+sum[id*2+1];
}
int query_max(int id,int l,int r,int L,int R)
{
if(l>=L && r<=R)
return maxx[id];
int res=0,mid=(l+r)/2;
if(L<=mid)
res=max(res,query_max(id*2,l,mid,L,R));
if(R>mid)
res=max(res,query_max(id*2+1,mid+1,r,L,R));
maxx[id]=max(maxx[id*2],maxx[id*2+1]);
//minn[id]=min(minn[id*2],minn[id*2+1]);
//sum[id]=sum[id*2]+sum[id*2+1];
return res;
}
int query_min(int id,int l,int r,int L,int R)
{
if(l>=L && r<=R)
return minn[id];
int res=1e9+7,mid=(l+r)/2;
if(L<=mid)
res=min(res,query_min(id*2,l,mid,L,R));
if(R>mid)
res=min(res,query_min(id*2+1,mid+1,r,L,R));
minn[id]=min(minn[id*2],minn[id*2+1]);
//minn[id]=min(minn[id*2],minn[id*2+1]);
//sum[id]=sum[id*2]+sum[id*2+1];
return res;
}
int query(int id,int l,int r,int L,int R)
{
if(l>=L && r<=R)
return sum[id];
//pushdown(id,l,r);
int res=0,mid=(l+r)/2;
if(L<=mid)
res+=query(id*2,l,mid,L,R);
if(R>mid)
res+=query(id*2+1,mid+1,r,L,R);
sum[id]=sum[id*2]+sum[id*2+1];
return res;
}
bool kk[maxn];
int main()
{ int m,n;
char st[50];
while(~scanf("%d",&m)){
init();
memset(kk,false,sizeof(kk));
memset(vis,false,sizeof(vis));
int a2,b2;
for(int i=2;i<=m;i++){
scanf("%d%d",&a2,&b2);
//add(b2,a2);
add(a2,b2);
kk[b2]=true;
}
for(int i=1;i<=m;i++)
if(!kk[i])
{dfs(i);
//cout<<i<<endl;
break;}
/*for(int i=1;i<=m;i++){
cout<<sta[i]<<" "<<end2[i]<<endl;
}
cout<<endl;
for(int i=1;i<=m;i++){
cout<<ide[i]<<" ";
}
cout<<endl;*/
build(1,1,m);
int ans=0;
for(int i=1;i<=m;i++){
int aaa=query_max(1,1,m,sta[i],end2[i]);
int bbb=query_min(1,1,m,sta[i],end2[i]);
int ccc=query(1,1,m,sta[i],end2[i]);
if((ccc-1)==(aaa-bbb))
ans++;
//cout<<aaa<<" "<<bbb<<" "<<sta[i]<<" "<<end2[i]<<endl;
}
printf("%d\n",ans);
/*scanf("%d",&n);
int tt;
for(int i=0;i<n;i++){
scanf(" %s",&st);
if(strcmp(st,"get")==0){
scanf("%d",&tt);
printf("%d\n",query(1,1,m,sta[tt],end2[tt]));
}
else{
scanf("%d",&tt);
update(1,1,m,sta[tt],end2[tt]);
}
}*/
}
return 0;
}