首页 > itarticle > codeforces round 271(div. 2)

codeforces round 271(div. 2)

admin 12月 05, 2020 0

C.Captain Marmot (几何,点旋转)

思路

其中顺时针旋转为负，逆时针旋转为正，角度angle是弧度值，如旋转30度转换为弧度为： $angle = pi/180 * 30$。

4、度与角度的转换
根据圆为$360 º$，弧度为$2π$，即 $360º = 2π$

4.1 角度转弧度：$2π / 360 = π / 180 ≈ 0.0174rad$, 即: $度数 (π / 180） = 弧度$
例如：将30º转为弧度rad
$ 30º (π / 180）= 0.523320 rad $

4.2 弧度转角度: $360 / 2π = 180 / π ≈ 57.3º$, 即: $ 弧度 (180 / π） = 度数$
例如：将$0.523320rad$转为度º
$0.523320rad (180 / π) = 29.9992352688º $

若o不是原点，则可先将a点坐标转换为相对坐标计算，计算结果再加上o点坐标。

参与计算的a点坐标实际应为 a - 0,最终计算公式如下：

$b.x = ( a.x - o.x)cos(angle) - (a.y - o.y)sin(angle) + o.x$

$b.y = (a.x - o.x)sin(angle) + (a.y - o.y)cos(angle) + o.y$

Flowers (DP)

思路

少于k的肯定全是1因为都只能放红色。

大于K的可以放红色$dp[i-1]$ 或者连续的k个白色$dp[i-k]$

E - Pillars (DP+线段树+离散化)

思路

很明显的DP，但是数值太大，所以考虑离散化然线段树取区间最大值

F - Ant colony (线段树区间gcd,线段树求最小值的个数)

思路

题意就是查询区间GCD 然后求出区间gcd的个数，后面的操作也可以主席树写


using namespace std;
typedef long long ll;
const int maxn=1e5+50;
int a[maxn];
#define bug cout<<"here"<<endl;
struct {
    #define ls (o<<1)
    #define rs ((o<<1)|1)
    int gcd[maxn<<2],mi[maxn<<2],num[maxn<<2];
    void push_up(int o){
        gcd[o]=__gcd(gcd[ls],gcd[rs]);
    }
    void build(int o,int l,int r){
        if(l==r){
            mi[o]=gcd[o]=a[l];
            num[o]=1;
            return;
        }
        int mid=(l+r)/2;
        build(ls,l,mid);
        build(rs,mid+1,r);
        push_up(o);
    }
    int query(int o,int l,int r,int ql,int qr){
        if(ql<=l&&qr>=r){
            return gcd[o];
        }
        int mid=(l+r)/2;
        int gc=0;
        if(ql<=mid)gc=__gcd(gc,query(ls,l,mid,ql,qr));
        if(qr>mid)gc=__gcd(query(rs,mid+1,r,ql,qr),gc);
        return gc;
    }
}tree;

int sum[maxn*40],rt[maxn*40];
int lss[maxn*40],rss[maxn*40];
int cnt;
void update(int &o,int pre,int l,int r,int val){
    o=++cnt;
    lss[o]=lss[pre];rss[o]=rss[pre];
    sum[o]=sum[pre];
    if(l==r){sum[o]++;return;}
    int mid=(l+r)/2;
    if(val<=mid)update(lss[o],lss[pre],l,mid,val);
    else update(rss[o],rss[pre],mid+1,r,val);
}
int query(int o,int l,int r,int val){
    if(l==r){
        return sum[o];
    }
    int mid=(l+r)/2;
    if(val<=mid)return query(lss[o],l,mid,val);
    else return query(rss[o],mid+1,r,val);
}

int n;

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        update(rt[i],rt[i-1],1,1e9,a[i]);
    }
    tree.build(1,1,n);
    int m;
    cin>>m;
    while(m--){
        int l,r;
        cin>>l>>r;
        int gc=tree.query(1,1,n,l,r);
        int num=query(rt[r],1,1e9,gc);
        int num1=query(rt[l-1],1,1e9,gc);
        cout<<r-l+1-num+num1<<endl;

    }
    return 0;
}