Blog - Floating Ocean
0%

FjnuOJ - 光棍新生欢乐赛

发表于 更新于
本文字数： 13k 阅读时长 ≈ 23 分钟
阅读次数： Valine：

Rank 1. AC 4/9.

因为11.11为四根棍，所以注定只能写四题

A. 乘方　CSP 2022 T1

题意

比较 和 的大小关系。

思路1 try-catch

用大数算法直接算，如果算得出来，那就比较；算不出来，也就是溢出了，那么一定是大于 的，利用语言特性，捕获这个异常然后输出 即可。

对应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

很简单，我们只需要循环 次把 乘上自己，判断一下是否大于 即可。

对应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

题意

对于方程组 , ，给定 ，解方程并输出 。

思路

  1. 化简第二个式子得到 ，设其为 .

  2. 由第一个式子得到 .

  3. 由1和2，.

  4. 求 ， 即为无解的第一种情况.

  5. 运用求根公式求出 ， 和 不为整数为无解的第二种情况，为整数就输出.

注意点：

  1. 肉眼可见会爆 ，用长整型.

  2. 不要用 ，会 .

对应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 提高组

题意

  1. 某数字为 的倍数， 的特点是至少有一位有 (与 相关)，则该数字不能被报出。

  2. 报到与 相关的数，输出 ，否则输出下一个非 相关的数。

思路

做一个类似于埃氏筛的预处理。

  1. 我们用类似于埃氏筛的思路，筛掉与 相关的数的倍数。

  2. 开一个数组，记录下一个非 相关的数，否则赋值为自己（或者可以是任意非正数）。

  3. 读它。

值得注意的是， 后面第一个非 相关的数是 ，所以我们不妨开 大小的数组，防止溢出。

对应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

题面

在编程语言中，存在逻辑表达式“短路”的现象，如：当判断 时，若前面为 ，那么后面的条件直接不判断了。

给定一个由 、、 、 和括号组成的逻辑表达式，其中 和 分别表示真与假。输出表达式的结果，以及形如 和 的短路各出现了几次。

思路1 expr

可以用类似于求中缀表达式的值的思路来做。

  1. 中缀表达式转后缀表达式

  2. 建立表达式树

  3. 计算并统计

这个方法码量有点大，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. 对于一个表达式，我们会先去找没有括号的优先级最高的符号，然后计算左右两边的值，这便是中缀表达式的直观求法。

  2. 由 所述，我们可以将表达式分层，并从优先级最高的那个符号开始左右分治求解，同时特判左边的值即可。

  3. 显然，我们不可能在每次求左右表达式的时候都遍历一遍字符串找符号，这肯定会 。于是乎，我们需要一个预处理，将当前位置之前该层最近的符号找出并记录它的下标。这样我们只要每次读取一下记录的下标是否在区间内即可。

对应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

题意

给定一个初始值 以及最大值 ，对于一个数组 ，在第 次操作时，可选择将当前的值加上或减去 ，或不操作。输出最后的最大值。

思路

一眼丁真，鉴定为 分组背包

不会做的去看背包九讲

  1. 题目特点：每个 都要选上，可以 可以 ，有范围限定。

  2. 分组：分成 组，每组为 和 。

  3. 我们可以用 类型的 数组存储当前音量能否达到，对此，有如下状态转移方程:

  4. 套模板即可。

对应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

题意

给定 个点坐标，可添加 个任意坐标，求出最长单调欧几里得距离序列。

思路

这道题如果联想到最长上升子序列就迎刃而解了。

  1. 用二维dp做，前 个点插入 个点的最长长度。

  2. 观察欧几里得距离可发现，若要使i~j序列可取，那么需要加上 个点， 。

  3. 类似于最长上升子序列，得到状态转移方程：

    。

对应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

题意

给定一个无向图，输出断开指定边后图中联通块的数量。

思路

  1. 首先是建立无向图，可以使用邻接表的方式存储。

  2. 标记这些需要断开的边，然后依次遍历各个边，若端点的根节点一样，那么就处于同一个连通块了。

  3. 因为至少存在 条边，那么连通块最多为 个。

  4. 综合 和 可知，答案即为 ，其中 为满足 条件的个数。

  5. 至于要输出每次打击后的值，我们可以逆向思维，将最后的状态还原到最初状态即可。

优化

我们可以使用并查集算法来优化。

没有解释地很清楚哈，还是有点难写的

对应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

题意

设计一个程序完成题面所指的算法。

太模拟了，建议看原题（

思路

一道逻辑很清楚但是不好写的模拟题。

  1. 我们很明显能发现，不可以 ，会寄，想想有序性，不难发现可以用优先队列。

  2. 我们需要存一下当前某一页的状态，方便找空页，我们可以用 。

  3. 模拟

如果使用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

题意

给定两个队的选手的实力，在分配最好和最坏的情况下，分别输出 队的分数。

思路

田忌赛马 　1. 田忌最快的马比齐王最快的马快，比之
　2. 田忌最快的马比齐王最快的马慢，用田忌最慢的马跟齐王最快的马比
　3. 田忌最快的马的速度与齐王最快的马速度相等
　　①田忌最慢的比齐王最慢的快，比之。
　　②田忌最慢的比齐王最慢的慢，田忌慢马 齐王快马

　　③田忌最慢的与齐王最慢的相等，田忌慢马 齐王快马

　不予证明。

更具体地说

维护双指针 和 , 按上述思路写

对应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，一个贪心想了我好久