(POI) XXI OI Round II - day 2 Task Little Bird

https://szkopul.edu.pl/problemset/problem/xfpVU8vFP2RzZ0hrqWq9kTZM/site/?key=statement

只能拜中國大神了<(_ _)>我這份code是看提示之後才AC的><。

#include <iostream>
#include <cstdio>
#include <utility>
#include <queue>
using namespace std;

const int N = 1000006;

#define F first
#define S second

typedef pair<int,int> pii;
typedef pair<pii,int> piii;

int a[N];
int dp[N];

int main ()
{
    int n;
    scanf("%d",&n);
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&a[i]);
    }
    int q;
    scanf("%d",&q);
    while (q--)
    {
        int k;
        scanf("%d",&k);
        deque<piii> dq;
        dp[1] = 0;
        dq.push_back(make_pair( make_pair(dp[1],-a[1]),1 ));
        #define SZ(x) ((int)(x).size())
        for (int i=2;n>=i;i++)
        {
            while (SZ(dq) &&dq[0].S == i-k-1) dq.pop_front();
            piii p = dq[0];
            dp[i] = (p.F.F + (-p.F.S > a[i]?0:1));
            piii now = make_pair( make_pair(dp[i],-a[i]),i );
            while (SZ(dq) && dq.back() > now)
            {
                dq.pop_back();
            }
            dq.push_back(now);
        }
        printf("%d\n",dp[n]);
    }
}

(POI) XXI OI Round I Task Salad Bar

https://szkopul.edu.pl/problemset/problem/d30xri2XGeuQ45CDrB7DWijK/site/?key=statement

#include <iostream>
#include <cstdio>
#include <vector>
#include <cassert>
using namespace std;

#define prev kirino

const int N = 1000006;
const int NN = 2*N;

int Val(int x)
{
    return x+N;
}

int rVal(int x)
{
    return x-N;
}

int suf[N];
int sufiter[NN];
vector<int> sufv[NN];
int suf_left[N];

int pre[N];
int preiter[NN];
vector<int> prev[NN];

int a[N];
char s[N];

int mn[4*N];

void build(int now,int L,int R)
{
    if (L == R)
    {
        mn[now] = suf_left[L];
        return;
    }
    int mid=(L+R)>>1;
    build((now<<1),L,mid);
    build(((now<<1)|1),mid+1,R);
    mn[now] = min(mn[(now<<1)],mn[((now<<1)|1)]);
}

const int INF = (1<<30);

int query2(int now,int L,int R,int left)
{
    if (L==R)
    {
        return (suf_left[L]>left?0:L);
    }
    int mid=(L+R)>>1;
    if (mn[((now<<1)|1)] <= left) return query2(((now<<1)|1),mid+1,R,left);
    else return query2((now<<1),L,mid,left);
}

int query(int now,int L,int R,int l,int r,int left)
{
    if (l <= L && R <= r)
    {
        if (mn[now] > left) return 0;
        else return query2(now,L,R,left);
    }
    int mid=(L+R)>>1;
    //[L,mid] [mid+1,R]
    //[l,r]
    if (mid+1 > r) return query((now<<1),L,mid,l,r,left);
    else if (l > mid) return query(((now<<1)|1),mid+1,R,l,r,left);
    int ret = 0;
    if ((ret = query(((now<<1)|1),mid+1,R,l,r,left)) != 0) return ret;
    else return query((now<<1),L,mid,l,r,left);
}

