A:
思路：ans=自己能够挨的🔪数/一只怪物能挨的🔪数
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int main(){
int n; scanf("%d", &n);
for(int i=1; i<=n; i++){
int h, a, H, A;
cin>>h>>a>>H>>A;
int x=H/a+(H%a?1:0);
int y=x-1;//自己能够挨的🔪数
int s2=(h-1)/A;//一只怪物能够挨的🔪数
if(a>=H){
cout<<-1<<endl;
}
else
cout<<s2/y<<endl;
}
return 0;
}B:
思路：如果开始n>m2或者m>n2就一直翻倍。后面就一直吃。一直到一个是另外一个的2倍。再翻倍。就n=m
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int main(){
int t; scanf("%d", &t);
for(int i=1; i<=t; i++){
int n, m; scanf("%d%d", &n, &m);
int ans=0;
while(n>m*2){
m*=2;
ans++;
}
while(m>2*n){
n*=2;
ans++;
}
while(n!=m){
if(n==2*m||m==2*n){
n=max(n, m);
ans++;
break;
}
n--; m--;
ans++;
}
ans+=n;
cout<<ans<<endl;
}
return 0;
}C:
思路：用并查集处理一下必须染相同颜色的块。然后2^n。或者DP就可以了。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int f[20]={0};
int fd(int x){
if(f[x]==0) return x;
else return fd(f[x]);
}
int siz[20]={0}, tot=0, s[20]={0};
int v[20]={0};
LL F[20][20][20][20][20]={0};
int main(){
for(int i=1; i<=4; i++){
scanf("%d", &s[i]);
}
int m; scanf("%d", &m);
for(int i=1; i<=m; i++){
int x, y; scanf("%d%d", &x, &y);
x=fd(x); y=fd(y); if(x!=y) f[x]=y;
}
for(int i=1; i<=12; i++){
siz[fd(i)]++;
}
for(int i=1; i<=12; i++){
if(siz[i]){
v[++tot]=siz[i];
}
}
F[0][0][0][0][0]=1;
for(int i=1; i<=tot; i++){
for(int k1=0; k1<=s[1]; k1++){
for(int k2=0; k2<=s[2]; k2++){
for(int k3=0; k3<=s[3]; k3++){
for(int k4=0; k4<=s[4]; k4++){
if(F[i-1][k1][k2][k3][k4]){
F[i][k1+v[i]][k2][k3][k4]+=F[i-1][k1][k2][k3][k4];
F[i][k1][k2+v[i]][k3][k4]+=F[i-1][k1][k2][k3][k4];
F[i][k1][k2][k3+v[i]][k4]+=F[i-1][k1][k2][k3][k4];
F[i][k1][k2][k3][k4+v[i]]+=F[i-1][k1][k2][k3][k4];
}
}
}
}
}
}
printf("%lld\n", F[tot][s[1]][s[2]][s[3]][s[4]]);
return 0;
}D:
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=100005;
vector< pair<LL ,LL > > e[maxn], e2[maxn];
LL n, m;
LL dis[maxn], DIS[maxn], vis[maxn];
priority_queue<pair<LL, LL> > q;
void dijkstra(LL s, LL dis[]){
memset(vis, 0, sizeof(vis));
dis[s]=0;
q.push(make_pair(-dis[s], s));
while(!q.empty()) {
int now=q.top().second;
q.pop();
if(vis[now]) continue;
vis[now]=1;
int len=e[now].size();
for(int i=0;i<len;i++){
LL v=e[now][i].first;
if(!vis[v]&&dis[v]>dis[now]+e[now][i].second){
dis[v]=dis[now]+e[now][i].second;
q.push(make_pair(-dis[v], v));
}
}
}
}
void dijkstra2(LL s, LL dis[]){
memset(vis, 0, sizeof(vis));
dis[s]=0;
q.push(make_pair(-dis[s], s));
while(!q.empty()) {
int now=q.top().second;
q.pop();
if(vis[now]) continue;
vis[now]=1;
int len=e2[now].size();
for(int i=0;i<len;i++){
LL v=e2[now][i].first;
if(!vis[v]&&dis[v]>dis[now]+e2[now][i].second){
dis[v]=dis[now]+e2[now][i].second;
q.push(make_pair(-dis[v], v));
}
}
}
}
struct node{
LL x, y, z;
node(LL x1, LL y1, LL z1){
x=x1, y=y1, z=z1;
}
node(){
}
}E[200005];
int main(){
LL n, m; scanf("%lld%lld", &n, &m);
for(LL i=0;i<maxn;i++){
dis[i]=1ll<<60;DIS[i]=1ll<<60;
}
for(LL i=1;i<=m;i++){
LL x, y, z;
scanf("%lld%lld%lld",&x,&y,&z);
e[x].push_back(make_pair(y ,z));
e2[y].push_back(make_pair(x ,z));
E[i]=node{x, y, z};
}
dijkstra(1, dis);
dijkstra2(n, DIS);
int q; scanf("%d", &q);
while(q--){
int k; scanf("%d", &k);
if(dis[E[k].y]+DIS[E[k].x]+E[k].z<dis[n]){
printf("YES\n");
}
else{
printf("NO\n");
}
}
return 0;
}
思路一：字符串哈希。二分x用哈希在找是否存在k个没有重叠的长度为x的字符串。
对于同一个字符的若干位置[l, r]我们按r排序贪心就可以了。但是我们不知道这个子串具体是哪段。我们用map保存所有的子串的r位置和可以选取的个数就可以了。
思路二：后缀数组得到height[i]>=mid的一个区间。对区间的SA位置进行排序贪心就可以。得到最多的选取的个数就可以了。
复杂度都是O(n * logn * logn)
思路一：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1e6+10;
LL mod[2]= {1610612741, 998244353};
LL base[2] ={131, 233};
LL p[2][maxn];
LL g[2][maxn];
char s[200005];
void getp(){
p[0][0]=p[1][0]=1;
for(int i=1; i<maxn; i++){
p[0][i]=p[0][i-1]*base[0]%mod[0];
p[1][i]=p[1][i-1]*base[1]%mod[1];
}
}
pair<LL, LL> Hash(char s[]){
int len=strlen(s+1);
g[0][0]=0, g[0][1]=s[1];
g[1][0]=0, g[1][1]=s[1];
for(int i=2; i<=len; i++){
g[0][i]=(g[0][i-1]*base[0]+s[i])%mod[0];
g[1][i]=(g[1][i-1]*base[1]+s[i])%mod[1];
}
return {g[0][len], g[1][len]};
}
pair<LL, LL> getLR(int l, int r){
LL ans1=((g[0][r]-g[0][l-1]*p[0][r-l+1])%mod[0]+mod[0])%mod[0];
LL ans2=((g[1][r]-g[1][l-1]*p[1][r-l+1])%mod[1]+mod[1])%mod[1];
return {ans1, ans2};
}
map<pair<LL, LL>, pair<int,int> > mp;
int slove(int mid, int n, int k){
int res=0;
for(int i=mid; i<=n; i++){
pair<LL, LL> now=getLR(i-mid+1, i);
if(mp.count(now)){
if(i>=mp[now].first+mid){
mp[now]=make_pair(i, mp[now].second+1);
res=max(res, mp[now].second);
}
}
else{
mp[now]=make_pair(i, 1);
res=max(res, 1);
}
}
mp.clear();
return res>=k;
}
int main(){
getp();
int n, k; scanf("%d%d", &n, &k);
scanf("%s", s+1);
Hash(s);
int len=strlen(s+1);
int l=0, r=len/k, x=0;
while(l<=r){
int mid=(l+r)/2;
if(slove(mid, len, k)){
l=mid+1; x=mid;
}
else{
r=mid-1;
}
}
cout<<x<<endl;
return 0;
}
思路二：
//#pragma GCC optimize(3,"Ofast","inline")
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define Mid ((l+r)/2)
#define pb push_back
#define mp make_pair
#define ls ((rt)<<1)
#define rs ((rt)<<1|1)
#define sq(u) ((u)*(u))
#define Abs(u) ((u)>0?(u):-(u))
#define ze(u) (Abs(u)<eps)
#define eq(u, v) (ze((u)-(v)))
#define Sgn(u) ((u)>eps?1:((u)<-eps?-1:0))
typedef long long LL;
typedef unsigned long long UL;
typedef double DB;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const DB eps = 1e-8;
const DB pi = acos(-1.0);
const int N = (int)2e5;
const int M = (int)12;
const int mxn = N + 5;
const int mxm = M + 5;
//以下为倍增算法求后缀数组
int wa[mxn], wb[mxn], wv[mxn], Ws[mxn];
int cmp(int* r, int a, int b, int l)
{
return r[a] == r[b] && r[a + l] == r[b + l];
}
/**< 传入参数：str,sa,len+1,ASCII_MAX+1 */
void da(const char r[], int sa[], int n, int m)
{
int i, j, p, * x = wa, * y = wb, * t;
for (i = 0; i < m; i++) Ws[i] = 0;
for (i = 0; i < n; i++) Ws[x[i] = r[i]]++;//以字符的ascii码为下标
for (i = 1; i < m; i++) Ws[i] += Ws[i - 1];
for (i = n - 1; i >= 0; i--) sa[--Ws[x[i]]] = i;
/*cout<<"SA"<<endl;;
for(int i=0;i<n+1;i++)cout<<sa[i]<<' ';*/
for (j = 1, p = 1; p < n; j *= 2, m = p)
{
for (p = 0, i = n - j; i < n; i++) y[p++] = i;
for (i = 0; i < n; i++) if (sa[i] >= j) y[p++] = sa[i] - j;
for (i = 0; i < n; i++) wv[i] = x[y[i]];
for (i = 0; i < m; i++) Ws[i] = 0;
for (i = 0; i < n; i++) Ws[wv[i]]++;
for (i = 1; i < m; i++) Ws[i] += Ws[i - 1];
for (i = n - 1; i >= 0; i--) sa[--Ws[wv[i]]] = y[i];
for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++)
x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
}
return;
}
int sa[mxn], Rank[mxn], height[mxn];
//求height数组
/**< str,sa,len */
void calheight(const char* r, int* sa, int n)
{
int i, j, k = 0;
for (i = 1; i <= n; i++) Rank[sa[i]] = i;
for (i = 0; i < n; height[Rank[i++]] = k)
for (k ? k-- : 0, j = sa[Rank[i] - 1]; r[i + k] == r[j + k]; k++);
for (int i = n; i >= 1; --i) ++sa[i], Rank[i] = Rank[i - 1];
}
char str[mxn];
int f[mxn];
vector<int> v;
int slove(int mid, int n, int kk){
int l=0, r=0, res=0;
for(int i=1; i<=n; ){
if(height[i]>=mid){
l=r=i;
while(r<=n&&height[r]>=mid){
r++;
}
r--; l--;
for(int i=l; i<=r; i++){
v.push_back(sa[i]);
}
sort(v.begin(), v.end());
int now=-1<<30, ans=0;
for(auto x: v){
if(x>=now+mid){
ans++;
now=x;
}
}
res=max(res, ans);
i=r+1;
v.clear();
}
else{
i++;
}
}
if(res>=kk){
return 1;
}
else{
return 0;
}
}
int main()
{
//int T; scanf("%d", &T);
//int n; scanf("%d", &n);
int n, k;
scanf("%d %d", &n, &k);
scanf("%s", str);
int len = n;
da(str, sa, len + 1, 130);
calheight(str, sa, len);
int l=1, r=(len/k), ans=0;
while(l<=r){
int mid=(l+r)/2;
if(slove(mid, len, k)){
l=mid+1;
ans=mid;
}
else{
r=mid-1;
}
}
cout<<ans<<endl;
return 0;
}
/*
7 4
abbabab
*/
京公网安备 11010502036488号