HDU 多校第三場

HDU 4628  Pieces

狀態壓縮dp，dp功底還是太弱了

[cpp] 
#include <cstdio>  
#include <iostream>  
#include <cmath>  
#include <cstring>  
# define N 16  
using namespace std; 
//狀態i的二進制中，1表示該位字符存在，0表示不存在  
int dp[1 << N],nice[1 << N]; //dp[i]表示i狀態下，刪除剩余字符需要的最少步數，nice[i]表示狀態i下，他是否是回文  
char str[N]; 
 
void init() { 
    memset(dp,0,sizeof(dp)); 
    memset(nice,0,sizeof(nice)); 
} 
 
int dfs(int n) { 
    if(dp[n] != 0) return dp[n]; 
    int ans = 100; 
    for(int i=n; i>=1; i &= n,i--) {// i & n 則捨去了諸多不能由i轉化到n的狀態  
 
        if(nice[i] && (i|n) == n) { 
            ans = min(ans,dfs(n-i)+1); 
        } 
    } 
    return dp[n] = ans; 
} 
 
int main() { 
    int T; 
    cin >> T; 
    while(T --) { 
        init(); 
        scanf("%s",str); 
        int len = strlen(str); 
        int n = 1 << len; 
        for(int i=0; i<n; i++) { 
            int cnt = 0; char tmp[N]; 
            for(int j=0; j<len; j++) { 
                if((i>>j) & 1)  {//表示i右移j位，末尾是零還是一  
                    tmp[cnt ++] = str[len-1-j]; 
                } 
            } 
            int l,r,flag = 1; 
            for(l=0,r=cnt-1; l<r; l++,r--) { 
                if(tmp[l] != tmp[r]) { 
                    flag = 0; 
                    break; 
                } 
            } 
            if(flag == 1) { 
 
                nice[i] = 1; 
                dp[i] = 1; 
            } 
        } 
        printf("%d\n",dfs(n-1)); 
    } 
    return 0; 
} 

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
# define N 16
using namespace std;
//狀態i的二進制中，1表示該位字符存在，0表示不存在
int dp[1 << N],nice[1 << N]; //dp[i]表示i狀態下，刪除剩余字符需要的最少步數，nice[i]表示狀態i下，他是否是回文
char str[N];

void init() {
    memset(dp,0,sizeof(dp));
    memset(nice,0,sizeof(nice));
}

int dfs(int n) {
    if(dp[n] != 0) return dp[n];
    int ans = 100;
    for(int i=n; i>=1; i &= n,i--) {// i & n 則捨去了諸多不能由i轉化到n的狀態

        if(nice[i] && (i|n) == n) {
            ans = min(ans,dfs(n-i)+1);
        }
    }
    return dp[n] = ans;
}

int main() {
    int T;
    cin >> T;
    while(T --) {
        init();
        scanf("%s",str);
        int len = strlen(str);
        int n = 1 << len;
        for(int i=0; i<n; i++) {
            int cnt = 0; char tmp[N];
            for(int j=0; j<len; j++) {
                if((i>>j) & 1)  {//表示i右移j位，末尾是零還是一
                    tmp[cnt ++] = str[len-1-j];
                }
            }
            int l,r,flag = 1;
            for(l=0,r=cnt-1; l<r; l++,r--) {
                if(tmp[l] != tmp[r]) {
                    flag = 0;
                    break;
                }
            }
            if(flag == 1) {

                nice[i] = 1;
                dp[i] = 1;
            }
        }
        printf("%d\n",dfs(n-1));
    }
    return 0;
}

HDU 4630 No Pain No Game

思路： 考慮從左到右掃描，對於每個數，記錄在它之前出現，並且最靠右邊的那個它的倍數，用previ表示。考慮當前數i的所有約數x，對於所有r >= i,l <= previ 的詢問，x就是可能的答案了。

用樹狀數組或者線段樹維護（此題線段樹速度巨慢）因為n只有5W，可以預處理好倍數約數關系

[cpp] 
#include <cstdio>  
#include <iostream>  
#include <cmath>  
#include <algorithm>  
#include <vector>  
#include <cstring>  
# define MAX 51111  
# define ll(x) x << 1  
# define rr(x) x << 1 | 1  
using namespace std; 
 