int main ()
{
    int n;
    scanf("%d\n",&n);
    scanf("%s",s);
    for (int i=1;n>=i;++i)
    {
        a[i] = (s[i-1] == 'p' ? 1 : -1);
        pre[i] = pre[i-1] + a[i];
        prev[Val(pre[i])].push_back(i);
    }
    for (int i=n;i>=1;--i)
    {
        suf[i] = suf[i+1] + a[i];
        sufv[Val(suf[i])].push_back(i);
    }
    for (int i=n;i>=1;--i)
    {
        int q=Val(suf[i+1]-1);
        int left = n+1;
        if (sufiter[q] == sufv[q].size()) left = 1;
        else left = sufv[q][sufiter[q]]+1;
        sufiter[Val(suf[i])]++;
        if (left != i+1)
        {
            suf_left[i] = left;
        }
        else
        {
            suf_left[i] = INF;
        }
    }
    build(1,1,n);
    int ans=0;
    int mx=0;
    for (int i=1;n>=i;++i)
    {
        int q=Val(pre[i-1]-1);
        int right = 0;
        if (preiter[q] == prev[q].size()) right = n;
        else right = prev[q][preiter[q]]-1;
        preiter[Val(pre[i])]++;
        if (right != i-1)
        {
            int ret=query(1,1,n,i,right,i);
            if (ret != 0)
            {
                ans = max(ans,ret-i+1);
            }
        }
    }
    printf("%d\n",ans);
}

(POI) XXI OI Round III (finals) - day 0 (trial) Task FarmCraft

https://szkopul.edu.pl/problemset/problem/dGllMe_Kjqa5SGT9wMo6UGlp/site/?key=statement

很具有想法性的一題XDD

#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 500006;

vector<int> G[N];
int par[N];
int sz[N];
int deg[N];
int c[N];
vector< pair<int,int> > v[N];

void dfs(int u,int p)
{
    sz[u] = 1;
    if (u!=p)
    {
        deg[p]++;
        //cout<<"p = "<<p<<" , deg = "<<deg[p]<<endl;
    }
    par[u] = p;
    for (int v:G[u])
    {
        if (v != p)
        {
            dfs(v,u);
            sz[u] += sz[v];
        }
    }
}

int solve(vector< pair<int,int> > v)
{
    sort( v.begin(),v.end(),[](const pair<int,int> &p1,const pair<int,int> &p2)
    {
        return p1.first-p1.second > p2.first-p2.second;
    });
    int mx = 0, pre = 0;
    for (pair<int,int> p:v)
    {
        mx = max(mx,p.first + pre);
        pre += p.second;
    }
    return mx;
}

int main ()
{
    int n;
    scanf("%d",&n);
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&c[i]);
    }
    for (int i=1;n>i;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1,1);
    queue<int> que;
    for (int i=1;n>=i;i++)
    {
        if (deg[i] == 0)
        {
            que.push(i);
        }
    }
    while (!que.empty())
    {
        int t=que.front();
        que.pop();
        if (t == 1) break;
        //cout<<"t = "<<t<<endl;
        int mx = max(solve(v[t]),c[t]);
        //cout<<"mx = "<<mx<<endl;
        v[par[t]].push_back(make_pair(mx+1,(sz[t])*2));
        deg[par[t]]--;
        if (deg[par[t]] == 0) que.push(par[t]);
    }
    int ans= c[1] + ((n-1)*2);
    ans = max(ans, solve(v[1]));
    printf("%d\n",ans);
}

(POI) XXI OI Round II - day 1 Task Supercomputer

https://szkopul.edu.pl/problemset/problem/e9ycK_efBDBt4aPs-QeqYpwR/site/?key=statement

看了中國大神們的解釋之後，終於寫出來了

附個網址：http://victorwonder.is-programmer.com/posts/80059.html

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

const int N = 1000006;

int depth[N];
int s[N];
int par[N];

int q[N];
long long ans[N];

typedef long long LL;

struct L
{
    LL m;
    LL b;
    L(LL _m,LL _b):m(_m),b(_b){}
    LL val(LL x)
    {
        return m*x+b;
    }
};

bool check(L a,L b,L c)
{
    return (a.m - b.m) * (a.b - c.b) > (a.b - b.b) * (a.m - c.m);
}

