写在前面：寒假之前报名了牛客的寒假算法训练营，当时没有好好参加，主要还是自己太菜，正好临近五一，所以计划每天学习一下当时比赛时候的题目和相关算法，因为这次训练营的题目是针对竞赛的，所以很多知识点我都还没学过，所以这里只记录一下相对来说简单一点的题目，后续学习了相关知识点后会持续补充~
官方题解地址:https://ac.nowcoder.com/discuss/364600?type=101&order=0&pos=1&page=3&channel=-1
A. honoka和格点三角形
因为是格点三角形且面积为1，所以只存在两种形式的三角形：底为2高为1的和底为1和高为2的，题目还要求三角形至少有一条边是与坐标轴平行的，所以我们再分为两条边都平行和只有一条边平行这两类进行讨论：
贴张我自己的笔记：
note
代码：
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
LL n,m;
int main()
{
LL ans = 0;
cin>>n>>m;
//两边平行
ans = 4 * ((n-1)*(m-2)%mod + (n-2)*(m-1)%mod)%mod;
//底边与x轴平行
ans = (ans + 2 *(n-1)*(m-2)%mod*(m-2) + 2*(m-1)*(n-2)%mod*(n-2)%mod)%mod;
//底边与y轴平行
ans = (ans + 2 * (m-1)*(n-2)%mod*(m-2)%mod + 2*(n-1)*(m-2)%mod*(n-2)%mod)%mod;
cout<<ans<<endl;
return 0;
}
G.eli和字符串
对每个字母都预处理一个数组，然后用尺取法(双指针)对26个数组依次进行扫描，更新答案
代码：
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <unordered_map>
using namespace std;
const int N = 200100;
string s;
int n,k;
int a[30][N];
int main()
{
cin>>n>>k;
cin>>s;
s = " " + s;
//预处理
for(int i = 0; i<26; i++){
for(int j = 1; j<=n; j++)
if(s[j] == ('a' + i))
a[i][j] = 1;
}
int ans = 1e9;
for(int i = 0; i<26; i++){
int res = N,l = 1,r = 1,sum = 0;
while(1){
while(r<=n && sum<k) sum += a[i][r++];
if(sum < k) break;
res = min(res,r-l);
sum -= a[i][l++];
}
//cout<<res<<endl;
ans = min(ans,res);
}
if(ans == N) cout<<-1<<endl;
else cout<<ans<<endl;
return 0;
}
H.nozomi和字符串
也是用尺取法，找到满足条件的最大区间
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
string s;
int n,k;
//尺取法
int solve(char a,char b){
int l = 0, r = 0,cnt = 0,res = 1;
for(int i = 0; i<n; i++){
if(s[i] == a){
if(cnt <k){
cnt++;
r++;
}
else{
while(l<=r && s[l] != a) l++;
l++,r++;
}
}
else r++;
res = max(res,r-l);
}
return res;
}
int main()
{
cin>>n>>k>>s;
int ans = max(solve('0','1'),solve('1','0'));
cout<<ans<<endl;
return 0;
}
I.nico和niconiconi
DP问题，dp[i]表示前i个字符的最大得分，状态转移方程为：
if(s.substr(i - 3, 4) == "nico")then dp[i] = max(dp[i],dp[i - 4] + a)
if(s.substr(i - 5, 6) == "niconi")then dp[i] = max(dp[i],dp[i- 6] + b)
if(s.substr(i - 9,10) == "niconiconi")then dp[i] = max(dp[i], dp[i - 10]+ c)
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
const int N = 300010;
int a,b,c;
int n;
long long dp[N];
string s;
int main()
{
cin>>n>>a>>b>>c>>s;
s = " " + s;
long long ans = 0;
if(n>=4){
for(int i = 1; i<=n; i++){
dp[i] = dp[i-1];
if(i>=4)
if(s.substr(i-3,4) == "nico")
dp[i] = max(dp[i-4] + a,dp[i]);
if(i>=6){
if(s.substr(i-5,6) == "niconi")
dp[i] = max(dp[i-6] + b,dp[i]);
}
if(i>=10){
if(s.substr(i-9,10) == "niconiconi")
dp[i] = max(dp[i-10] + c,dp[i]);
}
}
ans = dp[n];
}
//for(int i = 1; i<=n; i++) cout<<dp[i]<<endl;
cout<<ans<<endl;
return 0;
}
至此，day-1还有一个图论题，一个数论题，后面再更新~
2020 4.30 凌晨0.27分，顶不住了，溜了。
网友评论