Div1 530
感受到被 Div1 支配的恐惧了. jpg
真. 一个题都不会. jpg(虽然 T1 是我智障
感受到被构造题支配的恐惧了. jpg
A
直接树上贪心就行, 是我写错了. jpg
B
这个构造超级神仙有没有. jpg
给定的答案矩阵一定满足, 每一行或者每一列只有两种不同的字符交替出现
然后枚举 + 贪心即可...
C
被老 K Diss 了. jpg
这题给人的第一印象就是一个非常智障的构造.
然后发现它还有要求... 每个节点的度数最大值最小...
然后就不会了. jpg
(开什么玩笑, 怎么可能不会!
然后就可以通过枚举这个最大值的方式解决, 然后剩下的就直接连在某个点上来满足它的要求...
具体实现看代码吧... 有点说不清
总之就是一个 $K$ 叉树 + 一条链...
- #include <bits/stdc++.h>
- using namespace std;
- #define N 100005
- #define ll long long
- int fa[N],n,p;ll now,a[N];
- int main()
- {
- scanf("%d%lld",&n,&now);
- if(now*2>(ll)n*(n+1))return puts("No"),0;
- if(now<n*2-1)return puts("No"),0;
- for(p=1;p<=n;p++)
- {
- long long dep=1,cnt=1,t=1,c=1;
- while(cnt<n)c=c*p,dep++,t+=dep*min(c,n-cnt),cnt+=c;
- if(t<=now)break;
- }
- puts("Yes");
- long long dep=1,cnt=1,t=1,c=1;a[1]=1;
- while(cnt<n)
- {
- dep++;c=c*p;a[dep]=min(c,n-cnt);
- t+=dep*min(c,n-cnt),cnt+=c;
- }now-=t;
- long long now_d=dep,aft_d=dep+1;
- while(now)
- {
- if(a[now_d]<=1)now_d--;
- a[now_d]--;ll tmp=min(aft_d++,now_d+now);
- now-=tmp-now_d;a[tmp]++;
- }
- int lst=1;
- for(int i=2;i<aft_d;i++)
- {
- int nowp=lst-a[i-1]+1,nowk=0;
- // printf("%lld\n",a[i]);
- for(int j=lst+1;j<=lst+a[i];j++)
- {
- if(nowk==p)nowp++,nowk=0;
- nowk++,fa[j]=nowp;
- }lst+=a[i];
- }
- for(int i=2;i<=n;i++)printf("%d",fa[i]);puts("");
- }
- //sdadasdasd
- D
这个读题杀啊...
根本读不懂啊. jpg
读懂了就是维护一个动态前缀和来求满足这个式子 $sum_{i-1}\times 2\le a_i$ 的 $i$ 的数量. jpg
那么显然, 答案小于 $30$
然后就直接树状数组 + set 即可...
每次找到 $\min {a_i}$ 然后每次翻倍去找 + 树状数组查前缀和. jpg
就是慢了点. jpg
- #include <cstdio>
- #include <algorithm>
- #include <cmath>
- #include <cstring>
- #include <cstdlib>
- #include <queue>
- #include <iostream>
- #include <bitset>
- #include <set>
- using namespace std;
- #define N 500005
- #define ll long long
- int w[N],p[N],n,sp;char str[10];
- multiset<int>s;int siz;ll c[N];
- void fix(int x,int v){for(;x<=sp;x+=x&-x)c[x]+=v;}
- ll find(int x){ll ret=0;for(;x;x-=x&-x)ret+=c[x];return ret;}
- void add(int x){siz++;s.insert(p[x]);fix(x,p[x]);}
- void del(int x){siz--;s.erase(s.find(p[-x]));fix(-x,-p[-x]);}
- int get_ans()
- {
- if(!siz)return 0;
- int ret=1,now=*s.begin();
- while(1)
- {
- if(now>1e9)break;
- if(s.upper_bound(now<<1)!=s.end())
- {
- int t=*s.upper_bound(now<<1);
- t=lower_bound(p+1,p+sp+1,t)-p;
- if(find(t-1)*2<p[t])ret++;now=p[t]+now;
- }else return siz-ret;
- }return siz-ret;
- }
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- scanf("%s%d",str,&p[i]),(str[0]=='+'?(w[i]=p[i]):(w[i]=-p[i]));
- sort(p+1,p+n+1);sp=unique(p+1,p+n+1)-p-1;
- for(int i=1;i<=n;i++)w[i]=(w[i]<0)?-(lower_bound(p+1,p+sp+1,-w[i])-p):lower_bound(p+1,p+sp+1,w[i])-p;
- for(int i=1;i<=n;i++)
- if(w[i]<0)del(w[i]),printf("%d\n",get_ans());
- else add(w[i]),printf("%d\n",get_ans());
- }
- // dasdasd
来源: http://www.bubuko.com/infodetail-2945251.html