算法竞赛训练实录
目录
Codeforces Round 603
4题 rank1985
ABCD
都是很水的题。 cout << 000输出0，而cout<<"000"才输出000,因为这个WA6次要被笑(打)死。
E
判定括号序列合法性：每一个前缀和不小于0，同时最后一个前缀和等于0.线段树更新即可.新技能Get.
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int minz[maxn*4],tg[maxn*4],maxz[maxn*4],tg2[maxn*4];
char s[maxn];
inline int ls(int x){
return x<<1;
}
inline int rs(int x){
return x<<1|1;
}
void pushdown(int rt){
if(tg[rt]==0) return;
minz[ls(rt)]+=tg[rt];
tg[ls(rt)]+=tg[rt];
minz[rs(rt)]+=tg[rt];
tg[rs(rt)]+=tg[rt];
tg[rt]=0;
}
void pushdown2(int rt){
if(tg2[rt]==0) return;
maxz[ls(rt)]+=tg2[rt];
tg2[ls(rt)]+=tg2[rt];
maxz[rs(rt)]+=tg2[rt];
tg2[rs(rt)]+=tg2[rt];
tg2[rt]=0;
}
int upd(int il,int ir,int d,int rt,int l,int r){
if(il>r||ir<l) return minz[rt];
if(l>=il&&r<=ir){
minz[rt]+=d;
tg[rt]+=d;
return minz[rt];
}
pushdown(rt);
int mid=(l+r)>>1;
return minz[rt]=min(upd(il,ir,d,ls(rt),l,mid),upd(il,ir,d,rs(rt),mid+1,r));
}
int ask(int il,int ir,int rt,int l,int r){
if(il>r||ir<l) return 0x3f3f3f3f;
if(l>=il&&r<=ir) return minz[rt];
pushdown(rt);
int mid=(l+r)>>1;
return min(ask(il,ir,ls(rt),l,mid),ask(il,ir,rs(rt),mid+1,r));
}
int upd2(int il,int ir,int d,int rt,int l,int r){
if(il>r||ir<l) return maxz[rt];
if(l>=il&&r<=ir){
maxz[rt]+=d;
tg2[rt]+=d;
return maxz[rt];
}
pushdown2(rt);
int mid=(l+r)>>1;
return maxz[rt]=max(upd2(il,ir,d,ls(rt),l,mid),upd2(il,ir,d,rs(rt),mid+1,r));
}
int ask2(int il,int ir,int rt,int l,int r){
if(il>r||ir<l) return 0;
if(l>=il&&r<=ir) return maxz[rt];
pushdown2(rt);
int mid=(l+r)>>1;
return max(ask2(il,ir,ls(rt),l,mid),ask2(il,ir,rs(rt),mid+1,r));
}
int st[maxn];
int main(){
int n;
scanf("%d",&n);
scanf("%s",s+1);
int cur=1;
for(int i=1;i<=n;i++){
if(s[i]=='L') cur=max(1,cur-1);
else if(s[i]=='R') {
cur++;
}
else if(s[i]=='(') {
if(st[cur]==1) ;
else if(st[cur]==0){
st[cur]=1;
upd(cur,n,1,1,1,n);
upd2(cur,n,1,1,1,n);
}
else {
st[cur]=1;
upd(cur,n,2,1,1,n);
upd2(cur,n,2,1,1,n);
}
}
else if(s[i]==')'){
if(st[cur]==-1);
else if(st[cur]==0){
st[cur]=-1;
upd(cur,n,-1,1,1,n);
upd2(cur,n,-1,1,1,n);
}
else {
st[cur]=-1;
upd(cur,n,-2,1,1,n);
upd2(cur,n,-2,1,1,n);
}
}
else{
if(st[cur]==0) ;
else if(st[cur]==1){
st[cur]=0;
upd(cur,n,-1,1,1,n);
upd2(cur,n,-1,1,1,n);
}
else {
st[cur]=0;
upd(cur,n,1,1,1,n);
upd2(cur,n,1,1,1,n);
}
}
if(ask(1,n,1,1,n)>=0&&ask(n,n,1,1,n)==0){
printf("%d ", ask2(1,n,1,1,n));
}
else printf("-1 ");
}
return 0;
}
Codeforces Round 604
4题 rank 252
B
单调栈正反扫一遍，找每个数左边和右边第一个比它大的数的位置，位置之差等于它本身则成立，否则不成立。
似乎有更简单的做法。。懒得看了
#include <bits/stdc++.h>
using namespace std;
char ans[200005];
int a[200005];
int stk[200005],id[200005];
int l[200005],r[200005],pos[200005];
int main(){
int T;
cin >> T;
while(T--){
int n;
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i],pos[a[i]]=i;
int hd=0;
int i=1;
stk[0]=0x3f3f3f3f; id[0]=0;
while(i<=n){
while(stk[hd]<a[i]) hd--;
l[i]=id[hd]+1;
stk[++hd]=a[i];
id[hd]=i;
i++;
}
i=n; hd=0; id[0]=n+1;
while(i>0){
while(stk[hd]<a[i]) hd--;
r[i]=id[hd]-1;
stk[++hd]=a[i];
id[hd]=i;
i--;
}
for(i=1;i<=n;i++){
int j=pos[i];
if(r[j]-l[j]+1==i) ans[i]='1';
else ans[i]='0';
// cout << l[i] << " " << r[i] << endl;
}
for(i=1;i<=n;i++) cout << ans[i];
cout << endl;
}
return 0;
}
E
简单递推题，居然花了大段时间求无穷级数(居然还没求出来)。。。
设\(f(x)\)为到第\(x\)天的期望，那么显然有\(f(x)=p(i-1)*(f(x-1)+1)+(1-p(i-1))*(f(x)+f(x-1)+1)\)
解得 \(f(x)=(f(x-1)+1)/p(i-1)\) 求出\(f(n+1)\)即可
#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
int qpow(int x,int y){
int res=1,bas=x;
while(y){
if(y&1) res=1ll*res*bas%mod;
bas=1ll*bas*bas%mod;
y>>=1;
}
return res%mod;
}
int p[200005];
int dp[200005];
int main(){
int n;
cin >> n;
for(int i=1;i<=n;i++) cin >> p[i];
dp[1]=0;
for(int i=2;i<=n+1;i++){
dp[i]=(1ll*(dp[i-1]+1)*qpow(p[i-1],mod-2)%mod)*100%mod;
}
cout << dp[n+1];
return 0;
}
codeforces EDU round 78
3题rk891
A
memcmp函数返回值：相等为0，小于时小于0，大于时大于0
B
猜想：对于\(1\)到\(n\)的和\(\frac{n*(n+1)}{2}\),对于任意\(0\leq s \leq \frac{n*(n+1)}{2}\),总能找到\(1\)到\(n\)的子集，使其元素和为\(s\).
证明：\(s\)有两种情况：1）小于等于\(n\)，问题解决；2）大于\(n\)，则将\(s\)减去\(n\),此时\(s\)小于等于\(1\)到n-1的和，问题转化为1到n-1的情况；如此递归下去，得证。
C
枚举左边，判断右边，map维护
D
左端点排序，扫描线从左到右即可。
不会T的理由是并查集至多合并\(n\)次就一定可以break出来
#include <bits/stdc++.h>
using namespace std;
struct node{
int l,r;
}p[500005];
int id[1000005];
set<int> sr;
int fa[500005];
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
bool cmp(node x,node y){
return x.l<y.l;
}
bool join(int u,int v){
int x=find(u),y=find(v);
if(x==y) return false;
fa[x]=y;
return true;
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d%d",&p[i].l,&p[i].r);
fa[i]=i;
}
sort(p+1,p+n+1,cmp);
for(int i=1;i<=n;i++) id[p[i].l]=id[p[i].r]=i;
sr.insert(p[1].r);
bool ff=true;
for(int i=2;i<=n;i++){
set<int>::iterator it = sr.begin();
vector<int> tmp;
for(;it!=sr.end();it++){
if(p[i].l>*it) {
tmp.push_back(*it);
}
else break;
}
for(int j=0;j<int(tmp.size());j++) sr.erase(tmp[j]);
it=sr.begin();
bool f=true;
for(;it!=sr.end();it++){
if(p[i].r>*it){
f=join(i,id[*it]);
}
else break;
if(!f){
break;
}
}
if(!f){
ff=false;
break;
}
sr.insert(p[i].r);
}
int cnt=0;
for(int i=1;i<=n;i++) if(find(i)==i) cnt++;
if(cnt>1) ff=false;
if(ff) cout << "YES\n";
else cout << "NO\n";
return 0;
}
codeforces edu round 80
C
\(dp1[i][j]\)表示a数组第i位为j有多少种，\(dp2[i][j]\)表示b数组。。。这么简单怎么就想不出来
D
显然是二分答案。judge应该状态压缩，将每一行压缩为一个数，数位为1表示这一位大于等于x,否则为0，那么只要存在两行i,j其\(num(i)|num(j)==2^{m}-1\)即可。而状态数至多\(2^m\)个。
E
这一题极其重要。
首先应该快速反应过来最小值不是i就是1
考虑最大值：考虑任何一个朋友x，假设他在一段区间内都没有被移到队首，考察其他朋友对他的影响：假设朋友i在他右边并被移到队首，那么x的位置加一，而在这之后朋友i的移动都不会对x产生任何影响，因而可以知道x在这段区间内向右移动次数为这段区间内不同朋友的个数。这可以用主席树完成。而x没有被操作的区间显然就是它相邻两次被操作的区间。不过从一开始到x被操作的区间需要求比他大的不同朋友个数，这可以用BIT实时更新来求出来。所有区间取max即可。
主席树任何一次单点更新都将产生一棵新树，不可直接在原树上修改！！
