【牛客网】2018年湘潭大学程序设计竞赛 全题解

题解"/>

【牛客网】2018年湘潭大学程序设计竞赛 全题解

比赛链接

A:时间统计

给出两个时间求差值

因为结果不会超longlong直接乱来

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<cmath>
#include<stack>
#include<iomanip>
#include<functional>
using namespace std;
const int maxn = (int)(1e5) + 10;
const int BN = 30;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-6;
typedef long long LL;
typedef unsigned long long ull;
int main() {int T;scanf("%d", &T);while (T--) {LL d, h, m, s;scanf("%lldday%lld:%lld:%lld", &d, &h, &m, &s);LL ans1 = s + m * 60 + h * 3600 + d * 86400;scanf("%lldday%lld:%lld:%lld", &d, &h, &m, &s);LL ans2 = s + m * 60 + h * 3600 + d * 86400;printf("%lld\n", ans2 - ans1);}return 0;
}

B:String

给出一个标准的矩阵，现在有一个字符串S，对于标准矩阵来说，一行（或者一列）的权值为这一行（或列）中与S中相同字符的个数（不是种类数）。现在要输出最大权值的行和列的交点的字符。

这题难点就读题，匹配不会超时乱搞吧。

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<cmath>
#include<stack>
#include<iomanip>
#include<functional>
using namespace std;
const int maxn = (int)(1e5) + 10;
const int BN = 30;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-6;
typedef long long LL;
typedef unsigned long long ull;
char ori[10][10] = {"012345","6789AB","CDEFGH","IJKLMN","OPQRST","UVWXYZ"
};
int ccol[10], crow[10];
char s[550];
int main() {int T;scanf("%d", &T);while (T--) {scanf("%s", s);int len = strlen(s), maxc = 0, maxr = 0;memset(ccol, 0, sizeof(ccol));memset(crow, 0, sizeof(crow));for (int i = 0; i < 6; i++) {for (int j = 0; j < 6; j++) {for (int k = 0; k < len; k++) {if (ori[i][j] == s[k]) {ccol[i]++;crow[j]++;maxc = max(maxc, ccol[i]);maxr = max(maxr, crow[j]);}}}}string ans;for (int i = 0; i < 6; i++) {for (int j = 0; j < 6; j++) {if (ccol[i] == maxc&&crow[j] == maxr) {ans.push_back(ori[i][j]);}}}cout << ans << endl;}return 0;
}

C:Boom

提炼为给出n个矩形问他们最多有多少矩形能相交。

因为数据量很小，可以直接对这个坐标化为100*100的格子，进行标记。

听说会卡边界（不了解）

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<cmath>
#include<stack>
#include<iomanip>
#include<functional>
using namespace std;
const int maxn = (int)(1e5) + 10;
const int BN = 30;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-6;
typedef long long LL;
typedef unsigned long long ull;
int mark[111][111];
int main() {int T;scanf("%d", &T);while (T--) {int n;scanf("%d", &n);int a, b, c, d;memset(mark, 0, sizeof(mark));for (int i = 0; i < n; i++) {scanf("%d%d%d%d", &a, &b, &c, &d);for (int j = a; j < c; j++) {for (int k = b; k < d; k++) {mark[j][k]++;}}}int ans = 0;for (int i = 0; i <= 100; i++) {for (int j = 0; j <= 100; j++) {ans = max(mark[i][j],ans);}}printf("%d\n", ans);}return 0;
}

D:Fibonacci进制

把一个十进制数转化为斐波那契数（不能重复）的和，然后对这个根据这个些斐波那契数是第几项而转化为01串，这里方便表示为斐波那契进制数。

再把这个斐波那契进制数按二进制转化为十进制。要求输出最小答案。

任何一个实数都可以转化为斐波那契数和，所以贪心的从最逼近这个数的斐波那契数分解起一定能得到一个最大的二进制数。

