| 题号 | 标题 | 已通过代码 | 题解/讨论 | 通过率 | 团队的状态 |
|---|---|---|---|---|---|
| A | All-one Matrices | 点击查看 | 进入讨论 | 686/3129 | 通过 |
| B | Beauty Values | 点击查看 | 进入讨论 | 936/2199 | 通过 |
| C | CDMA | 点击查看 | 进入讨论 | 777/1263 | 通过 |
| D | Distance | 点击查看 | 进入讨论 | 157/1023 | 已补 |
| E | Explorer | 点击查看 | 进入讨论 | 311/1650 | 未通过 |
| F | Flower Dance | 点击查看 | 进入讨论 | 33/224 | 未通过 |
| G | Gemstones | 点击查看 | 进入讨论 | 954/2220 | 通过 |
| H | How Many Schemes | 点击查看 | 进入讨论 | 23/112 | 未通过 |
| I | Inner World | 点击查看 | 进入讨论 | 56/224 | 未通过 |
| J | Just Jump | 点击查看 | 进入讨论 | 240/1242 | 未通过 |
A
单调栈+前缀和
#include <bits/stdc++.h>
using namespace std;
const int N = 3100;
char s[N][N];
int sum[N][N];
int d[N],n,m,top;
pair<int,int> st[N];
#define fi first
#define se second
long long ans;
void popall(int i,int j){while(top){if(st[top].se <= j){ans++;}top--;}
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%s",s[i]+1);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){sum[i][j] = sum[i][j-1] + (s[i][j]=='1');}}for(int i=1;i<=n;i++){int last = -1;for(int j=1;j<=m;j++){if(s[i][j] == '0'){d[j] = 0;popall(i,last);if(s[i+1][j] != '1')last = j;continue;}d[j]++;int l = j;while(top && st[top].fi > d[j]){if(st[top].se <= last){ans++;}l = st[top].se;top--;}if(s[i+1][j] != '1')last = j;if(top == 0 || top && st[top].fi < d[j])st[++top] = {d[j],l};}popall(i,last);}cout<<ans<<endl;return 0;
}B
枚举每一位数字的贡献
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long ll;
int a[N],v[N];
ll d[N];
int n;
int main(){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);ll res = 0;for(int i=1;i<=n;i++){d[i] = d[i-1] + i - v[a[i]];v[a[i]] = i;res += d[i];}cout<<res<<endl;return 0;
}C
构造题
比题解思路要绕一点点....大体思路也是递推。
#include <bits/stdc++.h>
using namespace std;
const int N = 1100;
int a[N][N],b[N][N];
int n;
void create(int now,int nxt){for(int i=1;i<=now;i++){for(int j=1;j<=now;j++){b[i][2*j-1] = a[i][j];b[i][2*j] = a[i][j];}}for(int i=1;i<=now;i++){b[now+1][2*i-1] = 1;b[now+1][2*i] = -1;}for(int i=2;i<=now;i++){for(int j=1;j<=now;j++){b[now + i][j*2-1] = b[now+i-1][j*2-1];b[now + i][j*2] = b[now + i - 1][j*2];if(a[i][j] != a[i-1][j]){swap(b[now+i][j*2-1],b[now+i][j*2]);}}}
}
int main(){a[1][1] = 1;a[1][2] = 1;a[2][1] = 1;a[2][2] = -1;scanf("%d",&n);for(int i = 2;i<n;i=i*2){create(i,i*2);swap(a,b);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)printf("%d ",a[i][j]);puts("");}return 0;
}D
知识点：定期重构/三维树状数组
- 法一
对于所有询问，如果不需要更新标记，那么可以用一次bfs求出每个点离最近标记点的距离，询问可以\(O(1)\)回答
对于更新的标记，我们先不更新bfs的结果，而是将他们放到一个队列里面，每次询问可以先拿出bfs预处理结果，然后暴力枚举队列中的新标记更新答案。当队列元素数量超过一个阈值E的时候，就把队列中的标记与已有标记混合，并用bfs预处理每个位置的答案，最后清空队列
可以知道复杂度是\(O(qnmh/E+qE)\),当\(E=\sqrt{nmh}\)时，取到理论最小值。
法二
枚举空间曼哈顿距离的八种情况
- \((x+y+z)-(x_i+y_i+z_i)\)
- \((x+y-z)-(x_i+y_i-z_i)\)
- \((x-y+z)-(x_i-y_i+z_i)\)
- \((x-y-z)-(x_i-y_i-z_i)\)
- \((-x+y+z)-(-x_i+y_i+z_i)\)
- \((-x+y-z)-(-x_i+y_i-z_i)\)
- \((-x-y+z)-(-x_i-y_i+z_i)\)
- \((-x-y-z)-(-x_i-y_i-z_i)\)
每个询问的\(x,y,z\)是确定的，要找的就是后面的表达式最大值。用三维树状数组可以进行维护（维护细节可以参考CDQ分治的天使玩偶一题）
const int inf = 1<<30;
const int N = 300010;
int n,m,h,q;
void getmax(int &a,int b){ if(a < b)a = b;
}
void getmin(int &a,int b){if(a > b)a = b;
}
struct BIT{int a[N];inline int lowbit(int x){return x & -x;}inline int getid(int x,int y,int z){return x * m * h + y * h + z;}void clear(){for(int i=0;i<N;i++)a[i] = -inf;}void add(int x,int y,int z,int val){for (int i = x; i <= n; i += lowbit(i)) {for (int j = y; j <= m; j += lowbit(j)) {for (int k = z; k <= h; k += lowbit(k)) {getmax(a[getid(i, j, k)], val);}}}}int query(int x,int y,int z){int res = -inf;for (int i = x; i; i -= lowbit(i)) {for (int j = y; j; j -= lowbit(j)) {for (int k = z; k; k -= lowbit(k)) {res = max(res, a[getid(i, j, k)]);}}}return res;}
} d[8];int main()
{for(int i=0;i<8;i++)d[i].clear();scanf("%d%d%d%d",&n,&m,&h,&q);int x,y,z,op;while(q--){scanf("%d%d%d%d",&op,&x,&y,&z);if(op == 1){d[0].add(x, y, z, x + y + z);d[1].add(x, y, h - z + 1, x + y - z);d[2].add(x, m - y + 1, z, x - y + z);d[3].add(x, m - y + 1, h - z + 1, x - y - z);d[4].add(n - x + 1, y, z, -x + y + z);d[5].add(n - x + 1, y, h - z + 1, -x + y - z);d[6].add(n - x + 1, m - y + 1, z, -x - y + z);d[7].add(n - x + 1, m - y + 1, h - z + 1, -x - y - z);}else if(op ==2){int ans = inf;getmin(ans,x + y + z - d[0].query(x,y,z));getmin(ans,x + y - z - d[1].query(x,y,h-z+1));getmin(ans,x - y + z - d[2].query(x,m-y+1,z));getmin(ans,x - y - z - d[3].query(x,m-y+1,h-z+1));getmin(ans,-x + y + z - d[4].query(n-x+1,y,z));getmin(ans,-x + y - z - d[5].query(n-x+1,y,h-z+1));getmin(ans,-x - y + z - d[6].query(n-x+1,m-y+1,z));getmin(ans,-x - y - z - d[7].query(n-x+1,m-y+1,h-z+1));printf("%d\n",ans);}}return 0;
}G
用栈更合适一点，场上偏偏用了双链表
#include <bits/stdc++.h>
using namespace std;char s[100005];
int l[100005];
int r[100005];
int pre[100005];
int main() {scanf("%s", s + 1);int len = strlen(s + 1);for(int i = 1; i <= len; i++) {l[i] = i - 1;r[i] = i + 1;pre[i] = 1;}int ans = 0;for(int i = 2; i <= len; i = r[i]) {if(s[i] == s[l[i]]) {pre[i] = pre[l[i]] + 1;if(pre[i] == 3) {ans++;int h = l[l[i]];int t = i;r[l[h]] = r[i];l[r[i]] = l[h];i = l[h];}}}printf("%d\n", ans);return 0;
}
