今天又是读题困难的一天，题目读不懂要多看看，结合样例
A - Skibidus and Amog’u
其实就是阅读理解，读懂之后很好做，
#include<bits/stdc++.h>
using namespace std;
char s[50];
int main() {int t;cin>>t;while(t--){cin>>s+1;int n=strlen(s+1);for(int i=1;i<=n-2;i++){cout<<s[i];}cout<<"i";cout<<endl;}return 0;
}
B - Skibidus and Ohio
索引一般指的是下标，就是对于这个下标范围满足什么情况
#include<bits/stdc++.h>
using namespace std;
char s[50];
int main() {int t;cin>>t;while(t--){cin>>s+1;int n=strlen(s+1);int ans=n;for(int i=1;i<=n-1;i++){if(s[i]==s[i+1]){ans=1;}}cout<<ans<<endl;}return 0;
}C - Skibidus and Fanum Tax (easy version)
这题简单一些， M = 1 M=1 M=1 ，其实对于每个 A [ i ] A[i] A[i]来说要么维持自己不变，要么就用 B [ 1 ] B[1] B[1]来操作一下
注意当两种方法都可以满足题目意思的话，你要取最小的那种方法，让A的值尽量小还能满足要求才能使得后面的A有更大的发挥空间
给你两个数组A B
A的长度N
B的长度M=1 对于每个A数组的元素A[i] 我们至多可以操作一次
从B当中选一个数，然后把A[i]变为B[j]-A[i] 1 不改变
2 用B1-A【i】改变
问能不能使得a1<=a2<=a3....首先对于A1 b1-a1 取min
接下来 对于i>=2 来说 B[1]-A[i] A[i] 看看谁更小并且还能>=A[i-1] 如果不行 那么NO D - Skibidus and Fanum Tax (hard version)
这个题的区别就是 M M M取值范围是 2 e 5 2e5 2e5
意思就是说 A [ i ] A[i] A[i]的选择可以是任选一个 B [ j ] B[j] B[j]来做减法。
给你两个数组A B
A的长度N
B的长度M=2e5 课堂笔记推导 自己仔细看看 这个题要用到二分 对于每个A数组的元素A[i] 我们至多可以操作一次
从B当中选一个数，然后把A[i]变为B[j]-A[i] 先给B数组排序 A1 B[1]-A[1] 选择最小的 对于后面A[2~N] 它可以选择 A[i] B[?]>=x 你要找 B数组里面，满足这个式子最小的位置 B[1..mid....N] 二分 一分为二 B[mid]>=x 只需要logM次 就可以找到合适的B
#include<bits/stdc++.h>
using namespace std;
int A[200010],B[200010];
int main(){int t;cin>>t;while(t--){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>A[i];}for(int i=1;i<=m;i++){cin>>B[i];}sort(B+1,B+1+m);bool ok=true;A[1]=min(B[1]-A[1],A[1]);for(int i=2;i<=n;i++){int l=1,r=m;while(l<r){// 二分 int mid=(l+r)/2;if(B[mid]>=A[i-1]+A[i]){r=mid;}else l=mid+1;}if(B[r]>=A[i-1]+A[i]){ // 再次检验二分出来的答案行不行 if(A[i]>=A[i-1]){ //如果行的话，还要检查 直接保留原本的A【i】行不行 A[i]=min(A[i],B[r]-A[i]);}else{ //如果只有用操作才能行的话 那么A[i]是不是必须要变 A[i]=B[r]-A[i];}}else{//如果用操作 找不到答案 if(A[i]>=A[i-1]){ //判断不变 能不能行 continue; }ok=false;break;}}if(ok)cout<<"YES";else cout<<"NO";cout<<endl;}return 0;
} E - Skibidus and Sigma
一定要在做题的时候学会读题，
对于一个数组 A[1...N]
定义前i个元素的和=S[i]
定义分数为S[1]+S[2]+S[3]+....S[N] 现在题目给你N个数组 每个数组M个数 现在你可以把N个数组，任意排列 想问 最终N个数组排列后，n*m个数字的大数组
想求大数组最终最大的分数是多少 假设P是最终大数组 P[1] P[2] P[3] P[4] .... P[n*m]
前i个数的和 S[i]
分数 S[1]+S[2]+...S[n*m]P[1] P[1]+P[2]P[1+..3]P[1+..4]所以怎么办？ 先求N个数组的总和 然后按总和从大到小排序() 然后就正常算分数即可 #include<bits/stdc++.h>
using namespace std;//C++里面STL容器的一种
vector<数据类型>变量名; 不定长数组 从0开始编号
举例 vector<int>G;这是一个不定长数组G，数据类型是int vector<int>G[100]; 二维 string 字符串类型 属于不定长字符串
string s[100];
int main(){如何操作? vector<数据类型>变量名; 不定长数组 从0开始编号 举例 vector<int>G;这是一个不定长数组G，数据类型是int vector<int>G[100]; 二维 G[i].push_back(x); 存入一个x到G的末尾 如何获取当前有多少个元素在里面呢 G.size() 如何枚举vector内部元素?通常首先 先求里面有多少个元素 int num=G.size();for(int i=0;i<num;i++){if(G[i]>=2){}} return 0;
} #include<bits/stdc++.h>
using namespace std;
struct pe{long long int S;int pos;
}A[200010];
bool cmp(pe x,pe y){return x.S>y.S;
}
vector<long long int>B[200010];
int main(){int t;cin>>t;while(t--){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){A[i].S=0;A[i].pos=i;for(int j=1;j<=m;j++){long long int x;cin>>x;A[i].S=A[i].S+x;B[i].push_back(x);}}sort(A+1,A+1+n,cmp);long long int ans=0;long long int cnt=0;for(int i=1;i<=n;i++){for(int j=0;j<m;j++){cnt=cnt+B[A[i].pos][j];ans=ans+cnt;}B[i].clear();}cout<<ans<<'\n';}return 0;
} 今天顺带还复习了一下前缀和
前缀和 针对一个数组做数据维护
A[1...N]
定义前缀和S[i] = A[1]+A[2]+...+ A[i-1]+A[i]
S[i]=S[i-1]+A[i] for(int i=1;i<=n;i++){S[i]=S[i-1]+A[i];
}
O(N)
怎么用？ 求区间A[L...R]和 cout<<S[R]-S[L-1] ; S[R]=A[1]+A[2]+..A[L-1]+A[L]+...A[R] for(int i=L;i<=R;i++){s=s+A[i];
} 二位前缀和
A[n][m]
给你一个二维数组 求其中某一块矩形的总和 定义二位前缀和S[i][j] 为以(1,1)为左上点 以(i,j)为右下点构成矩形的总和 S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+A[i][j] 给定目标矩形左上点(x,y) 右下点(p,q)
如何求解该区域的总和？ S[p][q] - S[x-1][q]-S[p][y-1] + S[x-1][y-1] 二位前缀和的理解需要自己画图去思考