然后就是怎么对这个01串缩小。

由斐波那契数的性质可知fab[i]=fab[i-1]+fab[i-2]。这样分解可以从最高位开始分解使这个二进制数变小，直到不能分解为止。

然而如果只分解一次是不够的，因为低位的分解之后可能产生空位，使高位的也能分解。（不清楚的读者可以看一下样例

这里读者可以考虑用dfs分解，或者直接分解个20次。

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<cmath>
#include<stack>
#include<iomanip>
#include<functional>
using namespace std;
const int maxn = 2*(int)(1e5) + 10;
const int BN = 30;
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const double eps = 1e-6;
typedef long long LL;
typedef unsigned long long ull;
LL fab[100], t2[100];
void init() {fab[0] = 1, fab[1] = 2;t2[0] = 1, t2[1] = 2;for (int i = 2; i <= 50; i++) {fab[i] = fab[i - 1] + fab[i - 2];t2[i] = t2[i - 1] * 2;}
}
bool vis[50];
int maxp;
int main() {init();int T;scanf("%d", &T);while (T--) {LL x, ans = 0;scanf("%lld", &x);maxp = 0;memset(vis, 0, sizeof(vis));while (x) {int pos = upper_bound(fab, fab + 51, x) - fab;pos--;x -= fab[pos];vis[pos] = 1;maxp = max(maxp, pos);}for (int i = 0; i < 100; i++) {for (int j = maxp; j >= 2; j--) {if (vis[j] && !vis[j - 1] && !vis[j - 2]) {vis[j] = 0;vis[j - 1] = vis[j - 2] = 1;}}}for (int i = 0; i <= maxp; i++)if (vis[i])ans += t2[i];printf("%lld\n", ans);}return 0;
}

E:吃货

现在有n个食物的价格和价值，m个询问自己有多少钱，问买一种食物（只买一次）可以获得的价值最大是多少。

暴力明显不行，可以贪心一下。

当自己有x元时，最大价值一定在价格<=x的食物中找。所以我们可以先对价格排序。

然后对于价格高但是价值比价格低的小的食物，可以把大的价值赋值给价格高的，表示这个价格下实际可以得到的最大价值。

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<cmath>
#include<stack>
#include<iomanip>
#include<functional>
using namespace std;
const int maxn = (int)(1e4) + 10;
const int BN = 30;
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const double eps = 1e-6;
typedef long long LL;
typedef unsigned long long ull;
struct nodes {int wei, val;bool operator<(const nodes&a)const {return wei < a.wei;}
}a[3*maxn];
int main(){int T;scanf("%d", &T);while (T--) {int n, q, x;scanf("%d%d", &n, &q);for (int i = 0; i < n; i++)scanf("%d%d", &a[i].wei, &a[i].val);sort(a, a + n);for (int i = 1; i < n; i++)a[i].val = max(a[i].val, a[i - 1].val);while (q--) {scanf("%d", &x);int l = 0, r = n - 1, ans = 0;while (l <= r) {int mid = (l + r) >> 1;if (a[mid].wei <= x) {ans = a[mid].val;l = mid + 1;}else r = mid - 1;}printf("%d\n", ans);}}return 0;
}

F:maze

走迷宫，不过有单向传送门。

虽然也有人用最短路搞过去的（有必要吗）（其实这里优化用到了最短路dijkstra的堆优化思想，谢谢读者胡夫人的提醒），这还是用bfs吧。

把传送门标记一下，因为是单向的所以存储的时候注意一下。