inline void RD(int &ret) { 
    char c; 
    do { 
        c = getchar(); 
    } while(c < '0' || c > '9') ; 
    ret = c - '0'; 
    while((c=getchar()) >= '0' && c <= '9') 
        ret = ret * 10 + ( c - '0' ); 
} 
 
inline void OT(int a){ 
    if(a >= 10)OT(a / 10) ; 
    putchar(a % 10 + '0') ; 
} 
int a[MAX],pos[MAX],print[MAX]; 
struct node { 
    int l,r; 
    int num; 
}ask[MAX]; 
 
struct Node { 
    int s,e,next; 
}v[1111111]; 
int head[MAX]; 
int n,q,num = 0; 
 
void addedge(int s,int e) { 
    v[num].s = s; 
    v[num].e = e; 
    v[num].next = head[s]; 
    head[s] = num++; 
} 
 
void init() { //預處理  
    memset(head,-1,sizeof(head)); 
    for(int i=1; i<=50000; i++) { 
        for(int j=i; j<=50000; j+=i) { 
           addedge(j,i); 
        } 
    } 
} 
 
bool cmp(node a,node b) { 
    return a.r < b.r; 
} 
 
struct Tree { 
    int l,r,maxx,add,mid; 
}tree[MAX*4]; 
 
void up(int x) { 
    tree[x].maxx = max(tree[ll(x)].maxx,tree[rr(x)].maxx); 
} 
 
void down(int x) { 
    if(tree[x].add != 0) { 
        tree[ll(x)].add = max(tree[x].add,tree[ll(x)].add); 
        tree[rr(x)].add = max(tree[x].add,tree[rr(x)].add); 
        tree[ll(x)].maxx = max(tree[x].add,tree[ll(x)].maxx); 
        tree[rr(x)].maxx = max(tree[x].add,tree[rr(x)].maxx); 
        tree[x].add = 0; 
    } 
} 
 
void build(int l,int r,int x) { 
    tree[x].l = l; 
    tree[x].r = r; 
    tree[x].mid = (l+r) >> 1; 
    tree[x].maxx = 0; 
    tree[x].add = 0; 
    if(l == r) return ; 
    build(l,tree[x].mid,ll(x)); 
    build(tree[x].mid+1,r,rr(x)); 
} 
 
void update(int l,int r,int x,int t) { 
    if(l <= tree[x].l && r >= tree[x].r) { 
        tree[x].add = max(t,tree[x].add); 
        tree[x].maxx = max(tree[x].maxx,tree[x].add); 
        return ; 
    } 
    down(x); 
    if(r <= tree[x].mid) update(l,r,ll(x),t); 
    else if(l > tree[x].mid) update(l,r,rr(x),t); 
    else { 
        update(l,tree[x].mid,ll(x),t); 
        update(tree[x].mid+1,r,rr(x),t); 
    } 
    up(x); 
} 
 
int query(int l,int x) { 
    if(tree[x].l == tree[x].r) { 
        return tree[x].maxx; 
    } 
    down(x); 
    if(l > tree[x].mid) return query(l,rr(x)); 
    else return query(l,ll(x)); 
} 
int main() { 
    int T; 
    cin >> T; 
    init(); 
    while( T--) { 
        RD(n); 
        build(1,n,1); 
        memset(pos,0,sizeof(pos)); 
        for(int i=1; i<=n; i++) RD(a[i]); 
        RD(q); 
        for(int i=1; i<=q; i++) { 
            RD(ask[i].l); 
            RD(ask[i].r); 
            ask[i].num = i; 
        } 
        sort(ask+1,ask+1+q,cmp); 
        int cnt = 1,flag = 0; 
        for(int i=1; i<=n; i++) { 
            for(int j=head[a[i]]; j != -1; j = v[j].next) { 
                int t = v[j].e; 
                if(pos[t] != 0) update(1,pos[t],1,t); 
                pos[t] = i; 
            } 
            while(ask[cnt].r <= i) { 
               print[ask[cnt].num] = query(ask[cnt].l,1); 
                cnt++; 
                 if(cnt > q) { 
                    flag = 1; 
                    break; 
                 } 
            } 
            if(flag) break; 
        } 
        for(int i=1; i<=q; i++) OT(print[i]),puts(""); 
    } 
    return 0; 
} 

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstring>
# define MAX 51111
# define ll(x) x << 1
# define rr(x) x << 1 | 1
using namespace std;

