寂寞双十一

发表于 2024-01-12 更新于 2024-02-11 分类于 ACM
本文字数： 204 阅读时长 ≈ 1 分钟

描述

今年的双十一太冷清了，冷清到没人愿意在网上购物了。小 w 饿了，但是太晚了，小 w 只能去自动贩卖机购买泡面。因为自动贩卖机没有找零的功能，所以如果小 \(\mathrm{w}\) 想购买 \(X\) 元的泡面就必须准确投入总和为 \(X\) 元的硬币。现在小 w 手里只有 \(A\) 枚 1 元硬币， \(B\) 枚 5 元硬币和 \(C\) 枚十元硬币，请问小 w 能否成功购买泡面 ## 输入描述输入一行四个整数 \(A, B, C, X\) ，保证 \(1 \leq A, B, C \leq 10000,1 \leq X \leq 10^{5}\)
## 输出描述如果无法购买，则输出一行 Impossable 如果可以购买，则输出方案数 ### 用例输入 1 1 2 3 37 ### 用例输出 1
Impossable

16109

发表于 2024-01-12 更新于 2024-02-11 分类于 ACM
本文字数： 2.6k 阅读时长 ≈ 10 分钟

问题陈述

时间限制为 4 秒。

如果一个序列的乘积可以表示为两个平方数之和，则该序列被称为好序列。例如：

{1, 1, 1} 是好序列，因为 \(1*1*1 = 1 = 0^2 + 1^2\)。 {6, 164, 15} 是好序列，因为 \(6*164*15 = 14760 = 42^2 + 114^2\)。 {2, 3} 不是好序列，因为 \(2*3 = 6\)，而 6 不可能表示为两个平方数的和。

一个序列 X 的子序列是指从 X 中删除零个或多个元素而保持剩余元素顺序不变得到的任何序列。如果两个相同序列的子序列通过删除不同的索引对应到不同序列上，则它们是不同的。

阅读全文 »

W1054 永无止境的反转

发表于 2024-01-12 更新于 2024-02-11 分类于 ACM
本文字数： 296 阅读时长 ≈ 1 分钟

1 Description

给定一条长度为 \(n\) 的数轴，初始 \(n\) 个整点全为白色。接下来将执行若干次反转操作：将某个区间内的所有白色整点变为黑色，所有黑色整点变为白色。

举例来说，若数轴为 \(WBWWBBBB\)，将其中红色部分反转后变为 \(WWBBWBBB\)。其中 \(W\) 和 \(B\) 分别表示白色和黑色。

你的任务是在每次操作后，求出当前还有多少白色块。注意，每次操作将会永久地改变数轴。

2 Input

阅读全文 »

W1053「无圆数」

发表于 2024-01-12 更新于 2024-02-11 分类于 ACM
本文字数： 344 阅读时长 ≈ 1 分钟

1 Description

派派最近没能抽到喜欢的卡，他变成了一个《原神》黑子。现在他很讨厌看到圆。

尤其是数字里的圆。

通过问题 W1045 - 我超，原，你已经知道数字 0,4,6,8,9 包含圆。

阅读全文 »

W1032LCA

发表于 2024-01-12 更新于 2024-02-11 分类于 ACM
本文字数： 1k 阅读时长 ≈ 4 分钟

oj | 【模板】LCA 点的距离 ## Description 求给定 \(m\) 组询问，每次询问两个点之间在树上的距离 ## 输入 \(\boxed{\begin{align}&n&m\\&u_{1}&v_{1}\\&u_{2}&v_{2}\\&\vdots&n-1\text{ lines}\\&u_{n-1}&v_{n-1}\\&x_{1}&y_{1}\\&x_{2}&y_{2}\\&\vdots &m\text{ lines}\\&x_{n}&y_{n}\end{align}}\)

数据范围： - \(1\leq n\leq 10^6\) - \(1\leq m\leq 10^5\) - \(0\leq u,v,x,y\leq n-1\) - \(x\neq y\) ## 输出输出 \(m\) 行，第 \(i\) 行包含一个整数，表示第 \(i\) 次询问的答案。

Sample Input

Sample Output

阅读全文 »

W1024理论的推演

发表于 2024-01-12 更新于 2024-02-11 分类于 ACM
本文字数： 500 阅读时长 ≈ 2 分钟