int main ()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for (int i=1;m>=i;i++)
    {
        scanf("%d",&q[i]);
    }
    depth[1] = 1;
    s[0]++;
    int mx_depth = 0;
    for (int i=2;n>=i;i++)
    {
        scanf("%d",&par[i]);
        depth[i] = depth[par[i]] + 1;
        s[depth[i]-1]++;
        mx_depth = max(mx_depth,depth[i]);
    }
    for (int i=mx_depth;i>=1;i--)
    {
        s[i] += s[i+1];
    }
    //version O(n*k)
    //ans = max(i + ceil((s[i])/k))
    //ans = max(ceil((k*i + s[i])/k))
    /*
    70pts www
    for (int i=1;m>=i;i++)
    {
        int ans = 0;
        for (int j=1;mx_depth>=j;j++)
        {
            ans = max(ans,(j) + (s[j]+q[i]-1)/q[i]);
        }
        printf("%d",ans);
        if (i==m) puts("");
        else putchar(' ');
    }
    */
    deque<L> dq;
    #define SZ(x) ((int)(x).size())
    for (int i=1;mx_depth >= i;i++)
    {
        L line = L(i,s[i]);
        line.m = i;
        line.b = s[i];
        while (SZ(dq) >= 2 && check(dq[SZ(dq)-2],dq[SZ(dq)-1],line))
        {
            dq.pop_back();
        }
        dq.push_back(line);
    }
    for (int i=1;n>=i;i++)
    {
        while (SZ(dq) >= 2 && dq[0].val(i) < dq[1].val(i))
        {
            dq.pop_front();
        }
        ans[i] = dq[0].val(i);
        ans[i] = (ans[i] + i-1)/i;
    }
    for (int i=n + 1;1000000>=i;i++)
    {
        ans[i] = ans[i-1];
    }
    for (int i=1;m>=i;i++)
    {
        printf("%lld",ans[q[i]]);
        if (i==m) puts("");
        else putchar(' ');
    }
}

(POI) XXI OI Round I Task Couriers

https://szkopul.edu.pl/problemset/problem/Cs38m8lWFnOfDskXf43HR3lN/site/?key=statement

總共有三種作法，我實作了兩種

作法一：random sampling
靈感是來自2015年的全國賽啦。
那年的pF就是random sampling，所以，我想說，這題也應該可以用。

我最終的最法是：隨便挑27個數字，去看那個數字在區間的個數。

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int N = 500006;

vector<int> v[N];
int a[N];

int myRnd()
{
    return abs((rand()<<15)^rand());
}

int myRnd(int L,int R)
{
    return myRnd()%(R-L+1)+L;
}

const int K1 = 50;
const int K2 = 27;
const int K3 = 1;

int cnt[N];

int main ()
{
    srand(time(NULL));
    int n,q;
    scanf("%d %d",&n,&q);
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&a[i]);
        v[a[i]].push_back(i);
    }
    while (q--)
    {
        int l,r;
        scanf("%d %d",&l,&r);
        if (r-l <= K1)
        {
            for (int i=l;r>=i;i++)
            {
                cnt[a[i]]++;
            }
            int half = (r-l+1);
            half = (half)/2 + 1;
            int ans = 0;
            for (int i=l;r>=i;i++)
            {
                if (cnt[a[i]] >= half)
                {
                    ans = a[i];
                }
                cnt[a[i]]=0;
            }
            printf("%d\n",ans);
        }
        else
        {
            vector<int> vv;
            for (int i=0;K2>i;i++)
            {
                vv.push_back(myRnd(l,r));
            }
            for (int i:vv)
            {
                cnt[a[i]]++;
            }
            int half = (r-l+1);
            half >>= 1;
            half++;
            int ans = 0;
            for (int i:vv)
            {
                if (cnt[a[i]] >= K3)
                {
                    if (upper_bound(v[a[i]].begin(),v[a[i]].end(),r) - lower_bound(v[a[i]].begin(),v[a[i]].end(),l) >= half)
                    {
                        ans = a[i];
                    }
                }
                cnt[a[i]]=0;
            }
            printf("%d\n",ans);
        }
    }
}

作法二

