Codeforces Round #337 (Div. 2) ABCDE
2019-04-13 22:06发布
生成海报
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
打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