这里笔者没有试过普通队列能不能过，尽量优先队列吧。

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<cmath>
#include<stack>
#include<iomanip>
#include<functional>
using namespace std;
const int maxn = (int)(1e4) + 10;
const int BN = 30;
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const double eps = 1e-6;
typedef long long LL;
typedef unsigned long long ull;
struct nodes {int x, y, cnt;nodes() {}nodes(int a, int b, int c = 0) :x(a), y(b), cnt(c) {}bool operator<(const nodes&a)const {return cnt > at;}
};
int n, m, k;
vector<nodes> tp[350][350];
char mp[350][350];
int dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 };
nodes st, en;
int vis[350][350];
bool check(int x, int y,int val) {if (x >= n || x < 0 || y >= m || y < 0) return true;if (mp[x][y] == '#'||vis[x][y]<=val) return true;return false;
}
int bfs() {priority_queue<nodes> que;que.push(st);vis[st.x][st.y] = 0;while (!que.empty()) {nodes tmp1 = que.top();que.pop();if (tmp1.x == en.x&&tmp1.y == en.y)return tmp1t;int x = tmp1.x, y = tmp1.y;nodes tmp2;for (int i = 0; i < tp[x][y].size(); i++) {tmp2 = tp[x][y][i];tmp2t = tmp1t + 3;if (tmp2t < vis[tmp2.x][tmp2.y]) {vis[tmp2.x][tmp2.y] = tmp2t;que.push(tmp2);}}for (int i = 0; i < 4; i++) {tmp2 = nodes(x + dx[i], y + dy[i], tmp1t + 1);if (check(tmp2.x, tmp2.y, tmp2t)) continue;vis[tmp2.x][tmp2.y] = tmp2t;que.push(tmp2);}}return -1;
}
int main(){while (~scanf("%d%d%d", &n, &m, &k)) {for (int i = 0; i < n; i++) {scanf("%s", mp[i]);for (int j = 0; j < m; j++) {if (mp[i][j] == 'S')st = nodes(i, j);else if (mp[i][j] == 'T')en = nodes(i, j);tp[i][j].clear();vis[i][j] = inf;}}for (int i = 0; i < k; i++) {int X1, X2, Y1, Y2;scanf("%d%d%d%d", &X1, &Y1, &X2, &Y2);if (mp[X1][Y1] == '#' || mp[X2][Y2] == '#') continue;tp[X1][Y1].push_back(nodes(X2, Y2));}printf("%d\n", bfs());}return 0;
}

G:又见斐波那契

看公式。

显然是矩阵快速幂，和2016沈阳一样，不过这里是i^3。

