3.26 - 4.14

3.26-4.14

CF-629D

상승자 서열의 최대 합을 구한다.O(n^2)는 폭력적이므로 검색할 때 라인 트리로 유지해야 한다

권치는 부동점수이기 때문에 먼저 이산화하고 i번째 위치의 권치를 설정하여 작은 순위에서 큰 순위로 id로 한다.그러면 dp 이동 중\[d[i]=max(d[i],d[i]+d[j])\] 중\[j,그러므로 라인 트리 결점 구간[l,r]은 id=l에서 id=j의 최대 dp값

을 유지한다

#include 
using namespace std;
const int N = 100000;
double vol[N],r,h;
int n,has[N],g[N],dp[N],tot;
int c[N];
vector v;
int getId(double a){
    return lower_bound(v.begin(),v.end(),a)-v.begin()+1;
}
struct Tree{
    int l,r;
    double data;
}t[4*N];
void build(int p,int l,int r){
    t[p].l = l;
    t[p].r = r;
    if(l==r){
        t[p].data = 0;return;
    }
    int mid = l+r>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].data = 0;
}
void change(int p,int x,double val){
    if(t[p].l == t[p].r && t[p].l == x){
        t[p].data = max(t[p].data,val);
        return ;
    }
    int mid = (t[p].l+t[p].r)>>1;
    if(x<=mid)change(p*2,x,val);
    else change(p*2+1,x,val);
    t[p].data = max(t[p*2].data,t[p*2+1].data);
}
double ask(int p,int l,int r){
    if(t[p].l>=l&&t[p].r<=r)return t[p].data;
    int mid = (t[p].l+t[p].r)>>1;
    double val = 0;
    if(l<=mid)val = max(val,ask(p*2,l,r));
    if(r>mid)val = max(val,ask(p*2+1,l,r));
    return val;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lf%lf",&r,&h);
        vol[i] = acos(-1) * r * r * h;
        v.push_back(vol[i]);
    }
    sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());
    build(1,1,n);
    double res = 0;
    for(int i=1;i<=n;i++){
        int id = getId(vol[i]);
        double now = ask(1,1,id-1);
        now = max(vol[i],vol[i]+now);
        res = max(res,now);
        change(1,id,now);
    }
    printf("%.10lf
",res);
    return 0;
}

여러 번 뒤척였는데 부끄러워요. 트리가 문제를 너무 적게 냈어요

법2: 이산화+나무상수조

#include 
using namespace std;
const int N = 100010;
const int inf = 0x3f3f3f3f;
double vol[N],c[N];
vector v;
int n,g[N];
int getId(double res){
    return lower_bound(v.begin(),v.end(),res) - v.begin() + 1;
}
void add(int x,double y){
    c[x] = y;
    for(;x<=n;x+=x&-x)c[x] = max(c[x],y);
}
double ask(int x){
    double res = 0;
    for(;x;x-=x&-x)res = max(res,c[x]);
    return res;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        double r,h;
        scanf("%lf%lf",&r,&h);
        double vo = acos(-1) * r * r * h;
        vol[i] = vo;
        v.push_back(vo);
    }
    sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());
    double res = 0;
    for(int i=1;i<=n;i++){
        int x = getId(vol[i]);
        double now = ask(x-1) + vol[i];
        add(x,now);
        res = max(res,now);
    }
    printf("%.10lf
",res);
    return 0;
}

CF-332B

제목: 길이가 n인 서열을 정하고 두 단락이 교차하지 않는 길이가 k인 서열을 찾아 권한과 최대치를 설정합니다.
어떻게 하든지 할 수 있다. 사실 단조로운 대열과 같은 사상은 변수 하나만 보존하면 가장 좋은 결정을 내릴 수 있다

#include 
using namespace std;
const int N = 200010;
typedef long long ll;
int n,k;
ll a[N],sum[N];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        sum[i] = sum[i-1]+a[i];
    }
    int pre = 1,l = 1,r = k+1,fi = 1,se = 1;
    ll res = 0;
    for(;r<=n-k+1;r++){
        if(sum[pre+k-1]-sum[pre-1] < sum[r-1]-sum[r-1-k])pre = r-k;

        if(sum[r+k-1]-sum[r-1]+sum[pre+k-1]-sum[pre-1] > res){
            res = sum[r+k-1]-sum[r-1]+sum[pre+k-1]-sum[pre-1];
            fi = pre;
            se = r;
        }
    }
    printf("%d %d
",fi,se);
    return 0;
}

CF-1043D

