Problem A:水题，直接gan
#include<bits/stdc++.h> using namespace std; const int N=305; int vis[N]; int main() { int p,n; cin>>p>>n; int flag=-1; for(int i=1;i<=n;i++) { int g; scanf("%d",&g); int now=g%p; if(!vis[now]) vis[now]=1; else { if(flag==-1) flag=i; } } if(flag==-1) puts("-1"); else printf("%d ",flag); return 0; }
Problem B:水题，写的时候手贱，<26打成<25 wa了五次！！！！！
#include<bits/stdc++.h> using namespace std; const int N=2*1e3; int vis[30]; int k,mx; char a[N]; int main() { mx=-10000; scanf("%s%d",a,&k); for(int i=0;i<=25;i++) { scanf("%d",&vis[i]); if(vis[i]>mx) mx=vis[i]; } int ans=0,len=strlen(a); for(int i=0;i<len;i++) ans+=(i+1)*vis[a[i]-'a']; int cnt=len+1; while(k--) { ans+=cnt*mx; cnt++; } printf("%d ",ans); return 0; }
Problem C:
题目大意：给你n个数，求连续上升子序列，你将其中一个数该为任意值。
第一个思路：二分答案，看满不满足，可是判断满足的算法是n^2的 不行。
第二个思路：每个断点的前后都是上升序列，枚举这些段。。。这个算法按道理
是可以过的，可是写起来好麻烦啊啊啊啊啊，wawawawawa。
题解：先预处理处每个点的之前上升前缀和之后的上升前缀
枚举没点点当断点
if(a[i+1]-a[i-1]>1)
dp[i]=up[i-1]+down[i+1]+1;
else dp[i]=max(up[i-1],down[i+1])+1;
更新。。
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; int n,a[N],up[N],down[N],dp[N]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); up[1]=1; for(int i=2;i<=n;i++) { if(a[i]>a[i-1]) up[i]=up[i-1]+1; else up[i]=1; } down[n]=1; for(int i=n-1;i>=1;i--) { if(a[i]<a[i+1]) down[i]=down[i+1]+1; else down[i]=1; } dp[1]=1+down[2]; dp[n]=1+up[n-1]; for(int i=2;i<n;i++) { if(a[i+1]-a[i-1]>1) dp[i]=up[i-1]+down[i+1]+1; else dp[i]=max(up[i-1],down[i+1])+1; } int ans=-1; for(int i=1;i<=n;i++) ans=max(ans,dp[i]); printf("%d ",ans); return 0; }
Problem D:
题目大意：给你一个n*m的矩阵，给你k个操作，每个操作你可以选其中一行或者其中一列，把他们的和加到ans中，然后这
一行或这一列每个元素减去p，让你求k个操作后ans的最大值。
题解：我们可以这么想，每当我们选取一行（列）时，每一列（行）都减去一个p，这样的话选取之后在列（行）中他们的
相对大小没有变化，所以行和列是完全可以独立开的，如果行数和列数都确定了这个ans值就是确定的和顺序没有关系。
本来我想用两个优先队列存行和列，然后模拟k次，每次取其中的最大值，可是这样是有bug的，正确做法是枚举行数和列数
取其中的最大值。
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e3+5; const int M=1e6+1; ll n,m,k,p; ll w[N][N]; ll c[M],r[M]; int main() { scanf("%I64d%I64d%I64d%I64d",&n,&m,&k,&p); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%I64d",&w[i][j]); priority_queue<ll> col,row; for(int i=1;i<=n;i++) { ll ans=0; for(int j=1;j<=m;j++) ans+=w[i][j]; col.push(ans); } for(int j=1;j<=m;j++) { ll ans=0; for(int i=1;i<=n;i++) ans+=w[i][j]; row.push(ans); } for(int i=1;i<=k;i++) { ll now=col.top();col.pop(); c[i]=c[i-1]+now; col.push(now-m*p); } for(int i=1;i<=k;i++) { ll now=row.top();row.pop(); r[i]=r[i-1]+now; row.push(now-n*p); } ll ans=c[0]+r[k]; for(ll i=1;i<=k;i++) { if((c[i]+r[k-i]-i*(k-i)*p)>ans) ans=c[i]+r[k-i]-i*(k-i)*p; } printf("%I64d ",ans); return 0; }