古卷错缝

题目背景

盛唐年间，书生噜噜与好友 一只羊 行至洛阳白马寺外，见风吹古卷，卷面字迹参差。寺僧言：“欲令古卷复归整齐，需将所刻纹路化作交替阴阳之势。” 却只留下两行提示：

“零壹交织，方为正纹；首针可起零，亦可起壹。”

噜噜与一只羊苦思不得，请你施展算法之术，寻找最少改动次数，使卷上纹路成为严格的“0101…”或“1010…”交替图案。

题目描述

给定长度为的二进制字符串（仅含 0 与 1），你每次操作可以选择一个位置，将该位 0 改为 1 或将 1 改为 0。求至少需要多少次操作，才能把变成下列两种形态之一：

以 0 开头的完全交替串：
以 1 开头的完全交替串：

输出所需的最少操作次数。

输入格式

第一行一个整数。
第二行一个长度恰为的字符串，字符集为 0、1。

输出格式

输出一个整数，表示最少操作次数，末尾换行。

样例

1
2

5
11001

说明

若改成 10101，需修改次。

改成 01010 需修改次。

数据范围

参考代码

#include<bits/stdc++.h>
using namespace std;
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string s;
	int n;
	cin >> n;
	cin >> s;
	int ans_1 = 0, ans_2 = 0;
	for(int i = 0;i < s.size(); i++) {
		if(i % 2 == 0 && s[i] == '1') ans_1++;
		if(i % 2 == 1 && s[i] == '0') ans_1++; 
	}
	for(int i = 0;i < s.size(); i++) {
		if(i % 2 == 1 && s[i] == '1') ans_2++;
		if(i % 2 == 0 && s[i] == '0') ans_2++; 
	}
	cout << min(ans_1, ans_2);
	return 0;
}

古代密码

题目背景

在一次考古发掘中，噜噜和一只羊发现了一卷古老的羊皮卷。羊皮卷上记载了一种奇特的加密方法，用于在古代战争中传递秘密信息。这种方法被称为“乘方取模加密法”。

加密规则如下：将一个原始数（称为“底数” ）自乘次，得到它的次方，然后将这个结果对一个特定的数（称为“模数” ）取余数，最终得到的余数就是加密后的密文。

“一只羊”对这种古老的智慧非常着迷，它想请聪明的噜噜帮它实现一个计算器，来快速算出任意给定底数、指数和模数的加密结果。

问题描述

给定三个整数，请你计算的值。

这里的表示计算的次方，然后对取余数的结果。

输入格式

输入一行，包含三个整数，三个数之间用一个空格隔开。

输出格式

输出一个整数，表示的结果。

样例输入与输出

样例输入 1

2 10 9

样例输出 1

样例 1 解释

。
。
（计算过程：）

样例输入 2

3 0 100

样例输出 2

样例 2 解释

按照数学约定，。
。

数据规模与约定

对于30% 的数据：, 。
对于另外30% 的数据：, 。保证。
对于最后的40% 的数据：, 。
保证输入的为非负整数，为正整数。

参考代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int qp(int a, int b, int p) {
	int res = 1;
	while(b) {
		if(b & 1) res = res * a % p;
		b >>= 1;
		a = a * a % p;
	}
	return res;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int a, b, p;
	cin >> a >> b >> p;
	cout << qp(a, b, p);

	return 0;
}

羊羊市场

题目背景

在遥远的古代，有一个聪明的少年名叫“噜噜”。噜噜生活在一个广袤的草原上，他最亲密的伙伴是一只充满智慧、会说话的“一只羊”。有一天，一只羊对噜噜说：“我们的羊群数量太少了，你需要去山那边的集市上购买一些新的小羊，让我们的家族壮大起来。这是我毕生的积蓄，你一定要精打细算，尽可能多地买回小羊哦！” 噜噜带着钱和期望，来到了热闹非凡的羊羊市场。市场上的每一只羊都有自己的标价，噜噜想知道，用他现有的钱，最多能买回来多少只羊。

问题描述

