下面是题解时间
L1-1 编程解决一切
根据题意直接输出。
print("Problem? The Solution: Programming.")
L1-2 再进去几个人
题目有点绕，题意就是输出 b-a，直接看输出猜一遍过。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve(){
int a,b;
cin>>a>>b;
cout<<b-a;
return;
}
int main(){
//关闭输入输出同步以提高C++的IO效率
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t=1;
while(t--){
solve();
if(t)cout<<"\n";
}
return 0;
}
L1-3 帮助色盲
题目很绕，如果实在看不懂的话，可以把每种情况都列出来，对照题意输出，最多就是3x2=6种情况。感觉在做阅读理解。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve() {
int a,b;
cin>>a>>b;
if(a==0){
if(b==0){
cout<<"biii";
}else{
cout<<"-";
}
cout<<"\nstop";
}else if(a==1){
if(b==0){
cout<<"dudu";
}else{
cout<<"-";
}
cout<<"\nmove";
}else{
cout<<"-\nstop";
}
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t=1;
while(t--) {
solve();
if(t)cout<<"\n";
}
return 0;
}
L1-4 四项全能
根据题意，我们不难发现，对于样例 1，易知公式为 sum-(m-1)*n，但是人数不可能为负数，于是要与 0 比较取最大。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve() {
int n,m;
cin>>n>>m;
int a[1000];
int sum=0;
for(int i=0;i<m;++i){
cin>>a[i];
sum+=a[i];
}
cout<<max(sum-(m-1)*n,0);
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t=1;
while(t--) {
solve();
if(t)cout<<"\n";
}
return 0;
}
L1-5 别再来这么多猫娘了！
赛时得分为 12/15 ，怀疑是赛时外层循环是从 0 到字符串 ss 的末尾的缘故，而题目要求是第一个屏蔽词替换完成后才轮到第二个屏蔽词。按题意模拟即可，L1 难度的题目也不会特意去卡时间。
#include <bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;
//任意中文字即可，越短越好（防超时）
const string c="猫娘";
void solve() {
int clen=c.size();
string s[105];
int n;
cin>>n;
for(int i=0;i<n;++i){
cin>>s[i];
}
int k;
cin>>k;
//吃掉回车
getchar();
string ss;
getline(cin,ss);
int cnt=0;
//按屏蔽词顺序依次遍历待查找字符串ss
for(int i=0;i<n;++i){
auto it=ss.find(s[i]);
int len=s[i].size();
while(it!=string::npos){
ss.replace(it,len,c);
//记录替换次数
++cnt;
it=ss.find(s[i]);
}
}
auto it=ss.find(c);
//屏蔽词替换结束后，将其替换成真正的屏蔽词
while(it!=string::npos){
ss.replace(it,clen,"<censored>");
it=ss.find(c);
}
if(cnt<k){
cout<<ss;
}else{
cout<<cnt<<"\nHe Xie Ni Quan Jia!";
}
return;
}
int main() {
int t=1;
while(t--) {
solve();
if(t)cout<<"\n";
}
return 0;
}
L1-6 兰州牛肉面
题目第一行给出有几种牛肉面，第二行就是每种牛肉面的单价，随后 n 行会告诉你 x 种牛肉面售出了 y 碗。由于数据量很小，可以直接用数组存。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve() {
int n;
cin>>n;
double a[105];
for(int i=1;i<=n;++i){
cin>>a[i];
}
int lib[105];
memset(lib,0,sizeof(lib));
int x,y;
cin>>x>>y;
while(x&&y){
lib[x]+=y;
cin>>x>>y;
}
double sum=0;
for(int i=1;i<=n;++i){
cout<<lib[i]<<"\n";
sum+=a[i]*lib[i];
}
printf("%.2f",sum);
return;
}
int main() {
int t=1;
while(t--) {
solve();
if(t)cout<<"\n";
}
return 0;
}
L1-7 整数的持续性
根据题意，先自定义一个计算正整数持续性的函数 fun 。利用 map 来存持续性为某一值的整数数组，按题意从 a 遍历到 b 即可得到最后的结果。
#include <bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;
//返回整数x的持续性
int fun(int x){
int step=0;
while(x>10){
++step;
int now=1;
while(x){
now*=x%10;
x/=10;
}
x=now;
}
return step;
}
void solve(){
int a,b;
cin>>a>>b;
//记录步长为step的持续性时的所有整数
map <int,vector<int> >lib;
for(int i=a;i<=b;++i){
int step=fun(i);
lib[step].push_back(i);
}
//由于要输出最长的整数，map默认是按键从小到大排序，因而只要lib里面最后一个位置的步长和整数数组即可
auto it=lib.end();
--it;
cout<<it->fi<<"\n";
for(int i=0;i<it->se.size();++i){
if(i)cout<<" ";
cout<<it->se[i];
}
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t=1;
while(t--){
solve();
if(t)cout<<"\n";
}
return 0;
}
L1-8 九宫格
题目九宫格要求 1 到 9 这九个数字在每一行、每一列、每个正方形宫位出现且仅出现一次，其实就是数独。那么我们只需要定义三个数组分别用来标记每一行、每一列、每个宫位正整数出现的个数，最后再遍历一遍三个数组看值是不是为 1 就可以了。
对于 row[i][j] 而言，它的值就是在第 i 行，数字 j 出现的次数。
对于 col[i][j] 而言，它的值就是在第 i 列，数字 j 出现的次数。
对于 gong[i][j][k]而言，它的值就是在第 i 行第 j 列的正方形宫中，数字 k 出现的次数。
#include <bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;
//标记行的合法性
int row[9][10];
//标记列的合法性
int col[9][10];
//标记正方形宫位的合法性
int gong[3][3][10];
void solve() {
//数据初始化
memset(row,0,sizeof(row));
memset(col,0,sizeof(col));
memset(gong,0,sizeof(gong));
bool ok=1;
for(int i=0; i<9; ++i) {
for(int j=0; j<9; ++j) {
int x;
cin>>x;
if(x>=1&&x<=9) {//验证数字大小是否合法
++row[i][x];
++col[j][x];
++gong[i/3][j/3][x];
} else {
ok=0;
}
}
}
if(ok) {
//验证行和列的数据是否合法
for(int i=0; i<9; ++i) {
for(int j=1; j<=9; ++j) {
if(row[i][j]!=1||col[i][j]!=1) {
cout<<0;
return;
}
}
}
//验证正方形宫位的数据是否合法
for(int i=0; i<3; ++i) {
for(int j=0; j<3; ++j) {
for(int k=1; k<=9; ++k) {
if(gong[i][j][k]!=1) {
cout<<0;
return;
}
}
}
}
cout<<1;
} else {
cout<<0;
}
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t=1;
cin>>t;
while(t--) {
solve();
if(t)cout<<"\n";
}
return 0;
}
L2-1 鱼与熊掌
这题不能直接开二维数组，因为这样子做要开 1e10 的空间，显然是不行的。这题是 stl 套 stl 就能秒过的题，与往年的大模拟题相比难度下降很多。这道题按题意进行模拟就行了。
对于 lib[i][j] 而言，就是表示第 i 个人是否拥有第 j 种物品。
#include <bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;
void solve() {
int n,m;
cin>>n>>m;
//标记某人是否拥有某种物品
map <int,map<int,bool> >lib;
for(int i=1;i<=n;++i){
int k;
cin>>k;
for(int j=0;j<k;++j){
int x;
cin>>x;
lib[i][x]=1;
}
}
int q;
cin>>q;
while(q--){
int a,b;
cin>>a>>b;
int cnt=0;
for(int i=1;i<=n;++i){
//若两种物品都有，则计数
if(lib[i][a]==1&&lib[i][b]==1)++cnt;
}
cout<<cnt<<"\n";
}
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t=1;
while(t--) {
solve();
if(t)cout<<"\n";
}
return 0;
}
L2-2 懂蛇语
这题唯一值得注意的是，如何正确读取一行的字符串。若 getline 函数前有 cin ，它会意外地吃到一个回车，因而我们需要在 cin 后面多使用一次 getline 函数或者是用 getchar 函数来忽略掉这个回车。
由于这题会多次用到某字符串对应的首字母缩写，我们可以写一个 fun 函数来实现获取字符串对应的首字母缩写。之后可以用 stl 套 stl 通过首先存储每个首字母缩写对应的字符串，后面判断这个缩写所对应的数组的值就能知道查询的句子能否查到。因为要按字典序排序，所以要遍历一遍 lib 对每个数组进行排序。
#include <bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;
//返回字符串s对应的首字母缩写
string fun(string s){
bool f=1;
string res="";
for(auto x:s){
if(x==' '){
f=1;
}else{
if(f){
res+=x;
}
f=0;
}
}
return res;
}
void solve() {
map <string,vector<string> >lib;
int n;
cin>>n;
//用getchar函数吃掉回车
getchar();
//存储蛇语
for(int i=0;i<n;++i){
string s;
getline(cin,s);
lib[fun(s)].push_back(s);
}
//使得蛇语按整句的字典序排序
for(auto it=lib.begin();it!=lib.end();++it){
sort(it->se.begin(),it->se.end());
}
//进行m次查询
int m;
cin>>m;
getchar();
while(m--){
string s;
getline(cin,s);
string key=fun(s);
if(lib[key].size()){
for(int i=0;i<lib[key].size();++i){
if(i)cout<<"|";
cout<<lib[key][i];
}
}else{
cout<<s;
}
cout<<"\n";
}
return;
}
int main() {
int t=1;
while(t--) {
solve();
if(t)cout<<"\n";
}
return 0;
}
L2-3 满树的遍历
这题并不用真的去构建一颗树，用一个数组 son 就能存储每个节点的度，最后用 dfs 跑一遍输出前序序列。
#include <bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int NUM=1e5+5;
//记录节点度数，值为0时说明是叶子节点
int son[NUM];
//用来存储路径
map <int,vector<int> >lib;
//标记是否遍历过了
bool vis[NUM];
//用来格式控制，保证行首位无多余空格
bool kg=0;
//输出前序遍历序列
void dfs(int x){
if(kg)cout<<" ";
kg=1;
cout<<x;
vis[x]=1;
for(int i=0;i<lib[x].size();++i){
int to=lib[x][i];
if(!vis[to]){
dfs(to);
}
}
return;
}
void solve() {
int n;
cin>>n;
//记录根节点
int root;
for(int i=1;i<=n;++i){
int x;
cin>>x;
if(x){
++son[x];
lib[x].push_back(i);
}else{
root=i;
}
}
//记录非叶子节点的最大的度
int maxx=0;
bool ok=1;
for(int i=1;i<=n;++i){
if(son[i]){
//如果maxx为0说明先前都是叶子节点或者是节点1
if(maxx){
//若maxx和son[i]的值不等说明不满足k阶满树的条件
if(maxx!=son[i]){
ok=0;
maxx=max(maxx,son[i]);
}
}else{
maxx=son[i];
}
}
}
cout<<maxx<<" "<<(ok?"yes":"no")<<"\n";
dfs(root);
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t=1;
while(t--) {
solve();
if(t)cout<<"\n";
}
return 0;
}
L2-4 吉利矩阵
先来打个表，秒了，O（1）复杂度，我宣布这是这道题最优的解法（逃
#include <bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;
int a[10][5];
void solve() {
a[2][1]=3;
a[2][2]=21;
a[2][3]=282;
a[3][1]=4;
a[3][2]=55;
a[3][3]=2008;
a[4][1]=5;
a[4][2]=120;
a[4][3]=10147;
a[5][1]=6;
a[5][2]=231;
a[5][3]=40176;
a[6][1]=7;
a[6][2]=406;
a[6][3]=132724;
a[7][1]=8;
a[7][2]=666;
a[7][3]=381424;
a[8][1]=9;
a[8][2]=1035;
a[8][3]=981541;
a[9][1]=10;
a[9][2]=1540;
a[9][3]=2309384;
int l,n;
cin>>l>>n;
cout<<a[l][n];
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t=1;
while(t--) {
solve();
if(t)cout<<"\n";
}
return 0;
}
正解是 dfs + 剪枝，每次经过一点，要判断行和列是否合法。
#include <bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;
void solve() {
int l,n;
cin>>l>>n;
//统计目前某行的和
int row[15];
//统计目前某列的和
int col[15];
//数据初始化
memset(row,0,sizeof(row));
memset(col,0,sizeof(col));
int ans=0;
//dfs遍历所有可能性，pos从1开始
function<void(int)> dfs = [&](int pos){
int x=(pos-1)/n+1;
int y=(pos-1)%n+1;
if(pos==n*(n-1)+1){
++ans;
return;
}
for(int i=0;i<=l;++i){
row[x]+=i;
col[y]+=i;
if(row[x]<=l&&col[y]<=l){
if(!((x==n&&col[y]!=l)||(y==n&&row[x]!=l))){
dfs(pos+1);
}
}
row[x]-=i;
col[y]-=i;
}
return;
};
dfs(1);
cout<<ans;
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t=1;
// cin>>t;
while(t--) {
solve();
if(t)cout<<"\n";
}
return 0;
}
L3-1 夺宝大赛
补完题发现赛时只要再加一个 player 数组记录胜者并用 maxx 与当前距离大本营距离进行比较来辨别是否发生火拼，用 posx 和 posy 来标记胜者。发现 pta 上面定义不了全局变量 x1 和 y1 说是被定义了？
为了与平时写题习惯相吻合，这里定义 n 为行，m为列，题目有个陷阱就是 k 名队伍坐标是先给的列，再是给的行。
题目的整体思路就是用 bfs 从大本营跑一遍，当遇到的 dis 比 maxx 大的时候，若是 posx 不为 0 就证明前面已经有没有发生火拼的队伍且比当前队伍还要快的队伍存在了，就没有必要再搜索下去了。一定要剪枝！赛时我有 6 分卡在内存超出，6 分卡在时间超限。
#include <bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
using namespace std;
//全局变量初值为0
int n,m;
int a[105][105];
bool vis[105][105];
int dis[105][105];
int player[105][105];
queue <pair<int,int> > q;
//标记winner的位置 (0,0)表示没有胜者
int posx;
int posy;
//合法的移动
int dx[]= {0,0,1,-1};
int dy[]= {1,-1,0,0};
//目前最远距离
int maxx=0;
void solve() {
//初始化dis数组
memset(dis,0x3f,sizeof(dis));
cin>>n>>m;
//标记大本营位置
int x0,y0;
for(int i=1; i<=n; ++i) {
for(int j=1; j<=m; ++j) {
cin>>a[i][j];
if(a[i][j]==2) {
x0=i;
y0=j;
dis[x0][y0]=0;
}
}
}
int k;
cin>>k;
int cnt=0;
for(int i=1; i<=k; ++i) {
int x,y;
cin>>y>>x;
player[x][y]=i;
if(x==x0&&y==y0) {
++cnt;
}
}
if(cnt==1) {
cout<<player[x0][y0]<<" 0";
return;
} else if(cnt>1) {
cout<<"No winner.";
return;
}
q.push({x0,y0});
vis[x0][y0]=1;
auto bfs=[&]() {
while(q.size()) {
auto tmp=q.front();
q.pop();
int x=tmp.fi;
int y=tmp.se;
//只有有队伍存在的地方，最远距离才有意义
if(player[x][y]) {
if(maxx<dis[x][y]) {
if(posx!=0) {
break;
}
posx=x;
posy=y;
maxx=dis[x][y];
} else if(maxx==dis[x][y]) {
//火拼了，没有胜者
posx=0;
posy=0;
}
}
for(int i=0; i<4; ++i) {
int xx=x+dx[i];
int yy=y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]&&a[xx][yy]) {
vis[xx][yy]=1;
dis[xx][yy]=dis[x][y]+1;
q.push({xx,yy});
}
}
}
return;
};
bfs();
if(posx==0) {
cout<<"No winner.";
} else {
cout<<player[posx][posy]<<" "<<dis[posx][posy];
}
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t=1;
// cin>>t;
while(t--) {
solve();
if(t)cout<<"\n";
}
return 0;
}
L3-2 工业园区建设
二分加前缀和。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
// 解决问题的函数
void solve() {
int n, m, k;
cin >> n >> m >> k; // 输入 n, m, k
string s;
cin >> s; // 输入字符串 s
s = " " + s; // 将字符串 s 前添加一个空格以方便计算
// 计算前缀和数组
vector<int> sum(n + 1);
vector<ll> sum0(n + 1), sum1(n + 1);
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + (s[i] == '1');
sum0[i] = sum0[i - 1] + (s[i] == '0' ? i : 0);
sum1[i] = sum1[i - 1] + (s[i] == '1' ? i : 0);
}
// 获取最小的满足条件的区间 [l, r] 中心为 pos 的区间
auto get1 = [&](int pos) -> pii {
int l = 0, r = n;
auto check = [&](int mid) -> bool{
int L = max(1, pos - mid), R = min(n, pos + mid);
int cnt1 = sum[R] - sum[L - 1];
int cnt0 = R - L + 1 - cnt1;
return cnt1 + min(m, cnt0) >= k;
};
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
int resl = max(1, pos - l), resr = min(n, pos + l);
int cnt0 = sum[resr] - sum[resl - 1] + min(m, resr - resl + 1 - (sum[resr] - sum[resl - 1]));
if (cnt0 > k) {
if (resr - pos >= pos - resl) resr--;
else resl++;
}
return {resl, resr};
};
// 获取区间 [L0, R0] 中心为 pos 的区间
auto get2 = [&](int L0, int R0, int pos) -> pii {
int l = 0, r = max(R0 - pos, pos - L0);
int need = min(m, R0 - L0 + 1 - (sum[R0] - sum[L0 - 1]));
auto check = [&](int mid) -> bool
{
int L = max(L0, pos - mid), R = min(R0, pos + mid);
int cnt1 = sum[R] - sum[L - 1];
int cnt0 = R - L + 1 - cnt1;
return cnt0 >= need;
};
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
int resl = max(L0, pos - l), resr = min(R0, pos + l);
int cnt0 = resr - resl + 1 - (sum[resr] - sum[resl - 1]);
if (cnt0 > need && resl != resr) {
if (s[resl] == '0' && s[resr] == '0') {
if (resr - pos >= pos - resl) resr--;
else resl++;
} else if (s[resl] == '0') resl++;
else resr--;
}
return {resl, resr};
};
// 遍历每个中心点 pos，输出对应的结果
for (int i = 1; i <= n; i++) {
auto LR1 = get1(i);
int l1 = LR1.first, r1 = LR1.second;
auto LR2 = get2(l1, r1, i);
int l2 = LR2.first, r2 = LR2.second;
assert(l1 <= l2 && l2 <= i && i <= r2 && r2 <= r1);
// 计算四个部分的和
int len_l2_i = i - l2; // [l2,x]
ll sum_l2_i = (ll)len_l2_i * (len_l2_i + 1) / 2;
int len_i_r2 = r2 - i; // [i, r2]
ll sum_i_r2 = (ll)len_i_r2 * (len_i_r2 + 1) / 2;
ll sum_l1_l2 = (ll)i * (sum[l2 - 1] - sum[l1 - 1]) - (sum1[l2 - 1] - sum1[l1 - 1]); // [l1, l2 - 1]
ll sum_r2_r1 = (sum1[r1] - sum1[r2]) - (sum[r1] - sum[r2]) * (ll)i; // [r2 + 1, r1]
cout << sum_l1_l2 + sum_l2_i + sum_i_r2 + sum_r2_r1 << " \n"[i == n]; // 输出结果
}
}
// 主函数
int main() {
cin.tie(nullptr)->sync_with_stdio(false); // 提高输入输出速度
int t;
cin >> t; // 输入测试用例数量
while (t--) {
solve(); // 解决每个测试用例
}
return 0;
}
L3-3 攀岩
未完待续...
后记
192拿到个人国三，今年差三十来分分就团队国二了，记录一下。
今年L1就猫娘那题没拿满 12/15 ，题意实在难理解，拿到 12 分就跑。L2-4 应该没有人像我一样从 1 遍历到 100 最终找到两个样例拿到两分了吧？
其他内容后面更新。
( ╹ ▽ ╹ )