W1024理论的推演 ## Description 艾尔海森最近在教令院中抓捕犯下累累罪行的大贤者，大贤者能够在教令院手握大权，最重要的原因是教令院中内鬼很多！

作为一个普通的「文弱书生」，他决定在武力清除这些余党前做一些计算。首先他将教令院关系网络列出，由于艾尔海森智力超群，他只研究这张关系网络的最小生成树。在这棵树上，标注了若干红色的点，表示教令院中的内鬼。整个教令院内鬼间的团结程度定义为：所有红色点之间的距离之和。

由于艾尔海森还要去找卡维♂玩游戏，他现在要求你，教令院的学者，求出这棵教令院内鬼关系网络的最小生成树的内鬼之间的团结程度。聪明的你，一定能轻松解决这个问题。 ## Input \(\boxed{\begin{align}&n&m\\&r_{1}&r_{2}&&\dots&&r_{m}\\&u_{1}&v_{1}\\&u_{2}&v_{2}\\&\vdots &n-1\text{ lines}\\&u_{n-1}&v_{n-1}\end{align}}\)

输入包含 \(n+1\) 行 - 第一行包含两个整数 \(n, m\) 分别表示树的点数，红色点的个数 - 第二行包含 \(m\) 个数，表示红色点的编号 - 第 \(3\) 到第 \(n+1\) 行，每行包含两个整数 \(u, v\)，表示 \((u, v)\) 之间有一条边。数据范围： - \(1\leq n\leq 10^5\) - \(1\leq m\leq n\) - \(0\leq u,v\leq n-1\) ## Output 一个数，表示答案。

Sample Input

阅读全文 »

新生赛

发表于 2024-01-12 更新于 2024-01-17
本文字数： 2.6k 阅读时长 ≈ 9 分钟

1 数一数三角形

1.1 题目描述

在那遥远的角落三条边相拥相依它们相隔却又相连像爱情中的你我他三角形有着神秘的力量让我们的爱情纯粹又完美无论相隔多远，相连多近爱，永远如三角形般美丽

你得到一个正 \(N\) 边多边形。将任意一条边标记为边 \(1\)，然后按顺时针顺序将下一条边标记为边 \(2\)、\(3\)、\(\dots\)、\(N\)。在 \(i\) 侧有 \(A_i\) 个特殊点。这些点的位置使得边 \(i\) 被分成长度相等的 \(A_i + 1\) 段。

您希望创建尽可能多的 满足条件的三角形，同时满足以下要求。 - 每个三角形由 3 个不同的特殊点组成（不一定来自不同的边）作为它的角。 - 每个特殊点只能成为最多 1 个三角形的角。 - 所有的三角形不能互相相交。请你数一数可以创建的满足条件的三角形的最大数量。

阅读全文 »

2023新生赛题解

发表于 2024-01-12 更新于 2024-02-11
本文字数： 3.6k 阅读时长 ≈ 13 分钟

A 数一数三角形

难度：简单

- 在一般情况下，只要三个点不要都在一条边上就一定能构成三角形
    所以在一般情况下，将所有特殊点加起来除以 3 向下取整就可以，即: `cnt/3`

当一条边特殊点的数量远远多于其他边的时候，这个时候只有除了这条边之外的点可以和这个边能构成三角形，构成的三角形个数是 cnt-max(a[i])

注意数据范围，需要开 long long 即结果为: min(cnt/3,cnt-max(a[i]) 代码如下:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, a[200010];
int main()
{
    cin >> n;
    ll cnt = 0, maxa = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i], cnt += a[i], maxa = max(maxa, a[i]);
    cout << min(cnt / 3, cnt - maxa) << '\n';
}

### B 作文批改 #### 难度：入门一道考察大家代码功底的模拟题

#include<iostream>

using namespace std;
string word;
bool head = true;
int n, ans;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    while (n --)    
    {
        cin >> word;
        int i = 0;
        
        if((word.size() == 1 || word[1] < 'A') && word[0] == 'i')
        {
            ans ++;
            continue;
        }

        if(head)
        {
            if(word[i ++] > 'Z')ans ++;
            head = false;
        }


        for(; i < word.length(); i ++)
        {
            if(word[i] < 'A' && word[i] != ',')
            {
                head = true;
                continue;
            }
            if(word[i] < 'a' && word[i] >= 'A')ans ++;
        }
    }
    
    cout << ans;
}