给定噜噜拥有的总钱数 M 和市场上 N 只羊各自的价格。请你计算，噜噜最多能买多少只羊。

输入格式

输入共两行。

第一行包含两个正整数 N 和 M，分别表示市场上羊的数量和噜噜拥有的总钱数。

第二行包含 N 个正整数，表示每只羊的价格。

输出格式

输出一个整数，表示噜噜最多能买到的羊的数量。

样例输入与输出

样例输入 1

1 2	5 10 5 4 2 8 3

样例输出 1

样例 1 解释

市场上有 5 只羊，价格分别为 5, 4, 2, 8, 3。噜噜有 10 元钱。
为了买到尽可能多的羊，应该优先选择价格最低的。
价格从低到高排序为：2, 3, 4, 5, 8。

买下价格为 2 的羊，剩余钱数 10 - 2 = 8。
买下价格为 3 的羊，剩余钱数 8 - 3 = 5。
买下价格为 4 的羊，剩余钱数 5 - 4 = 1。
此时剩余 1 元，不够买任何一只剩下的羊了。
因此，噜噜最多能买 3 只羊。

数据规模与约定

对于20% 的数据：, , 。
对于另外30% 的数据：, , 。
对于最后的50% 的数据：, , 。

所有数据，保证为正整数。

参考代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 200005;
ll a[MAXN];              // 羊价

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

    int n; ll m;
    if(!(cin >> n >> m)) return 0;
    for(int i = 0; i < n; ++i) cin >> a[i];

    sort(a, a + n);      // 先按价格升序排，贪心选最便宜的
    ll s = 0;            // 当前已花费
    int ans = 0;         // 已买羊数
    for(int i = 0; i < n; ++i) {
        if(s + a[i] > m) break; // 钱不够则停止
        s += a[i];
        ++ans;
    }
    cout << ans << '\n';
    return 0;
}

素数对决

题目背景

噜噜和一只羊是草原上最好的朋友，他们也喜欢进行智力对决。一天，充满智慧的一只羊向噜噜提出了一个基于“哥德巴赫猜想”的挑战。它说：“噜噜，我给你一个偶数，你必须迅速地将它分解成两个素数之和。如果你能每次都快速地回答我，就算你赢得了今天的对决！”

哥德巴赫猜想是一个古老而著名的数论未解之谜，它声称：任何一个大于2的偶数，都可以表示成两个素数之和。

虽然这个猜想尚未被完全证明，但在很大的范围内都是成立的。噜噜决定编写一个程序来迎接挑战，他相信对于一只羊能提出的数字，这个规律一定成立。

问题描述

给定若干个大于2的偶数，你需要为每一个找到两个素数和，使得。

如果有多种组合满足条件，请输出其中最小的那一组。

（注：素数，又称质数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。例如，2, 3, 5, 7, 11 都是素数。）

输入格式

输入第一行包含一个正整数，表示测试数据的组数。

接下来行，每行包含一个偶数。

输出格式

对于每组测试数据，输出一行。

每行包含两个整数和，用一个空格隔开，表示你找到的满足且最小的两个素数。

样例输入与输出

样例输入 1

样例输出 1

1
2
3

3 7
3 17
2 2

样例 1 解释

对于，可以分解为或。最小的组合是。
对于，可以分解为或。最小的组合是。
对于，只能分解为。

数据规模与约定

对于 30% 的数据：，。
对于 100% 的数据：，。

保证是偶数。

参考代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MX=1'000'000;          // 上限
bool isp[MX+1];                  // 是否为素数
int pr[80'000], pc=0;            // 素数表

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

    /* 线性筛预处理素数 */
    fill(isp, isp+MX+1, 1);
    isp[0]=isp[1]=0;
    for(int i=2;i<=MX;++i){
        if(isp[i]) pr[pc++]=i;
        for(int j=0;j<pc && 1LL*i*pr[j]<=MX;++j){
            isp[i*pr[j]]=0;
            if(i%pr[j]==0) break;
        }
    }

    int T,n;                     // T 组数据
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=0;i<pc;++i){   // 枚举最小的 p1
            int p1=pr[i], p2=n-p1;
            if(p1>p2) break;     // p1 已超过 n/2，可停止
            if(isp[p2]){         // 找到符合条件的一对
                cout<<p1<<' '<<p2<<"\n";
                break;
            }
        }
    }
    return 0;
}

