实验室周赛暨CCPC选拔赛

比赛链接

第九届“图灵杯”NEUQ-ACM程序设计竞赛个人赛重现赛（A~K题）。

文章目录

• A.大学期末现状（签到题）
• B.G1024（签到题）
• C.NEUQ（贪心）
• D.小G的任务（暴力）
• E.nn与游戏（BFS）
• F.第二大数（滑动窗口）
• G.Num（数学+思维）
• H.特征值（前缀和+大数相加）
• I.玄神的字符串（思维）
• J.金牌厨师（二分+差分）
• K.WireConnection（自建边的最小生成树）

A.大学期末现状（签到题）

题意：

给一个考试分数 n，
及格（n ≥ 60）输出 “jige,haoye!”；
否则输出 “laoshi,caicai,laolao”。

思路：

签到题，直接判断

代码：

#include 
using namespace std;

int main()
{
    int n; cin >> n;
    if(n >= 60) puts("jige,haoye!");
    else puts("laoshi,caicai,laolao");
    return 0;
}

B.G1024（签到题）

题意：

给出 n 个人 和 k 天某班车已购票数 x 和 总票数 m，
求所有人买到同一天火车票的最早天数。

思路：

签到题，直接判断。
注意一个for别break，会卡掉输入，或者开两个for循环。

代码：

#include 
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k; cin >> n >> k;
    bool f = false;
    for(int i=1; i<=k; i++) 
    {
        int x, m; cin >> x >> m;
        if(m - x >= n && !f) 
        {
            cout << i << "n";
            f = true;
        }
    }
    if(!f) puts("G!");
    return 0;
}

C.NEUQ（贪心）

题意：

给出一个仅由大写字母A~Z组成的字符串，
问最少删除几个字母能得到仅由若干个"NEUQ"组成的子串。

思路：

不知道这题算什么，贪心？
遍历字符串，严格按照"NEUQ"的顺序确定保留下来的字母，
结果即为：n - cnt × 4（cnt为已确定"NEUQ"的个数）。

代码：

#include 
#include 
using namespace std;

int main()
{
    int n; cin >> n;
    string s; cin >> s;

	// 已有cnt个"NEUQ"
	// 下一个需要保留的字母为op, 0,1,2,3分别对应N,E,U,Q
    int cnt = 0, op = 0;
    for(int i=0; i
        if(s[i]=='N' && op==0) op = 1;
        else if(s[i]=='E' && op==1) op = 2;
        else if(s[i]=='U' && op==2) op = 3;
        else if(s[i]=='Q' && op==3) op = 0, cnt++;
    }
    cout << n - cnt*4 << "n";
    return 0;
}

D.小G的任务（暴力）

题意：

给出一个正整数 n，i 的范围为1~n ，sum为i 的各位数之和，现需求得sum的和。

思路：

直接暴力解，for遍历1 ~ n，while求得每一个 i 的各位数之和sum，再求和sum。

代码：

#include 
using namespace std;

int count(int x)
{
    int cnt = 0;
    while(x)
    {
        cnt += x%10;
        x /= 10;
    }
    return cnt;
}

int main()
{
    int n, res; cin >> n;
    for(int i=1; i<=n; i++) res += count(i);
    cout << res << "n";
    return 0;
}

E.nn与游戏（BFS）

题意：

给出一个n × n的地图和 m 个障碍物的坐标，再给出 t 对可控制单位和敌对单位，
障碍物、可控制单位和敌对单位均不可通过，即统一视为行走路线上的障碍物，
问：每一个可控制单位可否通过地图到达敌对单位的位置，如果可以，输出所需的最短步数；否则输出 -1。

思路：

障碍物标记为 -1，第 i 对可控制单位和敌对单位标记为 i，-1 和 i 均不可走过。
用 t 个可控制单位的坐标跑 t 遍广搜即可AC。

代码：

#include 
#include 
#include 
using namespace std;

