首页 > 代码库 > Codeforces Round #238 (Div. 1)
Codeforces Round #238 (Div. 1)
感觉这场题目有种似曾相识感觉，C题还没看，日后补上。一定要坚持做下去。
A
Unusual Product
题意：
给定一个n*n的01矩阵，3种操作，
1 i 将第i行翻转
2 i 将第i列翻转
3 询问矩阵第i行和第i列做向量乘法之和。
分析：
分析发现对于3的结果取决于对角线上1的个数num，即num%2，然后就很好做了，对于每次操作，只需要改变该行或该列后，对角线上仍然有多少个1.
代码：
1 #pragma comment(linker, "/STACK:16777216") 2 #include <cstdio> 3 #include <iostream> 4 #include <cstring> 5 #include <queue> 6 #include <vector> 7 #include <cmath> 8 #define inf 0x0f0f0f0f 9 #define in freopen("data.txt", "r", stdin);10 #define pb push_back11 #define bug(x) printf("Line : >>>>%d\n", (x));12 using namespace std;13 typedef unsigned short US;14 typedef long long LL;15 const int maxn = 1111;16 int vis[maxn];17 18 int main(){19 20 int n, q;21 scanf("%d", &n);22 int res = 0;23 for(int i = 0; i< n; i++) for(int j = 0; j < n; j++) {24 int t;25 scanf("%d", &t);26 if(i == j) vis[i] = t, res += t;27 }28 scanf("%d", &q);29 while(q--){30 int t, x;31 scanf("%d", &t);32 if(t != 3){33 scanf("%d", &x);34 vis[x] ^= 1;35 res += (vis[x] ? 1 : -1);36 }37 else{38 cout<<res%2;39 }40 }41 cout<<endl;42 return 0;43 }
B
Toy Sum
题意：
共有1,2,3到10^6这么些个数首先选出n个数，x1~xn，要从剩下的数中选出若干数满足灯饰sum{xi-1| 1 <= i <= n} = sum {s-yi|1 <= i <= m}
分析：
xi-1和s-yi分别表示的数到两端的距离。
那么对于xi如果离s一样的近的数没有被选中则优先选它，如果两端一样近的地方都选取了，先不管它。最后将能够选取的一样近的数都选取完毕后，再针对两端一样近的数都选了的情况，这时候也只要将两端一样近的从没选中的选进Y集合就行了。
上面这样似乎才是标准解法，可是我是dfs暴力求解，加了些剪枝，也能过。
我的代码：
1 #pragma comment(linker, "/STACK:16777216") 2 #include <cstdio> 3 #include <iostream> 4 #include <cstring> 5 #include <bitset> 6 #include <algorithm> 7 #include <queue> 8 #include <vector> 9 #include <cmath>10 #define inf 0x0f0f0f0f11 #define in freopen("data.txt", "r", stdin);12 #define pb push_back13 #define bug(x) printf("Line : >>>>%d\n", (x));14 using namespace std;15 typedef unsigned short US;16 typedef long long LL;17 const int maxn = (int)1e6 + 100;18 LL a[maxn];19 bitset<maxn> vis;20 LL sum[maxn];21 int ok;22 vector<int> ans;23 int s = (int)1e6;24 25 void dfs(int x, LL sm) {26 if(ok) return;27 if(sm == 0) {28 ok = 1;29 return;30 }31 int k = upper_bound(a+1, a+x+1, sm) - a;32 k--;33 for(int i = k; i >= 1 && sum[i] >= sm; i--) {34 ans.pb(s-a[i]);35 dfs(i-1, sm-a[i]);36 if(ok) return;37 ans.pop_back();38 }39 }40 int main() {41 42 int n;43 scanf("%d", &n);44 LL tmp = 0;45 for(int i = 1; i <= n; i++) {46 int u;47 scanf("%d", &u);48 tmp += u-1;49 vis[u] = 1;50 }51 52 // cout<<tmp<<endl;53 int cnt = 0;54 for(int i = s; i >= 1; i--)55 if(vis[i] == 0) {56 a[++cnt] = s-i;57 // if(cnt <= 10)58 // cout<<a[cnt]<<endl;59 sum[cnt] = sum[cnt-1] + s-i;60 }61 vis.reset();62 if(tmp == 0) {63 cout<< 1 <<endl;64 cout<< 1000000 << endl;65 return 0;66 }67 dfs(cnt, tmp);68 printf("%d\n", ans.size());69 70 for(int i = 0; i < ans.size(); i++)71 printf("%d%c", ans[i], i == ans.size()-1 ? ‘\n‘ : ‘ ‘);72 return 0;73 }
D
Hill Climbing
题意：
每座山用一根垂直线段表示，有x，y两种属性，按照x递增给定n座山的xi和yi，每次在第i座山的时候只能够到达在视野范围内（这样说是没有问题的）的最右的一座山，然后两个人分别位于两座山上，问他们分别出发，沿着上面的原则确定的路线转移，直到两者到达同一座山。
分析：
首先要确定没座山能够到达的最右的一座山，除了最右的山没有可到达的山，每座山显然能到达另一座山，可以从右往左扫，建立单调栈，将第i座山与栈顶的斜率k1，栈顶与栈顶以下的一座山的斜率k2比较，如果k1 < k2将栈顶元素出栈。最后第i座山能够到达栈顶那座山，同时将i入栈。
这样会得到一棵树，对于每个询问，只需要询问他们的lca就是了。
注意：倍增法求lca的时候，应该在dfs子树的时候将fa[u][i]更新求出来。
代码：
#pragma comment(linker, "/STACK:16777216")#include <cstdio>#include <iostream>#include <cstring>#include <bitset>#include <algorithm>#include <queue>#include <vector>#include <cmath>#define inf 0x0f0f0f0f#define in freopen("data.txt", "r", stdin);#define pb push_back#define esp 1e-6#define bug(x) printf("Line : >>>>%d\n", (x));using namespace std;typedef unsigned short US;typedef long long LL;const int maxn = (int)1e5 + 100;struct Po { double x, y;} h[maxn];int st[maxn];vector<int> g[maxn];double cal(int x, int y) { return (h[x].y-h[y].y)/(h[x].x-h[y].x);}int fa[maxn][20], dep[maxn];double dblcmp(double x) { if(fabs(x) < esp) return 0; return x > 0 ? 1 : -1;}void dfs(int u, int f) { dep[u] = dep[f] + 1; fa[u][0] = f; for(int i = 1; i < 20; i++) { fa[u][i] = fa[fa[u][i-1]][i-1]; } for(int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if(v == f) continue;// cout<<v<<endl; dfs(v, u); }}int lca(int x, int y) { if(dep[x] < dep[y]) swap(x, y); int d = dep[x]-dep[y]; for(int i = 0; i < 20; i++) if((d &(1<<i))) x = fa[x][i]; if(x != y) { for(int i = 19; i >= 0; i--) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i]; x = fa[x][0]; } return x;}int main() { int n, q; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%lf%lf", &h[i].x, &h[i].y); } int top = 0; for(int i = n; i >= 1; i--) { while(top >= 2 && dblcmp(cal(i, st[top]) - cal(st[top], st[top-1])) < 0) top--; if(top) { g[st[top]].pb(i); g[i].pb(st[top]); } st[++top] = i; } dfs(n, 0); scanf("%d", &q); for(int i = 1; i <= q; i++) { int u, v; scanf("%d%d", &u, &v); printf("%d%c", lca(u, v), i == q ? ‘\n‘ : ‘ ‘); } return 0;}
同样利用单调栈的一道题：HDU 5033 Building
Codeforces Round #238 (Div. 1)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。