Rank 449/4376. AC 7/13.
A. World Final? World Cup! (I)
题意
\(A\)队与\(B\)队轮流点球，\(A\)先手，判断\(10\)场内是否有某队必胜，输出该场次，或者输出\(-1\)
思路
对于第 \(i\) 场 \((i \in [0,9])\) ，剩余 \(left=10-i-1\) 场未打。
分开判断\(A\)队和\(B\)队，
对于\(A\)队，还有 \(left/2+(1-i\%2)\) 场；
对于\(B\)队，还有 \(left/2\) 场。
计算差值即可。
时间复杂度：\(O(n)\)
对应AC代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
while(t -- > 0){
int a = 0, b = 0;
char[] in = scanner.next().toCharArray();
int i = 0;
for(;i<10;i++) {
if (i % 2 == 0) a += in[i] - '0';
else b += in[i] - '0';
int left = 10 - i - 1;
if (a > b + left / 2 + (1 - i % 2)) break;
if (b > a + left / 2) break;
}
System.out.println(i != 10 ? i + 1 : -1);
}
}
}很签的题要做快一点
B. World Final? World Cup! (II)
待补充
C. 现在是，学术时间 (I)
题意
每个教授有一篇引用量为 \(a_i\) 的论文，一个教授可发表多篇论文，找出一种分配方式使所有教授的 \(H\) 指数最大。\(H\) 指数定义为使得"该教授发表的所有论文中，有至少 \(H\) 篇论文的引用量大于等于 \(H\) "这一命题成立的最大的 \(H\)。
思路
很容易发现，我们只需升序将文章分配，如果遇到有一篇论文分配不能让 \(h_i\) 增大，那就让另一个教授发表。因为每个教授只有一篇论文，所以论文无处可放的可能只有一个：引用量为 \(0\)。
\(ans=n-cnt_0\)
时间复杂度：\(O(1)\)
对应AC代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
while(t -- > 0){
int n = scanner.nextInt();
int cnt = n;
for(int i=0;i<n;i++) {
int a = scanner.nextInt();
if(a == 0) cnt --;
}
System.out.println(cnt);
}
}
}能贪心就别想着去模拟
D. 现在是，学术时间 (II)
题意
在平面直角坐标系中，给定两个与坐标轴平行的矩形，第一个矩形由对角线上的两点 \((0,0)\) 和 \((x,y)\) 确定，第二个矩形的一个顶点为点 \(P(x_p,y_p)\)。记两矩形的交集面积为 \(S_1\)， 并集面积为 \(S_2\)， 输出 \(\{\frac{S_1}{S_2}\}_{\max}\)。
思路
根据糖水原理，分子小于分母时，分子和分母各加上\(k\)，分式结果变大。
那么，我们只需在每个方向上取交集的最大值，然后计算即可。
时间复杂度：\(O(1)\)
对应AC代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
while(t -- > 0){ //写太乱了，不建议做参考
int x = scanner.nextInt(), y = scanner.nextInt(), xp = scanner.nextInt(), yp = scanner.nextInt();
if(xp <= x && yp <= y){
System.out.println((double) Math.max(Math.max((x - xp) * (y - yp), xp * (y - yp)), Math.max(xp * yp, (x - xp) * yp)) / (x * y));
}else if(xp > x && yp > y){
System.out.println((double) (x * y) / (xp * yp));
}else if(xp > x && yp <= y){
System.out.println(Math.max((double) (x * yp) / (x * y + yp * (xp - x)), (double) (x * (y - yp)) / (x * y + (y - yp) * (xp - x))));
}else{
System.out.println(Math.max((double) (y * xp) / (x * y + xp * (yp - y)), (double) (y * (x - xp)) / (x * y + (x - xp) * (yp - y))));
}
}
}
}猜就完事了
E. 鸡算几何
题意
一根夹角不为 \(180°\) 和 \(360°\) 的 \(L\) 型铁丝，先后给出在平面中的三个点的坐标，判断是否出现了以边为轴的翻转。
思路1
计算四条边和 \(x\) 轴正半轴的夹角，判断较长边是否出现在较短边的顺时针方向。
时间复杂度：\(O(1)?\)
对应AC代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
while(t -- > 0){
int xa = scanner.nextInt(), ya = scanner.nextInt(), xb = scanner.nextInt(), yb = scanner.nextInt(), xc = scanner.nextInt(), yc = scanner.nextInt();
double xd = scanner.nextDouble(), yd = scanner.nextDouble(), xe = scanner.nextDouble(), ye = scanner.nextDouble(), xf = scanner.nextDouble(), yf = scanner.nextDouble();
if(calLen(xa, ya, xb, yb) == calLen(xc, yc, xb, yb)){
System.out.println("NO");
continue;
}
System.out.println(judge(xa, ya, xb, yb, xc, yc) == judge(xd, yd, xe, ye, xf, yf) ? "NO" : "YES");
}
}
//返回较长边是否在较短边的顺时针方向
private static boolean judge(double xd, double yd, double xe, double ye, double xf, double yf){
double de = calLen(xe, ye, xd, yd), ef = calLen(xe, ye, xf, yf);
double dde = calDegree(xe, ye, xd, yd), def = calDegree(xe, ye, xf, yf);
if(de > ef){
if(dde > def){
if(dde - def > 180) return true;
else return false;
}else{
if(def - dde > 180) return false;
else return true;
}
}else {
if(dde > def){
if(dde - def > 180) return false;
else return true;
}else{
if(def - dde > 180) return true;
else return false;
}
}
}
private static double calDegree(double startX, double startY, double endX, double endY){
double tan = Math.atan2(endY - startY, endX - startX) * 180 / Math.PI;
if(tan < 0) tan += 360;
return tan;
}
private static double calLen(double x1, double y1, double x2, double y2){
return Math.sqrt(Math.pow(Math.abs(x1 - x2), 2) + Math.pow(Math.abs(y1 - y2), 2));
}
}思路2
通过叉乘的方式，判断较长边和较短边的位置关系。
时间复杂度：\(O(1)\)
对应AC代码
#include<bits/stdc++.h>
using namespace std;
double calLen(double x1, double y1, double x2, double y2){
return sqrt(pow(abs(x2 - x1), 2) + pow(abs(y2 - y1), 2));
}
double calCross(double x1, double y1, double x2, double y2){
return x1 * y2 - x2 * y1;
}
int main()
{
int t, xa, ya, xb, yb, xc, yc;
double xd, yd, xe, ye, xf, yf;
cin >> t;
while(t --){
cin >> xa >> ya >> xb >> yb >> xc >> yc >> xd >> yd >> xe >> ye >> xf >> yf;
double ab = calLen(xa, ya, xb, yb), bc = calLen(xb, yb, xc, yc),
de = calLen(xd, yd, xe, ye), ef = calLen(xe, ye, xf, yf);
if(ab == bc){
cout << "NO\n";
continue;
}
//叉乘判断的是一个边在另一个边的哪个方向，那我们就需要用长边叉乘短边（或者换过来
if(ab < bc) swap(xa, xc), swap(ya, yc);
if(de < ef) swap(xd, xf), swap(yd, yf);
cout << (calCross(xa - xb, ya - yb, xc - xb, yc - yb)
* calCross(xd - xe, yd - ye, xf - xe, yf - ye) < 0 ? "YES\n" : "NO\n");
}
return 0;
}
L型到底是不是直角呢？
F. 鸡玩炸蛋人
题意
给出一个不一定联通的无向图以及每个点的标记情况。一个符合要求的方案定义为在一个连通块内取两个可以重复的点作为起点和终点，在路上按题给要求做上标记，并不能经过已经做过标记的点。若起点和终点有一个不同即视为方案不同。输出方案数，若无合法方案，输出 \(0\) 。
思路
因为标记后才不能回溯，所以我们完全可以以 \(DFS\) 深度遍历，并在回溯时做上标记。
也就是说，只要起点终点确定，一定能使方案符合要求。
因而，一个连通图的方案数即为 \(pow(cnt，2)\) ，\(cnt\) 为连通图的大小（点的数量）。
根据有标记的连通块个数分三种情况输出答案即可。
时间复杂度：\(O(tnm)\)，\(t\)为连通块数量
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200020;
vector<int> e[N];
int egg[N], n, m;
bool vis[N];
pair<ll, bool> dfs(int root){
if(vis[root]) return {0, false};
vis[root] = true;
ll cnt = 1; //我自己
bool have = egg[root] > 0;
for(int t : e[root]){
auto c = dfs(t);
if(c.second) have = true;
cnt += c.first;
}
return {cnt, have};
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i=0;i<m;i++){
int u, v;
cin >> u >> v;
e[u].emplace_back(v);
e[v].emplace_back(u);
}
for(int i=1;i<=n;i++) cin >> egg[i];
ll tot = 0, cnt, eggCnt = 0;
for(int i=1;i<=n;i++){
if(vis[i]) continue;
auto one = dfs(i);
tot += one.first * one.first;
if(one.second){
eggCnt ++;
cnt = one.first * one.first;
}
}
if(eggCnt == 0) cout << tot << '\n';
else if(eggCnt == 1) cout << cnt << '\n';
else cout << 0 << endl;
}多看看题，这题真的比上一题好做多了
G. 鸡格线
题意
给定数组 \(a\) ，对于 \(m\) 次询问，分成两种操作处理：
输入 \(l\)，\(r\)，\(k\)，对区间 \([l,r]\) 中的所有数字执行 \(k\) 次赋值操作：\(a_i=round(10\sqrt x)\)。
输出所有数字的和
重点
当操作次数 \(k \geq 20\) 时，\(f(x)=x\)，可以根据收敛证明。
思路1
维护一个 \(Set\)，存放剩下需要操作的数，然后暴力即可。
对应AC代码
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), m = scanner.nextInt();
long[] a = new long[n + 1];
long sum = 0;
TreeSet<Integer> left = new TreeSet<>();
for(int i=1;i<=n;i++) {
sum += a[i] = scanner.nextInt();
if(f(a[i]) != a[i]) left.add(i);
}
while(m -- > 0){
int op = scanner.nextInt();
if(op == 1){
int l = scanner.nextInt(), r = scanner.nextInt(), k = scanner.nextInt();
while(true){
Object next = left.higher(l - 1);
if(next == null) break;
int nxt = Integer.parseInt(String.valueOf(next));
if(nxt > r) break;
for(int i=1;i<=Math.min(k, 20);i++){ //最多20次操作即可让x0=f(x0)
sum -= a[nxt];
a[nxt] = f(a[nxt]);
sum += a[nxt];
}
if(a[nxt] == f(a[nxt])) left.remove(nxt);
l = nxt + 1;
}
}else System.out.println(sum);
}
}
private static long f(long x){
return Math.round(Math.sqrt(x) * 10);
}
}思路2
如果 \(l\) 已完成，那么可以用并查集的方式找到一个连通块后面的未完成点，开数组记录完成情况以及完成后连通块指向的点即可。
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 100010;
ll a[N];
int p[N], ne[N];
bool ok[N];
int find(int x) {
return p[x] == x ? x : p[x] = find(p[x]);
}
void merge(int x, int y) {
x = find(x), y = find(y);
p[y] = x;
ne[x] = max(ne[x], ne[y]);
}
ll f(ll x){
return round(sqrt(x) * 10);
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
ll sum = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum += a[i];
ne[i] = i + 1;
p[i] = i;
}
while (m-- > 0) {
int op;
cin >> op;
if (op == 1) {
int l, r, k;
cin >> l >> r >> k;
while (true) {
int nxt = ok[l] ? ne[find(l)] : l;
if (nxt > r) break;
for (int i = 1; i <= min(k, 20); i++) { //最多20次操作即可让x0=f(x0)
sum -= a[nxt];
a[nxt] = f(a[nxt]);
sum += a[nxt];
}
if (a[nxt] == f(a[nxt])) {
ok[nxt] = true;
if (nxt < n && ok[nxt + 1]) merge(nxt, nxt + 1);
if (nxt > 1 && ok[nxt - 1]) merge(nxt, nxt - 1);
}
l = nxt + 1;
}
} else cout << sum << '\n';
}
}思路3
一眼线段树，但我不会写。
对应AC代码
待补充
这题其实难在k
H. 本题主要考察了DFS
题意
一个拼图有 \(n^2\) 块，部分块之间用凸出和缺口固定，缺口面积和凸出面积相等。一块拼图可用 上右下左 边的情况来表现状态，\(0\) 平整，\(1\) 缺口，\(2\) 凸起。给出 \(n^2-1\) 块，输出剩下的那块拼图的成本（\(10-cnt_1+cnt_2\)）。
思路
标题骗人，配对\(1\)和\(2\)即可
时间复杂度：\(O(n)\)
对应AC代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
while(t -- > 0){
int n = scanner.nextInt();
int one = 0, two = 0;
for(int i=0;i<n * n -1;i++){
String s = scanner.next();
for(char each : s.toCharArray()){
if(each == '1') one ++;
else if(each == '2') two ++;
}
}
int need = 10;
if(one < two){
need -= two - one;
}else if(one > two){
need += one - two;
}
System.out.println(need);
}
}
}这题还能做得再快点！
I. 本题也主要考察了DFS
待补充
J. 本题竟也主要考察了DFS
待补充
K. 本题主要考察了dp
题意
构建长为 \(n\)，只有 \(m\) 个 \(1\) 的 \(01\) 字符串，使连续的长度为\(3\)的子区间中满足 \(cnt_1>cnt_0\) 的子区间的数量最小，并输出数量。
思路1
可以证明在 \(100,100,100,...\) 序列的最后插 \(1\) 的情况下数量最小。
那么，我们可以分三种情况：
\(n \geq 3m-2\) 时，\(100\) 排不到结束，数量为 \(0\)。
\(n==m\)，一定只有 \(n - 2\) 个，不能再多了。
我们寻找成对出现的 \(00\) 和 \(0?0\)，可以得到对数为 \(\frac{3}{2}(n-m) + (n-m)\%2 + 1\)，用总对数 \(n-2\) 扣除即可。
时间复杂度：\(O(1)\)
对应AC代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), m = scanner.nextInt();
if(n >= 3 * m - 2){
System.out.println(0);
}else if(n == m){
System.out.println(n - 2);
}else{
System.out.println(n - 1 - (n - m) / 2 * 3 - (n - m) % 2);
}
}
}思路2
根据思路\(1\)的第一句话，模拟建立字符串并遍历统计个数。
时间复杂度：\(O(n)\)
对应AC代码
待补充
思路3
状压\(dp\)可解。
对应AC代码
待补充
来波逆向思维~
L. 本题主要考察了运气
题意
\(5\) 个团体，每个团体 \(4\) 人，对于猜测次数，输出\((\)猜对的数学期望\(-3.45)/0.05\)。
思路
五个团体，\(x=0.2 \times 1 + 0.2 \times 2 + 0.2 \times 3 + 0.4 \times 4=2.8\)；
四个人，\(y=0.25 \times 1+0.25 \times 2 + 0.5 \times 3=2.25\)；
\(ans=32(5.05)\)。
时间复杂度：\(O(1)\)
对应AC代码
import java.util.*;
public class Main {
public static void main(String[] args) {
System.out.println(32);
}
}6遍就猜对了哈哈哈
M. 本题主要考察了找规律
题意
将 \(m\) 份仙贝分给 \(n\) 位朋友。若分给某个好朋友时，还剩 \(x\) 个仙贝，并给了他 \(y\) 个仙贝，那么定义每个朋友的好感度为 \(\frac{y}{x}\)。求出总好感度的最大值。
思路
动态规划，不是找规律！！！
\(dp[i][j]\) 为 目前给了 \(i\) 个人仙贝，总共给了 \(j\) 个仙贝的最大总好感度。
枚举第 \(i\) 个人分到的仙贝数 \(k\)，得到状态转移方程：
\(dp[i][j]=max(dp[i-1][j-k]+\frac{k}{m-(j-k)}),k \leq j\)
时间复杂度：小于\(O(nm^2)\)
对应AC代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), m = scanner.nextInt();
double[][] dp = new double[n + 1][m + 1];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
double max = 0;
for(int k=1;k<=j;k++){
max = Math.max(max, dp[i - 1][j - k] + (double) k / (m - j + k));
}
dp[i][j] = max;
}
}
System.out.println(dp[n][m]);
}
}防诈骗