Codeforces Round #337 (Div. 2) ABCDE

2019-04-13 22:06发布

站内文章 / 模拟电子
17355 0 1356
A Pasha and Stick         简单分类讨论。 #include using namespace std; #define ll long long int main(){ int n; cin>>n; if(n&1){ cout<<0<>=1; if(n&1){ cout<
B Vika and Squares         贪心。就是找最小值之间的最大距离，我实现的时候把数组copy了一份放在后面，这样处理比较简单。 #include using namespace std; #define ll long long int a[400010]; int main(){ int n; cin>>n; int MIN=1e9+10; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); MIN=min(MIN,a[i]); } for(int i=1;i<=n;i++){ a[i+n]=a[i]; } int pre=1; int len=0; for(int i=1;i<=n*2;i++){ if(a[i]==MIN){ len=max(len,i-pre-1); pre=i; } } ll ans = (ll)n*MIN+len; cout<
C Harmony Analysis         构造题。首先k=1很容易构造出来。k=x+1其实是由4个k=x构成的，用4个k=x拼起来后，把其中一个取反即可。 #include using namespace std; #define ll long long int a[1111][1111]; int main(){ int k; cin>>k; int n = 1<
D Vika and Segments         这种题一看就知道是用map乱搞。大体思路是分开横向和纵向，先计算横向的，然后对于每个纵向的，看它穿过了多少个横向的，减去重叠部分即可。         一步一步来，首先是要把横向和纵向分开，同向的里面也有重叠的，把重叠的合并。然后简单计算一下所有横向的结果。计算完后，从左到右处理纵向的。对于枚举的每个纵向条条，维护有哪些横向的条条的横坐标包含了纵向条条的横坐标（我利用了map和priority_queue维护，具体见代码），然后利用树状数组（当然，事先离散化了Y坐标）计算它穿越了多少横向条条，把重叠部分减去即可。 #include using namespace std; #define ll long long int n; struct hor{ int x1,x2; int y; bool ban; bool operator<(const hor& other)const{ if(y!=other.y){ return y b.x2; } }; struct ver{ int y1,y2; int x; bool ban; bool operator<(const ver& other)const{ if(x!=other.x){ return x ymp; //用于离散化 int c[200010]; inline int lowbit(const int &x){ return x&(-x); } void update(int x,int val){ while(x<200010){ c[x]+=val; x+=lowbit(x); } } int query(int x){ int ans = 0; while(x){ ans+=c[x]; x-=lowbit(x); } return ans; } int main(){ cin>>n; for(int i=1;i<=n;i++){ int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if(x1>x2)swap(x1,x2); if(y1>y2)swap(y1,y2); if(x1==x2){ vers[vcnt].y1=y1; vers[vcnt].y2=y2; vers[vcnt].x =x1; vcnt++; }else{ hors[hcnt].x1=x1; hors[hcnt].x2=x2; hors[hcnt].y =y1; hcnt++; } ymp[y1]=0; ymp[y2]=0; } sort(vers,vers+vcnt); sort(hors,hors+hcnt); //离散化 int kk = 1; for(map::iterator it = ymp.begin();it!=ymp.end();it++){ it->second = kk++; } //同向的合并 for(int i=1;i,cmpx2> que; int k=0; for(int i=0;i
E Alphabet Permutations         线段树。线段树维护的是每个位置的字符，以及区间上，字符x紧接着字符y的次数（最多10*10组x,y）。对于每次询问，相当于得到了一个“字典序”，在线段树中查询，共有多少组相邻的字符xy，x的字典序小于y，记为sum，答案就是n-sum。因为n-repeat肯定是满足的，出现一次上述情况，可以省去一次。 #include using namespace std; int n,m,k; char str[200010]; struct node{ int l,r; int ch; int lazy; int val[10][10]; }tree[800010]; void push_up(int x){ if(tree[x].l==tree[x].r)return; node& lson = tree[x<<1]; node& rson = tree[(x<<1)|1]; for(int i=0;i>1; if(pos<=mid){ return queryCh(x<<1,pos); }else{ return queryCh((x<<1)|1,pos); } } void push_down(int x,int ch){ if(tree[x].l == tree[x].r){ tree[x].lazy = -1; return; } node& lson = tree[x<<1]; node& rson = tree[(x<<1)|1]; lson.lazy = rson.lazy = tree[x].lazy; tree[x].lazy = -1; lson.ch = tree[x].ch; rson.ch = tree[x].ch; for(int i=0;i>1; if(pos<=mid){ updateVal(x<<1,pos); }else{ updateVal((x<<1)|1,pos); } push_up(x); } void build_tree(int x,int l,int r){ tree[x].l = l; tree[x].r = r; tree[x].lazy = -1; if(l==r){ if(l)tree[x].val[str[l-1]-'a'][str[l]-'a'] = 1; tree[x].ch = str[l]-'a'; return; } int mid = (l+r)>>1; build_tree(x<<1,l,mid); build_tree((x<<1)|1,mid+1,r); push_up(x); } void update(int x,int l,int r,int ch){ if(l==tree[x].l && r==tree[x].r){ tree[x].lazy = ch; tree[x].ch = ch; memset(tree[x].val,0,sizeof(tree[x].val)); return; } if(~tree[x].lazy){ push_down(x,tree[x].lazy); } int mid = (tree[x].l+tree[x].r)>>1; if(mid>=r){ update(x<<1,l,r,ch); }else{ if(mid>1; if(mid>=r){ query(x<<1,l,r); }else{ if(mid>n>>m>>k; scanf("%s",str); build_tree(1,0,n-1); while(m--){ int op; scanf("%d",&op); if(op==1){ //update int l,r; char chs[2]; scanf("%d%d%s",&l,&r,chs); update(1,l-1,r-1,chs[0]-'a'); if(l-1)updateVal(1,l-1); updateVal(1,r); }else{ //query char per[11]; scanf("%s",per); Q(0,n-1); bool tmp[11][11] = {0}; for(int i=0;i

热门文章