题意：给出一个矩阵，每个位置有个时间点，每个时间点最多只能按10个位置，问可不可满足每个时间点的位置都被按时按到。
分析：直接模拟。
1 /*************************************** 2 * File Name:219a.cpp 3 * Author:`Wind 4 * mail:809098085@qq.com 5 * Created Time:2013年12月13日 22:00:51 6 ***************************************/ 7 #include <map> 8 #include <cmath> 9 #include <queue> 10 #include <string> 11 #include <cstdio> 12 #include <cstring> 13 #include <algorithm> 14 using namespace std; 15 16 char g[6][6]; 17 int ti[11]; 18 int main(){ 19 int k; 20 while (scanf("%d",&k)!=EOF){ 21 memset(ti, 0, sizeof(ti)); 22 for (int i=0; i<4; i++){ 23 scanf("%s",g[i]); 24 for (int j=0; j<4; j++){ 25 if (g[i][j] !='.'){ 26 ti[g[i][j]-'0']++; 27 } 28 } 29 } 30 int flag = 1; 31 for (int i=0; i<10; i++){ 32 if (2*k < ti[i]) 33 flag = 0; 34 } 35 if (flag)printf("YES "); 36 else printf("NO "); 37 } 38 return 0; 39 }
题意：每次给出三个整数 w (1 ≤ w ≤ 1016), m (1 ≤ m ≤ 1016), k (1 ≤ k ≤ 109). 要从整数m开始向后尽可能多的扩充连续的序列，每次扩充的代价为
s(n) = len(n)*k, len(n) 表示整数 n 的长度。
分析：二分枚举扩充序列的最后一个整数，计算出这段区间内1的个数num，如果num <= w/k 则满足题意。
/*************************************** * File Name:219b.cpp * Author:`Wind * mail:809098085@qq.com * Created Time:2013年12月13日 22:44:57 *************************************/ #include <map> #include <cmath> #include <queue> #include <string> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; long long w, m, k; long long bit[20]; void init(){ bit[1] = 1; for (int i=2; i<=17; i++){ bit[i] = bit[i-1] * 10; } } long long len(long long x){ long long tt = 0; while (x){ tt += 1; x /= 10; } return tt; } long long cal(long long x){ long long ll; long long tot = 0; while (x >= m){ ll = len(x); long long tmp = max(bit[ll], m); tot += (x-tmp+1) * ll; x = tmp-1; } return tot; } void solve(){ long long res = m-1; long long l = m, r = 100000000, mid; r *= r; r *= 16; while (l <= r){ mid = (l + r) / 2; if (cal(mid) <= w/k){ l = mid+1; res = mid; } else r = mid-1; } printf("%I64d ",res-m+1); } int main(){ init(); while (scanf("%I64d %I64d %I64d",&w,&m,&k)!=EOF){ solve(); } return 0; }
题意：每次给出一个整数 n (1 ≤ n ≤ 5·105)，表示袋鼠的数量，接下来一行n个整数si(1 ≤ si ≤ 105)表示每个袋鼠袋子的大小，要求是如果一个袋鼠的袋子
的2倍不超过另一个袋鼠袋子的大小，那么就可以将这个袋鼠放在大袋子的那个袋鼠袋子里，每个袋鼠只能装一只袋鼠，只能装袋子是空的袋鼠，问最少
能让多少只袋鼠露在外面。
分析： 排序，双指针，从中间开始枚举，前一半的袋鼠只用作是被装的，后一半的只用做装别的袋鼠的。
/*************************************** * File Name:219c.cpp * Author:`Wind * mail:809098085@qq.com * Created Time:2013年12月14日 7:12:36 ***************************************/ #include <map> #include <cmath> #include <queue> #include <string> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 500005; int a[maxn]; int main(){ int n; while (scanf("%d",&n)!=EOF){ for (int i=0; i<n; i++){ scanf("%d",&a[i]); } sort(a, a+n); int res = 0; int cnt = n-1; for (int i=n/2-1; i>=0; i--){ if (a[i] * 2 <= a[cnt]){ cnt--; } } printf("%d ",cnt+1); } return 0; }
题意：每次给出三个整数 n, m and q (1 ≤ n, m ≤ 40, 1 ≤ q ≤ 3·105)，表示方格阵的大小，grid中只含有0或1，规定0是白色，1是黑色，白色的矩形是指
某个子矩阵中每个元素都是0，q个询问，(x1,y1) (x2,y2) 分别表示矩阵的左下角和右上角，问该子矩阵中有多少个白色矩形。
分析：还没理解，找个代码先慢慢研究。
#include <cstdio> char a[50][50]; int s[50][50],f[50][50][50],g[50][50][50],ans[50][50][50][50]; inline bool check(int x0,int y0,int x1,int y1) { int sum=s[x1][y1]-s[x0-1][y1]-s[x1][y0-1]+s[x0-1][y0-1]; return(sum==(x1-x0+1)*(y1-y0+1)); } int main() { int n,m,Q; scanf("%d%d%d",&n,&m,&Q); for (int i=1;i<=n;i++) scanf("%s",a[i]+1); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+(a[i][j]=='0'); for (int x=n;x;x--) for (int y=m;y;y--) { for (int i=x;i<=n;i++) for (int j=y;j<=m;j++) { f[y][i][j]+=check(x,y,i,j); g[y][i][j]=g[y+1][i][j]+f[y][i][j]; } int tmp[50]={0}; for (int i=x;i<=n;i++) for (int j=y;j<=m;j++) { tmp[j]+=g[y][i][j]; ans[x][y][i][j]=ans[x][y][i][j-1]+tmp[j]; } } while (Q--) { int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); printf("%d ",ans[a][b][c][d]); } return(0); }
题意：一条街上将要放烟火，一共有n的烟火燃放点排在一条直线上，相邻距离为1，一共会放m次烟火，知道了每次烟火燃放的时间 ti 和燃放的位置 ai，每次
给出三个整数 n, m, d (1 ≤ n ≤ 150000; 1 ≤ m ≤ 300; 1 ≤ d ≤ n). d 表示每一个单位时间可以移动的距离，每个烟火获得的欢乐值为 bi - |ai - x| ，
起始位置可以任意选择，问最后可以获得的最大欢乐值是多少？
分析：dp[i][j] 表示第 i 个时间点在 j 位置时获得的总最大欢乐值，可以用滚动数组优化空间
dp[i][j] = max(dp[i-1][k]) + val[i][j] , ( j-t*d<= k <= j+t*d )
va[i][j] 表示 在时间点 i 处于 j 位置可以获得的最大欢乐值。
要用单调队列进行优化。