就做了签到题.....
菜的掉渣了..都...
A 题....签到题,竟然搞晕了半天...
其实第三种操作, 因为 60*k - (60-x)*k = 0 (mod 43200)
转化成 x*k = 43200*B, 因为是浮点型, 直接求单位的 k = (43200/x)*K*60 s
View Code
#include<stdio.h> #include<stdlib.h> #include<string.h> typedef long long LL; int gcd( int a, int b ){ return b == 0 ? a : gcd( b, a%b ); } int main(){ int T; scanf("%d", &T); while( T-- ){ int Q, x, t, k, op; scanf("%d", &x); scanf("%d", &Q); while( Q-- ){ scanf("%d", &op); if( op == 1 ){ scanf("%d", &t); double ans = 1.*t*(60-x); printf("%.2f\n", ans ); } else if( op == 2 ){ scanf("%d", &t); double ans = 3600.*t/(60-x); printf("%.2f\n", ans ); } else{ scanf("%d", &k); // printf("%I64d.00\n", 1LL*(43200/r)*60*k ); printf("%.2f\n", 86400.0 * 30.0 / x * k ); } } } return 0; }
B 题, 看了觉得是个搜索 3*3...但是状态好麻烦...不敢写...
C 题, 组合数学...情况太多了..无从下手....
岛神解题报告: http://www.shuizilong.com/house/archives/2013%E8%85%BE%E8%AE%AF%E7%BC%96%E7%A8%8B%E9%A9%AC%E6%8B%89%E6%9D%BE%E5%A4%8D%E8%B5%9B%E7%AC%AC%E4%B8%80%E5%9C%BA%EF%BC%883%E6%9C%8829%E6%97%A5%EF%BC%89/
D 题, 看了题目就往 矩形面积并靠...稀里哗啦写了200行...发现对于增长的t..处理时间复杂度O(n*n).果断T...
看到别人线段数,上还有个 二元函数.....跪了...
线段数写法: http://blog.csdn.net/laziercs/article/details/8738504
递推维护等差数列写法: http://paste.ubuntu.com/5658223/
有一篇很详细的讲解思维的 数组维护: http://blog.csdn.net/wh2124335/article/details/8739097
解题思路:
对于点(x,y), 与点(t,t) 形成的矩形,面积公式为: (t-x)*(t-y) => t*t - (x+y)*t + x*y
而对于矩形的四个顶点, 左下角和右上角都是加法, 左上角和右上角都是减法.
所以我们可以把 顶点分成两类,然后预处理, 并且按早 key = Max( x,y )进行排序,
然后对于任意的 t, 我们可以二分查找. 这个题因为t 是升序,所以我们只需要动态维护数组即可.
View Code
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> using namespace std; #define MAX(a,b) (a)>(b)?(a):(b) const int N = 40010; typedef long long LL; struct node{ int x, y, k; bool operator < (node tmp )const{ return k < tmp.k; } }l[N], r[N]; int n, tot; LL s1[2][N],s2[2][N]; int search( node *a, int cnt, int x ){ int L = 0, R = cnt-1, idx = -1; while( L < R ){ printf("L = %d, R = %d, x = %d\n", L, R, x ); int m = (R+L)>>1; if( a[m].k < x ) (idx=m),(L=m+1); else R = m; } printf("idx = %d\n", idx); return idx+1; } void solve(){ int T, t; scanf("%d", &T); int k1 = 0, k2 = 0; while( T-- ){ scanf("%d", &t); while( (k1<tot)&&(l[k1].k < t) ) k1++; while( (k2<tot)&&(r[k2].k < t) ) k2++; LL ans = 0; if( k1 > 0 ) ans += (1LL*k1*t*t - 1LL*t*s1[0][k1-1] + s2[0][k1-1]); if( k2 > 0 ) ans -= (1LL*k2*t*t - 1LL*t*s1[1][k2-1] + s2[1][k2-1]); printf("%I64d\n", ans ); } } int main(){ int T; scanf("%d",&T); while( T-- ){ scanf("%d",&n); int x1, y1, x2, y2; int ln = 0, rn = 0; for(int i = 0; i < n; i++){ scanf("%d%d%d%d",&x1,&y1,&x2,&y2); l[ln].x=x1,l[ln].y=y1,l[ln].k=MAX(x1,y1); ln++; l[ln].x=x2,l[ln].y=y2,l[ln].k=MAX(x2,y2); ln++; r[rn].x=x1,r[rn].y=y2,r[rn].k=MAX(x1,y2); rn++; r[rn].x=x2,r[rn].y=y1,r[rn].k=MAX(x2,y1); rn++; } tot = ln; sort( l, l+tot ); sort( r, r+tot ); for(int i = 0; i < tot; i++){ if( i == 0 ){ s1[0][i] = l[i].x+l[i].y; s1[1][i] = r[i].x+r[i].y; s2[0][i] = 1LL*l[i].x*l[i].y; s2[1][i] = 1LL*r[i].x*r[i].y; } else{ s1[0][i] = s1[0][i-1]+l[i].x+l[i].y; s1[1][i] = s1[1][i-1]+r[i].x+r[i].y; s2[0][i] = s2[0][i-1]+1LL*l[i].x*l[i].y; s2[1][i] = s2[1][i-1]+1LL*r[i].x*r[i].y; } } solve(); } return 0; }
E 题, 看了题就觉得 字符串匹配+DP.. 感觉要AC自动机+DP...又跪了....
加油...加油... 加油翻解题报告....
某大神...
另外附 