把初始矩阵弄个出来就行了（填数字游戏）

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<cmath>
#include<stack>
#include<iomanip>
#include<functional>
using namespace std;
const int maxn = 2*(int)(1e5) + 10;
const int BN = 30;
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const double eps = 1e-6;
typedef long long LL;
typedef unsigned long long ull;
int n = 6;
struct matrix {LL p[10][10];matrix operator *(const matrix &a)const {matrix ret;memset(ret.p, 0, sizeof(ret.p));for (int i = 1; i <= n; i++)for (int k = 1; k <= n; k++)if (p[i][k])//当矩阵中0很多时可以加速for (int j = 1; j <= n; j++)ret.p[i][j] = (ret.p[i][j] + p[i][k] * a.p[k][j]) % mod;return ret;}matrix operator ^(const LL &a)const {matrix ret;memset(ret.p, 0, sizeof(ret.p));LL b = a;matrix temp;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++)temp.p[i][j] = p[i][j];ret.p[i][i] = 1;}while (b) {if (b & 1) ret = ret*temp;temp = temp*temp;b >>= 1;}return ret;}
};int main() {matrix ori;ori.p[1][1] = 1, ori.p[1][2] = 1, ori.p[1][3] = 1, ori.p[1][4] = 1, ori.p[1][5] = 1, ori.p[1][6] = 1;ori.p[2][1] = 1, ori.p[2][2] = 0, ori.p[2][3] = 0, ori.p[2][4] = 0, ori.p[2][5] = 0, ori.p[2][6] = 0;ori.p[3][1] = 0, ori.p[3][2] = 0, ori.p[3][3] = 1, ori.p[3][4] = 3, ori.p[3][5] = 3, ori.p[3][6] = 1;ori.p[4][1] = 0, ori.p[4][2] = 0, ori.p[4][3] = 0, ori.p[4][4] = 1, ori.p[4][5] = 2, ori.p[4][6] = 1;ori.p[5][1] = 0, ori.p[5][2] = 0, ori.p[5][3] = 0, ori.p[5][4] = 0, ori.p[5][5] = 1, ori.p[5][6] = 1;ori.p[6][1] = 0, ori.p[6][2] = 0, ori.p[6][3] = 0, ori.p[6][4] = 0, ori.p[6][5] = 0, ori.p[6][6] = 1;int T;scanf("%d", &T);while (T--) {LL n;scanf("%lld", &n);if (n == 1) {printf("1\n");continue;}matrix a;a = ori ^ (n - 1);printf("%lld\n", (a.p[1][1] % mod + a.p[1][3] * 8 % mod + a.p[1][4] * 4 % mod + a.p[1][5] * 2 % mod + a.p[1][6] % mod) % mod);}return 0;
}

F:统计颜色

线段树区间更新，用或运算进行状态压缩（c<=60疯狂暗示压缩）

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<cmath>
#include<stack>
#include<iomanip>
#include<functional>
using namespace std;
const int maxn = 2*(int)(1e5) + 10;
const int BN = 30;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-6;
typedef long long LL;
typedef unsigned long long ull;
struct segment_tree {int left, right;LL sum, lazy;int mid() {return (left + right) >> 1;}
}trees[maxn << 4];
void pushup(int rt) {trees[rt].sum = trees[rt << 1].sum | trees[rt << 1 | 1].sum;
}
void pushdown(int rt) {if (trees[rt].lazy != 0) {trees[rt << 1].lazy = trees[rt << 1].lazy | trees[rt].lazy;trees[rt << 1 | 1].lazy = trees[rt << 1 | 1].lazy | trees[rt].lazy;trees[rt << 1].sum = trees[rt << 1].sum | trees[rt].lazy;trees[rt << 1 | 1].sum = trees[rt << 1 | 1].sum | trees[rt].lazy;trees[rt].lazy = 0;}
}
void btrees(int left, int right, int rt) {trees[rt].left = left, trees[rt].right = right, trees[rt].sum=trees[rt].lazy = 0;if (left == right) {//LL x;//scanf("%lld", &x);//trees[rt].sum = (1LL) << x;return;}int mid = trees[rt].mid();btrees(left, mid, rt << 1);btrees(mid + 1, right, rt << 1 | 1);//pushup(rt);
}
void update(int left, int right, int rt, LL add) {if (left <= trees[rt].left&&right >= trees[rt].right) {trees[rt].lazy = trees[rt].lazy | add;trees[rt].sum = trees[rt].sum | add;return;}pushdown(rt);int mid = trees[rt].mid();if (left <= mid) update(left, right, rt << 1, add);if (right > mid) update(left, right, rt << 1 | 1, add);pushup(rt);
}
LL query(int left, int right, int rt) {if (left <= trees[rt].left&&right >= trees[rt].right)return trees[rt].sum;pushdown(rt);int mid = trees[rt].mid();LL ans = 0;if (left <= mid) ans = ans | query(left, right, rt << 1);if (right > mid) ans = ans | query(left, right, rt << 1 | 1);return ans;
}
int main() {int n, m;while (~scanf("%d%d", &n, &m)) {btrees(1, n, 1);int op, l, r;LL col;for (int i = 0; i < m; i++) {scanf("%d", &op);if (op == 1) {scanf("%d%d%lld", &l, &r, &col);LL x = (1LL) << col;update(l, r, 1, x);}else {scanf("%d%d", &l, &r);LL x = query(l, r, 1);int cnt = 0;while (x) {cnt += x % 2;x /= 2;}printf("%d\n", cnt);}}}return 0;
}