A - DZY Loves Hash
水题，开辟一个数组即可
#include <iostream>
#include <vector>
#include <algorithm>
#include <string> using namespace std; int main(){
int p,n;
cin >> p >> n;
vector<bool> buckets(,false);
bool flag = false;
vector<int > x(n);
for(int i = ; i < n ; ++i) cin >> x[i];
int i = ;
for(i = ; i < n; ++i){
if(!buckets[x[i]%p]) buckets[x[i]%p] = true;
else{ cout<<i+<<endl; break;}
}
if(i >= n) cout<<-<<endl;
}
开辟一个数组即可
B - DZY Loves Strings
先把给定的字符的值求出来，然后插入权重最大的值即可
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
using namespace std; int main(){
string s;
int k;
vector<int> w(,);
cin >>s >> k;
for(int i = ; i < ; ++ i) cin >>w[i];
long long res = ;
for(int i = ;i < s.length(); ++ i){
res+=w[s[i]-'a']*(i+);
}
sort(w.begin(),w.end());
for(int i =s.length(); i < s.length()+k; ++ i){
res+=w[]*(i+);
}
cout<<res<<endl;
}
C - DZY Loves Sequences
题目的意思是给定一个序列，然后找出一个子序列，改变子序列的一个值，使该子序列严格单调递增，求出满足上述要求最长子序列的长度。
注意一定要是单调递增
思路是将数组分块，每一块都是严格单调递增的
如 7 2 3 1 5 6
分组后为 [7], [2,3], [1,5,6]，影响长度的是组与组之间的间隔
现在记录下每一个组的开始索引和结束索引，以及长度，所求最大子序列长度有三种可能
（1）如果该数组只有一个分组，则该长度就是所求结果的长度
（2）max（每个分组的长度+1），即就是每个分组的长度+改变与其相邻元素的值的最大值
（3）两个分组合并后的值即max(分组 i + 分组 i+1 )的值，注意这里分组有两种情况种情况
假设分组后两组元素为[astart1 .... aend1], [astart2 ..... aend2]，注意这两组元素是相邻的即 start2 == end1+1
要满足严格单调递增的情况必须满足 astart2+1-aend1 > 1 或者 astart2 - aend1-1 >1, 要像下面的用例一样[1,2,5],[4,5,7]即可
如果下面的用例
a、[1,2,4],[3,6,7]这两个分组无法合并 ，因为astart2 -aend1-1 <=1
b、[1,2,5],[3,5,7]这两个分组无法合并, 因为astart2+1-aend1 <=1
#include <iostream>
#include <vector>
#include <algorithm>
#include <string> using namespace std; struct Node{
int startIdx;
int endIdx;
Node(int a = ,int b = ): startIdx(a),endIdx(b){};
int getLength(){return endIdx-startIdx+;}
}; int main(){
int n;
cin >>n;
vector<int> a(n+,);
vector<Node> aux;
for(int i = ;i <=n ; ++i) cin >> a[i];
int startIdx = , maxLength = ;
bool flag = false;
for(int i = ; i < n ; ++i){
if(a[i] < a[i+]){
if(!flag) {startIdx = i;flag = true;}
}else{
aux.push_back(Node(startIdx,i));
maxLength = max(maxLength,i-startIdx+);
startIdx = i+;
flag = false;
}
}
if(startIdx == n ) {aux.push_back(Node(n,n));maxLength = max(maxLength,);}
else {aux.push_back(Node(startIdx,n));maxLength=max(maxLength,n-startIdx+);}
for(int i = ; i < aux.size()-; ++ i){
if(aux[i+].startIdx+<=aux[i+].endIdx && a[aux[i+].startIdx+]-a[aux[i].endIdx] > ) maxLength =max(maxLength,aux[i+].getLength()+aux[i].getLength());
if(aux[i].endIdx->=aux[i].startIdx && a[aux[i+].startIdx]-a[aux[i].endIdx-] > ) maxLength =max(maxLength,aux[i+].getLength()+aux[i].getLength());
maxLength =max(maxLength,aux[i].getLength()+);
}
if(aux.size() > ) maxLength =max(maxLength,aux[aux.size()-].getLength()+);
cout<<maxLength<<endl;
}
D - DZY Loves Modification
题目的意思是有一个nxm的矩阵，通过k次操作修改这个矩阵，每次操作包含下面任何一个：
- 挑选某行，然后累加该行获得pleasure值，然后该行的每个元素都减去p
- 挑选某列，然后累加该列获得pleasure值，然后该列的每个元素都减去p
通过k次操作后，求所有操作pleasure值最大是多少？注意k的范围是10^6，不能通过暴力解决
解题思路：
这种题目可以通过手动模拟小数据，了解其过程。每次选取的行或列都应该根据贪心从大到小选取，选择行和选择列顺序是无关的
设选取了 i 行，则选取了k-i 列，
假设先选取了i行，然后选取列，则选取列的时候跟选取行相交的元素多减去了p，故选取列的时候在原有列的基础上少了i*p（该列与i行肯定相交），由于列与列选取互不相影响
选取k-i列比初始列的值少了i*p*(k-i)
故只需要在初始矩阵上求出选取i行，选取k-i行的pleasure值，然后减去i*p*(k-i)即可，最后取个最大值
需要注意的地方是：每行可以操作多次
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <functional>
#include <utility>
#define LL long long
using namespace std; struct Node{
int index;
LL sum;
Node(int idx = , LL su = ):index(idx), sum(su){}
bool operator < (const Node& a)const{
return sum < a.sum;
}
}; int main(){
LL n,m,k,p;
cin >>n >> m >> k >>p;
vector<vector<int> > a(n,vector<int>(m,));
for(int i = ; i <n ; ++ i){
for(int j = ; j < m ; ++ j){
cin >> a[i][j];
}
} vector<Node> rowSum(n),colSum(m);
for(int i = ; i < n; ++ i ){
LL sum = ;
for(int j = ; j < m ; ++ j) sum+=a[i][j];
rowSum[i]=Node(i,sum);
}
for(int j = ; j < m; ++ j){
LL sum = ;
for(int i = ; i < n ; ++ i) sum+=a[i][j];
colSum[j]=Node(j,sum);
} priority_queue<Node> que;
vector<LL> rowRes(k+,),colRes(k+,);
for(int i = ; i < n; ++i) que.push(rowSum[i]);
int cnt = ;
LL res = ;
while(!que.empty()&& cnt< k){
Node row =que.top(); que.pop();
cnt ++;
res+=row.sum;
rowRes[cnt] = res;
row.sum-=m*p;
que.push(row);
}
que=priority_queue<Node>();
for(int i = ; i < m; ++i) que.push(colSum[i]);
cnt = ;res = ;
while(!que.empty()&& cnt< k){
Node col =que.top(); que.pop();
cnt ++;
res+=col.sum;
colRes[cnt] = res;
col.sum-=n*p;
que.push(col);
}
LL maxRes = -1e18;
for(int i = ; i <= k; ++i){
maxRes = max(maxRes,rowRes[i]+colRes[k-i]-i*(k-i)*p);
}
cout<<maxRes<<endl; }