目錄
A - Similar Strings
B - card card card
C - String
D - Complete the Sequence
E - u Calculate e
F - Maximum Subrectangle
G - Producing Snow
A - Similar Strings
題意：
給定字元串A與字元串B，如果有A的子串A'與B的子串B'滿足條件：
- length(A')==length(B')
- A'與B‘在相同位置上最多有k個字元不同
我們就認為A'與B'棒極了。
現在我想知道A'與B'最長是多長?
思路：
對兩個字元串分别進行尺取。
- 不斷枚舉字元串B的子串B'的開始位置對字元串A進行尺取
- 不斷枚舉字元串A的子串A'的開始位置對字元串B進行尺取
-
考察點：字元串，尺取，枚舉，暴力
代碼：
#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int ans,k,t;
int len1,len2;
int main(){
cin>>t;
while(t--){
cin>>k;
cin>>s1;
cin>>s2;
ans=-1;
len1=s1.size(),len2=s2.size();
for(int i=0;i<len1;i++){
int l=0,r=0,cnt=0;
while(i+r<len1&&r<len2){
if(s1[i+r]!=s2[r])
cnt++;
while(cnt>k){
if(s1[i+l]!=s2[l])
cnt--;
l++;
}
ans=max(ans,r-l+1);
r++;
}
}
for(int i=0;i<len2;i++){
int l=0,r=0,cnt=0;
while(r<len1&&i+r<len2){
if(s1[r]!=s2[i+r])
cnt++;
while(cnt>k){
if(s1[l]!=s2[i+l])
cnt--;
l++;
}
ans=max(ans,r-l+1);
r++;
}
}
cout<<ans<<endl;
}
}
B - card card card
題意：
有一個長度為 n 的撲克牌序列a，當你拿第i張牌的時候有一個懲罰值bi，我們開始從第一張牌開始取牌，隻要拿的撲克牌點數之和不小于對應的懲罰值之和，則所拿撲克合法。
求在保證可以拿到的撲克牌點數之和最大的情況下，初始最少要拿幾張牌放到序列後面去？
思路：
首先既然需要将部分字元串放置在尾部，幹脆存兩倍長度（複制一份放在後面）。對序列進行尺取，分别計算(ai - bi)與ai的和，前者用來判斷取值結束，後者存儲最大值。
-
考察點：尺取，序列和
代碼：
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+100;
int a[maxn],b[maxn]; ///a[i]:第i張牌的價值 b[i]:第i張牌的懲罰值
int c[maxn]; ///c[i]:第i張牌的純收益 c[i]=a[i]-b[i]
int main()
{
int n;
ios::sync_with_stdio(false);
while(cin>>n)
{
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
cin>>b[i];
for(int i=0;i<n;i++)
c[i]=a[i]-b[i];
for(int i=n;i<2*n;i++)
c[i]=a[i%n]-b[i%n];
int l=0,r=0;
int sum=0,ans=0,sumc=0,cnt=0; ///ans：最大價值 sumc：目前收益 sum:目前的價值
while(l<n){
while(r<2*n&&sumc+c[r]>=0)
{
sumc+=c[r];
r++;
sum+=a[r];
}
if(sum>ans){
ans=sum;
cnt=l;
}
sumc-=c[l];
sum-=c[l];
l++;
}
cout<<cnt<<endl;
}
}
C - String
題意：
給定一個字元串S，求出S有多少個子串滿足：
子串S'中不同字母的數量至少有k個。
思路：
對字元串S進行尺取。
目前尺取出的子串S'若滿足條件，則以它為開始字元串的子串都滿足條件。
-
考察點：尺取，思維，字元串
代碼：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+100;
char ss[maxn];
int num[30];
int num_len()
{
int len=0;
for(int i=0;i<26;i++)
if(num[i]) len++;
return len;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
int k;
scanf("%s",ss);
scanf("%d",&k);
memset(num,false,sizeof(num));
ll ans=0;
int l=0,r=0,len=strlen(ss);
while(true){
while(num_len()<k&&r<len){
num[ss[r++]-'a']++;
}
if(num_len()<k)
break;
ans+=len-r+1;
num[ss[l++]-'a']--;
}
printf("%lld\n",ans);
}
}
D - Complete the Sequence
題意：
根據給定的長度為S的序列的規律算出接下來C個元素的值。
思路：
如果數學好的話不難看出這題用到了拉格朗日插值法。
簡而言之就是多元差分數組。
解釋樣例：
原始資料：1 1 1 1 1 1 1 1 1 2 11 56 一階差分：0 0 0 0 0 0 0 0 1 9 45 二階差分：0 0 0 0 0 0 0 1 8 36 三階差分：0 0 0 0 0 0 1 7 28 四階差分：0 0 0 0 0 1 6 21 五階差分：0 0 0 0 1 5 15 六階差分：0 0 0 1 4 10 七階差分：0 0 1 3 6 八階差分：0 1 2 3 九階差分：1 1 1
部落客比較笨，懂，但不知道怎麼描述。
-
考察點：拉格朗日插值，差分數組
代碼：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int num[500][500];
int main()
{
int t,s,c;
cin>>t;
while(t--){
cin>>s>>c;
for(int i=0;i<s;i++)
cin>>num[0][i];
for(int i=1;i<s;i++){
for(int j=0;j<s-i;j++)
num[i][j]=num[i-1][j+1]-num[i-1][j];
}
for(int i=1;i<s+c;i++)
num[s-1][i]=num[s-1][0]; //複制最後一層
for(int i=s-2;i>=0;i--){
for(int j=s-i;j<s+c;j++)
num[i][j]=num[i+1][j-1]+num[i][j-1]; //倒推上一層
}
for(int i=0;i<c;i++){
if(i) cout<<" ";
cout<<num[0][s+i];
}
cout<<endl;
}
return 0;
}
E - u Calculate e
題意：
對于題目中給定的公式，求出n取值從0到9時e對應的值，并按照規定格式輸出。
思路：
沒有思路，暴力打表，阿巴阿巴
-
考察點：暴力，枚舉
代碼：
#include<bits/stdc++.h>
using namespace std;
int main()
{
printf("n e\n");
printf("- -----------\n");
printf("0 1\n");
printf("1 2\n");
printf("2 2.5\n");
printf("3 2.666666667\n");
printf("4 2.708333333\n");
printf("5 2.716666667\n");
printf("6 2.718055556\n");
printf("7 2.718253968\n");
printf("8 2.718278770\n");
printf("9 2.718281526\n");
return 0;
}
F - Maximum Subrectangle
題意：
給定長度為n的序列a與長度為m的序列b，你可以得到一個n*m的矩陣c，滿足：
C( i , j )==Ai * Bj
現在找出C矩陣的最大子矩陣使得：
- 矩陣元素盡可能的多
- 矩陣和小于等于x
輸出這個矩陣的元素個數。
思路：
首先分别對序列a，序列b求字首和。
然後貪心出當序列a的子串長度為i時，序列a的子序列和的最小值，存儲起來。同時貪心出當序列b的子串長度為i時，序列b的子序列和的最小值，存儲起來。
接下來就通過兩個最小子序列和數組相乘得答案。
-
考察點：字首和，貪心
代碼：
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f
using namespace std;
typedef long long ll;
ll a[2005];
ll b[2005];
ll mina[2005];
ll minb[2005];
int main()
{
int n,m;
ll x;
cin>>n>>m;
a[0]=b[0]=0;
for(int i=1; i<=n; i++)
{
cin>>a[i];
a[i]+=a[i-1];
}
for(int i=1; i<=m; i++)
{
cin>>b[i];
b[i]+=b[i-1];
}
cin>>x;
memset(mina,inf,sizeof(mina));
memset(minb,inf,sizeof(minb));
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
mina[i]=min(mina[i],a[j]-a[j-i]);
for(int i=1;i<=m;i++)
for(int j=i;j<=m;j++)
minb[i]=min(minb[i],b[j]-b[j-i]);
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
//cout<<i<<" "<<j<<" "<<mina[i]*minb[j]<<endl;
if(mina[i]*minb[j]<=x){
ans=max(ans,i*j);
}
}
cout<<ans<<endl;
}
G - Producing Snow
題意：
每一天在你家門口會形成不同的雪堆。
每天早上形成高度為ai米的雪堆，晚上會因為溫度關系，所有雪堆最多減少bi米。
請給出每天晚上當天融化了多少雪？
思路：
對每天的雪的融化量求字首和。
對于每次的融化量考慮三種情況：
- 第i個雪堆高度大于等于融化量
- 第i個雪堆高度小于融化量
- 第i個雪堆高度為0
-
考察點：字首和，思維
代碼：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+100;
ll a[maxn],b[maxn],c[maxn];
ll sur[maxn],num[maxn];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
c[0]=0;
for(int i=1;i<=n;i++){
cin>>b[i];
c[i]=c[i-1]+b[i];
}
memset(num,0,sizeof(num));
for(int i=1;i<=n;i++){
int pos=upper_bound(c+1,c+1+n,a[i]+c[i-1])-c;
sur[pos]+=a[i]+c[i-1]-c[pos-1];
num[i]++;
num[pos]--;
}
ll cnt=0;
for(int i=1;i<=n;i++){
cnt+=num[i];
if(i!=1) cout<<" ";
cout<<sur[i]+cnt*b[i];
}
cout<<endl;
}