const int N = 1010;
int n, m, t;
int g[N][N], st[N][N]; //g存地图，st标记某个坐标是否行走过
int d[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//地图中四个移动方向
struct node
{// 可控制单位的坐标(x, y)，走到对应敌对单位所需的步数
    int x, y, cnt;
}ser[15];

int bfs(int x, int y)
{
    // 初始化标记数组
    memset(st, 0, sizeof(st));
    
    queue  q;
    q.push({x, y, 0});
    st[x][y] = 1;// (x, y)已走过
    
    while(q.size())
    {
        auto tt = q.front();
        q.pop();
        
        for(int i=0; i<4; i++)
        {
            int ix=tt.x+d[i][0], iy=tt.y+d[i][1];
            // 出界 或 某点已经走过
            if(ix<0 || ix>=n || iy<0 || iy>=n || st[ix][iy]) continue;
            if(g[ix][iy] == 0)
            {// 某点可以走， -1 和 1~t均不可走
                q.push({ix, iy, tt.cnt+1});
                st[ix][iy] = 1;
            }// 找到敌对单位了
            else if(g[ix][iy] == g[x][y]) return tt.cnt + 1;
        }
    }
    return -1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    for(int i=1; i<=m; i++) 
    {
        int x, y; cin >> x >> y;
        g[x][y] = -1;//障碍物标记为-1
    }
    cin >> t;
    for(int i=1; i<=t; i++)
    {
        int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
        g[x1][y1] = g[x2][y2] = i;
        ser[i] = {x1, y1, 0};
    }
    for(int i=1; i<=t; i++) 
        cout << bfs(ser[i].x, ser[i].y) << "n";
    return 0;
}

F.第二大数（滑动窗口）

滑动窗口这个说法是在别处看到的，利于理解解题思路，这里拿来主义一下。

题意：

给出一个正整数n 和 n 个数，求和区间 [L, R] 中的第二大值
其中 L 和 R 均为下标，且L ∈ [1, n-1]，R ∈ [L+1, n]

思路：

定义两个遍历记录当前区间的最大值(maxk)和第二大值(seck)，
两层for循环，第一层遍历L，第二层遍历R,
（1）当R = L + 1 时，区间仅有两个元素，初始maxk 和 seck
（2）当R > L + 1 时，进行最大值和第二大值维护，即更新maxk和seck

• 当新进入区间的一个数num > maxk时，maxk和seck都需更新
• 当 maxk > num > seck时，仅需更新seck

代码：

#include 
#include 
#define int long long
using namespace std;

const int N = 1e4 + 10;
int a[N];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n; cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
    int res = 0;//结果
    int maxk=0, seck=0;//当前第一大数maxk、第二大树seck
    for(int i=1; i
        for(int j=i+1; j<=n; j++)
        {
            if(j == i+1) maxk=max(a[i],a[j]), seck=min(a[i],a[j]);
            else
            {//更新当前区间的最大值和第二大值
                if(a[j] > maxk) seck=maxk, maxk=a[j];
                else if(a[j] > seck) seck = a[j];
            }
            res += seck;
        }
    }
    cout << res << "n";
    return 0;
}

G.Num（数学+思维）

题意：

给出一个数 n ，判断其是否可以分解为 a ∗ b + a + b 的形式，Yes or No
(其中a>0，b>0)

思路：

a ∗ b + a + b = （a+1）×（b+1）- 1
可以转化为 判断是否存在 a、b 使得 n + 1 =（a+1）×（b+1）成立

• 当n + 1 为素数时，（a+1）×（b+1）= 1 ×（n+1），此时a=0，b=n，不符合题意；
• 当n + 1 不为素数时，存在a>0且b>0使得 a ∗ b + a + b = n，符合题意。

代码：

#include 
using namespace std;

bool check(int x)
{// x是否为素数
    for(int i=2; i<=x/i; i++)
        if(x % i == 0) return false;
    return true;
}

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

    int n; cin >> n;
    if(check(n + 1)) puts("No");
    else puts("Yes");
    return 0;
}

H.特征值（前缀和+大数相加）

题意：

给一个贼大的数 x，其中 1 ≤ x ≤ pow(10, 500000)，求它的特征值，
即求：x + while(x) { int t = x/10; x += t; }
当然不能这么求结果，因为 x 贼大，超int 和 long long 只能用字符串输入，只是用上述代码阐述一下题意中的“特征值”。

思路：

看一个样例：1225 + 122 + 12 + 1 = 1360，观察可知：