用可持久化線段樹維護值域，每次query的時候都走size比較大的那邊。

作法三

每個統計bit出現的次數，把那些bit組合起來，看看那個數字有沒有符合條件。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 500006;
const int M = 20;

int sum[N][M];

int a[N];

vector<int> v[N];

int query(int l,int r,int ask)
{
    if (ask >= N) return 0;
    return upper_bound(v[ask].begin(),v[ask].end(),r) - lower_bound(v[ask].begin(),v[ask].end(),l);
}

int main ()
{
    int n,q;
    scanf("%d %d",&n,&q);
    for (int i=1;n>=i;i++)
    {
        scanf("%d",&a[i]);
        v[a[i]].push_back(i);
        for (int j=0;M>j;j++)
        {
            sum[i][j] = sum[i-1][j];
            sum[i][j] += (((1<<j)&a[i])!=0);
        }
    }
    while (q--)
    {
        int l,r;
        scanf("%d %d",&l,&r);
        int half = ((r-l+1)>>1)+1;
        int ask = 0;
        for (int i=0;M>i;i++)
        {
            if (sum[r][i] - sum[l-1][i] >= half) ask |= (1<<i);
        }
        if (query(l,r,ask) >= half) printf("%d\n",ask);
        else puts("0");
    }
}

(POI) XXI OI Round II - day 2 Task Rally

https://szkopul.edu.pl/problemset/problem/BnzEADCfeJFjjev1Y9iHQANg/site/?key=statement

超級無敵精湛的一題XDD。

要不是有set還真的可以壓到O(N+M) XDD。

#include <iostream>
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;

const int N = 500006;

vector<int> oriG[N];
vector<int> preG[N];
vector<int> sufG[N];

int mp[N];

int predp[N],predpmx[N];
int sufdp[N],sufdpmx[N];
int deg[N];

vector< pair<int,int> > in_event[N],out_event[N];

int main ()
{
    vector< pair<int,int> > edges;
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;m>=i;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        oriG[x].push_back(y);
        deg[y]++;
        edges.push_back(make_pair(x,y));
    }
    queue<int> que;
    for (int i=1;n>=i;i++)
    {
        if (!deg[i])
        {
            que.push(i);
        }
    }
    int id=0;
    while (!que.empty())
    {
        int t=que.front();
        que.pop();
        mp[t] = ++id;
        for(int j:oriG[t])
        {
            deg[j]--;
            if (!deg[j])
            {
                que.push(j);
            }
        }
    }
    for (pair<int,int> &p:edges)
    {
        p.first = mp[p.first];
        p.second = mp[p.second];
        preG[p.second].push_back(p.first);
        sufG[p.first].push_back(p.second);
    }
    for (int i=1;n>=i;i++)
    {
        predp[i] = 0;
        for (int j:preG[i])
        {
            predp[i] = max(predp[i],predp[j] + 1);
        }
        predpmx[i] = max(predpmx[i-1],predp[i]);
    }
    for (int i=n;i>=1;i--)
    {
        sufdp[i] = 0;
        for (int j:sufG[i])
        {
            sufdp[i] = max(sufdp[i],sufdp[j] + 1);
        }
        sufdpmx[i] = max(sufdpmx[i+1],sufdp[i]);
    }
    for (pair<int,int> p:edges)
    {
        if (p.second - p.first > 1)
        {
            in_event[p.first+1].push_back(p);
            out_event[p.second].push_back(p);
        }
    }
    int mx=(1<<30),ans=0;
    multiset<int> st;
    for (int i=1;n>=i;i++)
    {
        int tmpmx = max(predpmx[i-1],sufdpmx[i+1]);
        for (pair<int,int> p:in_event[i])
        {
            st.insert(predp[p.first] + sufdp[p.second] + 1);
        }
        for (pair<int,int> p:out_event[i])
        {
            st.erase(st.find(predp[p.first]+sufdp[p.second]+1));
        }
        if (!st.empty())
        {
            tmpmx = max(tmpmx,*(--st.end()));
        }
        if (tmpmx < mx)
        {
            mx = tmpmx;
            ans = i;
        }
    }
    for (int i=1;n>=i;i++)
    {
        if (mp[i] == ans)
        {
            ans = i;
            break;
        }
    }
    printf("%d %d\n",ans,mx);
}

