弱到一定程度了... 不过还好.又涨经
值和姿势了.....
hdu 4551 生日猜猜猜
月份和日期都比较小, (12,31) 果断暴力, 然后判定下当前月份和天数是否合法.
#include<cstdio> #include<cstdlib> #include<cstring> using namespace std; int day[2][13] = { {0,31,28,31,30,31,30,31,31,30,31,30,31 } ,{0,31,29,31,30,31,30,31,31,30,31,30,31 } }; int gcd(int a,int b){ return b==0?a:gcd(b,a%b); } int lcm(int a,int b){ return a*b/gcd(a,b); } bool key(int y){ if( (y%400==0) || ((y%100!=0)&&(y%4==0)) ) return true; return false; } bool legal(int m, int d, int y){ if( d <= day[ key(y) ][m] ) return true; return false; } int main(){ int T; scanf("%d", &T); for(int Case = 1; Case <= T; Case++){ int x, y, z; scanf("%d%d%d", &x,&y,&z); int cnt = 0, aa,bb; for(int a = 1; a <= 12; a++){ for(int b = 1; b <= 31; b++){ if( (gcd(a,b)==x) && (lcm(a,b)==y) ){ if( legal(a,b,z) ){ cnt++; aa = a, bb = b; } } } } printf("Case #%d: ", Case); if( cnt == 0 ) printf("-1\n"); else if( cnt == 1 ) printf("%d/%02d/%02d\n", z, aa, bb); else puts("1"); } return 0; }
hdu 4552 怪盗基德的挑战书
根据next函数定义, next[i+1]-1 表示 以i位置结尾的后缀所能完全匹配到的最长前缀. 定义dp[i]表示以i位置结尾的的串其前缀(包含子前缀)出现总次数, 则有 dp[i] += dp[ next[i+1]-1 ]. 初始dp[i] = 1,代表 [1,i]作为前缀的串出现了一次. 举例更容易理解点貌似:
index: 1, 2, 3, 4, 5, 6, 7, 8, 9,
letter: a, b, c, a, a, b, c, a, -
next : 0, 1, 1, 1, 2, 2, 3, 4, 5
首先看dp[4],则以[1,4]为前缀串出现的次数, 初始值是1, 因为S(1,4)本身可作为前缀出现. 再看当前串S(1,4) 的最大后缀和最大前缀的长度为, next[5]-1 = 2-1 = 1. 则意味着最大相同前缀为 "a", 换句话说, S(1,4) 除了包含了一个(1,4)的前缀, 还包含了一个 (1,1)的前缀. 所以 dp[4] + dp[1] = 2. 再到 i = 8, 此时串 S(1,8), 其最长前后缀为 next[9]-1 = 4. 其最大相同前后缀为 "abca", 同样的, 其除了包含了一个(1,8)的前缀外, 还包含了一个(1,4)的前缀, "abca", 所以此时以 S[8] 结束的串其前缀出现次数除了初始1外还要加上 dp[4]. 由前面可知 dp[4] = 2, 所以 dp[8] = 1 + dp[4] = 3. 其他类似.
#include<cstdio> #include<cstring> #include<cstdlib> #include<string> #include<algorithm> using namespace std; const int N = (int)1e5+10; int nxt[N], dp[N]; char s[N]; int main(){ while( scanf("%s", s) != EOF){ int i = 0, j = 1; nxt[1] = 0; int ans = 0, len = strlen(s); while( j <= len ){ if( i == 0 || s[i-1] == s[j-1] ) nxt[++j] = ++i; else i = nxt[i]; } ans = 0; dp[0] = 0; for(int i = 1; i <= len; i++) dp[i] = 1; for(int i = 1; i <= len; i++){ if( nxt[i+1] > 1 ) dp[i] += dp[ nxt[i+1]-1 ]; ans += dp[i]; ans %= 256; } printf("%d\n", ans ); } return 0; }
HDU还有个一样的.hdu 3336
hdu 4553 约会安排
果断又涨经验了.... 表示看了别人思路才学会的....越来越渣...
其实挺容易想到用线段书实现区间覆盖, 有三种: 空覆盖(清空), 被DS覆盖, 被NS覆盖. 然后对于三类覆盖有不同查询. 还要求长度.并且满足要求中要最左边的起始下标的. 然后就有点麻烦了....
我们将 空覆盖看作0, DS覆盖看作1, 女神覆盖看做2.
分析下.可以发现 对于NS的查询操作: 若 全 00000满足要求长度的有, 则覆盖全0, 否则看 0101混合是否有满足要求长度. 而对于DS只能看 全0的是否有满足长度要求的. 并且所有查询操作, 若有满足要求的需要返回 最左边的下标. 则我们可以这样来设计查询 操作. 然后再看 需要哪些辅助信息来 维护查询.
int query(int rt,int l,int r,int len,int c){ if( mx[rt][c] < len ) return -1; // mx[rt][c] >= len if( l == r ) return l; int m = (l+r)>>1; push_down(rt,l,r); if( mx[rt<<1][c] >= len ) return query(lch,len,c); else if( conr[rt<<1][c]+conl[rt<<1|1][c] >= len ) return m-conr[rt<<1][c]+1; else if( mx[rt<<1|1][c] >= len ) return query(rch,len,c); return -1; }
若 左子区间 满足要求,则在左边找下去, 否则看左右组合是否满足, 若满足, 则返回下标 M - ConR[ lchild ] + 1. 否则在右子区间查找.
总体是维护一个左连续和, 右连续和. 以及区间最大和. 感脚这题比较神奇的是
1. 转换. 0 表示连续0的, 而1, 表示01混合的.
2. 查询. 设计成 [ x1, M] + [ M+1, x2 ] 这样的形似. 然后下标即为 M-x1+1, 不断细分下去. 不过要特殊处理下, 当查询len=1,而 l == r无法结束,此时l即为所需下标.
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; #define lch rt<<1,l,m #define rch rt<<1|1,m+1,r const int N = (int)1e6+10; int col[N<<2], mx[N<<2][2], conl[N<<2][2],conr[N<<2][2]; void push_up(int rt, int l, int r){ int lc = rt<<1, rc = rt<<1|1, m = (l+r)>>1; for(int i = 0; i < 2; i++){ //left sum if( conl[lc][i] == m-l+1 ) conl[rt][i] = conl[lc][i] + conl[rc][i]; else conl[rt][i] = conl[lc][i]; //right sum if( conr[rc][i] == r-m ) conr[rt][i] = conr[rc][i] + conr[lc][i]; else conr[rt][i] = conr[rc][i]; //max sum mx[rt][i] = max( mx[lc][i], mx[rc][i] ); mx[rt][i] = max( mx[rt][i], conr[lc][i]+conl[rc][i] ); } } void push_down(int rt,int l,int r){ if( l == r ) return; if( col[rt] != -1 ){ int lc = rt<<1, rc = rt<<1|1, m = (l+r)>>1; col[lc] = col[rc] = col[rt]; if( col[rt] == 0 ){ for(int i = 0; i < 2; i++){ mx[lc][i]=conl[lc][i]=conr[lc][i]= m-l+1; mx[rc][i]=conl[rc][i]=conr[rc][i]= r-m; } } else if( col[rt] == 1 ){ for(int i = 0; i < 2; i++){ mx[lc][i]=conl[lc][i]=conr[lc][i]= (i==0)? 0: m-l+1; mx[rc][i]=conl[rc][i]=conr[rc][i]= (i==0)? 0: r-m; } } else{ // col[rt] == 2 for(int i = 0; i < 2; i++){ mx[lc][i]=conl[lc][i]=conr[lc][i]= 0; mx[rc][i]=conl[rc][i]=conr[rc][i]= 0; } } col[rt] = -1; } } void build(int rt,int l,int r){ col[rt] = -1; for(int i = 0; i < 2; i++) mx[rt][i] = conl[rt][i] = conr[rt][i] = r-l+1; if( l == r ) return; int m = (l+r)>>1; build( lch ), build( rch ); } void update(int rt,int l,int r,int a,int b,int c){ if(a <= l && r <= b){ col[rt] = c; if(c == 0){ for(int i = 0; i < 2; i++) mx[rt][i]=conl[rt][i]=conr[rt][i]=r-l+1; }else if(c == 1){ for(int i = 0; i < 2; i++) mx[rt][i]=conl[rt][i]=conr[rt][i]=(i==0)?0:r-l+1; }else{ for(int i = 0; i < 2; i++) mx[rt][i]=conl[rt][i]=conr[rt][i]=0; } return; } push_down(rt,l,r); int m = (l+r)>>1; if(a <= m) update(lch,a,b,c); if(m < b) update(rch,a,b,c); push_up(rt,l,r); } int query(int rt,int l,int r,int len,int c){ if( mx[rt][c] < len ) return -1; // mx[rt][c] >= len if( l == r ) return l; int m = (l+r)>>1; push_down(rt,l,r); if( mx[rt<<1][c] >= len ) return query(lch,len,c); else if( conr[rt<<1][c]+conl[rt<<1|1][c] >= len ) return m-conr[rt<<1][c]+1; else if( mx[rt<<1|1][c] >= len ) return query(rch,len,c); return -1; } int main(){ freopen("1.in","r",stdin); int _; scanf("%d", &_); for(int Case = 1; Case <= _; Case++){ printf("Case %d:\n", Case); int n, m; scanf("%d%d", &n, &m); build( 1, 1, n ); char op[10]; int a, b, len; for(int i = 0; i < m; i++){ scanf("%s",op); if( op[0] == 'D' ){ scanf("%d", &len); int t = query(1,1,n,len,0); if( t == -1 ) puts("fly with yourself"); else{ update(1,1,n, t,t+len-1,1); printf("%d,let's fly\n", t); } } else if( op[0] == 'N'){ scanf("%d", &len); int t = query(1,1,n,len,0); if( t == -1 ){ t = query(1,1,n,len,1); if( t == -1 ) puts("wait for me"); else{ update(1,1,n, t,t+len-1,2); printf("%d,don't put my gezi\n",t); } } else{ update(1,1,n, t,t+len-1,2); printf("%d,don't put my gezi\n",t); } } else{ scanf("%d%d",&a,&b); puts("I am the hope of chinese chengxuyuan!!"); update(1,1,n, a,b,0 ); } } } return 0; }