• 个位 = 5 + 2 + 2 + 1 = 10（mod 10）= 0；
• 十位 = 2 + 2 + 1 + 个位满十进的 1 = 6
• 百位 = 2 + 1 = 3
• 千位 = 1

可得到，x 的特征值的每一位为该数位和该数位前面所有数位之和取余于十，然后满 10 向该数位的高数位进 1。
这里可以引出一个概念（瞎胡说）：数位前缀和。例：数字1225 个位的数位前缀和为1 + 2 + 2 + 5。

代码：

#include 
#include 
#include 
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string s; cin >> s;// 输入
    vector  v;   // 存每一个的数位前缀和
    int sum = 0;     // 记录数位前缀和
    for(int i=0; i
        sum += s[i] - '0';
        v.push_back(sum);
    }
    
    vector  ans;// 存每一位的结果
    int t = 0;      // 记录该数位是否进位
    for(int i=v.size()-1; i>=0; i--)
    {
        ans.push_back((t + v[i]) % 10);
        t = (t + v[i]) / 10;
    }// 如果最后一位仍满十进位了
    if(t) ans.push_back(t);
    // 倒序输出结果
    for(int i=ans.size()-1; i>=0; i--) cout << ans[i];
    return 0;
}

I.玄神的字符串（思维）

题意：

给出一个01序列 s，序列 s 的长度为偶数，可以进行3种操作和所需花费代价，求得将 s 删空的最小代价。

1. 任意删除序列中一个 0 和 1，代价为 a ；
2. 任意删除序列中两个 0 或 两个 1 ，代价为 b ；
3. 将任意一个 0 --> 1 或 1 --> 0，代价为 c 。

思路：

对比操作1 和 操作2 的代价大小，以确定哪种删除操作优先进行，
记录序列中 0 和 1 的个数，利用序列长度为偶数的特性，考虑01个数的所有情况。
另外：操作1 + 操作 3 = 操作 2，操作2 + 操作3 = 操作1

• 当a + c < b 时，我们可以用操作1 + 操作 3 替代 操作 2；
• 当b + c < a 时，我们可以用操作2 + 操作 3 替代 操作 1；

各种 a b 代价大小和 01 个数情况：

1. 操作1 优先
   cnt[0] = 5, cnt[1] = 5 , 进行 t 次操作1 后序列为空；
   cnt[0] = 4, cnt[1] = 6 , 进行 t 次操作1 后cnt[0] = 0, cnt[1] = 2
   cnt[0] = 2, cnt[1] = 8 , 进行 t 次操作1 后cnt[0] = 0, cnt[1] = 6
   因此if(cnt[0] || cnt[1]) cost += max(cnt[0], cnt[1])/2 * min(a+c, b);
   不能写成if(cnt[0] || cnt[1]) cost += max(cnt[0], cnt[1]) * min(a+c, b);
2. 操作1 优先
   cnt[0] = 5, cnt[1] = 5 , 尽可能多地进行操作2 后序列仍不为空；
   仅需进行一次操作1 或 操作2+3 if(cnt[0] && cnt[1]) cost += min(a, b+c);
   cnt[0] = 4, cnt[1] = 6 , 尽可能多地进行操作2 后序列为空；
   cnt[0] = 2, cnt[1] = 8 , 尽可能多地进行操作2 后序列为空。

代码：

#include 
#include 
#include 
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string s; cin >> s;
    int a, b, c; cin >> a >> b >> c;
    
    int cnt[2]; // 存储序列中0 1的个数
    for(int i=0; i
        if(s[i] == '0') cnt[0]++;
        else cnt[1]++;
    }
    
    int cost = 0;// 所需代价
    if(a <= b)
    {// 操作1 优先
        int t = min(cnt[0], cnt[1]);// 进行 t 次 操作1
        cost += a * t;
        cnt[0] -= t; cnt[1] -= t;
        // 01序列长度为偶数，删掉 t 对 01 后仅有两种情况序列不为空：
        // cnt[0] = 0 , cnt[1] = 偶 或 cnt[0] = 偶 , cnt[1] = 0
        if(cnt[0] || cnt[1]) cost += max(cnt[0], cnt[1])/2 * min(a+c, b);
    } 
    else 
    {// 操作2 优先
        cost += (cnt[0]/2 + cnt[1]/2)* b; // 进行 cnt[0]/2 + cnt[1]/2 次操作2
        cnt[0] -= cnt[0]/2*2; cnt[1] -= cnt[1]/2*2;
        // 01序列长度为偶数，删掉 cnt[0]/2 对 0 和 cnt[1]/2 对 1 后仅有一种情况序列不为空：
        // cnt[0] = 1 , cnt[1] = 1
        if(cnt[0] && cnt[1]) cost += min(a, b+c);
    }
    cout << cost << "n";
    return 0;
}