inline void RD(int &ret) {
    char c;
    do {
        c = getchar();
    } while(c < '0' || c > '9') ;
    ret = c - '0';
    while((c=getchar()) >= '0' && c <= '9')
        ret = ret * 10 + ( c - '0' );
}

inline void OT(int a){
    if(a >= 10)OT(a / 10) ;
    putchar(a % 10 + '0') ;
}
int a[MAX],pos[MAX],print[MAX];
struct node {
    int l,r;
    int num;
}ask[MAX];

struct Node {
    int s,e,next;
}v[1111111];
int head[MAX];
int n,q,num = 0;

void addedge(int s,int e) {
    v[num].s = s;
    v[num].e = e;
    v[num].next = head[s];
    head[s] = num++;
}

void init() { //預處理
    memset(head,-1,sizeof(head));
    for(int i=1; i<=50000; i++) {
        for(int j=i; j<=50000; j+=i) {
           addedge(j,i);
        }
    }
}

bool cmp(node a,node b) {
    return a.r < b.r;
}

struct Tree {
    int l,r,maxx,add,mid;
}tree[MAX*4];

void up(int x) {
    tree[x].maxx = max(tree[ll(x)].maxx,tree[rr(x)].maxx);
}

void down(int x) {
    if(tree[x].add != 0) {
        tree[ll(x)].add = max(tree[x].add,tree[ll(x)].add);
        tree[rr(x)].add = max(tree[x].add,tree[rr(x)].add);
        tree[ll(x)].maxx = max(tree[x].add,tree[ll(x)].maxx);
        tree[rr(x)].maxx = max(tree[x].add,tree[rr(x)].maxx);
        tree[x].add = 0;
    }
}

void build(int l,int r,int x) {
    tree[x].l = l;
    tree[x].r = r;
    tree[x].mid = (l+r) >> 1;
    tree[x].maxx = 0;
    tree[x].add = 0;
    if(l == r) return ;
    build(l,tree[x].mid,ll(x));
    build(tree[x].mid+1,r,rr(x));
}

void update(int l,int r,int x,int t) {
    if(l <= tree[x].l && r >= tree[x].r) {
        tree[x].add = max(t,tree[x].add);
        tree[x].maxx = max(tree[x].maxx,tree[x].add);
        return ;
    }
    down(x);
    if(r <= tree[x].mid) update(l,r,ll(x),t);
    else if(l > tree[x].mid) update(l,r,rr(x),t);
    else {
        update(l,tree[x].mid,ll(x),t);
        update(tree[x].mid+1,r,rr(x),t);
    }
    up(x);
}

int query(int l,int x) {
    if(tree[x].l == tree[x].r) {
        return tree[x].maxx;
    }
    down(x);
    if(l > tree[x].mid) return query(l,rr(x));
    else return query(l,ll(x));
}
int main() {
    int T;
    cin >> T;
    init();
    while( T--) {
        RD(n);
        build(1,n,1);
        memset(pos,0,sizeof(pos));
        for(int i=1; i<=n; i++) RD(a[i]);
        RD(q);
        for(int i=1; i<=q; i++) {
            RD(ask[i].l);
            RD(ask[i].r);
            ask[i].num = i;
        }
        sort(ask+1,ask+1+q,cmp);
        int cnt = 1,flag = 0;
        for(int i=1; i<=n; i++) {
            for(int j=head[a[i]]; j != -1; j = v[j].next) {
                int t = v[j].e;
                if(pos[t] != 0) update(1,pos[t],1,t);
                pos[t] = i;
            }
            while(ask[cnt].r <= i) {
               print[ask[cnt].num] = query(ask[cnt].l,1);
                cnt++;
                 if(cnt > q) {
                    flag = 1;
                    break;
                 }
            }
            if(flag) break;
        }
        for(int i=1; i<=q; i++) OT(print[i]),puts("");
    }
    return 0;
}