제의: 간격이 k인 n개의 점이 수축에 있고 아래는\(1,k+1,2*k+1,(n-1)*k+1\)로 표시되어 있다.시작점은 s이고 보폭은 L이다. 그러나 지금은 s가 가장 가까운 점의 거리는 a이고 (s+L) 거리가 가장 가까운 점의 거리는 b라는 것만 알 수 있다.s에서 출발해 처음으로 s로 돌아왔을 때 가장 많이 걷고 가장 적게 걷는다.

분석: x보를 걸어서 출발점으로 돌아가면\(x*l=t*n*k\) x보를 걸어서 t권을 용서하고 x와 t의 상호질로 인해 처음으로 s로 돌아가는 것을 보증하기 때문에\(x={n*k\overgcd(n*k,l)}\)가 있다.그래서 모든 가능한 l을 매거하여 gcd의 최대치와 최소치를 얻으면 된다.

l (l

\(l = k-a-b\)

\(l = k+b-a\)

\(l = a+b\)

\(l = k+a-b\)

그리고 모든 상황은 원래의 기초 위에서 i개의 k를 더 추가할 수 있다.총 4*n종l

#include 
using namespace std;
typedef long long ll;
ll n,k,a,b;
int main(){
    cin>>n>>k>>a>>b;
    ll mi = LONG_LONG_MAX;
    ll mx = 0;
    for(int i=0;i

CF-620 E - New Year Tree(상태 압축 + 세그먼트 트리)

#include 
using namespace std;
const int N = 400010;
typedef long long ll;
int n,m,cnt,c[N],num[N],id[N];
ll color[N];
vector v[N];
void dfs(int x,int fa){
    num[x] = 1;
    color[++cnt] = 1ll<>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].data = t[p*2].data | t[p*2+1].data;
}
void spread(int p){
    if(t[p].tag){
        t[p*2].data = t[p].data;
        t[p*2+1].data = t[p].data;
        t[p*2].tag = 1;
        t[p*2+1].tag = 1;
        t[p].tag = 0;
    }
}
void change(int p,int l,int r,int val){
    if(t[p].l>=l&&t[p].r<=r){
        t[p].data = 1ll<>1;
    if(l<=mid)change(p*2,l,r,val);
    if(r>mid)change(p*2+1,l,r,val);
    t[p].data = t[p*2].data | t[p*2+1].data;
}
ll ask(int p,int l,int r){
    
    if(t[p].l>=l&&t[p].r<=r){
        return t[p].data;
    }
    spread(p);
    int mid = t[p].l+t[p].r>>1;
    ll res= 0;
    if(mid>=l)res |= ask(p*2,l,r);
    if(mid>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",&c[i]);
    for(int i=1;i<=n-1;i++){
        int x,y;scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,-1);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int k,x,y;
        scanf("%d%d",&k,&x);
        if(k==1){
            scanf("%d",&y);
            change(1,id[x],id[x]+num[x]-1,y);
        }
        else{
            ll res = ask(1,id[x],id[x]+num[x]-1);
            int ans = 0;
            while(res){if(res&1)ans++;res/=2;}
            printf("%d
",ans);
        }
    }
    return 0;
}

CF-1140 E - Palindrome-less Arrays

제목: 채우지 않은 서열을 지정합니다. 수치가 -1이면 1~k의 숫자로 덮어쓸 수 있습니다. 이 서열을 채운 후 길이가 홀수인 회문열이 존재하지 않는 방안 수를 구하십시오.
분석:

길이가 홀수인 회문열이 존재하지 않도록 하고 길이가 3인 회문열이 존재하지 않는 것을 만족시키면 된다.다시 말하면\(a[i] eq a[i+2]\)는 모든\(i\)에 대해 성립된다.i의 홀수와 i의 짝수는 서로 영향을 주지 않는다는 것을 알 수 있다.그래서 두 줄로 나눌 수 있어요.

한 줄에 $a1,a_3,a_5,\dots$구성

다른 문자열은 $a2,a_4,a_6,\dots$구성

현재 문제는 다음과 같다. 하나의 서열을 정하고 그 수치를 -1의 위치에서 1~k의 숫자로 바꾸어 서열에서 두 개의 인접한 숫자가 다른 방안수로 바꾼다.각도를 바꾸어 생각해 보면 어떤 조의 연속적인 -1(길이는 0 또는 1)은 양쪽 모두 네 가지 상황일 뿐이다

양쪽에 숫자가 없다(즉 전체 열이 -1이다)

양쪽 중 한 쪽이 있는지 없는지(꿰미 전체의 좌우 양쪽만 이런 경우)

양쪽의 숫자가 같다

양쪽의 숫자가 다르다

또한 앞의 두 가지 상황은 뒤의 두 가지 상황으로 미룰 수 있기 때문에 0~(n/2)+1 길이의 -1열을 예처리하면 문제가 쉽게 풀린다는 것을 알 수 있다.

\(d(i, j)\)는 길이가\(i\)인 -1열을 나타내고 j는 0이면 양쪽 숫자가 같고 1이면 양쪽 숫자가 같지 않은 방안 수를 나타내며\(d[0][0]=0, d[0][1]=1\)는 전이 방정식이 있다.

\(i\)가 홀수입니다.

$d[i][0] = d[i/2][0]d[i/2][0] + (k-1)d[i/2][1]*d[i/2][1] $

\(d[i][1] = d[i/2][0]*d[i/2][1]*2 + (k-2)*d[i/2][1]*d[i/2][1]\)

\(i\)는 짝수입니다.

\(d[i][0] = (k-1)*d[i-1][1]\)

\(d[i][1] = d[i-1][0] + (k-2)*d[i-1][1]%mod\)

i가 홀수인 경우 우리는 이 서열의 중간 위치인mid를 꺼낼 수 있다. -1열의 양쪽 숫자가 같고 모두 x와 같을 때mid숫자가 x와 같다고 가정하면 두 개의 길이가 i/2이고 서열의 양쪽 끝이 같은 서브문제로 전환한 다음에mid가 x와 다르다고 가정하면 (k-1)가지 방법이 있다. 똑같이 두 개의 길이가 i/2이고 서열의 양쪽 끝이 다른 서브문제로 전환할 수 있다.-1열의 양쪽 숫자가 같지 않으면 같은 이치이다.
d수 그룹을 미리 처리한 후에 우리가 이전에 나누었던 짝짓기를 처리할 수 있습니다.사고방식은 이전에 -1이 되지 않았던 위치를 기록하는 것이다.그리고 마지막으로 특판을 하면 정답을 얻을 수 있다.

#include 
using namespace std;
typedef long long ll;
const int mod = 998244353;
ll d[100010][2];
int a[100010],b[100010];
ll n,k;
ll solve(int *a,ll len){
    ll res = 1;
    ll last = 0;
    for(ll i=1;i<=len;i++){
        if(a[i] == -1)continue;
        else{
            if(i == 1){
                last = i;continue;
            }
            if(last == 0){
                res = res * (d[i-2][0] + (k-1)*d[i-2][1])%mod;
            }
            else{
                if(a[i] == a[last]){
                    res = res * d[i-last-1][0]%mod;
                }
                else res = res * d[i-last-1][1]%mod;
            }
            last = i;
        }
    }
    if(last==0){
        res = k;
        for(int i=2;i<=len;i++)res = (res*(k-1))%mod;
    }
    else if(last !=len){
        res = res * (d[len-last-1][0] + (k-1)*d[len-last-1][1]%mod)%mod;
    }
    return res;
}
int main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++){
        if(i&1)scanf("%d",&a[(i+1)/2]);
        else scanf("%d",&b[i/2]);
    }
    d[0][0] = 0;d[0][1] = 1;
    for(int i=1;i<=(n+1)/2;i++){
        if(i&1){
            int len = i/2;
            d[i][0] = (d[len][0] * d[len][0]%mod + (k-1) * d[len][1]%mod * d[len][1]%mod)%mod;
            d[i][1] = (d[len][0] * d[len][1]%mod * 2%mod + (k-2) * d[len][1]%mod * d[len][1]%mod)%mod;
        }
        else{
            d[i][0] = (d[i-1][1] * (k-1)) % mod;
            d[i][1] = (d[i-1][0] + (k-2) * d[i-1][1]%mod)%mod;
        }
    }
    printf("%lld
",(solve(a,(n+1)/2)*solve(b,n-(n+1)/2))%mod);
    return 0;
}

CH6101 최우선 무역(최단로)

#include 
using namespace std;
const int N = 100010;
const int M = 500010;
int val[N],n,m,d[N],f[N],vis[N];
vector v[N];
struct edge{
    int x,y,k;
}e[M];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&val[i]);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].k);
        v[e[i].x].push_back(e[i].y);
        if(e[i].k == 2)v[e[i].y].push_back(e[i].x);
    }
    memset(d,0x3f,sizeof d);
    d[1] = val[1];
    priority_queue< pair > q;
    q.push(make_pair(-val[1],1));
    while(!q.empty()){
        int x = q.top().second;q.pop();
        if(vis[x])continue;
        vis[x] = 1;
        for(int i=0;i min(val[y],d[x])){
                d[y] = min(val[y],d[x]);
                q.push(make_pair(-d[y],y));
            }
        }
    }
    for(int i=1;i<=n;i++){
        v[i].clear();vis[i] = 0;
    }
    for(int i=1;i<=m;i++){
        v[e[i].y].push_back(e[i].x);
        if(e[i].k == 2)v[e[i].x].push_back(e[i].y);
    }
    q.push(make_pair(val[n],n));
    f[n] = val[n];
    while(!q.empty()){
        int x = q.top().second;q.pop();
        if(vis[x])continue;
        vis[x] = 1;
        for(int i=0;i

CF-1141F2 - Same Sum Blocks (Hard)

제목: 길이가 n(n<=1500)인 서열로 최대한 많은 구간으로 나누어 각 구간을 합친 것과 같다.
분석: 맵으로 각각 대응하는 구간의 좌우 단점map>> segs;을 저장한 다음에 동일한 화합에 대해 서로 교차하지 않는 구간을 최대 몇 개까지 나눌 수 있는지 확인해 본다.비교적 쉽게 생각할 수 있는 욕심 전략은 오른쪽 단점이 점차적으로 증가하는 순서대로 구간을 선택하는 것이다. 그러면 우리가 처음에 구간을 선별할 때 오른쪽 단점이 왼쪽에서 오른쪽으로 순서대로 하면 된다.

#include 
using namespace std;
int main(){
    int n;
    cin >> n;
    vector a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    map>> segs;
    //              
    for (int r = 0; r < n; r++) {
        int sum = 0;                              
        for (int l = r; l >= 0; l--) {
            sum += a[l];
            segs[sum].push_back({l, r});
        }
    }
    int result = 0;
    vector> best;
    for (const auto& p: segs) {
        //const   ，    
        const vector>& pp = p.second;
        int cur = 0;
        int r = -1;
        //    
        vector> now;
        for (auto seg: pp)
            if (seg.first > r) {
                cur++;
                now.push_back(seg);
                r = seg.second;
            }
        if (cur > result) {
            result = cur;
            best = now;
        }
    }
    cout << result << endl;
    for (auto seg: best)
        cout << seg.first + 1 << " " << seg.second + 1 << endl;
    return 0;
}

1119 D - Frets On Fire

사유문제, 어렵지 않은데 왜 겁먹었어.이런 난이도는 동메달 연습 문제도 계산하지 않을 것으로 추정된다.

#include 
using namespace std;
const int N = 100010;
typedef unsigned long long ll;
ll s[N],n,q,c[N],sum[N];
int main(){
    scanf("%lld",&n);
    for(int i=0;i

1119 E - Pavel and Triangles

욕심이야, 지나칠 수 없는 욕심이 틀린 게 틀림없어. 우선 1+2의 일치 방안

#include 
using namespace std;
const int N = 300010;
typedef long long ll;
ll a[N],n;
int main(){
    scanf("%d",&n);
    long long res = 0;
    for (int i = 0; i < n; ++i)
    {
        scanf("%lld",&a[i]);
    }
    queue q;
    ll last = 0;
    ll now = 0;
    for(int i=0;i

1139 E - Maximize Mex

마지막으로 그림을 만들고 이분도를 일치시킵니다.

#include 
using namespace std;
const int N = 5050;
int n,m,p[N],c[N],d,del[N],res[N],k[N];
vector v[N];
int match[N],vis[N];
bool dfs(int x){
    for(int i=0;i=1;i--){
        int id = k[i];
        for(;j<=5000;j++){
            if(!dfs(j))break;//       ，    Mex j
        }
        res[i] = j;
        v[p[id]].push_back(c[id]);//           
    }
    for(int i=1;i<=d;i++)
        printf("%d
",res[i]);
    return 0;
}

결어:
최근에 물 문제를 좀 풀었죠. 별로 나아진 게 없는 것 같아서 사유량이 있는 문제를 만나면 오버를 해요.어제 시합을 했는데 자폐를 했습니다. 그래서 2주 동안 밀린 기록을 보충했습니다. 사실 평소에도 썼는데 어수선할 뿐입니다. 최근 2주 동안 두 번째 푸른 책을 보고 있습니다.여름 방학 전에 정해진 내용을 다 보내야 해요.힘을 내다
전재 대상:https://www.cnblogs.com/1625--H/p/10706010.html