J.金牌厨师（二分+差分）

一个二分题，但check()有两个条件，想不出来，没能AC。
下面是跟大佬学习的解题代码，大佬题解链接 。

题意：

给出一个数 n， 表示厨师做菜的辣度值范围为 [ 1，n ]
再给出 m 个学生可以接受的辣度值范围 [ Li，Ri ]
从 m 个学生中任选 k 个，k 个学生都能接受的辣度值范围长度为 x
问：max（k，x）最大值为多少？

思路：

尝试写思路的时候人裂开了，下面仅讲一个让我恍然大悟的点。
cnt[p[i].first + mid - 1]++; cnt[p[i].second + 1]--;
一般差分操作为cnt[p[i].first]++; cnt[p[i].second + 1]--;
而这里是cnt[p[i].first + mid - 1]++;表示所选 k 个学生在辣度值范围长度满足mid的前提下的可滑动的范围为[p[i].first+mid-1, p[i].second]。

代码：

#include 
#include 
#define pii pair 
using namespace std;

const int N = 300010;
int n, m; 
pii p[N];
int cnt[N];


bool check(int mid)
{
    memset(cnt, 0, sizeof(cnt));
    
    for(int i=1; i<=m; i++)
    {
        int len = p[i].second - p[i].first + 1;
        if(len >= x)
        {
            cnt[p[i].first + mid - 1]++;
            cnt[p[i].second + 1]--;
        }
    }
    
    for(int i=1; i<=n; i++)
    {
        cnt[i] += cnt[i-1];
        if(cnt[i] >= mid) return true;
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int l, r; cin >> l >> r;
        p[i] = {l, r};
    }
    int l=1, r=n;
    while(l < r)
    {
        int mid = (l + r + 1) / 2;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << "n";
    return 0;
}

K.WireConnection（自建边的最小生成树）

题意：

给出 n 个接线器的三维空间坐标（x，y，z），用电线连接 n 个接线器。
问：所需的电线最短是多少？

思路：

自建边 + kruskal算法求最小生成树,记得开long long。

代码：

#include 
#include 
#include 
#define int long long 
using namespace std;

const int N = 2010;
int n;
int bcj[N];//并查集数组

struct point
{//存点的空间坐标(x, y, z)
    int x, y, z;
}p[N];

struct edge
{// 存点a与点b之间的距离len
    int a, b, len;
}e[N*N/2];//注意这里开N*N, N*N/2也可
int idx;//表示已建idx条边
// 边按权值从小到大排序
bool cmp(edge a, edge b) {return a.len < b.len;}
// 找根节点
int find(int x) {return x == bcj[x] ? bcj[x] : find(bcj[x]);}

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

    cin >> n;
    for(int i=1; i<=n; i++)
    {
        int x,y,z; cin>>x>>y>>z;
        p[i] = {x, y, z};
    }// 以上为输入
    
    // 建边
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
            e[++idx]={i, j, (int)ceil(sqrt(pow((p[i].x-p[j].x),2)*1.0+pow((p[i].y-p[j].y),2)*1.0+pow((p[i].z-p[j].z),2)*1.0))};
    // 边按权值从小到大排序
    sort(e+1, e+idx+1, cmp);
    //初始化并查集
    for(int i=1; i<=n; i++) bcj[i] = i;
    
    // Kruskal求最小生成数
    int res = 0, cnt = 0;//已接电线的总长度res, 已连接cnt条电线
    for(int i=1; i<=idx; i++)
    {
        int a=e[i].a, b=e[i].b, len=e[i].len;
        a = find(a); b = find(b);
        if(a != b)
        {
            cnt++;
            bcj[a] = b;
            res += len;
        }
        if(cnt == n-1) break;
    }
    cout << res << "n";
    return 0;
}