|
前面的碎碎念：
菜鸡差点爆0，题目有点不对胃口
牛客练习赛61
A、打怪
签到题，差点没签到成功
思路：
计算勇士砍死一个怪需要的次数，从而得到砍死一个怪需要消耗的血量，于是能砍死的怪物数量就等于自身血量除于需要消耗的血量，如果能整除则答案数减一，特判自身血量为0；
复杂度：\thetaθ (1)。
#include<bits/stdc++.h>
#define ll long long
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int t,n,m,a,b;
int main() {
js;
cin>>t;
while(t--) {
cin>>n>>m>>a>>b;
if(!n||!m) {
cout<<"0"<<endl;
continue;
}
int cnt=a/m+(a%m!=0);
int temp=cnt-1;
int ans=(n-1)/b;
if(m>=a) cout<<"-1"<<endl;
else cout<<ans/temp<<endl;
}
}
B、吃水果
贪心
思路：
又是差点没A，幸好是弱化版的可以直接模拟，因为y/x会随着x和y的一直减小而增大，为了让他们尽早相等而花费最小就要先翻倍再减，而不是一直减到1在翻倍（我这么写也就是想碰碰运气），假设x<y,最后一定要减y次，又因为y/x会增大而且保证有解，所以一定会翻y/x+(y%x!=0)次
Code：
复杂度：\thetaθ (n)
贪心代码：
复杂度：\thetaθ (1)
#include<bits/stdc++.h>
#define ll long long
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int t,x,y;
int main() {
js;
cin>>t;
while(t--) {
cin>>x>>y;
if(x>y) swap(x,y);
int ans=y;
while(x<y) {
x<=1;
++ans;
}
cout<<ans<<endl;
}
}
C.四个选项
题目大意：
有12个小块组成若干个连通块，每个连通块只能放一种物品，每个连通块能放下的体积等于小块的数量，共有4种物品总体积为12，求装完物品的方案数。
动态规划，数据小dfs也可以。
思路；
方法1.并查集 + dfs暴搜：递归所以方案并剪枝，最后判断是否符合题意：
复杂度：\thetaθ （12*4^{12}4
12
)
方法2.最先看到的就是钟涛大佬写出来的并查集 + dfs暴搜升级版：有点贪心的味道，将每个联通块的的体积排序后每种颜色都试试能不能放进去，放完后填下一个连通块。
复杂度：\thetaθ （4^{12}4
12
)
方法3.dp.状态：dp[i][a][b][c][d],表示处理到第i个联通块用了a个A,b个B,c个C,d个D的方案数，状态转移方程：dp[i]+=dp[i-1][a][b][c][d],dp[i]表示在dp[i-1][a][b][c][d]的状态上选v[i]个a或b或c或d来填满第i个连通块
复杂度：\thetaθ (n*4^3)
Code：
#include<bits/stdc++.h>
#define ll long long
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
ll dp[13][30][30][30][30];
int fa[13],size[13],v[13],a[5],tot,m;
int find(int x) {
return fa[x]?(fa[x]=find(fa[x])):x;
}
int main() {
js;
cin>>a[1]>>a[2]>>a[3]>>a[4]>>m;
while(m--) {
int i,j,x,y;
cin>>i>>j;
x=find(i),y=find(j);
if(x!=y) fa[x]=y;
}
for(int i=1;i<=12;++i) ++size[find(i)];
for(int i=1;i<=12;++i) if(size[i])
v[++tot]=size[i];
dp[0][0][0][0][0]=1;
for(int i=1;i<=tot;++i)
for(int j=0;j<=a[1];++j)
for(int k=0;k<=a[2];++k)
for(int u=0;u<=a[3];++u)
for(int w=0;w<=a[4];++w) if(dp[i-1][j][k][u][w]){
dp[i][j+v[i]][k][u][w]+=dp[i-1][j][k][u][w];
dp[i][j][k+v[i]][u][w]+=dp[i-1][j][k][u][w];
dp[i][j][k][u+v[i]][w]+=dp[i-1][j][k][u][w];
dp[i][j][k][u][w+v[i]]+=dp[i-1][j][k][u][w];
}
cout<<dp[tot][a[1]][a[2]][a[3]][a[4]]<<endl;
}
D、最短路变短了
又一次被模板虐了，Dijkstra算法。
要用到Dijkstra，没写过可以看看下面《算法入门到进阶》的模板：
思路：
从点1跑出到其他点的最短路数组dis[]
建反向图，从点n跑出到其他点的最短路数组bis[]
设我们要反向的边为u?>v，那么原图实际上可能更优的路径多了一条1->v->u->n。所以只要判断dis[v]+bis[u]+cost(u,v)<dis[n]是否成立就可以了。
注意：最短路的长度是ll型的，所以inf应该设为inf=0x3f3f3f3f3f3f3f3f，如果是int型就设0x3f3f3f3f，wa了一下。
#include<bits/stdc++.h>
#define ll long long
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const ll inf=0x3f3f3f3f3f3f3f3f;
struct edge{
int to,w;
edge(int a,int b) {to=a;w=b;}
};
vector<edge>e[100005],g[100005];
struct node{
int id;
ll dis;
node(int a,ll b) {id=a; dis=b;}
bool operator<(const node &a) const
{return dis>a.dis;}
};
int n,m;
ll dis[100005],bis[100005];
bool done[100005],bone[100005];
priority_queue<node>q;
void dijkstra1() {
int s=1;
dis[s]=0;
q.push(node(s,dis[s]));
while(!q.empty()) {
node u=q.top();
q.pop();
if(done[u.id]) continue;
done[u.id]=true;
for(int i=0;i<e[u.id].size();++i) {
edge y=e[u.id][i];
if(done[y.to]) continue;
if(dis[y.to]>y.w+u.dis) {
dis[y.to]=y.w+u.dis;
q.push(node(y.to,dis[y.to]));
}
}
}
}
void dijkstra2() {
int s=n;
bis[s]=0;
q.push(node(s,bis[s]));
while(!q.empty()) {
node u=q.top();
q.pop();
if(bone[u.id]) continue;
bone[u.id]=true;
for(int i=0;i<g[u.id].size();++i) {
edge y=g[u.id][i];
if(bone[y.to]) continue;
if(bis[y.to]>y.w+u.dis) {
bis[y.to]=y.w+u.dis;
q.push(node(y.to,bis[y.to]));
}
}
}
}
int u[100005<<1],v[100005<<1],c[100005<<1];
int main() {
js;
cin>>n>>m;
for(int i=1;i<=m;++i) {
cin>>u[i]>>v[i]>>c[i];
e[u[i]].push_back(edge(v[i],c[i]));
g[v[i]].push_back(edge(u[i],c[i]));
}
for(int i=1;i<=n;++i) dis[i]=bis[i]=inf;
dijkstra1();
dijkstra2();
int t; cin>>t;
while(t--) {
int x,i,j,p;
cin>>x; i=u[x],j=v[x],p=c[x];
ll temp=dis[j]+bis[i]+p;
if(temp<dis[n]) cout<<"YES\n";
else cout<<"NO\n";
}
}
E、相似的子串
思路：
题意要求k个有最长公共前缀长度为x且互不相交的x最大值，那么我们只要求k个位置长度为x的不相交的相等的子串，并且x最大。
方法一：后缀数组，具体原理我还不知道，只能被学长的代码劝退。
方法二：哈希+二分答案。
我们可以枚举长度x，如果有长度x的子串符合条件，那么我们会想着更大的x可不可以，如果x不行我们就想着x小点行不行，明显的二分答案，但是r=n+1，是防止mid=0带来麻烦。
然后我们可以\thetaθ(n)求出字符串每个位置的哈希值，然后由区间的哈希值确定子串，方便记录字串出现的次数。接着判断能否找到长度为x符合条件的子串遍历每一种字串，统计出现的次数记录在mp[ha].second里，同时mp[ha].first防止相同的子串出现重叠的现象，如果某个子串出现了k次就说明找到了。
注意：哈希因为不能映射到一个巨大的空间里，所以一班需要现在空间，一般方法是取余，其实这里也有取余，当哈希值超过232会自动对232取余，这就是哈希数组开ull的原因。seed开57，101也能a，开100只能过90，原因是因为取模后会有不一样的字符串的哈希值相同，一个有效的解决方法是把哈希值重复的字符串存到容器里。
#include<bits/stdc++.h>
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int maxn=2e5+5;
typedef unsigned long long ull;
unordered_map<ull,pair<int,int> >mp;
char s[maxn];
int n,k;
ull hs[maxn],po[maxn];
void Hash() {
ull seed=131;
po[0]=1;
for(int i=1;i<=n;++i) {
hs[i]=hs[i-1]*seed+s[i]-'a';
po[i]=po[i-1]*seed;
}
}
bool check(int x) {
mp.clear();
for(int i=x;i<=n;++i) {
ull ha=hs[i]-hs[i-x]*po[x];
if(i-mp[ha].first >= x) mp[ha].first=i,++mp[ha].second;
if(mp[ha].second>=k) return 1;
}
return 0;
}
int main() {
js;
cin>>n>>k>>s+1;
Hash();
int l=0,r=n+1,ans=0;
while(l+1<r) {
int mid=l+r>>1;
if(check(mid)) ans=l=mid;
else r=mid;
}
cout<<ans<<endl;
}
|