校試合のテーマ

A best fit ringセグメントツリー+DP
いくつかの点の座標と点の値を与えて、同環の点数を加算して、それから尋ねる時最大値の範囲を与えることを要求して、つまり連続環の値が最大(最大連続サブセグメントと)で、尋ねる過程の中で少しの値の変更があります.
code:

#include <cstdio>
#include <iostream>
#include <algorithm>
typedef struct{
    int dis;
    int v;
    int id;
}Node;
Node p[100001]; //    ，         
int v[100001];  //       ，  ，     
int id[100001]; //        ，           。 
bool cmp(const Node &a, const Node &b)
{
    if ( a.dis <= b.dis )
        return true;
    return false;    
}

typedef struct{
    int lmax, rmax, max, sum;
    int l, r, mid;
}TNode;

TNode tree[400010];
int max(int a, int b)
{
    return (a > b ? a : b);
}
void merge(int i)
{
    int l = i << 1, r = l + 1;
    
    tree[i].sum = tree[l].sum + tree[r].sum;
    
    tree[i].lmax = max(tree[l].lmax, tree[r].lmax + tree[l].sum);
        
    tree[i].rmax = max(tree[r].rmax, tree[l].rmax +tree[r].sum);
    
    tree[i].max = tree[l].rmax + tree[r].lmax;  //          ，        ，       ，      
    if ( tree[i].max < tree[l].max )
        tree[i].max = tree[l].max;
    if ( tree[i].max < tree[r].max )
        tree[i].max = tree[r].max;    
}
void build(int l, int r, int ind)
{
    int mid;
    tree[ind].l = l;
    tree[ind].r = r;
    if ( l == r )
    { 
        tree[ind].max = tree[ind].lmax = tree[ind].rmax = tree[ind].sum = p[l].v;
        return ;    
    }    
    if ( l < r ) //      
    {
        mid = tree[ind].mid = (l + r ) >> 1;
        build(l, mid, ind << 1);
        build(mid+1, r, (ind << 1) + 1);
        merge(ind); //       
    }   
} 

void insert(int l, int r, int ind, int val)
{
    if ( l == tree[ind].l && tree[ind].r == r )
    {
        tree[ind].max = tree[ind].lmax = tree[ind].rmax = tree[ind].sum = p[l].v;
        return ;    
    }        
    int mid = tree[ind].mid;
    if ( l > mid )
    {
        insert(l, r, (ind << 1 ) + 1, val);
    }
    else if ( r <= mid )  //     ，   insert(l, r, ind << 1, val); 
    {
        insert(l, r, ind << 1, val); 
    }
    else
    {
        insert(l, r, ind << 1, val);
        insert(l, r, (ind << 1 ) + 1, val); 
    }   
   
    merge(ind);  
}

int main()
{
    int n;
    int x, y;
    int i;
    int tot;
    int m;
    char str[10];
    while ( scanf("%d", &n ) != EOF )
    {
        for ( i = 1; i <= n; ++i )
        {
            scanf("%d%d%d",&x, &y, &p[i].v);
            p[i].dis = x * x + y * y;
            p[i].id = i;
            v[i] = p[i].v;
        } 
       std::sort(p+1, p+1+n, cmp);

        id[p[1].id] = 1;
        tot = 1;
        
        for ( i = 2; i <= n; ++i )
        {
            if ( p[i].dis == p[i-1].dis)
            {
                p[tot].v += p[i].v;    
            }    
            else
            {
                p[++tot].v = p[i].v;
            }
            id[p[i].id] = tot;
        }
        build(1, tot, 1);
        
        scanf("%d", &m);
        while (m--)
        {
            scanf("%s", str);
          
            if ( str[0] == 'Q')
            {
                printf("%d
", tree[1].max);    
            }
            else
            {
                scanf("%d%d", &x, &y);
                p[id[x]].v = p[id[x]].v - v[x] + y;
                v[x] = y;
                insert(id[x], id[x], 1, y);
            }    
        }
    } 
         
    return 0;    
} 

 
Shortest Path
DP:カエルが川を渡る変種で、時間の要求が厳しい、1 sec.最初は1石で、n石に要求し、最小ステップ数を出力し、出力-1に到達できない.
各石にはrの値があり、その石から最も前方に到達できる距離を表す.
連続範囲遍歴の考え方によれば,時間複雑度はO(n)である.
 

#include <cstdio>

int dp[100001];
int a[100001];
int max(int x, int y)
{
    if ( x > y )    return x;
    return y;
}
int main()
{
    int tc;
    int n;
    int i, left ,right, maxright;
    int ans;
    scanf("%d", &tc);
    {
        while(tc--)
        {
            scanf("%d", &n);
            for ( i = 0; i < n; ++i )
                scanf("%d", &a[i]);
            left = 0;
            right = 1;
            for ( ans = 0; ; ++ans)
            {
                if ( left >= right )
                {
                    ans = -1;
                    break;
                }
                if ( left >= n - 1 || n - 1 < right)
                    break;
                maxright = -1;
                for ( i = left; i < right ; ++i )
                    maxright = max(maxright, a[i] + i + 1);
                left = right;
                right = maxright;
            }
            
            printf("%d
", ans);
        }
    }
    return 0;
}
     

 
 
play beans
検索シミュレーション:最初の問題を読み間違えて、自分で生成したスペースの順序を列挙すると思っています.タイトルには列挙順序が限定されており,上から下へ,左から右へ.
私の理解通りにしたいのですが、この問題はどうすればいいですか??

#include <cstdio>
#include <cstring>

int count(int h, int w, char g[][21])
{
    int cnt = 0;
    int i , j;
    for ( i = 0; i < h; ++i )
        for ( j = 0; j < w; ++j )
            if ( g[i][j] != '.' )
                cnt++;
    return cnt;    
}

void dis(int h, int w, char g[][21], int i, int j )
{
    int fang[4][2] = {{0,1},{0,-1}, {1,0},{-1,0}};
    int ii, x, y, c;
    int tag[27];
    int que[27][2];
    for ( ii = 0; ii < 27; ++ii)
        tag[ii] = 0;
    for ( ii = 0; ii < 4; ii++)
    {
        x = i + fang[ii][0];
        y = j + fang[ii][1];
        while ( x >= 0 && x < h && y >=0 && y < w )
        {
            if ( g[x][y] != '.' )
            {
                c = g[x][y] -'A';
                if ( tag[c] )
                {
                    g[x][y] = '.';
                    g[que[c][0]][que[c][1]] = '.';
                }
                else
                {
                    tag[c] = 1;
                    que[c][0] = x;
                    que[c][1] = y;    
                }   
                break; 
            } 
            x += fang[ii][0];
            y += fang[ii][1];
        }
    }       
}
void solve(int h, int w, char g[][21])
{
    int cnt = count(h,w,g);
    char gg[21][21];
    int i , j;

    for ( i = 0; i < h; ++i )
        strcpy(gg[i],g[i]);
    for ( i = 0; i < h; ++i )
    for ( j = 0; j < w; ++j )
        if ( g[i][j] == '.' )
            dis(h, w, gg, i, j);  
    for ( i = 0; i < h; ++i )
        strcpy(g[i],gg[i]);
    if ( cnt == count(h,w,g) )
        return ;
    solve(h,w,g);
}


int main()
{
    char g[21][21];
    int n;
    int i;
    int h, w;
    while (scanf("%d%d", &h, &w) != EOF && h + w)
    {
        for ( i = 0; i < h; ++i )
            scanf("%s", g[i]);
        solve(h,w,g);
        printf("%d
",count(h,w,g));
    }
        
    return 0;
}