(POI) XXI OI Round II - day 1 Task Criminal

https://szkopul.edu.pl/problemset/problem/APWi6y6XTt5ujve8ynI_FNJ1/site/?key=statement

神奇的線性解XDD

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cassert>
using namespace std;

#define LL   long long
#define ld   long double
#define pii  pair<int,int>
#define pLL  pair<LL,LL>
#define vint vector<int>
#define vLL  vector<LL>
#define vpii vector<pii>

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define MP make_pair
#define PB push_back

#define Si(x) scanf("%d",&(x));
#define Sii(x,y) scanf("%d %d",&(x),&(y));
#define Siii(x,y,z) scanf("%d %d %d",&(x),&(y),&(z));
#define Siiii(x,y,z,w) scanf("%d %d %d %d",&(x),&(y),&(z),&(w));
#define Siiiii(x,y,z,w,a) scanf("%d %d %d %d %d",&(x),&(y),&(z),&(w),&(a));
#define Siiiiii(x,y,z,w,a,b) scanf("%d %d %d %d %d %d",&(x),&(y),&(z),&(w),&(a),&(b));
#define SL(x) scanf("%lld",&(x));
#define SLL(x,y) scanf("%lld %lld",&(x),&(y));
#define SLLL(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));
#define SLLLL(x,y,z,w) scanf("%lld %lld %lld %lld",&(x),&(y),&(z),&(w));
#define SLLLLL(x,y,z,w,a) scanf("%lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a));
#define SLLLLLL(x,y,z,w,a,b) scanf("%lld %lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a),&(b));

#define Pi(x) printf("%d\n",(x));
#define Pii(x,y) printf("%d %d\n",(x),(y));
#define Piii(x,y,z) printf("%d %d %d\n",(x),(y),(z));
#define Piiii(x,y,z,w) printf("%d %d %d %d\n",(x),(y),(z),(w));
#define Piiiii(a,b,c,d,e) printf("%d %d %d %d %d\n",(a),(b),(c),(d),(e));
#define Piiiiii(a,b,c,d,e,f) printf("%d %d %d %d %d %d\n",(a),(b),(c),(d),(e),(f));
#define PL(x) printf("%lld\n",(x)*1LL);
#define PLL(x,y) printf("%lld %lld\n",(x)*1LL,(y)*1LL);
#define PLLL(x,y,z) printf("%lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL);
#define PLLLL(x,y,z,w) printf("%lld %lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL,(w)*1LL);
#define PLLLLL(a,b,c,d,e) printf("%lld %lld %lld %lld %lld\n",(a)*1LL,(b)*1LL,(c)*1LL,(d)*1LL,(e)*1LL);
#define PLLLLLL(a,b,c,d,e,f) printf("%lld %lld %lld %lld %lld %lld\n",(a)*1LL,(b)*1LL,(c)*1LL,(d)*1LL,(e)*1LL,(f)*1LL);

#define Pi1(x) printf("%d",  (x));
#define PL1(x) printf("%lld",(x));
#define Pspace putchar(' ');
#define Pendl  puts("");

#define MEM0(x) memset( (x), 0, sizeof( (x) ) )
#define MEM1(x) memset( (x),-1, sizeof( (x) ) )
#define REP1(i,n)  for (int i = 1; (n) >= i ; ++i)
#define REP0(i,n)  for (int i = 0; (n) >  i ; ++i)

int myRnd() {
    return abs(  ((rand()<<15) ^ rand()) );
}

int myRnd(int L,int R) {
    return abs(( (rand()<<15)^rand() ) ) % (R-L+1) + L;
}

