前言:最后一题,哈希/字典树.毒瘤卡常.需要考虑下优化空间和时间.
A.悬崖
思路:
首先由于可以斜着跳,本质上在墙没有完全闭合之前都是可以,每次跳x米的.
需要注意的是 最开始的时候,x垂直跳的距离必须$\geq n$,否则直接摔死.
AC Code：
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
ll x,n;
cin>>x>>n;
if(x<n)
{
cout<<x<<endl;
return ;
}
cout<<n*x<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
B.数数
思路:
DFS的方式,等价于求一个等差数列:$1+3+5+7+9+11+..... d=2$
公式为:$\frac{1 + 1 + (n - 1)d}{x+1}$: (首项+尾项)*项数/2
AC Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
// 1+3+5+7+9+11+.....d=2
ll n;cin>>n;
// a_n=a1+(n-1)d
cout<<(1+1+(n-1)*2)*n/2<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("test.in","r",stdin);
solve();
return 0;
}
C.山楂
思路:
在不考虑,提前知道结论的情况下.
考虑两种DFS方式:
1. 按值贡献最大优先合并.
2. 按生成下一级糖果数量最多优先合并.
由于,每一层只有两种状态,只有9层.因此只有$2^{9}=512$不会超时.
当然需要注意的是对于合成方式1.同时还需要注意,在贡献相同的时候,应该优先合并数量多的.
而我们注意到 对3,取模的时候余数只有,$0,1,2$.注意讨论下更优解即可.
AC Code：
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
ll a[10];
ll ans;
void dfs(int u,ll score)
{
// cout<<u<<' '<<score<<endl;
if(u==9)
{
ans=max(ans,score);
return ;
}
a[u+1]+=a[u]/3;
dfs(u+1,score+(a[u]-a[u]%3)*u);
a[u+1]-=a[u]/3;
if(a[u]%3==0)a[u+1]+=a[u]/3,dfs(u+1,score+a[u]*u),a[u+1]-=a[u]/3;
else
{
if(a[u]%3==1)
{
if(a[u]==1)dfs(u+1,score);
else a[u+1]+=a[u]/3,dfs(u+1,score+a[u]*u),a[u+1]-=a[u]/3;
}else
{
if(a[u]==2)dfs(u+1,score);//无法合并
else if(a[u]==5)a[u+1]+=1,dfs(u+1,score+4*u),a[u+1]-=1;//4优先级高
else a[u+1]+=a[u]/3,dfs(u+1,score+a[u]*u),a[u+1]-=a[u]/3;
}
}
}
void solve()
{
for(int i=1;i<=8;i++)cin>>a[i];
dfs(1,0);
cout<<ans<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
D.切糕
思维题.
首先需要知道一个前提:
合法的括号：指对于一个字符串他的左括号数量和右括号一样多，且对于任意前缀左括号始终不小于右括号数。
字符串的前缀：指字符串的从第一个字符开始，到任意字符停止的一个字符串。
通过这个前提我们可以直接快速判断,括号序列是否合法,并且统计所有能切割的位置—左括号前缀数量==右括号前缀数量.
最后就是一个简单,组合数学的内容.切法就是:$C_n^{0}+C_n^{1}+.....C_n^{n}=2^n$
注意特判下,最后一个位置如果不满足$l==r$说明括号是不合法的.
并且最后一个位置并不算切法.相当于没切.因此需要 $n-1$
AC Code：
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
ll qmi(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
void solve()
{
string s;cin>>s;
int l=0,r=0;
ll res=0;
for(int i=0;i<s.size();i++)
{
if(s[i]==')')r++;
else l++;
if(l==r)res++;
if(l<r)
{
cout<<"-1"<<endl;
return ;
}
}
if(l!=r)
{
cout<<"-1"<<endl;
return ;
}
cout<<qmi(2,res-1)<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
E.筑巢
思路：
树形DP.
可以发现,题目存在明显的子结构问题.每一个点只有两个状态,选或者不选.
就相当于,每个点记录一个状态:以这个点为根的子树,所能产生的最大权.
初始化:$F[root]=w[root]$
状态转移就是$F[root]+=(F[child]+w(root->child)>0?F[child]+w(root->child):0)$
AC Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int e[N],ne[N],h[N],idx;
ll f[N],w[N];
void add(int a,int b,ll c)
{
e[idx]=b,ne[idx]=h[a],w[idx]+=c,h[a]=idx++;
}
ll ans=-llinf;
ll a[N];
void dfs(int u,int fa)
{
f[u]=a[u];
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j!=fa)
{
dfs(j,u);
if(f[j]+w[i]>0)f[u]+=f[j]+w[i];
}
}
}
void solve()
{
memset(h,-1,sizeof h);
int n;cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n-1;i++)
{
int a,b;
ll c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
dfs(1,-1);
// cout<<f[1][0]<<' '<<f[1][1]<<endl;
for(int i=1;i<=n;i++)ans=max(ans,f[i]);
cout<<ans<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
F.交换
思路：
最开始写的:哈希+逆操作.TLE了.
TLE Code：
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int n,m;
unordered_map<string,int>mp;
ll get(vector<ll>p)
{
ll ans=0;
int res=0;
for(int i=p.size()-1;i>=1;i--)
{
ans+=p[i]*(ll)pow(10,res);
if(p[i]==10)res+=2;
else res++;
}
return ans;
}
void solve()
{
cin>>n>>m;
vector<PII>a(n+1);
for(int i=1;i<=n;i++)cin>>a[i].first>>a[i].second; //读入操作
for(int i=n;i>=1;i--)
{
vector<ll>p(11);
for(int j=1;j<=10;j++)p[j]=j;//初始化排列
for(int j=i;j>=1;j--)//所有以i为起点的指令
{
swap(p[a[j].first],p[a[j].second]);
for(int len=10;len>=1;len--)
{
vector<ll>tmp(len+1);
for(int k=1;k<=len;k++)tmp[k]=p[k];
string s=to_string(get(tmp));
if(!mp.count(s))mp[s]=i-j+1;
else mp[s]=min(mp[s],i-j+1);
}
}
}
while(m--)
{
int k;
cin>>k;
vector<ll>p(k+1);
for(int i=1;i<=k;i++)cin>>p[i];
string s=to_string(get(p));
bool ok=true;
for(int i=1;i<k;i++)
if(p[i+1]<p[i])
{
ok=false;
}
if(ok)
{
cout<<"0"<<endl;
continue;
}
if(!mp.count(s))cout<<"-1"<<endl;
else cout<<mp[s]<<endl;
}
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
为什么会TLE.因为 map.每次查询是$O(\log n)$,和总字符串数量成正比.
而实际操作会得到的字符串有 $O(n^2*(10!+9!+8!+....1))$.
因此考虑,用字典树来优化查询的过程.变成O(length).
同时注意：由于操作产生的字符串 远远多余 任务查询的字符串.
因此,如果是先存操作会产生的字符串,后查询任务字符串是否在字典树上是会超内存的.
所以,我们应该是任务字符串存在字典树上,后操作产生字符串时,只要查询字典树上是否存在,从而说明能否还原即可.
总结下就是:
先预处理查询字符串,插到字典树上.
然后将操作过程,逆着来一遍.对于产生的字符串,查询其是否在字典树上.如果是就说明可以还原.并更新其还原的最小值.
注意特判下:已经是升序的.
AC Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=4e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int n,m;
int son[N][10],idx;
int mp[N];//映射值
int insert(string s)
{
int p=0;
for(auto c:s)
{
int u=c-'0';
if(!son[p][u])son[p][u]=++idx;
p=son[p][u];
}
return p;
}
int find(string s)
{
int p=0;
for(auto c:s)
{
int u=c-'0';
if(!son[p][u])return 0;//不存在
p=son[p][u];
}
return p;//返回最后一个字母的下标
}
bool check(string s)
{
vector<int>tmp={1,2,3,4,5,6,7,8,9};
for(int i=1;i<s.size();i++)
{
int cur,last;
if(s[i]=='0')cur=10;
else cur=tmp[(int)(s[i]-'0')-1];
if(s[i-1]=='0')last=10;
else last=tmp[(int)(s[i-1]-'0')-1];
// cout<<last<<' '<<cur<<endl;
if(cur<last)return false;
}
return true;
}
void solve()
{
/* string s="321";
if(check(s))cout<<"YES"<<endl;
else cout<<"NO"<<endl;*/
memset(mp,inf,sizeof mp);
cin>>n>>m;
vector<PII>a(n+1);
vector<int>ans(m+1);
for(int i=1;i<=n;i++)cin>>a[i].first>>a[i].second; //读入操作
for(int i=1;i<=m;i++)//读入m个任务,并存到字典树上.
{
string tmp="1234567890";
string s;
int k;cin>>k;
for(int j=1;j<=k;j++)
{
int x;cin>>x;
s+=tmp[x-1];
}
int pos;
if(!find(s))pos=insert(s);
else pos=find(s);
ans[i]=pos;
if(check(s))
{
// cout<<s<<endl;
mp[pos]=0;
}
}
for(int i=n;i>=1;i--)
{
string s="1234567890";
for(int j=i;j>=1;j--)//所有以i为起点的指令
{
swap(s[a[j].first-1],s[a[j].second-1]);
for(int len=10;len>=1;len--)
{
string tmp;
for(int k=0;k<len;k++)tmp+=s[k];
if(find(tmp))
{
int pos=find(tmp);
mp[pos]=min(mp[pos],i-j+1);
}
}
}
}
for(int i=1;i<=m;i++)
{
if(mp[ans[i]]==inf)cout<<"-1"<<endl;
else cout<<mp[ans[i]]<<endl;
}
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
