1001 Magician
线段树。根据奇偶性分成4个区间。维护子列和最大值。
想法很简单。但是并不好写。
首先初始化的时候对于不存在的点要写成-INF。
然后pushup的时候。对于每个区间要考虑四个情况。
例如sum01。
他可能是左子树的sum01右子树的sum01。
或者左子树的sum01+右子树的sum01。
或者左子树的sum00+右子树的sum11。
最后注意query函数的写法。
如果在递归的时候就讨论奇偶性。
下层的每个区间都要被重复调用。而且是层数的指数级。
于是参考学习了一种直接把子区间合并成一个区间类型返回的方法。
合成目标区间后再讨论奇偶性。
【其实pushup和query可以写好看些。好不容易调对。懒得改了。】
# include <iostream>
# include <cstdio>
# include <algorithm>
using namespace std;
typedef long long LL;
# define maxn
# define INF (LL)
LL a[maxn]; struct node
{
int l,r;
LL sum00,sum01,sum10,sum11;
}tree[*maxn]; void pushup(int i)
{
tree[i].sum00=tree[i].sum01=tree[i].sum10=tree[i].sum11=-INF;
tree[i].sum00=max(tree[i].sum00,tree[*i].sum00+tree[*i+].sum10);
tree[i].sum00=max(tree[i].sum00,tree[*i].sum01+tree[*i+].sum00);
tree[i].sum00=max(tree[i].sum00,tree[*i].sum00);
tree[i].sum00=max(tree[i].sum00,tree[*i+].sum00);
tree[i].sum01=max(tree[i].sum01,tree[*i].sum00+tree[*i+].sum11);
tree[i].sum01=max(tree[i].sum01,tree[*i].sum01+tree[*i+].sum01);
tree[i].sum01=max(tree[i].sum01,tree[*i].sum01);
tree[i].sum01=max(tree[i].sum01,tree[*i+].sum01);
tree[i].sum10=max(tree[i].sum10,tree[*i].sum10+tree[*i+].sum10);
tree[i].sum10=max(tree[i].sum10,tree[*i].sum11+tree[*i+].sum00);
tree[i].sum10=max(tree[i].sum10,tree[*i].sum10);
tree[i].sum10=max(tree[i].sum10,tree[*i+].sum10);
tree[i].sum11=max(tree[i].sum11,tree[*i].sum10+tree[*i+].sum11);
tree[i].sum11=max(tree[i].sum11,tree[*i].sum11+tree[*i+].sum01);
tree[i].sum11=max(tree[i].sum11,tree[*i].sum11);
tree[i].sum11=max(tree[i].sum11,tree[*i+].sum11);
return;
} void buildtree(int i,int l,int r)
{
tree[i].l=l; tree[i].r=r;
if(l<r)
{
buildtree(*i,l,(l+r)/);
buildtree(*i+,(l+r)/+,r);
pushup(i);
}
else
{
if(l%)
{
tree[i].sum11=a[l];
tree[i].sum10=tree[i].sum01=tree[i].sum00=-INF;
}
else
{
tree[i].sum00=a[l];
tree[i].sum10=tree[i].sum01=tree[i].sum11=-INF;
}
}
return;
} void update(int i,int p,int v)
{
if(tree[i].l==tree[i].r)
{
if(p%) tree[i].sum11=v;
else tree[i].sum00=v;
}
else
{
if(p<=(tree[i].l+tree[i].r)/) update(*i,p,v);
else update(*i+,p,v);
pushup(i);
}
return;
} node query(int i,int l,int r)
{
if(tree[i].l>=l&&tree[i].r<=r) return tree[i];
if(r<=(tree[i].l+tree[i].r)/) return query(*i,l,r);
if(l>=(tree[i].l+tree[i].r)/+) return query(*i+,l,r);
node t,t1,t2;
t1=query(*i,l,r);
t2=query(*i+,l,r);
t.sum00=max(t1.sum00,t2.sum00);
t.sum00=max(t.sum00,t1.sum00+t2.sum10);
t.sum00=max(t.sum00,t1.sum01+t2.sum00);
t.sum01=max(t1.sum01,t2.sum01);
t.sum01=max(t.sum01,t1.sum00+t2.sum11);
t.sum01=max(t.sum01,t1.sum01+t2.sum01);
t.sum10=max(t1.sum10,t2.sum10);
t.sum10=max(t.sum10,t1.sum10+t2.sum10);
t.sum10=max(t.sum10,t1.sum11+t2.sum00);
t.sum11=max(t1.sum11,t2.sum11);
t.sum11=max(t.sum11,t1.sum10+t2.sum11);
t.sum11=max(t.sum11,t1.sum11+t2.sum01);
return t;
} int main(void)
{
int T; cin>>T;
while(T--)
{
int n,m; scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%I64d",a+i);
buildtree(,,n);
while(m--)
{
int type,x,y; scanf("%d%d%d",&type,&x,&y);
if(type) update(,x,y);
else
{
node tem=query(,x,y);
LL ans=-INF;
ans=max(ans,tem.sum00);
ans=max(ans,tem.sum01);
ans=max(ans,tem.sum10);
ans=max(ans,tem.sum11);
printf("%I64d\n",ans);
}
}
}
return ;
}
Aguin
1002 RGCDQ
先枚举1000000内所有质因数。
然后统计区间内每个数的质因数个数。
注意到最大只有7。
对于因子个数为1-7的数的个数处理一下前缀和。
对于每个询问。算区间内因子数分别为1-7的数的个数。
找到最大的gcd就是答案。
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <vector>
using namespace std;
# define maxn
bool tag[maxn]={,};
int prime[],cnt[maxn]={},presum[][maxn]={}; int main(void)
{
int t=;
for(int i=;i<maxn/;i++)
{
if(!tag[i]) prime[++t]=i;
for(int j=;j<=t&&i*prime[j]<maxn;j++)
{
tag[i*prime[j]]=;
if(i%prime[j]==) break;
}
}
for(int i=;i<=t;i++)
for(int j=;prime[i]*j<=maxn;j++)
cnt[prime[i]*j]++;
for(int i=;i<=maxn;i++)
for(int j=;j<=;j++)
{
presum[j][i]=presum[j][i-];
if(cnt[i]==j) presum[j][i]++;
}
int T; cin>>T;
while(T--)
{
int l,r; scanf("%d%d",&l,&r);
int mark[]={};
for(int i=;i<;i++) mark[i]=max(,presum[i][r]-presum[i][l-]);
if(mark[]>=) printf("7\n");
else if(mark[]>=) printf("6\n");
else if(mark[]>=) printf("5\n");
else if(mark[]>=) printf("4\n");
else if(mark[]>=||mark[]&&mark[]) printf("3\n");
else if(mark[]>=||mark[]&&mark[]||mark[]&&mark[]) printf("2\n");
else printf("1\n");
}
return ;
}
Aguin
1004 Painter
看成R和B的两张图。
统计R\斜边上与B/斜边上的连续染色段数即为答案。
# include <iostream>
# include <cstdio>
# include <cstring>
using namespace std;
# define CLR(x) memset(x,,sizeof(x))
char map[][];
int R[][],B[][]; int main(void)
{
int T; cin>>T;
while(T--)
{
CLR(map); CLR(R); CLR(B);
int n; scanf("%d",&n);
for(int i=;i<n;i++) scanf("%s",map[i]);
int len=strlen(map[]);
for(int i=;i<n;i++)
for(int j=;j<len;j++)
{
if(map[i][j]=='R') R[i][j]=;
else if(map[i][j]=='B') B[i][j]=;
else if(map[i][j]=='G') R[i][j]=B[i][j]=;
}
int ans=;
for(int i=-n;i<len;i++)
{
int flag=;
for(int j=;j<n&&i+j<len;j++)
{
if(i+j<) continue;
if(!flag&&R[j][i+j]) {ans++;flag=;}
if(!R[j][i+j]) flag=;
}
}
for(int i=;i<n+len-;i++)
{
int flag=;
for(int j=;j<len&&i-j>=;j++)
{
if(i-j>=n) continue;
if(!flag&&B[i-j][j]) {ans++;flag=;}
if(!B[i-j][j]) flag=;
}
}
printf("%d\n",ans);
}
return ;
}
Aguin
1005 Fan Li
1006 Beautiful Set
1007 Hope
1008 Solve this interesting problem
暴搜可行 证明不会。
l<0跳。l>r-l跳。r>现有答案跳。
搜[l,2*r-l]的时候注意死循环。
# include <iostream>
# include <cstdio>
# include <algorithm>
using namespace std;
typedef long long LL;
LL ans; void dfs(LL l,LL r)
{
if(l==)
{
if(ans==-) ans=r;
else ans=min(ans,r);
return;
}
if(l<) return;
if(ans!=-&&r>=ans) return;
if(r>*l) return;
if(r>l) dfs(l,*r-l);
dfs(*l-r-,r);
dfs(*l-r-,r);
dfs(l,*r-l+);
return;
} int main(void)
{
LL l,r;
while((scanf("%I64d%I64d",&l,&r))!=EOF)
{
ans=-;
dfs(l,r);
printf("%I64d\n",ans);
}
return ;
}
Aguin
1009 Boring Class
1010 Crazy Bobo
按官方题解。
把每条边变成从w大的点到w小的点的有像边。
以u为min的目标集就是能走到u的点的集合。
花了较长的时间思考这个问题。
换一种说法。
其实就是对于一个已经确定最小值u的目标集S。
点v在S中当且仅当v能通过递减的路到达u。
简要说明一下必要性和充分性。
随手画了个图。
任意取一条链。比方X。它必然有一个端点x1。
只要说明离x1最近的点x2小于x1。然后考虑去掉x1的图。归纳即可得到上述结论。
考虑S中比x1小的最大的点p的位置。
如果x2就是p。那么它比x1小。
如果x2不是p。那么由于x2离x1最近。无论p在什么位置。x2都在p-x1的链上。
根据S的定义。x2小于x1。
反之。如果所有链都是以递减的顺序通向u的。
那么考虑图中的最大点。其必然在一条链的端点。
比方仍取X链。x1是最大点。
最大点给集合带来的约束条件只有一条。
那就是最大点到次大点的路径上的所有点小于最大点。
但是所有点都小于最大点。所以这个条件必然成立。
也就是说原来的点属于S集等价于去掉最大点后的所有点属于S集合。
而去掉x1后的最大点可能是x2或者是其他链的端点。
只要不断从端点去掉最大点。归纳即可证明原来的所有点属于S集。
证明这个之后。树dp即可。
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <vector>
using namespace std;
# define maxn
int w[maxn],dp[maxn];
vector<int> edge[maxn]; struct V
{
int id,w;
} node[maxn]; bool cmp(V a,V b)
{
return a.w>b.w;
} int main(void)
{
int n;
while((scanf("%d",&n))!=EOF)
{
memset(edge,,sizeof(edge));
for(int i=;i<=n;i++)
{
scanf("%d",w+i);
node[i].id=i;
node[i].w=w[i];
}
for(int i=;i<n;i++)
{
int a,b; scanf("%d%d",&a,&b);
if(w[a]>w[b]) edge[b].push_back(a);
else if(w[a]<w[b]) edge[a].push_back(b);
}
sort(node+,node++n,cmp);
int ans=;
for(int i=;i<=n;i++)
{
int pos=node[i].id;
dp[pos]=;
for(int j=;j<edge[pos].size();j++)
dp[pos]+=dp[edge[pos][j]];
ans=max(dp[pos],ans);
}
printf("%d\n",ans);
}
return ;
}
Aguin
1011 Work
签到题。dfs一遍即可。
# include <iostream>
# include <cstdio>
# include <cstring>
# include <vector>
using namespace std;
int ind[],cnt[];
vector <int> edge[]; void dfs(int x)
{
cnt[x]=edge[x].size();
for(int i=;i<edge[x].size();i++)
{
dfs(edge[x][i]);
cnt[x]+=cnt[edge[x][i]];
}
return;
} int main(void)
{
int n,k;
while((scanf("%d%d",&n,&k))!=EOF)
{
memset(ind,,sizeof(ind));
memset(cnt,,sizeof(cnt));
for(int i=;i<=n;i++) edge[i].clear();
for(int i=;i<n;i++)
{
int u,v; scanf("%d%d",&u,&v);
edge[u].push_back(v);
ind[v]++;
}
for(int i=;i<=n;i++) if(!ind[i]) dfs(i);
int ans=;
for(int i=;i<=n;i++) if(cnt[i]==k) ans++;
printf("%d\n",ans);
}
return ;
}
Aguin