牛客网-“景驰科技杯”2018年华南理工大学程序设计竞赛
题目链接：传送门
B-一级棒
（树-路径压缩）
题意：给出一个n，表示有n个节点0~n，0为根结点，随后给出n-1个数表示第i个节点连接的父节点
再给出一个q，随后q次操作：R u v 表示节点u~v之间的路径被访问的次数加1Eg:5 0 1 1 3 W x 表示请你输出经过x及他的父节点之间这条路被访问的情况
5 若没有被访问过输出"Not yet",若被访问超过2次输出"Many times"
R 2 4 若只被访问过一次输出那次访问的路径端点（Eg：小端点 大端点）
W 3 (输出:2 4）注意：要求输出访问过一次的情况时是输出路径端点（不一定是他和其父节点，试试左边样例）
R 1 2
W 2 (输出:Many times)
W 1 (输出:Not yet)
解法：第一次访问路径u，v，直接对路径中的所有节点都进行访问+1的操作
若访问到被访问过一次的路径时进行对其pre值进行修改为其父节点
（目的：把被访问到第二次的路径都压缩起来，下次不在访问）
若访问到被访问过两次的路径时直接根据其pre的并查集得到压缩路径后的终点（节省时间）
代码如下：
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int maxn = 1e5 + 500;
struct node
{int l, r; //记录第一次访问时的路径端点int dept; //记录该节点所在层数int fa; //记录其父节点int cnt; //对节点的访问次数进行统计（路径压缩后中间节点num最大2）
}tre[maxn];
int pre[maxn];//并查集对树上操作超过2次的操作进行路径压缩处理
int find(int x)
{if (pre[x] == x)return x;return pre[x] = find(pre[x]);
}
void operation(int x, int y)
{int u = x, v = y;//保留u，v（因为恰好是“一级棒的边”时，要回答恰好经过这条边的路径端点）while (u != v){if (tre[u].dept < tre[v].dept)swap(u, v); //先对深度大的进行向上前进操作（保证它们能相遇）tre[u].cnt++;if (tre[u].cnt == 1)tre[u].l = min(x, y), tre[u].r = max(x, y);elsepre[u] = tre[u].fa;u = find(tre[u].fa);}
}
int main()
{int n;while (~scanf("%d", &n)){for (int i = 1; i < n; i++){scanf("%d", &tre[i].fa);tre[i].dept = tre[tre[i].fa].dept + 1;tre[i].cnt = 0;pre[i] = i;}int q, u, v;scanf("%d", &q);char s[2];while (q--){scanf("%s", &s);if (s[0] == 'R'){scanf("%d%d", &u, &v);operation(u, v);}else{scanf("%d", &u);if (tre[u].cnt == 0) printf("Not yet\n");else if (tre[u].cnt == 1)printf("%d %d\n", tre[u].l, tre[u].r);else printf("Many times\n");}}}return 0;
} E-Youhane Assemblerti
（KMP） 题意：给出一个n，随后给你n条字符串（1~n），再给出一个q，表示q次询问，每次询问给出一个u，v，要求返回第u条字符串的后缀字符串和第v条字符串的前缀字符串的最大匹配数（即最大相同个数） 解法：题目保证每个文件只有一组数据而且数据总的字符串长度不会超过3e5，因此每个子串都很短，实际上暴力就可以过（现场数据的确都被暴力过了，然而我用的是KMP）在这里的kmp模板直接返回题目要的答案，不懂可以学一手kmp。 代码如下：#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
const int maxn = 3e5 + 500;
string s[maxn];
int nxt[maxn];
void get_next(int y)
{int len = s[y].length();int i = 0, j = -1;nxt[0] = -1;while (i> n;for (int i = 1; i <= n; i++)cin >> s[i];int q,x,y;cin >> q;while (q--){scanf("%d%d", &x, &y);if (x == y)cout << s[x].length() << endl;elsecout << kmp(x, y) << endl;}return 0;
}
G-Youhane as "Bang Riot"
（暴力剪枝） 题意：给出一个n，随后有2行，第一行n个数表示a[i],第二行n个数表示b[i]，题目想要输出全部a[i]且付出的代价最小，代价公式如下
因此可以选择一次输出一个也可以连续输出几个，只要求最后的代价最小值即可。
解法：正解我觉得是斜率优化DP（本人不怎么会）因此在此的解法为根据题目的数据进行巧妙的剪纸方法，然后直接暴力过。
（因为题目的a[i],b[i]的数据大小为【0，1e3】,因此对cost分析，当a[i]选择单个输出时最大代价为1e6,（在此先定义：sum[i]=a[1]+...+a[i]) )然后当sum[i]-sum[j]>2000时，cost=(2e3-b[i])^2,最小值为1e6，这时候就和单个输出的最大值相同代价了，因此在此可以break。（当然仔细想想感觉，好像有有点出入，因为上面的是单个代价为1e6，下面可能是多个数输出的代价才为1e6，那么2000就只能算是卡出题人数据的最小值吧，不过所幸2000的临界点交上去就ac了，如果不行可以考虑放大些。
代码如下：
#include
#include
#include
#include
#include
#include
#include
#include
#include H-对称与反对称
（水题）
题意：
给出一个N*N的方阵A。构造方阵B,C:使得A = B + C.其中 B为对称矩阵，C为反对称矩阵。
对于方阵S中的任意元素,若(S)ij = (S)ji,则称S为对称矩阵
对于方阵T中的任意元素,若(T)ij = -(T)ji,则称T为反对称矩阵
注意，所有运算在模M意义下。
对于每组数据，将反对称矩阵C在N行中输出；
若不存在解，则输出"Impossible"；
若存在多解，则输出任意解。
解法：比赛时没有留意M为奇数，故Impossible的情况是不存在的，而B，C方正又取值随意（满足条件下）因此，我们只需要在纸上画一个2*2的B，C方正加起来就可以看出A方正和B,C方正的联系，及C方正左对角线上值都是0，其它（Aij+Aji）/2=Bij=Bji，且Cij=Aij-Bij 或Cij=-（Aij-Bij），因此就可以通过A反正消去B方正得到C方正的值。由于题目说所有数据都要在模运算%M下进行，而我们过程中存在除2运算（所以比赛时我们傻傻的写了一波2的逆元ac过去，不过题不用求2的逆元，因为M为奇数，当（Aij+Aji）为奇数时加一个M就可以了）
//注意最终输出的C方正也要%M
代码如下：
#include
#include
#include
#include
using namespace std;
#define ll long long
ll a[1500][1500];
int main()
{ll n, mod;while (~scanf("%lld%lld", &n, &mod)){for (int i = 0; i < n; i++)for (int j = 0; j < n; j++){scanf("%lld", &a[i][j]);if (i == j)a[i][j] = 0;a[i][j] %= mod;}int flag = 0;for (int i = 0; i < n; i++)for (int j = i; j < n; j++){ll tmp = a[i][j] + a[j][i];if (tmp % 2 != 0) tmp += mod;tmp /= 2;a[i][j] -= tmp + mod; a[i][j] %= mod; a[i][j] += mod; a[i][j] %= mod;a[j][i] -= tmp + mod; a[j][i] %= mod; a[j][i] += mod; a[j][i] %= mod;if ((a[i][j]+a[j][i]) % mod != 0)flag = 1;}if (flag)cout << "Impossible" << endl;else{for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)printf("%lld%c", a[i][j], j == n - 1 ? '\n' : ' ');}}return 0;
}
K-小马哥的超级盐水
（折半枚举法）
题意：小马哥有杯盐水，第
杯有
单位的盐和
单位的水。小马哥很无聊，于是他想知道有多少种这
杯盐水的非空子集，倒在一起之后盐和水的比是
解法：折半枚举法，因为是求能组合出的所有情况，因此对于每一杯盐水都只有2种状态，取和不取，但是n_max=35，2^35的运算肯定超时，因此需要进行一波折半操作，对于每n杯盐水，我们分为2份，每份最大的讨论情况为2^18<1e6，因此我们可以先分别处理出2部分的所有组合情况，然后选择小部分中的每个数据到另一份数据中进行二分查找，找到满足组合之后值为x/y的数量即可时间复杂度O（nlogn）（这里的n是枚举所有情况的n，不是题目的n了）
代码如下：
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
const int maxn = 3e5+500;
int n, top1, top2;
ll ans, xx, yy;
struct node
{ll x, y;
}a[maxn];
ll s1[maxn], s2[maxn];
void dfs1(int i,ll x, ll y)
{if (i == n / 2) {s1[top1++] = xx*y - yy*x;return;}dfs1(i + 1, x, y);dfs1(i + 1, x + a[i].x, y + a[i].y);
}
void dfs2(int i,ll x, ll y)
{if (i == n) {s2[top2++] = yy*x - xx*y;return;}dfs2(i + 1, x, y);dfs2(i + 1, x + a[i].x, y + a[i].y);
}
int main()
{int t;scanf("%d", &t);while (t--){scanf("%d%lld%lld", &n, &xx, &yy);for (int i = 0; i < n; i++)scanf("%lld%lld", &a[i].x, &a[i].y);top1 = 0; dfs1(0, 0, 0);top2 = 0; dfs2(n / 2, 0, 0);ans = 0;// x s1.x+s2.x//--- = ------------ => x*s1.y+x*s2.y=y*s1.x+y*s2.x=> x*s1.y-y*s1.x = y*s2.x-x*s2.y// y s1.y+s2.ysort(s2, s2 + top2);for (int i = 0; i < top1; i++)ans += (upper_bound(s2, s2 + top2, s1[i]) - s2) - (lower_bound(s2, s2 + top2, s1[i]) - s2);cout << ans - 1 << endl;}return 0;
} 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！