SMU Summer 2023 Contest Round 1
A - The Contest
思路：求出最短解决问题总时间，在所有区间找出大于等于总时间的最短时刻。
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;
void solve(){
int n,m,s=0,ans=-1;cin>>n;
for(int i=0,x;i<n;++i){
cin>>x;s+=x;
}
cin>>m;
for(int i=0,l,r;i<m;++i){
cin>>l>>r;
if(ans==-1&&r>=s)ans=max(l,s);
}
cout<<ans;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}
View Code
B - The Golden Age
思路：记录所有unlucky year，找出[l，r]里最大长度的连续lucky year
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e6+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;
void solve(){
int x,y,l,r;
int ans=0;
cin>>x>>y>>l>>r;
set<int>se;
for(__int128 a=1;a<=(__int128)r;a*=(__int128)x)
for(__int128 b=1;a+b<=(__int128)r;b*=(__int128)y)
se.insert((int)(a+b));
int last=l;
for(auto i:se){
if(i<l)continue;
ans=max(ans,i-last);
last=i+1;
}
ans=max(ans,r-last+1);
cout<<ans;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}
View Code
C - The Tag Game
思路：求出Alice 和 Bob 到各个点的最短路，若disA[i]<disB[i]说明Alice可以比Bob先到达i点，那么B追上A的时间即为disB*2，遍历所有点求出最大的时间
#include<bits/stdc++.h>
using namespace std;
//#define int long long
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;
vector<int>dis1,dix;
vector<int>ve[N];
void dfs(int u,int fa,vector<int>&dis){
dis[u]=dis[fa]+1;
for(auto v:ve[u]){
if(v==fa)continue;
dfs(v,u,dis);
}
}
void solve(){
int n,x;cin>>n>>x;
dis1=vector<int>(n+1,0);
dix=vector<int>(n+1,0);
for(int i=2,u,v;i<=n;++i){
cin>>u>>v;
ve[u].push_back(v);
ve[v].push_back(u);
}
dfs(1,0,dis1);
dfs(x,0,dix);
int ans=0;
for(int i=2;i<=n;++i){
if(dix[i]<dis1[i]){
ans=max(ans,dis1[i]*2);
}
}
cout<<ans-2;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}
View Code
D - Two Melodies
题意：给一个序列，选出两个不重复的子序列，两个子序列中满足相邻的元素差为1或同余7，且两个子序列长度和最大。
思路：dp[i][j]表示以i和j结尾的子序列的最大长度。
这里固定i，dp[i][j]的状态转移：dp[i][k]+1（k<j），a[k]是所有能和a[j]相邻的元素中的dp[i][k]值最大的一个。
k为0时，
直接找到a[k]的方法：用maxn[j]表示前j个元素中最大的dp[i][j]的值，maxm[j%7]表示前j个元素中最大的dp[i][j%7]的值。
更新maxn，maxm：每转移一次dp[i][j]，更新下当前的maxn[j]，maxm[j]
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=5e3+5,M=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;
typedef long long ll;
int dp[N][N];
int maxn[M],maxm[10];
void solve(){
int n,ans=0;cin>>n;
vector<int>a(n+1);
for(int i=1;i<=n;++i)cin>>a[i];
for(int i=0;i<=n;++i){
memset(maxn,0,sizeof maxn);
memset(maxm,0,sizeof maxm);
for(int j=1;j<=i;++j){
maxn[a[j]]=max(maxn[a[j]],dp[i][j]);
maxm[a[j]%7]=max(maxm[a[j]%7],dp[i][j]);
}
for(int j=i+1;j<=n;++j){
dp[i][j]=max(dp[i][j],dp[i][0]+1);
dp[i][j]=max(dp[i][j],maxn[a[j]-1]+1);
dp[i][j]=max(dp[i][j],maxn[a[j]+1]+1);
dp[i][j]=max(dp[i][j],maxm[a[j]%7]+1);
dp[j][i]=dp[i][j];
maxm[a[j]%7]=max(maxm[a[j]%7],dp[i][j]);
maxn[a[j]]=max(maxn[a[j]],dp[i][j]);
ans=max(ans,dp[i][j]);
}
}
cout<<ans;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}
View Code
标签：Summer,typedef,const,Contest,int,SMU,long,solve,dp From： https://www.cnblogs.com/bible-/p/17554343.html