[Atcoder Regular Contest 063] Tutorial
Link:
C:
将每种颜色的连续出现称为一段,寻找总段数即可
#include <bits/stdc++.h> using namespace std;
int cnt=,len;
char s[];
int main()
{
scanf("%s",s+);len=strlen(s+);
for(int i=;i<=len;i++)
if(s[i]!=s[i-]) cnt++;
printf("%d",cnt-);
return ;
}
Problem C
D:
可以发现对于每一个点的最优解$res_i$为:
$max(w_j)-w_i(j>i)$
找到最小的$res_i$的个数即可
#include <bits/stdc++.h> using namespace std;
int n,d,dat[],mx,res,cnt;
int main()
{
scanf("%d%d",&n,&d);
for(int i=;i<=n;i++) scanf("%d",&dat[i]);
mx=dat[n];
for(int i=n-;i>=;i--)
{
if(mx>dat[i])
{
if(mx-dat[i]>res) res=mx-dat[i],cnt=;
else if(mx-dat[i]==res) cnt++;
}
mx=max(mx,dat[i]);
}
printf("%d",cnt);
return ;
}
Problem D
E:
仔细考虑一下会发现并没有那么难……
首先每个已知权值的节点的权值和其深度的异或值要相同,保证其奇偶性合法
(一定要先剔除奇偶性不合法的情况,否则后面可能会判为合法)
接下来就只要考虑权值大小是否合法即可
可以$dfs$出每个节点的可能区间,将$l[i]>r[i]$视为不合法
构造答案时只要保证该节点的值在区间内即可(感性证明)
#include <bits/stdc++.h> using namespace std;
const int MAXN=1e5+,INF=<<;
struct edge{int nxt,to;}e[MAXN<<];
int n,k,x,y,fst,head[MAXN],dep[MAXN],l[MAXN],r[MAXN],val[MAXN],tot=; void add(int from,int to)
{e[++tot].nxt=head[from];e[tot].to=to;head[from]=tot;} void cal_dep(int x,int anc)
{
for(int i=head[x];i;i=e[i].nxt)
{
if(e[i].to==anc) continue;
dep[e[i].to]=dep[x]+;cal_dep(e[i].to,x);
}
} void dfs(int x,int anc)
{
if(val[x]!=INF) l[x]=r[x]=val[x];
else l[x]=-INF,r[x]=INF; for(int i=head[x];i;i=e[i].nxt)
{
if(e[i].to==anc) continue;
dfs(e[i].to,x);
l[x]=max(l[x],l[e[i].to]-);
r[x]=min(r[x],r[e[i].to]+);
} if(l[x]>r[x]){puts("No");exit();}
} void print(int x,int anc)
{
if(val[x]==INF)
{
if(val[anc]+>=l[x]&&val[anc]+<=r[x]) val[x]=val[anc]+;
else val[x]=val[anc]-;
}
for(int i=head[x];i;i=e[i].nxt)
if(e[i].to!=anc) print(e[i].to,x);
} int main()
{
scanf("%d",&n);
for(int i=;i<n;i++)
scanf("%d%d",&x,&y),add(x,y),add(y,x);
cal_dep(,);
for(int i=;i<=n;i++) val[i]=INF; scanf("%d",&k);
for(int i=;i<=k;i++)
{
scanf("%d%d",&x,&y);val[x]=y;
if(i==) fst=(dep[x]&)^(val[x]&);
else if((dep[x]&)^(val[x]&)!=fst) return !puts("No");
} dfs(,);
if(val[]==INF) val[]=l[];
puts("Yes");print(,);
for(int i=;i<=n;i++) printf("%d\n",val[i]); return ;
}
Problem E
F:
原来模拟赛中出现过的一道题目,现在终于刚掉了
当时听杨主力讲题时一脸懵逼,完全不知所云
首先要看出一个结论:矩形一定经过中线$\frac{n}{2}$或$\frac{m}{2}$
(原因在于矩形周长的下限为$2*(max(n,m)+1)$,而$\frac{n}{2}*\frac{m}{2}$的矩形的周长明显是比其小的)
而这两种情况可以只考虑一种,剩下一种将每个点的$x,y$坐标翻转即可
接下来都以$\frac{m}{2}$为中线来举例
要使周长最大,明显要使子矩阵为一个极大子矩阵
可以先将所有节点按$x$坐标递增的方式来排序
确定了两个点就确定了该矩阵的左右边界,上下边界的最大值由中间的点来限定
假如选定了$i$为右边界,那么当前的最值为$max\{ X_i-X_j+len_j\}$
其中$len_j$为以点$j$为左边界时由$i....j$的点限定出的最长竖直距离
于是可以上下各维护一个单调栈,保证栈中的纵坐标向两侧递增
每次新增一个节点时按照单调栈中的信息在退栈时将$len_j$更新即可
为了在$log(n)$的时间内完成上述操作,可以使用线段树维护$len_j-X_j$的最大值
退栈时将那条线段整体平移到当前线段的位置,也就是将所有点的$len$都减去与当前线段的差值,为区间减操作
最后将最大值,即$seg[1]$加上$X_i$就是以$i$为右边界时的最大值
#include <bits/stdc++.h> using namespace std;
typedef pair<int,int> P;
#define X first
#define Y second
#define mid (l+r)/2
#define lc k<<1,l,mid
#define rc k<<1|1,mid+1,r
const int MAXN=3e5+;
int n,m,k,seg[MAXN<<],tag[MAXN<<],res=;
P dat[MAXN],st1[MAXN],st2[MAXN]; void pushdown(int k)
{
if(!tag[k]) return;
tag[k<<]+=tag[k];seg[k<<]+=tag[k];
tag[k<<|]+=tag[k];seg[k<<|]+=tag[k];
tag[k]=;
} void Update(int a,int b,int x,int k,int l,int r)
{
if(a<=l&&r<=b){tag[k]+=x;seg[k]+=x;return;}
pushdown(k);
if(a<=mid) Update(a,b,x,lc);
if(b>mid) Update(a,b,x,rc);
seg[k]=max(seg[k<<],seg[k<<|]);
} void solve()
{
memset(seg,,sizeof(seg));
memset(tag,,sizeof(tag));
sort(dat+,dat+k+); int t1=,t2=;
for(int i=;i<=k;i++)
{
if(dat[i].Y<=m/)
{
int lst=i-;
while(t1&&st1[t1].Y<dat[i].Y)
Update(st1[t1].X,lst,st1[t1].Y-dat[i].Y,,,k),
lst=st1[t1--].X-;
if(lst!=i-) st1[++t1]=P(lst+,dat[i].Y);
}
else
{
int lst=i-;
while(t2&&st2[t2].Y>dat[i].Y)
Update(st2[t2].X,lst,dat[i].Y-st2[t2].Y,,,k),
lst=st2[t2--].X-;
if(lst!=i-) st2[++t2]=P(lst+,dat[i].Y);
} st1[++t1]=P(i,);st2[++t2]=P(i,m);
Update(i,i,m-dat[i].X,,,k);
res=max(res,seg[]+dat[i+].X);
}
} int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=k;i++)
scanf("%d%d",&dat[i].X,&dat[i].Y);
dat[++k]=P(,);dat[++k]=P(n,m);
solve();
for(int i=;i<=k;i++)
swap(dat[i].X,dat[i].Y);
swap(n,m);
solve(); printf("%d",res*);
return ;
}
Problem F
最新文章
- SQL Server 查询分解
- Effective objective-c 2.0阅读笔记
- CSS实现自定义手型气泡提示
- nsstring字符串重组
- 【优化AC】建立联系
- Eclipse设置UTF-8
- Vim经常使用技巧总结1
- Android Material Design带UI变化
- TensorFlow 基础知识
- ansible小计
- #2019-2020-4 《Java 程序设计》第八周总结
- js获取select选中的内容
- 不是说记住rm -rf的教训就够了
- 三大平衡树(Treap + Splay + SBT)总结+模板[转]
- 2018.11.07 bzoj1965: [Ahoi2005]SHUFFLE 洗牌(快速幂+exgcd)
- netbeans启动后一会崩溃处理
- C++ 第七课 标准 C I/O
- listen的参数backlog的意义
- Header的Request部分和Response部分
- 51Nod:1086背包问题 V2