神力农田

题目背景

在古老的东方，少年“噜噜”和他的伙伴“一只羊”拥有一片神奇的方形农田。这片农田被划分为个小方格，每个方格都有一块土地。起初，所有土地的肥力都是 0。

“一只羊”告诉噜噜，天上的神灵会不定期地降下“神力之雨”来滋养这片土地。每一次神力之雨都会覆盖一个矩形区域，使得这个区域内所有土地的肥力都增加 1。经过了整整一个生长季节，神灵一共降下了次神力之雨。现在，噜噜和一只羊想知道，在所有滋养结束后，农田里肥力最高的土地，其肥力值是多少？以及有多少块土地达到了这个最高的肥力值？

问题描述

给定一个的网格，初始时所有格子的值都为 0。接下来有次操作，每次操作会给出一个矩形区域的左上角坐标和右下角坐标，你需要将这个矩形区域内（包括边界）所有格子的值都加上 1。

在所有次操作完成后，请你找出网格中最大的值，以及这个最大值在网格中出现了多少次。

输入格式

输入第一行包含三个正整数，分别表示农田的行数、列数和神力之雨的次数。

接下来行，每行包含四个正整数，描述了一次神力之雨覆盖的矩形区域。其中是矩形的左上角坐标，是右下角坐标。(, )

输出格式

输出一行，包含两个整数，用一个空格隔开。第一个整数是农田中最高的肥力值，第二个整数是拥有最高肥力值的土地数量。

样例输入与输出

样例输入 1

1
2
3

3 4 2
1 1 2 2
1 2 2 3

样例输出 1

2 2

样例 1 解释

农田是一个 3x4 的网格，初始状态如下：

1
2
3

0 0 0 0
0 0 0 0
0 0 0 0

第一次神力之雨覆盖 (1,1) 到 (2,2) 的区域后，农田变为：

1
2
3

1 1 0 0
1 1 0 0
0 0 0 0

第二次神力之雨覆盖 (1,2) 到 (2,3) 的区域后，农田变为：

1
2
3

1 2 1 0
1 2 1 0
0 0 0 0

最终，农田中的最大肥力值是 2，有 2 块土地的肥力达到了 2。因此输出 2 2。

数据规模与约定

对于20% 的数据：, 。
对于另外30% 的数据：, 。
对于最后的50% 的数据：, 。

所有数据，保证 , 。

参考代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 1005;        // N,M ≤1000，所以开到 1005

int d[MX+2][MX+2];          // 二维差分数组

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

    int n,m,k;
    if(!(cin>>n>>m>>k)) return 0;
    for(int t=0;t<k;++t){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        ++d[x1][y1];
        --d[x1][y2+1];
        --d[x2+1][y1];
        ++d[x2+1][y2+1];
    }

    int mx = 0;      // 最大值
    ll  cnt = 0;     // 最大值出现次数
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1]; // 前缀和还原
            if(d[i][j]>mx){
                mx = d[i][j];
                cnt = 1;
            }else if(d[i][j]==mx){
                ++cnt;
            }
        }
    }
    cout<<mx<<" "<<cnt<<"\n";
    return 0;
}

果壳语法杯ROUND7题解

古卷错缝

题目背景

题目描述

输入格式

输出格式

样例

数据范围

参考代码

古代密码

题目背景

问题描述

输入格式

输出格式

样例输入与输出

数据规模与约定

参考代码

羊羊市场

题目背景

问题描述

输入格式

输出格式

样例输入与输出

数据规模与约定

参考代码

素数对决

题目背景

问题描述

输入格式

输出格式

样例输入与输出

数据规模与约定

参考代码

神力农田

题目背景

问题描述

输入格式

输出格式

样例输入与输出

数据规模与约定

参考代码