Rank 1. AC 4/9.因为11.11为四根棍，所以注定只能写四题
A. 乘方 CSP 2022 T1
题意
比较 \(a ^ b\) 和 \(10 ^ 9\) 的大小关系。
思路1 try-catch
用大数算法直接算，如果算得出来，那就比较；算不出来，也就是溢出了，那么一定是大于 \(1e9\) 的，利用语言特性，捕获这个异常然后输出 \(-1\) 即可。
对应AC代码
import java.math.*;
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
try{
BigInteger a = new BigInteger(scanner.next());
int b = scanner.nextInt();
BigInteger ans = a.pow(b);
if(ans.compareTo(BigInteger.valueOf(1000000000L)) > 0) System.out.println(-1);
else System.out.println(ans);
}catch(Throwable e){
System.out.println(-1); //投机取巧.jpg
}
}
}思路2
很简单，我们只需要循环 \(b\) 次把 \(a\) 乘上自己，判断一下是否大于 \(1e9\) 即可。
对应AC代码
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int a = scanner.nextInt(), b = scanner.nextInt();
long ans = 1L;
for(int i=0;i<b;i++) {
ans *= a;
if(ans > 1000000000L) {
System.out.println(-1);
return;
}
}
System.out.println(ans);
}
}对思路2的优化
可以使用快速幂降低时间复杂度。
注意：可能会爆long long，用大数解。
对应AC代码
import java.math.*;
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
BigInteger weight = BigInteger.valueOf(scanner.nextLong());
int b = scanner.nextInt();
BigInteger ans = BigInteger.ONE;
while(b > 0){
if(b % 2 == 1) { //二进制非递归快速幂
ans = ans.multiply(weight);
if(ans.compareTo(BigInteger.valueOf(1000000000L)) > 0) {
System.out.println(-1);
return;
}
}
weight = weight.multiply(weight); //这里在测试点9会爆long
b >>= 1;
}
System.out.println(ans);
}
}怎么能叫投机取巧呢（
B. 解密 CSP 2022 T2
题意
对于方程组 \(n = p q\) , \(ed = (p - 1) (q - 1) + 1\)，给定 \(n, d, e\)，解方程并输出 \(p, q\)。
思路
化简第二个式子得到 \(p + q = n - e d + 2\)，设其为 \(m\).
由第一个式子得到 \(p = \frac{n}{q}\).
由1和2，\(\frac{n}{q} + q = m \rightarrow q ^ 2 - m q + n = 0\).
求 \(\Delta = m ^ 2 - 4 n\)，\(\Delta < 0\) 即为无解的第一种情况.
运用求根公式求出 \(p, q\)，\(p\) 和 \(q\) 不为整数为无解的第二种情况，为整数就输出.
注意点：
肉眼可见会爆 \(int\)，用长整型.
不要用 \(java\)，会 \(tle\).
对应AC代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int k;
long long n, d, e;
scanf("%d", &k);
for(int w=0;w<k;w++){
scanf("%lld %lld %lld", &n, &d, &e);
long long m = n + 2 - e * d;
long long delta = m * m - 4 * n;
if(delta < 0) printf("NO\n");
else {
double p = (m - sqrt(delta)) / 2, q = (m + sqrt(delta)) / 2;
if((int) p != p || (int) q != q) printf("NO\n");
else printf("%d %d\n", (int) p, (int) q);
}
}
}简简单单数学题
C. 报数 NOIP 2021 提高组
题意
某数字为 \(x\) 的倍数， \(x\) 的特点是至少有一位有 \(7\) (与 \(7\) 相关)，则该数字不能被报出。
报到与 \(7\) 相关的数，输出 \(-1\)，否则输出下一个非 \(7\) 相关的数。
思路
做一个类似于埃氏筛的预处理。
我们用类似于埃氏筛的思路，筛掉与 \(7\) 相关的数的倍数。
开一个数组，记录下一个非 \(7\) 相关的数，否则赋值为自己（或者可以是任意非正数）。
读它。
值得注意的是，\(1e7\) 后面第一个非 \(7\) 相关的数是 \(10000010\)，所以我们不妨开 \(1e7+11\) 大小的数组，防止溢出。
对应AC代码
import java.util.*;
public class Main{
private static boolean relate(int x){ //是否与7相关
while(x > 0){
if(x % 10 == 7) return true;
x /= 10;
}
return false;
}
private static int[] preTreat(){
int[] next = new int[10000011];
for(int i=1;i<10000011;i++){
if(next[i] == 0 && relate(i)){ //类似于埃氏筛
for(int j=1;i*j<10000011;j++) next[i * j] = 1;
}
}
int last = 1;
for(int i=2;i<10000011;i++){
if(next[i] == 0){
next[last] = i;
last = i;
} else next[i] = i; //反正只要后面可以特判就行
}
return next;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
int[] next = preTreat();
for(int w=0;w<t;w++){
int cur = scanner.nextInt();
System.out.println(next[cur] == cur ? -1 : next[cur]);
}
}
}算是第一次接触数论了（
D. 逻辑表达式 CSP 2022 T3
题面
在编程语言中，存在逻辑表达式“短路”的现象，如：当判断 \(\&\) 时，若前面为 \(false\)，那么后面的条件直接不判断了。
给定一个由 \(0\)、\(1\)、\(\&\) 、 \(|\) 和括号组成的逻辑表达式，其中 \(1\) 和 \(0\) 分别表示真与假。输出表达式的结果，以及形如 \(a \& b\) 和 \(a | b\) 的短路各出现了几次。
思路1 expr
可以用类似于求中缀表达式的值的思路来做。
中缀表达式转后缀表达式
建立表达式树
计算并统计
这个方法码量有点大，dfs有点深，只能上cpp了（
对应AC代码
#include <bits/stdc++.h>
using namespace std;
struct Node{
int val, left, right;
};
int ansAnd = 0, ansOr = 0, nodeSize = 0;
vector<Node> nodes;
//expr 中缀转后缀
vector<int> toSuffix(const string& mid) {
vector<int> ex;
stack<char> ts;
map<char, int> pri;
pri['&'] = 4;
pri['|'] = 3;
pri['('] = 2;
for (char each : mid) {
if (each == '@') {
while (!ts.empty()) ex.push_back(pri[ts.top()]), ts.pop();
break;
} else if (each >= '0' && each <= '9') ex.push_back(each - '0');
else {
if (each == '(') ts.push(each);
else if (each == ')') {
while (ts.top() != '(') ex.push_back(pri[ts.top()]), ts.pop();
ts.pop(); //弹出左括号
} else {
while (!ts.empty() && pri[ts.top()] >= pri[each]) ex.push_back(pri[ts.top()]), ts.pop();
ts.push(each);
}
}
}
return ex;
}
//建表达式树
void build(const vector<int>& suffix){
stack<int> index;
for(int each : suffix){
if(each == 0 || each == 1){
nodes.push_back({each, -1, -1});
index.push(nodeSize ++);
}else{
int r = index.top();
index.pop();
int l = index.top();
index.pop();
nodes.push_back({each, l, r});
index.push(nodeSize ++);
}
}
}
int dfs(int index) {
if (nodes[index].val == 0 || nodes[index].val == 1) return nodes[index].val;
int l = dfs(nodes[index].left);
if (l == 0 && nodes[index].val == 4) {
ansAnd++;
return 0;
}
if (l == 1 && nodes[index].val == 3) {
ansOr++;
return 1;
}
return dfs(nodes[index].right); //既然不断路，那么值一定只和右边的值有关
}
int main() {
string mid;
cin >> mid;
mid += "@";
build(toSuffix(mid));
printf("%d\n", dfs(nodeSize - 1));
printf("%d %d\n", ansAnd, ansOr);
}思路2 分治
对于一个表达式，我们会先去找没有括号的优先级最高的符号，然后计算左右两边的值，这便是中缀表达式的直观求法。
由 \(1\) 所述，我们可以将表达式分层，并从优先级最高的那个符号开始左右分治求解，同时特判左边的值即可。
显然，我们不可能在每次求左右表达式的时候都遍历一遍字符串找符号，这肯定会 \(tle\)。于是乎，我们需要一个预处理，将当前位置之前该层最近的符号找出并记录它的下标。这样我们只要每次读取一下记录的下标是否在区间内即可。
对应AC代码
#include <bits/stdc++.h>
using namespace std;
int nowAnd[1000010], nowOr[1000010], lastAnd[1000010], lastOr[1000010];
string mid;
int ansAnd, ansOr;
int dc(int l, int r) {
if (nowOr[r] >= l) { //or的优先级更高
int left = dc(l, nowOr[r] - 1);
if (left == 1) {
ansOr++;
return 1;
}
return left | dc(nowOr[r] + 1, r);
} else if (nowAnd[r] >= l) {
int left = dc(l, nowAnd[r] - 1);
if (left == 0) {
ansAnd++;
return 0;
}
return left & dc(nowAnd[r] + 1, r);
} else if (mid[l] == '(' && mid[r] == ')') return dc(l + 1, r - 1);
return mid[l] - '0';
}
int main() {
cin >> mid;
int n = mid.size(), layer = 0;
mid = " " + mid;
for (int i = 1; i < n + 1; i++) { //预处理
switch (mid[i]) {
case '(':
layer++;
break;
case ')':
layer--;
break;
case '|':
lastOr[layer] = i;
break;
case '&':
lastAnd[layer] = i;
break;
}
nowAnd[i] = lastAnd[layer];
nowOr[i] = lastOr[layer];
}
printf("%d\n", dc(1, n));
printf("%d %d\n", ansAnd, ansOr);
}怎么比赛里面还有码农题（
E. 音量调节 HAOI 2012
题意
给定一个初始值 \(beginLevel\) 以及最大值 \(maxLevel\)，对于一个数组 \(c\)，在第 \(i\) 次操作时，可选择将当前的值加上或减去 \(c_i\)，或不操作。输出最后的最大值。
思路
一眼丁真，鉴定为 分组背包
不会做的去看背包九讲
题目特点：每个 \(c\) 都要选上，可以 \(+c\) 可以 \(-c\)，有范围限定。
分组：分成 \(c\) 组，每组为 \(c\) 和 \(-c\)。
我们可以用 \(boolean\) 类型的 \(dp\) 数组存储当前音量能否达到，对此，有如下状态转移方程: \(dp[i][v] = dp[i][v] || dp[i - 1][v ± c]\)
套模板即可。
对应AC代码
import java.util.*;
//快乐分组背包呀
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt(), begin = scanner.nextInt(), V = scanner.nextInt();
boolean[][] dp = new boolean[N + 1][V + 1];
dp[0][begin] = true;
for(int i=1;i<=N;i++){
int c = scanner.nextInt();
for(int v = V;v>=0;v--){
if(v - c >= 0) dp[i][v] |= dp[i - 1][v - c];
if(v + c <= V) dp[i][v] |= dp[i - 1][v + c];
}
}
for(int v=V;v>=0;v--) if(dp[N][v]){
System.out.println(v);
return;
}
System.out.println(-1);
}
}略微变化了一下的分组背包
F. 上升点列 CSP 2022 T4
题意
给定 \(n\) 个点坐标，可添加 \(k\) 个任意坐标，求出最长单调欧几里得距离序列。
思路
这道题如果联想到最长上升子序列就迎刃而解了。
用二维dp做，前 \(i\) 个点插入 \(j\) 个点的最长长度。
观察欧几里得距离可发现，若要使i~j序列可取，那么需要加上 \(d\) 个点， \(d = xi - xj + yi - yj + 1\)。
类似于最长上升子序列，得到状态转移方程： $dp[i][p] = max(dp[i][p], dp[j][p - d] + d + 1), p∈[d, k] $。
对应AC代码
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(), k = scanner.nextInt();
int[][] data = new int[n + 1][2];
for(int i=1;i<=n;i++) {
data[i][0] = scanner.nextInt();
data[i][1] = scanner.nextInt();
}
Arrays.sort(data, 1, n + 1, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0]);
int[][] dp = new int[n + 1][k + 1];
for(int i=1;i<=n;i++) for(int j=0;j<=k;j++) dp[i][j] = j + 1; //差了j个那就塞上j个
for(int i=2;i<=n;i++){
for(int j=i-1;j>=1;j--){ //i状态由j状态推得
if(data[j][1] > data[i][1]) continue;
//因为i状态由j状态推得，所以需要至少d个点才能满足欧几里得距离
int d = data[i][0] - data[j][0] + data[i][1] - data[j][1] - 1;
for(int p=d;p<=k;p++) dp[i][p] = Math.max(dp[i][p], dp[j][p - d] + d + 1); //最长上升子序列模板
}
}
int ans = 0;
for(int i=1;i<=n;i++) ans = Math.max(ans, dp[i][k]);
System.out.println(ans);
}
}想不到就废了（悲
G. 星球大战 JSOI 2008
题意
给定一个无向图，输出断开指定边后图中联通块的数量。
思路
首先是建立无向图，可以使用邻接表的方式存储。
标记这些需要断开的边，然后依次遍历各个边，若端点的根节点一样，那么就处于同一个连通块了。
因为至少存在 \(n\) 条边，那么连通块最多为 \(n-k\) 个。
综合 \(2\) 和 \(3\) 可知，答案即为 \(n - k - cnt\)，其中 \(cnt\) 为满足 \(2\) 条件的个数。
至于要输出每次打击后的值，我们可以逆向思维，将最后的状态还原到最初状态即可。
优化
我们可以使用并查集算法来优化。
没有解释地很清楚哈，还是有点难写的
对应AC代码
#include <bits/stdc++.h>
using namespace std;
typedef struct{
int a, b; //两点
int to;
}Edge;
int parent[400010];
Edge edges[400010];
int tot = 0;
int head[400010], broken[400010], ans[400010];
bool visited[400010];
//并查集查询，返回父节点id并将child全设为父节点直属下司(
int findParent(int child) {
int ground = child, father = child;
while (father != parent[father]) father = parent[father];
//更新father
while (ground != parent[ground]) {
int tmp = ground;
ground = parent[ground];
parent[tmp] = father;
}
return father;
}
//联通两个子树的爸爸即可(把一个爸爸设为另一个爸爸的直属下司
void unionIt(int x, int y) {
parent[findParent(x)] = findParent(y);
}
void addEdge(int a, int b){
edges[++tot].a = a;
edges[tot].b = b;
edges[tot].to = head[a];
head[a] = tot;
}
int main() {
int n, m, u, v, k;
long long w;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) parent[i] = i; //初始化并查集，我是我爸爸
for (int i = 0; i < m; i++) {
scanf("%d %d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
scanf("%d", &k);
for(int i=1;i<=k;i++){
scanf("%d", &broken[i]);
visited[broken[i]] = true;
}
int united = n - k;
for (int i = 0; i < 2 * m; i++) {
if (!visited[edges[i].a] && !visited[edges[i].b] && findParent(edges[i].a) != findParent(edges[i].b)) {//爸爸不一样，由union函数的写法可以看出俩玩意儿没联通
united --;
unionIt(edges[i].a, edges[i].b);
}
}
ans[k + 1] = united;
for(int i=k;i>=1;i--){
int x = broken[i];
visited[x] = false;
united ++;
for (int j = head[x]; j != 0; j = edges[j].to) {
int nowB = edges[j].b;
if(!visited[nowB] && findParent(x) != findParent(nowB)){
united --;
unionIt(x, nowB);
}
}
ans[i] = united;
}
for(int i=1;i<=k+1;i++) printf("%d\n", ans[i]);
}反着想有时候会更简单
H. 虚拟内存 HNOI 2005
题意
设计一个程序完成题面所指的算法。
太模拟了，建议看原题（
思路
一道逻辑很清楚但是不好写的模拟题。
我们很明显能发现，不可以 \(O(mn)\)，会寄，想想有序性，不难发现可以用优先队列。
我们需要存一下当前某一页的状态，方便找空页，我们可以用 \(map\)。
模拟
如果使用HashMap，对于某些如java的语言需要重写一下类的hashCode()和equals()方法，不然会像我一样WA。
当然，最好用cpp写，其他语言容易卡到tle和mle
对应AC代码
import java.util.*;
public class Main{
private static class Page{
int id, cnt, time;
Page(int id, int cnt, int time) {
this.id = id;
this.cnt = cnt;
this.time = time;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
Page page; //java版本低，用ide自动生成的还得改改（（（
if (!(o instanceof Page)) return false;
page = (Page) o;
return id == page.id && cnt == page.cnt && time == page.time;
}
@Override
public int hashCode() {
return Objects.hash(id, cnt, time);
}
}
private static class Pair<A, B>{
A A;
B B;
Pair(A a, B b) {
A = a;
B = b;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
Pair<?, ?> pair;
if (!(o instanceof Pair<?, ?>)) return false;
pair = (Pair<?, ?>) o;
return Objects.equals(A, pair.A) && Objects.equals(B, pair.B);
}
@Override
public int hashCode() {
return Objects.hash(A, B);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
//优先队列
int n = scanner.nextInt(), m = scanner.nextInt();
Map<Integer, Pair<Integer, Integer>> data = new HashMap<>();
PriorityQueue<Page> least = new PriorityQueue<>(((o1, o2) -> o1.cnt == o2.cnt ? o1.time - o2.time : o1.cnt - o2.cnt));
int ans = 0;
for (int i = 0; i < m; i++) {
int query = scanner.nextInt();
if(data.containsKey(query)){
int cnt = data.get(query).A, time = data.get(query).B;
least.remove(new Page(query, cnt, time));
least.offer(new Page(query, cnt + 1, time));
data.put(query, new Pair<>(cnt + 1, time));
ans ++;
}else if(data.size() < n){
data.put(query, new Pair<>(1, i));
least.offer(new Page(query, 1, i));
}else{
Page page = least.poll();
data.remove(page.id);
data.put(query, new Pair<>(1, i));
least.offer(new Page(query, 1, i));
}
}
System.out.println(ans);
}
}题目读半天...
I. 泡泡堂 ZJOI 2008
题意
给定两个队的选手的实力，在分配最好和最坏的情况下，分别输出 \(ZJ\) 队的分数。
思路
田忌赛马
1. 田忌最快的马比齐王最快的马快，比之2. 田忌最快的马比齐王最快的马慢，用田忌最慢的马跟齐王最快的马比
3. 田忌最快的马的速度与齐王最快的马速度相等
①田忌最慢的比齐王最慢的快，比之。
②田忌最慢的比齐王最慢的慢，田忌慢马 \(VS\) 齐王快马
③田忌最慢的与齐王最慢的相等，田忌慢马 \(VS\) 齐王快马
不予证明。
更具体地说
维护双指针$ head$ 和 \(end\), 按上述思路写
对应AC代码
import java.util.*;
public class Main{
//md，一个贪心想了我好久
private static long judge(int n, long[] a, long[] b){
int score = 0;
int headA = 0, headB = 0, endA = n - 1, endB = n - 1; //双指针？
while(headA <= endA && headB <= endB){
if(a[headA] > b[headB]){
score += 2;
headA ++;
headB ++;
}else if(a[endA] > b[endB]){
score += 2;
endA --;
endB --;
} else {
if(a[headA] == b[endB]) score ++;
headA ++;
endB --;
}
}
return score;
}
//我就猜一猜
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
long[] zj = new long[n], sb = new long[n];
for(int i=0;i<n;i++) zj[i] = scanner.nextLong();
for(int i=0;i<n;i++) sb[i] = scanner.nextLong();
Arrays.sort(zj);
Arrays.sort(sb);
System.out.printf("%d %d\n", judge(n, zj, sb), 2L * n - judge(n, sb, zj)); //有个小技巧（（（
}
}md，一个贪心想了我好久
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Blog - Floating Ocean！
评论