预计分数 70 + 30 + 60
实际分数 50 + 0 + 60
感觉这套题不错
做题顺序竟然是 T3 T2 T1
通读全篇
感觉T3的30分暴力是送分的，就先写了T3的暴力，然后看数据，模数相同，然后想到用链表可以轻松过60分，lgj竟然用的是莫对%%%%%
T3的30分是一个裸地爆搜，甚至任何剪枝都不需要，轻松些了出来，然而是可以过第一个样例的，第二个样例并没有使，然而0分，
原因是：读题不认真，没有看到各个数字可以重复，然后就GG
T1没有任何思路，然后看到部分分的特征乱搞了50分
总结：读题要认真，多读几遍，不要读错任何条件，要不然就是00000
T1 ci相同，按照高度排序，枚举从每个点开始跳
跳楼的集合 话费有一个 C 的和，与跳楼顺序无关
从低往高 或者 从高往低
从低往高排序，按照高度
hi < h (i+1)
枚举最高的楼和最低的楼
i， j
i + 1, j - 1;
h
没有影响
正解：
f[i][j] 在第i栋楼，已经跳了j栋楼的最小花费
从低的楼到高的楼
f[k][j+1] = min{f[k][j+1], f[i][j] + c[k] + h[k] - h[i]};
找到f[i][j]fit
T2
a1 < a2 < a3 < a4
b1 < b2 < b3 < b4 ...
a1 + a2 = b1
a1 + a3 = b2
a2 + a3 = x;
calc a1 a2 a3
求出后删掉
确定 a2 + a3
枚举 a2 + a3 = b 里面的那个数
找一个数在一个数组中出现过
T3
数据结构题
链表
比较好理解
100 %
对p分块
大于10000时数据没有意义
% 后相同
0， 1， 2， 3，.... p - 1;
总空间 p*n ＴＬＥ
不能对all p预处理
只对 1 <=p <= 100; 预处理，相同于60%
p > 100;
不预处理
每次询问
l， r， p， v；
%p = v
v + k * p;有贡献
k最多到100
v + kp <= 10000;
k<= 100;
枚举这100个数
f[1000][1000]
直接将数值加入数组
先不%p
将两种不同的p分别进行暴力
T1
//std #include <algorithm> #include <cstdio> const int N = 105; struct Building{ int h, c; bool operator<(const Building &x)const{ return h < x.h; } }; Building B[N]; int n, f[N][N]; int main() { freopen("meet.in", "r", stdin); freopen("meet.out", "w", stdout); scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &B[i].c); for (int i = 0; i < n; ++i) scanf("%d", &B[i].h); int T; scanf("%d", &T); std::sort(B, B + n); int ans = 0; for (int i = 0; i < n; ++i) if ((f[1][i] = B[i].c) <= T) ans = 1; for (int i = 2; i <= n; ++i) for (int j = 0, minv = T + 1; j < n; ++j) { if ((f[i][j] = minv + B[j].h + B[j].c) <= T) ans = i; minv = std::min(minv, f[i - 1][j] - B[j].h); } printf("%d ", ans); return 0; }
T2
//30 暴力 #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <map> #define LL long long using namespace std; const int N = 10; int c[N], a[N], imp[20], n; bool vis[N]; int answer, js, sb; struct Node{ int ans[N]; }Ans[N]; map <LL, bool> mp; inline int read() { int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } bool pd() { int tot = 0; for(int i = 1; i < n; i ++) for(int j = i + 1; j <= n; j ++) imp[++ tot] = a[i] + a[j]; sort(imp + 1, imp + sb + 1); for(int i = 1; i <= sb; i ++) if(c[i] != imp[i]) return 0; return 1; } void dfs(int step) { if(step == n + 1) { if(pd()) { int tmp[10]; for(int i = 1; i <= n; i ++) tmp[i] = a[i]; sort(tmp + 1, tmp + n + 1); LL impo = 0; for(int i = 1; i <= n; i ++) impo = impo * 10 + tmp[i]; if(!mp[impo] && impo) { answer ++; for(int i = 1; i <= n; i ++) Ans[answer].ans[i] = tmp[i]; mp[impo] = 1; } } return ; } for(int i = 1; i <= 10; i ++) { if( i >= step) { a[++ js] = i; dfs(step + 1); js --; } } } inline bool cmp(Node a, Node b) { for(int i = 1; i <= n; i ++) if(a.ans[i] > b.ans[i]) return 1; return 0; } int main() { n = read(); double nn = (double) n; double n2 = (nn - 1) / 2; double impe = nn * n2; sb = (int)impe; for(int i = 1; i <= sb; i ++) c[i] = read(); sort(c + 1, c + sb + 1); dfs(1); sort(Ans + 1, Ans + answer + 1, cmp); printf("%d ", answer); for(int i = 1; i <= answer; i ++) { for(int j = 1; j <= n; j ++) printf("%d ", Ans[i].ans[j]); printf(" "); } return 0; } /* 4 3 5 4 7 6 5 */
#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; const int maxn=310; int n,m,res[maxn],ans[maxn][maxn],z[maxn*maxn],cnt; bool use[maxn*maxn]; void check(int p) { memset(use,false,sizeof(use)); if ((z[1]+z[2]+z[p])&1) return; res[1]=(z[1]+z[2]+z[p])/2-z[p]; res[2]=z[1]-res[1]; res[3]=z[2]-res[1]; use[1]=use[2]=use[p]=true; for (int a=4,b=3;a<=n;a++) { while (b<=m && use[b]) b++; if (b>m) return; res[a]=z[b]-res[1]; use[b]=true; for (int c=2;c<a;c++) { if (res[c]>res[a]) return; int v=res[c]+res[a]; int p=lower_bound(z+1,z+m+1,v)-z; if (z[p]!=v) return; int px=p; while (px && z[px]==z[p]) px--; px++; while (px<=m && z[px]==z[p] && use[px]) px++; if (z[px]!=z[p] || use[px]) return; p=px; use[p]=true; } } cnt++; for (int a=1;a<=n;a++) ans[cnt][a]=res[a]; } int main() { freopen("city.in","r",stdin); freopen("city.out","w",stdout); scanf("%d",&n); m=n*(n-1)/2; for (int a=1;a<=m;a++) scanf("%d",&z[a]); sort(z+1,z+m+1); for (int a=3;a<=m;) { check(a); int b=a; while (b<=m && z[b]==z[a]) b++; a=b; } printf("%d ",cnt); for (int a=1;a<=cnt;a++) for (int b=1;b<=n;b++) { printf("%d",ans[a][b]); if (b==n) printf(" "); else printf(" "); } return 0; }
T3
//60分暴力 #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; const int N = 1e5 + 10; int f[N], head[N]; int a[N]; int n, m, now = 1; inline int read() { int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } struct Node{ int u, v, nxt; }E[N]; void add(int u, int v) { E[now].u = u; E[now].v = v; E[now].nxt = head[u]; head[u] = now ++; } int main() { freopen("light.in", "r", stdin); freopen("light.out", "w", stdout); n = read(); m = read(); for(int i = 1; i <= n; i ++) a[i] = read(); if(n <= 1000 && m <= 1000) { for(int i = 1; i <= m; i ++) { int l = read(); int r = read(); int lgj = read(); int v = read(); int answer = 0; for(int j = l; j <= r; j ++) if(a[j] % lgj == v) answer ++; printf("%d ", answer); } return 0; } for(int i = 0; i <= 10000; i ++) head[i] = -1; int impl = read(); int impr = read(); int implgj = read(); int impv = read(); for(int i = 1; i <= n; i ++) a[i] %= implgj; for(int i = 1; i <= n; i ++) add(a[i], i); int ls = 0; for(int i = head[impv]; ~ i; i = E[i].nxt) { int v = E[i].v; if(v >= impl && v <= impr) ls ++; } printf("%d ", ls); for(int i = 2; i <= m; i ++) { int l = read(); int r = read(); int my = read(); int u = read(); int answer = 0; for(int j = head[u]; ~ j; j = E[j].nxt) { int v = E[j].v; if(v >= l && v <= r) answer ++; } printf("%d ", answer); } return 0; } /* 5 2 1 5 2 3 7 1 3 2 1 2 5 3 0 */
//std #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100009; const int maxv = 10000; const int bsz = 100; const int maxb = 103; int n, m; int a[maxn], vb[maxb][maxb], ve[maxb][maxb]; int xb[maxn], xe[maxn]; int i_buf[maxn * maxb * 2], tib; void pre() { memset(ve, 0, sizeof(ve)); memset(xe, 0, sizeof(xe)); for (int i = 1; i <= n; ++ i) ++ xe[a[i]]; for (int i = 0; i <= maxv; ++ i) { xb[i] = tib; tib += xe[i]; xe[i] = xb[i]; } for (int i = 1; i <= n; ++ i) i_buf[xe[a[i]] ++] = i; for (int m = 1; m <= bsz; ++ m) { for (int i = 1; i <= n; ++ i) ++ ve[m][a[i] % m]; for (int i = 0; i < m; ++ i) { vb[m][i] = tib; tib += ve[m][i]; ve[m][i] = vb[m][i]; } for (int i = 1; i <= n; ++ i) i_buf[ve[m][a[i] % m] ++] = i; } } int queryb(int l0, int r0, int p, int k) { if (vb[p][k] == ve[p][k]) return 0; int *x1 = lower_bound(i_buf + vb[p][k], i_buf + ve[p][k], l0); int *x2 = upper_bound(i_buf + vb[p][k], i_buf + ve[p][k], r0); return x2 - x1; } int querys(int v, int l0, int r0) { if (xb[v] == xe[v]) return 0; int *x1 = lower_bound(i_buf + xb[v], i_buf + xe[v], l0); int *x2 = upper_bound(i_buf + xb[v], i_buf + xe[v], r0); return x2 - x1; } int querya(int l0, int r0, int p, int k) { int ans = 0; for (int i = k; i <= maxv; i += p) ans += querys(i, l0, r0); return ans; } int main() { freopen("light.in", "r", stdin); freopen("light.out", "w", stdout); scanf("%d%d", &n, &m); tib = 0; for (int i = 1; i <= n; ++ i) scanf("%d", a + i); pre(); while (m --) { int l, r, p, k; scanf("%d%d%d%d", &l, &r, &p, &k); if (p <= bsz) printf("%d ", queryb(l, r, p, k)); else printf("%d ", querya(l, r, p, k)); } }