void Parr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++) {
        printf("%d%c",arr[i]," \n"[i==R]);
    }
}

void Pvec(vint v) {
    for (int i=0;SZ(v)>i;i++) {
        printf("%d%c",v[i]," \n"[i==SZ(v)-1]);
    }
}

void Sarr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++)
    {
        Si(arr[i]);
    }
}

const int N = 1e6 + 6;

int a[N];
int x[N];
int on_x[N];
int y[N];
int on_y[N];
int pre[N],suf[N];
int last[N];

int now_ans;
int pre_cnt[N];
int suf_cnt[N];

bool can[N];

int n;

void add(int L,int R)
{
    L = max(L,1);
    R = min(R,n);
    if (L>R) return;
    for (int i=L;R>=i;i++)
    {
        int now = a[i];
        pre_cnt[now]++;
        if (pre_cnt[now] == 1 && suf_cnt[now]>0 && now > 0) now_ans++;
    }
}

void del(int L,int R)
{
    L = max(L,1);
    R = min(R,n);
    if (L>R) return;
    for (int i=L;R>=i;i++)
    {
        int now = a[i];
        suf_cnt[now]--;
        if (suf_cnt[now] == 0 && pre_cnt[now]>0 && now > 0) now_ans--;
    }
}

int main () {
    //srand(time(NULL));
    int k;
    Sii(n,k);
    Sarr(a,1,n);
    int m,l;
    Sii(m,l);
    //if (m==l && l==1) for(;;);
    REP1(i,m)
    {
        Si(x[i]);
        on_x[ x[i] ] = i;
        can[ x[i] ] = 1;
    }
    REP1(i,l)
    {
        Si(y[i]);
        on_y[ y[i] ] = i;
        can[ y[i] ] = 1;
    }
    REP1(i,m)
    {
        last[i] = -1;
    }
    pre[0] = -1;
    REP1(i,n)
    {
        int now = a[i];
        if (!on_x[now])
        {
            pre[i] = pre[i-1];
            continue;
        }
        int tmpp;
        if (on_x[now] == 1)
        {
            //tmpp = last[1];
            last[1] = i;
        }
        else
        {
            last[ on_x[now] ] = last[ on_x[now]-1 ];
        }
        pre[i] = last[m];
        //if (pre[i] != -1) pre[i]--;
        //if (m == 1) pre[i] = tmpp;
    }
    suf[n+1] = n+1;
    REP1(i,l)
    {
        last[i] = n+1;
    }
    for (int i=n;i>=1;i--)
    {
        int now = a[i];
        if (!on_y[now])
        {
            suf[i] = suf[i+1];
            continue;
        }
        int tmpp;
        if (on_y[now] == 1)
        {
            //tmpp = last[1];
            last[1] = i;
        }
        else
        {
            last[ on_y[now] ] = last[ on_y[now]-1 ];
        }
        suf[i] = last[l];
        //if (suf[i] != n+1) suf[i]++;
        //if (l==1) suf[i] = tmpp;
    }
    REP1(i,n)
    {
        suf_cnt[ a[i] ]++;
    }
    //cout<<"pre = ";Parr(pre,1,n);
    //cout<<"suf = ";Parr(suf,1,n);
    int last_pre = 0,last_suf = 0;
    vint ans;
    for (int i=2;n>i;i++)
    {
        del(last_suf+1,suf[i]);
        //cout<<"last_suf+1 = "<<last_suf+1<<" , suf = "<<suf[i+1]<<endl;
        last_suf = suf[i];
        add(last_pre+1,pre[i]-1);
        //cout<<"last_pre + 1 = "<<last_pre+1<<" , pre = "<<pre[i-1]<<endl;
        last_pre = pre[i]-1;
        if (a[i] == x[m] && now_ans != 0)
        {
            ans.PB(i);
        }
        //cout<<"i = "<<i<<" , now_ans = "<<now_ans<<endl;
    }
    Pi(SZ(ans));
    Pvec(ans);
}