http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2427
线段树+离散化 不离散化不知道会不会超时 一直RE 可能N值没有说的那么小吧 题意有问题 按1W开数组就RE 按10W开就A了
View Code
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #include<iostream> 5 using namespace std; 6 #define N 100001 7 int s[N*6],num,f[100011],po[100011][2]; 8 struct node 9 { 10 int li,num; 11 }line[200011]; 12 void build(int l,int r,int w) 13 { 14 s[w] = -1; 15 if(l==r) 16 { 17 return ; 18 } 19 int m = (l+r)/2; 20 build(l,m,2*w); 21 build(m+1,r,2*w+1); 22 } 23 void add(int a,int b,int da,int l,int r,int w) 24 { 25 if(l==a&&b==r) 26 { 27 s[w] = da; 28 return ; 29 } 30 int m = (l+r)/2; 31 if(s[w]>0) 32 { 33 s[2*w] = s[w]; 34 s[2*w+1] = s[w]; 35 s[w] = -1; 36 } 37 if(b<=m) 38 add(a,b,da,l,m,2*w); 39 else 40 if(a>m) 41 add(a,b,da,m+1,r,2*w+1); 42 else 43 { 44 add(a,m,da,l,m,2*w); 45 add(m+1,b,da,m+1,r,2*w+1); 46 } 47 } 48 void search(int l,int r,int w) 49 { 50 if(s[w]>0) 51 { 52 f[s[w]] = 1; 53 return ; 54 } 55 if(l==r) 56 return ; 57 int m = (l+r)/2; 58 search(l,m,2*w); 59 search(m+1,r,2*w+1); 60 } 61 bool cmp(node a,node b) 62 { 63 return a.num<b.num; 64 } 65 int main() 66 { 67 int n,i,j,t,a,b; 68 scanf("%d", &t); 69 while(t--) 70 { 71 memset(f,0,sizeof(f)); 72 num = 0; 73 scanf("%d", &n); 74 build(1,N,1); 75 for(i = 0; i < n ;i++) 76 { 77 scanf("%d%d", &po[i][0],&po[i][1]); 78 line[2*i].li = i+1; 79 line[2*i].num = po[i][0]; 80 line[2*i+1].li = -(i+1); 81 line[2*i+1].num = po[i][1]; 82 } 83 sort(line,line+2*n,cmp); 84 int te = line[0].num,g = 1; 85 for(i = 0 ; i < 2*n ; i++) 86 { 87 if(te!=line[i].num) 88 { 89 te = line[i].num; 90 g++; 91 } 92 if(line[i].li>0) 93 { 94 po[line[i].li][0]=g; 95 } 96 else 97 po[-line[i].li][1]=g; 98 } 99 for(i = 1; i <= n ; i++) 100 { 101 add(po[i][0],po[i][1],i,1,N,1); 102 } 103 search(1,N,1); 104 for(i = 1; i <= n ; i++) 105 if(f[i]) 106 num++; 107 printf("%d\n",num); 108 } 109 return 0; 110 }
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2430
DP 前一个的1或者最高 到这一个1或者最高 中间选一个最优的
View Code
1 #include<iostream> 2 #include<cstdio> 3 #include<string.h> 4 #include<cmath> 5 using namespace std; 6 int main() 7 { 8 int i,j,n,m,x,a[111],k; 9 double dp[111][111]; 10 while(scanf("%d",&n)!=EOF) 11 { 12 memset(dp,0,sizeof(dp)); 13 for(i = 1; i <= n ; i++) 14 scanf("%d",&a[i]); 15 scanf("%d", &k); 16 if(n==1) 17 { 18 printf("0.000000\n"); 19 continue; 20 } 21 for(i = 2; i <= n ; i++) 22 { 23 x = a[i-1]; 24 if(dp[i][1]<dp[i-1][x]+sqrt(k*k+(x-1)*(x-1))) 25 dp[i][1] = dp[i-1][x]+sqrt(k*k+(x-1)*(x-1)); 26 if(dp[i][1]<dp[i-1][1]+k) 27 dp[i][1] = dp[i-1][1]+k; 28 if(dp[i][a[i]]<dp[i-1][x]+sqrt(k*k+(x-a[i])*(x-a[i]))) 29 dp[i][a[i]] = dp[i-1][x]+sqrt(k*k+(x-a[i])*(x-a[i])); 30 if(dp[i][a[i]]<dp[i-1][1]+sqrt(k*k+(a[i]-1)*(a[i]-1))) 31 dp[i][a[i]] = dp[i-1][1]+sqrt(k*k+(a[i]-1)*(a[i]-1)); 32 } 33 if(dp[n][1]>dp[n][a[n]]) 34 printf("%.6lf\n",dp[n][1]); 35 else 36 printf("%.6lf\n",dp[n][a[n]]); 37 } 38 return 0; 39 } 40
http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2429
模拟 这题WA惨了 最后两分钟交对 好险。。
x不能为负值 就算最后有符合的负值也是输出-1 考虑两种情况x为0或者不为0的情况
View Code
1 #include<stdio.h> 2 #include<string.h> 3 int main() 4 { 5 int i,j,n,f[401],m; 6 long long k,a[61],stack[401],b[61]; 7 while(scanf("%d",&n)!=EOF) 8 { 9 int top =200; 10 memset(stack,0,sizeof(stack)); 11 memset(f,0,sizeof(f)); 12 for(i = 1; i <= n ; i++) 13 { 14 scanf("%lld",&a[i]); 15 b[i] = a[i]; 16 } 17 scanf("%lld", &k); 18 for(j = 1; j <= n ; j++) 19 { 20 if(a[j]==-1) 21 a[j]=0; 22 if(a[j]==0) 23 { 24 top--; 25 long long x = stack[top]; 26 top--; 27 x+=stack[top]; 28 stack[top++] = x; 29 } 30 else 31 stack[top++] = a[j]; 32 } 33 top--; 34 if(stack[top]==k) 35 { 36 printf("0\n"); 37 continue; 38 } 39 top = 200; 40 for(j = 1; j <= n ; j++) 41 { 42 if(b[j]==-1) 43 { 44 f[top]=1; 45 stack[top++] = 0; 46 } 47 else 48 if(b[j]==0) 49 { 50 top--; 51 long long x = stack[top]; 52 top--; 53 x+=stack[top]; 54 if(f[top]||f[top+1]) 55 { 56 f[top] = 1; 57 } 58 stack[top++] = x; 59 } 60 else 61 stack[top++] = b[j]; 62 } 63 top--; 64 if(!f[top]&&stack[top]==k) 65 { 66 printf("0\n"); 67 continue; 68 } 69 if(f[top]&&k-stack[top]>0) 70 printf("%lld\n",k-stack[top]); 71 else 72 printf("-1\n"); 73 } 74 return 0; 75 }