比赛链接
A. Two Screens
简单对前面相同的个数进行判断即可
点击查看代码
#include<bits/stdc++.h>#define int long long
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
void solve() {string a,b;cin>>a>>b;if(a.size()>b.size()){swap(a,b);}int same=0;for(int i=0;i<a.size();i++){if(a[i]==b[i])same++;else break;}if(same==0){cout<<a.size()+b.size()<<'\n';}else {cout<<1+a.size()+b.size()-same<<'\n';}
}
signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int _=1;cin>>_;while(_--)solve();
}
B. Binomial Coefficients, Kind Of
快速打表发现为2的冥次 当且仅当i==j时为1
点击查看代码
#include<bits/stdc++.h>#define int long long
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
const int mod=1e9+7;
int qpw(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
void solve() {int n;cin>>n;vector<int>a(n),b(n),c;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++){if(a[i]==b[i]){c.pb(1);}else {c.pb(qpw(2,b[i]));}}for(auto i:c){cout<<i<<'\n';}
}
signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int _=1;
// cin>>_;while(_--)solve();
}
C. New Game
用队列维护前连续数对的值
然后通过每组都进行取mx即可
点击查看代码
#include<bits/stdc++.h>#define int long long
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
const int mod=1e9+7;
int qpw(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
void solve() {map<int,int>mp;int n,k;cin>>n>>k;queue<int>q;set<int>s;for(int i=0;i<n;i++){int x;cin>>x;mp[x]++;s.insert(x);}int mx=0,sum=0;for(auto &son:s){if(q.size()==k){int qp=q.front();q.pop();mx=max(mx,sum);sum-=mp[qp];}if(q.size()<k&&mp[son-1]){q.push(son);sum+=mp[son];}else {mx=max(mx,sum);while(q.size())q.pop();sum=0;sum+=mp[son];q.push(son);}}mx=max(mx,sum);cout<<mx<<'\n';
}
signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int _=1;cin>>_;while(_--)solve();
}
D. Attribute Checks
发现m很小 但是n很大
于是对m进行维护
对于每个地方的值 其后方能获得的通过数是固定的
于是提前预处理掉 该处的值
其他的就是m^2的转移
唯一需要注意的点就是转移时还需要注意 分别讨论智力增长和力量增长（wa8）
点击查看代码
#include<bits/stdc++.h>//#define int long long
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
const int mod=1e9+7;
int qpw(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}
void solve() {int n,m;cin>>n>>m;vector<int>a(n+1);vector cnt1(m+1,vector<int>(m+1));vector cnt2(m+1,vector<int>(m+1));vector dp(m+1,vector<int>(m+1));for(int i=1;i<=n;i++)cin>>a[i];int last=0;int ret=0;for(int i=1;i<=n;i++){if(!a[i])last=++ret;else if(a[i]>0){cnt1[last][a[i]]++;}else {cnt2[last][abs(a[i])]++;}}for(int i=1;i<=last;i++){for(int j=1;j<=i;j++){cnt1[i][j]+=cnt1[i][j-1];cnt2[i][j]+=cnt2[i][j-1];}}int mx=0;for(int i=1;i<=last;i++){for(int j=0;j<=i;j++){dp[i][j]=max(dp[i][j],dp[i-1][j]+cnt1[i][j]+cnt2[i][i-j]);if(j>=1){dp[i][j]=max(dp[i][j],dp[i-1][j-1]+cnt1[i][j]+cnt2[i][i-j]);}mx=max(mx,dp[i][j]);}}for(int j=0;j<=last;j++)mx=max(mx,dp[last][j]);cout<<mx<<'\n';
}
signed main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int _=1;
// cin>>_;while(_--)solve();
}
